NLA MT25, Courant-Fischer minmax theorem
Flashcards
@State the Courant-Fischer minmax theorem.
Suppose:
- $A \in \mathbb R^{n \times n}$ is a symmetric matrix
then:
\[\begin{aligned} \lambda _ i(A) &= \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S} \frac{x^\top A x}{x^\top x} \\ &= \min _ {\dim \mathcal S = n-i + 1} \max _ {x \in \mathcal S} \frac{x^\top A x}{x^\top x} \end{aligned}\]and analogously, if
- $A \in \mathbb C^{m \times n}$ where $m \ge n$
then:
\[\begin{aligned} \sigma _ i(A) &= \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2} \\ &= \min _ {\dim \mathcal S = n - i + 1} \max _ {x \in \mathcal S} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2} \end{aligned}\](here, $\max _ {\dim \mathcal S = i}$ means that we’re taking the maximum over all possible subspaces $\mathcal S$ of dimension $i$).
@Prove the ∆courant-fischer-minmax-theorem, i.e. that if $A \in \mathbb R^{n \times n}$ is a symmetric matrix then:
\[\begin{aligned}
\lambda _ i(A) &= \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S \setminus \{0\}} \frac{x^\top A x}{x^\top x} & (1) \\
&= \min _ {\dim \mathcal S = n-i + 1} \max _ {x \in \mathcal S \setminus \{0\}} \frac{x^\top A x}{x^\top x}
\end{aligned}\]
and furthermore, if $A \in \mathbb C^{m \times n}$ where $m \ge n$ then:
\[\begin{aligned}
\sigma _ i(A) &= \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2} &\quad (2) \\
&= \min _ {\dim \mathcal S = n - i + 1} \max _ {x \in \mathcal S \setminus \{0\}} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2}
\end{aligned}\]
We adopt the conventions $\lambda _ 1 \ge \cdots \ge \lambda _ n$ and $\sigma _ 1 \ge \cdots \ge \sigma _ n$. Write $r(x) := \frac{x^\top A x}{x^\top x}$ for the Rayleigh quotient.
On the hypothesis: writing $A$ real symmetric is only a convenience. The identical argument proves (1) for any Hermitian $A \in \mathbb C^{n \times n}$, with $x^\top$ replaced by $x^*$ and $c _ j^2$ by $ \vert c _ j \vert ^2$. Self-adjointness is what makes the eigenvalues real and ordered with an orthonormal eigenbasis, so that $r(x)$ is a real convex combination of the $\lambda _ j$. It cannot be dropped: a non-self-adjoint matrix can have complex eigenvalues with no ordering and a non-real $r(x)$, so the statement would not even make sense.
Proof of (1): Let an orthogonal diagonalisation of $A$ be $Q \Lambda Q^\top$ with $Q = [q _ 1, \ldots, q _ n]$ so that $Aq _ j = \lambda _ j q _ j$. For any unit vector $x = \sum _ j c _ j q _ j$, $r(x) = \sum _ j \lambda _ j c _ j^2$, which is a convex combination of the eigenvalues.
Lower bound: Fix any subspace $\mathcal S$ and let $Q _ i = [q _ i, \ldots, q _ n]$. Then
\[\dim(\mathcal S) + \dim(\text{span}(Q _ i)) = i + (n - i + 1) = n + 1 > n\]Since this quantity is bigger than $n$, it follows there exists some non-zero $w \in \mathcal S \cap Q _ i$, and in particular we may choose $ \vert \vert w \vert \vert _ 2 = 1$. Write $w$ in the eigenbasis so that $w = \sum _ {j \ge i} c _ j q _ j$. Then
\[r(w) = \sum _ {j \ge i} \lambda _ j c _ j^2 \le \lambda _ i \sum _ {j \ge i} c _ j^2 = \lambda _ i.\]Hence $\min _ {x \in \mathcal S} r(x) \le \lambda _ i$.
Upper bound: Take $S^\ast := \text{span}(q _ 1, \ldots, q _ i)$. For any unit $w = \sum _ {j \le i} c _ j q _ j \in \mathcal S^\ast$, then
\[r(w) = \sum _ {j \le i} \lambda _ j c _ j^2 \ge \lambda _ i,\]so $\min _ {x \in \mathcal S^\ast} r(x) = \lambda _ i$ (attained at $w = q _ i$). Hence the max is attained at $S^\ast$ with value $\lambda _ i$.
Min-max version: Apply the same argument to $-A$, whose eigenvalues are $-\lambda _ n \ge \cdots \ge -\lambda _ 1$. The $i$th eigenvalue of $-A$ is $-\lambda _ {n-i+1}$, giving
\[-\lambda _ {n-i+1} = \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S \setminus \{0\}} \frac{-x^\top A x}{x^\top x} = -\min _ {\dim \mathcal S = i} \max _ {x \in \mathcal S} r(x).\]Reindexing with $i \mapsto n - i + 1$ yields the min-max formula.
Proof of (2): Apply part (1) to $B := A^\top A$ (Hermitian $A^* A$ in the complex case), which is valid by the hypothesis remark above. $B$ is symmetric positive semidefinite with eigenvalues $\lambda _ i(B) = \sigma _ i(A)^2$, ordered $\sigma _ 1^2 \ge \cdots \ge \sigma _ n^2 \ge 0$. Its Rayleigh quotient is exactly the square of the singular-value one:
\[\frac{x^\top B x}{x^\top x} = \frac{(Ax)^\top (Ax)}{x^\top x} = \frac{\|Ax\| _ 2^2}{\|x\| _ 2^2}.\]So part (1) applied to $B$ gives
\[\sigma _ i(A)^2 = \lambda _ i(B) = \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S \setminus \{0\}} \frac{\|Ax\| _ 2^2}{\|x\| _ 2^2} = \min _ {\dim \mathcal S = n - i + 1} \max _ {x \in \mathcal S \setminus \{0\}} \frac{\|Ax\| _ 2^2}{\|x\| _ 2^2}.\]Since $\|Ax\| _ 2 / \|x\| _ 2 \ge 0$ and $t \mapsto \sqrt{t}$ is a monotone increasing bijection on $[0, \infty)$, the square root commutes with both the inner and the outer optimisation ($\sqrt{\max f} = \max \sqrt f$ and $\sqrt{\min f} = \min \sqrt f$ for $f \ge 0$). Taking square roots of the displayed equalities passes straight through the max-min and the min-max, and $\sqrt{\sigma _ i^2} = \sigma _ i$, giving
\[\sigma _ i(A) = \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S \setminus \{0\}} \frac{\|Ax\| _ 2}{\|x\| _ 2} = \min _ {\dim \mathcal S = n - i + 1} \max _ {x \in \mathcal S \setminus \{0\}} \frac{\|Ax\| _ 2}{\|x\| _ 2}.\]@Prove that for a matrix $A$,
\[\sigma _ 1 = \max _ {x} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2}\]
and
\[\sigma _ n = \min _ {x} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2} = \min _ { \vert \vert x \vert \vert _ 2 = 1} \vert \vert Ax \vert \vert _ 2\]
by appealing to the ∆courant-fischer-minmax-theorem (recall here that $\sigma _ 1$ is the largest singular value, and $\sigma _ n$ is the smallest).
Recall the CF theorem states that
\[\begin{aligned} \sigma _ i(A) &= \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2} &\quad (2) \\ &= \min _ {\dim \mathcal S = n - i + 1} \max _ {x \in \mathcal S} \frac{ \vert \vert Ax \vert \vert _ 2}{ \vert \vert x \vert \vert _ 2} \end{aligned}\]then plug in $i = 1$ and $i = n$.
@Define what a “variational characterisation” means in the context of numerical linear algebra, and why a variational characterisation of a quantity is useful.
A variational characterisation of a quantity is one that expresses it as the optimum of some functional. Compare:
- Largest eigenvalue $\lambda _ 1(A)$ for symmetric $A$. Algebraic: $\chi _ A(\lambda _ 1(A)) = 0$. Variational: $\lambda _ 1(A) = \max _ {x \ne 0} \frac{x^\top A x}{x^\top x}$.
- All eigenvalues $\lambda _ i(A)$ for symmetric $A$. Algebraic: roots of $\chi _ A$. Variational: ∆courant-fischer-minmax-theorem.
- Largest singular value $\sigma _ 1(A)$. Algebraic: $\sigma _ 1(A) = \sqrt{\lambda _ 1(A^\top A)}$. Variational: $\sigma _ 1(A) = \max _ {x \ne 0} \frac{\|Ax\| _ 2}{\|x\| _ 2} = \|A\| _ 2$.
- Solution to $Ax = b$ for $A \succ 0$. Algebraic: $x = A^{-1}b$. Variational: $x = \text{argmin} _ x \frac 1 2 x^\top A x - x^\top b$.
This is useful for several reasons, but one is that it makes proving inequalities easier, since if you restrict the set over which the optimum is taken, the estimate can only grow or shrink.
Applications
See also Notes - NLA MT25, Weyl’s inequalityU.
Suppose $A _ 1, A _ 2$ are matrices. @State a result about $\sigma _ i\left(\begin{bmatrix}A _ 1 \\ A _ 2\end{bmatrix}\right)$ and $\sigma _ i(\begin{bmatrix}A _ 1 & A _ 2\end{bmatrix})$.
and
\[\sigma _ i(\begin{bmatrix}A _ 1 & A _ 2\end{bmatrix}) \ge \max(\sigma _ i(A _ 1), \sigma _ i(A _ 2))\]@Prove that if $A _ 1, A _ 2$ are matrices, then
\[\sigma _ i\left(\begin{bmatrix}A _ 1 \\ A _ 2\end{bmatrix}\right) \ge \max(\sigma _ i (A _ 1), \sigma _ i(A _ 2)) \quad\quad (1)\]
and
\[\sigma _ i(\begin{bmatrix}A _ 1 & A _ 2\end{bmatrix}) \ge \max(\sigma _ i(A _ 1), \sigma _ i(A _ 2)) \quad\quad (2)\]
Proof of (1):
The left-hand side is:
\[\sigma _ i\left(\begin{bmatrix}A _ 1 \\ A _ 2\end{bmatrix}\right) = \max _ {\dim \mathcal S = i} \min _ {x \in \mathcal S, \vert \vert x \vert \vert _ 2 = 1} \left \vert \left \vert \begin{bmatrix}A _ 1 \\ A _ 2\end{bmatrix} x\right \vert \right \vert \]and for any $x$,
\[\left \vert \left \vert \begin{bmatrix}A _ 1 \\ A _ 2\end{bmatrix} x\right \vert \right \vert _ 2 \ge \max( \vert \vert A _ 1 x \vert \vert _ 2, \vert \vert A _ 2 x \vert \vert _ 2)\]Proof of (2):
The left-hand side is:
\[\sigma _ i(\begin{bmatrix}A _ 1 & A _ 2\end{bmatrix}) = \max _ {\dim \mathcal S = i} \min _ {\begin{bmatrix}x _ 1 \\ x _ 2\end{bmatrix} \in \mathcal S, \vert \vert \begin{bmatrix}x _ 1 \\ x _ 2\end{bmatrix} \vert \vert = 1} \left \vert \left \vert \begin{bmatrix}A _ 1 & A _ 2\end{bmatrix} \begin{bmatrix}x _ 1 \\ x _ 2\end{bmatrix}\right \vert \right \vert _ 2\]while
\[\sigma _ i(\begin{bmatrix}A _ 1 & A _ 2\end{bmatrix}) = \max _ {\substack{\dim S = i, \\ \mathrm{range}(S) \in \mathrm{range}\begin{bmatrix} I _ n \\ 0 \end{bmatrix}}} \min _ {\substack{\begin{bmatrix} x _ 1 \\ x _ 2 \end{bmatrix} \in S, \\ \left\| \begin{bmatrix} x _ 1 \\ x _ 2 \end{bmatrix} \right\| _ 2 = 1}} \left\| \begin{bmatrix} A _ 1 & A _ 2 \end{bmatrix} \begin{bmatrix} x _ 1 \\ x _ 2 \end{bmatrix} \right\| _ 2 .\]Since the latter imposes restrictions on $\mathcal S$ to take the maximum over, the former is at least as big.
@State and @prove the singular-value submultiplicativity bound: for $A \in \mathbb R^{m \times n}$ and $B \in \mathbb R^{n \times \ell}$ and every $i$,
\[\sigma _ i(AB) \le \sigma _ i(A)\, \|B\| _ 2.\]
Setup. By ∆courant-fischer-minmax-theorem applied to $AB$,
\[\sigma _ i(AB) = \max _ {\dim \mathcal S = i} \min _ {0 \ne x \in \mathcal S} \frac{\|AB x\| _ 2}{\|x\| _ 2}.\]To upper-bound $\sigma _ i(AB)$, it suffices to show that for every $i$-dimensional $\mathcal S \subseteq \mathbb R^\ell$,
\[\min _ {0 \ne x \in \mathcal S} \frac{\|AB x\| _ 2}{\|x\| _ 2} \le \sigma _ i(A)\, \|B\| _ 2 \qquad (\star).\]Case 1: $B$ is not injective on $\mathcal S$. Pick $0 \ne x _ * \in \mathcal S$ with $Bx _ * = 0$; then $\frac{\|ABx _ *\| _ 2}{\|x _ *\| _ 2} = 0 \le \sigma _ i(A) \|B\| _ 2$, so the min in $(\star)$ is $0$.
Case 2: $B$ is injective on $\mathcal S$. Then $B \mathcal S$ is an $i$-dimensional subspace of $\mathbb R^n$. Apply Courant-Fischer to $A$:
\[\sigma _ i(A) = \max _ {\dim \mathcal T = i} \min _ {0 \ne y \in \mathcal T} \frac{\|Ay\| _ 2}{\|y\| _ 2} \ge \min _ {0 \ne y \in B\mathcal S} \frac{\|Ay\| _ 2}{\|y\| _ 2},\]since $B\mathcal S$ is one particular $i$-dimensional subspace. Let $y _ * \in B\mathcal S$ attain this min, and let $x _ * = B^{-1} y _ * \in \mathcal S$ (well-defined by injectivity). Then
\[\begin{aligned} \frac{\|AB x _ *\| _ 2}{\|x _ *\| _ 2} &= \frac{\|A y _ *\| _ 2}{\|y _ *\| _ 2} \cdot \frac{\|y _ *\| _ 2}{\|x _ *\| _ 2} && (\star 1) \\ &= \frac{\|A y _ *\| _ 2}{\|y _ *\| _ 2} \cdot \frac{\|B x _ *\| _ 2}{\|x _ *\| _ 2} && (\star 2) \\ &\le \sigma _ i(A) \cdot \|B\| _ 2 && (\star 3) \end{aligned}\]so the min in $(\star)$ is at most $\sigma _ i(A) \|B\| _ 2$, as required.
- $(\star 1)$ Use $ABx _ * = Ay _ *$ and multiply-and-divide by $\|y _ *\| _ 2$.
- $(\star 2)$ Use $y _ * = Bx _ *$, so $\|y _ *\| _ 2 = \|Bx _ *\| _ 2$.
- $(\star 3)$ Use $\frac{\|Ay _ *\| _ 2}{\|y _ *\| _ 2} \le \sigma _ i(A)$ (from the CF application above) and $\frac{\|Bx _ *\| _ 2}{\|x _ *\| _ 2} \le \|B\| _ 2$ (definition of the spectral norm).
Taking $\max _ {\mathcal S}$ over $(\star)$ gives $\sigma _ i(AB) \le \sigma _ i(A) \|B\| _ 2$. $\blacksquare$
Why useful: combined with $\|M\| _ F^2 = \sum \sigma _ i(M)^2$, this gives the Frobenius-spectral submultiplicativity $\|AB\| _ F \le \|A\| _ F \|B\| _ 2$ (NLA 2023 Q1(a)(iv)). It is also the singular-value analogue of Weyl’s product bound and underpins many perturbation results.
Bite-sized
The $i = 1$ special case of Courant-Fischer for eigenvalues collapses to the Rayleigh quotient characterisation: $\lambda _ 1(A) = \max _ {x \ne 0} \tfrac{x^\top A x}{x^\top x}$. The $i = n$ case gives $\lambda _ n(A) = $ $\min _ {x \ne 0} \tfrac{x^\top A x}{x^\top x}$.
How does Courant-Fischer immediately give the Rayleigh-Ritz inequality $\hat \lambda _ i \le \lambda _ i(A)$ for the Ritz values $\hat \lambda _ i$ of a symmetric $A$ on a subspace $\mathcal T = \mathrm{range}(Q)$?
Ritz values: take orthonormal $Q \in \mathbb R^{n \times k}$ with $\mathrm{range}(Q) = \mathcal T$ ($k = \dim \mathcal T$). The Ritz values $\hat \lambda _ 1 \ge \cdots \ge \hat \lambda _ k$ are the eigenvalues of the compressed matrix $Q^\top A Q \in \mathbb R^{k \times k}$ — the Rayleigh-Ritz approximations to $\mathrm{eig}(A)$ extracted from $\mathcal T$ (∆rayleigh-ritz-algorithm).
Applying Courant-Fischer to the $k \times k$ matrix $Q^\top A Q$ (substitute $x = Qy$, so $\tfrac{x^\top A x}{x^\top x} = \tfrac{y^\top Q^\top A Q\, y}{y^\top y}$ since $Q^\top Q = I _ k$) expresses each $\hat \lambda _ i$ as a max-min of the Rayleigh quotient over $i$-dimensional subspaces inside $\mathcal T$. That feasible set is a subset of all $i$-dimensional subspaces of $\mathbb R^n$ (which give $\lambda _ i(A)$), so the maximum can only decrease:
\[\hat \lambda _ i = \max _ {\substack{\mathcal U \subseteq \mathcal T \\ \dim \mathcal U = i}} \min _ {x \in \mathcal U \setminus \{0\}} \tfrac{x^\top A x}{x^\top x} \;\le\; \max _ {\dim \mathcal U = i} \min _ {x \in \mathcal U \setminus \{0\}} \tfrac{x^\top A x}{x^\top x} = \lambda _ i(A).\]The Cauchy interlacing lower bound $\hat \lambda _ i \ge \lambda _ {n - k + i}(A)$ comes from the same argument applied to the min-max form.
The key technical step in the Courant-Fischer proof is a dimension count: for an arbitrary $i$-dim $\mathcal S$ and the $(n - i + 1)$-dim trailing eigenvector span $V _ i = \mathrm{span}(v _ i, \ldots, v _ n)$, we have $\dim \mathcal S + \dim \mathrm{span}(V _ i) = $ $n + 1$, so $\mathcal S \cap V _ i$ contains a nonzero vector.
Strategy for proving Courant-Fischer (∆courant-fischer-minmax-proof) for symmetric eigenvalues.
Two-sided bound on the max-min.
- Upper bound (constructive witness): take $\mathcal S^\ast = \mathrm{span}(q _ 1, \ldots, q _ i)$ where $q _ j$ are eigenvectors with $\lambda _ j$ decreasing. Any unit $w \in \mathcal S^\ast$ has Rayleigh quotient $\sum _ {j \le i} \lambda _ j c _ j^2 \ge \lambda _ i$. So the inner min is exactly $\lambda _ i$, attained at $w = q _ i$.
- Lower bound (dimension count): for arbitrary $i$-dim $\mathcal S$, pair with the $(n - i + 1)$-dim trailing eigenspace $V _ i = \mathrm{span}(q _ i, \ldots, q _ n)$. Then $\dim \mathcal S + \dim V _ i = n + 1 > n$, so they intersect in some nonzero $w$. On $w$, $r(w) \le \lambda _ i$, so the inner min is $\le \lambda _ i$.
- Min-max version: apply the same argument to $-A$ and re-index.
- Singular-value version: identical structure, but with $A^\top A$’s eigenvectors $v _ j$ replacing the $q _ j$ and $\|Av\| _ 2 / \|v\| _ 2$ replacing the Rayleigh quotient.
Courant-Fischer ordering (symmetric $A$, eigenvalues $\lambda _ 1 \ge \cdots \ge \lambda _ n$, Rayleigh quotient $r(x) = \tfrac{x^\top A x}{x^\top x}$). State both equivalent characterisations of the $i$th eigenvalue, getting the operator order and subspace dimensions right:
$\lambda _ i(A) = \max _ {\dim \mathcal S = i}\, \min _ {x \in \mathcal S,\, x \ne 0} r(x) = \min _ {\dim \mathcal S = n - i + 1}\, \max _ {x \in \mathcal S,\, x \ne 0} r(x)$
Recall aid: the outer optimiser is always over subspaces (taken first); the two subspace dimensions sum to $n + 1$ — the $i + (n - i + 1) > n$ count that forces the subspace intersection in the proof.