パーマネント (数学)

線型代数学における正方行列のパーマネントは、行列式  によく似た行列変数の函数である。パーマネントは、行列式と同様に、行列の成分を変数とする多項式である。Permutationと determinantを合成したカバン語をもじったものである。英単語の「Permanent」から永久式または恒久式と訳されたこともある。中国語の名称は積和式。

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

1. 定義
-----

n}}次正方行列 //A// coloneqq}} (//asub のパーマネントは//

で与えられる。右辺の和は、対称群 Ssub の任意の元 σ}}に亙ってとるものとする。

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

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

となる。

A}} のパーマネントの定義において、A}} の行列式のそれと異なる点は、各置換に対して行列式が置換の符号を考慮するのに対してパーマネントは考慮しないことである。

行列 A}} のパーマネントは記号で per   //A//, perm   //A//, Per   //A//}} などと書く。Minc は A}} が矩形行列の場合に Per}}, 正方行列には per}} と使い分けている。Muir は で括る記法を用いている。

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

2. 性質
-----

パーマネントを n}}本の列ベクトルを引数にとる写像と見るとき、多重線型対称函数である。より具体的に、n}}次正方行列 1=//A// = (//asub に対して以下が成り立つRyser25-26}}：//

perm}} は A}} の行または列ベクトルに関する任意の置換の下で不変である。この性質を任意の置換行列 //P//, //Q//}} を用いて 1=perm = perm}} という形で記号的に表せる。
A}} の任意の一つの行または列にスカラー s}} を掛けるとき、perm}} は //s//⋅perm}} に写る。
perm}} は転置の下で不変：1=perm = perm(//A//sup.n}}次正方行列 //A// coloneqq}} (//asub に対し//

が成立するPercus2}}。ただし、//s//, //t//}} は mset の同じサイズの部分集合で、overline はそれぞれの補集合である。

これと対照に、行列式の基本性質である乗法性はパーマネントでは成り立たないRyser26}}簡単な例を以下に示す:

}}。行列式に対するラプラス展開と同様に、パーマネントを行、列または対角線にそって展開することができるPercus12}}。

3. 応用
-----

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

3.1. 対称テンソル
-----------

パーマネントはヒルベルト空間上の対称テンソル冪の研究において自然に生じてくる。具体的に、H}} をヒルベルト空間とし、その対称テンソル全体の成す空間である対称テンソル冪を と書くと、特に は H}} の元からなる対称積によって生成されることに注意する。//x//sub の対称積は

と定義される。 を考えるとき、その上に内積 angbr が定義されれば、それに応じて

となることが分かる。コーシー＝シュワルツの不等式を適用すれば、 および

が確かめられる。

3.2. 閉路被覆
---------

任意の正方行列 //A// coloneqq}}  な有向閉路の集まりで、グラフの全ての頂点を被覆するものをいう。このとき、有向グラフの各頂点 i}} は、その閉路被覆において一意的な「後続点」//σ//}} を持ち、σ}} は msetの置換となる。逆に、mset 上の任意の置換 σ}} は、各 i}} に対して頂点 i}} から //σ//}} へ結ぶ弧がある閉路被覆に対応する。

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

と書ける。n}}次正方行列 A}} のパーマネントの定義

と比較すれば、隣接行列 A}} のパーマネントが、対応する有向グラフの閉路被覆全てに亙る重み付き和に等しいことが分かる。

3.3. 完全マッチング
------------

正方行列 //A// coloneqq}} (//asub を、頂点集合 mset および mset を持つ二部グラフで、頂点 xsub から頂点 ysub へ結んだ辺の重みが asub であるものの隣接行列と見ることもできる。xsub を ysub にマッチさせる 完全マッチング σ}} の重みを、このマッチングに現れる辺全ての重みの総乗と定義するならば//

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

4. 二値行列のパーマネント
--------------

4.1. 数え上げ
---------

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

Ω}} は n}}次 }}-値の行列で各行各列の成分の和が k}} に等しいもの全体の成すクラスとする。このクラスに属する任意の行列 A}} は perm > 0}} であるRyser124}}。射影平面の接続行列は、適当な整数 //n// > 1}} に対するクラス Ω = 24 = abs が成り立っている。これは Z}} が巡回行列であることと、以下の定理からの帰結であるRyser125}}。

定理 A}} がクラス Ω}} に属する巡回行列ならば、//k// > 3}} のとき、perm > abs であり、1=//k// = 3}} のとき 1=perm = abs が成り立つ。さらには、1=//k// = 3}} のとき、行および列を入れ替えて、A}} を行列 Z}} の e}}個のコピーの直和の形にすることができて、したがって 1=//n// = 7//e//}} および 1=perm = 24sup となる。位置の制限を含む置換の総数の計算にもパーマネント は利用できる。標準 n}}元-集合 mset に対して、1=//A// = }}-行列とするとき、perm}} は標準 n}}-元集合上でこれらの制限を全て満たす置換の総数に等しいPercus12}}。このような例としてよく知られた特別の場合が、完全順列問題とメナージュの問題である。完全順列の場合、n}}元-集合において不動点が一つもない置換の総数は//

で与えられる。ただし J}} は全ての成分が 1}} の n}}次正方行列で、I}} は n}}次単位行列である。一方、メナージュ問題の場合の数は

で与えられる。ただし、I'}} は }}成分および }}成分のみが非零である }}-行列とする。

4.2. 上界
-------

ブレグマン–ミンク不等式は n}}次 }}-行列の上界を与える。

定理 各 1 ≤ //i// ≤ //n//}} に対して、A}} の第 i}}行には rsub個の 1}} があるものとするとき、が成り立つ。

5. ファンデルヴェルデンの予想
----------------

Van der Waerden はn}}次二重確率行列の中で最小のパーマネントは //n//!///nsup で、それは全ての成分が sfrac に等しい行列によって達成されると予想した。この予想の証明は、first=B. および first=G. P. および first=D. I. として出版された。Egorychev の証明はアレクサンドロフ–フェンケル不等式の一つの応用であるBrualdi。この業績により Egorychev と Falikman はファルカーソン賞を1982年に受賞している。//

6. 計算
-----

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

主張Asub は A}} から k}} 個の列を取り除いて得られる任意の行列とする。//P//(//Asub は Asub の行和の総乗とし、Asub として考え得る全ての行列に亙って //P//(//Asub を加えた和を Σsub と書けば、が成り立つ。あるいはこれを行列の成分を陽に出して書けば

と書ける。パーマネントの計算は行列式の場合に比べて複雑になると信じられている。もっと言えば、}}-行列のパーマネントの計算はシャープP完全である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、1=ill2 となるが、これは P =}} NP}} よりもいっそう強い主張である。しかし、A}} の成分が全て非負の場合、パーマネントは確率的多項式時間で近似的に計算することができる。半正定値行列のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる。

7. マクマホンの基本定理
-------------

パーマネントを多変数母函数を通じて解釈する視点もある。n}}次正方行列 1=//A// = (//asub に対して、多変数母函数//

を考えると、//F//}} に等しいPercus14}}。

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

定義任意の長さ n}} の非負整数列 に対して を における の係数と定める。 定理  パーマネントと行列式の間の関係として、「 は における の係数に等しい」が成り立つPercus17}}。ただし、I}} は n}}次単位行列で、X}} は対角成分が (//x//sub である対角行列とする。

8. 矩形行列のパーマネント
--------------

パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合と見るものがある。具体的には、//m// × //n//}} 行列 1=//A// = (//asub で //m// ≤ //n//}} とするとき、//

と定める。ただし、//P//}} は n}}元-集合 mset から m}} 元選ぶ部分置換全体の成す集合であるRyser25}}。

パーマネントに対するRyserの計算論的結果も一般化できる。A}} が //m// × //n//}} 行列  のとき、A}} から k}} 個の列を取り除いて Asub が得られるとすると、Asub の行和の積を //P//(//Asub, 可能な全ての Asub に対する //P//(//Asub の総和を σsub と書けば、

が成り立つRyser26}}。

8.1. 完全代表系
----------

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

命題://S//sub は n}}元-集合の部分集合で、//m// ≤ //n//}} とする。この部分集合族の接続行列 A}} は //m// × //n//}} の }}-行列である。この族の横断 総数は perm}} であるRyser54}}。

9. 関連項目
-------

バパット–ベッグの定理：順序統計学における応用
スレイター行列式：量子力学における応用

10. 注
-----

10.1. 注釈
--------

10.2. 出典
--------

11. 参考文献
--------

12. 関連文献
--------

first=Marshall Contains a proof of the Van der Waerden conjecture.

13. 外部リンク
---------