# Sufficient condition for existence of solution for linear system

Let $\sigma_{ij}, \ i,j=1,\ldots,n$ ($n \geq 4$) be a sequence of positive real numbers such that $\sigma_{ij}=\sigma_{ji}$. Do you know any sufficient condition on $\sigma_{ij}$ (which is simpler than the system itself) such that the linear system of equations

$$a_i+a_j=\sigma_{ij},\ i,j=1,\ldots,n, i \neq j$$

admits at least a solution? Thank you.

-
The following "4-cycle condition" is clearly necessary: $\sigma_{ij} + \sigma_{kl} = \sigma_{jk} + \sigma_{li}$ for all distinct ordered 4-tuples $(i, j, k, l)$. I think this is sufficient as well, but I don't have a proof at hand. – Srivatsan Jan 30 '12 at 15:02

Following Srivatsan's comment, the condition is also sufficient. We can prove it by induction on $n$. The case $n=4$ is easy to deal with.
Suppose that for $n$ the 4-cycle condition $\sigma_{ij}+\sigma_{kl}=\sigma_{jk}+\sigma_{li}$ implies the existence of a solution.
For $n+1$, if the 4-cycle condition is satisfied, by the hypothesis induction there are $a_1,...,a_n$ such that $a_i+a_j=\sigma_{ij},\ i,j=1..n, i \neq j$. Now we are left to pick $a_{n+1}=\sigma_{i(n+1)}-a_i$. For $a_1,...,a_n,a_{n+1}$ to be a solution for the system it is enough to prove that $a_{n+1}$ given by the above relation is the same for every $i=1..n$.
We have $\sigma_{i(n+1)}-a_i=\sigma_{j(n+1)}-a_j \iff \sigma_{i(n+1)}+\sigma_{jk}=\sigma_{j(n+1)}+\sigma_{ik}$, which is true by the 4-cycle condition.