永久の計算

二部グラフにおける完全マッチングの数は、グラフの二部隣接行列のパーマネントによってカウントされ、任意の 0-1 行列のパーマネントは、このようにしてグラフにおける完全マッチングの数として解釈できます。平面グラフ(二部グラフであるかどうかに関わらず) の場合、FKT アルゴリズムは、グラフのTutte 行列のエントリの慎重に選択された部分集合の符号を変更することによって、多項式時間で完全マッチングの数を計算します。これにより、結果として得られる歪対称行列のPfaffian (その行列式の平方根) が完全マッチングの数になります。この手法は、完全な二部グラフK _3,3と同相な部分グラフを含まないグラフに一般化できます。^{[ 5 ]}

ジョージ・ポリアは、 01行列Aの一部の要素の符号を変更することで、新しい行列の行列式がAのパーマネントとなるのはどのような場合かという疑問を提起した^{[ 6 ]。}すべての01行列がこのように「変換可能」なわけではない。実際、線形写像は存在しないことが知られている（マーカス＆ミンク（1961） ）。${\displaystyle T}$そのため${\displaystyle \operatorname {per} T(A)=\det A}$すべての人々のために${\displaystyle n\times n}$行列${\displaystyle A}$「変換可能」な行列の特徴付けは、Little (1975)によって与えられ、そのような行列は、 Pfaffian 方向を持つ二部グラフの二部隣接行列であることを示しました。Pfaffian 方向とは、すべての偶数サイクルに対して、エッジの方向が となるような方向です。${\displaystyle C}$そのために${\displaystyle G\setminus C}$完全マッチングがあり、C に沿って方向付けられたエッジの数が奇数である（したがって、反対方向のエッジの数も奇数である）。また、これらのグラフは、 と同相な部分グラフを含まないグラフと正確に一致することも示された。${\displaystyle K_{3,3}}$上記のとおり。

モジュロ2では、パーマネントは行列式と同じである。${\displaystyle (-1)\equiv 1{\pmod {2}}.}$また、モジュロで計算することもできます。$2k$時間が経つにつれて${\displaystyle O(n^{4k-3})}$のために${\displaystyle k\geq 2}$しかし、2のべき乗でない任意の数を法とするパーマネントを計算することは非常に困難である。ヴァリアント（1979）

グリン（2010）は、素数pを法とする計算のためのさまざまな公式を提示している。まず、偏微分を用いた記号計算を用いる公式がある。

第二に、p = 3 の場合、n×n 行列に対して次の式が成り立つ。${\displaystyle A}$行列の主小行列式を含む（Kogan（1996））：

${\displaystyle \operatorname {per} (A)=(-1)^{n}\sum _{J\subseteq \{1,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}}),}$

どこ${\displaystyle A_{J}}$は、${\displaystyle A}$行と列によって誘発される${\displaystyle A}$ インデックス${\displaystyle J}$、 そして${\displaystyle {\bar {J}}}$は${\displaystyle J}$で${\displaystyle \{1,\dots ,n\}}$一方、空の小行列の行列式は1と定義される。

上記の展開は、任意の特性pに関して、次の双対恒等式のペアとして一般化できる。 $${\displaystyle {\begin{aligned}\operatorname {per} (A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})\\\det(A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dotsm \operatorname {per} (A_{J_{p-1}})\end{aligned}}}$$ どちらの式においても、和はすべての ( p − 1) 組について取られる。${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$集合の分割である${\displaystyle \{1,\dots ,n\}}$p − 1 個の部分集合に分割する。これらの部分集合の中には、空集合が含まれる場合もある。

前者の式は、対称的なハフニアンに対応する類似式を持つ。${\displaystyle A}$そして奇妙なp:

$$\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})(-1)^{|J_{1}|+\dots +|J_{(p-1)/2}|}}$$

同じインデックスの集合について和をとる。さらに、特性がゼロの場合、パーマネントと行列式の両方を含む同様の畳み込み和表現は、ハミルトン閉路多項式（次のように定義される）を与える。$\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$どこ${\displaystyle H_{n}}$は、サイクルを1つだけ持つn順列の集合です。 $$\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.}$$

特性2では、後者の等式は$\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$したがって、これは任意のユニタリのハミルトンサイクル多項式を多項式時間で計算する機会を提供する${\displaystyle U}$（つまり、${\displaystyle U^{\textsf {T}}U=I}$どこ${\displaystyle I}$（n × n単位行列）は、そのような行列の各小行列式がその代数的補行列と一致するため、単位行列である。${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$どこ${\displaystyle I_{/1}}$これは、 n × n単位行列のインデックス 1,1 の要素を 0 に置き換えたものです。さらに、これはn × n単位行列に一般化することもできます。${\displaystyle U}$として${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$どこ${\displaystyle K}$は {1, ..., n }の部分集合です。${\displaystyle I_{/K}}$は、すべてのkに属するインデックスk、kの要素を 0 に置き換えたn × n単位行列です。${\displaystyle K}$、そして定義します${\textstyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}(K)}\prod _{i=1}^{n}a_{i,\sigma (i)}}$どこ${\displaystyle H_{n}(K)}$は、各サイクルに少なくとも 1 つの要素が含まれる n 置換の集合である。${\displaystyle K}$。

この式は、標数3の体において以下の恒等式も意味する。

任意の可逆${\displaystyle A}$

${\displaystyle \operatorname {per} (A^{-1})\operatorname {det} ^{2}(A)=\operatorname {per} (A);}$

任意のユニタリ${\displaystyle U}$つまり、正方行列${\displaystyle U}$そのため${\displaystyle U^{\textsf {T}}U=I}$どこ${\displaystyle I}$は対応するサイズの単位行列です。

${\displaystyle \operatorname {per} ^{2}(U)=\det(U+V)\det(-U)}$

どこ${\displaystyle V}$は、対応する要素の立方である要素を持つ行列です。${\displaystyle U}$。

また、( Kogan (1996) ) 正方行列を定義すると、${\displaystyle A}$k-半ユニタリとして${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$1-半ユニタリ行列のパーマネントは、標数3の体上では多項式時間で計算可能ですが、k > 1 の場合は#3-P-完全問題となります。（標数2のハミルトン閉路多項式に関する並行理論があります。ユニタリ行列上での計算は多項式時間で実行可能ですが、k-半ユニタリ行列の場合は任意のk > 0に対して #2-P-完全問題となります。）後者の結果は2017年に本質的に拡張され（Knezevic & Cohen (2017)）、標数3では正方行列のパーマネントとその部分逆行列（${\displaystyle A_{11}}$そして${\displaystyle A_{22}}$四角いので、${\displaystyle A_{11}}$可逆であること):

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}=\operatorname {det} ^{2}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}}$$

そして、k行またはk -1行のサブセットが別の（互いに素な）k行のサブセットの線形結合として表現できるn × n行列のパーマネントの計算を、それぞれ( n - k )×( n - k)行列または(n- k +1)× ( n - k +1)行列のパーマネントの計算に多項式時間で還元することを可能にする。これにより、特性3のパーマネントを「保存」する圧縮演算子（行列式の計算に適用されるガウス修正に類似）が導入される。（類似して、特性2のハミルトン閉路多項式も不変行列圧縮を持つことに注目すべきである。これは、3つの等しい行を持つ任意のn × n行列A、またはn >2の場合、i番目とj番目の行が同一で、 i番目とj番目の列が同一であるインデックスのペアi、jに対してham( A ) = 0となるという事実を考慮すると、である。 （同様に。）その演算子の閉包は、転置変換（演算子が行列をそのまま残すたびに使用される）とともに逐次適用された極限として定義され、行列のクラスに適用された場合、あるクラスから別のクラスへの演算子マッピングでもあります。圧縮演算子は 1-半ユニタリ行列のクラスをそれ自身とユニタリ行列および 2-半ユニタリ行列のクラスに写像しますが、1-半ユニタリ行列のクラス (およびユニタリ行列から任意の行ベクトルで 1 つの行を置き換えることによって得られる行列のクラス- このような行列のパーマネントは、ラプラス展開を介して 1-半ユニタリ行列のパーマネントの和であり、したがって多項式時間で計算可能です) の圧縮閉包はまだ不明であり、標数 3 におけるパーマネントの計算複雑性の一般的な問題とP 対 NPの主要な問題に密接に関連しています。 ( Knezevic & Cohen (2017)で示されたように)、このような圧縮閉包が標数 3 の体上のすべての正方行列の集合であるか、少なくともパーマネントの計算が#3-P 完全である行列クラス(2-半ユニタリ行列のクラスなど) を含む場合、パーマネントはこの特性に関して多項式時間で計算可能である。

さらに、特性3に存在する永続性を保つ圧縮の類似物を他の素特性について見つけて分類するという問題が定式化され（Knezevic & Cohen (2017) ）、 n × n行列に対して次の恒等式が与えられた。${\displaystyle A}$そして、2つのn次元ベクトル（すべての要素が集合{0, ..., p − 1}から構成される）${\displaystyle \alpha }$そして${\displaystyle \beta }$そのため${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$任意の素数特性pにおいて有効：

$${\displaystyle \operatorname {per} (A^{(\alpha ,\beta )})=\det ^{p-1}(A)\operatorname {per} (A^{-1})^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)\left(\prod _{j=1}^{n}\beta _{j}!\right)(-1)^{n+\sum _{i=1}^{n}\alpha _{i}}}$$

ここで、n × m行列の場合${\displaystyle M}$n次元ベクトル${\displaystyle x}$そしてmベクトル${\displaystyle y}$両方のベクトルは、すべての要素が集合 {0, ..., p − 1} から得られます。${\displaystyle M^{(x,y)}}$は、から受け取った行列を表します。${\displaystyle M}$繰り返しによって${\displaystyle x_{i}}$i = 1, ..., nのi番目の行を掛け、${\displaystyle y_{j}}$j = 1, ..., mのj番目の列の倍数（行または列の重複度がゼロの場合、その行または列が削除されたことを意味するため、この概念は部分行列の概念の一般化である）、${\displaystyle {\vec {1}}_{n}}$は、すべての要素が 1 に等しい n 次元ベクトルを表します。この恒等式は、行列の小行列式をその逆行列の小行列式で表す古典的な公式と全く同じであり、したがって、行列式とパーマネントが相対的イマナントとして一種の双対性を持っていることを（再び）示しています。（実際には、対称行列のハフニアンに対するそれ自身の類似物です。）${\displaystyle A}$そして奇素数pは${\textstyle \operatorname {haf} ^{2}(A^{(\alpha ,\alpha )})=\det ^{p-1}(A)\operatorname {haf} ^{2}(A^{-1})^{((p-1){\vec {1}}_{n}-\alpha ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)^{2}(-1)^{n(p-1)/2+n+\sum _{i=1}^{n}\alpha _{i}}}$)

さらに、素数標数 p の部分逆の場合のより広い一般化として、${\displaystyle A_{11}}$、${\displaystyle A_{22}}$四角いので、${\displaystyle A_{11}}$反転可能でサイズも${\displaystyle {n_{1}}}$x${\displaystyle {n_{1}}}$、 そして${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$そこには同一性も存在する

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}^{(\alpha ,\beta )}={\det }^{p-1}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{1,i}!\right)\left(\prod _{j=1}^{n}\beta _{1,j}!\right)(-1)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$$

ここで、共通の行/列多重度ベクトル${\displaystyle \alpha }$そして${\displaystyle \beta }$行列の場合${\displaystyle A}$対応する行/列の多重度ベクトルを生成する${\displaystyle \alpha _{s}}$そして${\displaystyle \beta _{t}}$、s,t = 1,2、そのブロックの場合（同じ懸念事項）${\displaystyle A}$（等式の右辺にある部分逆数）。