Courant–Fischer Theorem
Let \(M\) be a symmetric matrix with eigenvalues \(\mu_1 \ge \mu_2 \ge \cdots \ge \mu_n.\)
Then
\[
\mu_k
=
\max_{\substack{S \subset \mathbb{R}^n\\ \dim(S)=k}}
\ \min_{\substack{x \in S \\ x \neq 0}}
\frac{x^{\!T} M x}{x^{\!T} x}
\;=\;
\min_{\substack{T \subset \mathbb{R}^n\\ \dim(T)=n-k+1}}
\ \max_{\substack{x \in T \\ x \neq 0}}
\frac{x^{\!T} M x}{x^{\!T} x},
\]
where the maximization and minimization are taken over subspaces \(S\) and \(T\) of \(\mathbb{R}^n\).
Be warned that most references omit writing the condition \(x \neq 0\), though it is always implied.
Reference : https://jasoncantarella.com/downloads/sagt-courant-fischer.pdf
The Courant–Fischer theorem provides a variational characterization of eigenvalues in terms of Rayleigh quotients
\[
R_M(x)=\frac{x^{\!T} M x}{x^{\!T} x}.
\]
It establishes that each eigenvalue \(\mu_k\) equals the best (max–min or min–max) value the Rayleigh quotient can achieve over \(k\)-dimensional subspaces.
Monotonicity under PSD perturbations and interlacing with rank-one matrix
\(A\in\mathbb{R}^{n\times n}\) be symmetric positive definite (SPD) with ordered eigenvalues
\[
\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n > 0.
\]
\(B = A + \gamma\,\mathbf u\mathbf u^{\!\top}\) where \(\gamma>0\) and \(\mathbf u\in\mathbb{R}^n\setminus\{0\}\).
Relating to the diagonal (Golub’s) case
Even if \(A\) is not diagonal, by the spectral theorem there exists an orthogonal matrix \(Q\) such that
\[
A = Q\,\Lambda\,Q^{\!\top},
\quad \text{where}\quad
\Lambda = \operatorname{diag}(\lambda_1,\dots,\lambda_n).
\]
Define the transformed vector \(\mathbf v = Q^{\!\top}\mathbf u\)
Then
\[
B = Q\bigl(\Lambda + \gamma\,\mathbf v\mathbf v^{\!\top}\bigr)Q^{\!\top}.
\]
Because orthogonal similarity preserves eigenvalues,
the spectra of \(B\) and \(\Lambda + \gamma\,\mathbf v\mathbf v^{\!\top}\) are identical.
Thus, the problem reduces to Golub’s diagonal case with \(D=\Lambda\).
Positive Semidefinite Rank-One Update
Since \(\gamma\,\mathbf u\mathbf u^{\!\top}\succeq 0\), every Rayleigh quotient increases:
\[
\mathbf x^{\!\top}B\mathbf x
=
\mathbf x^{\!\top}A\mathbf x + \gamma(\mathbf u^{\!\top}\mathbf x)^2
\ \ge\
\mathbf x^{\!\top}A\mathbf x,
\quad \forall\,\mathbf x\neq 0.
\]
Hence, by the Courant–Fischer theorem
\[
\mu_k
=
\min_{\substack{T\subset\mathbb{R}^n\\ \dim(T)=n-k+1}}
\ \max_{\substack{\mathbf x\in T\\ \mathbf x\neq 0}}
\frac{\mathbf x^{\!\top}B\mathbf x}{\mathbf x^{\!\top}\mathbf x},
\qquad
\lambda_k
=
\min_{\substack{T\subset\mathbb{R}^n\\ \dim(T)=n-k+1}}
\ \max_{\substack{\mathbf x\in T\\ \mathbf x\neq 0}}
\frac{\mathbf x^{\!\top}A\mathbf x}{\mathbf x^{\!\top}\mathbf x}.
\]
Since the inner Rayleigh quotient for \(B\) is always at least that for \(A\), each minimization gives a value at least as large
\[
\boxed{\lambda_k \;\le\; \mu_k,\quad k=1,\dots,n.}
\]
Interlacing Bounds :
Using Golub’s rank-one interlacing results on the diagonalized form
\[
\Lambda+\gamma\,\mathbf v\mathbf v^{\!\top},
\]
We can obtain tighter eigenvalue bounds
\[
\boxed{
\lambda_k \;\le\; \mu_k \;\le\; \lambda_{k-1},
\qquad k = 1,2,\dots,n,
\quad\text{with } \lambda_0 := +\infty.
}
\]
Reference : https://www.stat.uchicago.edu/~lekheng/courses/309f10/modified.pdf
How the direction of \(\mathbf u\) decides which eigenvalues change
Let the symmetric matrix \(A\) have eigenpairs \((\lambda_i,\mathbf v_i)\) for \(i=1,\dots,n\),
so that \(A\mathbf v_i = \lambda_i\mathbf v_i\) and \(\{\mathbf v_i\}\) form an orthonormal basis.
We can write
\[
\mathbf u = \sum_{i=1}^{n} \alpha_i \mathbf v_i,
\quad \text{where } \alpha_i = \mathbf v_i^{\!\top}\mathbf u.
\]
These coefficients tell us *how much of* \(\mathbf u\) *lies along each eigenvector direction of \(A\)*.
Only the directions with \(\alpha_i \neq 0\) will affect the eigenvalues.
Case 1: \(\mathbf u\) is parallel to the eigenvector \(\mathbf v_1\)
If \(\mathbf u \parallel \mathbf v_1\), the perturbation \(\gamma\,\mathbf u\mathbf u^{\!\top}\) modifies only the one-dimensional subspace spanned by \(\mathbf v_1\)
Hence, only the largest eigenvalue increases to \(\lambda_1 + \gamma\), while all other eigenvalues remain unchanged.
Case 2: \(\mathbf u\) is orthogonal to the eigenvector \(\mathbf v_1\)
If \(\mathbf u \perp \mathbf v_1\) (i.e., \(\alpha_1=0\)), then
\[
\mathbf v_1^{\!\top}B\mathbf v_1 = \mathbf v_1^{\!\top}A\mathbf v_1 = \lambda_1.
\]
Thus,
\[
\mu_1 = \lambda_1.
\]
However, any component of \(\mathbf u\) along lower eigenvectors (\(\alpha_j\neq 0\) for \(j>1\))
will cause those corresponding \(\lambda_j\) to increase.
Case 3: \(\mathbf u\) has a component along the smallest eigenvector \(\mathbf v_n\)
If \(\alpha_n \neq 0\), the smallest eigenvalue increases:
\[
\lambda_n < \mu_n \le \lambda_{n-1}.
\]
If \(\alpha_n = 0\), then \(\mu_n = \lambda_n.\)
Option A
“The eigenvector corresponding to \(\mu_1\) is orthogonal to \(\mathbf v_n\)”
This can be true. If \(\mathbf u \perp \mathbf v_n\), then \(\mathbf v_n\) remains an eigenvector of \(B\) with eigenvalue \(\lambda_n\), and the top eigenvector of \(B\), \(\mathbf w_1\), lies in the span of \(\{\mathbf v_1,\dots,\mathbf v_{n-1}\}\), hence orthogonal to \(\mathbf v_n\).
Hence, possible
Option B
“\(\mu_n>\lambda_n\) and \(\mu_1=\lambda_1\)”
Choose \(\mathbf u\perp \mathbf v_1\) but with component along \(\mathbf v_n\) (\(\alpha_1=0,\ \alpha_n\neq 0\)). Then \(\mu_1=\lambda_1\) (top unchanged) and \(\mu_n>\lambda_n\) (bottom increased).
Hence, Possible
Option C
\(\mu_1>\lambda_1\) and the eigenvector for \(\mu_1\) is \(\parallel \mathbf v_1\)”
Choose \(\mathbf u\parallel \mathbf v_1\). Then the top eigenvalue increases (\(\mu_1=\lambda_1+\gamma>\lambda_1\)) and its eigenvector remains the same.
Hence, Possible
Option D
“There exists \(k\) with \(\mu_k<\lambda_k\) and \(\mu_{k+1}>\lambda_{k+1}\)”
From the interlacing bound for PSD updates,
\[
\lambda_k \le \mu_k \le \lambda_{k-1}.
\]
No eigenvalue of \(A\) ever decreases, so \(\mu_k<\lambda_k\) is impossible.
Never True
\[
\begin{array}{|l|l|}
\hline
\textbf{Symbol} & \textbf{Meaning} \\
\hline
\mathbf{v}_i & \text{Eigenvectors of } A \\
\hline
\lambda_i & \text{Eigenvalues of } A \\
\hline
\mathbf{w}_i & \text{Eigenvectors of } B = A + \gamma\,\mathbf{u}\mathbf{u}^{\!\top} \\
\hline
\mu_i & \text{Eigenvalues of } B \\
\hline
\mathbf{u} & \text{Fixed update direction used in the rank-one term} \\
\hline
\end{array}
\]
