21
$\begingroup$

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

$\endgroup$
11
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 15, 2010 at 0:07
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 15, 2010 at 0:12
  • $\begingroup$ @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? $\endgroup$
    – Petya
    Mar 15, 2010 at 0:14
  • 1
    $\begingroup$ I;ve just tried a brute search for the first version, generating random $01$-matrices. No luck for smallish values of $n$... $\endgroup$ Mar 15, 2010 at 0:30
  • 2
    $\begingroup$ Mikola, [[0,1],[1,0]] has determinant -1 but changing the sign of a one yields determinant 1. $\endgroup$ Mar 15, 2010 at 1:18

2 Answers 2

26
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Petya
    Mar 15, 2010 at 16:24
  • $\begingroup$ ahh I see. should read the questions more carefully . . . $\endgroup$ Mar 15, 2010 at 16:29
  • 3
    $\begingroup$ 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 :-) $\endgroup$ Mar 15, 2010 at 18:12
  • $\begingroup$ Nice argument, Robin! $\endgroup$
    – Petya
    Mar 15, 2010 at 18:27

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.