パーマネント (数学)

線型代数学における正方行列のパーマネント（テンプレート:Lang-en-short）は、行列式 (determinant) によく似たテンプレート:Ill2である。パーマネントは、行列式と同様に、行列の成分を変数とする多項式である。Permutation（置換）と determinant（行列式）を合成したカバン語をもじったものである。英単語の「Permanent」から永久式または恒久式と訳されたこともある。

パーマネントと行列式はともに、より一般の行列函数イマナントの特別の場合である。

定義

テンプレート:Mvar次正方行列 テンプレート:Math2 のパーマネントは

$\mathrm{perm}(A):=\sum _{\sigma \in S_n}\prod _{i=1}^n{a}_{i,\sigma (i)}$

で与えられる。右辺の和は、対称群 テンプレート:Mvar の任意の元 テンプレート:Mvar（つまり、番号 テンプレート:Math2 の置換）に亙ってとるものとする。

例えば、二次正方行列に対しては

$\mathrm{perm}\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=ad+bc$

であり、三次正方行列に対しては

$\mathrm{perm}\left(\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right)=aei+bfg+cdh+ceg+bdi+afh$

となる。

テンプレート:Mvar のパーマネントの定義において、テンプレート:Mvar の行列式のそれと異なる点は、各置換（に対応する項）に対して行列式が置換の符号を考慮するのに対してパーマネントは考慮しないことである。

行列 テンプレート:Mvar のパーマネントは記号で テンプレート:Math2 などと書く（引数をパーレンで括ることもある）。テンプレート:Harvtxt は テンプレート:Mvar が矩形行列の場合に テンプレート:Math, 正方行列には テンプレート:Math と使い分けている。テンプレート:Harvtxt は $\stackrel{+}{|}\stackrel{+}{|}$ で括る記法を用いている。

術語「パーマネント」は元々はコーシーが1812年に “fonctions symétriques permanentes” として関連する函数の一種に対して用いた。より特定した現代的な意味での使用は テンプレート:Harvtxt によるテンプレート:Sfnテンプレート:Rp。

性質

パーマネントを テンプレート:Mvar本の列（または行）ベクトルを引数にとる写像と見るとき、多重線型テンプレート:Ill2（引数となるベクトルの順番を入れ替えても結果は変わらない）である。より具体的に、テンプレート:Mvar次正方行列 テンプレート:Math に対して以下が成り立つテンプレート:Sfnテンプレート:Rp：

• テンプレート:Math は テンプレート:Mvar の行または列ベクトルに関する任意の置換の下で不変である。この性質を任意の置換行列 テンプレート:Math2 を用いて テンプレート:Math2 という形で記号的に表せる。
• テンプレート:Mvar の任意の一つの行または列にスカラー テンプレート:Mvar を掛けるとき、テンプレート:Math は テンプレート:Math に写る。
• テンプレート:Math は転置の下で不変：テンプレート:Math.

テンプレート:Mvar次正方行列 テンプレート:Math2 に対し

$\mathrm{perm}(A+B)=\sum _{s,t}\mathrm{perm}(a_{ij}{)}_{i\in s,j\in t}\mathrm{perm}(b_{ij}{)}_{i\in \overline{s},j\in \overline{t}}$

が成立するテンプレート:Sfnテンプレート:Rp。ただし、テンプレート:Math2 は テンプレート:Math2 の同じサイズの部分集合で、テンプレート:Math2 はそれぞれの補集合である。

これと対照に、行列式の基本性質である乗法性はパーマネントでは成り立たないテンプレート:Sfnテンプレート:Rpテンプレート:Efn。

行列式に対するラプラス展開と同様に、パーマネントを行、列または対角線にそって展開することができるテンプレート:Sfnテンプレート:Rp（行列式の場合には各余因子に交代符号が付いたが、パーマネントの場合には符号は付かない）。テンプレート:Efn

応用

行列式の場合とは違い、パーマネントは平易な幾何学的解釈はない。主な応用先として、組合せ論、量子力学におけるボソンのグリーン関数の扱いにおいて、およびテンプレート:Ill2システムの状態可能性の決定においてなどがある。ただし、2種類のグラフ理論的解釈をもつ（有向グラフのテンプレート:Ill2の重み付き和、および二部グラフにおける完全マッチングの重み付き和）。

対称テンソル

パーマネントはヒルベルト空間上の対称テンソル冪の研究において自然に生じてくる。具体的に、テンプレート:Mvar をヒルベルト空間とし、その対称テンソル全体の成す空間である対称テンソル冪を ${\bigvee }^{k}H$ と書くと、特に ${\bigvee }^{k}H$ は テンプレート:Mvar の元からなる対称（テンソル）積によって生成されることに注意する。テンプレート:Math2 の対称積は

$x_1\vee x_2\vee \cdots \vee x_k:=(k!{)}^{-\frac{1}{2}}\sum _{\sigma \in S_k}{x}_{\sigma (1)}\otimes x_{\sigma (2)}\otimes \cdots \otimes x_{\sigma (k)}$

と定義される。${\bigvee }^{k}H$ を（テンプレート:Mvar の テンプレート:Mvar次テンプレート:Ill2 ${⨂}^{k}H$ の部分空間として）考えるとき、その上に内積 テンプレート:Math が定義されれば、それに応じて

$⟨x_1\vee x_2\vee \cdots \vee x_k,y_1\vee y_2\vee \cdots \vee y_k⟩=\mathrm{perm}((⟨x_i,y_j⟩{)}_{1\le i,j\le k})(x_j,y_j\in H)$

となることが分かる。コーシー＝シュワルツの不等式を適用すれば、$\mathrm{perm}((⟨x_i,x_j⟩{)}_{1\le i,j\le k})\ge 0$ および

$|\mathrm{perm}((⟨x_i,y_j⟩{)}_{1\le i,j\le k}){|}^2\le \mathrm{perm}((⟨x_i,x_j⟩{)}_{1\le i,j\le k})\cdot \mathrm{perm}((⟨y_i,y_j⟩{)}_{1\le i,j\le k})$

が確かめられる。

閉路被覆

任意の正方行列 テンプレート:Math2 は適当な重み付き有向グラフの隣接行列と見なすことができて、各 テンプレート:Mvar は頂点 テンプレート:Mvar から テンプレート:Mvar へ結ぶ弧の重み付けを表す。 重み付き有向グラフのテンプレート:Ill2とは、その有向グラフの点素 (vertex-disjoint) な有向閉路の集まりで、グラフの全ての頂点を被覆するものをいう。このとき、有向グラフの各頂点 テンプレート:Mvar は、その閉路被覆において一意的な「後続点」テンプレート:Math を持ち、テンプレート:Mvar は テンプレート:Math2（テンプレート:Mvar はグラフの頂点数）の置換となる。逆に、テンプレート:Math2 上の任意の置換 テンプレート:Mvar は、各 テンプレート:Mvar に対して頂点 テンプレート:Mvar から テンプレート:Math へ結ぶ弧がある閉路被覆に対応する。

「閉路被覆の重み」を各閉路における重みの総乗と定めるならば、

$\mathrm{weight}(\sigma ):=\prod _{i=1}^n{a}_{i,\sigma (i)}$

と書ける。テンプレート:Mvar次正方行列 テンプレート:Mvar のパーマネントの定義

$\mathrm{perm}(A)=\sum _{\sigma }\prod _{i=1}^n{a}_{i,\sigma (i)}$

（テンプレート:Mvar は テンプレート:Math2 上の置換）と比較すれば、隣接行列 テンプレート:Mvar のパーマネントが、対応する有向グラフの閉路被覆全てに亙る重み付き和に等しいことが分かる。

完全マッチング

正方行列 テンプレート:Math2 を、頂点集合 テンプレート:Math2 および テンプレート:Math2 を持つ二部グラフで、頂点 テンプレート:Mvar から頂点 テンプレート:Mvar へ結んだ辺の重みが テンプレート:Mvar であるものの隣接行列と見ることもできる。テンプレート:Mvar を テンプレート:Mvar にマッチさせる テンプレート:Ill2 テンプレート:Mvar の重みを、このマッチングに現れる辺全ての重みの総乗と定義するならば

$\mathrm{weight}(\sigma ):=\prod _{i=1}^n{a}_{i,\sigma (i)}$

と書けるから、テンプレート:Mvar のパーマネントはこの二部グラフの完全マッチング全てに亙る重み付き和に等しいことが分かる。

テンプレート:Vanc

数え上げ

多くの数え上げ問題に テンプレート:Math と テンプレート:Math のみを成分とする行列のパーマネントを計算することで答えることができる。

テンプレート:Math2 は テンプレート:Mvar次 テンプレート:Math-値の行列で各行各列の成分の和が テンプレート:Mvar に等しいもの全体の成すクラスとする。このクラスに属する任意の行列 テンプレート:Mvar は テンプレート:Math2 であるテンプレート:Sfnテンプレート:Rp。射影平面の接続行列は、適当な整数 テンプレート:Math2 に対するクラス テンプレート:Math2 に属する。最小の射影平面に対応するパーマネントは計算されており、テンプレート:Math2 に対してその値はそれぞれ テンプレート:Math となるテンプレート:Sfnテンプレート:Rp。テンプレート:Math2 のときの射影平面（ファノ平面と呼ばれる）の接続行列を テンプレート:Mvar とすると、特筆すべきことに テンプレート:Math2 が成り立っている（右辺は テンプレート:Mvar の行列式の絶対値の意味である）。これは テンプレート:Mvar が巡回行列であることと、以下の定理からの帰結であるテンプレート:Sfnテンプレート:Rp。

定理

テンプレート:Mvar がクラス テンプレート:Math に属する巡回行列ならば、テンプレート:Math のとき、テンプレート:Math2 であり、テンプレート:Math のとき テンプレート:Math2 が成り立つ。さらには、テンプレート:Math2 のとき、行および列を入れ替えて、テンプレート:Mvar を行列 テンプレート:Mvar の テンプレート:Mvar個のコピーの直和の形にすることができて、したがって テンプレート:Math2 および テンプレート:Math2 となる。

位置の制限（禁止）を含む置換の総数の計算にもパーマネント は利用できる。標準 テンプレート:Mvar元-集合 テンプレート:Math2 に対して、テンプレート:Math を、各 テンプレート:Mvar は素の置換で テンプレート:Math2 と写せるならば テンプレート:Math, さもなくば テンプレート:Math と定めて得られる テンプレート:Math-行列とするとき、テンプレート:Math は標準 テンプレート:Mvar-元集合上でこれらの制限を全て満たす置換の総数に等しいテンプレート:Sfnテンプレート:Rp。このような例としてよく知られた特別の場合が、完全順列問題（不動点を全く持たない場合）とテンプレート:Ill2（problème des ménages: 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める）である。完全順列の場合、テンプレート:Mvar元-集合において不動点が一つもない置換の総数は

$\mathrm{perm}(J-I)=\mathrm{perm}\left(\begin{array}{ccccc}0& 1& 1& \dots & 1\\ 1& 0& 1& \dots & 1\\ 1& 1& 0& \dots & 1\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 1& 1& \dots & 0\end{array}\right)=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}$

で与えられる。ただし テンプレート:Mvar は全ての成分が テンプレート:Math の テンプレート:Mvar次正方行列で、テンプレート:Mvar は テンプレート:Mvar次単位行列である。一方、メナージュ問題の場合の数（テンプレート:Ill2）は

$\begin{array}{cc}\mathrm{perm}(J-I-I^{\prime })& =\mathrm{perm}\left(\begin{array}{ccccc}0& 0& 1& \dots & 1\\ 1& 0& 0& \dots & 1\\ 1& 1& 0& \dots & 1\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 1& 1& \dots & 0\end{array}\right)\\ & =\sum _{k=0}^n(-1{)}^k\frac{2n}{2n-k}(\genfrac{}{}{0ex}{}{2n-k}{k})(n-k)!\end{array}$

で与えられる。ただし、テンプレート:Mvar は テンプレート:Math成分および テンプレート:Math成分のみが非零である テンプレート:Math-行列とする。

上界

テンプレート:Ill2（テンプレート:Harvsで予想され、テンプレート:Ill2が1973年に証明したテンプレート:Sfnテンプレート:Rp）は テンプレート:Mvar次 テンプレート:Math-行列の上界を与える。

定理 (Bregman–Minc inequality)

各 テンプレート:Math2 に対して、テンプレート:Mvar の第 テンプレート:Mvar行には テンプレート:Mvar個の テンプレート:Math があるものとするとき、

$\mathrm{perm}A\le \prod _{i=1}^n(r_i){!}^{\frac{1}{r_i}}$

が成り立つ。

ファンデルヴェルデンの予想

テンプレート:Harvtxt はテンプレート:Mvar次二重確率行列の中で最小のパーマネントは テンプレート:Math で、それは全ての成分が テンプレート:Math に等しい行列によって達成されると予想した。この予想の証明は、テンプレート:Harvs および テンプレート:Harvs および テンプレート:Harvsとして出版された。Egorychev の証明はテンプレート:Ill2の一つの応用であるテンプレート:Sfn。この業績により Egorychev と Falikman はファルカーソン賞を1982年に受賞している。

計算

テンプレート:Main 定義通りに素朴にパーマネントを計算しようとすれば、比較的小さい行列に対してさえ計算量的に不可能である。知られている最も速いアルゴリズムの一つは テンプレート:Harvs による包除原理に基づいたテンプレート:Ill2で、以下のように与えられるテンプレート:Sfnテンプレート:Rp:

主張

テンプレート:Mvar は テンプレート:Mvar から テンプレート:Mvar 個の列を取り除いて得られる任意の行列とする。テンプレート:Math は テンプレート:Mvar の行和の総乗とし、テンプレート:Mvar として考え得る全ての行列に亙って テンプレート:Math を加えた和を テンプレート:Math と書けば、

$\mathrm{perm}(A)=\sum _{k=0}^{n-1}(-1{)}^k{\mathrm{\Sigma }}_k$

が成り立つ。あるいはこれを行列の成分を陽に出して書けば

$\mathrm{perm}(A)=(-1{)}^n\sum _{S\subseteq \{1,\dots ,n\}}(-1{)}^{|S|}\prod _{i=1}^n\sum _{j\in S}{a}_{ij}$ と書ける。

パーマネントの計算は行列式の場合に比べて複雑になると信じられている（例えば、行列式はガウスの消去法を用いて多項式時間で計算できるが、パーマネントはガウス消去では計算できない）。もっと言えば、テンプレート:Math-行列のパーマネントの計算はテンプレート:Ill2である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、テンプレート:Nowrap となるが、これは [[P≠NP予想|テンプレート:Nowrap]] よりもいっそう強い主張である。しかし、テンプレート:Mvar の成分が全て非負の場合、パーマネントは確率的多項式時間で近似的に計算することができる（その誤差は、パーマネントの値 テンプレート:Mvar と任意の テンプレート:Math2 に対する テンプレート:Mvar に関するオーダーでとる）。半正定値行列のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる（この近似で達成可能な最良の誤差は テンプレート:Math である。テンプレート:Mvar はやはりパーマネントの値とする）。

マクマホンの基本定理

テンプレート:Main パーマネントを多変数母函数を通じて解釈する視点もある。テンプレート:Mvar次正方行列 テンプレート:Math に対して、多変数母函数

$F(x_1,x_2,\dots ,x_n):=\prod _{i=1}^n\left(\sum _{j=1}^n{a}_{ij}{x}_j\right)=\left(\sum _{j=1}^n{a}_{1j}{x}_j\right)\left(\sum _{j=1}^n{a}_{2j}{x}_j\right)\cdots \left(\sum _{j=1}^n{a}_{nj}{x}_j\right)$

を考えると、テンプレート:Math2 における $x_1{x}_2\dots x_n$ の係数は テンプレート:Math に等しいテンプレート:Sfnテンプレート:Rp。

このことの一般化として、

定義

任意の長さ テンプレート:Mvar の非負整数列 $s_1,s_2,\dots ,s_n$ に対して

${\mathrm{perm}}^{(s_1,s_2,\dots ,s_n)}(A)$ を ${\left(\sum _{j=1}^n{a}_{1j}{x}_j\right)}^{s_1}{\left(\sum _{j=1}^n{a}_{2j}{x}_j\right)}^{s_2}\cdots {\left(\sum _{j=1}^n{a}_{nj}{x}_j\right)}^{s_n}$ における ${x_1}^{s_1}{x_2}^{s_2}\cdots {x_n}^{s_n}$ の係数

と定める。

定理 (MacMahon's Master Theorem)

パーマネントと行列式の間の関係として、

「${\mathrm{perm}}^{(s_1,s_2,\dots ,s_n)}(A)$ は $\frac{1}{\det (I-XA)}$ における ${x_1}^{s_1}{x_2}^{s_2}\cdots {x_n}^{s_n}$ の係数に等しい」

が成り立つテンプレート:Sfnテンプレート:Rp。ただし、テンプレート:Mvar は テンプレート:Mvar次単位行列で、テンプレート:Mvar は対角成分が テンプレート:Math2 である対角行列とする。

テンプレート:Vanc

パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合と見るものがある。具体的には、テンプレート:Math2 行列 テンプレート:Math2 で テンプレート:Math2 とするとき、

$\mathrm{perm}(A):=\sum _{\sigma \in P(n,m)}{a}_{1\sigma (1)}{a}_{2\sigma (2)}\dots a_{m\sigma (m)}$

と定める。ただし、テンプレート:Math は テンプレート:Mvar元-集合 テンプレート:Math2 から テンプレート:Mvar 元選ぶ部分置換（順列）全体の成す集合であるテンプレート:Sfnテンプレート:Rp。

パーマネントに対するRyserの計算論的結果も一般化できる。テンプレート:Mvar が テンプレート:Math 行列 (テンプレート:Math2) のとき、テンプレート:Mvar から テンプレート:Mvar 個の列を取り除いて テンプレート:Mvar が得られるとすると、テンプレート:Mvar の行和の積を テンプレート:Math, 可能な全ての テンプレート:Mvar に対する テンプレート:Math の総和を テンプレート:Mvar と書けば、

$\mathrm{perm}(A)=\sum _{k=0}^{m-1}(-1{)}^k(\genfrac{}{}{0ex}{}{n-m+k}{k}){\sigma }_{n-m+k}$

が成り立つテンプレート:Sfnテンプレート:Rp。

完全代表系

矩形行列に対してパーマネントの定義を一般化することで、いくつかの応用においてはより自然な方法でこれを用いることができるようになる。例えば:

命題

（相異なるとは限らない）テンプレート:Math2 は テンプレート:Mvar元-集合の部分集合で、テンプレート:Math2 とする。この部分集合族の接続行列 テンプレート:Mvar は テンプレート:Math2 の テンプレート:Math2-行列である。この族のテンプレート:Ill2（systems of distinct representatives; 相異なる代表系、個別代表系; SDR）総数は テンプレート:Math であるテンプレート:Sfnテンプレート:Rp。テンプレート:Efn

関連項目

• テンプレート:Ill2：順序統計学における応用
• スレイター行列式：量子力学における応用

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation

関連文献

• テンプレート:Citation Contains a proof of the Van der Waerden conjecture.
• テンプレート:Citation

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:MathWorld
• テンプレート:PlanetMath
• テンプレート:PlanetMath
• テンプレート:ProofWiki
• テンプレート:SpringerEOM