# Does there exist a 4 vectors are linearly independent modulo 2 but not linearly indepdent integrally?

Does there exist a $4\times 4$ matrix with 0's and 1's as entries, which is row equivalent to the identity matrix modulo 2, but is not row equivalent to the identity matrix when working with the integers?

Equivalently, does there exist four vectors $a,b,c,d$, each with four components with 0's and 1's as entries, such that $a,b,c,d$ are linearly independent over ${\mathbb{Z}}/2$, but not linearly indepdent over ${\mathbb{Z}}?$

• I would say no, because if you have a linear dependance relation of these vectors in $\mathbb{Z}$, either at least one of the coefficients is odd, or if they are all even, you can always divide all the relation by two, this until you get at least one odd coefficient, which gives you dependance relation in $\mathbb{Z}/2\mathbb{Z}$ when taking modulo $2$ – yago May 12 '14 at 9:58

## 1 Answer

Regarding your second question:

Let $A=(a_{ij})\in M_n(\mathbb{Z})$. Denote by $\overline{A}=(a_{ij}\ mod_2)\in M_n(\mathbb{Z}_2)$.

Notice that $det(\overline{A})=det(A)\ mod_2$.

If the rows of $A$ are linear dependent over $\mathbb{Z}$ then $det(A)=0$ then $det(\overline{A})=0$. Thus, the rows of $\overline{A}$ are linear dependent over $\mathbb{Z}_2$.

Regarding your first question:

If $A=(a_{ij})\in M_n(\mathbb{Z})$ is row equivalent to the identity(using only operations with integers) then $A$ has an inverse in $M_n(\mathbb{Z})$.

Thus, $det(A)det(A^{-1})=1$. Since $det(A),det(A^{-1})\in \mathbb{Z}$ then $det(A),det(A^{-1})$ are 1 or -1.

Thus, you need more than only $det(A)\neq 0$ for $A$ to be row equivalent(using only operations with integers) to the identity. It is necessary that $det(A)=1$ or $-1$.

This site, http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html , says that the maximum determinant for binary matrices $(a_{ij}=0$ or $1)$ of order 4 is 3. Thus, exists a binary matrix $A$ of order 4, with determinat equals to $3$, that is not row equivalent to the identity in $M_4(\mathbb{Z})$ but $det(\overline{A})\neq 0\ mod_2$. So, $\overline{A}$ is row equivalent to the identity in $M_4(\mathbb{Z}_2)$ using operations with coefficients in $\mathbb{Z}_2$.

Your first question is not equivalent to the second.

Now, I am not sure if a matrix $A\in M_n(\mathbb{Z})$ with $det(A)=1$ is row equivalent to the identity.

• Thank you for your answer and for giving me awareness of the Hadamard maximal determinant problem. Why does a matrix with entries in ${\mathbb{Z}}$ whose rows are linearly dependent have determinant 0? Do I need to be careful that ${\mathbb{Z}}$ is a ring? – user17982 May 13 '14 at 21:49
• Wikipedia (en.wikipedia.org/wiki/Unimodular_matrix) says that a square matrix with entries in ${\mathbb{Z}}$ has inverse if and only if its determinant is either 1 or $-1$. – user17982 May 13 '14 at 21:56
• @ColinTan If the rows are linearly dependent over $\mathbb{Z}$ then the rows are linear dependent over $\mathbb{Q}$. So the determinant is 0. If the $det(A)=1$ or $-1$ then $A^{-1}=Adj(A)$ or $-Adj(A)$. Notice that $Adj(A)\in\ M_n(\mathbb{Z})$, where $Adj(A)$ means the classical adjoint of $A$. I am not sure if row equivalence to the identity (using only operations with integers) is equivalent to have a inverse in M_n(\mathbb{Z}). Of course if a matrix is row equivalent to the identity then it has a inverse in $M_n(\mathbb{Z})$, but I am not sure if the converse is true. – Daniel May 13 '14 at 22:36
• @ColinTan The converse is also true. I will try to write here the idea. I will perform column operations, because it is easier to write here. – Daniel May 13 '14 at 23:20
• Let $a_{11},...,a_{1n}$ be the first row. Change the order of the columns to obtain $|a_{11}|\geq\ldots\geq|a_{1n}|$. Write $a_1j=m_{1j}a_{1n}+r_j$, where $m_{1j}$ and $r_j$ are integers such that $|r_j|<|a_{1n}|$. Start to subtract multiples of the last column to obtain $r_1,\ldots,r_{n-1},a_{1n}$ as the new first row. Notice that the determinant remains 1 or -1 after these operations. Repeat the process. Eventually you will end with only zeros in the first row and a number different from zero. This number is 1, otherwise the determinant would not be $1$ or $-1$. – Daniel May 13 '14 at 23:27