Proof of The Courant–Fischer Min–Max Theorem

Routine facts about scalars in the dot product, subspaces of $\mathbb{R}^{n}$, finite coordinate sums, and tuples and functions given by explicit values are used without comment (Toolkit for AL3, Finite Sums of the Coordinates of a Point of ℝⁿ, Values, Restriction and Equality of a Map, and the Map $u\mapsto t(u)$ as a Defined Set Symbol).

For $x\in\mathbb{R}^{n}$ and $i\in[n]$ write

$$c_{i}(x)=x\cdot(Qe_{i}),$$

the coordinate of $x$ along the $i$th column of $Q$. We first establish four facts about these coordinates and then prove the two clauses.

Orthonormal columns. Since $Q\in\mathrm{O}(n)$, Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion (iv) gives

$$(Qe_{i})\cdot(Qe_{j})=\delta_{ij}\qquad(i,j\in[n]).$$

The form in coordinates. Let $x\in\mathbb{R}^{n}$. The $i$th component of $Q^{\top}x$ is $e_{i}\cdot(Q^{\top}x)$ by Standard Basis Vectors of ℝ^q: Coordinates, Orthonormality and Unit Length (i). Using the symmetry of the dot product (The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (i)), then Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (viii) for the matrix $Q^{\top}$, and finally $(Q^{\top})^{\top}=Q$ (Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes (vii)), we get

$$(Q^{\top}x)_{i}=(Q^{\top}x)\cdot e_{i}=x\cdot\bigl((Q^{\top})^{\top}e_{i}\bigr)=x\cdot(Qe_{i})=c_{i}(x).$$

Since $A=(Q\operatorname{diag}(\lambda))Q^{\top}$, Toolkit for AL3 (xxi), applied to the tuple $\lambda$ and the point $x$, and Toolkit for AL3 (xxii) express the quadratic form and the norm through the components of $Q^{\top}x$:

$$x\cdot(Ax)=\sum_{i=1}^{n}\lambda_{i}\,c_{i}(x)^{2},\qquad\lVert x\rVert^{2}=\sum_{i=1}^{n}c_{i}(x)^{2}.$$

Spans of consecutive columns. Let $1\le a\le b\le n$ and $S=\operatorname{span}(Qe_{a},\dots,Qe_{b})$; here, and for the spans $V_{k}$ and $U_{k}$ below, the family $(Qe_{a},\dots,Qe_{b})$ is read as the $(b-a+1)$-tuple whose $i$th entry is $Qe_{a+i-1}$. By The Span of a Finite Family is the Smallest Subspace Containing It (ii), $S$ is a subspace of $\mathbb{R}^{n}$ containing each $Qe_{i}$ with $a\le i\le b$, and the family $(Qe_{a},\dots,Qe_{b})$ spans $S$, because its span computed in $S$ equals its span computed in $\mathbb{R}^{n}$ (Linear Subspaces Are Vector Spaces; Intersections (iv)). The family is linearly independent in $\mathbb{R}^{n}$, hence in $S$ by the same clause: if $\sum_{i=a}^{b}\alpha_{i}Qe_{i}=0$, then for $a\le j\le b$ the dot product with $Qe_{j}$, expanded by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (ii) and evaluated by the orthonormality of the columns, gives

$$0=\sum_{i=a}^{b}\alpha_{i}\,(Qe_{i})\cdot(Qe_{j})=\alpha_{j}.$$

So the family is a basis of $S$, which is a vector space by Linear Subspaces Are Vector Spaces; Intersections (i), and $\dim S=b-a+1$ by Finite-Dimensional Vector Spaces and Their Dimension (ii). The same computation shows that every $x=\sum_{i=a}^{b}\alpha_{i}Qe_{i}$ in $S$ has $c_{j}(x)=0$ for every $j\in[n]$ outside $\{a,\dots,b\}$.

Normalisation. Let $x\in\mathbb{R}^{n}$ with $x\neq0$. Then $x\cdot x>0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (vi), so $\lVert x\rVert>0$, and $u=\lVert x\rVert^{-1}x$ lies in every subspace that contains $x$. It is a unit vector: by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (ii) and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite (iii), $u\cdot u=\lVert x\rVert^{-2}\,x\cdot x=1$, so $\lVert u\rVert=\sqrt{u\cdot u}=1$ (The Euclidean Norm on $\mathbb{R}^n$ (i)).

Max–min. Let $U$ be a subspace of $\mathbb{R}^{n}$ with $\dim U=k$, and let $V_{k}=\operatorname{span}(Qe_{k},\dots,Qe_{n})$, which has dimension $n-k+1$ by the paragraph on spans. Since $\dim\mathbb{R}^{n}=n$ (Properties of Dimension (vi)) and

$$\dim U+\dim V_{k}=n+1>n,$$

Two Subspaces Whose Dimensions Add Up to More Than the Whole Space Meet (i) gives a nonzero $x\in U\cap V_{k}$; after normalisation we may take $x$ to be a unit vector, still in $U\cap V_{k}$. As $x\in V_{k}$, $c_{i}(x)=0$ for $i<k$, while $\lambda_{i}\le\lambda_{k}$ for $i\ge k$. So the formulas for the quadratic form and the norm give

$$x\cdot(Ax)=\sum_{i=k}^{n}\lambda_{i}\,c_{i}(x)^{2}\le\lambda_{k}\sum_{i=k}^{n}c_{i}(x)^{2}=\lambda_{k}\lVert x\rVert^{2}=\lambda_{k}.$$

This is the first assertion of (i). For the second, $U_{k}=\operatorname{span}(Qe_{1},\dots,Qe_{k})$ is a subspace of dimension $k$ by the paragraph on spans, and every unit vector $x\in U_{k}$ has $c_{i}(x)=0$ for $i>k$. As $\lambda_{i}\ge\lambda_{k}$ for $i\le k$,

$$x\cdot(Ax)=\sum_{i=1}^{k}\lambda_{i}\,c_{i}(x)^{2}\ge\lambda_{k}\sum_{i=1}^{k}c_{i}(x)^{2}=\lambda_{k}\lVert x\rVert^{2}=\lambda_{k}.$$

Min–max. Let $U$ be a subspace of $\mathbb{R}^{n}$ with $\dim U=n-k+1$. Then $\dim U+\dim U_{k}=n+1>n$, so Two Subspaces Whose Dimensions Add Up to More Than the Whole Space Meet (i), followed by normalisation, gives a unit vector $x\in U\cap U_{k}$, and $x\cdot(Ax)\ge\lambda_{k}$ by the second part of (i). For the second assertion of (ii), $V_{k}$ is a subspace of dimension $n-k+1$ by the paragraph on spans, and the computation in the first part of the proof of (i), which used only that $x$ is a unit vector in $V_{k}$, gives $x\cdot(Ax)\le\lambda_{k}$ for every unit vector $x\in V_{k}$.