# Lifting matrices mod 2 to integers.

The following question was motivated by my research.

Consider a $n\times n$ matrix whose elements are $0$'s or $1$'s such that the determinant is odd. The question is: is it possible to assign signs to matrix elements such that the determinant of the matrix will be equal to $1$? I do not know an answer even to a weaker question: is it possible to replace some of the $1$'s in the matrix with odd integers so that the determinant will be equal to $1$?

Remark: it is known that a natural reduction mod $N$ map $SL_n(\mathbb Z) \to SL_n(\mathbb Z/ N\mathbb Z)$ is surjective for any $n,N$.

• I would guess that this (your first question) is unlikely to be true. How hard have you tried to search for a counterexample, either by pure brute force search or by a targeted search of 0-1 matrices with large odd determinant? C.f. mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html – Pete L. Clark Mar 15 '10 at 0:07
• Also the title of your question was confusing to me. Your weaker question has something to do with lifting matrices mod 2 (except that you do not want to change the zero entries by even integers), but your stronger question has nothing to do with it, so far as I can see. – Pete L. Clark Mar 15 '10 at 0:12
• @Pete, I tried to construct a counterexample by hands (I also suppose that answer is negative). Could you, please, explain me why one should try to search a counterexample through matrices with large odd determinant? – Petya Mar 15 '10 at 0:14
• I;ve just tried a brute search for the first version, generating random $01$-matrices. No luck for smallish values of $n$... – Mariano Suárez-Álvarez Mar 15 '10 at 0:30
• Mikola, [[0,1],[1,0]] has determinant -1 but changing the sign of a one yields determinant 1. – Jonas Meyer Mar 15 '10 at 1:18

I believe that the weaker question can be proved by induction on $n$. The case $n=1$ is clear. Now assume for $n-1$ and expand the $n\times n$ determinant by the first row. At least one of the terms in the expansion must be odd. Thus the original matrix $A$ has an $(n-1)\times (n-1)$ submatrix $B$, say consisting of entries not in row 1 or column $j$, with odd determinant such that $A_{1j}=1$. By induction we can change some of the 1's in $B$ to odd integers so that the new matrix $B'$ satisfies det$(B')=1$. Let $A'$ be $A$ after replacing $B$ with $B'$. Now det$(A')= A_{1j} +$ terms not involving $A_{1j}$, say det$(A')=A_{1j}+c$. Since $A_{1j}=1$ and det$(A')$ is odd, it follows that $c$ is even. Hence we can replace $A_{1j}$ with the odd integer $1-c$ so that the resulting matrix has determinant 1.

I want to address the weaker question in a more general setting:

Given any matrix over $\mathbb{Z}$ with determinant $1$ mod $m$. Is it possible to add multiples of $m$ to each entry to get a matrix with determinant one?

Call a matrix transformable, iff this is possible. Given any $A$ matrix over $\mathbb{Z}$. Consider the image of the induced map $\mathbb{Z}^n\rightarrow \mathbb{Z}^n$. It is a submodule of $\mathbb{Z}^n$. For any such submodule with rank $k$ it is always possible to find a basis of $b_1,\ldots,b_n$ of $\mathbb{Z}^n$ and numbers $r_1,\ldots,r_k$, such that $r_i|r_{i+1}$ for $i=1\ldots k-1$ and $r_1b_1,\ldots r_kb_k$ is a basis of the given submodule. The proof of this is roughly the same as the proof of the structure theorem of finitely generated abelian groups.

This tells us, that we can write our matrix $A$ in the form $A=BDC$, where $B$ and $C$ are invertible and $D$ is a diagonal matrix, with the entries $r_1,\ldots ,r_n$ from above. As the determinant is not zero, the image must have full rank and hence $k=n$.

It is easy to see, that left (right) multiplication with invertible matrices doesn't change the transformability. So we might assume, that $A$ has the given form. We will reduce inductively the number of non-one diagonal entries of $A$ without changing the determinant modulo $m$. This number is the length of $\mathbb{Z}^n/Im(A)=\bigoplus_{i=1}^n\mathbb{Z}/r_i$.

Suppose there is a non-one diagonal entry $r_i$. Then there has to be a second one $r_{i'}$, as the product of all diagonal entries is $1$ mod $m$. Otherwise this is the last non-one diagonal entry and it has to be $1$ mod $m$ and we can transform the matrix into the identity matrix.

Now add $m$ to $r_i$ and it will become coprime to the other non-one entry $r_{i'}$, as $r_i|r_{i'}\;,\;gcd(m,r_i)=1=gcd(m,r_i')$. Hence we get $\mathbb{Z}/(r_i+m)\oplus\mathbb{Z}/r_{i'}\cong\mathbb{Z}/((r_i+m)r_{i'})$ Call the resulting matrix $A'$ and observe that the length of $\mathbb{Z}^n/Im(A')$ is one smaller, than the length of $\mathbb{Z}^n/Im(A)$. Then we can again find the normal form for $A'$ and repeat this process until we end up with the identity matrix. Hence every matrix with determinant $1$ mod $m$ is transformable.

• Thank you. See my remark to the original question -- it seems you are proving it. I note that Richard's proof also works for it. – Petya Mar 15 '10 at 16:24
• ahh I see. should read the questions more carefully . . . – HenrikRüping Mar 15 '10 at 16:29
• This is a bit weaker than Petya's original question since there the entries in the lifted matrix are constrained to be 0, 1 or -1. For the proof of the surjectivity of $SL_n(\mathbf{Z})\to SL_n(\mathbf{Z}/N\mathbf{Z})$ my favoured argument goes roughly as follows. Show that $SL_n(\mathbf{Z}/N\mathbf{Z})$ is generated by elementary matrices of the form $I + E_{ij}$ where $E_{ij}$ is a matrix unit with $i\ne j$. As these matrices all lie in the image, the map is surjective. I haven't seen this argument in the textbooks :-) – Robin Chapman Mar 15 '10 at 18:12
• Nice argument, Robin! – Petya Mar 15 '10 at 18:27