7
$\begingroup$

Let $G$ be a $n\times n-$symmetric matrix with integral coefficients and determinant $1$ (i.e. unimodular) such that the associated quadratic form is positive-definite.

I am interested in having an algorithm to find a rational basis of a lattice $L$ such that $G$ is the Gram matrix of $L$. Concretely, this consists in finding a square matrix $M$ (with rational coefficients) such that $G$ factors as $^tM \cdot M$.

Note that:

1) The unimodular condition and Hasse-Minkowski theory predict that this is indeed possible (this is a remark in Serre's course in arithmetics, §1.3.6 p. 86 in the French edition).

2) I demand the matrix $M$ to be square. (For non-square $M$, this is much easier: first by the Gram-Schmidt process, one can assume that $M$ is diagonal (with positive rational entries); then write each diagonal entry as a sums of (at most 4) squares).

$\endgroup$
  • 1
    $\begingroup$ If you do "completing squares" on the quadratic form $f(x)=x^TGx$, you can rewrite it as $x^TGx=\sum D_j(x_j+a_{j,j+1}x_{j+1}+...+a_{j,n}x_n)^2$ where all the coefficients are rationals. This is equivalent to the expression $G=M_1^tDM_1$ where $D$ is diagonal and $M_1$ is triangular. So $M=\sqrt{D}M_1$ but this is not rational because of the square root. $\endgroup$ – user56403 Sep 8 '14 at 13:37
  • 1
    $\begingroup$ Yes, that's more or less implicit in my "note n°2". $\endgroup$ – Oblomov Sep 8 '14 at 13:55
  • $\begingroup$ Yes. Now I understand what you mean : Gram Schmidt is essentially completing squares but how to write 1/7 as a sum of squares of rationals ? $\endgroup$ – user56403 Sep 8 '14 at 14:53
  • $\begingroup$ 1/7=7/49 and 7=2²+1²+1²+1², so 1/7=(2/7)²+(1/7)^2+(1/7)^2+(1/7)^2. $\endgroup$ – Oblomov Sep 8 '14 at 14:59
  • 1
    $\begingroup$ In general, p/q=pq/q^2 and use Lagrange's theorem to decompose a the (positive) numerator as a sum of at most 4 squares. $\endgroup$ – Oblomov Sep 8 '14 at 15:01
3
$\begingroup$

Here is a method.

Let $\mathrm{V}$ be the bilinear space $(\mathbf Q^n, b)$ with Gram Matrix $G$ in the canonical basis.

Let $M_0$ be the lattice $\mathbf Z^n$ on $\mathbf Q^n$. Find a primitive vector $v_0\in M_0$ such that $b(v_0,v_0)$ is a square, say $b(v_0,v_0)=m^2$ in $M_0$ (note that this can be done quite efficiently : use LLL to get a basis of vectors with small norms, take the two* first vectors, study the lattice they generate).

( * Edit 1: in fact you need to take the first 4 vectors ... indeed, there exists (many) $3\times 3$ positive definite Gram matrices that don't represent any square over $\mathbf Q$ ... The simplest example is $7.I_3$.)

( Edit 2: If you don't use this trick, you can arrange so as to find a $v_0$ such that $m=2^s$ ... this will allow you to find an orthonormal basis inside $\mathbf Z[\frac 12]^n$, whose existence is predicted by the Strong Approximation Theorem.)

Let $K_1$ be the lattice made of vectors $w\in M_0$ such that $(v,w)\equiv 0$ mod. $m$.

Let $L_1$ be the lattice $K_1+\mathbf Z\cdot\frac{v_0}{m}$. Then $L_1$ is integral, unimodular, and has a vector of length $1$, namely $w_0:=\frac{v_0}{m}$.

Let $M_1$ be the orthogonal complement of $w_0$ in $L_1$. Then $M_1$ is an $n-1$-dimensional unimodular lattice (contained in the $n-1$-dimensional subspace $<w_0>^\perp$ of $\mathrm{V}$).

Go on to find $v_1\in M_1$, construct $M_2$ and so on ... you're done (the matrix $M$ you were looking for is the inverse of the matrix whose columns are $(w_0,\dots,w_{n-1})$.

[The classification of unimodular lattices shows that at least when $n\leq 7$, you can always arrange so as to have $(v_0,v_0)=1$ (so that $M_1\subset M_0$), and for $n\leq 24$, you can find some $v_0$ with $(v_0,v_0)=4$.]

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Oblomov : I would not like to seem fidgety but ... after one week, what do you think of this answer ? (ok, you had to wait 2 month before getting an answer to your question, so maybe I should expect it will also ask you two month to comment on it ...) $\endgroup$ – few_reps Nov 26 '14 at 8:34
  • $\begingroup$ Indeed, sorry for my delay in reading your answer. $\endgroup$ – Oblomov Dec 17 '14 at 9:15
  • $\begingroup$ I am a bit confused by the first step. My (stupid) question is: why does a positive definite 4-dimensional integral quadratic form represent a square? $\endgroup$ – Oblomov Dec 17 '14 at 9:23
  • $\begingroup$ Ok, I know why it represents a square, but is there an algorithmic way to find such a vector? $\endgroup$ – Oblomov Dec 17 '14 at 9:51
  • $\begingroup$ Yes, even if it is not necessarily efficient : identify successively the spheres of square radii 1,4,9, etc. There are algorithms to do this. $\endgroup$ – few_reps Dec 17 '14 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.