Calculating the rank of a particular singular matrix

Question

Question. Let $A=(a_{ij})\in\mathbb R^{(2n+1)\times (2n+1)}$, while $a_{ii}=0$, for all $i=1,\ldots,2n+1$, and $a_{ij}\in\{-1,1\}$, if $i\ne j$. If $$ \sum_{j=1}^{2n+1}a_{ij}=0, \quad \text{for all $i=1,\ldots,2n+1$}, $$ show that $\mathrm{Rank}(A)=2n$.

Clearly, $A\boldsymbol{u}=0$, where $\boldsymbol{u}=(1,1,\ldots,1)$, and hence $\mathrm{Rank}(A)\le 2n$, and $\mathrm{Ker}A\ne\{0\}$. Another piece of information which could be useful is that the kernel of $A$ is spanned by eigenvectors with rational (or even integer) elements.

Answer 1

Let $M$ be the leading principal $2n\times2n$ submatrix of $A$. Then $M\equiv I_{2n}-\mathbf1\mathbf1^T$ modulo $2$ and in turn, $\det(M)\equiv1-\mathbf1^T\mathbf1\equiv1$ modulo $2$. Hence $\det(M)$ is an odd integer and the rank of $A$ is at least $2n$.

Answer 2

First of all, this question originates from the following old Soviet Olympiad problem (see also here):

Given 13 gears each weighing an integral number of grams. It is known that any twelve of them may be placed on a pan balance, six on each pan, in such a way that the scale will be in equilibrium. Prove that all these gears must be of equal weight.

It turns out that the requirement the the gears should be integral numbers of grams can be relaxed. It is still true even if the gears are real numbers of grams. Also the number 13 could be replaced by any odd positive integer.

If $\boldsymbol v=(v_1,\ldots,v_{13})$ a set of gears satisfying the requirements of the problem, then the vector $\boldsymbol v\,$ belongs to the kernel of a $13\times13$ matrix $A$ of the form of the OP. Clearly, $(1,1,\ldots,1)\in \mathrm{Ker}\,A$. It suffices to show that $\mathrm{Rank}(A)=12$.

Assume now we have proved the case in which the gears are integers. (See here.) We next observe that the Kernel of $A$ is spanned by vectors with rational elements (i.e., using Gauss-Jordan). In fact, it is spanned with vectors with integral elements. But the only such vectors with integer elements are the multiples of $(1,1,\ldots,1)$.