vector subspace of K^30 where K is a nf of degree 20

[Vincent Delecroix]

Dear linear algebra specialists,

I am stuck with an elementary linear algebra problem where
Sage is (for now) of no help. I want to compute the rank of
a 30 x 30 dense matrix over a number field of degree 30.

sage: x = polygen(QQ, 'x')
sage: K = NumberField(x^30 - 3, 'a')
sage: M = MatrixSpace(K, 30)
sage: m = M.random_element()
sage: m.rank()

See also

https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/

Any hint?

Best
Vincent

[David Roe]

For matrices over Q there's sage.matrix.misc.matrix_rational_echelon_form_multimodular, which is the default for matrices with more than 25 rows/columns.  It should be possible to adapt this to number fields.

You might also look into what Pari is capable of, since we're getting our number fields from there and they probably need to do linear algebra with number fields.

David

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/2f5b1208-e65e-d603-0b73-91121eacb591%40gmail.com.

[Nils Bruin]

On Tuesday, April 7, 2020 at 3:10:00 PM UTC-7, David Roe wrote:

For matrices over Q there's sage.matrix.misc.matrix_rational_echelon_form_multimodular, which is the default for matrices with more than 25 rows/columns.  It should be possible to adapt this to number fields.

In particular, by Weil restriction you can consider your matrix as a matrix over Q. You'll get a subspace of Q^(20*30), but the multimodular methods implemented for that should be able to get you good rank information fairly quickly: the rank over K should just be that rank divided by 20 (if it doesn't come out as a multiple of 20, something went wrong).

[Vincent Delecroix]

Hi Nils,

How do you make the Weil restriction happen? Is this the following

Let K = Q[a] be of degree d. For each row v of the matrix, make
d new rows for the new matrix with a, a*v, a^2*v, ..., a^(d-1)*v
seen as elements of Q^(d * ncols).

If so, I will give it a try. One inconvenient with this approach is
that you are duplicating a lot the information. A priori, the data
fits into QQ^(nrows * ncols * d) but the above procedure constructs
a matrix over QQ^(nrows * ncols * d * d). As you said, we get d times
the rank in the end.

Best
Vincent

PS: In PARI there is a bunch of ZabM_* functions that works over
cyclotomic fields (though not available in GP). We also have
something in Sage specialized for cyclotomic field. I am
investigating on this side as well (my fields are subfields
of cyclotomic fields that gives an extension at most 4).

[Nils Bruin]

On Tuesday, April 7, 2020 at 11:42:41 PM UTC-7, vdelecroix wrote:

Hi Nils,

How do you make the Weil restriction happen? Is this the following

   Let K = Q[a] be of degree d. For each row v of the matrix, make
   d new rows for the new matrix with a, a*v, a^2*v, ..., a^(d-1)*v
   seen as elements of Q^(d * ncols).

Exactly. If you're worried about space usage and are happy to only be morally sure of your answer, you can reduce the matrix modulo a whole bunch of primes and compute the rank there. Over finite fields (also non-primitive ones), I'm sure the rank computation shouldn't be a huge hurdle.

The rank bound in reduction will be a lower bound on the rank. If you compute enough primes, then it will also be an upper bound: you can bound the height of the rxr minors, so if you're finding that they're all zero modulo enough primes that the smallest non-zero field element that reduces to 0 modulo all the primes you have selected exceeds that bound, then you've proven the rank isn't larger than what you've found. That's basically what the multimodular algorithms would do, so it's probably way less work to convert to a matrix over Q.