Courant–Fischerのミニマックス定理(Courant–Fischer min-max theorem)とは、$n$ 次の Hermite 行列 $A$(実対称行列を含む)の大きい順に $k$ 番目の固有値 $\lambda_k$ が、Rayleigh 商 $x^*Ax/x^*x$ の $k$ 次元部分空間の上での最小値の最大値に等しく、$n-k+1$ 次元部分空間の上での最大値の最小値にも等しい、という定理である。固有ベクトルを使わずに固有値を 2 次形式で表すので、$B-A$ が半正定値なら番号ごとに $\lambda_k(A)\le\lambda_k(B)$ となることや、固有値の交錯、特異値の同じ形の表示が導かれる。Hermite でない行列や、コンパクトでない無限次元の自己共役作用素では、一般には成り立たない。
Courant–Fischerのミニマックス定理(Courant–Fischer min-max theorem)とは、Hermite 行列(実対称行列を含む)の固有値を、大きい順の番号ごとに、Rayleigh 商の「最小値の最大値」または「最大値の最小値」として表す定理である。$n$ 次の Hermite 行列 $A$ の固有値を重複度を込めて $\lambda_1\ge\dots\ge\lambda_n$ と並べると、$k=1,\dots,n$ について
$$
\lambda_k=\max_{\dim W=k}\ \min_{x\in W\setminus\{0\}}\frac{x^*Ax}{x^*x}=\min_{\dim W=n-k+1}\ \max_{x\in W\setminus\{0\}}\frac{x^*Ax}{x^*x}
$$
が成り立つ。ここで $W$ は $\mathbb{C}^n$ の部分空間を動き、$x^*$ は $x$ の共役転置である。
右辺には固有ベクトルが現れない。固有値を「2 次形式 $x^*Ax$ の大小」だけで書き表しているので、2 つの行列の固有値を比べる問題が、2 次形式を比べる問題に帰着する。たとえば $n$ 次の Hermite 行列 $A,B$ について $x^*Ax\le x^*Bx$ がすべての $x$ で成り立てば、番号ごとに $\lambda_k(A)\le\lambda_k(B)$ となる。行列を少し変えたときの固有値の動き(Weylの不等式(固有値))や、行と列を取り除いたときの固有値の並び方(固有値の交錯定理)も、この定理から導かれる。$k=1$ の場合は、最大の固有値が Rayleigh 商の最大値であるというよく知られた事実である。
この記事では、固有ベクトルの正規直交基底での展開と、部分空間の次元の数え上げだけで定理を証明する。続いて、直交条件で書いた形、固有値の単調性、特異値の同じ形の表示を導く。最後に、Hermite でない行列や、無限次元の作用素で結論が崩れる例を挙げる。
$\mathbb{C}^n$ には標準内積 $\langle x,y\rangle:=y^*x=\sum_{i=1}^nx_i\overline{y_i}$ を入れ、$\|x\|:=\sqrt{x^*x}$ と書く。$x,y$ が 直交する($x\perp y$)とは $\langle x,y\rangle=0$ のことである。ベクトル $v_1,\dots,v_m$ の張る部分空間を $\langle v_1,\dots,v_m\rangle$ と書く。
$n$ 次の複素正方行列 $A$ が Hermite 行列($A^*=A$)であるとき、Hermite行列 の定理「ユニタリ対角化できる行列」により、$A$ の固有値はすべて実数であり、$\mathbb{C}^n$ には $A$ の固有ベクトルからなる正規直交基底がある(固有ベクトルからなる正規直交基底の存在は、Axl24 7.31 の complex spectral theorem が正規作用素について述べており、Hermite 行列はその特別な場合である)。
$A$ を $n$ 次の Hermite 行列とする。
$x^*Ax$ は実数である(Hermite行列 の命題「Hermite 行列の特徴づけ」)。よって $R_A(x)$ は実数であり、$0$ でない複素数 $c$ について $R_A(cx)=R_A(x)$ が成り立つ。$x$ が固有値 $\lambda$ の固有ベクトルなら $R_A(x)=\lambda$ である。Rayleigh 商そのものの性質は Rayleigh商 の記事にまとめてある。
以下、$A$ を固定し、$\lambda_j:=\lambda_j(A)$ と書く。$A$ の固有ベクトルからなる正規直交基底 $u_1,\dots,u_n$ を、$Au_j=\lambda_ju_j$ となるように番号を付けて 1 組とる。
$0$ でない部分空間 $W$ の上で $R_A$ の最大値と最小値は存在する。$R_A(x)=R_A(x/\|x\|)$ なので $W$ の単位ベクトル全体の上で考えればよく、そこは有界閉集合なのでコンパクトであり、$R_A$ はその上で連続だからである。以下の証明では、最大値・最小値を与えるベクトルも具体的に示す。
$1\le k\le n$ とする。
$x=\sum_{j=1}^nc_ju_j$($c_j=u_j^*x$)と展開する。$Ax=\sum_j\lambda_jc_ju_j$ であり、$u_i^*u_j$ は $i=j$ のとき $1$、それ以外は $0$ なので
$$
x^*x=\sum_{j=1}^n|c_j|^2,\qquad x^*Ax=\sum_{j=1}^n\lambda_j|c_j|^2
$$
である。
1:$x$ が $u_1,\dots,u_{k-1}$ に直交するので $c_1=\dots=c_{k-1}=0$ である。$j\ge k$ では $\lambda_j\le\lambda_k$ なので
$$
\lambda_k\,x^*x-x^*Ax=\sum_{j\ge k}(\lambda_k-\lambda_j)|c_j|^2\ \ge\ 0
$$
であり、$x^*x>0$ で割って $R_A(x)\le\lambda_k$ を得る。
2:$c_{k+1}=\dots=c_n=0$ である。$j\le k$ では $\lambda_j\ge\lambda_k$ なので $x^*Ax-\lambda_k\,x^*x=\sum_{j\le k}(\lambda_j-\lambda_k)|c_j|^2\ge0$ であり、$R_A(x)\ge\lambda_k$ を得る。
最後の主張は、1 を $k=1$ で、2 を $k=n$ で使ったものである。$\square$
$\mathbb{C}^n$ の部分空間 $W,U$ が $\dim W+\dim U>n$ を満たすなら、$W\cap U$ は $0$ でないベクトルを含む。
部分空間 の命題「次元公式(参照)」により $\dim(W\cap U)=\dim W+\dim U-\dim(W+U)$ である。$W+U\subset\mathbb{C}^n$ なので $\dim(W+U)\le n$ であり、$\dim(W\cap U)\ge\dim W+\dim U-n\ge1$ となる。$\square$
$A$ を $n$ 次の Hermite 行列とし、$1\le k\le n$ とする。$W$ が $\mathbb{C}^n$ の部分空間を動くとき
$$
\lambda_k(A)=\max_{\dim W=k}\ \min_{x\in W\setminus\{0\}}R_A(x)\qquad\text{(1)}
$$
$$
\lambda_k(A)=\min_{\dim W=n-k+1}\ \max_{x\in W\setminus\{0\}}R_A(x)\qquad\text{(2)}
$$
が成り立つ。$A$ の固有ベクトルからなる正規直交基底 $u_1,\dots,u_n$ を $Au_j=\lambda_j(A)u_j$ となるようにとると、(1) の外側の最大は $W=\langle u_1,\dots,u_k\rangle$ で、(2) の外側の最小は $W=\langle u_k,\dots,u_n\rangle$ で達成される。
$W_0:=\langle u_1,\dots,u_k\rangle$($k$ 次元)、$U_0:=\langle u_k,\dots,u_n\rangle$($n-k+1$ 次元)とおく。$u_1,\dots,u_n$ は正規直交基底なので、$U_0$ はちょうど $u_1,\dots,u_{k-1}$ のすべてに直交するベクトルの全体である。
(1) の証明.段 1:$W_0$ の上では lem-cf-bounds の 2 により $R_A\ge\lambda_k$ であり、$u_k\in W_0$ で $R_A(u_k)=\lambda_k$ となる。よって $W_0$ の上での $R_A$ の最小値は $\lambda_k$ である。
段 2:$W$ を任意の $k$ 次元部分空間とする。$\dim W+\dim U_0=k+(n-k+1)=n+1>n$ なので、lem-cf-intersection により $0$ でない $x\in W\cap U_0$ がある。$x$ は $u_1,\dots,u_{k-1}$ に直交するので、lem-cf-bounds の 1 により $R_A(x)\le\lambda_k$ である。よって $W$ の上での $R_A$ の最小値は $\lambda_k$ 以下である。
段 1・段 2 から、$k$ 次元部分空間 $W$ についての「$W$ の上での最小値」はどれも $\lambda_k$ 以下で、$W=W_0$ のとき $\lambda_k$ に等しい。したがってその最大値が存在して $\lambda_k$ に等しい。
(2) の証明.段 1:$U_0$ の上では lem-cf-bounds の 1 により $R_A\le\lambda_k$ であり、$u_k\in U_0$ で等号が成り立つ。よって $U_0$ の上での最大値は $\lambda_k$ である。
段 2:$W$ を任意の $n-k+1$ 次元部分空間とする。$\dim W+\dim W_0=n+1>n$ なので $0$ でない $x\in W\cap W_0$ があり、lem-cf-bounds の 2 により $R_A(x)\ge\lambda_k$ である。よって $W$ の上での最大値は $\lambda_k$ 以上である。
以上から、$n-k+1$ 次元部分空間の上での最大値の最小値が存在して $\lambda_k$ に等しく、$W=U_0$ で達成される。$\square$
外側の最大・最小は無限個の部分空間にわたるが、証明はそれが具体的な $W_0$・$U_0$ で達成されることも示している。$k=1$ では (1) の $W$ は直線、(2) の $W$ は $\mathbb{C}^n$ 全体なので、(2) から $\lambda_1=\max_{x\ne0}R_A(x)$ を得る。同様に $k=n$ の (1) から $\lambda_n=\min_{x\ne0}R_A(x)$ を得る。
$A$ が実対称行列のときは、固有ベクトルの正規直交基底を $\mathbb{R}^n$ の中にとれる(対称行列 の定理「直交対角化できる実行列」)。このとき、$W$ を $\mathbb{R}^n$ の部分空間、$x$ を実ベクトルに限っても、上の証明は $\mathbb{C}$ を $\mathbb{R}$ に、$|c_j|^2$ を $c_j^2$ に替えるだけでそのまま通る。実対称行列の場合の主張は BH11 Theorem 2.4.1(p. 26)に、「$i$ 次元の $W$ について $\lambda_i\ge\min_WR_A$」と「$W^{\perp}$ の上で $\lambda_{i+1}\le\max R_A$」の形で述べられている。
$A$ を $n$ 次の Hermite 行列とし、$1\le k\le n$ とする。
$$
\lambda_k(A)=\min_{w_1,\dots,w_{k-1}\in\mathbb{C}^n}\ \max\{R_A(x)\mid x\ne0,\ x\perp w_1,\dots,w_{k-1}\}\qquad\text{(3)}
$$
$$
\lambda_k(A)=\max_{w_1,\dots,w_{n-k}\in\mathbb{C}^n}\ \min\{R_A(x)\mid x\ne0,\ x\perp w_1,\dots,w_{n-k}\}\qquad\text{(4)}
$$
が成り立つ。$w_i$ は $\mathbb{C}^n$ の任意のベクトルを動き、$0$ や重複も許す($k=1$ の (3)、$k=n$ の (4) では条件はない)。$u_j$ を thm-cf-main の正規直交基底とすると、(3) は $w_i=u_i$ で、(4) は $w_i=u_{k+i}$ で達成される。
(3):$w_1,\dots,w_{k-1}$ を任意にとり、$Z:=\{x\mid x\perp w_1,\dots,w_{k-1}\}$ とおく。$Z$ は $\langle w_1,\dots,w_{k-1}\rangle$ の直交補空間であり、同記事の定理「有限次元の部分空間の直交分解」の 3 により $\dim Z=n-\dim\langle w_1,\dots,w_{k-1}\rangle\ge n-k+1$ である。$Z$ の中に $n-k+1$ 次元の部分空間 $W$ をとると、$W\subset Z$ なので $Z$ の上での最大値は $W$ の上での最大値以上であり、(2) によりそれは $\lambda_k$ 以上である。一方 $w_i=u_i$($i=1,\dots,k-1$)とすると、prf-cf-main の記号で $Z=U_0$ であり、(2) の証明の段 1 により $Z$ の上での最大値は $\lambda_k$ に等しい。
(4):同様に $Z:=\{x\mid x\perp w_1,\dots,w_{n-k}\}$ は $\dim Z\ge k$ を満たす。$Z$ の中に $k$ 次元の部分空間 $W$ をとると、$Z$ の上での最小値は $W$ の上での最小値以下であり、(1) によりそれは $\lambda_k$ 以下である。$w_i=u_{k+i}$($i=1,\dots,n-k$)とすると $Z=W_0$ であり、(1) の証明の段 1 により最小値は $\lambda_k$ に等しい。$\square$
$A=\operatorname{diag}(3,1,-2)$ とすると、$\lambda_1=3$、$\lambda_2=1$、$\lambda_3=-2$ で、$u_j$ は標準基底 $e_j$ にとれる。
$$
R_A(x)=\frac{3|x_1|^2+|x_2|^2-2|x_3|^2}{|x_1|^2+|x_2|^2+|x_3|^2}
$$
である。$k=2$ の (1) を確かめる。
次の例では、外側の最大・最小を与える部分空間が固有ベクトルで張られていなくてもよいこと、そして 1 つの部分空間で固有値を上下から挟めることを見る。
$$
A=\begin{pmatrix}2&1&0\\1&2&1\\0&1&2\end{pmatrix}
$$
とする。$W=\langle e_1,e_3\rangle$ の $x=(a,0,c)$ について、$x^*Ax=2|a|^2+2|c|^2$ である($x$ の第 2 成分が $0$ で、$A$ の $(1,3)$ 成分も $0$ なので、対角成分だけが残る)。よって $W$ の上で $R_A\equiv2$ である。
$n=3$、$k=2$ では $k=n-k+1=2$ なので、同じ $W$ を (1) と (2) の両方に使える。(1) から $\lambda_2\ge\min_WR_A=2$、(2) から $\lambda_2\le\max_WR_A=2$ であり、$\lambda_2=2$ がわかる。実際、固有多項式は $(2-t)\bigl((2-t)^2-2\bigr)$ で、固有値は $2+\sqrt2,\ 2,\ 2-\sqrt2$ である。
$W$ は固有ベクトルだけでは張られていない。固有値 $2$ の固有ベクトル $(1,0,-1)$ は $W$ に属するが、$W$ の元 $(1,0,1)$ は $A(1,0,1)^{\top}=(2,2,2)^{\top}$ なので固有ベクトルではない。
$A,B$ を $n$ 次の Hermite 行列とし、$B-A$ が半正定値、すなわちすべての $x$ について $x^*(B-A)x\ge0$ であるとする。このとき、すべての $k=1,\dots,n$ について $\lambda_k(A)\le\lambda_k(B)$ である。
$x\ne0$ について $R_B(x)-R_A(x)=x^*(B-A)x/x^*x\ge0$ である。よって任意の部分空間 $W\ne0$ について $\min_{W\setminus\{0\}}R_B\ge\min_{W\setminus\{0\}}R_A$ であり、$k$ 次元の $W$ について最大をとると、(1) により $\lambda_k(B)\ge\lambda_k(A)$ を得る。$\square$
固有値の個々の値は行列の成分の複雑な関数だが、この系は「2 次形式が大きくなれば、すべての番号の固有値が大きくなる」ことを、固有ベクトルの動きを追わずに示している。$B=A+E$ と書けば、より一般に $\lambda_k(A)+\lambda_n(E)\le\lambda_k(A+E)\le\lambda_k(A)+\lambda_1(E)$ が同じ論法で示せる(Hermite行列 の定理「固有値の摂動の評価」)。番号をずらした精密な形が Weylの不等式(固有値) である。
$S$ を列が正規直交な $n\times m$ 行列($S^*S=I_m$、$m< n$)とし、$B:=S^*AS$ とおく。$y\in\mathbb{C}^m$ について $R_B(y)=R_A(Sy)$ であり、$S$ は $\mathbb{C}^m$ の $k$ 次元部分空間を $\mathbb{C}^n$ の $k$ 次元部分空間に移す。これを (1)・(2) に当てると $\lambda_k(A)\ge\lambda_k(B)\ge\lambda_{n-m+k}(A)$ が得られる。$B$ が $A$ の主小行列(同じ番号の行と列だけを残した行列)の場合が Cauchy の交錯定理であり、証明と応用は 固有値の交錯定理 にある。
$M$ を $m\times n$ の複素行列とする。$M^*M$ は $n$ 次の Hermite 行列で、$x^*M^*Mx=\|Mx\|^2\ge0$ なので固有値はすべて $0$ 以上である。$1\le k\le n$ について $\sigma_k(M):=\sqrt{\lambda_k(M^*M)}$ とおく。
$M$ を $m\times n$ の複素行列とし、$1\le k\le n$ とする。$W$ が $\mathbb{C}^n$ の部分空間を動くとき
$$
\sigma_k(M)=\max_{\dim W=k}\ \min_{x\in W\setminus\{0\}}\frac{\|Mx\|}{\|x\|}=\min_{\dim W=n-k+1}\ \max_{x\in W\setminus\{0\}}\frac{\|Mx\|}{\|x\|}
$$
である。とくに $\sigma_1(M)=\max_{x\ne0}\|Mx\|/\|x\|$ である。
$x\ne0$ について $R_{M^*M}(x)=\|Mx\|^2/\|x\|^2$ である。thm-cf-main を $M^*M$ に使うと、$\lambda_k(M^*M)$ は $\|Mx\|^2/\|x\|^2$ の最小値の最大値、および最大値の最小値に等しい。$t\mapsto\sqrt t$ は $[0,\infty)$ で狭義単調増加なので、最大・最小をとる操作と入れ替えられ、両辺の平方根をとって主張を得る。最後の主張は $k=1$ の第 2 の等式で $W=\mathbb{C}^n$ としたものである。$\square$
$k\le\min\{m,n\}$ のとき、$\sigma_k(M)$ は 特異値分解 の定義「特異値と特異値分解」の特異値と同じものである。$k>m$ では $M^*M$ の階数が $m$ 以下なので $\sigma_k(M)=0$ である。特異値を $M^*M$ の固有値の平方根として定めることは Axl24 7.65(p. 271)にある。最後の主張は、$\sigma_1(M)$ が $M$ の作用素ノルム($\|Mx\|/\|x\|$ の最大値)に等しいことを述べている。
たとえば $M=\begin{pmatrix}1&2\\0&1\\1&0\end{pmatrix}$ では $M^*M=\begin{pmatrix}2&2\\2&5\end{pmatrix}$ の固有値は $6,1$ で、$\sigma_1=\sqrt6$、$\sigma_2=1$ である。$k=2$ の第 1 の等式は $W=\mathbb{C}^2$ だけを考えればよく、$\|Mx\|/\|x\|$ の最小値が $1$ であることを述べる。実際 $x=(2,-1)$ では $Mx=(0,-1,2)$ で、$\|Mx\|^2=\|x\|^2=5$ である。
| 外す条件・替える条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $A$ が Hermite であること | $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$ | 固有値は $0,0$ だが、実ベクトルに限っても $\max R_A=\tfrac12$ で、$k=1$ の (2) が崩れる |
| (1) の外側を max、内側を min にとること(次元 $k$ のまま入れ替える) | $A=\operatorname{diag}(3,1,-2)$、$k=1$ | $\min_{\dim W=1}\max_{W}R_A=-2$ で、$\lambda_1=3$ に一致しない |
| Rayleigh 商の分母を $x^*x$(標準内積)にとること | $A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$、分母を $x_1^2+4x_2^2$ に替える(実ベクトル) | 商の最大値は $\tfrac12$ で、$\lambda_1=1$ に一致しない |
| 有限次元であること | $L^2(0,1)$ 上の自己共役作用素 $(Tf)(t)=tf(t)$ | 固有値がなく、Rayleigh 商の上限 $1$ は達成されない |
各行で破れている条件と、崩れる結論を確かめる。
1 行目:$A$ は実行列だが $A^{\top}\ne A$ で、Hermite でない。固有多項式は $t^2$ なので固有値は $0,0$ である。複素ベクトルでは $x^*Ax=\overline{x_1}x_2$ が実数とは限らず、Rayleigh 商の大小が意味をもたない。実ベクトルに限ると $R_A(x)=x_1x_2/(x_1^2+x_2^2)$ で、$2|x_1x_2|\le x_1^2+x_2^2$ から $|R_A|\le\tfrac12$、$x=(1,1)$ で $\tfrac12$ となる。最大値 $\tfrac12$ は $\lambda_1=0$ と一致しない。$x^{\top}Ax$ は対称部分 $\tfrac12(A+A^{\top})$ の 2 次形式と同じであり、Rayleigh 商が読み取るのはその固有値 $\pm\tfrac12$ である。
2 行目:$A$ は Hermite で、変えたのは max と min の順だけである。1 次元の $W=\langle x\rangle$ の上で $R_A$ は定数 $R_A(x)$ なので、$\min_{\dim W=1}\max_WR_A=\min_{x\ne0}R_A(x)=\lambda_3=-2$ となる(lem-cf-bounds の最後の主張と $x=e_3$)。(2) で $k=1$ のときの正しい次元は $n-k+1=3$ である。
3 行目:$A$ は実対称で、変えたのは分母の内積だけである。相加平均と相乗平均の不等式から $x_1^2+4x_2^2\ge4|x_1x_2|$ なので $|2x_1x_2|/(x_1^2+4x_2^2)\le\tfrac12$ で、$x=(2,1)$ で $\tfrac12$ となる。この商の最大値・最小値 $\pm\tfrac12$ は $A$ の固有値 $\pm1$ ではなく、$G=\operatorname{diag}(1,4)$ として $G^{-1}A$ の固有値である。分母を別の内積に替えると、その内積で $A$ に対応する写像($G^{-1}A$)の固有値を表す式になる。
4 行目:$T$ は有界な自己共役作用素で、有限次元という条件だけが外れている。$f\ne0$ について Rayleigh 商は $1$ より小さく、区間 $(1-\varepsilon,1)$ の定義関数で $1-\varepsilon$ 以上になるので、上限は $1$ で達成されない。$Tf=\lambda f$ なら $(t-\lambda)f(t)=0$ がほとんどいたるところ成り立ち $f=0$ なので、$T$ は固有値をもたない。詳しくは Rayleigh商 の例「上限が達成されない例」にある。
定理は E. Fischer と R. Courant の名で呼ばれ、min-max 原理とも呼ばれる。H. Weyl の名を加えて Courant–Fischer–Weyl の min-max 原理と呼ぶこともある。固有値を小さい順に番号付ける流儀では、(1)・(2) の max と min の役割が入れ替わる。この記事の (1) は「$k$ 次元の部分空間の上の最小値」を最大化し、(2) は「$n-k+1$ 次元の部分空間の上の最大値」を最小化する。どちらの次元を使うかは、補題の 2 つの部分空間 $\langle u_1,\dots,u_k\rangle$ と $\langle u_k,\dots,u_n\rangle$ の次元で覚えられる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する