パーマネント (数学)

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

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

定義

n次正方行列 A ≔ (a_i,j) のパーマネントは

${\displaystyle \operatorname {perm} (A):=\textstyle \sum \limits _{\sigma \in S_{n}}\prod \limits _{i=1}^{n}a_{i,\sigma (i)}}$

で与えられる。右辺の和は、対称群 S_n の任意の元 σ（つまり、番号 1, 2, …, n の置換）に亙ってとるものとする。

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

${\displaystyle \operatorname {perm} \!{\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc}$

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

${\displaystyle \operatorname {perm} \!{\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh}$

となる。

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

行列 A のパーマネントは記号で per A, perm A, Per A などと書く（引数をパーレンで括ることもある）。Minc (1984) は A が矩形行列の場合に Per(A), 正方行列には per(A) と使い分けている。Muir (1882) は ${\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}$ で括る記法を用いている。

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

性質

パーマネントを n本の列（または行）ベクトルを引数にとる写像と見るとき、多重線型対称形式（英語版）（引数となるベクトルの順番を入れ替えても結果は変わらない）である。より具体的に、n次正方行列 A = (a_ij) に対して以下が成り立つ^[6]:25-26：

• perm(A) は A の行または列ベクトルに関する任意の置換の下で不変である。この性質を任意の置換行列 P, Q を用いて perm(A) = perm(PAQ) という形で記号的に表せる。
• A の任意の一つの行または列にスカラー s を掛けるとき、perm(A) は s⋅perm(A) に写る。
• perm(A) は転置の下で不変：perm(A) = perm(A^⊤).

n次正方行列 A ≔ (a_ij), B ≔ (b_ij) に対し

${\displaystyle \operatorname {perm} (A+B)=\textstyle \sum \limits _{s,t}\operatorname {perm} (a_{ij})_{i\in s,j\in t}\operatorname {perm} (b_{ij})_{i\in {\bar {s}},j\in {\bar {t}}}}$

が成立する^[7]:2。ただし、s, t は {1, 2, …, n} の同じサイズの部分集合で、s, t はそれぞれの補集合である。

これと対照に、行列式の基本性質である乗法性はパーマネントでは成り立たない^{[6]:26[注釈 1]}。

行列式に対するラプラス展開と同様に、パーマネントを行、列または対角線にそって展開することができる^[7]:12（行列式の場合には各余因子に交代符号が付いたが、パーマネントの場合には符号は付かない）。^{[注釈 2]}

応用

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

対称テンソル

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

${\displaystyle x_{1}\vee x_{2}\vee \cdots \vee x_{k}:=(k!)^{-{\tfrac {1}{2}}}\textstyle \sum \limits _{\sigma \in S_{k}}x_{\sigma (1)}\otimes x_{\sigma (2)}\otimes \cdots \otimes x_{\sigma (k)}}$

と定義される。${\displaystyle \bigvee ^{k}H}$ を（H の k次テンソル冪（英語版） ${\displaystyle \bigotimes ^{k}H}$ の部分空間として）考えるとき、その上に内積 ⟨,⟩ が定義されれば、それに応じて

${\displaystyle \langle x_{1}\vee x_{2}\vee \cdots \vee x_{k},y_{1}\vee y_{2}\vee \cdots \vee y_{k}\rangle =\operatorname {perm} ((\langle x_{i},y_{j}\rangle )_{1\leq i,j\leq k})\qquad (x_{j},y_{j}\in H)}$

となることが分かる。コーシー＝シュワルツの不等式を適用すれば、${\displaystyle \operatorname {perm} ((\langle x_{i},x_{j}\rangle )_{1\leq i,j\leq k})\geq 0}$ および

${\displaystyle {\Bigl |}\operatorname {perm} ((\langle x_{i},y_{j}\rangle )_{1\leq i,j\leq k}){\Bigr |}^{2}\leq \operatorname {perm} ((\langle x_{i},x_{j}\rangle )_{1\leq i,j\leq k})\cdot \operatorname {perm} ((\langle y_{i},y_{j}\rangle )_{1\leq i,j\leq k})}$

が確かめられる。

閉路被覆

任意の正方行列 A ≔ (a_ij) は適当な重み付き有向グラフの隣接行列と見なすことができて、各 a_ij は頂点 i から j へ結ぶ弧の重み付けを表す。 重み付き有向グラフの閉路被覆（英語版）とは、その有向グラフの点素 (vertex-disjoint) な有向閉路の集まりで、グラフの全ての頂点を被覆するものをいう。このとき、有向グラフの各頂点 i は、その閉路被覆において一意的な「後続点」σ(i) を持ち、σ は {1, 2, …, n}（n はグラフの頂点数）の置換となる。逆に、{1, 2, …, n} 上の任意の置換 σ は、各 i に対して頂点 i から σ(i) へ結ぶ弧がある閉路被覆に対応する。

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

${\displaystyle \operatorname {weight} (\sigma ):=\textstyle \prod \limits _{i=1}^{n}a_{i,\sigma (i)}}$

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

${\displaystyle \operatorname {perm} (A)=\textstyle \sum \limits _{\sigma }\prod \limits _{i=1}^{n}a_{i,\sigma (i)}}$

（σ は {1, 2, …, n} 上の置換）と比較すれば、隣接行列 A のパーマネントが、対応する有向グラフの閉路被覆全てに亙る重み付き和に等しいことが分かる。

完全マッチング

正方行列 A ≔ (a_ij) を、頂点集合 {x₁, x₂, …, x_n} および {y₁, y₂, …, y_n} を持つ二部グラフで、頂点 x_i から頂点 y_j へ結んだ辺の重みが a_ij であるものの隣接行列と見ることもできる。x_i を y_j にマッチさせる 完全マッチング（英語版） σ の重みを、このマッチングに現れる辺全ての重みの総乗と定義するならば

${\displaystyle \operatorname {weight} (\sigma ):=\textstyle \prod \limits _{i=1}^{n}a_{i,\sigma (i)}}$

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

二値行列のパーマネント

数え上げ

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

Ω(n,k) は n次 (0, 1)-値の行列で各行各列の成分の和が k に等しいもの全体の成すクラスとする。このクラスに属する任意の行列 A は perm(A) > 0 である^[6]:124。射影平面の接続行列は、適当な整数 n > 1 に対するクラス Ω(n² + n + 1, n + 1) に属する。最小の射影平面に対応するパーマネントは計算されており、n = 2, 3, 4 に対してその値はそれぞれ 24, 3852, 18,534,400 となる^[6]:124。n = 2 のときの射影平面（ファノ平面と呼ばれる）の接続行列を Z とすると、特筆すべきことに perm(Z) = 24 = |det(Z)| が成り立っている（右辺は Z の行列式の絶対値の意味である）。これは Z が巡回行列であることと、以下の定理からの帰結である^[6]:125。

定理

A がクラス Ω(n,k) に属する巡回行列ならば、k > 3 のとき、perm(A) > |det (A)| であり、k = 3 のとき perm(A) = |det(A)| が成り立つ。さらには、k = 3 のとき、行および列を入れ替えて、A を行列 Z の e個のコピーの直和の形にすることができて、したがって n = 7e および perm(A) = 24^e となる。

位置の制限（禁止）を含む置換の総数の計算にもパーマネント は利用できる。標準 n元-集合 {1, 2, …, n} に対して、A = (a_ij) を、各 a_ij は素の置換で i → j と写せるならば 1, さもなくば 0 と定めて得られる (0, 1)-行列とするとき、perm(A) は標準 n-元集合上でこれらの制限を全て満たす置換の総数に等しい^[7]:12。このような例としてよく知られた特別の場合が、完全順列問題（不動点を全く持たない場合）とメナージュの問題（英語版）（problème des ménages: 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める）である。完全順列の場合、n元-集合において不動点が一つもない置換の総数は

${\displaystyle \operatorname {perm} (J-I)=\operatorname {perm} \!{\begin{pmatrix}0&1&1&\dots &1\\1&0&1&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&1&1&\dots &0\end{pmatrix}}=n!\textstyle \sum \limits _{i=0}^{n}{\dfrac {(-1)^{i}}{i!}}}$

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

${\displaystyle {\begin{aligned}\operatorname {perm} (J-I-I')&=\operatorname {perm} \!{\begin{pmatrix}0&0&1&\dots &1\\1&0&0&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&1&1&\dots &0\end{pmatrix}}\\&=\textstyle \sum \limits _{k=0}^{n}(-1)^{k}{\dfrac {2n}{2n-k}}{\dbinom {2n-k}{k}}(n-k)!\end{aligned}}}$

で与えられる。ただし、I' は (i, i + 1)成分および (n, 1)成分のみが非零である (0, 1)-行列とする。

上界

ブレグマン–ミンク不等式（英語版）（H. Minc (1963)^[10]で予想され、ブレグマン（英語版）が1973年に証明した^[5]:101）は n次 (0, 1)-行列の上界を与える。

定理 (Bregman–Minc inequality)

各 1 ≤ i ≤ n に対して、A の第 i行には r_i個の 1 があるものとするとき、

${\displaystyle \operatorname {perm} A\leq \textstyle \prod \limits _{i=1}^{n}(r_{i})!^{\tfrac {1}{r_{i}}}}$

が成り立つ。

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

Van der Waerden (1926) はn次二重確率行列の中で最小のパーマネントは n!/nⁿ で、それは全ての成分が 1/n に等しい行列によって達成されると予想した^[11]。この予想の証明は、(B. Gyires 1980)^[12] および (G. P. Egorychev 1980, 1981)^[13][14] および (D. I. Falikman 1981)^[15]として出版された。Egorychev の証明はアレクサンドロフ–フェンケル不等式（英語版）の一つの応用である^[16]。この業績により Egorychev と Falikman はファルカーソン賞を1982年に受賞している^[17]。

計算

→詳細は「パーマネントの計算（英語版）」および「01値パーマネントの♯P完全性（英語版）」を参照

定義通りに素朴にパーマネントを計算しようとすれば、比較的小さい行列に対してさえ計算量的に不可能である。知られている最も速いアルゴリズムの一つは H. J. Ryser (1963) による包除原理に基づいたRyser法（英語版）で、以下のように与えられる^[5]:99:

主張

A_k は A から k 個の列を取り除いて得られる任意の行列とする。P(A_k) は A_k の行和の総乗とし、A_k として考え得る全ての行列に亙って P(A_k) を加えた和を Σ_k と書けば、

${\displaystyle \operatorname {perm} (A)=\textstyle \sum \limits _{k=0}^{n-1}(-1)^{k}\Sigma _{k}}$

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

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

パーマネントの計算は行列式の場合に比べて複雑になると信じられている（例えば、行列式はガウスの消去法を用いて多項式時間で計算できるが、パーマネントはガウス消去では計算できない）。もっと言えば、(0, 1)-行列のパーマネントの計算は#P完全（英語版）である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、FP（英語版） = #P となるが、これは P = NP よりもいっそう強い主張である。しかし、A の成分が全て非負の場合、パーマネントは確率的多項式時間で近似的に計算することができる（その誤差は、パーマネントの値 M と任意の ε > 0 に対する εM に関するオーダーでとる）^[18]。半正定値行列のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる（この近似で達成可能な最良の誤差は ε√M である。M はやはりパーマネントの値とする）^[19]。

マクマホンの基本定理

→詳細は「マクマホンの基本定理（英語版）」を参照

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

${\displaystyle F(x_{1},x_{2},\dotsc ,x_{n}):=\textstyle \prod \limits _{i=1}^{n}{\biggl (}\sum \limits _{j=1}^{n}a_{ij}x_{j}{\biggr )}={\biggl (}\sum \limits _{j=1}^{n}a_{1j}x_{j}{\biggr )}{\biggl (}\sum \limits _{j=1}^{n}a_{2j}x_{j}{\biggr )}\cdots {\biggl (}\sum \limits _{j=1}^{n}a_{nj}x_{j}{\biggr )}}$

を考えると、F(x₁, x₂, …, x_n) における ${\displaystyle x_{1}x_{2}\dots x_{n}}$ の係数は perm(A) に等しい^[7]:14。

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

定義

任意の長さ n の非負整数列 ${\displaystyle s_{1},s_{2},\dotsc ,s_{n}}$ に対して

${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)}$ を ${\displaystyle \left(\textstyle \sum \limits _{j=1}^{n}a_{1j}x_{j}\right)^{s_{1}}\left(\textstyle \sum \limits _{j=1}^{n}a_{2j}x_{j}\right)^{s_{2}}\cdots \left(\textstyle \sum \limits _{j=1}^{n}a_{nj}x_{j}\right)^{s_{n}}}$ における ${\displaystyle {x_{1}}^{s_{1}}{x_{2}}^{s_{2}}\cdots {x_{n}}^{s_{n}}}$ の係数

と定める。

定理 (MacMahon's Master Theorem)

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

「${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)}$ は ${\displaystyle {\frac {1}{\det(I-XA)}}}$ における ${\displaystyle {x_{1}}^{s_{1}}{x_{2}}^{s_{2}}\cdots {x_{n}}^{s_{n}}}$ の係数に等しい」

が成り立つ^[7]:17。ただし、I は n次単位行列で、X は対角成分が (x₁, x₂, …, x_n) である対角行列とする。

矩形行列のパーマネント

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

${\displaystyle \operatorname {perm} (A):=\textstyle \sum \limits _{\sigma \in P(n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\dotsc a_{m\sigma (m)}}$

と定める。ただし、P(n,m) は n元-集合 {1, 2, …, n} から m 元選ぶ部分置換（順列）全体の成す集合である^[6]:25。

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

${\displaystyle \operatorname {perm} (A)=\textstyle \sum \limits _{k=0}^{m-1}(-1)^{k}{\dbinom {n-m+k}{k}}\sigma _{n-m+k}}$

が成り立つ^[6]:26。

完全代表系

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

命題

（相異なるとは限らない）S₁, S₂, …, S_m は n元-集合の部分集合で、m ≤ n とする。この部分集合族の接続行列 A は m × n の (0, 1)-行列である。この族の完全代表系（英語版）（systems of distinct representatives; 相異なる代表系、個別代表系; SDR）総数は perm(A) である^[6]:54。^{[注釈 3]}

関連項目

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