# Echelon form of matrix have the same rank, after operations modulo

In my homework task, I need to prove that if my matrix have rank $k$ modulo $\ell$, then it also have rank $k$ modulo $p$. Please give me advice, how to prove it.

--edit--

On the diagonal of square matrix of order $n$ are $0$s, other places are $1$ or $2012$. Prove that the rank of this matrix is $n$ or $n-1$. Consider modulo function.

-
Yes. The specific case is square matrix modulo 1 and modulo 2012. –  Jonny Jan 9 '13 at 9:39
The statement in general is false. For instance, consider the scalar case where $A=2$. Then $A$ modulo $2$ has rank $0$, but $A$ modulo $4$ has rank $1$. I suggest you to mention the specific case in the question, too. –  user1551 Jan 9 '13 at 9:51
Yes, sorry. That's order n –  Jonny Jan 9 '13 at 10:11

For any nonnegative integer matrix $A\in\mathbb{R}^{n\times n}$ and any natural number $p\ge2$, let "$A\operatorname{mod}p$" denotes matrix in $\mathbb{R}^{n\times n}$ whose entries are the remainder of the entries of $A$ divided by $p$. We have the following lemma:

Lemma. $\operatorname{rank}(A) \ge \operatorname{rank}(A\operatorname{mod}p)$.

Hint: For any square matrix $B$, we have $\det(B) \equiv \det(B\operatorname{mod}p)\,\operatorname{mod}\,p$. Now recall that the rank of a matrix is the size of its maximal square submatrix with nonzero determinant.

We now turn to your specific case. Call the matrix in question $A$. If $n=1$, clearly $\operatorname{rank}A=0=n-1$. Suppose $n\ge2$. Put $p=2011$ in the above lemma, it suffices to show that $C:=A\operatorname{mod}2011$ is nonsingular. However, note that $C=ee^T-I$, where $e^T=(1,\ldots,1)$. You may prove that $C$ is nonsignular by showing that it is orthogonally similar to a nonsingular diagonal matrix. Alternatively, consider $Cx=0$ and see if there is any nonzero solution $x$.

-
I'm trying to understand this solution. Could You describe, why $C = e e^T - I?$ and if $e^T = diag(1,1,...1)$? –  Jonny Jan 9 '13 at 11:43
What implies the equation, that $C*x=0$? –  Jonny Jan 9 '13 at 11:45
No, $e^T$ is not $\operatorname{diag}(1,1,\ldots,1)$. It is the vector with all ones. For example, $ee^T=\begin{pmatrix}1\\ 1\end{pmatrix}\begin{pmatrix}1&1\end{pmatrix}=\begin{pmatrix}1&1\\ 1&1\end{pmatrix}$. Also, if $C$ is singular, $Cx=0$ must have a nonzero solution. So, to show that $C$ is nonsingular, you may show that $Cx=0$ has no nontrivial solution. –  user1551 Jan 9 '13 at 11:49
So: $ee^T=diag(1,1,1...)$ ? I still don't understand, why I need to show that C is nonsingular. Is the idea to check if the largest submatrix with nonzero determinant will still have nonzero determinant after transformation? It prove us, that the rank of matrix won't be larger than n, If I understand your point. Please tell me more details, what is a general idea of your solution. Thanks in advance! –  Jonny Jan 10 '13 at 0:54
@Jonny How come you think that $ee^T=diag(1,\ldots,1)$?! As I stated previously, $ee^T$ is a square matrix containing all ones, not $diag(1,\ldots,1)$ (the diagonal matrix with unit diagonal entries). As for $C$, the lemma implies $rank(A)\ge rank(C)$. So, if you can show that $C$ is nonsingular, then $A$ is nonsingular too. –  user1551 Jan 10 '13 at 9:34