パーマネント (数学)のソースを表示

[[線型代数学]]における[[正方行列]]の'''パーマネント'''（{{lang-en-short|Permanent}}）は、[[行列式]] (determinant) によく似た{{ill2|行列変数の函数|en|matrix function}}である。パーマネントは、行列式と同様に、行列の成分を変数とする多項式である<ref>{{Cite journal |author=Marcus, Marvin |author2=Minc, Henryk |title=Permanents |journal=Amer. Math. Monthly |volume=72 |year=1965 |pages=577-591 |url=https://www.maa.org/programs/maa-awards/writing-awards/permanents |doi=10.2307/2313846}}</ref>。Permutation（置換）と determinant（行列式）を合成した[[カバン語]]をもじったものである。英単語の「Permanent」から'''永久式'''<ref>{{Cite journal|和書 |author=李磊、友田敏章、緑川章一、堀端孝俊 |title=制限付き占有問題の簡単な計数公式 |journal=日本応用数理学会論文誌 |year=1997 |volume=7 |issue=4 |pages=321-331 |doi=10.11540/jsiamt.7.4_321}}</ref>または'''恒久式'''<ref>{{Cite journal |url=http://math.shinshu-u.ac.jp/~maekawa/wakate2014/proceedings/tabata_proceedings.pdf |title=Immanant不等式とImmanantal Polynomials |author=田端亮 |series=[http://math.shinshu-u.ac.jp/~maekawa/wakate2014/ 第19回代数若手研究会 報告書] |year=2014 |format=PDF}}</ref>と訳されたこともある。

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

== 定義 ==
{{mvar|n}}次正方行列 {{math2|''A'' {{coloneqq}} (''a{{sub|i,j}}'')}} のパーマネントは
:<math>\operatorname{perm}(A) := \textstyle\sum\limits_{\sigma\in S_n} \prod\limits_{i=1}^n a_{i,\sigma(i)}</math>
で与えられる。右辺の和は、[[対称群]] {{mvar|S{{sub|n}}}} の任意の元 {{mvar|σ}}（つまり、番号 {{math2|1, 2, …, ''n''}} の[[置換 (数学)|置換]]）に亙ってとるものとする。

例えば、二次[[正方行列]]に対しては
:<math>\operatorname{perm}\!\begin{pmatrix}
a &b \\
c &d
\end{pmatrix}=ad+bc</math>
であり、三次正方行列に対しては
:<math>\operatorname{perm}\!\begin{pmatrix}a&b&c \\ d&e&f \\ g&h&i \end{pmatrix}=aei + bfg + cdh + ceg + bdi + afh</math>
となる。

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

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

術語「パーマネント」は元々は[[オーギュスタン＝ルイ・コーシー|コーシー]]が1812年に “fonctions symétriques permanentes” として関連する函数の一種に対して用いた<ref>{{Citation |last=Cauchy |first=A. L. |title=Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment. |url=https://gallica.bnf.fr/ark:/12148/bpt6k90193x/f97 |journal=Journal de l'École Polytechnique |volume=10 |pages=91–169 |year=1815}}</ref>。より特定した現代的な意味での使用は {{harvtxt|Muir|1882}} による{{sfn|van Lint|Wilson|2001}}{{rp|108}}。

== 性質 ==
パーマネントを {{mvar|n}}本の列（または行）ベクトルを引数にとる写像と見るとき、[[多重線型写像|多重線型]]{{ill2|対称函数|en|Symmetric function|label=対称形式}}（引数となるベクトルの順番を入れ替えても結果は変わらない）である。より具体的に、{{mvar|n}}次[[正方行列]] {{math|1=''A'' = (''a{{sub|ij}}'')}} に対して以下が成り立つ{{sfn|Ryser|1963}}{{rp|25-26}}：
* {{math|perm(''A'')}} は {{mvar|A}} の行または列ベクトルに関する任意の置換の下で不変である。この性質を任意の[[置換行列]] {{math2|''P'', ''Q''}} を用いて {{math2|1=perm(''A'') = perm(''PAQ'')}} という形で記号的に表せる。
* {{mvar|A}} の任意の一つの行または列に[[スカラー (数学)|スカラー]] {{mvar|s}} を掛けるとき、{{math|perm(''A'')}} は {{math|''s''⋅perm(''A'')}} に写る。
* {{math|perm(''A'')}} は[[転置行列|転置]]の下で不変：{{math|1=perm(''A'') = perm(''A''{{sup|⊤}})}}.

{{mvar|n}}次正方行列 {{math2|''A'' {{coloneqq}} (''a{{sub|ij}}''), ''B'' {{coloneqq}} (''b{{sub|ij}}'')}} に対し
:<math>\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}}</math>
が成立する{{sfn|Percus|1971}}{{rp|2}}。ただし、{{math2|''s'', ''t''}} は {{math2|{{mset|1, 2, …, ''n''}}}} の同じサイズの部分集合で、{{math2|{{overline|''s''}}, {{overline|''t''}}}} はそれぞれの補集合である。

これと対照に、行列式の基本性質である乗法性はパーマネントでは成り立たない{{sfn|Ryser|1963}}{{rp|26}}{{efn|簡単な例を以下に示す:
: <math>\begin{align}
4 &= \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}</math>}}。

行列式に対する[[ラプラス展開]]と同様に、パーマネントを行、列または対角線にそって展開することができる{{sfn|Percus|1971}}{{rp|12}}（行列式の場合には各余因子に交代符号が付いたが、パーマネントの場合には符号は付かない）。{{efn|例えば、第一列に沿った展開：
:<math>\begin{align}
\operatorname{perm}\!\begin{pmatrix}
  1 &1 &1 &1 \\
  2 &1 &0 &0 \\
  3 &0 &1 &0 \\
  4 &0 &0 &1
\end{pmatrix} = {} &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}</math>
あるいは最終行に沿った展開：
:<math>\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}</math>}}

== 応用 ==
行列式の場合とは違い、パーマネントは平易な幾何学的解釈はない。主な応用先として、[[組合せ数学|組合せ論]]、[[量子力学]]におけるボソンの[[グリーン関数 (多体理論)|グリーン関数]]の扱いにおいて、および{{ill2|ボソンサンプリング|en|Boson sampling}}システムの状態可能性の決定において<ref>{{Cite arXiv |last=Aaronson |first=Scott |date=14 Nov 2010 |title=The Computational Complexity of Linear Optics |eprint=1011.3245}}</ref>などがある。ただし、2種類の[[グラフ理論]]的解釈をもつ（[[有向グラフ]]の{{ill2|点閉路被覆|en|Vertex cycle cover|label=閉路被覆}}の重み付き和、および[[二部グラフ]]における完全マッチングの重み付き和）。

=== 対称テンソル ===
パーマネントは[[ヒルベルト空間]]上の対称テンソル冪の研究において自然に生じてくる<ref>{{Cite book |last1=Bhatia |first1=Rajendra |title=Matrix Analysis |year=1997 |publisher=Springer-Verlag |location=New York |isbn=0-387-94846-5 |pages=16-19}}</ref>。具体的に、{{mvar|H}} をヒルベルト空間とし、その[[対称テンソル]]全体の成す空間である対称テンソル冪を <math>\bigvee^k H</math> と書くと、特に <math>\bigvee^k H</math> は {{mvar|H}} の元からなる対称（テンソル）積によって生成されることに注意する。{{math2|''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|k}}'' ∈ ''H''}} の対称積は
:<math>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)}</math>
と定義される。<math>\bigvee^k H</math> を（{{mvar|H}} の {{mvar|k}}次{{ill2|ヒルベルト空間のテンソル積|en|Tensor product of Hilbert spaces|label=テンソル冪}} <math>\bigotimes^k H</math> の部分空間として）考えるとき、その上に内積 {{math|{{angbr|,}}}} が定義されれば、それに応じて
:<math>\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)</math>
となることが分かる。[[コーシー＝シュワルツの不等式]]を適用すれば、<math>\operatorname{perm}((\langle x_i,x_j \rangle)_{1\le i,j\le k}) \geq 0</math> および
:<math>\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})</math>
が確かめられる。

=== 閉路被覆 ===
任意の正方行列 {{math2|''A'' {{coloneqq}} (''a{{sub|ij}}'')}} は適当な重み付き有向グラフの[[隣接行列]]と見なすことができて、各 {{mvar|a{{sub|ij}}}} は頂点 {{mvar|i}} から {{mvar|j}} へ結ぶ弧の重み付けを表す。
重み付き有向グラフの{{ill2|点閉路被覆|en|Vertex cycle cover|label=閉路被覆}}とは、その有向グラフの点素 (vertex-disjoint) な[[有向閉路]]の集まりで、グラフの全ての頂点を被覆するものをいう。このとき、有向グラフの各頂点 {{mvar|i}} は、その閉路被覆において一意的な「後続点」{{math|''σ''(''i'')}} を持ち、{{mvar|σ}} は {{math2|{{mset|1, 2, …, ''n''}}}}（{{mvar|n}} はグラフの頂点数）の[[置換 (数学)|置換]]となる。逆に、{{math2|{{mset|1, 2, …, ''n''}}}} 上の任意の置換 {{mvar|σ}} は、各 {{mvar|i}} に対して頂点 {{mvar|i}} から {{math|''σ''(''i'')}} へ結ぶ弧がある閉路被覆に対応する。

「閉路被覆の重み」を各閉路における重みの総乗と定めるならば、
:<math>\operatorname{weight}(\sigma) := \textstyle\prod\limits_{i=1}^n a_{i,\sigma(i)}</math>
と書ける。{{mvar|n}}次正方行列 {{mvar|A}} のパーマネントの定義
:<math>\operatorname{perm}(A) = \textstyle\sum\limits_\sigma \prod\limits_{i=1}^n a_{i,\sigma(i)}</math>
（{{mvar|σ}} は {{math2|{{mset|1, 2, …, ''n''}}}} 上の置換）と比較すれば、隣接行列 {{mvar|A}} のパーマネントが、対応する有向グラフの閉路被覆全てに亙る重み付き和に等しいことが分かる。

=== 完全マッチング ===
正方行列 {{math2|''A'' {{coloneqq}} (''a{{sub|ij}}'')}} を、頂点集合 {{math2|{{mset|''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|n}}''}}}} および {{math2|{{mset|''y''{{sub|1}}, ''y''{{sub|2}}, …, ''y{{sub|n}}''}}}} を持つ[[二部グラフ]]で、頂点 {{mvar|x{{sub|i}}}} から頂点 {{mvar|y{{sub|j}}}} へ結んだ辺の重みが {{mvar|a{{sub|ij}}}} であるものの[[隣接行列]]と見ることもできる。{{mvar|x{{sub|i}}}} を {{mvar|y{{sub|j}}}} にマッチさせる {{ill2|完全マッチング|en|perfect matching}} {{mvar|σ}} の重みを、このマッチングに現れる辺全ての重みの総乗と定義するならば
:<math>\operatorname{weight}(\sigma) := \textstyle\prod\limits_{i=1}^n a_{i,\sigma(i)}</math>
と書けるから、{{mvar|A}} のパーマネントはこの二部グラフの完全マッチング全てに亙る重み付き和に等しいことが分かる。

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

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

位置の制限（禁止）を含む[[置換 (数学)|置換]]の総数の計算にもパーマネント は利用できる。標準 {{mvar|n}}元-集合 {{math2|{{mset|1, 2, …, ''n''}}}} に対して、{{math|1=''A'' = (''a{{sub|ij}}'')}} を、各 {{mvar|a{{sub|ij}}}} は素の置換で {{math2|''i'' → ''j''}} と写せるならば {{math|1}}, さもなくば {{math|0}} と定めて得られる {{math|(0, 1)}}-行列とするとき、{{math|perm(''A'')}} は標準 {{mvar|n}}-元集合上でこれらの制限を全て満たす置換の総数に等しい{{sfn|Percus|1971}}{{rp|12}}。このような例としてよく知られた特別の場合が、[[完全順列]]問題（不動点を全く持たない場合）と{{ill2|メナージュの問題|en|ménage problem}}（''problème des ménages'': 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める）である。完全順列の場合、{{mvar|n}}元-集合において不動点が一つもない置換の総数は
:<math>\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!}</math>
で与えられる。ただし {{mvar|J}} は全ての成分が {{math|1}} の {{mvar|n}}次正方行列で、{{mvar|I}} は {{mvar|n}}次単位行列である。一方、メナージュ問題の場合の数（{{ill2|メナージュ数|en|ménage number}}）は
:<math>\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} \\
  &= \textstyle\sum\limits_{k=0}^n (-1)^k \dfrac{2n}{2n-k} \dbinom{2n-k}{k} (n-k)!
\end{align}</math>
で与えられる。ただし、{{mvar|I'}} は {{math|(''i'', ''i'' + 1)}}成分および {{math|(''n'', 1)}}成分のみが非零である {{math|(0, 1)}}-行列とする。

=== 上界 ===
{{ill2|ブレグマン&ndash;ミンク不等式|en|Bregman–Minc inequality}}（{{harvs|txt |first=H.|last=Minc |year=1963}}<ref>{{Citation |first=Henryk |last=Minc |title=Upper bounds for permanents of (0,1)-matrices |journal=Bulletin of the American Mathematical Society |volume=69|year=1963 |pages=789-791 |doi=10.1090/s0002-9904-1963-11031-9 |ref=harv}}</ref>で予想され、{{ill2|レフ・M・ブレグマン|en|Lev M Bregman|label=ブレグマン}}が1973年に証明した{{sfn|van Lint|Wilson|2001}}{{rp|101}}）は {{mvar|n}}次 {{math|(0, 1)}}-行列の上界を与える。

;定理 (Bregman–Minc inequality)
:各 {{math2|1 ≤ ''i'' ≤ ''n''}} に対して、{{mvar|A}} の第 {{mvar|i}}行には {{mvar|r{{sub|i}}}}個の {{math|1}} があるものとするとき、
:<math>\operatorname{perm} A \leq \textstyle\prod\limits_{i=1}^n (r_i)!^{\tfrac{1}{r_i}}</math>
が成り立つ。

== ファンデルヴェルデンの予想 ==
{{harvtxt|Van der Waerden|1926}} は{{mvar|n}}次[[二重確率行列]]の中で最小のパーマネントは {{math|''n''!/''n{{sup|n}}''}} で、それは全ての成分が {{math|{{sfrac|1|''n''}}}} に等しい行列によって達成されると予想した<ref>{{Citation |last=van der Waerden |first=B. L. |authorlink=Bartel Leendert van der Waerden |journal=Jber. Deutsch. Math.-Verein. |page=117 |title=Aufgabe 45 |volume=35 |year=1926 |ref=harv}}.</ref>。この予想の証明は、{{harvs |first=B. |last=Gyires |year=1980}}<ref>{{Citation |last=Gyires |first=B. |issue=3-4 |journal=Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis |mr=604006 |pages=291–304 |title=The common source of several inequalities concerning doubly stochastic matrices |volume=27 |year=1980}}.</ref> および {{harvs |first=G. P. |last=Egorychev |year1=1980 |year2=1981}}<ref>{{Citation |last=Egoryčev |first=G. P. |language=Russian |location=Krasnoyarsk |mr=602332 |page=12 |publisher=Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz. |title=Reshenie problemy van-der-Vardena dlya permanentov |year=1980}}. {{Citation |last=Egorychev |first=G. P. |issue=6 |journal=Akademiya Nauk SSSR |language=Russian |mr=638007 |pages=65–71, 225 |title=Proof of the van der Waerden conjecture for permanents |volume=22 |year=1981 |ref=harv}}</ref><ref>{{Citation |last=Egorychev |first=G. P. |doi=10.1016/0001-8708(81)90044-X |issue=3 |journal=Advances in Mathematics |mr=642395 |pages=299-305 |title=The solution of van der Waerden's problem for permanents |volume=42 |year=1981 |ref=harv}}.</ref> および {{harvs |first=D. I. |last=Falikman |year=1981}}<ref>{{Citation |last=Falikman |first=D. I. |issue=6 |journal=Akademiya Nauk Soyuza SSR |language=Russian |mr=625097 |pages=931-938, 957 |title=Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix |volume=29 |year=1981 |ref=harv}}.</ref>として出版された。Egorychev の証明は{{ill2|アレクサンドロフ&ndash;フェンケル不等式|en|Alexandrov&ndash;Fenchel inequality}}の一つの応用である{{sfn|Brualdi|2006|p=487}}。この業績により Egorychev と Falikman は[[ファルカーソン賞]]を1982年に受賞している<ref>[http://www.mathopt.org/?nav=fulkerson Fulkerson Prize], Mathematical Optimization Society, retrieved 2012-08-19.</ref>。

== 計算 ==
{{main|{{ill2|パーマネントの計算|en|Computing the permanent}}|{{ill2|01値パーマネントの♯P完全性|en|Sharp-P-completeness of 01-permanent}}}}
定義通りに素朴にパーマネントを計算しようとすれば、比較的小さい行列に対してさえ計算量的に不可能である。知られている最も速いアルゴリズムの一つは {{harvs|txt |first=H. J. |last=Ryser |authorlink=H. J. Ryser |year=1963 |page=27}} による[[包除原理]]に基づいた{{ill2|Ryserの公式|en|Ryser's formula|label=Ryser法}}で、以下のように与えられる{{sfn|van Lint|Wilson|2001}}{{rp|{{google books quote|id=5l5ps2JkyT0C|pg=PA108|text=permanent+ryser|99}}}}:

;主張
:{{mvar|A{{sub|k}}}} は {{mvar|A}} から {{mvar|k}} 個の列を取り除いて得られる任意の行列とする。{{math|''P''(''A{{sub|k}}'')}} は {{mvar|A{{sub|k}}}} の行和の総乗とし、{{mvar|A{{sub|k}}}} として考え得る全ての行列に亙って {{math|''P''(''A{{sub|k}}'')}} を加えた和を {{math|Σ{{sub|''k''}}}} と書けば、
:<math>\operatorname{perm}(A)= \textstyle\sum\limits_{k=0}^{n-1} (-1)^k \Sigma_k</math>
が成り立つ。あるいはこれを行列の成分を陽に出して書けば
:<math>\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}</math> と書ける。

パーマネントの計算は行列式の場合に比べて複雑になると信じられている（例えば、行列式は[[ガウスの消去法]]を用いて[[多項式時間]]で計算できるが、パーマネントはガウス消去では計算できない）。もっと言えば、{{math|(0, 1)}}-行列のパーマネントの計算は{{ill2|シャープP完全|en|sharp-P-complete|label=#P完全}}である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、'''{{nowrap|1={{ill2|FP (計算量)|en|FP (complexity)|label=FP}} = [[＃P|#P]]}}''' となるが、これは [[P≠NP予想|{{nowrap|P {{=}} NP}}]] よりもいっそう強い主張である。しかし、{{mvar|A}} の成分が全て非負の場合、パーマネントは[[確率的アルゴリズム|確率的]]多項式時間で[[近似アルゴリズム|近似的に]]計算することができる（その誤差は、パーマネントの値 {{mvar|M}} と任意の {{math2|''ε'' > 0}} に対する {{mvar|εM}} に関するオーダーでとる）<ref>{{Citation |last1=Jerrum |first1=M. |author1-link=Mark Jerrum |last2=Sinclair |first2=A. |author2-link=Alistair Sinclair |last3=Vigoda |first3=E. |title=A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries |journal=[[Journal of the ACM]] |year=2004 |volume=51 |pages=671-697 |doi=10.1145/1008731.1008738}}</ref>。[[半正定値行列]]のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる（この近似で達成可能な最良の誤差は {{math|''ε''{{sqrt|''M''}}}} である。{{mvar|M}} はやはりパーマネントの値とする）<ref>{{Cite journal |last1=Chakhmakhchyan |first1=Levon |last2=Cerf |first2=Nicolas |last3=Garcia-Patron |first3=Raul |title=A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices |journal=Phys. Rev. A |volume=96 |issue=2 |page=022329 |doi=10.1103/PhysRevA.96.022329 |year=2017 |bibcode=2017PhRvA..96b2329C |arxiv=1609.02416}}</ref>。

== マクマホンの基本定理 ==
{{main|{{ill2|マクマホンの基本定理|en|MacMahon Master theorem}}}}
パーマネントを多変数[[母函数]]を通じて解釈する視点もある。{{mvar|n}}次正方行列 {{math|1=''A'' = (''a{{sub|ij}}'')}} に対して、多変数母函数
:<math>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)</math>
を考えると、{{math2|''F''(''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|n}}'')}} における <math>x_1 x_2 \dots x_n</math> の係数は {{math|perm(''A'')}} に等しい{{sfn|Percus|1971}}{{rp|14}}。

このことの一般化として、
;定義
:任意の長さ {{mvar|n}} の非負整数列 <math>s_1,s_2,\dotsc,s_n</math> に対して <div style="margin:1ex 2em"><math>\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A)</math> を <math>\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}</math> における <math>{x_1}^{s_1} {x_2}^{s_2} \cdots {x_n}^{s_n}</math> の係数</div>と定める。

; 定理 (MacMahon's Master Theorem)
: パーマネントと行列式の間の関係として、<div style="margin:1ex 2em">「<math>\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A)</math> は <math>\frac{1}{\det(I - XA)}</math> における <math>{x_1}^{s_1} {x_2}^{s_2} \cdots {x_n}^{s_n}</math> の係数に等しい」</div>が成り立つ{{sfn|Percus|1971}}{{rp|17}}。ただし、{{mvar|I}} は {{mvar|n}}次単位行列で、{{mvar|X}} は対角成分が {{math2|(''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|n}}'')}} である対角行列とする。

== {{vanc|矩形行列のパーマネント|矩形行列のパーマネント}} ==
パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合と見るものがある<ref>特に {{harvtxt|Minc|1984}} や {{harvtxt|Ryser|1963}} ではそうなっている。</ref>。具体的には、{{math2|''m'' × ''n''}} 行列 {{math2|1=''A'' = (''a{{sub|ij}}'')}} で {{math2|''m'' ≤ ''n''}} とするとき、
:<math>\operatorname{perm}(A) := \textstyle\sum\limits_{\sigma \in P(n,m)} a_{1 \sigma(1)} a_{2 \sigma(2)} \dotsc a_{m \sigma(m)}</math>
と定める。ただし、{{math|''P''(''n'',''m'')}} は {{mvar|n}}元-集合 {{math2|{{mset|1, 2, …, ''n''}}}} から {{mvar|m}} 元選ぶ部分置換（[[順列]]）全体の成す集合である{{sfn|Ryser|1963}}{{rp|25}}。

パーマネントに対するRyserの計算論的結果も一般化できる。{{mvar|A}} が {{math|''m'' × ''n''}} 行列 ({{math2|''m'' ≤ ''n''}}) のとき、{{mvar|A}} から {{mvar|k}} 個の列を取り除いて {{mvar|A{{sub|k}}}} が得られるとすると、{{mvar|A{{sub|k}}}} の行和の積を {{math|''P''(''A{{sub|k}}'')}}, 可能な全ての {{mvar|A{{sub|k}}}} に対する {{math|''P''(''A{{sub|k}}'')}} の総和を {{mvar|σ{{sub|k}}}} と書けば、
:<math>\operatorname{perm}(A) = \textstyle\sum\limits_{k=0}^{m-1} (-1)^k \dbinom{n-m+k}{k} \sigma_{n-m+k}</math>
が成り立つ{{sfn|Ryser|1963}}{{rp|26}}。

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

; 命題:（相異なるとは限らない）{{math2|''S''{{sub|1}}, ''S''{{sub|2}}, …, ''S{{sub|m}}''}} は {{mvar|n}}元-集合の部分集合で、{{math2|''m'' ≤ ''n''}} とする。この部分集合族の[[接続行列]] {{mvar|A}} は {{math2|''m'' × ''n''}} の {{math2|(0, 1)}}-行列である。この族の{{ill2|横断 (組合せ論)|en|transversal (combinatorics)|label=完全代表系}}（systems of distinct representatives; 相異なる代表系、個別代表系; '''SDR'''）総数は {{math|perm(''A'')}} である{{sfn|Ryser|1963}}{{rp|54}}。{{efn|[[ホールの結婚定理]]も参照}}

== 関連項目 ==
* {{ill2|バパット&ndash;ベッグの定理|en|Bapat–Beg theorem}}：[[順序統計量|順序統計学]]における応用
* [[スレイター行列式]]：[[量子力学]]における応用

== 注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{notelist}}
=== 出典 ===
{{Reflist|30em}}

== 参考文献 ==
* {{Cite book |zbl=1106.05001 |last=Brualdi |first=Richard A. |authorlink=Richard A. Brualdi |title=Combinatorial matrix classes |series=Encyclopedia of Mathematics and Its Applications |volume=108 |location=Cambridge |publisher=[[ケンブリッジ大学出版局|Cambridge University Press]] |year=2006 |isbn=0-521-86565-4 |ref=harv}}
* {{Cite book |last=Minc |first=Henryk |title=Permanents |others=With a foreword by Marvin Marcus |series=Encyclopedia of Mathematics and its Applications |volume=6 |publisher=Addison–Wesley |year=1978 |issn=0953-4806 |oclc=3980645 |zbl=0401.15005 |location=Reading, MA |ref=harv}}
* {{Cite book |last=Muir |first=Thomas |author2=William H. Metzler. |year=1960 |origyear=1882 |title=A Treatise on the Theory of Determinants |location=New York |publisher=Dover |oclc=535903}}
* {{Citation |first=J.K. |last=Percus |title=Combinatorial Methods |series=Applied Mathematical Sciences #4 |publisher=Springer-Verlag |place=New York |year=1971 |isbn=0-387-90027-6 |ref=harv}}
* {{Citation |first=Herbert John |last=Ryser |authorlink=H. J. Ryser|title=Combinatorial Mathematics |series=The Carus Mathematical Monographs #14 |year=1963 |publisher=The Mathematical Association of America |ref=harv}}
* {{Citation |last1=van Lint |first1=J.H. |last2=Wilson |first2=R.M. |title=A Course in Combinatorics |publisher=Cambridge University Press |year=2001 |isbn=0521422604 |ref=harv}}

== 関連文献 ==
* {{Citation |first=Marshall |last=Hall, Jr. |authorlink=Marshall Hall (mathematician) |title=Combinatorial Theory |edition=2nd |year=1986 |publisher=John Wiley & Sons|place=New York |isbn=0-471-09138-3 |pages=56-72}} Contains a proof of the Van der Waerden conjecture.
* {{Citation |first1=M. |last1=Marcus |first2=H.|last2=Minc |title=Permanents |journal=The American Mathematical Monthly |volume=72 |year=1965 |pages=577-591 |doi=10.2307/2313846}}

== 外部リンク ==
* {{高校数学の美しい物語|1290|行列のパフィアン，パーマネント，ハフニアン}}
* {{MathWorld|urlname=Permanent|title=Permanent}}
* {{PlanetMath|urlname=Permanent|title=permanent}}
* {{PlanetMath|urlname=VanDerWaerdensPermanentConjecture|title=Van der Waerden's permanent conjecture}}
* {{ProofWiki|urlname=Definition:Permanent|title=Definition:Permanent}}
* {{SpringerEOM|urlname=Permanent|title=Permanent|first=V. E.|last=Tarakanov}}

{{DEFAULTSORT:はあまねんと}}
[[Category:組合せ論]]
[[Category:線型代数学]]
[[Category:行列論]]
[[Category:置換]]
[[Category:数学に関する記事]]