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 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.
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:
$$\bigg\lfloor n x \rfloor = \sum_{k = 0}^{n - 1} \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.