Pages

Thursday, May 20, 2010

Cannot be all negative

Suppose $a_1,a_2,a_3,a_4$ and $b_1,b_2,b_3,b_4$ are eight real numbers. Prove that there is $i,j$ distinct indices such that $a_ia_j + b_ib_j \geq 0$.

Advanced version:
Suppose $a_i,b_i,c_i, 1 \leq i \leq 5$ are fifteen real numbers. Prove that there is $i,j$ distinct indices such that $a_ia_j + b_ib_j + c_ic_j \geq 0$.

General version:
Suppose $A_{i,j}, 1 \leq i \leq n, 1 \leq j \leq n+2$ is a matrix of $n \times (n+2)$ real numbers, prove that there are two columns $p,q$ such that their dot product is non-negative. That is:
$$\sum_{i=1}^{n} A_{i,p} A_{i,q} \geq 0$$

Also find an example of a $n \times (n+1)$ matrix where this property does not hold

A geometric interpretation of this problem is that, given $n+2$ vectors in $n$-dimensional space, two of them must form an angle of 90 degrees or less.

No comments:

Post a Comment