a little something to commemorate pi day
Given \(n + 2\) vectors \(\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_{n + 2} \in \mathbb{R}^n\), prove that there always \(2\) distinct vectors \(\mathbf{v}_i\) and \(\mathbf{v}_j\) such that \(\langle \mathbf{v}_i, \mathbf{v}_j\rangle \geq 0\).
Proof: This one is gorgeous. Define the matrix
$$ \begin{align*} \mathbf{V} := \begin{bmatrix} \mid & \mid & \cdots & \mid \\ \mathbf{v}_1 & \mathbf{v}_2 & \ddots & \mathbf{v}_{n + 2} \\ \mid & \mid & \cdots & \mid \\ \end{bmatrix} \in \mathbb{R}^{n \times (n + 2)} \end{align*} $$
and consider the corresponding Gram matrix
$$ \begin{align*} \mathbf{G} = \mathbf{V}^\top \mathbf{V} \in \mathbb{R}^{(n + 2) \times (n + 2)} \implies \text{rank}(\mathbf{G}) = \text{rank}(\mathbf{V}^\top \mathbf{V}) \leq \text{rank}(\mathbf{V}) \leq n \end{align*} $$
We now argue via contradiction. Assume there are no distinct \(i, j\) such that \(\langle \mathbf{v}_i, \mathbf{v}_j\rangle \geq 0\). Therefore all the off-diagonal entries of \(\mathbf{G}\) are strictly negative. Then, we have the matrix \(\mathbf{M} := \left\{\max \limits_{1 \leq i \leq n + 2} (\|\mathbf{v}_i\|) + 1\right\} \mathbb{I} - \mathbf{G}\) has strictly positive entries. By the Perron-Frobenius theorem, it has unique maximal eigenvalue \(\lambda_{\text{max}}\). Equivalently, \(\mathbf{G}\) has a unique minimal eigenvalue \(\lambda_{\text{min}}\). To see this put \(c := \max \limits_{1 \leq i \leq n + 2} (\|\mathbf{v}_i\|) + 1\) and notice that since \(c \mathbb{Id}\) and \(\mathbf{G}\) commute, they possess a shared eigenbasis. Denote this eigenbasis by \(\{\mathbf{y}_1, \ldots, \mathbf{y}_{n + 2}\}\). Since \(\mathbf{M}\) is defined to be the sum of these matrices, it too possesses this eigenbasis. Let \(\{\beta_i\}\) be the eigenvalues of \(\mathbf{M}\) and \(\{\lambda_i\}\) be the eigenvalues of \(\mathbf{G}\). Noting that the eigenvalues of the identity are all \(1\), we have
$$ \begin{align*} \beta_k \mathbf{y}_k = \mathbf{M} \mathbf{y}_k &= c \mathbf{y}_k - \lambda_k \mathbf{y}_k \implies \lambda_{\text{min}} = c - \beta_{\text{max}} \end{align*} $$
Since \(\mathbf{G} \succeq 0\), its eigenvalues are \(\geq 0\). However by the rank-constraint, \(\mathbf{G}\) has rank at most \(n\) and therefore nullity at least \(2\), implying that its minimal eigenvalue is non-unique. Contradiction!
Given \(m\) vectors \(\mathbf{v}_1, \ldots, \mathbf{v}_m \in \mathbb{R}^n\) with equal pairwise distances, i.e. \(\|\mathbf{v}_i - \mathbf{v}_j\|_{\ell_2} = d\) for \(i, j \in [m]\) and \(d \in \mathbb{R}\). Then, \(m \leq n + 1\).
Proof: Let \(\{\mathbf{v}_i\}_{i = 1}^{m} \subset \mathbb{R}^n\) be a set of vectors with equal \(\ell_2\) pairwise distances \(d\) for some \(d \in \mathbb{R}\). Define a new set of vectors \(\{\mathbf{x}_i\}_{i = 1}^{m - 1} \subset \mathbb{R}^n\) where \(\mathbf{x}_i := \mathbf{v}_i - \mathbf{v}_m\) for \(i \in [m - 1]\). Then by construction, we have the following distance guarantees
$$ \begin{align*} \|\mathbf{v}_i\|^2_{\ell_2} &= \|\mathbf{v}_i - \mathbf{v}_m\|^2_{\ell_2} = d^2 \text{ for all } i \in [m - 1] \\ \|\mathbf{v}_i - \mathbf{v}_j\|^2_{\ell_2} &= \|\mathbf{v}_i - \mathbf{v}_m - (\mathbf{v}_j - \mathbf{v}_m)\|^2_{\ell_2} = \|\mathbf{v}_i - \mathbf{v}_j\|^2_{\ell_2} = d^2 \text{ for all } i, j \in [m - 1] \\ \langle \mathbf{v}_i, \mathbf{v}_j \rangle &= \frac{1}{2} \big(\|\mathbf{v}_i\|^2_{\ell_2} + \|\mathbf{v}_j\|^2_{\ell_2} - \|\mathbf{v}_i - \mathbf{v}_j\|^2_{\ell_2}\big) = d^2 - \frac{\|\mathbf{v}_i - \mathbf{v}_j\|^2_{\ell_2}}{2} = \frac{d^2}{2} \end{align*} $$
Now define the matrix
$$ \begin{align*} \mathbf{V} &:= \begin{pmatrix} - & \mathbf{v}_1 & - \\ - & \mathbf{v}_2 & - \\ \vdots & \vdots & \vdots \\ - & \mathbf{v}_{m - 1} & - \end{pmatrix} \in \mathbb{R}^{(m - 1) \times n} \end{align*} $$
By some friendly computation, one observes that
$$ \begin{align*} \mathbf{V} \mathbf{V}^\top &= \begin{pmatrix} \|\mathbf{v}_1\|^2_{\ell_2} & \langle \mathbf{v}_1, \mathbf{v}_2 \rangle & \cdots & \langle \mathbf{v}_1, \mathbf{v}_{m - 1} \rangle \\ \langle \mathbf{v}_2, \mathbf{v}_1 \rangle & \|\mathbf{v}_2\|^2_{\ell_2} & \cdots & \langle \mathbf{v}_2, \mathbf{v}_{m - 1} \rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle \mathbf{v}_{m - 1}, \mathbf{v}_1 \rangle & \langle \mathbf{v}_{m - 1}, \mathbf{v}_2 \rangle & \cdots & \|\mathbf{v}_{m - 1}\|^2_{\ell_2} \end{pmatrix} = \begin{pmatrix} d^2 & d^2/2 & \cdots & d^2/2 \\ \vdots & \vdots & \ddots & \vdots \\ d^2/2 & d^2/2 & \cdots & d^2 \end{pmatrix} \end{align*} $$
In particular, it can be verified \(\mathbf{V} \mathbf{V}^\top\) is linearly independent. However, one can immediately verify that it is not possible to have more than \(n\) linearly independent vectors in \(\mathbb{R}^n\), thereby necessitating that \(m - 1 \leq n\). This settles the claim.
I imagine by this point, folks are well-familiar with the Cauchy-Schwarz inequality given its ubiquity. The statement admits many proofs as we’ve discovered in a previous blog post. This might be my new favorite proof. It comes from Chapter \(3\) of The Schur complement and its applications and is due to Fuzhen Zhang. Given vectors \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\), define the matrix \(\mathbf{A} := \begin{bmatrix} \mathbf{x} & \mathbf{y} \end{bmatrix}\). Then
$$ \begin{align*} \mathbf{B} := \mathbf{A}^\top \mathbf{A} &= \begin{bmatrix} \mathbf{x} \\ \mathbf{y} \end{bmatrix} \begin{bmatrix} \mathbf{x} & \mathbf{y} \end{bmatrix} = \begin{bmatrix} \|\mathbf{x}\|^2 & \langle \mathbf{x}, \mathbf{y}\rangle \\ \langle \mathbf{x}, \mathbf{y}\rangle & \|\mathbf{y}\|^2 \end{bmatrix} \end{align*} $$
In particular, the Gram matrix of \(\mathbf{A}\) is positive semi-definite by construction. \(\therefore\) All the eigenvalues of \(\mathbf{B}\) are \(\geq 0\), and consequently, it has non-negative determinant. This necessitates
$$ \begin{align*} 0 \leq \text{det}(\mathbf{B}) &= \|\mathbf{x}\|^2 \cdot \|\mathbf{y}\|^2 - \langle \mathbf{x}, \mathbf{y}\rangle \cdot \langle \mathbf{x}, \mathbf{y}\rangle \implies \langle \mathbf{x}, \mathbf{y}\rangle \leq \|\mathbf{x}\| \cdot \|\mathbf{y}\| \end{align*} $$
providing the desired result.