The Min-Max Principle

Definition Let $A \in \mathbb{F}^{n \times n}$ be Hermitian, $A^{*} = A$, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$. For $\mathbb{F} = \mathbb{R}$ this means that $A$ is real symmetric. By the spectral theorem the eigenvalues of $A$ are real and $\mathbb{F}^n$ has an orthonormal basis of eigenvectors of $A$. List the eigenvalues in increasing order, each repeated as often as its multiplicity,

and choose an orthonormal eigenbasis $q_1, \dots, q_n$ in the same order, so that $Aq_j = \lambda_j q_j$. Multiplicity here is algebraic multiplicity, which for a Hermitian matrix equals the dimension of the eigenspace. The list of numbers is determined by $A$, but the eigenvectors are not. Each $q_j$ can be multiplied by a scalar of absolute value $1$, and a repeated eigenvalue allows any orthonormal basis of its eigenspace. For a nonzero vector $x = c_1 q_1 + \cdots + c_n q_n$ the Rayleigh quotient is a weighted average of the eigenvalues,

Two consequences are used throughout. If $x \ne 0$ lies in $\operatorname{span}(q_1, \dots, q_k)$, then only eigenvalues at most $\lambda_k$ receive positive weight, so $R_A(x) \le \lambda_k$. If $x \ne 0$ lies in $\operatorname{span}(q_k, \dots, q_n)$, then $R_A(x) \ge \lambda_k$ for the same reason. In both cases the vector $q_k$ gives equality. Here and below a tuple such as $(1, 1, 1)$ stands for a column vector.

Definition Let $U$ and $W$ be subspaces of a vector space $V$ of finite dimension $n$ over $\mathbb{F}$. Then

In particular, if $\dim U + \dim W > n$, then $U \cap W$ contains a nonzero vector. This follows from the dimension formula for a sum. The sum $U + W$ is a subspace of $V$, so its dimension is at most $n$, and

Both principles below use this with dimensions $k$ and $n - k + 1$, whose sum is $n + 1$. All dimensions are taken over the same field $\mathbb{F}$, so for $\mathbb{F} = \mathbb{C}$ they are complex dimensions. The count only says that a shared nonzero vector exists. Which vector it is depends on both subspaces, and the argument uses no angles or orthogonality.

Definition Let $A \in \mathbb{F}^{n \times n}$ be Hermitian, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$, with eigenvalues $\lambda_1 \le \cdots \le \lambda_n$ in increasing order. For every $k = 1, \dots, n$,

where $S$ runs over all subspaces of $\mathbb{F}^n$ of dimension $k$. The inner maximum exists for each $S$. The quotient does not change when $x$ is multiplied by a nonzero scalar, so on $S$ it takes the same values as on the unit sphere of $S$, which is compact because $S$ is finite-dimensional, and the quotient is continuous there. The outer minimum exists because the subspace $S_0$ in the proof attains it. The result is also called the Courant-Fischer theorem. It holds in the same form for a self-adjoint operator $T$ on an $n$-dimensional inner product space over $\mathbb{F}$, with $R_T(v) = \langle v, Tv \rangle / \langle v, v \rangle$.

For the proof, let $S_0 = \operatorname{span}(q_1, \dots, q_k)$. Every nonzero vector of $S_0$ has quotient at most $\lambda_k$, and $q_k \in S_0$ has quotient exactly $\lambda_k$, so the maximum on $S_0$ is $\lambda_k$. Now let $S$ be any subspace of dimension $k$, and let $E = \operatorname{span}(q_k, \dots, q_n)$, of dimension $n - k + 1$. Since $k + (n - k + 1) = n + 1 > n$, the dimension count gives a nonzero $x \in S \cap E$. Because $x \in E$, its quotient is at least $\lambda_k$, so the maximum on $S$ is at least $\lambda_k$. Every $k$-dimensional subspace has maximum at least $\lambda_k$ and $S_0$ has maximum exactly $\lambda_k$, which proves the formula. For $k = 1$ the subspaces are lines and the formula is the minimum of the quotient over all nonzero vectors, which is $\lambda_1$. For $k = n$ the only subspace is $\mathbb{F}^n$, and the formula gives the maximum $\lambda_n$. The Hermitian hypothesis supplies the real quotient, the real eigenvalues and the orthonormal eigenbasis that the proof uses.

Definition Let $A \in \mathbb{F}^{n \times n}$ be Hermitian, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$, with eigenvalues $\lambda_1 \le \cdots \le \lambda_n$ in increasing order. For every $k = 1, \dots, n$,

where $L$ runs over all subspaces of $\mathbb{F}^n$ of dimension $n - k + 1$. The inner minimum exists for the same compactness reason as before. For the proof, let $L_0 = \operatorname{span}(q_k, \dots, q_n)$. Every nonzero vector of $L_0$ has quotient at least $\lambda_k$ and $q_k$ gives equality, so the minimum on $L_0$ is $\lambda_k$. For any $L$ of dimension $n - k + 1$, the subspace $\operatorname{span}(q_1, \dots, q_k)$ has dimension $k$, the dimensions add up to $n + 1$, and the two share a nonzero vector $x$ with $R_A(x) \le \lambda_k$. So the minimum on $L$ is at most $\lambda_k$, and $L_0$ attains this value. The same formula also follows from the min-max principle applied to $-A$, whose eigenvalues in increasing order are $-\lambda_n \le \cdots \le -\lambda_1$.

The dimension $n - k + 1$ belongs with increasing order. With the same order, the maximum over $k$-dimensional subspaces of the minimum quotient is $\lambda_{n - k + 1}$, the $k$th largest eigenvalue. Pairing dimension $k$ with the max-min is the convention for eigenvalues listed in decreasing order.

Definition Let $A \in \mathbb{F}^{n \times n}$ be Hermitian with eigenvalues $\lambda_1 \le \cdots \le \lambda_n$. In the min-max principle, a $k$-dimensional subspace $S$ attains the bound when its maximum quotient equals $\lambda_k$. In the max-min principle, an $(n - k + 1)$-dimensional subspace $L$ attains it when its minimum quotient equals $\lambda_k$. For every orthonormal eigenbasis in increasing order, the subspaces

attain. Because these subspaces exist, the outer optimizations are a true minimum and a true maximum, and no compactness argument over the family of all subspaces is needed. The principles determine the number $\lambda_k$, but they need not determine the subspace. Suppose first that the eigenvalues are distinct. For $k = 1$ and $k = n$ the subspaces $S_0$ and $L_0$ are the only attaining subspaces, but for $1 < k < n$ each principle has infinitely many, and they need not be spanned by eigenvectors. When $\lambda_k$ is repeated, at least one of $S_0$ and $L_0$ contains only part of the eigenspace of $\lambda_k$, so it depends on the eigenbasis and can be chosen in many ways. Every nonzero vector of that eigenspace has quotient $\lambda_k$.