Min max теорема

From Wikipedia, the free 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.

In the case that the operator is non-Hermitian, the theorem provides an equivalent characterization of the associated singular values.
The min-max theorem can be extended to self-adjoint operators that are bounded below.

Matrices[edit]

Let A be a n × n Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient R_A : Cⁿ {0} → R defined by

where (⋅, ⋅) denotes the Euclidean inner product on Cⁿ.
Clearly, the Rayleigh quotient of an eigenvector is its associated eigenvalue. Equivalently, the Rayleigh–Ritz quotient can be replaced by

For Hermitian matrices A, the range of the continuous function R_A(x), or f(x), is a compact interval [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.

Min-max theorem[edit]

Let A be an n × n Hermitian matrix with eigenvalues λ₁ ≤ … ≤ λ_k ≤ … ≤ λ_n, then

and

,

in particular,

and these bounds are attained when x is an eigenvector of the appropriate eigenvalues.

Also the simpler formulation for the maximal eigenvalue λ_n is given by:

Similarly, the minimal eigenvalue λ₁ is given by:

Counterexample in the non-Hermitian case[edit]

Let N be the nilpotent matrix

Define the Rayleigh quotient exactly as above in the Hermitian case. Then it is easy to see that the only eigenvalue of N is zero, while the maximum value of the Rayleigh quotient is 1/2. That is, the maximum value of the Rayleigh quotient is larger than the maximum eigenvalue.

Applications[edit]

Min-max principle for singular values[edit]

The singular values {σ_k} of a square matrix M are the square roots of the eigenvalues of M*M (equivalently MM*). An immediate consequence^{[citation needed]} of the first equality in the min-max theorem is:

Similarly,

Here denotes the k^th entry in the increasing sequence of σ’s, so that .

Cauchy interlacing theorem[edit]

Let A be a symmetric n × n matrix. The m × m matrix B, where m ≤ n, is called a compression 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 α₁ ≤ … ≤ α_n, and those of B are β₁ ≤ … ≤ β_j ≤ … ≤ β_m, then for all j ≤ m,

This can be proven using the min-max principle. Let β_i have corresponding eigenvector b_i and S_j be the j dimensional subspace S_j = span{b₁, …, b_j}, then

According to first part of min-max, α_j ≤ β_j. On the other hand, if we define S_m−j+1 = span{b_j, …, b_m}, then

where the last inequality is given by the second part of min-max.

When n − m = 1, we have α_j ≤ β_j ≤ α_j+1, hence the name interlacing theorem.

Compact operators[edit]

Let A be a compact, Hermitian operator on a Hilbert space H. Recall that the spectrum of such an operator (the set of eigenvalues) is a set of real numbers whose only possible cluster point is zero.
It is thus convenient to list the positive eigenvalues of A as

where entries are repeated with multiplicity, as in the matrix case. (To emphasize that the sequence is decreasing, we may write .)
When H is infinite-dimensional, the above sequence of eigenvalues is necessarily infinite.
We now apply the same reasoning as in the matrix case. Letting S_k ⊂ H be a k dimensional subspace, we can obtain the following theorem.

Theorem (Min-Max). Let A be a compact, self-adjoint operator on a Hilbert space H, whose positive eigenvalues are listed in decreasing order … ≤ λ_k ≤ … ≤ λ₁. Then:

A similar pair of equalities hold for negative eigenvalues.

Self-adjoint operators[edit]

The min-max theorem also applies to (possibly unbounded) self-adjoint operators.^[1][2] Recall the essential spectrum is the spectrum without isolated eigenvalues of finite multiplicity.
Sometimes we have some eigenvalues below the essential spectrum, and we would like to approximate the eigenvalues and eigenfunctions.

Theorem (Min-Max). Let A be self-adjoint, and let be the eigenvalues of A below the essential spectrum. Then

.

If we only have N eigenvalues and hence run out of eigenvalues, then we let (the bottom of the essential spectrum) for n>N, and the above statement holds after replacing min-max with inf-sup.

Theorem (Max-Min). Let A be self-adjoint, and let be the eigenvalues of A below the essential spectrum. Then

.

If we only have N eigenvalues and hence run out of eigenvalues, then we let (the bottom of the essential spectrum) for n > N, and the above statement holds after replacing max-min with sup-inf.

The proofs^[1][2] use the following results about self-adjoint operators:

Theorem. Let A be self-adjoint. Then for if and only if .^[1]: 77

Theorem. If A is self-adjoint, then

and

.^[1]: 77

See also[edit]

• Courant minimax principle
• Max–min inequality

References[edit]

External links and citations to related work[edit]

• Fisk, Steve (2005). «A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian matrices». arXiv:math/0502408.
• Hwang, Suk-Geun (2004). «Cauchy’s Interlace Theorem for Eigenvalues of Hermitian Matrices». The American Mathematical Monthly. 111 (2): 157–159. doi:10.2307/4145217. JSTOR 4145217.
• Kline, Jeffery (2020). «Bordered Hermitian matrices and sums of the Möbius function». Linear Algebra and Its Applications. 588: 224–237. doi:10.1016/j.laa.2019.12.004.
• Reed, Michael; Simon, Barry (1978). Methods of Modern Mathematical Physics IV: Analysis of Operators. Academic Press. ISBN 978-0-08-057045-7.

В линейной алгебре и функциональном анализе мин- теорема максимума, или вариационная теорема, или принцип мин-макс Куранта – Фишера – Вейля, является результатом, который дает вариационную характеристику собственных значений компактные эрмитовы операторы в гильбертовых пространствах. Его можно рассматривать как отправную точку для многих результатов аналогичного характера.

В этой статье сначала обсуждается конечномерный случай и его приложения, а затем рассматриваются компактные операторы в бесконечномерных гильбертовых пространствах. Мы увидим, что для компактных операторов доказательство основной теоремы по существу использует ту же идею из конечномерного аргумента.

В случае, если оператор неэрмитов, теорема обеспечивает эквивалентную характеристику связанных сингулярных значений. Теорема min-max может быть расширена до самосопряженных операторов, ограниченных снизу.

Содержание

• 1 Матрицы
  • 1.1 Теорема о минимуме и максимуме
  • 1.2 Контрпример в неэрмитовском случае
• 2 Приложения
  • 2.1 Принцип минимума и максимума для сингулярных значений
  • 2.2 Чередование Коши теорема
• 3 Компактные операторы
• 4 Самосопряженные операторы
• 5 См. также
• 6 Ссылки

Матрицы

Пусть A будет × n эрмитовой матрицей. Как и во многих других вариационных результатах для собственных значений, рассматривается фактор Рэлея – Ритца RA: C {0} → R, определяемый как

RA (x) = (A x, x) (x, x) { displaystyle R_ {A} (x) = { frac {(Ax, x)} {(x, x)}}}

где (⋅, ⋅) обозначает евклидово внутреннее произведение на С . Ясно, что фактор Рэлея собственного вектора — это соответствующее собственное значение. Эквивалентно, частное Рэлея – Ритца можно заменить на

f (x) = (A x, x), ‖ x ‖ = 1. { displaystyle f (x) = (Ax, x), ; | x | = 1.}

Для эрмитовых матриц область значений непрерывной функции R A (x) или f (x) является компактным подмножеством [a, b] вещественного линия. Максимум b и минимум a — это наибольшее и наименьшее собственное значение A соответственно. Теорема о мин-макс является уточнением этого факта.

Теорема о минимуме и максимуме

Пусть A будет n × n эрмитовой матрицей с собственными значениями λ 1 ≤… ≤ λ k ≤… ≤ λ n, тогда

λ k = min U {max x {RA (x) ∣ x ∈ U и x ≠ 0} ∣ dim ⁡ (U) = k} { displaystyle lambda _ {k} = min _ {U} { max _ {x} {R_ {A} (x) mid x in U { text {and}} x neq 0 } mid dim (U) = k }}

и

λ k = max U {min x {RA (x) ∣ x ∈ U и x ≠ 0} ∣ dim ⁡ (U) = N — К + 1} { Displaystyle lambda _ {k} = max _ {U} { min _ {x} {R_ {A} (x) mid x in U { text {and}} x neq 0 } mid dim (U) = n-k + 1 }}

, в частности,

λ 1 ≤ RA (x) ≤ λ n ∀ x ∈ C n ∖ {0} { displaystyle lambda _ {1} leq R_ {A} (x) leq lambda _ {n} quad forall x in mathbf {C} ^ {n} backslash { 0 }}

, и эти границы достигаются, когда x является собственным вектором соответствующих собственных значений.

Также более простая формулировка для максимального собственного значения λ n дается формулой

λ n = max {R A (x): x ≠ 0}. { displaystyle lambda _ {n} = max {R_ {A} (x): x neq 0 }.}

Аналогично, минимальное собственное значение λ 1 задается следующим образом:

λ 1 = min {RA (x): x ≠ 0}. { displaystyle lambda _ {1} = min {R_ {A} (x): x neq 0 }.}

Доказательство —

Поскольку матрица A эрмитова, она диагонализуема и мы можем выбрать ортонормированный базис собственных векторов {u 1,…, u n }, то есть u i является собственным вектором для собственного значения λ i и такие, что (u i, u i) = 1 и (u i, u j) = 0 для всех i ≠ j.

Если U — подпространство размерности k, то его пересечение с подпространством span {u k,…, u n } не равно нулю (по просто проверяя размеры), и, следовательно, существует вектор v ≠ 0 на этом пересечении, который мы можем записать как

v = ∑ i = kn α iui { displaystyle v = sum _ {i = k} ^ {n} альфа _ {i} u_ {i}}

и коэффициент Рэлея которого равен

RA (v) = ∑ i = kn λ i α i 2 ∑ i = kn α i 2 ≥ λ k { displaystyle R_ { A} (v) = { frac { sum _ {i = k} ^ {n} lambda _ {i} alpha _ {i} ^ {2}} { sum _ {i = k} ^ { n} alpha _ {i} ^ {2}}} geq lambda _ {k}}

(как и все λ я ≥ λ k { displaystyle lambda _ {i} geq lambda _ {k}}для i = k,.., n) и, следовательно,

max {RA (x) ∣ x ∈ U} ≥ λ k { displaystyle max {R_ {A } (x) mid x in U } geq lambda _ {k}}

Поскольку это верно для всех U, мы можем заключить, что

min {max {RA (x) ∣ x ∈ U и Икс ≠ 0} ∣ тусклый ⁡ (U) = k} ≥ λ К { Displaystyle min { max {R_ {A} (x) mid x in U { text {and}} x neq 0 } mid dim (U) = k } geq lambda _ {k}}

Это один в равенство. Чтобы установить другое неравенство, выберите конкретное k-мерное пространство V = span {u 1,…, u k }, для которого

max {RA (x) ∣ Икс ∈ В и Икс ≠ 0} ≤ λ К { Displaystyle max {R_ {A} (x) mid x in V { text {and}} x neq 0 } leq lambda _ {k}}

, поскольку λ k { displaystyle lambda _ {k}}является наибольшим собственным значением в V. Следовательно, также

min {max {RA (x) ∣ x ∈ U и x 0} ∣ dim ⁡ (U) = k} ≤ λ k { displaystyle min { max {R_ {A} (x) mid x in U { text { и}} x neq 0 } mid dim (U) = k } leq lambda _ {k}}

. В случае, когда U — подпространство размерности n-k + 1, мы продолжаем аналогичным образом: рассмотрим подпространство размерности k, span {u 1,…, u k }. Его пересечение с подпространством U не равно нулю (просто проверяя размеры), и, следовательно, существует вектор v в этом пересечении, который мы можем записать как

v = ∑ i = 1 k α iui { displaystyle v = sum _ {i = 1} ^ {k} alpha _ {i} u_ {i}}

и коэффициент Рэлея которого равен

RA (v) = ∑ i = 1 k λ i α i 2 ∑ i = 1 К α я 2 ≤ λ К { Displaystyle R_ {A} (v) = { гидроразрыва { sum _ {i = 1} ^ {k} lambda _ {i} alpha _ {i} ^ {2 }} { sum _ {i = 1} ^ {k} alpha _ {i} ^ {2}}} leq lambda _ {k}}

и, следовательно,

min {RA (x) ∣ Икс ∈ U} ≤ λ К { Displaystyle min {R_ {A} (x) mid x in U } leq lambda _ {k}}

Поскольку это верно для всех U, мы можем заключить, что

max {min {RA (x) ∣ x ∈ U и x ≠ 0} ∣ dim ⁡ (U) = n — k + 1} ≤ λ k { displaystyle max { min {R_ {A} (x) mid x in U { text {and}} x neq 0 } mid dim (U) = n-k + 1 } leq lambda _ {k} }

Опять же, это одна часть уравнения. Чтобы получить другое неравенство, отметим еще раз, что собственный вектор u для λ k { displaystyle lambda _ {k}}содержится в U = span {u k,…, u n }, так что мы можем заключить равенство.

Контрпример в неэрмитовом случае

Пусть N — нильпотентная матрица

[0 1 0 0]. { displaystyle { begin {bmatrix} 0 1 \ 0 0 end {bmatrix}}.}

Определите частное Рэлея RN (x) { displaystyle R_ {N} (x)}точно так же, как в эрмитовом случае. Тогда легко увидеть, что единственное собственное значение N равно нулю, в то время как максимальное значение отношения Рэлея равно 1/2. То есть максимальное значение отношения Рэлея больше максимального собственного значения.

Приложения

Принцип минимума-максимума для сингулярных значений

Особые значения {σk} квадратной матрицы M являются квадратными корнями из собственных значений матрицы M * M (эквивалентно MM *). Непосредственным следствием первого равенства в теореме min-max является:

σ k ↑ = min S: dim ⁡ (S) = k max x ∈ S, ‖ x ‖ = 1 (M ∗ M x, x) 1 2 = min S: dim ⁡ (S) = k max x ∈ S, ‖ x ‖ = 1 ‖ M x ‖. { displaystyle sigma _ {k} ^ { uparrow} = min _ {S: dim (S) = k} max _ {x in S, | x | = 1} (M ^ { *} Mx, x) ^ { frac {1} {2}} = min _ {S: dim (S) = k} max _ {x in S, | x | = 1} | Mx |.}

Аналогично

σ k ↑ = max S: dim ⁡ (S) = n — k + 1 min x ∈ S, ‖ x ‖ = 1 ‖ M x ‖. { displaystyle sigma _ {k} ^ { uparrow} = max _ {S: dim (S) = n-k + 1} min _ {x in S, | x | = 1} | Mx |.}

Здесь σ k = σ k ↑ { displaystyle sigma _ {k} = sigma _ {k} ^ { uparrow}}обозначает k запись в возрастающей последовательности σ, так что σ 1 ≤ σ 2 ≤ ⋯ { displaystyle sigma _ {1} leq sigma _ {2} leq cdots}.

теорема Коши о чересстрочной развертке

Пусть A — симметричная матрица размера n × n. Матрица B размером m × m, где m ≤ n, называется сжатием матрицы A, если существует ортогональная проекция P на подпространство размерности m, такое как что PAP * = B. Теорема Коши утверждает:

Теорема. Если собственные значения A равны α 1 ≤… ≤ α n, и те из B равны β 1 ≤… ≤ β j ≤… ≤ β m, тогда для всех j ≤ m

α j ≤ β j ≤ α n — m + j. { displaystyle alpha _ {j} leq beta _ {j} leq alpha _ {n-m + j}.}

Это можно доказать, используя принцип минимума-максимума. Пусть β i имеет соответствующий собственный вектор b i, а S j будет j-мерным подпространством S j = span {b 1,…, b j }, тогда

β j = max x ∈ S j, ‖ x ‖ = 1 (B x, x) = max x ∈ S j, ‖ x ‖ = 1 (PAP ∗ x, x) ≥ min S j max x ∈ S j, ‖ x ‖ = 1 (A (P ∗ x), P ∗ x) = α j. { displaystyle beta _ {j} = max _ {x in S_ {j}, | x | = 1} (Bx, x) = max _ {x in S_ {j}, | x | = 1} (PAP ^ {*} x, x) geq min _ {S_ {j}} max _ {x in S_ {j}, | x | = 1} (A ( P ^ {*} x), P ^ {*} x) = alpha _ {j}.}

Согласно первой части min-max, α j ≤ β j. С другой стороны, если мы определим S m − j + 1 = span {b j,…, b m }, то

β j = min x ∈ S m — j + 1, ‖ x ‖ = 1 (B x, x) = min x ∈ S m — j + 1, ‖ x ‖ = 1 (PAP ∗ x, x) = min x ∈ S м — J + 1, ‖ Икс ‖ знак равно 1 (A (P ∗ x), P ∗ x) ≤ α N — m + j, { displaystyle beta _ {j} = min _ {x in S_ {m-j + 1}, | x | = 1} (Bx, x) = min _ {x in S_ {m-j + 1}, | x | = 1} (PAP ^ {*} x, x) = min _ {x in S_ {m-j + 1}, | x | = 1} (A (P ^ {*} x), P ^ {*} x) leq alpha _ {n-m + j},}

где последнее неравенство дается второй частью min-max.

Когда n — m = 1, мы имеем α j ≤ β j ≤ α j + 1, отсюда и название теоремы о чередовании.

Компактные операторы

Пусть A компактный, эрмитов оператор в гильбертовом пространстве H. Напомним, что спектр такого оператора (набор собственных значений) представляет собой набор действительных чисел, единственная возможная точка кластера которого равна нулю. Таким образом, удобно перечислить положительные собственные значения A как

⋯ ≤ λ k ≤ ⋯ ≤ λ 1, { displaystyle cdots leq lambda _ {k} leq cdots leq lambda _ {1},}

, где элементы повторяются с кратностью, как в матричном случае. (Чтобы подчеркнуть, что последовательность убывает, мы можем написать λ k = λ k ↓ { displaystyle lambda _ {k} = lambda _ {k} ^ { downarrow}}.) Когда H бесконечномерно, указанная выше последовательность собственных значений обязательно бесконечна. Теперь применим те же рассуждения, что и в матричном случае. Если S k ⊂ H — k-мерное подпространство, мы можем получить следующую теорему.

Теорема (Мин-Макс). Пусть A — компактный самосопряженный оператор в гильбертовом пространстве H, положительные собственные значения которого перечислены в порядке убывания… ≤ λ k ≤… ≤ λ 1. Тогда:

max S k min x ∈ S k, ‖ x ‖ = 1 (A x, x) = λ k ↓, min S k — 1 max x ∈ S k — 1 ⊥, ‖ x ‖ = 1 ( A x, x) = λ k ↓. { displaystyle { begin {align} max _ {S_ {k}} min _ {x in S_ {k}, | x | = 1} (Ax, x) = lambda _ {k } ^ { downarrow}, \ min _ {S_ {k-1}} max _ {x in S_ {k-1} ^ { perp}, | x | = 1} (Ax, x) = lambda _ {k} ^ { downarrow}. end {align}}}

Аналогичная пара равенств верна для отрицательных собственных значений.

Доказательство —

Пусть S ‘будет замыканием линейного промежутка S’ = span ⁡ {uk, uk + 1,…} { displaystyle S ‘= operatorname {span} {u_ {k}, u_ {k + 1}, ldots }}. Подпространство S ‘имеет коразмерность k — 1. По тому же аргументу, что и в случае матрицы, S’ ∩ S k непусто. Итак, существует x ∈ S ‘∩ S k с ‖ x ‖ = 1 { displaystyle | x | = 1}. Поскольку он является элементом S ‘, такой x обязательно удовлетворяет

(A x, x) ≤ λ k. { displaystyle (Ax, x) leq lambda _ {k}.}

Следовательно, для всех S k

inf x ∈ S k, ‖ x ‖ = 1 (A x, x) ≤ λ k { displaystyle inf _ {x in S_ {k}, | x | = 1} (Ax, x) leq lambda _ {k}}

Но A компактно, поэтому функция f (x) = (Ax, x) слабо непрерывно. Более того, любое ограниченное множество в H слабо компактно. Это позволяет заменить нижнюю грань на минимум:

min x ∈ S k, ‖ x ‖ = 1 (A x, x) ≤ λ k. { displaystyle min _ {x in S_ {k}, | x | = 1} (Ax, x) leq lambda _ {k}.}

Итак,

sup S k min x ∈ S k, ‖ x ‖ = 1 (A x, x) ≤ λ k. { displaystyle sup _ {S_ {k}} min _ {x in S_ {k}, | x | = 1} (Ax, x) leq lambda _ {k}.}

Поскольку равенство достигается, когда S k = span ⁡ {u 1,…, uk} { displaystyle S_ {k} = operatorname {span} {u_ {1}, ldots, u_ {k} } },

max S k min x ∈ S k, ‖ x ‖ = 1 (A x, x) = λ k. { displaystyle max _ {S_ {k}} min _ {x in S_ {k}, | x | = 1} (Ax, x) = lambda _ {k}.}

Это является первой частью теоремы о минимуме и максимуме для компактных самосопряженных операторов.

Аналогично, рассмотрим теперь (k — 1) -мерное подпространство S k − 1, ортогональное дополнение которого обозначается S k − 1. Если S ‘= span {u 1… u k },

S ′ ∩ S k — 1 ⊥ ≠ 0. { Displaystyle S ‘ cap S_ {k-1} ^ { perp} neq {0}.}

Итак,

∃ x ∈ S k — 1 ⊥ ‖ x ‖ = 1, (A x, х) ≥ λ k. { displaystyle существует x in S_ {k-1} ^ { perp} , | x | = 1, (Ax, x) geq lambda _ {k}.}

Это означает

макс Икс ∈ S К — 1 ⊥, ‖ Икс ‖ знак равно 1 (А Икс, Икс) ≥ λ К { Displaystyle макс _ {х в S_ {к-1} ^ { perp}, | х | = 1} (Ax, x) geq lambda _ {k}}

, где применялась компактность A. Индексирование указанного выше набора k-1-мерных подпространств дает

inf S k — 1 max x ∈ S k — 1 ⊥, ‖ x ‖ = 1 (A x, x) ≥ λ k. { displaystyle inf _ {S_ {k-1}} max _ {x in S_ {k-1} ^ { perp}, | x | = 1} (Ax, x) geq lambda _ {k}.}

Выбираем S k − 1 = span {u 1,…, u k − 1 }, и мы выводим

min S k — 1 max x ∈ S k — 1 ⊥, ‖ x ‖ = 1 (A x, x) = λ k. { displaystyle min _ {S_ {k-1}} max _ {x in S_ {k-1} ^ { perp}, | x | = 1} (Ax, x) = lambda _ {k}.}

Самосопряженные операторы

Теорема о минимуме и максимуме также применима к (возможно, неограниченным) самосопряженным операторам. Напомним, существенный спектр — это спектр без изолированных конечнократных собственных значений. Иногда у нас есть собственные значения ниже существенного спектра, и мы хотели бы аппроксимировать собственные значения и собственные функции.

Теорема (Мин-Макс). Пусть A самосопряжен, и пусть E 1 ≤ E 2 ≤ E 3 ≤ ⋯ { displaystyle E_ {1} leq E_ {2} leq E_ {3} leq cdots}— собственные значения A ниже существенного спектра. Тогда

E n = min ψ 1,…, ψ n max {⟨ψ, A ψ⟩: ψ ∈ span ⁡ (ψ 1,…, ψ n), ‖ ψ ‖ = 1} { displaystyle E_ {n } = min _ { psi _ {1}, ldots, psi _ {n}} max { langle psi, A psi rangle: psi in operatorname {span} ( psi _ {1}, ldots, psi _ {n}), , | psi | = 1 }}.

Если у нас есть только N собственных значений и, следовательно, они исчерпываются, то мы полагаем E n: = inf σ ess (A) { displaystyle E_ {n}: = inf sigma _ {ess} (A)}(нижняя часть основного спектра) для n>N, и приведенное выше утверждение остается в силе после замены min-max на inf-sup.

Теорема (Max-Min). Пусть A самосопряженный, и пусть E 1 ≤ E 2 ≤ E 3 ≤ ⋯ { displaystyle E_ {1} leq E_ {2} leq E_ {3} leq cdots}— собственные значения A ниже существенного спектра. Тогда

E n = max ψ 1,…, ψ n — 1 min {⟨ψ, A ψ⟩: ψ ⊥ ψ 1,…, ψ n — 1, ‖ ψ ‖ = 1} { displaystyle E_ {n } = max _ { psi _ {1}, ldots, psi _ {n-1}} min { langle psi, A psi rangle: psi perp psi _ {1}, ldots, psi _ {n-1}, , | psi | = 1 }}.

Если у нас есть только N собственных значений и, следовательно, они исчерпаны, то мы позволяем E n : = inf σ ess (A) { displaystyle E_ {n}: = inf sigma _ {ess} (A)}(нижняя часть основного спектра) для n>N, и Приведенное выше утверждение остается в силе после замены max-min на sup-inf.

В доказательствах используются следующие результаты о самосопряженных операторах:

Теорема. Пусть A самосопряженный. Тогда (A — E) ≥ 0 { displaystyle (AE) geq 0}для E ∈ R { displaystyle E in mathbb {R}}тогда и только тогда, когда σ (A) ⊆ [E, ∞) { displaystyle sigma (A) substeq [E, infty)}.

Теорема. Если A самосопряженный, то

inf σ (A) = inf ψ ∈ D (A), ‖ ψ ‖ = 1 ⟨ψ, A ψ⟩ { displaystyle inf sigma (A) = inf _ { psi in { mathfrak {D}} (A), | psi | = 1} langle psi, A psi rangle}

и

sup σ (A) = sup ψ ∈ D (A) ‖ Ψ ‖ знак равно 1 ⟨ψ, A ψ⟩ { Displaystyle sup sigma (A) = sup _ { psi in { mathfrak {D}} (A), | psi | = 1 } langle psi, A psi rangle}.

См. также

• Принцип минимакса Куранта
• Неравенство Max – min

Литература

• M. Рид и Б. Саймон, Методы современной математической физики IV: Анализ операторов, Academic Press, 1978.

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.

In the case that the operator is non-Hermitian, the theorem provides an equivalent characterization of the associated singular values.
The min-max theorem can be extended to self-adjoint operators that are bounded below.

MatricesEdit

Let A be a n × n Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient R_A : Cⁿ {0} → R defined by

 

where (⋅, ⋅) denotes the Euclidean inner product on Cⁿ.
Clearly, the Rayleigh quotient of an eigenvector is its associated eigenvalue. Equivalently, the Rayleigh–Ritz quotient can be replaced by

 

For Hermitian matrices A, the range of the continuous function R_A(x), or f(x), is a compact interval [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.

Min-max theoremEdit

Let A be an n × n Hermitian matrix with eigenvalues λ₁ ≤ … ≤ λ_k ≤ … ≤ λ_n, then

 

and

 ,

in particular,

 

and these bounds are attained when x is an eigenvector of the appropriate eigenvalues.

Also the simpler formulation for the maximal eigenvalue λ_n is given by:

 

Similarly, the minimal eigenvalue λ₁ is given by:

 

Proof

Since the matrix A is Hermitian it is diagonalizable and we can choose an orthonormal basis of eigenvectors {u₁, …, u_n} that is, u_i is an eigenvector for the eigenvalue λ_i and such that (u_i, u_i) = 1 and (u_i, u_j) = 0 for all i ≠ j.

If U is a subspace of dimension k then its intersection with the subspace span{u_k, …, u_n} isn’t zero,
for if it were, then the dimension of the span of the two subspaces would be  , which is impossible. Hence there exists a vector v ≠ 0 in this intersection that we can write as

 

and whose Rayleigh quotient is

 

(as all   for i=k,..,n)
and hence

 

Since this is true for all U, we can conclude that

 

This is one inequality. To establish the other inequality, choose the specific k-dimensional space
V = span{u₁, …, u_k} , for which

 

because   is the largest eigenvalue in V. Therefore, also

 

To get the other formula, consider the Hermitian matrix  , whose eigenvalues in increasing order are  .
Applying the result just proved,

 

The result follows on replacing   with  .

Counterexample in the non-Hermitian caseEdit

Let N be the nilpotent matrix

 

Define the Rayleigh quotient   exactly as above in the Hermitian case. Then it is easy to see that the only eigenvalue of N is zero, while the maximum value of the Rayleigh quotient is 1/2. That is, the maximum value of the Rayleigh quotient is larger than the maximum eigenvalue.

ApplicationsEdit

Min-max principle for singular valuesEdit

The singular values {σ_k} of a square matrix M are the square roots of the eigenvalues of M*M (equivalently MM*). An immediate consequence^{[citation needed]} of the first equality in the min-max theorem is:

 

Similarly,

 

Here   denotes the k^th entry in the increasing sequence of σ’s, so that  .

Cauchy interlacing theoremEdit

Let A be a symmetric n × n matrix. The m × m matrix B, where m ≤ n, is called a compression 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 α₁ ≤ … ≤ α_n, and those of B are β₁ ≤ … ≤ β_j ≤ … ≤ β_m, then for all j ≤ m,

 

This can be proven using the min-max principle. Let β_i have corresponding eigenvector b_i and S_j be the j dimensional subspace S_j = span{b₁, …, b_j}, then

 

According to first part of min-max, α_j ≤ β_j. On the other hand, if we define S_m−j+1 = span{b_j, …, b_m}, then

 

where the last inequality is given by the second part of min-max.

When n − m = 1, we have α_j ≤ β_j ≤ α_j+1, hence the name interlacing theorem.

Compact operatorsEdit

Let A be a compact, Hermitian operator on a Hilbert space H. Recall that the spectrum of such an operator (the set of eigenvalues) is a set of real numbers whose only possible cluster point is zero.
It is thus convenient to list the positive eigenvalues of A as

 

where entries are repeated with multiplicity, as in the matrix case. (To emphasize that the sequence is decreasing, we may write  .)
When H is infinite-dimensional, the above sequence of eigenvalues is necessarily infinite.
We now apply the same reasoning as in the matrix case. Letting S_k ⊂ H be a k dimensional subspace, we can obtain the following theorem.

Theorem (Min-Max). Let A be a compact, self-adjoint operator on a Hilbert space H, whose positive eigenvalues are listed in decreasing order … ≤ λ_k ≤ … ≤ λ₁. Then:

 

A similar pair of equalities hold for negative eigenvalues.

Proof

Let S’ be the closure of the linear span  .
The subspace S’ has codimension k − 1. By the same dimension count argument as in the matrix case, S’ ∩ S_k has positive dimension. So there exists x ∈ S’  ∩ S_k with  . Since it is an element of S’ , such an x necessarily satisfy

 

Therefore, for all S_k

 

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  ,

 

This is the first part of min-max theorem for compact self-adjoint operators.

Analogously, consider now a (k − 1)-dimensional subspace S_k−1, whose the orthogonal complement is denoted by S_k−1^⊥. If S’ = span{u₁…u_k},

 

So

 

This implies

 

where the compactness of A was applied. Index the above by the collection of k-1-dimensional subspaces gives

 

Pick S_k−1 = span{u₁, …, u_k−1} and we deduce

 

Self-adjoint operatorsEdit

The min-max theorem also applies to (possibly unbounded) self-adjoint operators.^[1][2] Recall the essential spectrum is the spectrum without isolated eigenvalues of finite multiplicity.
Sometimes we have some eigenvalues below the essential spectrum, and we would like to approximate the eigenvalues and eigenfunctions.

Theorem (Min-Max). Let A be self-adjoint, and let   be the eigenvalues of A below the essential spectrum. Then

 .

If we only have N eigenvalues and hence run out of eigenvalues, then we let   (the bottom of the essential spectrum) for n>N, and the above statement holds after replacing min-max with inf-sup.

Theorem (Max-Min). Let A be self-adjoint, and let   be the eigenvalues of A below the essential spectrum. Then

 .

If we only have N eigenvalues and hence run out of eigenvalues, then we let   (the bottom of the essential spectrum) for n > N, and the above statement holds after replacing max-min with sup-inf.

The proofs^[1][2] use the following results about self-adjoint operators:

Theorem. Let A be self-adjoint. Then   for   if and only if  .^[1]: 77

Theorem. If A is self-adjoint, then

and

 .^[1]: 77

See alsoEdit

• Courant minimax principle
• Max–min inequality

ReferencesEdit

External links and citations to related workEdit

• Fisk, Steve (2005). «A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian matrices». arXiv:math/0502408.
• Hwang, Suk-Geun (2004). «Cauchy’s Interlace Theorem for Eigenvalues of Hermitian Matrices». The American Mathematical Monthly. 111 (2): 157–159. doi:10.2307/4145217. JSTOR 4145217.
• Kline, Jeffery (2020). «Bordered Hermitian matrices and sums of the Möbius function». Linear Algebra and Its Applications. 588: 224–237. doi:10.1016/j.laa.2019.12.004.
• Reed, Michael; Simon, Barry (1978). Methods of Modern Mathematical Physics IV: Analysis of Operators. Academic Press. ISBN 978-0-08-057045-7.

I’m currently studying a paper which uses extensively the term ‘min-max theorems‘ in graph theory, and claims to present a tool allowing to generalize these theorems. (here is the link to the paper if needed)

Among those, we can find for example :

• The max-flow-min cut theorem.
• Edmond’s disjoint arborescences theorem (link).

I have some intuition about what a min-max theorem would be, but I can’t come with a concise and precise definition.

My question is : what would be a definition of such a family of theorems ?

And a second question along : is this min-max theorem concept always linked to the strong duality theorem, meaning that they mainly state that one problem is actually the dual of the other, like the max-flow-min-cut is ?

Теорема мин-макс

В линейной алгебре и функциональный анализе , в теореме минимакса , или вариационной теореме или Куранта-Фишер-Вейль минимакса принципе , является результатом , который дает вариационную характеристику собственному от компактных эрмитовых операторов в гильбертовых пространствах . Его можно рассматривать как отправную точку для многих результатов аналогичного характера.

В этой статье сначала обсуждается конечномерный случай и его приложения, а затем рассматриваются компактные операторы в бесконечномерных гильбертовых пространствах. Мы увидим, что для компактных операторов доказательство основной теоремы по существу использует ту же идею из конечномерного аргумента.

В случае, когда оператор неэрмитов, теорема обеспечивает эквивалентную характеризацию связанных сингулярных значений . Теорема min-max может быть распространена на самосопряженные операторы , ограниченные снизу.

Пусть A — эрмитова матрица размера n × n . Как и во многих других вариационных результатах о собственных значениях, рассматривается фактор Рэлея – Ритца R _A  : C ⁿ {0} → R, определяемый формулой

где (⋅, ⋅) обозначает евклидов скалярное произведение на C ⁿ . Ясно, что фактор Рэлея собственного вектора — это связанное с ним собственное значение. Эквивалентно фактор Рэлея – Ритца можно заменить на

Для эрмитовых матриц A образ непрерывной функции R _A ( x ) или f ( x ) является компактным подмножеством [ a , b ] вещественной прямой. Максимум b и минимум a — это наибольшее и наименьшее собственное значение A соответственно. Теорема о минимуме и максимуме является уточнением этого факта.

---

«Variational theorem» redirects here. The term is also sometimes applied to the variational principle.

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.

Matrices

Let A be a n × n Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient R: Cⁿ → R defined by

where (·, ·) denotes the Euclidean inner product on Cⁿ. 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 S_k be a k dimensional subspace.

1. If the eigenvalues of A are listed in increasing order λ₁ ≤ … ≤ λ_k ≤ … ≤ λ_n, then there exists x ∈ S_k, ||x|| = 1 such that (Ax, x) ≥ λ_k.
2. Similarly, if the eigenvalues of A are listed in decreasing order λ₁ ≥ … ≥ λ_k ≥ … ≥ λ_n, then there exists y ∈ S_k, ||y|| = 1 such that (Ay, y) ≤ λ_k.

Proof:

1. Let u_i be the eigenvector corresponding to λ_i. Consider the subspace S’ = span{u_k…u_n}. Simply by counting dimensions, we see that the subspace S’ ∩ S_k is not equal to {0}. So there exists x ∈ S’ ∩ S_k with ||x|| = 1. But for all x ∈ S’ , (Ax, x) ≥ λ_k. So the claim holds.
2. 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 λ₁ ≤ … ≤ λ_k ≤ … ≤ λ_n, then for all k dimensional subspace S_k,

This implies

The min-max theorem consists of the above two equalities.

Equality is achieved when S_k is span{u₁…u_k}. Therefore

where the ↑ indicates it is the kth eigenvalue in the increasing order. Similarly, the second part of lemma gives

Applications

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 is

Similarly,

Cauchy interlacing theorem

Let A be a n × n matrix. The m × m matrix B, where m ≤ n, is called a compression 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 α₁ ≤ … ≤ α_n, and those of B are β₁ ≤ … β_j … ≤ β_m, then for all j < m+1,

This can be proven using the min-max principle. Let β_i have corresponding eigenvector b_i and S_j be the j dimensional subspace S_j = span{b₁…b_j}, then

According to first part of min-max,

On the other hand, if we define S_m−j+1 = span{b_j…b_m}, 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 compact, 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 S_k ⊂ H be a k dimensional subspace, and S’ be the closure of the linear span S’ = span{u_k, u_k + 1, …}. The subspace S’ has codimension k − 1. By the same dimension count argument as in the matrix case, S’ ∩ S_k is non empty. So there exists x ∈ S’  ∩ S_k with ||x|| = 1. Since it is an element of S’ , such an x necessarily satisfy

Therefore, for all S_k

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 S_k = span{&u;₁…&u;_k},

This is the first part of min-max theorem for compact self-adjoint operators.

Analogously, consider now a k − 1 dimensional subspace S_k−1, whose the orthogonal compliment is denoted by S_k−1^⊥. If S’ = span{u₁…u_k},

So

This implies

where the compactness of A was applied. Index the above by the collection of (k − 1)-dimensional subspaces gives

Pick S_k−1 = span{u₁…u_k−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.

References

• M. Reed and B. Simon, Methods of Modern Mathematical Physics IV: Analysis of Operators, Academic Press, 1978.

See also

• Courant minimax principle

«Variational theorem» redirects here. It is not to be confused with variational principle.

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.

In the case that the operator is non-Hermitian, the theorem provides an equivalent characterization of the associated singular values. 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_A : Cⁿ {0} → R defined by

where (⋅, ⋅) denotes the Euclidean inner product on Cⁿ. Clearly, the Rayleigh quotient of an eigenvector is its associated eigenvalue. Equivalently, the Rayleigh–Ritz quotient can be replaced by

For Hermitian matrices, the range of the continuous function R_A(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.

Min-max Theorem

Let A be a n × n Hermitian matrix with eigenvalues λ₁ ≤ … ≤ λ_k ≤ … ≤ λ_n then

and

in particular,

and these bounds are attained when x is an eigenvector of the appropriate eigenvalues.

Also note that the simpler formulation for the maximal eigenvalue λ_n is given by:

Similarly, the minimal eigenvalue λ₁ is given by:

Proof

Since the matrix A is Hermitian it is diagonalizable and we can choose an orthonormal basis of eigenvectors {u₁, …, u_n} that is, u_i is an eigenvector for the eigenvalue λ_i and such that (u_i, u_i) = 1 and (u_i, u_j) = 0 for all i ≠ j.

If U is a subspace of dimension k then its intersection with the subspace span{u_k, …, u_n} isn’t zero (by simply checking dimensions) and hence there exists a vector v ≠ 0 in this intersection that we can write as

and whose Rayleigh quotient is

(as all for i=k,..,n) and hence

Since this is true for all U, we can conclude that

This is one inequality. To establish the other inequality, chose the specific k-dimensional space V = span{u₁, …, u_k} , for which

because is the largest eigenvalue in V. Therefore, also

In the case where U is a subspace of dimension n-k+1, we proceed in a similar fashion: Consider the subspace of dimension k, span{u₁, …, u_k}. Its intersection with the subspace U isn’t zero (by simply checking dimensions) and hence there exists a vector v in this intersection that we can write as

and whose Rayleigh quotient is

and hence

Since this is true for all U, we can conclude that

Again, this is one part of the equation. To get the other inequality, note again that the eigenvector u of is contained in U = span{u_k, …, u_n} so that we can conclude the equality.

Counterexample in the non-Hermitian case

Let N be the nilpotent matrix

Define the Rayleigh quotient exactly as above in the Hermitian case. Then it is easy to see that the only eigenvalue of N is zero, while the maximum value of the Rayleigh ratio is <templatestyles src=»Sfrac/styles.css» />1/2. That is, the maximum value of the Rayleigh quotient is larger than the maximum eigenvalue.

Applications

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^{[citation needed]} of the first equality from min-max theorem is

Similarly,

Cauchy interlacing theorem

Let A be a symmetric n × n matrix. The m × m matrix B, where m ≤ n, is called a compression of A if there exists an orthogonal projection P onto a subspace of dimension m such that P*AP = B. The Cauchy interlacing theorem states:

Theorem. If the eigenvalues of A are α₁ ≤ … ≤ α_n, and those of B are β₁ ≤ … ≤ β_j ≤ … ≤ β_m, then for all j < m + 1,

This can be proven using the min-max principle. Let β_i have corresponding eigenvector b_i and S_j be the j dimensional subspace S_j = span{b₁, …, b_j}, then

According to first part of min-max, α_j ≤ β_j. On the other hand, if we define S_m−j+1 = span{b_j, …, b_m}, then

where the last inequality is given by the second part of min-max.

Notice that, when n − m = 1, we have α_j ≤ β_j ≤ α_j+1, hence the name interlacing theorem.

Compact operators

Let A be a compact, 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. Letting S_k ⊂ H be a k dimensional subspace, we can obtain the following theorem.

Theorem (Min-Max). Let A be a compact, self-adjoint operator on a Hilbert space H, whose positive eigenvalues are listed in decreasing order … ≤ λ_k ≤ … ≤ λ₁. Then:

A similar pair of equalities hold for negative eigenvalues.

Proof:

Self-adjoint operators

The min-max theorem also applies to (possibly unbounded) self-adjoint operators.^{[1] [2]} Recall the essential spectrum is the spectrum without isolated eigenvalues of finite multiplicity. Sometimes we have some eigenvalues below the bottom of the essential spectrum, and we would like to approximate the eigenvalues and eigenfunctions.

Theorem (Min-Max). Let A be self-adjoint, and let be the eigenvalues of A below the essential spectrum. Then

.

If we only have N eigenvalues and hence run out of eigenvalues, then we let (the bottom of the essential spectrum) for n>N, and the above statement holds after replacing min-max with inf-sup.

Theorem (Max-Min). Let A be self-adjoint, and let be the eigenvalues of A below the essential spectrum. Then

.

If we only have N eigenvalues and hence run out of eigenvalues, then we let (the bottom of the essential spectrum) for n>N, and the above statement holds after replacing max-min with sup-inf.

The proofs^[1][2] use the following results about self-adjoint operators:

Theorem. Let A be self-adjoint. Then for if and only if .

Theorem. If A is self-adjoint, then

and

.

See also

• Courant minimax principle
• Max–min inequality

References

• M. Reed and B. Simon, Methods of Modern Mathematical Physics IV: Analysis of Operators, Academic Press, 1978.