This is a replay of a problem recently posed by @Algebra-Math-Arash.
I was the only one to post an answer, and although my posted proof had a few gaps (helpfully identified by @Andreas Blass), it was, I think, basically correct.
However the OP showed no work, so the question was closed for lack of context, and eventually deleted.
Shown below is a revised (hopefully correct) version of my prior proof.
What I'm looking for in this thread are two things:
- Is my proof correct?$\\[8pt]$
- Is there an alternative, perhaps simpler approach?
OK, so here's the problem, followed by my proposed proof . . .
Problem:
Show that if $A$ is the adjacency matrix of a simple graph $G$ of order $n$, then the rank of $A$ in $M_n(\mathbb{Z}_2)$ is even.
Proof:
Proceed by induction on $n$.
If $n=1$, then $A=0$, so the rank of $A\;$is zero, hence is even.
Next, let $n > 1$, and assume the claimed result is true for all simple graphs of order $n-1$.
Let $r\;$be the rank of $A\;$in $M_n(\mathbb{Z}_2)$.
Suppose $r\;$is odd.
Our goal is to derive a contradiction.
Claim $r < n$.$\;$Consider two cases . . .
Case $(1)$:$\;n\;$is even.
Then since $r\;$is odd, we must have $r < n$.
Case $(2)$:$\;n\;$is odd.
Temporarily regard $A\;$as an element of $M_n(\mathbb{Z})$, and let $S\;$be the element of $M_n(\mathbb{Z})$ whose entries are the same as $A\;$except negated below the main diagonal. Then $S\;$is skew-symmetric, hence, since $n\;$is odd, it follows that in $M_n(\mathbb{Z})$, we have $\det(S)=0$.
By considering the sum of signed products of generalized diagonals, it follows that $\det(A) \equiv \det(S)\;(\text{mod}\; 2)$, so $\det(A)$ is even.
Returning to $M_n(\mathbb{Z}_2)$, we have $\det(A) = 0$, hence $r < n$.
Thus, in both cases, we have $r < n$.
Since $r < n$, there is some vertex $v$ of $G$ such that the row of $A$ corresponding to $v$, row $i$ say, is dependent on the other rows of $A$. Then, since $A$ is symmetric, column $i$ of $A$ is dependent on the other columns of $A$.
Deleting row $i$ from $A$ yields an $(n{-}1){\times}n$ matrix, $B_1$ say.
Since row $i$ in $A$ is dependent on the other rows of $A$, it follows that $\text{rank}(B_1)=\text{rank}(A)$.
The dependency relation for column $i$ in $A$ still holds for column $i$ in $B_1$, hence if you delete column $i$ from $B_1$, you get an $(n{-}1){\times}(n{-}1)$ matrix, $B_2$ say, such that $\text{rank}(B_2) = \text{rank}(B_1)$.
Thus, $\text{rank}(B_2) = r$.
But $B_2$ is the adjacency matrix for $G-v$, hence by the inductive hypothesis, the rank of $B_2\;$in $M_{n-1}(\mathbb{Z}_2)$ is even, contrary to the assumption that $r$ is odd.
Thus, the induction is complete.
This completes the proof.