To Advent Calendar 2020

クリスマスと言えば永遠の愛．ということでパーマネント(permanent)について話す．数学におけるパーマネントとは，正方行列$A$に対して定義されるもので，$\mathrm{perm}(A)$と書き，

$$\mathrm{perm}(A) = \sum_{\pi \in \mathcal{S}_n} \prod_{i=1}^n A_{i,\pi(i)}$$

のことである．

定義は行列式(determinant)と似ている．確認のために行列式の定義を書いておくと，正方行列$A$の行列式$\det(A)$とは，

$$\mathrm{det}(A) = \sum_{\pi \in \mathcal{S}_n} \mathrm{sgn}(\pi) \prod_{i=1}^n A_{i,\pi(i)}$$

である．どちらも愚直に計算しようとすると$O(n \cdot n!)$で，定義が似ている２つだが，実は多くの点で異なっている．

小さいサイズならまだしも，大きいサイズの行列式を上の定義式そのままで計算する人はいないだろう．行列式は行基本変形で不変である性質を持ち，それを考えるとガウスの消去法などで$O(n^3)$で計算できる．もっと早い計算アルゴリズムもいくつか知られている．

一方，パーマネントの計算はそう上手くいかない．行列式のような不変性や，行列式がベクトルの体積を表しているみたいな幾何的解釈を持たない．今知られている一番早い計算アルゴリズムはRyser(1963)のRyser法と呼ばれるもので，$O(n \cdot 2^n)$である．さらに，$(0,1)$-行列のパーマネントの計算は$\#P$完全と知られており，$P \neq NP$だとすると，多項式時間では解けないことになる．Valliant(1979)などを参考にすると良い．他に，パーマネントの計算困難性を示唆するのは，パーマネントの計算は二部グラフの完全マッチングの数え上げを含むことである．二部グラフの完全マッチングの数え上げと同じなのは，二部グラフの隣接行列を考えるとわかるだろう．

ついでなので，他の数え上げ問題について言及すると，グラフの全域木は行列木定理によって行列式で書けるので多項式時間で計算できる．また，平面グラフであれば，完全マッチングが多項式時間で計算できることが知られている．これは凄い．

因みに関係ないが，数え上げの計算量クラスで$\#P$はシャープピーと呼ばれるが，よく見るとこれはシャープの記号ではない．

2つの差をテンソル的に言うと，行列式は交代形式で，パーマネントは対称形式であるということである．

1.二重確率行列のパーマネントの話

さて，良く知られたパーマネントの性質として，van-der Waerdenの予想と言われるものがある．これはEgorychev(1981)などにより，肯定的に解決済である．

二重確率行列とは，非負行列で，全ての行和も列和も$1$になるような行列のこと．van-der Waerdenの予想とは，二重確率行列$A$のパーマネントが

$$\frac{n!}{n^n} \approx e^{-n} \leq \mathrm{perm}(A) \leq 1.$$

を満たすというものである．一番大きい値を取るのが単位行列で，一番小さい値を取るのが，例えば$3 \times 3$行列なら，

$$ \left( \begin{array}{ccc} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{array} \right)$$

というものである．これの一般化で，$n \times n$行列で全ての成分が$1/n$になっている行列のパーマネントが$n!/n^n$になることは計算をすれば分かるだろう．

Egorychev(1981)の証明は，パーマネントをそのまま計算して評価を求めるものであったが，母関数を考えると証明がエレガントに終わることが知られている．そのとき用いるのがGurvitsの定理というものだ．これはgeometry of polynomialsという分野でよく現れるもので，real stableな多項式に関する定理である．

定理 (Gurvits 2002)

$p \in \mathbb{R}[z_1,z_2,...,z_n]$を非負係数のreal stableな多項式とする．そのとき，

$$e^{-n} \inf_{z>0} \frac{p(z_1,...,z_n)}{z_1 \cdots z_n} \leq \partial_{z_1} \cdots \partial_{z_n} p |_{z=0} \leq \inf_{z>0} \frac{p(z_1,...,z_n)}{z_1 \cdots z_n}$$

が成立する．

これは$z_1\cdots z_n$の係数が上と下から抑えられることを言っている．二重確率行列$M$に対して，多項式$p$を

$$p(z_1,...,z_n) = \prod_{i=1}^n \sum_{j=1}^n M_{ij} z_j$$

のように定義すると

$$\partial_{z_1} \cdots \partial_{z_n} p |_{z=0} = \mathrm{perm}(M) = \sum_{\sigma \in S_n} \prod_{i=1}^n M_{i \sigma_i}$$

で，AM-GM不等式と行和が$1$であることより

$$p(z_1,...,z_n) \geq \prod_{j=1}^n z_j ^{\sum_{i=1}^n M_{ij}} = \prod_{j=1}^n z_j$$

が成立する．よって、

$$\mathrm{perm}(M) \geq e^{-n}$$

という下限を得る．

一般の行列のパーマネントの近似を得たいときに，上の二重確率行列の性質を用いて，$O(e^{-n})$-近似が得られることが知られている．Sinkhorn(1967)の行列スケーリングのアルゴリズムを使って，行列を二重確率行列に変換することができる．これは，Linial, Samorodnitsky and Wigderson(2000)のアイデアである．

2.相関関数とパーマネントの話

話題を少し変更する．

場の量子論における，相関関数(correlation function)をご存知だろうか？実は，行列式やパーマネントはそれぞれフェルミ粒子，ボソン粒子の相関関数として，場の量子論の中で一例として登場する．

相関関数は，粒子たちがどのようにお互い相関しあって存在するかというものを表現したものである．定義の仕方は分野で様々かもしれない．

フェルミ粒子についてはスレーター行列式を思い出すとわかりやすいかもしれない．
$n$個のフェルミ気体を記述する波動関数は，
1つの波動関数を$\varphi$とすると，

$$\psi(x_1,\ldots ,x_n) =\frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n} \prod_{i=1}^n \varphi_{i}(x_{\sigma(i)}) =\frac{1}{\sqrt{n!}} \det \left( \varphi_{i}(x_{\sigma(i)}) \right) _{1\leq i,j \leq n}$$

で与えられる．これはパウリの排他律を表現しており，同じ場所に異なる粒子は配置しない．
$n$粒子の同時存在確率は，波動関数の2乗で与えられ，

$$\begin{aligned} p(x_1,\ldots ,x_n) &= |\psi(x_1,\ldots ,x_n)|^2 \\ &=\frac{1}{n!} \det \left( \varphi_{i}(x_{\sigma(i)}) \right) _{1\leq i,j \leq n} \det \overline{ \left( \varphi_{i}(x_{\sigma(i)}) \right) } _{1\leq i,j \leq n} \\ &=\frac{1}{n!} \det \left( K(x_i,x_j) \right) _{1\leq i,j \leq n} \end{aligned}$$

となる．

ここで，$K(x,y)=\sum_{i=1}^n \varphi_{i}(x) \varphi_{i}(y)$をカーネルと呼ぶ．さらに，$\{ x_1,\cdots ,x_n \}$について，
相関関数$\rho$は，存在確率$p$で$\rho=n!p$と書けるので，

$$\rho(x_1,\ldots ,x_n) = \sum_{\pi \in S_n} p(x_{\pi_1},\ldots ,x_{\pi_n}) = n! p(x_1,\ldots ,x_n) =\det \left( K(x_i,x_j) \right) _{1\leq i,j \leq n}$$

となる．

さて，一方，ボソン粒子はどうかというと，上の相関関数$\rho$がパーマネントで表現される．ボソン粒子は２つの同種粒子を入れ替えても符号が変化しないので，対称形式であることが分かるだろう．

行列式点過程の話

相関関数の議論を行列式に注目して定義が与えられたものが，行列式点過程(Determinantal Point Process)，あるいは，行列式測度(Determinantal measure)である．これは，上の相関関数が何かしらの行列式で与えられたようなもののことである．一般的な定義として，行列は半正定値エルミート行列として述べられる．同じように，相関関数がパーマネントで与えられるものを，パーマネント点過程(Permanental Point Process)と呼ぶ．性質の良さから，行列式点過程は様々な文脈で研究されている．パーマネント点過程は...，自分はあまり知らない．行列式点過程の性質の良さとは，後で話す不等式によるもので，同時存在確率が上から抑えられることである．これは，粒子の反発性(repulsive)を示唆しており，その性質は他に機械学習などにも広く応用される．

量子計算の話

話が飛び飛びになるが，量子計算が古典的な計算より優れていることを主張する，量子超越性(quantum supremacy)というものがある．例えば，素因数分解を行うShorのアルゴリズムはよく知られていると思う．量子計算において他に注目されているものが，Aaronson and Arkhipov(2013)で提案されたボソンサンプリングである．これは，ガウス行列(ランダムな行列)のパーマネントの期待値を計算するという問題なのだが，先に見てきた通り，古典的な計算では$\#P$完全で，多項式時間で扱えない．それを，ボソン粒子の相関関数として見て計算するのだろうが，最近，アメリカや中国で量子計算により実行されたみたいな論文(2019,2020)が出たらしく，驚いていたりする．量子計算には全く明るくないので，詳しい人は教えて欲しい．

3.パーマネントと不等式評価の話

パーマネントの計算困難性と関連させて，不等式評価を見てみることにする．これらから，行列式とパーマネントの違いが少しずつ見えてくるかもしれない．
分かりやすいように半正定値対称行列を考えるが，一般の行列でも少し違うが似た不等式を得る．まずは，行列式についてHadmardの不等式(1893)というものが知られている．これは，行列$A$が半正定値対称行列なら

$$\det(A) \leq a_{1,1}\cdot a_{2,2} \cdots a_{n,n}$$

と対角成分の要素の積で上から抑えられるというものである．また，これをもう少し一般化して，Fisher
の不等式(1907)が知られている．
半正定値対称行列$A$が

$$ A=\left( \begin{array}{cc} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{array} \right)$$

とブロックに分割されたとき，

$$\det(A) \leq \det(A_{1,1}) \cdot \det(A_{2,2})$$

と上から評価できる．

これは，非対角成分を大きな値に変えてしまっても行列式は大きくならないという話でもある．また，先に行列式の粒子の反発性(repulsive)と述べたのは大体これらの不等式のことである．つまり，行列式点過程で2粒子だけみると，

$$\mathrm{Pr}[x_1とx_2が同時に存在する] \leq \mathrm{Pr}[x_1が存在する] \cdot \mathrm{Pr}[x_2が存在する] $$

という感じである．

さて，一方パーマネントについても同じような不等式が成立することが知られている．ただし，不等式の向きは逆である．

まず，Marcusの不等式(1964)と言われているものは，半正定値対称行列$A$について，

$$\mathrm{perm}(A) \geq a_{1,1}\cdot a_{2,2} \cdots a_{n,n}$$

を言っている．

また，Liebの不等式(1966)は，半正定値対称行列$A$について，Fisherの不等式のブロックと同じように分割されたならば

$$\mathrm{perm}(A)\geq \mathrm{perm}(A_{1,1}) \cdot \mathrm{perm}(A_{2,2})$$

になることを述べている．
これらはパーマネントは行列式と違って，非対角成分を大きくするとパーマネントの値は大きくなっていくことを示唆する．また，パーマネント点過程では，お互い引き寄せあっている事(attractive)を述べている．

基本的に下からの評価が多いパーマネントに関して，上からの評価がないわけではない．Bregman-Mincの不等式(1973)は，一般の行列$A$について，$r_i$を$i$行の行和とすると，

$$\mathrm{perm}(A) \leq \prod_{i=1}^n (r_i!)^{1/r_i}$$

という不等式が成立していることを言っている．

また，Carlen, Lieb and Loss(2006)は，パーマネントに対してもHadmardの不等式と似た形の上からのバウンドを証明している．実は，半正定値とは限らない一般の行列に関して，Hadmardの不等式は，$|a_i|^2=a_{i,1}^2+\cdots + a_{i,n}^2$として，

$$|\det(A)| \leq \prod_{i=1}^n |a_i|$$

と書ける．また，パーマネントに関しては，

$$|\mathrm{perm}(A)| \leq \frac{n!}{n^{n/2}} \prod_{i=1}^n |a_i|$$

である．

不等式は，どれくらいタイトなのだろうか分からないが，これらパーマネントに関する評価の応用は，パーマネントの計算の評価に使えるだけ出なく，グラフの完全マッチングの個数の評価にも使える．いくつか面白い話があるらしい．

4.行列式とパーマネントの一般化の話

最後にこれまで話してきた行列式とパーマネントを上手く一般化したものがあるので，それらを見てみたい．全然詳しくないので，紹介程度になると思われる．まず，Vere-Jones(1988)が導入した$\alpha$-行列式($\alpha$-determinant)というものがある．
これは，行列$A$に対して，

$$\mathrm{det}^{(\alpha)}(A) = \sum_{\pi \in \mathcal{S}_n} \alpha^{\nu(\pi)} \prod_{i=1}^n A_{i,\pi(i)}$$

と定めるものである．ここで，$\nu(\pi)$とは$n$から$\pi$の中にあるサイクルの数を引いた数である．$\alpha$が$-1$なら行列式，$1$ならパーマネントになる．簡単な一般化である．だが，これがどのような振る舞いをするのかは結構難しい．また，$\alpha$-行列式点過程というものが自然と作れそうだが，どのような$\alpha$で存在するかはあまり分かっていない．

また，LittlewoodとRichardson(1934)は，$n$次元の対称群$\mathcal{S}_n$の既約表現が、$n$次のヤング図形($n$の分割)と一対一に対応する性質から，行列式とパーマネントの一般化，イマナント(Immanant)を

$$\mathrm{Imma}_{\lambda}(A) =\sum_{\pi \in \mathcal{S}_n} \chi_{\lambda}(\pi) \prod_{i=1}^n A_{i,\pi(i)}$$

と定めた．ここで，$\chi_{\lambda}$は指標である．指標として交代指標にすると行列式になり，自明な指標にするとパーマネントになる．

他にも，一般化の方法はあるだろうが，自分の知るところはこの程度である．

5.後書き

パーマネントの計算の話を中心に，応物のAdvent Calenderである事を意識して関連した色々な話題を展開した．個々は軽く話す程度になってしまい，深く説明しない部分が多かったように思う．それ故，理解されないパートも多くあるだろう．こんなものがあるんだという程度に適当に読んで頂ければ幸いである．こういうことは後書きではなく，最初に書けと言われそうだ．
後，多くの文献の引用をしたのだが，参考文献を全て提示するのが面倒になってしまった．そのうち更新するかもしれないが，気になったパートがあるなら，個人個人，固有名詞を参考に調べてもらうと助かる．