永久（数学）

線型代数では、正方行列のパーマネントは行列式に似た行列の関数です。パーマネントも行列式も、行列の要素の多項式です。^{[1]どちらも、}内在関数と呼ばれる行列のより一般的な関数の特殊なケースです。

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のすべての順列に及びます。

例えば、

$${\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は長方形行列のパーマネントにPer( A )を使用し、 Aが正方行列の場合はper( A )を使用します。 ^[2] MuirとMetzlerは という表記を使用します。^[3]${\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}$

永久的という語は、1812年にコーシーが「fonctions symétriques permanentes」として関連したタイプの関数として用いた言葉で、^{[4]ミュアとメッツラー[5]}によって現代的な、より具体的な意味で使用されました^{[6] 。}

パーマネントをn個のベクトルを引数とする写像とみなすと、それは多重線型写像であり、対称的である（つまり、ベクトルのどの順序でも同じパーマネントになる）。さらに、 n次の正方行列が与えられると、次の式が得られる。^[7]${\displaystyle A=\left(a_{ij}\right)}$

• perm( A )は、 Aの行および/または列の任意の順列に対して不変である。この特性は、任意の適切なサイズの順列行列PおよびQに対して、記号的にperm( A ) = perm( PAQ )と表記される。
• Aの任意の行または列にスカラー sを掛けると、perm( A )はs⋅perm ( A )に変わります。
• perm( A )は転置に対して不変です。つまり、perm( A )=perm( A ^T )です。
• およびがn次の正方行列である場合、^[8]で、sとtは{1,2,..., n }の同じサイズの部分集合であり、その集合内のそれぞれの補集合である。${\displaystyle A=\left(a_{ij}\right)}$${\displaystyle B=\left(b_{ij}\right)}$ $${\displaystyle \operatorname {perm} \left(A+B\right)=\sum _{s,t}\operatorname {perm} \left(a_{ij}\right)_{i\in s,j\in t}\operatorname {perm} \left(b_{ij}\right)_{i\in {\bar {s}},j\in {\bar {t}}},}$$${\displaystyle {\bar {s}},{\bar {t}}}$
• が三角行列、つまり のときはいつでも、あるいは のときはいつでも、その永久行列式 (および行列式) は対角要素の積に等しくなります。${\displaystyle A}$${\displaystyle a_{ij}=0}$${\displaystyle i>j}$${\displaystyle i<j}$$${\displaystyle \operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.}$$

行、列、対角線に沿った行列式を計算するためのラプラスのマイナー展開は、すべての符号を無視することで永久に拡張されます。[ 9 ^]

すべての に対して、 ${\textstyle i}$

$${\displaystyle \mathbb {perm} (B)=\sum _{j=1}^{n}B_{i,j}M_{i,j},}$$

ここで、 はBのi行目とj列目の要素であり、 はBのi行目とj列目を削除して得られる部分行列のパーマネントです。 ${\displaystyle B_{i,j}}$${\textstyle M_{i,j}}$

例えば、最初の列に沿って展開すると、

$${\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&1\cdot \operatorname {perm} \left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right)+2\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}}\right)\\&{}+\ 3\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}}\right)+4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)\\={}&1(1)+2(1)+3(1)+4(1)=10,\end{aligned}}}$$

最後の行に沿って展開すると、

$${\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)+0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}}\right)\\&{}+\ 0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}}\right)+1\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&1\end{matrix}}\right)\\={}&4(1)+0+0+1(6)=10.\end{aligned}}}$$

一方、行列式の基本的な乗法の性質は、永久的なものには当てはまりません。^[10]簡単な例でこれが分かります。

$${\displaystyle {\begin{aligned}4&=\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\\&\neq \operatorname {perm} \left(\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\right)=\operatorname {perm} \left({\begin{matrix}2&2\\2&2\end{matrix}}\right)=8.\end{aligned}}}$$

行列式とは異なり、パーマネントには簡単な幾何学的解釈がありません。パーマネントは主に組合せ論、量子場の理論におけるボソングリーン関数の取り扱い、ボソンサンプリングシステムの状態確率の決定に使用されます。^{[11]しかし、パーマネントには2つの}グラフ理論的解釈があります。有向グラフのサイクル被覆の重みの合計として、および二部グラフの完全マッチングの重みの合計としてです。

パーマネントは、ヒルベルト空間の対称テンソル冪 の研究で自然に生じる。^[12]特に、ヒルベルト空間 に対して、の 番目の対称テンソル冪を表すものとする。これは対称テンソルの空間である。特に、は の要素の対称積によって張られることに注意されたい。 に対して、これらの要素の対称積を で定義する。 （ の部分空間として、のk番目のテンソル冪） を考え、それに応じて の内積を定義すると、 に対して となることがわかる。コーシー・シュワルツの不等式 を適用すると、 となり、 ${\displaystyle H}$${\displaystyle \vee ^{k}H}$${\displaystyle k}$${\displaystyle H}$${\displaystyle \vee ^{k}H}$${\displaystyle H}$${\displaystyle x_{1},x_{2},\dots ,x_{k}\in H}$$${\displaystyle 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)}}$$${\displaystyle \vee ^{k}H}$${\displaystyle \otimes ^{k}H}$${\displaystyle H}$${\displaystyle \vee ^{k}H}$${\displaystyle x_{j},y_{j}\in 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} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}}$$${\displaystyle \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0}$$${\displaystyle \left|\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}\right|^{2}\leq \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\cdot \operatorname {perm} \left[\langle y_{i},y_{j}\rangle \right]_{i,j=1}^{k}}$$

任意の正方行列は、頂点集合 上の重み付き有向グラフの隣接行列として見ることができます。ここで、 は頂点iから頂点jへの弧の重みを表します。重み付き有向グラフのサイクル カバーは、グラフ内のすべての頂点をカバーする有向グラフ内の頂点が互いに素な有向サイクルのコレクションです。したがって、有向グラフ内の各頂点i はサイクル カバー内に一意の「後続頂点」を持ち、V上の順列を表します。逆に、 V上の任意の順列は、各頂点iから頂点 への弧を持つサイクル カバーに対応します。 ${\displaystyle A=(a_{ij})_{i,j=1}^{n}}$${\displaystyle V=\{1,2,\dots ,n\}}$${\displaystyle a_{ij}}$${\displaystyle \sigma (i)}$${\displaystyle \sigma }$${\displaystyle \sigma }$${\displaystyle \sigma (i)}$

サイクルカバーの重みが各サイクルのアークの重みの積として定義されている場合、次の ことが意味されます 。したがって、 A のパーマネントは、有向グラフのすべてのサイクルカバーの重みの合計に等しくなります。 $${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)},}$$$${\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\operatorname {weight} (\sigma ).}$$

正方行列は、一方に頂点があり、もう一方に頂点がある二部グラフの隣接行列として見ることもできます。この場合、頂点から頂点への辺の重みを表します。に一致する完全マッチングの重みが、マッチング内の辺の重みの積として定義される場合、 したがって、 A のパーマネントは、グラフのすべての完全マッチングの重みの合計に等しくなります。 ${\displaystyle A=(a_{ij})}$ ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$${\displaystyle y_{1},y_{2},\dots ,y_{n}}$${\displaystyle a_{ij}}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$ ${\displaystyle \sigma }$${\displaystyle x_{i}}$${\displaystyle y_{\sigma (i)}}$$${\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)}.}$$

多くの数え上げの質問に対する答えは、0 と 1 のみをエントリとして持つ行列のパーマネントとして計算できます。

Ω( n , k ) を、各行と列の合計がkに等しいn次 (0, 1) 行列すべてのクラスとします。このクラスのすべての行列Aは、 perm( A ) > 0です。 ^[13]射影平面の接続行列は、 n が1 より大きい整数の場合、クラス Ω( n ² + n + 1, n + 1)にあります。最小の射影平面に対応するパーマネントが計算されています。n = 2、3、4 の場合、値はそれぞれ 24、3852、18,534,400 です。^[13] Z を、 n = 2 の射影平面、つまりファノ平面の接続行列とします。注目すべきことに、 perm( Z ) = 24 = |det ( Z )| であり、 Zの行列式の絶対値です。これはZが巡回行列であることと定理^[14]の結果である。

Aがクラス Ω( n , k )の巡回行列である場合、 k  > 3 であれば perm( A ) > |det ( A )| であり、k  = 3 であれば perm( A ) = |det ( A )| です。さらに、k  = 3 の場合、行と列を並べ替えると、A は行列Zのe個のコピーの直和の形にすることができ、その結果、n  = 7 eおよび perm( A ) = 24 ^eになります。

パーマネントは、制限された（禁止された）位置を持つ順列の数を計算するためにも使用できます。標準的なnセット{1, 2, ..., n }に対して、i  →  jが順列で許可されている場合はa _ij = 1 、そうでない場合はa _ij = 0となる（0, 1）行列を とします。すると、perm( A )は、すべての制限を満たすnセットの順列の数に等しくなります。 ^{[9]この2つのよく知られた特別なケースは、}乱れ問題とメネジェ問題の解決です。固定点のないnセットの順列の数（乱れ）は、次のように与えられます。 ${\displaystyle A=(a_{ij})}$

$${\displaystyle \operatorname {perm} (J-I)=\operatorname {perm} \left({\begin{matrix}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{matrix}}\right)=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}},}$$ ここでJはn × nのすべて1の行列、Iは単位行列であり、メナージュ数は次のように与えられる。

$${\displaystyle {\begin{aligned}\operatorname {perm} (J-I-I')&=\operatorname {perm} \left({\begin{matrix}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{matrix}}\right)\\&=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!,\end{aligned}}}$$

ここで、I'は、位置( i、i + 1)および( n 、 1)に非ゼロの要素を持つ(0、1)行列です。

ブレグマン・ミンクの不等式は、1963年にH.ミンクによって予想され^[15]、1973年にLMブレグマンによって証明され^{[16] 、} n × n （0, 1）行列のパーマネントの上限を与える。Aのi行目に1 ≤ i ≤ nのそれぞれに対してr _i個の1がある場合、不等式は次のようになる。 $${\displaystyle \operatorname {perm} A\leq \prod _{i=1}^{n}(r_{i})!^{1/r_{i}}.}$$

1926年、ファン・デル・ワールデンは、すべてのn × n 二重確率行列の中で最小のパーマネントはn !/ n ⁿであり、これはすべての要素が1/ nに等しい行列によって達成されると予想した。^{[17]この予想の証明は、1980年にB. Gyires [18]}、1981年にGP Egorychev ^[19]とDI Falikman ^[20]によって発表された。Egorychevの証明は、アレクサンドロフ-フェンチェル不等式の応用である。^[21]この研究により、EgorychevとFalikmanは1982年にフルカーソン賞を受賞した。^[22]

定義を用いた単純なパーマネント計算法は、比較的小さな行列であっても計算上不可能である。最も高速な既知のアルゴリズムの1つは、HJ Ryserによるものである^[23] 。Ryserの方法は、次のように与えられる包含排除式に基づいている^[24] 。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}.}$$

これを行列の要素の観点から書き直すと次のようになります。 $${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$$

パーマネントは行列式の計算よりも難しいと考えられている。行列式はガウス消去法によって多項式時間で計算できるが、パーマネントの計算にガウス消去法を使用することはできない。さらに、(0,1)行列のパーマネントの計算は#P 完全である。したがって、パーマネントが任意の方法で多項式時間で計算できる場合、FP  =  #Pとなり、これはP = NPよりもさらに強い主張である。ただし、 Aの要素が非負の場合、パーマネントはの誤差まで確率多項式時間で近似的に計算できる。ここで はパーマネントの値で は任意である。^{[25]特定の}半正定値行列のパーマネントは、指数以下の因子内で近似することが NP 困難である。^[26]スペクトルにさらなる条件が課せられると、パーマネントは確率多項式時間で近似できる。この近似で達成可能な最良の誤差は（再びパーマネントの値である）である。^{[27]これらの場合の困難さは、}ボソンサンプリング実験をシミュレートする難しさと密接に関連している。 ${\displaystyle \varepsilon M}$${\displaystyle M}$${\displaystyle \varepsilon >0}$${\displaystyle \varepsilon {\sqrt {M}}}$${\displaystyle M}$

パーマネントを見るもう一つの方法は、多変量生成関数を使うことです。をn次の正方行列とします。多変量生成関数を考えます。 の 係数はperm( A )です。^[28]${\displaystyle A=(a_{ij})}$$${\displaystyle {\begin{aligned}F(x_{1},x_{2},\dots ,x_{n})&=\prod _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}x_{j}\right)\\&=\left(\sum _{j=1}^{n}a_{1j}x_{j}\right)\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right).\end{aligned}}}$$${\displaystyle x_{1}x_{2}\dots x_{n}}$${\displaystyle F(x_{1},x_{2},\dots ,x_{n})}$

一般化として、 n個の非負整数の任意の列に対して、次のように定義します。 ${\displaystyle s_{1},s_{2},\dots ,s_{n}}$$${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)}$$${\displaystyle x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}}$${\displaystyle \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}}.}$

マクマホンのパーマネントと行列式に関するマスター定理は^[29] である。 ここでIはn次の単位行列、Xは対角行列である。$${\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)={\text{ coefficient of }}x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}{\text{ in }}{\frac {1}{\det(I-XA)}},}$$${\displaystyle [x_{1},x_{2},\dots ,x_{n}].}$

パーマネント関数は、非正方行列にも適用できるように一般化できる。実際、何人かの著者はこれをパーマネントの定義とし、正方行列への制限を特別なケースとみなしている。^[30]具体的には、m  ≤  nのm  ×  n行列について、次のように定義する。 ここで、 P( n , m ) は、 n集合 {1,2,...,n} のすべてのm順列の集合である。^[31]${\displaystyle A=(a_{ij})}$$${\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\ldots a_{m\sigma (m)}}$$

Ryserのパーマネントの計算結果も一般化できる。Aがm×n行列でm≤nの場合、A から k列を削除して得られるものとし、をの行和の積とし、をすべて の 可能なにおけるの値の合計とすると^[10]${\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}^{m-1}(-1)^{k}{\binom {n-m+k}{k}}\sigma _{n-m+k}.}$$

永久行列の定義を非正方行列に一般化することで、この概念をいくつかのアプリケーションでより自然な方法で使用できるようになります。たとえば、

S ₁、S ₂、...、S _{m を}、 m  ≤  nのn集合の部分集合（必ずしも異なる必要はない）とする。この部分集合の集合の接続行列は、 m  ×  n (0,1)行列Aである。この集合の異なる代表システムの数はperm( A )である。^[32]

• 永久的な計算
• バパット・ベグ定理、順序統計におけるパーマネントの応用
• スレーター行列式、量子力学における永久変数の応用
• ハフニアン

• Brualdi, Richard A. (2006).組み合わせ行列クラス. 数学とその応用百科事典. 第108巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-86565-4.ZBL1106.05001  。​
• Minc, Henryk (1978)。パーマネント。数学とその応用の百科事典。第 6 巻 。Marvin Marcus による序文付き。マサチューセッツ州レディング: Addison–Wesley。ISSN  0953-4806。OCLC 3980645。Zbl 0401.15005  。
• ミュア、トーマス; メッツラー、ウィリアム H. (1960) [1882].行列式の理論に関する論文. ニューヨーク: ドーバー. OCLC  535903.
• パーカス、JK（1971）、組み合わせ法、応用数学科学＃4、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-90027-8
• ライザー、ハーバート・ジョン（1963）、組合せ数学、カーラス数学モノグラフ＃14、アメリカ数学協会
• van Lint, JH; Wilson, RM (2001)、A Course in Combinatorics、ケンブリッジ大学出版局、ISBN 978-0521422604

• ホール・ジュニア、マーシャル（1986）、組合せ理論（第2版）、ニューヨーク：ジョン・ワイリー＆サンズ、pp.56-72、ISBN 978-0-471-09138-7Van der Waerden 予想の証明が含まれています。
• マーカス, M.; ミンク, H. (1965)、「パーマネント」、アメリカ数学月刊誌、72 (6): 577–591、doi :10.2307/2313846、JSTOR  2313846

• PlanetMathに常駐。
• PlanetMathにおける Van der Waerden の永久予想。