# Finding more non-trivial solutions to a system of linear algebraic equations

Suppose we have a system of $n$ linear algebraic equations in $n$ unknowns, where $n > 1$ is a positive odd integer. The matrix $A = \{a_{ij}\}_{i,j=1}^n$ of this system has the following properties:

• $a_{ii}=0$ for every $i=1,\ldots,n$, i.e., $A$ has zeros on the main diagonal

• $a_{ij} \in \{\pm 1\}$ for every $i\neq j$

• $\sum_{j=1}^n a_{ij}=0$ for every $i=1,\ldots, n$, i.e., the sum of every row is zero

This system has an evident solution $C(1,\ldots,1)^T$ for any $C\in\mathbb{R}$. For $n=3,5$ it is the only series of solutions and $\mathrm{rank}A=n-1$ (I wrote a small program that brute-forces all combinations). Is it true for any odd $n\in \mathbb{N}$? If not, then for each $n$ we have $\mathrm{rank}A<n-1$?

Edit: I posted an answer for the case when $A\in M_n(\mathbb{Q})$. But can we conclude from it the result for the case $A\in M_n(\mathbb{R})$? The latter would mean also that the result stands for the case $A\in M_n(\mathbb{C})$, since $\mathbb{C}=\mathbb{R}+i\mathbb{R}$.

• Can you show us your calculation for $n=1,3,5$? I don't see how you can have $\mathrm{det}A\neq 0$ with sum of every row is zero. – Sungjin Kim Jul 24 '16 at 1:33
• Replace the first column vector by the sum of all column vectors, you get a matrix having same determinant as $A$ but with all zeros in first column... So $\det A = 0$. – achille hui Jul 24 '16 at 2:18
• @i707107, you're right, sorry, I got confused. I edited the question, the problem appears to be deeper. – Glinka Jul 24 '16 at 2:33
• @achillehui, true, thank you. I couldn't figure out what I was trying to achieve. I've edited the question, now it's better – Glinka Jul 24 '16 at 5:03
• @i707107, I think I figured this out. Could you please take a look? – Glinka Jul 24 '16 at 8:17

## Partial answer (over $\mathbb{Q}$)

The system has no solutions in $\mathbb{Q}^n\setminus \langle(1,\ldots,1)^T\rangle_\mathbb{Q}$, so $\mathrm{rank}A=n-1$ for all odd $n>1$.

Suppose $v\in\mathbb{Q}^n\setminus \langle(1,\ldots,1)^T\rangle_\mathbb{Q}$ is a solution of our system, i.e. $Av=(0,\ldots,0)^T$. Let's consider $z=\mathrm{lcm}(q_1,\ldots,q_n)\cdot v$, where $v_i=p_i/q_i$ is the $i$-th component of $v$, and $p_i,q_i\in\mathbb{Z}$.

Now we have $z\in\mathbb{Z}^n\setminus \langle(1,\ldots,1)^T\rangle_\mathbb{Q}$, denote $z=(z_1,\ldots,z_n)^T$. Among $z_1,\ldots,z_n$ we have odd amount $k$ of numbers of one parity and even amount $p$ of numbers of another parity. If $p>0$ then we could choose $z_i$ of that parity and $i$-th component of $Az$ would be odd (as a sum of odd amount of odd numbers and odd amount of even numbers); and so $Az\neq (0,\ldots,0)^T$. Thus $p=0$ and all $z_i$ have the same parity.

Let's consider $\tilde{z}=z-(\min z_i,\ldots,\min z_i)^T$. Since both vectors in the right side are solutions, so as $\tilde{z}$. At least one component of $\tilde{z}$ is zero, but not all of them; all components of $\tilde{z}$ are even. We divide $\tilde{z}$ by $2$ until at least one of the components becomes odd. Zero component remains zero, thus even. But earlier was established that all components of the integer solution must be of the same parity. Contradiction.