二重確率行列(doubly stochastic matrix)とは、成分がすべて $0$ 以上で、各行の和と各列の和がすべて $1$ である正方行列のことである。$n$ 次の全体は置換行列を頂点とする $(n-1)^2$ 次元の凸多面体をなすので、その上の線形関数の最適化は置換の問題に帰着する。成分が正の行列は対角行列を両側から掛けてただ 1 通りの二重確率行列に直せる(Sinkhorn の定理)。優越、割当問題、固有値の摂動の Hoffman–Wielandt の不等式、パーマネントの下界などに現れる。
成分がすべて $0$ 以上で、各行の和と各列の和がすべて $1$ である正方行列を 二重確率行列(doubly stochastic matrix)という。確率の言葉では、推移行列のうち一様分布を保つものである。組合せの言葉では、置換行列 を確率的に混ぜたもの(置換の「ぼかし」)である。
$n$ 次の二重確率行列の全体 $\Omega_n$ は、置換行列を頂点とする凸多面体になる(Birkhoff–von Neumann の定理)。この事実があるので、$\Omega_n$ の上の線形関数の最適化は置換の問題に帰着する。割当問題、固有値の摂動、優越(どちらの列がより「ならされている」か)など、一見別の問題がここで結びつく。
この記事では、定理そのものの証明は別の記事に任せ(rem-ds-birkhoff)、$\Omega_n$ の形(次元・面・頂点の隣接)、成分が正の行列を対角行列で二重確率行列に直す Sinkhorn の定理、ユニタリ行列から来る二重確率行列、その応用としての Hoffman–Wielandt の不等式を証明する。
| 主張 | 内容 | この記事で |
|---|---|---|
| prop-ds-basic | 積・転置・置換で閉じる、パーマネントの上界 | 証明する |
| prop-ds-block | $0$ のブロックがあれば直和に分かれる | 証明する |
| thm-ds-polytope | 次元 $(n-1)^2$、面の個数、頂点の隣接 | 証明する |
| thm-ds-sinkhorn | 正の行列の対角による正規化 | 証明する |
| prop-ds-unitary | ユニタリ行列から来る行列と、そうでない例 | 証明する |
| thm-ds-hw | Hoffman–Wielandt の不等式 | 証明する |
実数を成分とする $n$ 次正方行列 $A=(a_{ij})$ で、次を満たすものを 二重確率行列 という。
置換 $\sigma$ に対し、$(i,\sigma(i))$ 成分が $1$ で他が $0$ の行列を $Q_\sigma$ と書く。全成分が $1/n$ の行列を $J_n$ と書く。
1:$AB\mathbf{1}=A\mathbf{1}=\mathbf{1}$、$(AB)^{\top}\mathbf{1}=B^{\top}A^{\top}\mathbf{1}=\mathbf{1}$ である。残りも同様である。
2:$A\mathbf{1}=\mathbf{1}$ なので $1$ は固有値である。$Av=\lambda v$($v\ne0$)とし、$\lvert v_i\rvert$ が最大の $i$ をとると、$\lvert\lambda\rvert\lvert v_i\rvert\le\sum_ja_{ij}\lvert v_j\rvert\le\lvert v_i\rvert$ である。
3:$1=\prod_i(\sum_ja_{ij})$ を展開すると、写像 $\tau\colon\{1,\dots,n\}\to\{1,\dots,n\}$ にわたる $\prod_ia_{i\tau(i)}$ の和で、置換の項の和が $\operatorname{per}A$ である。よって $\operatorname{per}A\le1$ である。ある列 $j$ に $a_{ij},a_{kj}>0$($i\ne k$)があると、$\tau(i)=\tau(k)=j$ で、他の行は正の成分を選ぶ写像の項が正なので、不等式は真である。どの列にも正の成分が 1 つだけなら、列の和から成分は $1$ で、$A$ は置換行列である。
4:各行の和が $1$ なので各行に $1$ がちょうど 1 つあり、列についても同じである。$\square$
$A\in\Omega_n$ の第 $I$ 行・第 $K$ 列の小行列が $0$ で、$\lvert I\rvert=r$、$\lvert K\rvert=s$ とする。このとき $r+s\le n$ である。$r+s=n$ なら第 $I^{\mathrm c}$ 行・第 $K^{\mathrm c}$ 列の小行列も $0$ であり、行と列を並べ替えると $A$ は二重確率行列 2 つの直和になる。
第 $I$ 行の成分の総和は $r$ で、すべて第 $K^{\mathrm c}$ 列にある。第 $K^{\mathrm c}$ 列の成分の総和は $n-s$ なので、$r\le n-s$ である。$r=n-s$ なら第 $K^{\mathrm c}$ 列の成分はすべて第 $I$ 行にある。よって第 $I^{\mathrm c}$ 行・第 $K^{\mathrm c}$ 列は $0$ である。$\square$
$\Omega_n$ の元はどれも置換行列の凸結合である。証明は 2 通りが別の記事にある。Hallの結婚定理 の定理「Birkhoff–von Neumann の定理」は相異なる代表系を取って引いていく証明、輸送問題 の系「Birkhoff–von Neumann の定理」は多面体の頂点を調べる証明で、頂点がちょうど $n!$ 個の置換行列であることと、線形関数 $\sum_{i,j}c_{ij}x_{ij}$ の $\Omega_n$ 上の最小値が $\min_\sigma\sum_ic_{i\sigma(i)}$ に等しいことも述べている。定理は Birkhoff の Bir46 により、名前の後半は von Neumann の Neu53 にちなむ。
帰結として、$A\in\Omega_n$ の正の成分はどれも、ある置換 $\sigma$ の項がすべて正である対角 $(a_{i\sigma(i)})_i$ の上にある(凸結合に現れる $Q_\sigma$ をとる)。とくに $\operatorname{per}A>0$ である。
$\Omega_n$ を Birkhoff多面体 ともいう。以下、$\mathbb{R}^{n\times n}$ の中の多面体として形を調べる。$\Omega_n$ は不等式 $x_{ij}\ge0$ と等式で定まるので、面はどれも、ある位置の集合 $Z$ の上で $x_{ij}=0$ とした $\Omega_n$ の部分集合である(空でなければ。多面体)。
1:行和・列和の条件を満たす行列は、左上の $(n-1)\times(n-1)$ ブロックを自由に決めると最後の行と列が決まる(右下の成分は行からも列からも同じ値に決まる)。よって条件の定めるアフィン部分空間の次元は $(n-1)^2$ である。$J_n$ は全成分が正なので、その近傍は $\Omega_n$ に入る。
2:$(i,j)$ を固定する。$\sigma(i)\ne j$ であるすべての置換についての $Q_\sigma$ の平均を $X$ とする。$X$ は $\Omega_n$ の元で $x_{ij}=0$ である。ほかの位置 $(k,l)$ では $X$ の成分は正である。実際、$\sigma(k)=l$、$\sigma(i)\ne j$ の置換がある:$k=i$ なら $l\ne j$ で明らかである。$l=j$ なら $k\ne i$ で、$\sigma(k)=j$ から $\sigma(i)\ne j$ である。$k\ne i$、$l\ne j$ なら、$n\ge3$ なので $\sigma(i)\notin\{j,l\}$ と選べる。よって $X$ は等式 $x_{ij}=0$ を加えたアフィン部分空間の中の内点で、この部分空間の次元は $(n-1)^2-1$ である(1 の座標では、$x_{ij}=0$ は定数でない 1 次式の条件である)。よって各 $x_{ij}=0$ は余次元 1 の面で、$X$ が他の $x_{kl}$ で正なので互いに異なる。逆に余次元 1 の面は 1 つの不等式で定まる。
3:$S:=\{(i,\sigma(i))\}\cup\{(i,\tau(i))\}$ とする。$Q_\sigma,Q_\tau$ を含む面の $Z$ は $S$ と交わらないので、最小の面は $F:=\{X\in\Omega_n\mid\text{$S$ の外で }x_{ij}=0\}$ である。行を一方、列を他方の頂点とし、$S$ を辺とする二部グラフを考える。$\sigma(i)=\tau(i)$ の行では成分は $1$ に決まる。それ以外の成分は、次数 $2$ の頂点からなる偶閉路に分かれる。閉路は $\sigma^{-1}\tau$ の長さ 2 以上の巡回と 1 対 1 に対応する。閉路の上で辺の重みを順に $t,1-t,t,\dots$ と置くのが行和・列和の条件のすべてで、$t\in[0,1]$ は閉路ごとに独立に選べる($\sigma$ の辺を $t$ とする)。よって $F\cong[0,1]^c$ で、$Q_\sigma,Q_\tau$ は対角の位置の 2 頂点である。$c=1$ のとき $F$ は線分である。$\square$
$\Omega_2$ は線分($x_{11}=0$ と $x_{22}=0$ は同じ点を定める)で、thm-ds-polytope の 2 の $n\ge3$ は外せない。$\Omega_3$ は 4 次元、頂点 $6$ 個、余次元 1 の面 $9$ 個で、$\mathfrak{S}_3$ の単位元以外はすべて 1 個の巡回なので、どの 2 頂点も辺で結ばれる。$\Omega_4$ では $\sigma^{-1}\tau=(1\,2)(3\,4)$ のとき $Q_\sigma,Q_\tau$ は辺で結ばれず、正方形の対角をなす。次元・面・隣接は $n\le4$ で頂点の座標から計算して確かめた。
Carathéodoryの定理(凸幾何) と thm-ds-polytope の 1 から、$\Omega_n$ の元は高々 $(n-1)^2+1$ 個の置換行列の凸結合で書ける。個数は元による。$J_n$ は巡回シフト $n$ 個の平均である。
二重確率行列でない行列を、行と列の尺度を変えて二重確率行列に直せるか。
$A$ を成分がすべて正の $n$ 次行列とする。対角成分が正の対角行列 $D_1,D_2$ で $D_1AD_2\in\Omega_n$ となるものがある。$D_1AD_2$ はただ 1 つで、$(D_1,D_2)$ は $(cD_1,c^{-1}D_2)$($c>0$)の違いを除いて一意である。
$y\in\mathbb{R}^n$ について
$$
F(y):=\sum_{i=1}^n\log\Bigl(\sum_{j=1}^na_{ij}e^{y_j}\Bigr)-\sum_{j=1}^ny_j
$$
とおく。すべての $y_j$ に同じ定数を足しても $F$ は変わらない。
最小点の存在. $a_0:=\min_{i,j}a_{ij}>0$、$M:=\max_jy_j$ とすると、$\sum_ja_{ij}e^{y_j}\ge a_0e^M$ なので
$$
F(y)\ge n\log a_0+\sum_j(M-y_j)\ge n\log a_0+M-\min_jy_j
$$
である。$M=0$ に正規化すると、$F$ は $\min_jy_j\to-\infty$ で $+\infty$ に発散するので、最小点 $y^*$ がある。
最小点から行列へ. $x_j:=e^{y^*_j}$、$r_i:=(\sum_la_{il}x_l)^{-1}$ とおき、$b_{ij}:=r_ia_{ij}x_j$ とする。行の和は定義から $1$ である。$\partial F/\partial y_j=0$ は $\sum_ir_ia_{ij}x_j=1$ であり、列の和が $1$ であることを意味する。
一意性. $D_1=\operatorname{diag}(r_i)$、$D_2=\operatorname{diag}(x_j)$ で $D_1AD_2\in\Omega_n$ なら、行の和から $r_i=(\sum_la_{il}x_l)^{-1}$ で、列の和から $y=(\log x_j)$ は $F$ の臨界点である。$v\in\mathbb{R}^n$ の方向の 2 階微分は
$$
\frac{d^2}{ds^2}F(y+sv)\Big|_{s=0}=\sum_i\Bigl(\sum_jw_{ij}v_j^2-\bigl(\sum_jw_{ij}v_j\bigr)^2\Bigr)\quad\bigl(w_{ij}:=\tfrac{a_{ij}e^{y_j}}{\sum_la_{il}e^{y_l}}\bigr)
$$
である。各 $i$ の項は確率 $w_{ij}>0$ についての $v_j$ の分散なので $0$ 以上で、$0$ になるのは $v$ が定数のときに限る。よって $F$ は定数方向を除いて狭義凸で、臨界点は定数の差を除いて 1 つである。$x$ は定数倍を除いて決まり、$r$ は $x$ から決まる。$\square$
定理は Sin64 による。上の証明は、Gur08 の容量の考え方に沿った形である。実際、$\exp F(y)=\prod_i(\sum_ja_{ij}x_j)/\prod_jx_j$ なので、$\min F$ は $p_A(x):=\prod_i(\sum_ja_{ij}x_j)$ の容量 $\inf_{x>0}p_A(x)/\prod_jx_j$ の対数である。
thm-ds-sinkhorn の $A$ について、$\operatorname{cap}(p_A)$ を上の容量とすると
$$
\frac{n!}{n^n}\operatorname{cap}(p_A)\le\operatorname{per}A\le\operatorname{cap}(p_A)
$$
である。
$B=D_1AD_2$($D_1=\operatorname{diag}(r_i)$、$D_2=\operatorname{diag}(x_j)$、$x$ は最小点)とすると $\operatorname{per}B=\prod_ir_i\prod_jx_j\operatorname{per}A$ で、$\operatorname{cap}(p_A)=p_A(x)/\prod_jx_j=(\prod_ir_i\prod_jx_j)^{-1}$ である。よって $\operatorname{per}A=\operatorname{cap}(p_A)\operatorname{per}B$ である。$\operatorname{per}B\le1$ は prop-ds-basic の 3、下界は van der Waerden予想(パーマネント) による。$\square$
$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ とする。$D_1AD_2$ の交差比 $\frac{b_{11}b_{22}}{b_{12}b_{21}}$ は $A$ の交差比 $\frac{1\cdot4}{2\cdot3}=\frac23$ に等しい。$\Omega_2$ の元の交差比は $a^2/(1-a)^2$ なので、$a=\frac{\sqrt{2/3}}{1+\sqrt{2/3}}\approx0.4495$ で
$$
B\approx\begin{pmatrix}0.4495&0.5505\\0.5505&0.4495\end{pmatrix}
$$
である。行と列を交互に和 $1$ に正規化する反復も、数値ではこの $B$ に収束する。
成分が $0$ 以上の行列 $A$ については、$0$ でなく、すべての正の成分が正の対角(rem-ds-birkhoff の意味)の上にあることが、$D_1AD_2\in\Omega_n$ となる $D_1,D_2$ の存在の必要十分条件である(SK67 の定理、p. 344)。必要性は rem-ds-birkhoff の帰結から分かる。$D_1AD_2$ は $A$ と正の成分の位置が同じだからである。同じ定理によれば、$A$ が正の対角を 1 つでももてば交互の正規化は二重確率行列に収束するが、上の条件が満たされていなければ極限は $D_1AD_2$ の形にならない。たとえば $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ の交互の正規化は単位行列に収束する。
$U=(u_{ij})$ が ユニタリ行列 なら、$(\lvert u_{ij}\rvert^2)$ は $\Omega_n$ の元である(行と列がそれぞれ単位ベクトル)。このような行列を unistochastic 行列(ユニタリ確率行列)という。
1:$\begin{pmatrix}\cos^2\theta&\sin^2\theta\\\sin^2\theta&\cos^2\theta\end{pmatrix}$ が $\Omega_2$ のすべてである。
2:$n=3$ で $A=\frac12\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}$ とする。$A=(\lvert u_{ij}\rvert^2)$ なら、$U$ の第 1 行と第 2 行は第 1 列でだけ同時に $0$ でないので、内積は $u_{11}\overline{u_{21}}\ne0$ であり、直交しない。$n>3$ では単位行列との直和をとれば、第 1・2 行は同じ理由で直交しない。
3:スペクトル定理 により $H=U\operatorname{diag}(\lambda)U^*$ で、$h_i=\sum_j\lvert u_{ij}\rvert^2\lambda_j$ である。優越は Karamataの不等式 の定理「二重確率行列による優越の特徴づけ」から従う。$\square$
たとえば $H=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ の固有値は $3,1$、対角は $2,2$ で、$(2,2)$ は $(3,1)$ に優越される。
次の不等式は、ユニタリ確率行列を rem-ds-birkhoff の最小値の主張に代入する典型である。
$A,B$ を $n$ 次の 正規行列 とし、固有値をそれぞれ $\alpha_1,\dots,\alpha_n$、$\beta_1,\dots,\beta_n$ とする。ある置換 $\sigma$ について
$$
\sum_i\lvert\alpha_i-\beta_{\sigma(i)}\rvert^2\le\|A-B\|_F^2
$$
である。ここで $\|X\|_F^2:=\sum_{i,j}\lvert x_{ij}\rvert^2$ である。$A,B$ が Hermite 行列で固有値を大きい順に並べれば、$\sigma$ は恒等置換にとれる。
$A=U\operatorname{diag}(\alpha)U^*$、$B=V\operatorname{diag}(\beta)V^*$ とし、$W:=U^*V$ とおく。Frobenius ノルムはユニタリ行列を掛けても変わらないので
$$
\|A-B\|_F^2=\|\operatorname{diag}(\alpha)W-W\operatorname{diag}(\beta)\|_F^2=\sum_{i,j}\lvert\alpha_i-\beta_j\rvert^2\lvert w_{ij}\rvert^2
$$
である。$(\lvert w_{ij}\rvert^2)\in\Omega_n$ なので、右辺は $c_{ij}:=\lvert\alpha_i-\beta_j\rvert^2$ の線形関数の $\Omega_n$ 上の値であり、rem-ds-birkhoff により $\min_\sigma\sum_ic_{i\sigma(i)}$ 以上である。
Hermite の場合、固有値は実数で、$\sum_i(\alpha_i-\beta_{\sigma(i)})^2=\sum_i\alpha_i^2+\sum_j\beta_j^2-2\sum_i\alpha_i\beta_{\sigma(i)}$ である。並べ替え不等式により最後の和は $\alpha,\beta$ を同じ順に並べたときに最大である。$\square$
定理は HW53 による。証明の核は、線形関数の最小値が 置換行列 でとれることである。
| 外す条件 | 反例 | 成り立たなくなるもの |
|---|---|---|
| 各列の和が $1$ | $\begin{pmatrix}1&0\\1&0\end{pmatrix}$(行の和は $1$) | 置換行列の凸結合であること |
| 成分が $0$ 以上 | $\begin{pmatrix}2&-1\\-1&2\end{pmatrix}$(行と列の和は $1$) | 置換行列の凸結合であること、prop-ds-basic の 2(固有値 $3$) |
| 成分が正(Sinkhorn) | $\begin{pmatrix}1&1\\0&1\end{pmatrix}$($0$ 以上で、正の対角をもつ) | thm-ds-sinkhorn の存在 |
| $A$ が正規行列(Hoffman–Wielandt) | $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$、$B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ | thm-ds-hw の不等式 |
第 3 行を確かめる。$D_1AD_2=\begin{pmatrix}b&c\\0&d\end{pmatrix}$($b,c,d>0$)なら、第 1 列の和から $b=1$、第 1 行の和から $c=0$ となって矛盾する。第 4 行では、$B$ は正規行列で、固有値は $A$ が $0,0$、$B$ が $\pm1$ である。左辺はどの $\sigma$ でも $2$、右辺は $\|A-B\|_F^2=1$ である。
| 誤り | 正しくは |
|---|---|
| 正則な二重確率行列の逆行列も二重確率行列である | $\frac14\begin{pmatrix}3&1\\1&3\end{pmatrix}$ の逆行列は $\frac12\begin{pmatrix}3&-1\\-1&3\end{pmatrix}$ で、負の成分をもつ。$J_n$($n\ge2$)は正則でさえない |
| $\Omega_n$ の元はどれもユニタリ行列の成分の絶対値の 2 乗で書ける | $n\ge3$ で偽(prop-ds-unitary の 2) |
| Birkhoff の分解は一意である | $J_n$($n\ge3$)は巡回シフトの平均にも全置換の平均にもなる |
| 対称な $0$ 以上の行列なら二重確率行列である | 各行の和が $1$ であることが必要である |
Markov 連鎖との関係. $P\in\Omega_n$ を推移行列とする Markov連鎖 で分布 $\pi$ が $\pi P$ に移ると、$\pi P$ は $\pi$ に優越される。よって Karamataの不等式 と凹関数 $-x\log x$ により、Shannonエントロピー は 1 回の推移で減らない。
割当問題. 線形関数の最小化が置換で達成されることは、割当問題が線形計画として解けることの根拠である(輸送問題)。
パーマネントの下界. $\Omega_n$ の上の $\operatorname{per}$ の最小値は $n!/n^n$ で、$J_n$ だけでとる(van der Waerden予想(パーマネント))。最大値は $1$ で、prop-ds-basic の 3 のとおり頂点でとる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する