Rank of a matrix with diagonal entries $0$ and $\pm 1$ outside of the diagonal.

Question

Let $n$ be an odd number. Let $A$ be an $n \times n$ matrix with diagonal entries equal to $0$ and off-diagonal entries in $ \{1,-1\}$. Each row of $A$ has the same number of $1$s and $-1$s. Show that $$\text{rank} (A)=n-1$$

---

Clearly, adding all rows to the last row, gives $0$ row, so $\text{rank} (A)\leq n-1 $. However, how to show the $\text{rank} (A)\geq n-1$?

Answer 1

I remember a very nice formulation of this problem. You have an odd number of rocks such that if you take any rock out, you can separate the rest in two bags of the same number of rocks that have the same weight. Prove that all rocks have the same weight.

Indeed, the vector of weights of rocks $w$ is such that $Aw=0$ for a matrix $A$ verifying the conditions in your question. We need to prove that $\text{rank}(A) = n-1$ to guarantee that $w$ is proportional to the vector $(1, \dots, 1)$.

---

Here is the proof.

Since there are the same number of $-1$ and $1$ on each row, the vector $v_n = (1,\dots, 1)$ verifies $Av = 0$, so $\text{rank}(A) \leq n-1$. Now let $A'$ be the submatrix consisting of the first $n-1$ lines and $n-1$ columns. The determinant of $A'$ is equal modulo 2 to the determinant of the matrix $B = J_{n-1} - I_{n-1}$ with $J_{n-1}$ the matrix with ones everywhere. The eigenvalues of $B$ are $n-2$ for the vector $v_{n-1} = (1,\dots, 1)$ and $-1$ for all vectors that are orthogonal to $v_{n-1}$, so $\text{det}(B) = (n-2)(-1)^{n-2}$, which is odd. Thus $\text{det}(A')$ is also odd, so it is not null. We can conclude that $\text{rank}(A) = \text{rank}(A') = n-1$.

Answer 2

More generally next statement hold.Your problem is easily proved using it. becaus you already know $rank(A)\leq n-1$
(Prop)
Let $A$ be a $n\times n$ matrix such that
(a)Every diagonal element is even integer.
(b)Other elements are odd integer.
Then
(1)Then $det(A) \equiv n+1$ (mod.$2$)
(2)$rank(A)=n$ is $n$ if even, $rank(A)\geq n-1$ if $n$ is odd.

(proof) At first we will prove (2) using (1). If $n$ is even we know $det(A) \neq 0$ by (1).So $rank(A)=n$. If $n$ is odd, let consider the submatrix $A'$ of A which is from (1st to $n-1$th row part) $\times$ (from 1st to $n-1$th column part) of A. $A'$ is $(n-1)\times(n-1)$ matrix so $rank(A')=n-1$ for $n-1$ is ever. Hence $rank(A) \geq n-1$.
Well,let show (1).Let consider $A$ in $R=Mat(n,F)$ where $F$ is finite field with order $2$ i.e. $F=\mathbb{Z}/2\mathbb{Z}$.We write $A'$ as $A$ in $R$. Then the form of $A'$ is very simple.That is
(a)Every diagonal element is 0 (in $F$).
(b)Other elements are 1 (in $F$).
Then the fact that determinant of $A'$ is $n+1$ can be prove as followings.
(step1)Substract $1$-st column vector from $j$-th column vector for $n\leq j>1$.
(step2) Substract $1$-st row vector from $i$-th row vector for $n\leq i>1$.
Then we get lower triangular matrix $A''$ with diagonal element $-(n-1),1,1,...,1$. Then $det(A')=det(A'')=-(n-1)=n+1$ (in $F$).So we proved $det(A) \equiv n+1$ (mod.$2$).

Sorry for my poor English....