# Thread: Algebra, Problems For Fun (25)

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

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

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

Suggestion:

Spoiler:
A clever induction over $n.$

2. Thanks for this nice problem!

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