Proving all variables are equal

Question

I came across a puzzle lately.

Let $A$ be a matrix of size $(2n+1)$ by $(2n+1)$. The diagonal of $A$ is all zeros. Every other entry of $A$ is either $+1$ or $-1$. Each row of $A$ sum to zero. In other words, each row has $n$ of $+1$ and $n$ of $-1$.

Now we need to show that the system of equations $$ A (x_1, \dots, x_{2n+1})^T = (0, \dots, 0)^T $$ can always be reduced to $x_1=x_2=\dots=x_{2n+1}$.

This is pretty easy to see for $n=1$. For $n=2$, one can show this by case analysis. (Or simply write a piece of code to exhaustively check all possible $A$). But I was not able to generalize this to arbitrary $n$.

Answer 1

Based on the form of $A$, the condition $A(x_1,\dots,x_{2n+1})^T=0$ translates to:

If you take out any one number from $x_1,\ldots,x_{2n+1}$, then the remaining $2n$ numbers can be halved to have equal sums.

This is clearly invariant on multiplying or adding a same constant to all $x_i$'s.

(1) Assume that all $x_i$'s are integers. If $S$ denotes $x_1 + \cdots + x_{2n+1}$, then $S-x_i$ is even for each $i$, since it is the sum of two equal sums. Thus, all $x_i$'s have same parity.

If all $x_i$'s are even, divide everything by $2$. This (strictly) decreases the absolute values of all $x_i$'s. (except for zeros)

If all $x_i$'s are odd, then perform $x \mapsto (x-1)/2$. This (strictly) decreases the absolute values of $x_i$'s except for zeros and negative ones. If only zeros or negative ones remain, just flip the sign and continue.

Eventually, one will get $(0,0,\ldots,0)$, meaning that if you perform the steps backward, it initially should have been $x_1 = \dots = x_{2n+1}$.

(2) Assume all $x_i$'s are rationals. Then, multiply by some integer to make all $x_i$'s integer and go to step (1).

(3) Finally, since $A$ is a matrix with rational entries, the solution space $Ax=0$ would have rational basis. Therefore, we only need to consider the rational solutions. So everything is done in (2).

Answer 2

It is a really nice problem that used to be presented with small rocks and masses.

What you need to do is to show that the size of the kernel is 1 so that the matrix is of rank n-1. for that you take a minor $D$ of that size and you show that it is invertible.

And now you use a simple trick: you compute $|D|$ in a different field (here we take $\frac{\mathbb{Z}}{2\mathbb{Z}}$). This works because the determinant is invariant over a changement of field (linear combinations for each column)

By doing so all $\pm 1$ becomes 1 and computing the determinant is easy. showing that the determinant is not null there do the trick. the kernel is of size 1 and the solution is the one you found.