4
$\begingroup$

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

  • 0
    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$.2011-03-28

1 Answers 1

1

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?

  • 0
    @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.2011-03-08
  • 0
    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.2011-03-08
  • 0
    Is my proof rigorous? Can the proof be further refined?2011-03-08
  • 0
    @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.2011-03-08
  • 0
    @Moron: it suddenly occurs to me: is this the unique solution to this problem?2011-03-26
  • 0
    @Shiyu: I don't think so. $1,2,3,4$ we can get two triangles: $1+2,3,4$ and $2,1+3,4$2011-03-26