Lifting matrices mod 2 to integers.

Question

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

Answer 1

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.

Answer 2

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.