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 $x_i (i=1,...,n, n>d)$ be a unit vector in $R^d$. $c_i>0$ is a positive real scalar. How to prove the following fact?

Fact: There exist some vectors $x_i$ such that $\sum_{i=1}^n c_i x_i=0$ if and only if $c_i\le\sum_{j\neq i}c_j, \forall i$.

The necessity is easy to prove. (My proof of the necessity: If $\sum_{i=1}^n c_i x_i=0$, then $c_i x_i = -\sum_{j\neq i}c_j x_j$. So $\| c_i x_i \|=c_i\le\sum_{j\neq i}\| c_j x_j\|=\sum_{j\neq i}c_j)$.

But how to prove the sufficiency? That is: if $c_i\le\sum_{j\neq i}c_j, \forall i$, can we always find some $x_i$ such that $\sum_{i=1}^n c_i x_i=0$? It seems a very basic result, but not easy to prove for me.

Thank you for your help. Shiyu

share|improve this question
    
The statement could be written a lot clearer. Given the $\{c_i\}$, you are asking when some configuration of $\{x_i\}$ exists. Also, you require $d>1$. The critical case is $d=2$. –  Douglas Zare Mar 28 '11 at 5:10

1 Answer 1

up vote 1 down vote accepted

Hint:

Assume $c_1 \le c_2 \le \dots \le c_n$.

Can you try to find a $k$ such that $c_1 + \dots + c_{k-1}$, $c_k$ and $c_{k+1} + \dots + c_n$ form the sides of a triangle?

share|improve this answer
    
@Moron: Many thanks. My Proof: Firstly if $a=\sum_{i=1}^{k-1}c_i$, $c_k$ and $b=\sum_{i=k+1}^{n}c_i$ can form the sides of a triangle, then we can choose $x_i, i=1,...,k-1$ parallel to the side $a$, $x_k$ parallel to the side $c_k$ and $x_i, i=k+1,...,n$ parallel to the side $b$ such that $\sum_{i=1}^n c_i x_i=0$. This is easy to understand. –  Shiyu Mar 8 '11 at 17:02
    
Secondly, I need to find the $k$. Without loss of generality, assume $c_1\le c_2\le ... \le c_n$ and $\sum_{i=1}^n c_i=1 $. $a, c_k$ and $b$ form the sides of a triangle iff $c_k\le a+b, a\le b+c_k, b\le a+c_k$. Because $c_i\le \sum_{j\neq i}c_j, \forall i$, $c_k\le a+b, \forall k$. Next, since $\sum_{i=1}^n c_i=1$, there exsits $p\le n-1$ such that $\sum_{i=1}^{p}c_i\le 0.5$. Choose $k=max(p)+1$ such that $\sum_{i=1}^{k}c_i\ge 0.5$. Recall $a+c_k+b=1$, so $a\le 0.5$ and hence $a\le 0.5 \le b+c_k$; and $b\le 0.5$ and hence $b\le 0.5 \le a+c_k$. Now we say $a,c_k$ and $b$ form a triangle. –  Shiyu Mar 8 '11 at 17:03
    
Is my proof rigorous? Can the proof be further refined? –  Shiyu Mar 8 '11 at 17:04
    
@Shiyu: You seem to be on the right track! You also have to consider the case when $k=n$, though. You might want to update the question with your thoughts. –  Aryabhata Mar 8 '11 at 17:13
    
@Moron: it suddenly occurs to me: is this the unique solution to this problem? –  Shiyu Mar 26 '11 at 2:31

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.