# Thread: Algebra, Problems For Fun (25)

1. ## Algebra, Problems For Fun (25)

This problem is a generalization of this simple fact that if $\displaystyle \{a_1,a_2,a_3 \} \subset \mathbb{R},$ then $\displaystyle a_ia_j \geq 0$ for some $\displaystyle i \neq j$:

Let $\displaystyle u_1, \cdots , u_{n+2}$ be any $\displaystyle n+2$ vectors in $\displaystyle \mathbb{R}^n.$ Show that $\displaystyle u_i \cdot u_j \geq 0$ for some $\displaystyle i \neq j.$

Suggestion:

Spoiler:
A clever induction over $\displaystyle n.$

2. Thanks for this nice problem!

By induction over $\displaystyle n$:
- obvious if $\displaystyle n=0$ ($\displaystyle \mathbb{R}^0=\{0\}$: the 0-dimensional vector space)
- take $\displaystyle n\geq 1$ and assume this is true for $\displaystyle n-1$: among any $\displaystyle (n+1)$-uplet of vectors in $\displaystyle \mathbb{R}^{n-1}$ (or in any $\displaystyle (n-1)$-dimensional Euclidean vector space, equivalently), there are (at least) two vectors that have nonnegative dot product. Let $\displaystyle u_1,\ldots,u_{n+2}\in\mathbb{R}^n$. If any vector is zero, the result is obvious, so we may assume $\displaystyle u_{n+2}\neq 0$. Denote by $\displaystyle \pi$ the projection on the $\displaystyle (n-1)$-dimensional subspace $\displaystyle u_{n+2}^\perp$. By induction, there are $\displaystyle 1\leq i\neq j\leq n+1$ such that $\displaystyle \pi(u_i)\cdot\pi(u_j)\geq 0$. Then, consider $\displaystyle u_i,u_j,u_{n+2}$. I claim that one of $\displaystyle u_i\cdot u_j$, $\displaystyle u_i\cdot u_{n+2}$ or $\displaystyle u_j\cdot u_{n+2}$ is nonnegative. Indeed, if $\displaystyle u_i\cdot u_{n+2}<0$ and $\displaystyle u_j\cdot u_{n+2}<0$, then $\displaystyle u_i\cdot u_j=\pi(u_i)\cdot\pi(u_j)+\frac{u_i\cdot u_{n+2}}{\|u_{n+2}\|}\times\frac{u_j\cdot u_{n+2}}{\|u_{n+2}\|}> 0$ (because for any vector $\displaystyle u$, $\displaystyle u=\pi(u)+\frac{u\cdot u_{n+2}}{\|u_{n+2}\|^2}u_{n+2}$).