Rank of a matrix with diagonal elements zero, all other elements either 1 or -1 and row-sum of eash row is 0.

Question

Let A be a $n \times n$ matrix such that:

1) all the diagonal elements are $0$,

2) all other elements are either $1$ or $-1$

3) number of $1$'s in a row are equal to number of $-1$'s in the row, i.e. the row-sum is $0$ for all rows.

It is obvious that $n$ is odd here. I have done some experiments and found that the rank of such an $A$ is always $n-1$. Can someone help me with a proof? I can only see that

\begin{bmatrix} 1 \\ 1\\ \vdots\\ 1\\ 1\\ \end{bmatrix}

is an eigen vector with eigen value =0.

Answer 1

Look at the leading principal $(n-1)\times(n-1)$ submatrix $A_{n-1}$. In modulo-2 arithmetic, $A_{n-1}=ee^T-I_{n-1}$, where $e^T=(1,\ldots,1)$. Its eigenvalues are $n-2$ and $-1$ modulo $2$, which are nonzero because $n$ is odd. So $\det A_{n-1}\ne0$ in modulo-2 arithmetic and $\det A_{n-1}\ne0$ over $\mathbb R$ too. Hence $A_{n-1}$ is nonsingular and $A$ has rank $n-1$.

Answer 2

I'll outline a proof ...

Let $A$ be an $n$ x $n$ matrix of the specified type.

As noted, $n$ must be odd.

Let $B$ be the $(n-1)$ x $(n-1)$ upper left-hand submatrix of $A$.

The determinant of $B$ is the sum of the products of the generalized diagonals.

Of the $(n-1)!$ such products, the nonzero products are odd (equal to either $+1$ or $-1$).

The number of diagonals whose product is nonzero is the number of derangements of $\{1,...,n-1\}.$

Since $n-1$ is even, the number of derangements is odd.

Thus, $\text{det}(B)$ is the sum of an odd number of odd numbers, so is odd, and hence is nonzero.

It follows that $\text{rank}(A) \ge n-1$.

Since the columns of $A$ sum to zero, $\text{rank}(A) \le n-1$.

Therefore $\text{rank}(A) = n-1$.