Weyl's inequality for singular values

Idea. Each $\sigma_k$ is given by a min-max of the quantity $|Ax|$ over unit vectors, and $x\mapsto|Ax|$ moves by at most $\|A-B\|$ when $A$ is replaced by $B$.

Step 0: the min-max formula. $\sigma_k(A)^2=\lambda_k(A^TA)$, the $k$-th largest eigenvalue of the symmetric matrix $A^TA$. By the Courant-Fischer theorem (quoted without proof),
$$\lambda_k(A^TA)=\max_{\dim V=k}\ \min_{x\in V,|x|=1}x^TA^TAx=\max_{\dim V=k}\min_{x\in V,|x|=1}|Ax|^2.$$
Taking square roots gives the displayed formula (square root is increasing).

Step 1: pointwise comparison. For every unit vector $x$,
$$|Ax|\ge|Bx|-|(A-B)x|\ge|Bx|-\|A-B\|.$$

Step 2: min over $V$. For any $k$-dimensional subspace $V$,
$$\min_{x\in V,|x|=1}|Ax|\ge\min_{x\in V,|x|=1}|Bx|-\|A-B\|.$$

Step 3: max over $V$. Taking the maximum over all $k$-dimensional $V$ on both sides,
$$\sigma_k(A)\ge\sigma_k(B)-\|A-B\|.$$

Step 4: symmetry. Exchanging $A$ and $B$: $\sigma_k(B)\ge\sigma_k(A)-\|A-B\|$. Together: $|\sigma_k(A)-\sigma_k(B)|\le\|A-B\|$.

Numeric check. For a random $5\times5$ matrix $A$ and $B=A+0.1\,\mathrm{noise}$ the largest deviation $\max_k|\sigma_k(A)-\sigma_k(B)|=0.229$ is below $\|A-B\|=0.322$.

Remark.
- Consequences: each $\sigma_k$ is $1$-Lipschitz, hence continuous; with $k=n$ one recovers that $\sigma_{\min}$ is the distance to the singular matrices (Problem 63) and with $k=1$ that $\|\cdot\|$ is $1$-Lipschitz (Problem 72).
- In contrast with the eigenvalues of a non-normal matrix (Problem 82), singular values are *Lipschitz* functions of the matrix: this is why numerical analysts prefer them.