[行列解析4.3.49]

4.3.49

定理 4.3.49. \(n \ge 2\) とし、ベクトル \(x=[x_i]\in\mathbb{R}^n\) および \(y=[y_i]\in\mathbb{R}^n\) を与える。次の3条件は同値である：

(a) \(x\) は \(y\) をメジャライズする（\(x\) majorizes \(y\)）。

(b) ある二重確率行列（doubly stochastic）\(S=[s_{ij}]\in M_n\) が存在して \(y = Sx\) となる。

(c) \(y\) は次の凸結合に属する：\(\sum_{i=1}^{n!}\alpha_i P_i x\) （\(\alpha_i \ge 0\), \(\sum_{i=1}^{n!}\alpha_i=1\)、各 \(P_i\) は置換行列）。

証明（概略）. まず (a) ⇒ (b) を示す。\(x\) が \(y\) をメジャライズするなら、前定理（定理 4.3.48）より実直交行列 \(Q=[q_{ij}]\in M_n\) が存在して

y = \mathrm{diag}\!\bigl(Q\,\mathrm{diag}(x)\,Q^T\bigr)

となる。成分ごとに計算すると各 \(i\) について

y_i = \sum_{j=1}^n q_{ij}^2 \, x_j,

すなわち \(y = Sx\) であり、\(S=[q_{ij}^2]\) は非負成分をもち、各行・各列の和が 1 であるから二重確率行列である。したがって (a) ⇒ (b)。

次に (b) ⇔ (c) は Birkhoff の定理（定理 8.7.2）により明らかである：二重確率行列は置換行列の凸結合で表せる。したがって (b) ⇔ (c)。

残るは (b) ⇒ (a)。\(y = Sx\) かつ \(S\) が二重確率行列とする。任意の置換行列 \(P_1,P_2\) を用いて \(x = P_1 x^\downarrow\) および \(y = P_2 y^\downarrow\) と表せるので、\(y^\downarrow = (P_2^T S P_1) x^\downarrow\) である。置換で順序を整えることはメジャライズを保存するので、一般性を失わずに \(x_1 \ge \cdots \ge x_n\)、\(y_1 \ge \cdots \ge y_n\)、\(y = Sx\)、かつ \(S\) は二重確率行列であると仮定できる。

\(k\) を \(1\le k\le n\) に固定し、\(w^{(k)}_j = \sum_{i=1}^k s_{ij}\) と置く。すると \(0 \le w^{(k)}_j \le 1\)、\(w^{(n)}_j = 1\)、および \(\sum_{j=1}^n w^{(k)}_j = k\) が成り立つ。\(y_i = \sum_{j=1}^n s_{ij} x_j\) であるから

\sum_{i=1}^k y_i = \sum_{i=1}^k \sum_{j=1}^n s_{ij} x_j = \sum_{j=1}^n w^{(k)}_j x_j.

一方で次の差を考えると（\(x_1\ge\cdots\ge x_n\) を用いる）

\sum_{i=1}^k x_i - \sum_{i=1}^k y_i = \sum_{i=1}^k (x_i - x_k) (1-w^{(k)}_i) + \sum_{i=k+1}^n w^{(k)}_i (x_k - x_i) \ge 0.

したがって任意の \(k=1,\dots,n\) について \(\sum_{i=1}^k x_i \ge \sum_{i=1}^k y_i\) が成り立ち、\(k=n\) では等号となる。これがメジャライズの定義（トップダウン不等式）であり、よって (b) ⇒ (a)。これで (a),(b),(c) の同値性が示された。◻︎

結論として、与えられたベクトル \(x\) によってメジャライズされるすべてのベクトルは、\(x\) の成分を置換して得られる（高々 \(n!\) 個の）ベクトルの凸包として記述される。

次に示す結果は、行列の固有値とそのエルミート部分（Hermitian part）との関係を与えるものである：エルミート部分の固有値は元の行列の固有値のメジャライズ関係に従う、という趣旨である。