LLL_gram of matrices with 0 eigenvalues

[Victor Miller]

Suppose that A is an m by n integer matrix.  Its Gram matrix is G = A*A^t.  If A is not full rank, then G has some eigenvalues of 0.  If I do G.LLL_gram() I get a somewhat uniformative error message like:

Value Error: ma matrix from Full MatrixSpace of 10 by 2 dense matrices over Integer Ring cannot be converted to a matrix in Full MatrixSpace of 10 by 10 dense matrices over Integer Ring!

I understand that pari (which is what I understand, actually computes LLL_gram) doesn't like non-definite matrices.  But, in this case it looks like it returned something to SAGE of lower dimension (what?) and SAGE didn't know what to do with it.  Can the error message at least be changed to something more informative.

I've found a work around for some of my matrices:   Let N be some big integer, and let G'= N*G + identity_matrix(G.nrows()).  This perturbs G a little so that the 0 eigenvalues go away.

Victor

[Dima Pasechnik]

On 2013-03-19, Victor Miller <victor...@gmail.com> wrote:
> ------=_Part_554_9793948.1363718282627
> Content-Type: text/plain; charset=ISO-8859-1

>
> Suppose that A is an m by n integer matrix. Its Gram matrix is G = A*A^t.
> If A is not full rank, then G has some eigenvalues of 0. If I do
> G.LLL_gram() I get a somewhat uniformative error message like:
>
> Value Error: ma matrix from Full MatrixSpace of 10 by 2 dense matrices over
> Integer Ring cannot be converted to a matrix in Full MatrixSpace of 10 by
> 10 dense matrices over Integer Ring!
>
> I understand that pari (which is what I understand, actually computes
> LLL_gram) doesn't like non-definite matrices. But, in this case it looks
> like it returned something to SAGE of lower dimension (what?) and SAGE
> didn't know what to do with it. Can the error message at least be changed
> to something more informative.

This is certainly easy to fix, but here is a workaround that seems to
work. Let's make a low rank, say, 3x3 matrix:

sage: A=matrix([[1,2,3]])
sage: G=A.T*A; G
[1 2 3]
[2 4 6]
[3 6 9]
sage: x=G._pari_(); x # this is what PARI will get
[1, 2, 3; 2, 4, 6; 3, 6, 9]
sage: x.lllgram() # compute its LLL in PARI
[1; 0; 0]

HTH,
Dmitrii

[John Cremona]

pari's qflllgram function returns (given input a positive semidefinite
square G, not necessarily positive definite) a "unimodular" U such
that the columns of GT are an LLL-reduced basis for the lattice
spanned by the columns of G. That's from the documentation, but when
G is singular U will not be square, so I would not call it unimodular.

So what is wrong is Sage's interface in the case where G is not
definite. In the lines

MS = matrix_space.MatrixSpace(ZZ,n)
U = MS(U.python())
# Fix last column so that det = +1
if U.det() == -1:
for i in range(n):
U[i,n-1] = - U[i,n-1]
return U

in the first line it should say MatrixSpace(ZZ,n,U.ncols()) and then
the determinant fix should be omitted unless U.nows()==U.ncols().

That would be an easy patch!

John

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Victor Miller]

Thanks Dima and John, In the meantime, since I have Magma available to me I tried to use magma's functions.  What I'm really interested is getting the unimodular (when it makes sense to use that term) transition matrix needed to put a matrix in reduced form.  It looks like, but correct me if I'm wrong, that the only sage function which returns this is LLL_gram.  I looked at the Magma documentation, and saw the the LLL function in Magma returns 3 things: the reduced matrix, the transition matrix, and the rank.  However, when I do that I get a traceback from sage, plus at the end

TypeError: Error evaluating Magma code:
IN:_sage[1]:=[_a : _a in _sage[2]];
OUT:
>> _sage_[1]:=[_a : _a in _sage[2]];
                              ^
Runtime error in for: Iteration is not possible over this object

When I look at the returned value of magma.LLL it only has the reduced matrix.  Is there a way of getting the entire tuple of returned values from magma?

Victor

B,U,rk = magma.LLL(A)

I get a message from sage (it's pretty obscure) saying that it

[Victor Miller]

Aha, I found the nvals= option to magma commands.  So for now I'll use that.  I would like to ask that LLL optionally return the transition matrix (and also BKZ if that's possible).

Victor

On Tuesday, March 19, 2013 2:38:02 PM UTC-4, Victor Miller wrote: