永久的な計算

線型代数学では、定義が一見似ているにもかかわらず、 行列のパーマネントの計算は行列の行列式の計算よりも難しい問題であると考えられています。

パーマネントは、行列式と同様に、異なる行と列にある行列要素の集合の積の合計として定義されます。ただし、行列式では集合の偶奇に基づいてこれらの積のそれぞれに ±1 の符号が付けられますが、パーマネントではそれらすべてに +1 の符号が付けられます。

行列式はガウス消去法によって多項式時間で計算できますが、パーマネントは多項式時間では計算できないと一般に考えられています。計算複雑性理論では、Valiant の定理により、パーマネントの計算は#P 困難であり、すべての要素が 0 または 1 である行列では#P 完全ですらあるとされています (Valiant (1979))。これにより、パーマネントの計算はNPよりも計算が難しいと考えられている問題のクラスに分類されます。対数空間一様ACC ⁰回路ではパーマネントの計算は不可能であることが知られています(Allender & Gore 1994)。

行列のパーマネントを計算するための正確なアルゴリズムと近似アルゴリズムの両方の開発は、活発な研究分野です。

n行n列の行列A = ( a _i,j )のパーマネントは次のように定義される。

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

ここでの和は対称群 S _nのすべての要素 σ に及びます。つまり、数 1、2、...、nのすべての順列に及びます。この式は、行列式の対応する式と、行列式では各積に順列σ の符号が掛けられるのに対し、この式では各積に符号がないという点のみが異なります。この式は、すべての順列を合計し、その合計内で各行列要素を掛け合わせるという、式を単純に展開するアルゴリズムに直接変換できます。これにはn! n 回の算術演算が必要です。

最もよく知られている^{[1]一般的な厳密アルゴリズムは、} HJ Ryser  (1963)によるものです。Ryserの方法は、次のように与えられる包含排除式に基づいています^[2] 。k列を削除してAから得られるものとし、の行の合計の積をとし、すべての可能なにおけるの値の合計をとします。 ${\displaystyle A_{k}}$${\displaystyle P(A_{k})}$${\displaystyle A_{k}}$${\displaystyle \Sigma _{k}}$${\displaystyle P(A_{k})}$${\displaystyle A_{k}}$

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

これを行列の要素で書き直すと次のようになる^[3]。

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$

ライザーの公式は、算術演算を使用して、またはセットをグレイコード順に処理することによって評価することができます。^[4]${\displaystyle O(2^{n-1}n^{2})}$${\displaystyle O(2^{n-1}n)}$${\displaystyle S}$

Ryser の式と同じくらい速い (あるいは 2 倍速い) と思われる別の式が、2 つの博士論文に示されています。 (Balasubramanian 1980)、(Bax 1998)、(Bax & Franklin 1996) を参照してください。式を求める方法はまったく異なり、それぞれミュア代数の組合せ論と差分理論に関連しています。不変理論に関連する別の方法は、対称テンソルの分極恒等式を介したものです(Glynn 2010)。この式は、これらすべての著者によって発見されたように、無限に多くの他の式に一般化されますが、それらが基本式よりも速いかどうかは明らかではありません。 (Glynn 2013) を参照してください。

このタイプの最も単純な既知の式（体の特性が2でない場合）は

${\displaystyle \operatorname {perm} (A)={\frac {1}{2^{n-1}}}\left[\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}\right],}$

ここで外側の合計はすべてのベクトルにわたります。 ${\displaystyle 2^{n-1}}$${\displaystyle \delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}}$

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

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

2を法として、パーマネントは行列式と同じであり、 を法として時間内に計算することもできます。しかし、2の累乗でない任意の数を法としてパーマネントを計算するのはUP困難です。Valiant (1979) ${\displaystyle (-1)\equiv 1{\pmod {2}}.}$${\displaystyle 2^{k}}$${\displaystyle O(n^{4k-3})}$${\displaystyle k\geq 2}$

Glynn (2010) は、素数p を法とする計算についてさまざまな公式を提示しています。まず、偏微分による記号計算を使用する公式があります。

第二に、p = 3の場合、行列の主な小行列式を含むn×n行列の次の式があります（Kogan（1996））。 ${\displaystyle A}$

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

ここで、 はの行と列によって誘導されるの部分行列であり、 はにおけるの補行列です。一方、空の部分行列の行列式は 1 と定義されます。 ${\displaystyle A_{J}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle J}$${\displaystyle {\bar {J}}}$${\displaystyle J}$${\displaystyle \{1,\dots ,n\}}$

上記の展開は、任意の特性pにおいて、次の一対の双対恒等式として一般化できます。 ここで、両方の式において、和は、集合をp − 1 個の部分集合に分割するすべての ( p − 1) 組に対して取られ、その一部は空である可能性があります。 $${\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}}}$$${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$${\displaystyle \{1,\dots ,n\}}$

前者の式は対称かつ奇数の p のハフニアンに類似しています。${\displaystyle A}$

$${\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}|}}$$

同じインデックスのセットに対して合計が取られます。さらに、特性 0 では、永久項と行列式の両方を含む同様の畳み込み合計式により、ハミルトン閉路多項式 ( と定義されます。ここで、は 1 つの閉路のみを持つ n 順列の集合です) が生成されます。 ${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$${\displaystyle H_{n}}$$${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.}$$

特性 2 では、後者の等式は に変わり、任意のユニタリ(つまり、 が単位n × n行列であるもの)のハミルトン閉路多項式を多項式時間で計算する機会を提供します。これは、このような行列の各小行列がその代数的補行列と一致するためです。は、インデックス 1,1 の要素が 0 に置き換えられた単位n × n行列です。さらに、これはユニタリn × n行列に対して次のようにさらに一般化できます。は{1, ..., n }のサブセット、 は、に属するすべてのkについて、インデックスk、kの要素が0 に置き換えられた単位n × n行列、 は各閉路に の少なくとも 1 つの要素が含まれる n 順列の集合です。 ${\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}$${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$${\displaystyle I_{/1}}$${\displaystyle U}$${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$${\displaystyle K}$${\displaystyle I_{/K}}$${\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)}$${\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)}$

ここで、 は、の対応する要素の 3 乗を要素とする行列です。 ${\displaystyle V}$${\displaystyle U}$

また、 のときに正方行列をk 半ユニタリとして定義すると、1 半ユニタリ行列のパーマネントは標数 3 の体上で多項式時間で計算可能であるが、k > 1 の場合、問題は #3-P 完全 になることも示されました (Kogan (1996))。(平行理論は標数 2 のハミルトン閉路多項式に関するものです。ユニタリ行列上での計算は多項式時間で実行可能ですが、k > 0の任意のk半ユニタリ行列では、問題は #2-P 完全です)。後者の結果は 2017 年に本質的に拡張され (Knezevic & Cohen (2017))、標数 3 では、正方行列のパーマネントとその部分逆行列 (およびが正方で、可逆)を関連付ける簡単な式があることが証明されました。 ${\displaystyle A}$${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$${\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 に対して ham( A ) = 0 であるという事実、または n > 2 の場合は、 i 番目とj番目の行が同一で、i番目と j 番目の列が等しい2つのインデックスi、j を持つ任意のn × n行列 A に対して ham( A ) = 0であるという事実を考慮すると、も同様です。) 転置変換 (演算子が行列をそのまま残すたびに利用される) とともに順次適用の限界として定義されるその演算子の閉包は、行列のクラスに適用された場合、あるクラスから別のクラスへの演算子マッピングでもあります。圧縮演算子は、1-セミユニタリ行列のクラスをそれ自体とユニタリ行列および2-セミユニタリ行列のクラスにマッピングしますが、1-セミユニタリクラス（および、1つの行を任意の行ベクトルに置き換えることによってユニタリ行列から取得される行列のクラス（このような行列のパーマネントは、ラプラス展開を介して、1-セミユニタリ行列のパーマネントの合計であり、したがって、多項式時間で計算可能））の圧縮閉包はまだ知られておらず、特性3におけるパーマネントの計算複雑性の一般的な問題と、P対NPの主な問題に緊張関係にあります。（Knezevic＆Cohen（2017））で示されたように、そのような圧縮閉包が特性3の体上のすべての正方行列の集合であるか、少なくともパーマネントの計算が#3-P完全である行列クラス（2-セミユニタリ行列のクラスのように）を含む場合、パーマネントこの特性では多項式時間で計算可能です。

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

$${\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行列、n ベクトル、m ベクトル で、両方のベクトルのすべての要素が集合 {0, ..., p − 1}から成り、は、 i = 1, ..., nの場合にi番目の行を、j = 1, ..., mの場合にj番目の列をそれぞれ繰り返してから受け取った行列を表します(ある行または列の多重度が 0 に等しい場合、その行または列が削除されたことを意味し、したがって、この概念は部分行列の概念の一般化です)。また、すべての要素が 1 に等しい n ベクトルを表します。この恒等式は、行列のマイナーをその逆行列のマイナーで表す古典的な公式とまったく同じであり、したがって (もう一度) 相対的内在としての行列式とパーマネントとの間の一種の双対性を示しています (実際には、対称で奇数の素数 p のハフニアンに対する独自の類似物は です)。 ${\displaystyle M}$${\displaystyle x}$${\displaystyle y}$${\displaystyle M^{(x,y)}}$${\displaystyle M}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$${\displaystyle {\vec {1}}_{n}}$${\displaystyle A}$${\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の部分逆の場合のさらに広い一般化として、 が正方で、可逆で、サイズがxであり、 である場合、恒等式も成り立つ。 ${\displaystyle A_{11}}$${\displaystyle A_{22}}$${\displaystyle A_{11}}$${\displaystyle {n_{1}}}$${\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}}}$$

ここで、行列の共通行/列多重度ベクトルおよびは、そのブロックの対応する行/列多重度ベクトルおよび、s,t = 1,2 を生成します（等式の右側の の部分逆行列についても同様です）。 ${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle A}$${\displaystyle \alpha _{s}}$${\displaystyle \beta _{t}}$${\displaystyle A}$

Aの要素が非負の場合、パーマネントは、誤差 ε Mまで確率多項式時間で近似的に計算できます。ここで、M はパーマネントの値であり、 ε > 0 は任意です。言い換えると、完全多項式時間ランダム近似スキーム(FPRAS)が存在します(Jerrum、Sinclair、Vigoda (2001))。

計算で最も難しいステップは、与えられた二部グラフ内のすべての完全マッチングの集合からほぼ均一にサンプリングするアルゴリズム、つまり完全多項式ほぼ均一サンプラー (FPAUS) を構築することです。これは、メトロポリス規則を使用して、分布が均一に近く、混合時間が多項式であるマルコフ連鎖を定義および実行するマルコフ連鎖モンテカルロ アルゴリズムを使用して実行できます。

グラフ内の完全マッチングの数を、FPAUS と Jerrum、Valiant、Vazirani (1986) によるよく知られたサンプリングからカウントへの還元法とを組み合わせて使用​​することで、パーマネントの自己簡約性を介して近似的にカウントすることができます。における完全マッチングの数を で表します。 大まかに言えば、の特定のエッジについて、 における多数のマッチングをサンプリングし、そのうち におけるマッチングがいくつあるかを数えることで、比率 の推定値を得ることができます。 この場合、その数は となり、 は同じ方法を再帰的に適用することで近似できます。 ${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle e}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G\setminus e}$${\textstyle \rho ={\frac {M(G)}{M(G\setminus e)}}}$${\displaystyle M(G)}$${\displaystyle \rho M(G\setminus e)}$${\displaystyle M(G\setminus e)}$

パーマネントが特に興味深い別のクラスの行列は、半正定値行列である。^[7]ストックマイヤーカウントの手法を使用すると、クラス 内で計算できるが、これは一般に実行不可能なクラスであると考えられている。 PSD 行列のパーマネントを指数以下の因子内で近似することは NP 困難であり、困難であると推測されている[ ^8]スペクトルにさらに制約が課される場合、より効率的なアルゴリズムが知られている。 1 つのランダム化アルゴリズムは、ボソンサンプリングのモデルに基づいており、量子光学に固有のツールを使用して、半正定値行列のパーマネントを特定のランダム変数の期待値として表す。 次に、後者はそのサンプル平均によって近似される。^[9]このアルゴリズムは、半正定値行列の特定のセットに対して、加法誤差までの多項式時間でパーマネントを近似し、これは Gurvits による標準的な古典的な多項式時間アルゴリズムよりも信頼性が高い。^[10]${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$

• Barvinok, A. (2017)、「パーマネントとハフニアン近似」、離散解析、arXiv : 1601.07518、doi :10.19086/da.1244、S2CID  397350。