It is classically known that every positive integer is a sum of at most four squares of integers, i.e. every sum of squares of integers is a sum of four squares of integers. Now consider a symmetric $n\times n$ matrix $M$ with integer entries which can be written as $M= Q^{\rm T} Q$ for an $m \times n$ matrix $Q$ with integer entries. Can we bound $m$ in some way? I.e. is there a constant $c(n)\in \mathbb{Z}$ depending only on $n$ such that in this situation we can always find a decomposition $M= \widetilde{Q}^{\rm T} \widetilde{Q}$ for a $c(n) \times n$ matrix $\widetilde{Q}$ with integer entries? What is the smallest possible such constant (perhaps even linear growth?)?


If we look at the same situation over the polynomial ring $\mathbb{R}[T]$ in one variable, we have the following: Every sum of squares in $\mathbb{R}[T]$ is a sum of two squares and one can show that $c(n)$ grows linearly in $n$: $c(n)=2n$. Thus, I hope that a similar result might hold over the integers too. Perhaps $c(n)$ even grows linearly in $n$?


Is someone aware of something in that direction?



"Pythagoras number" for integral matrices
Here is an answer (see the last point). It differs from what I had been claiming in my first post. There I was saying that any positive bilinear module $\Lambda$ over $\mathbf Z[\frac 12]$ was representable by some euclidean module $\mathrm{I}\_n\otimes\mathbf Z[\frac 12]$. This is true (with $n\leq \text{rk}(\Lambda)+3$), but is of no use in our situation. 


Nevertheless the same technics show that any positive bilinear $m$-dimensional module over $\mathbf Z$ is representable by somebody in the same genus than the euclidean module of rank $m+4$. This is proved here in the third point, since it might be of interest.


In terms of matrices, as in the OP, it says that for any symmetric positive definite matrix $M\in\mathrm{Sym}\_m(\mathbf Z)$ there exists a symmetric positive definite matrix $G\in\mathrm{Sym}\_{m+4}(\mathbf Z)$ with determinant $1$ and at least one odd diagonal entry, and a matrix $Q\in \mathrm{Mat}\_{m+4,m}(\mathbf Z)$ such that the following holds :
$$Q^t.G.Q=M\ \ \ .$$


Let $M$ be a positive definite symmetric $m\times m$ matrix. Let $\mathrm{M}$ be the bilinear module $(\mathbf{Z}^m,M)$. The question can be rephrased :


What is the smallest value $n$ such that the standard euclidean bilinear module $\mathrm{I}\_n$ represents $\mathrm{M}$. 


$\blacktriangleright$ First note that in general, such an $n$ doesn't exist. Indeed, a positive definite integral lattice decomposes as the orthogonal sum of indecomposable (for the orthogonal direct sum) lattices in a unique manner. In particular, the only unimodular (i.e. $\det(M)=1$) lattice $\mathrm{M}$ represented by $\mathrm{I}\_n$ are isomorphic to $\mathrm{I}\_m$. 


$\blacktriangleright$ Over $\mathbf Q$, the space $\mathrm{M}\otimes\mathbf Q$ is represented by $\mathrm{I}\_{n}\otimes\mathbf Q$ for some $n\leq m+3$. This follows from the Hasse principle (that implies that a rank $4$ positive definite space represents $1$), Witt cancellation, and the fact that, for example, $(\mathrm{M}\otimes\mathbf Q)^{\perp 4}$ is euclidean, as a computation of Hasse-Minkowski symbols shows.


$\blacktriangleright$ It follows that over $\mathbf Z$, any bilinear module $\mathrm{M}$ is represented by some bilinear module $\mathrm{N}$ lying in the genus of $\mathrm{I}\_{n}$, for some $n\leq m+4$ (the addition of a one dimensional module $\mathrm{I}\_1$ might be necessary when $m+3$ is a multiple of $8$, in order to ensure that $\mathrm{N}$ is odd).


$\blacktriangleright$ Finally, here is an answer to the question. Let $M$ be an $m$-dimensional submodule of $\mathrm{I}\_n$. Let $P$ be its orthogonal. Let $\pi : \mathrm{I}\_n\otimes Q\to M\otimes Q$ be the orthogonal projection. Then $\pi(\mathrm{I}\_n)$ is contained in $M^\sharp$ (the dual lattice of $M$ in $M\otimes \mathbf Q$), and there exists a smallest $d$ such that $M^\sharp\subset d^{-1}M$. Let $S$ be the sphere of unitary vectors in $\mathrm{I}\_n$. Then the vectors of $d.\pi(S)\subset M$ have squared length smaller than $d^2$. If the number of such vectors is smaller than $\mathrm{card}(S)=2^n$, this means that a vector of squared length $2$ in $I\_n$ lies in $P$, so $\mathrm{M}$ is in fact represented by $\mathrm{I}\_{n-2}\perp <2>$. If once again the same phenomenon occurs, then $\mathrm{M}$ is in fact represented by $\mathrm{I}\_{n-4}\perp <2,2>$ which is represented by $\mathrm{I}\_{n-2}$. So what we get is :


Let $d$ be the smallest integer such that $\mathrm{M}^\sharp\subset \frac 1d\mathrm{M}$. Let $B\_d(\mathrm{M})$ denote the number of non-trivial vectors of $M$ in the ball of radius $d$. Let $n\_0$ be the floor of $2+\log\_2(B\_d(\mathrm{M}))$. If $\mathrm{M}$ is represented by $\mathrm{I}\_n$ for some $n$, then $\mathrm{M}$ is represented by $\mathrm{I}\_{n\_0}$.


I hope there are better bounds, but I cannot see how to get them.


