Perturbation bounds and rank cutoffs for sorted matrix eigenvalues #
For a Hermitian matrix over RCLike, an entrywise perturbation of size ε changes each
sorted eigenvalue by at most card ι * ε. An entrywise bound on the matrix itself gives the
same a-priori bound on the absolute values of its eigenvalues. These estimates connect
coordinatewise error bounds to spectral error bounds for random matrices.
A perturbation smaller than the distance of a sorted eigenvalue from a real threshold
preserves its membership in [c, ∞). Thus perturbations smaller than a spectral gap
preserve the number of eigenvalues above the threshold, counted with multiplicity.
This is the rank stability used when selecting a spectral subspace by a fixed threshold.
The norm in these threshold results is the Euclidean operator norm, selected by
Matrix.Norms.L2Operator.
All statements use Mathlib's decreasing enumeration Matrix.IsHermitian.eigenvalues₀,
including multiplicities. For positive-semidefinite matrices its nonzero entries form an
initial segment of length equal to the rank. Thus a rank bound is equivalent to vanishing
of the corresponding sorted tail. Arbitrary finite index types, including empty ones, are
allowed.
The perturbation estimate combines the operator Weyl inequality in
TauCeti.Analysis.InnerProductSpace.CourantFischer with the entrywise operator bound in
TauCeti.Analysis.Matrix.EntrywiseOpNorm. The rank count reindexes Mathlib's
Matrix.IsHermitian.rank_eq_card_non_zero_eigs to the sorted enumeration.
Weyl's additive inequalities λₖ(A + B) ≤ λᵢ(A) + λⱼ(B) for i + j ≤ k, and their lower
counterpart, are the matrix forms of the operator inequalities in
TauCeti.Analysis.InnerProductSpace.CourantFischer. A Hermitian matrix of rank at most r has
at most r positive eigenvalues, so a perturbation A - B of rank at most r gives the rank
interlacing λ_{i+r}(A) ≤ λᵢ(B). Consequently the numbers of eigenvalues of A and B in
(-∞, t], counted with multiplicity, differ by at most rank (A - B) for every t. Divided by
the size, this is the uniform bound on the difference of the distribution functions of the
empirical spectral measures that drives truncation arguments for random matrices.
References #
- R. A. Horn, C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press (2013), Theorem 4.3.1 (Weyl's perturbation inequality).
- R. Bhatia, Matrix Analysis, Springer (1997), Theorem III.2.1 (Weyl's inequalities).
- Z. Bai, J. W. Silverstein, Spectral Analysis of Large Dimensional Random Matrices, 2nd ed., Springer (2010), Theorem A.43 (the rank inequality for spectral distribution functions).
- R. Vershynin, High-Dimensional Probability, Cambridge University Press (2018), Chapter 4 (matrix norm bounds and spectral estimates).
Entrywise perturbations of size ε change every sorted eigenvalue of a Hermitian matrix
by at most card ι * ε.
An entrywise bound on a Hermitian matrix bounds the absolute value of each sorted eigenvalue by the matrix size times that bound.
Weyl's perturbation bound for ordered eigenvalues of Hermitian matrices: corresponding eigenvalues differ by at most the Euclidean operator norm of the matrix difference.
A Hermitian perturbation smaller than the distance of a sorted eigenvalue from c
preserves whether that eigenvalue belongs to [c, ∞). The norm is the Euclidean operator
norm.
Hermitian perturbations of Euclidean operator norm less than a spectral gap around
c preserve the number of eigenvalues in [c, ∞), with multiplicity. The gap bound may
be attained, and the matrix index type may be empty.
Reindexing a sorted eigenvalue by the canonical finite equivalence gives the corresponding matrix-indexed eigenvalue.
The rank of a Hermitian matrix counts its nonzero sorted eigenvalues, with multiplicity.
Every entry of the sorted eigenvalue list of a positive-semidefinite matrix is nonnegative.
A sorted eigenvalue of a positive-semidefinite matrix vanishes from the rank onward.
A positive-semidefinite matrix has rank at most d exactly when its sorted eigenvalues
vanish at all indices at least d. The criterion also applies when d exceeds the size.
Weyl's additive inequalities and rank perturbations #
Weyl's additive inequality for Hermitian matrices, upper form: if i + j ≤ k, then
λₖ(A + B) ≤ λᵢ(A) + λⱼ(B) for the decreasing enumerations eigenvalues₀. For k = i + j
this is the classical λ_{i+j-1}(A + B) ≤ λᵢ(A) + λⱼ(B) in one-based indexing.
Weyl's additive inequality for Hermitian matrices, lower form: if
k + card ι ≤ i + j + 1, then λᵢ(A) + λⱼ(B) ≤ λₖ(A + B) for the decreasing enumerations
eigenvalues₀.
A Hermitian matrix of rank at most r has at most r positive eigenvalues: its sorted
eigenvalues are nonpositive from index r on.
Rank interlacing. If A - B has rank at most r, then λ_{i+r}(A) ≤ λᵢ(B): a
Hermitian perturbation of rank at most r raises each sorted eigenvalue no higher than the one
r places before it.
Rank perturbation of eigenvalue counts. Passing from B to A increases the number of
sorted eigenvalues in (-∞, t], counted with multiplicity, by at most rank (A - B).
Rank perturbation bound for eigenvalue counts. The numbers of sorted eigenvalues of two
Hermitian matrices in (-∞, t], counted with multiplicity, differ by at most the rank of their
difference.