Min-max theorem
Encyclopedia
In linear algebra
and functional analysis
, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact
Hermitian operators on Hilbert spaces. It can be viewed as the starting point of many results of similar nature.
This article first discusses the finite dimensional case and its applications before considering compact operators on infinite dimensional Hilbert spaces. We will see that for compact operators, the proof of the main theorem uses essentially the same idea from the finite dimensional argument.
The min-max theorem can be extended to self adjoint operators that are bounded below.
where (·, ·) denotes the Euclidean inner product on Cn. Equivalently, the Rayleigh–Ritz quotient can be replaced by
For Hermitian matrices, the range of the continuous function R(x), or f(x), is a compact subset [a, b] of the real line. The maximum b and the minimum a are the largest and smallest eigenvalue of A, respectively. The min-max theorem is a refinement of this fact.
Lemma Let Sk be a k dimensional subspace.
Proof:
From the above lemma follows readily the min-max theorem.
Theorem (Min-max) If the eigenvalues of A are listed in increasing order λ1 ≤ ... ≤ λk ≤ ... ≤ λn, then for all k dimensional subspace Sk,
This implies
The min-max theorem consists of the above two equalities.
Equality is achieved when Sk is span{u1...uk}. Therefore
where the ↑ indicates it is the kth eigenvalue in the increasing order. Similarly, the second part of lemma gives
Similarly,
of A if there exists an orthogonal projection P onto a subspace of dimension m such that PAP = B. The Cauchy interlacing theorem states:
Theorem If the eigenvalues of A are α1 ≤ ... ≤ αn, and those of B are β1 ≤ ... βj ... ≤ βm, then for all j < m+1,
This can be proven using the min-max principle. Let βi have corresponding eigenvector bi and Sj be the j dimensional subspace Sj = span{b1...bj}, then
According to first part of min-max,
On the other hand, if we define Sm−j+1 = span{bj...bm}, then
where the last inequality is given by the second part of min-max.
Notice that, when n − m = 1, we have
Hence the name interlacing theorem.
, Hermitian
operator on a Hilbert space H. Recall that the spectrum
of such an operator form a sequence of real numbers whose only possible cluster point is zero. Every nonzero number in the spectrum is an eigenvalue. It no longer makes sense here to list the positive eigenvalues in increasing order. Let the positive eigenvalues of A be
where multiplicity is taken into account as in the matrix case. When H is infinite dimensional, the above sequence of eigenvalues is necessarily infinite. We now apply the same reasoning as in the matrix case. Let Sk ⊂ H be a k dimensional subspace, and S' be the closure of the linear span S' = span{uk, uk + 1, ...}. The subspace S' has codimension k − 1. By the same dimension count argument as in the matrix case, S' ∩ Sk is non empty. So there exists x ∈ S' ∩ Sk with ||x|| = 1. Since it is an element of S' , such an x necessarily satisfy
Therefore, for all Sk
But A is compact, therefore the function f(x) = (Ax, x) is weakly continuous. Furthermore, any bounded set in H is weakly compact. This lets us replace the infimum by minimum:
So
Because equality is achieved when Sk = span{&u;1...&u;k},
This is the first part of min-max theorem for compact self-adjoint operators.
Analogously, consider now a k − 1 dimensional subspace Sk−1, whose the orthogonal compliment is denoted by Sk−1⊥. If S' = span{u1...uk},
So
This implies
where the compactness of A was applied. Index the above by the collection of (k − 1)-dimensional subspaces gives
Pick Sk−1 = span{u1...uk−1} and we deduce
In summary,
Theorem (Min-Max) Let A be a compact, self-adjoint operator on a Hilbert space H, whose positive eigenvalues are listed in decreasing order:
Then
A similar pair of equalities hold for negative eigenvalues.
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
and functional analysis
Functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure and the linear operators acting upon these spaces and respecting these structures in a suitable sense...
, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact
Compact operator on Hilbert space
In functional analysis, compact operators on Hilbert spaces are a direct extension of matrices: in the Hilbert spaces, they are precisely the closure of finite-rank operators in the uniform operator topology. As such, results from matrix theory can sometimes be extended to compact operators using...
Hermitian operators on Hilbert spaces. It can be viewed as the starting point of many results of similar nature.
This article first discusses the finite dimensional case and its applications before considering compact operators on infinite dimensional Hilbert spaces. We will see that for compact operators, the proof of the main theorem uses essentially the same idea from the finite dimensional argument.
The min-max theorem can be extended to self adjoint operators that are bounded below.
Matrices
Let A be a n × n Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient R: Cn → R defined bywhere (·, ·) denotes the Euclidean inner product on Cn. Equivalently, the Rayleigh–Ritz quotient can be replaced by
For Hermitian matrices, the range of the continuous function R(x), or f(x), is a compact subset [a, b] of the real line. The maximum b and the minimum a are the largest and smallest eigenvalue of A, respectively. The min-max theorem is a refinement of this fact.
Lemma Let Sk be a k dimensional subspace.
- If the eigenvalues of A are listed in increasing order λ1 ≤ ... ≤ λk ≤ ... ≤ λn, then there exists x ∈ Sk, ||x|| = 1 such that (Ax, x) ≥ λk.
- Similarly, if the eigenvalues of A are listed in decreasing order λ1 ≥ ... ≥ λk ≥ ... ≥ λn, then there exists y ∈ Sk, ||y|| = 1 such that (Ay, y) ≤ λk.
Proof:
- Let ui be the eigenvector corresponding to λi. Consider the subspace S' = span{uk...un}. Simply by counting dimensions, we see that the subspace S' ∩ Sk is not equal to {0}. So there exists x ∈ S' ∩ Sk with ||x|| = 1. But for all x ∈ S' , (Ax, x) ≥ λk. So the claim holds.
- Exactly the same as 1. above.
From the above lemma follows readily the min-max theorem.
Theorem (Min-max) If the eigenvalues of A are listed in increasing order λ1 ≤ ... ≤ λk ≤ ... ≤ λn, then for all k dimensional subspace Sk,
This implies
The min-max theorem consists of the above two equalities.
Equality is achieved when Sk is span{u1...uk}. Therefore
where the ↑ indicates it is the kth eigenvalue in the increasing order. Similarly, the second part of lemma gives
Min-max principle for singular values
The singular values {σk} of a square matrix M are the square roots of eigenvalues of M*M (equivalently MM*). An immediate consequence of the first equality from min-max theorem isSimilarly,
Cauchy interlacing theorem
Let A be a n × n matrix. The m × m matrix B, where m ≤ n, is called a compressionCompression (functional analysis)
In functional analysis, the compression of a linear operator T on a Hilbert space to a subspace K is the operatorP_K T \vert_K : K \rightarrow K...
of A if there exists an orthogonal projection P onto a subspace of dimension m such that PAP = B. The Cauchy interlacing theorem states:
Theorem If the eigenvalues of A are α1 ≤ ... ≤ αn, and those of B are β1 ≤ ... βj ... ≤ βm, then for all j < m+1,
This can be proven using the min-max principle. Let βi have corresponding eigenvector bi and Sj be the j dimensional subspace Sj = span{b1...bj}, then
According to first part of min-max,
On the other hand, if we define Sm−j+1 = span{bj...bm}, then
where the last inequality is given by the second part of min-max.
Notice that, when n − m = 1, we have
Hence the name interlacing theorem.
Compact operators
Let A be a compactCompact operator on Hilbert space
In functional analysis, compact operators on Hilbert spaces are a direct extension of matrices: in the Hilbert spaces, they are precisely the closure of finite-rank operators in the uniform operator topology. As such, results from matrix theory can sometimes be extended to compact operators using...
, Hermitian
Hermitian
A number of mathematical entities are named Hermitian, after the mathematician Charles Hermite:*Hermitian adjoint*Hermitian connection, the unique connection on a Hermitian manifold that satisfies specific conditions...
operator on a Hilbert space H. Recall that the spectrum
Spectrum (functional analysis)
In functional analysis, the concept of the spectrum of a bounded operator is a generalisation of the concept of eigenvalues for matrices. Specifically, a complex number λ is said to be in the spectrum of a bounded linear operator T if λI − T is not invertible, where I is the...
of such an operator form a sequence of real numbers whose only possible cluster point is zero. Every nonzero number in the spectrum is an eigenvalue. It no longer makes sense here to list the positive eigenvalues in increasing order. Let the positive eigenvalues of A be
where multiplicity is taken into account as in the matrix case. When H is infinite dimensional, the above sequence of eigenvalues is necessarily infinite. We now apply the same reasoning as in the matrix case. Let Sk ⊂ H be a k dimensional subspace, and S' be the closure of the linear span S' = span{uk, uk + 1, ...}. The subspace S' has codimension k − 1. By the same dimension count argument as in the matrix case, S' ∩ Sk is non empty. So there exists x ∈ S' ∩ Sk with ||x|| = 1. Since it is an element of S' , such an x necessarily satisfy
Therefore, for all Sk
But A is compact, therefore the function f(x) = (Ax, x) is weakly continuous. Furthermore, any bounded set in H is weakly compact. This lets us replace the infimum by minimum:
So
Because equality is achieved when Sk = span{&u;1...&u;k},
This is the first part of min-max theorem for compact self-adjoint operators.
Analogously, consider now a k − 1 dimensional subspace Sk−1, whose the orthogonal compliment is denoted by Sk−1⊥. If S' = span{u1...uk},
So
This implies
where the compactness of A was applied. Index the above by the collection of (k − 1)-dimensional subspaces gives
Pick Sk−1 = span{u1...uk−1} and we deduce
In summary,
Theorem (Min-Max) Let A be a compact, self-adjoint operator on a Hilbert space H, whose positive eigenvalues are listed in decreasing order:
Then
A similar pair of equalities hold for negative eigenvalues.