Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.