パーマネント (数学)
線型代数学における正方行列のパーマネント(Permanent)は、行列式 (determinant) によく似た行列変数の函数である。パーマネントは、行列式と同様に、行列の成分を変数とする多項式である。Permutation(置換)と determinant(行列式)を合成したカバン語をもじったものである。英単語の「Permanent」から永久式または恒久式と訳されたこともある。中国語の名称は積和式。
パーマネントと行列式はともに、より一般の行列函数イマナントの特別の場合である。
n × n 行列 A coloneqq (ai,j) のパーマネントは \operatorname{perm}(A) := \sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)} で与えられる。右辺の和は、対称群 Sn の任意の元 σ(つまり、番号 1, 2, …, n の置換)に亙ってとるものとする。
例えば、任意の二次正方行列に対して \operatorname{perm}\!\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc であり、任意の三次正方行列に対して \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 などと書く(引数をパーレンで括ることもある)。 は A が矩形行列の場合に Per(A), 正方行列には per(A) と使い分けている。 は \overset{+}〔}\quad \overset{+}〔} で括る記法を用いている。
術語「パーマネント」はもともとはコーシーが1812年に “fonctions symétriques permanentes" として関連する函数の一種に対して用いた。より特定した現代的な意味での使用は  による。
パーマネントを n 本の列(または行)ベクトルを引数にとる写像とみるとき、多重線型対称函数(引数となるベクトルの順番を入れ替えても結果は変わらない)である。より具体的に、A = (aij) が n 次の正方行列であるとき以下が成り立つ:
perm(A) は A の行または列ベクトルに関する任意の置換のもとで不変である。この性質を任意の置換行列 P, Q を用いて perm(A) = perm(PAQ) という形で記号的に表せる。
A の任意の一つの行または列にスカラー s を掛けるとき、perm(A) は s⋅perm(A) に写る。
perm(A) は転置のもとで不変: perm(A) = perm(A⊤).
n-次正方行列 A coloneqq (aij), B coloneqq (bij) に対し \operatorname{perm}(A + B) = \sum_{s,t} \operatorname{perm} (a_{ij})_{i \in s, j \in t} \operatorname{perm} (b_{ij})_{i \in \bar{s}, j \in \bar{t} が成立する。ただし、s, t は 1, 2, …, n の同じサイズの部分集合で、s, t はそれぞれの補集合である。
これと対照に、行列式の基本性質である乗法性はパーマネントでは成り立たない。 \operatorname{perm}\!\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\operatorname{perm}\!\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\\
&\neq \operatorname{perm}\!\Bigl(\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\Bigr) = \operatorname{perm}\!\begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix}= 8.\end{align}
行列式に対するラプラス展開と同様に、パーマネントを行、列または対角線にそって展開することができる(行列式の場合には各余因子に交代符号が付いたが、パーマネントの場合には符号は付かない)。 {} & 1 \cdot \operatorname{perm}\!\begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{pmatrix} + 2\cdot \operatorname{perm}\!\begin{pmatrix}1&1&1\\0&1&0\\0&0&1\end{pmatrix}\\
& {} + \ 3\cdot \operatorname{perm}\!\begin{pmatrix}1&1&1\\1&0&0\\0&0&1\end{pmatrix} + 4 \cdot \operatorname{perm}\!\begin{pmatrix}1&1&1\\1&0&0\\0&1&0\end{pmatrix}\\
= {} & 1(1) + 2(1) + 3(1) + 4(1) = 10, \end{align} あるいは最終行に沿った展開: \begin{align}\operatorname{perm}\!\begin{pmatrix} 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end{pmatrix}
= {} & 4 \cdot \operatorname{perm}\!\begin{pmatrix}1&1&1\\1&0&0\\0&1&0\end{pmatrix} + 0\cdot \operatorname{perm}\!\begin{pmatrix}1&1&1\\2&0&0\\3&1&0\end{pmatrix}\\
& {} + \ 0\cdot \operatorname{perm}\!\begin{pmatrix}1&1&1\\2&1&0\\3&0&0\end{pmatrix} +
1 \cdot \operatorname{perm}\!\begin{pmatrix} 1&1&1\\ 2&1&0\\ 3&0&1\end{pmatrix}\\
= {} & 4(1) + 0 + 0 + 1(6) = 10.\end{align}
行列式の場合とは違い、パーマネントは平易な幾何学的解釈はない。主な応用先として、組合せ論、量子力学におけるボソンのグリーン関数の扱いにおいて、およびボソンサンプリングシステムの状態可能性の決定においてなどがある。ただし、2種類のグラフ理論的解釈をもつ(有向グラフの点閉路被覆の重み付き和、および二部グラフにおける完全マッチングの重み付き和)。
パーマネントはヒルベルト空間上の対称テンソル冪の研究において自然に生じてくる。具体的に、H をヒルベルト空間とし、その対称テンソル全体の成す空間である対称テンソル冪を \bigvee^k H と書くと、特に \bigvee^k H は H の元からなる対称(テンソル)積によって生成されることに注意する。x1, x2, …, xk ∈ H の対称積は  x_1 \vee x_2 \vee \cdots \vee x_k
:= (k!)^{-1/2} \sum_{\sigma \in S_k} x_{\sigma(1)} \otimes x_{\sigma(2)} \otimes \cdots \otimes x_{\sigma(k)}
と定義される。\bigvee^k H を(H の k-次ヒルベルト空間のテンソル積 \bigotimes^k H の部分空間として)考えるとき、その上に内積 , が定義されれば、それに応じて \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\le i,j\le k})\qquad (x_j,y_j \in H) となることが分かる。コーシー–シュヴァルツの不等式を適用すれば、\operatorname{perm}((\langle x_i,x_j \rangle)_{1\le i,j\le k}) \geq 0 および \Bigl|\operatorname{perm}((\langle x_i,y_j \rangle)_{1\le i,j\le k})\Bigr|^2 \leq
\operatorname{perm}((\langle x_i,x_j \rangle)_{1\le i,j\le k}) \cdot
\operatorname{perm}((\langle y_i,y_j \rangle)_{1\le i,j\le k})
が確かめられる。
任意の正方行列 A coloneqq (aij) は適当な重み付き有向グラフの隣接行列と見なすことができて、各 aij は頂点 i から j へ結ぶ弧の重み付けを表す。
重み付き有向グラフの点閉路被覆とは、その有向グラフの点素 (vertex-disjoint) な有向閉路のあつまりで、グラフのすべての頂点を被覆するものを言う。このとき、有向グラフの各頂点 i は、その閉路被覆において一意的な「後続点」σ(i) を持ち、σ は 1, 2, …, n(n はグラフの頂点数)の置換となる。逆に、1, 2, …, n 上の任意の置換 σ は、各 i に対して頂点 i から σ(i) へ結ぶ弧がある閉路被覆に対応する。
「閉路被覆の重み」を各閉路における重みの総乗と定めるならば、\operatorname{weight}(\sigma) := \prod_{i=1}^n a_{i,\sigma(i)} と書ける。n × n 行列 A のパーマネントの定義 \operatorname{perm}(A) = \sum_\sigma \prod_{i=1}^n a_{i,\sigma(i)}(σ は 1, 2, …, n 上の置換)と比較すれば、隣接行列 A のパーマネントが、対応する有向グラフの閉路被覆すべてに亙る重み付き和に等しいことが分かる。
任意の正方行列 A coloneqq (aij) を、頂点集合 x1, x2, xn および y1, y2, …, yn を持つ二部グラフで、頂点 xi から頂点 yj へ結んだ辺の重みが aij であるようなものの隣接行列と見ることもできる。xi を yj にマッチさせる 完全マッチング σ の重みを、このマッチングに現れる辺すべての重みの総乗と定義するならば \operatorname{weight}(\sigma) := \prod_{i=1}^n a_{i,\sigma(i)} と書けるから、A のパーマネントはこの二部グラフの完全マッチングすべてに亙る重み付き和に等しいことがわかる。
多くの数え上げ問題に 0 と 1 のみを成分とする行列のパーマネントを計算することで答えることができる。
Ω(n,k) は n-次 (0, 1)-値の行列で各行各列の成分の和が k に等しいもの全体の成すクラスとする。このクラスに属する任意の行列 A は perm(A) > 0 である。射影平面の接続行列は、適当な整数 n > 1 に対するクラス Ω(n2 + n + 1, n + 1) に属する。最小の射影平面に対応するパーマネントは計算されており、n = 2, 3, 4 に対してその値はそれぞれ 24, 3852, 18,534,400 となる。n = 2 のときの射影平面(ファノ平面と呼ばれる)の接続行列を Z とすると、特筆すべきことに perm(Z) = 24 = det(Z) が成り立っている(右辺は Z の行列式の絶対値の意味である)。これは Z が巡回行列であることと、以下の定理からの帰結である。
A がクラス Ω(n,k) に属する巡回行列ならば、k > 3 のとき、perm(A) > det (A) であり、k = 3 のとき perm(A) = det(A) が成り立つ。さらには、k = 3 のとき、行および列を入れ替えて、A を行列 Z の e 個のコピーの直和の形にすることができて、したがって n = 7e および perm(A) = 24e となる。
位置の制限(禁止)を含む置換の総数の計算にもパーマネント は利用できる。標準 n-元集合 1, 2, …, n に対して、A = (aij) を、各 aij は素の置換で i → j と写せるならば 1, さもなくば 0 と定めて得られる (0, 1)-行列とするとき、perm(A) は標準 n-元集合上でこれらの制限をすべて満足する置換の総数に等しい。このような例としてよく知られた特別の場合が、完全順列問題(不動点を全く持たない場合)とメナージュの問題(problème des ménages: 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める)である。完全順列の場合、n-元集合において不動点が一つもないような置換の総数は \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! \sum_{i=0}^n \frac{(-1)^i}{i!} で与えられる。ただし J は全ての成分が 1 の n × n 行列で、I は n-次単位行列である。いっぽう、メナージュ問題の場合の数(メナージュ数)は \begin{align}\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}\\
&= \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!
\end{align} で与えられる。ただし、I′ は (i, i + 1)-成分および (n, 1)-成分のみが非零であるような (0, 1)-行列とする。
ブレグマン–ミンク不等式(で予想され、レフ・M・ブレグマンが1973年に証明した)は n-次 (0, 1)-行列の上界を与える。
定理 (Bregman–Minc inequality)
各 1 ≤ i ≤ n に対して、A の第 i-行には ri 個の 1 があるものとするとき、\operatorname{perm} A \leq \prod_{i=1}^n (r_i)!^{1/r_i} が成り立つ。
はn × n 二重確率行列の中で最小のパーマネントは n!/nn で、それは全ての成分が 1/n に等しい行列によって達成されると予想した。この予想の証明は、 および  および として出版された。Egorychev の証明はアレクサンドロフ–フェンケル不等式の一つの応用である。この業績により Egorychev と Falikman はファルカーソン賞を1982年に受賞している。
定義通りに素朴にパーマネントを計算しようとすれば、比較的小さい行列に対してさえ計算量的に不可能である。知られている最も速いアルゴリズムの一つは  による包除原理に基づいたRyserの公式で、以下のように与えられる:
主張: Ak は A から k 個の列を取り除いて得られる任意の行列とする。P(Ak) は Ak の行和の総乗とし、Ak として考え得るすべての行列に亙って P(Ak) を加えた和を Σk と書けば、\operatorname{perm}(A)=\sum_{k=0}^{n-1} (-1)^{k}\Sigma_k が成り立つ。あるいはこれを行列の成分を陽に出して書けば \operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\} (-1)^ \prod_{i=1}^n \sum_{j\in S} a_{ij} と書ける。
パーマネントの計算は行列式の場合に比べて複雑になると信じられている(例えば、行列式はガウスの消去法を用いて多項式時間で計算できるが、パーマネントはガウス消去では計算できない)。もっと言えば、(0, 1)-行列のパーマネントの計算はシャープP完全である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、FP (計算量) = #P となるが、これは P  NP よりもいっそう強い主張である。しかし、A の成分がすべて非負の場合、パーマネントは確率的多項式時間で近似的に計算することができる(その誤差は、パーマネントの値 M と任意の ε > 0 に対する εM に関するオーダーでとる)。半正定値行列のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる(この近似で達成可能な最良の誤差は εM である。M はやはりパーマネントの値とする)。
パーマネントを多変数母函数を通じて解釈する視点もある。n-次正方行列 A = (aij) に対して、多変数母函数 F(x_1,x_2,\dotsc,x_n) := \prod_{i=1}^n \biggl(\sum_{j=1}^n a_{ij} x_j\biggr) = \biggl(\sum_{j=1}^n a_{1j} x_j\biggr)\biggl(\sum_{j=1}^n a_{2j} x_j\biggr)\cdots \biggl(\sum_{j=1}^n a_{nj} x_j\biggr) を考えると、F(x1, x2, …, xn) における x_1 x_2 \dots x_n の係数は perm(A) に等しい。
このことの一般化として、
定義: 任意の長さ n の非負整数列 s_1,s_2,\dotsc,s_n に対して \operatorname{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): パーマネントと行列式の間の関係として、「\operatorname{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} の係数に等しい」が成り立つ。ただし、I は n-次単位行列で、X は対角成分が (x1, x2, …, xn) である対角行列とする。
パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合とみるものがある。具体的には、m × n 行列 A = (aij) で m ≤ n とするとき、\operatorname{perm}(A) := \sum_{\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 元選ぶ部分置換(順列)全体の成す集合である。
パーマネントに対するRyserの計算論的結果も一般化できる。A が m × n 行列 (m ≤ n) のとき、A から k 個の列を取り除いて Ak が得られるとすると、Ak の行和の積を P(Ak), 可能なすべての Ak に対する P(Ak) の総和を σk と書けば、\operatorname{perm}(A) = \sum_{k=0}^{m-1} (-1)^{k}\binom{n-m+k}{k}\sigma_{n-m+k} が成り立つ。
矩形行列に対してパーマネントの定義を一般化することで、いくつかの応用においてはより自然な方法でこれをもちいることができるようになる。例えば:
命題:(相異なるとは限らない)S1, S2, …, Sm は n-元集合の部分集合で、m ≤ n とする。この部分集合族の接続行列 A は m × n の (0, 1)-行列である。この族の横断 (組合せ論) (systems of distinct representatives; 相異なる代表系、個別代表系; SDR) の総数は perm(A) である。ホールの結婚定理も参照