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.
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_1} = \epsilon\) for \(i, j \in [m]\) and \(\epsilon \in \mathbb{R}\). Then, \(m < \infty\).
Proof: A volumetric argument suffices. Suppose \(\|\mathbf{x}_i - \mathbf{x}_j\|_{\ell_1} = \epsilon\) for all \(i \neq j\). This implies that the \(\ell_1\) balls of radius \(\epsilon/2\) around centered at \(\mathbf{x}_i\) and \(\mathbf{x}_j\) are disjoint. Additionally, the union of all such balls is contained in the ball \((1 + \epsilon/2)\mathcal{B}^d_1\) where \(\mathcal{B}^d_1\) denotes the unit \(\ell_1\) ball in \(\mathbb{R}^d\). Denoting \(\mathcal{B}^d_1(c, r)\) as the \(\ell_1\) ball centered at \(c\) with radius \(r\), we have
$$ \begin{align*} \text{vol}\left(\bigcup_{i = 1}^{n} \mathcal{B}^d_1(\mathbf{x}_i, \epsilon/2)\right) &\leq \text{vol}\left((1 + \epsilon/2)\mathcal{B}^d_1\right) \\ \implies \sum_{i = 1}^{n} \text{vol}\left(\mathcal{B}^d_1(\mathbf{x}_i, \epsilon/2)\right) &\leq \text{vol}\left((1 + \epsilon/2) \mathcal{B}^d_1\right) \\ n \cdot \frac{2^d}{d!} \left(\frac{\epsilon}{2}\right)^d &\leq \frac{2^d}{d!} (1 + \epsilon/2)^d \\ \implies n \leq \left(\frac{1 + \epsilon/2}{\epsilon/2}\right)^d &= \left(1 + \frac{2}{\epsilon}\right)^d \end{align*} $$
where we make use of the fact that the balls are disjoint. This settles the claim.
Exercise: Can you make a similar argument under the \(\ell_p\) metric for \(1 < p <\infty\).
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. 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.
This one isn’t really a theorem statement, it’s mostly just a surprising integral computation I discovered a couple of years ago; so I thought to include it here.
$$\int_{0}^1 x \cdot \sqrt{x \cdot \sqrt[3]{x \cdot \sqrt[4]{x} \cdots}} \; \mathrm{d}x = \frac{1}{e}$$
As promised, one can compute the integral to find
$$\begin{align*} \int_{0}^1 x \cdot \sqrt{x \cdot \sqrt[3]{x \cdot \sqrt[4]{x} \cdots}} \; \mathrm{d}x &= \int_{0}^1 \prod_{i = 1}^{\infty} x^{\frac{1}{i!}} \; \mathrm{d}x \\ &= \int_{0}^1 x^{\sum_{i = 1}^\infty \frac{1}{i!}} \; \mathrm{d}x = \int_{0}^1 x^{e - 1} \; \mathrm{d}x \\ &= \frac{x^e}{e} \big|_{0}^1 = \frac{1}{e} \end{align*}$$
For \(n \in \mathbb{N}, x \in \mathbb{R}\), the following equation holds true:
$$\lfloor n x \rfloor = \sum_{k = 0}^{n - 1} \bigg\lfloor x + \frac{k}{n} \bigg\rfloor$$.
Proof: This one is nice. Define a function
$$\begin{align*} f_n(x) := \sum_{k = 0}^{n - 1} \bigg\lfloor x + \frac{k}{n}\bigg\rfloor - \lfloor n x \rfloor \end{align*}$$
Notice that
$$\begin{align*} f_n\left(x + \frac{1}{n}\right) &= \sum_{k = 0}^{n - 1} \bigg\lfloor x + \frac{k + 1}{n}\bigg\rfloor - \lfloor n x + 1\rfloor \\ &= \sum_{k = 1}^n \bigg\lfloor x + \frac{k}{n}\bigg\rfloor - \lfloor n x\rfloor - 1 \\ &= \sum_{k = 0}^{n - 1} \bigg\lfloor x + \frac{k}{n}\bigg\rfloor + \lfloor x + 1 \rfloor - \lfloor x \rfloor - \lfloor n x\rfloor - 1 \\ &= f_n(x) + \lfloor x \rfloor + 1 - \lfloor x \rfloor - 1 = f_n(x) \end{align*} $$
where we make use of reindexing our sum and in the third line, we add the \(k = 0\) and subtract the \(k = n\) terms of the aforementioned sum. The aforementioned result is useful for the following reasons. \(f_n(x)\) has a period of \(1/n\), so it suffices to check \(f_n\) for \(x \in [0, 1/n)\). In particular for \(x\) in the above range, \(\lfloor nx \rfloor\) and \(\sum_{k = 0}^{n - 1} \bigg\lfloor x + \frac{k}{n}\bigg\rfloor\) are both \(0\). Therefore \(f_n(x) \equiv 0\).
note this list is incomplete and will hopefully grow with time.