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).

  • 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$
    – Chua KS
    Sep 8, 2014 at 13:37
  • 1
    $\begingroup$ Yes, that's more or less implicit in my "note n°2". $\endgroup$
    – Oblomov
    Sep 8, 2014 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$
    – Chua KS
    Sep 8, 2014 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, 2014 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, 2014 at 15:01

1 Answer 1


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$.]

  • $\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, 2014 at 8:34
  • $\begingroup$ Indeed, sorry for my delay in reading your answer. $\endgroup$
    – Oblomov
    Dec 17, 2014 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, 2014 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, 2014 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, 2014 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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