大学数学基礎解説

2重確率行列の存在の特徴づけ～2022年度東京大学大学院数理科学研究科公開講座「量子の世界の数学」に参加して～

二重確率行列

346

はじめに

この記事は「量子の世界の数学」の講演資料を参考に作りました．

昨日，東大の公開講座「量子の世界の数学」に参加してきました．

帰りに撮った写真．駒場祭と同日開催だった．

数学書やネットの記事などでしか出会ったことがない数学者の方々に対面でお会いすることが出来たり質問で来たりしたのがよかったです．数理棟30周年の冊子ももらいました．数学漬けの一日で，めっちゃホリデーでした．

一番印象に残っているのは，福泉先生の講演後に，参加者の邪魔にならないように屈みながら歩いていた河東先生です．丁度自分の席の横方面を進んでおられて，必死に進んでいた先生とたまに目が合って気まずくなりました．
河東先生の講演では質問もさせて頂き，回答して頂きました．
例えば「なんとかという数を素因数分解したい！」と思って，量子コンピュータを使って結果を得るということを考えます．ここで遠回りをして，素因数分解に対応する組みひもを作り，その組みひもに対応するジョーンズ多項式を得て，それから複素数の値が得られるんですが，なんとその値と，はじめに書いた量子コンピュータを使った素因数分解の結果が対応するというお話（トポロジカル量子コンピュータ．この対応によりエラーコントロールが簡単になるとのことでした．）が最後にあったのですが・・・，
組みひもが1本，2本と数えられる範囲のものであったことが引っ掛かりました．Mathlogにてネットからはじめる位相空間論というシリーズものを作っている（つもり）で，どうしても点列ではなくネットを使わなければならない具体例を探していた私は，トポロジカル量子コンピュータで非可算の対象を扱う・または扱わざるをえない状況の有無について土壇場で質問してみました．河東先生のアンサーは「離散的な対象だとエラーコントロールができるけど連続的対象だと難しくなる」とのことでした．質問時に手持ちの荷物をバラバラ床に落とすくらい落ち着きがなく，分かりづらい質問の仕方をした私にも真摯に答えて頂き，とてもありがたかったです．

そして，最後の緒方先生の講演も印象的でした．
緒方先生の講演は線形代数の問題を通して理解を深めようという形でした．僕は味わい深かったですが，中にはノート替わりのiPadに頭を突っ伏していた人もいました．一般向けか？という物差しだったらちょいレベル高かったと思いますねー．がしかしかなり興味深いお話があったので今回はそれを皆さんに紹介します．
全部を全部紹介するのではなく，講演にて特定の場合でしか示されなかった定理があるんですが，その証明を完成させたいと思います．

目標：緒方先生の講演にあった，二重確率行列の存在の特徴づけ定理の証明を完成してみる

本題

二重確率行列の存在の特徴づけ，に進む前にまず二重確率行列を定義します．

二重確率行列

$(\begin{matrix} a_{11} & \dots & a_{1 n} \\ ⋮ & ⋱ & ⋮ \\ a_{n 1} & \dots & a_{n n} \end{matrix})$
が二重確率行列
$⟺$ 非負の実対称行列で $\forall i \in {1, 2, \dots, n} \sum_{j = 1}^{n} a_{i j} = 1, \sum_{k = 1}^{n} a_{k i} = 1$

各行各列で成分を足すと共に1になる，全ての成分が非負な実対称行列のことです．二重確率行列の成分はどれも $0$ 以上 $1$ 以下です．

ここで次の問いを考えてみます．これは講演で実際に出た例です．

$x := (\begin{matrix} \frac{3}{5} \\ \frac{2}{5} \end{matrix}) y := (\begin{matrix} \frac{4}{5} \\ \frac{1}{5} \end{matrix})$
という2つの列ベクトルを用意した時， $y = A x$ となる二重確率行列があるか？

二択です．どうでしょうか？答えは「ない」です．こうやって問題出してすぐに答え出す人は嫌な感じがしますが，とりあえず解説に進んでみます．
背理法で， $y = A x$ なる $2 \times 2$ の二重確率行列 $A$ を， $a \in [0, 1]$ を用いて
$(\begin{matrix} a & 1 - a \\ 1 - a & a \end{matrix})$
とする（というかこういう形にならざるを得ないんだけど）と，計算していくと $a = 2$ となって，「二重確率行列の成分はどれも $0$ 以上 $1$ 以下」に反してしまいます．

さて，この結果を一般化させます．

二重確率行列の存在の特徴付け

$x := (\begin{matrix} x_{1} \\ ⋮ \\ x_{n} \end{matrix}), y := (\begin{matrix} y_{1} \\ ⋮ \\ y_{n} \end{matrix})$
( $n \in N$ )で以下を満たすものを考える：
$\sum_{i = 1}^{n} x_{i} = 1, \sum_{j = 1}^{n} y_{j} = 1, x_{1} ≧ x_{2} ≧ \dots ≧ x_{n} ≧ 0, y_{1} ≧ y_{2} ≧ \dots ≧ y_{n} ≧ 0$

このとき以下は同値：
$(1) \exists$ 二重確率行列 $A$ s.t. $y = A x$
$(2) \forall k \in {1, \dots, n - 1}, \sum_{j = 1}^{k} y_{j} ≦ \sum_{i = 1}^{k} x_{i}$

この定理を使ってさっきの問題を考えてみると， $(2)$ の $k = 1$ として $y_{1} ≦ x_{1}$ とならないので， $y = A x$ なる二重確率行列 $A$ がないことがわかります．一発ですね．
この定理を示します． $n = 1$ のときはアタリマエすぎる $(x = y = A = 1)$ ので， $n ≧ 2$ の証明に文字数を費やします．

$n = 2$ の証明（講演にあったもの）

$(1) ⟹ (2)$
$0 ≦ \exists a ≦ 1$ s.t.
$(\begin{matrix} a & 1 - a \\ 1 - a & a \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \end{matrix}) = (\begin{matrix} a x_{1} + (1 - a) x_{2} \\ (1 - a) x_{1} + a x_{2} \end{matrix}) = (\begin{matrix} y_{1} \\ y_{2} \end{matrix})$
このとき
$y_{1} = a x_{1} + (1 - a) x_{2} \overset{x_{2} ≦ x_{1} より}{≦} a x_{1} + (1 - a) x_{1} = x_{1}$
$∴ (2)$ 成立．

$(2) ⟹ (1)$ : $y_{1} ≦ x_{1}$ と仮定．このとき
$1 - y_{2} \overset{y の定義}{=} y_{1} ≦ x_{1} \overset{x の定義}{=} 1 - x_{2}$
$∴ x_{2} ≦ y_{2}$
このとき $x_{2} ≦ y_{2} ≦ y_{1} ≦ x_{1}$ で， $y_{1}$ が $x_{1}, x_{2}$ の間にあるので， $x_{1}, x_{2}$ の凸結合で表せる：
$0 ≦ \exists a ≦ 1$ s.t. $y_{1} = a x_{1} + (1 - a) x_{2}$
$∴ y_{2} = 1 - y_{1} = 1 - (a x_{1} + (1 - a) x_{2}) = (x_{1} + x_{2}) - (a x_{1} + (1 - a) x_{2}) = (1 - a) x_{1} + a x_{2}$
このとき
$(\begin{matrix} a & 1 - a \\ 1 - a & a \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \end{matrix}) = (\begin{matrix} y_{1} \\ y_{2} \end{matrix})$
$(1)$ 成立．

一般の場合の証明（直接計算）

$n = k - 1 (k = 2, 3, \dots)$ での $(1) ⟺ (2)$ の成立を仮定し， $n = k$ での成立を示す．
$(1) ⟹ (2)$
$x := (\begin{matrix} x_{1} \\ ⋮ \\ x_{k} \end{matrix}), y := (\begin{matrix} y_{1} \\ ⋮ \\ y_{k} \end{matrix})$
$\sum_{i = 1}^{k} x_{i} = 1, \sum_{j = 1}^{k} y_{j} = 1, x_{1} ≧ x_{2} ≧ \dots ≧ x_{k} ≧ 0, y_{1} ≧ y_{2} ≧ \dots ≧ y_{k} ≧ 0$
とした時，二重確率行列 $A = (A_{i j})$ が存在し $y = A x$ を満たすとする．
$(\begin{matrix} y_{1} \\ y_{2} \\ y_{3} \\ ⋮ \\ y_{l} \\ ⋮ \\ y_{k - 1} \\ y_{k} \end{matrix}) = (\begin{matrix} a_{11} & a_{12} & a_{13} & \dots & a_{1 l} & \dots & a_{1 (k - 1)} & 1 - \sum_{i_{1} = 1}^{k - 1} a_{1 i_{1}} \\ a_{12} & a_{22} & a_{23} & \dots & a_{2 l} & \dots & a_{2 (k - 1)} & 1 - (a_{12} + \sum_{i_{2} = 2}^{k - 1} a_{2 i_{2}}) \\ a_{13} & a_{23} & a_{33} & \dots & a_{3 l} & \dots & a_{3 (k - 1)} & 1 - (a_{13} + a_{23} + \sum_{i_{3} = 3}^{k - 1} a_{3 i_{3}}) \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & \dots & ⋮ & ⋮ \\ a_{1 l} & a_{2 l} & a_{3 l} & \dots & a_{l l} & \dots & a_{l (k - 1)} & 1 - (\sum_{m_{l} = 1}^{l - 1} a_{m_{l} l} + \sum_{i_{l} = l}^{k - 1} a_{l i_{l}}) \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ a_{1 (k - 1)} & a_{2 (k - 1)} & a_{3 (k - 1)} & \dots & a_{l (k - 1)} & \dots & a_{(k - 1) (k - 1)} & 1 - (\sum_{m_{k - 1} = 1}^{(k - 1) - 1} a_{m_{k - 1} k - 1} + \sum_{i_{k - 1} = k - 1}^{k - 1} a_{k - 1 i_{k - 1}}) \\ 1 - \sum_{i_{1} = 1}^{k - 1} a_{1 i_{1}} & 1 - (a_{12} + \sum_{i_{2} = 2}^{k - 1} a_{2 i_{2}}) & 1 - (a_{13} + a_{23} + \sum_{i_{3} = 3}^{k - 1} a_{3 i_{3}}) & \dots & 1 - (\sum_{m_{l} = 1}^{l - 1} a_{m_{l} l} + \sum_{i_{l} = l}^{k - 1} a_{l i_{l}}) & \dots & 1 - (\sum_{m_{k - 1} = 1}^{(k - 1) - 1} a_{m_{k - 1} k - 1} + \sum_{i_{k - 1} = k - 1}^{k - 1} a_{k - 1 i_{k - 1}}) & 2 - k + \sum_{s = 1}^{k - 1} a_{s s} + 2 (\sum_{1 ≦ t < u ≦ k - 1} a_{t u}) \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ x_{l} \\ ⋮ \\ x_{k - 1} \\ x_{k} \end{matrix})$
このとき $l \in {1, \dots, k - 1}$ に対し
$y_{l} = a_{1 l} x_{1} + a_{2 l} x_{2} + a_{3 l} x_{3} + \dots + a_{l l} x_{l} + \dots + a_{l (k - 1)} x_{k - 1} + {1 - (\sum_{m_{l} = 1}^{l - 1} a_{m_{l} l} + \sum_{i_{l} = l}^{k - 1} a_{l i_{l}})} x_{k} \overset{n = 2 と同様に}{≦} a_{1 l} x_{1} + a_{12} x_{1} + a_{13} x_{1} + \dots + a_{1 l} x_{l} + \dots + a_{1 (k - 1)} x_{l} + {1 - (\sum_{m_{l} = 1}^{l - 1} a_{m_{l} l} + \sum_{i_{l} = l}^{k - 1} a_{l i_{l}})} x_{l} = x_{l} - {\sum_{m_{l} = 1}^{l - 1} a_{m_{l} l}} (x_{1} - x_{l}) ≦ x_{l}$
複雑すぎるので計算を端折ると
$y_{k} = (1 - \sum_{i_{1} = 1}^{k - 1} a_{1 i_{1}}) x_{1} + (1 - (a_{12} + \sum_{i_{2} = 2}^{k - 1} a_{2 i_{2}})) x_{2} + (1 - (a_{13} + a_{23} + \sum_{i_{3} = 3}^{k - 1} a_{3 i_{3}})) x_{3} + \dots + (1 - (\sum_{m_{l} = 1}^{l - 1} a_{m_{l} l} + \sum_{i_{l} = l}^{k - 1} a_{l i_{l}})) x_{l} + \dots + (1 - (\sum_{m_{k - 1} = 1}^{(k - 1) - 1} a_{m_{k - 1} k - 1} + \sum_{i_{k - 1} = k - 1}^{k - 1} a_{k - 1 i_{k - 1}})) x_{k - 1} + (2 - k + \sum_{s = 1}^{k - 1} a_{s s} + 2 (\sum_{1 ≦ t < u ≦ k - 1} a_{t u})) x_{k} \leq x_{k} - (非負) \leq x_{k}$
$∴ (2)$ 成立．