常勤（数学）

線形代数では、正方行列のパーマネントは行列式と同様に行列の関数です。パーマネントは行列式と同様に、行列の要素に関する多項式です。^{[ 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 は、${\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}$[ ^{3 ]​}

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

パーマネントをn個のベクトルを引数として取るマップと見なすと、それは多重線形マップであり、対称的である（つまり、ベクトルの順序に関係なく、同じパーマネントが得られる）。さらに、正方行列が与えられた場合${\displaystyle A=\left(a_{ij}\right)}$n次数: ^{[ 7 ]}

• perm( A ) は、 Aの行および/または列の任意の置換に対して不変です。この性質は、適切なサイズの置換行列PおよびQに対して、perm( A ) = perm( PAQ )と記号的に記述できます。
• Aの任意の単一の行または列にスカラーλを掛けると、perm( A ) はλ ⋅perm( A ) に変わります。
• perm( A ) は転置に対して不変である、つまり perm( A ) = perm( A ^T ) である。
• もし${\displaystyle A=\left(a_{ij}\right)}$そして${\displaystyle B=\left(b_{ij}\right)}$n次の正方行列である場合、$${\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}}},}$$ここで、sとt は{1, 2, ..., n }の同じサイズのサブセットであり、${\displaystyle {\bar {s}},{\bar {t}}}$それらはその集合におけるそれぞれの補集合である。^{[ 8 ]}
• もし${\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},}$$

どこ${\displaystyle B_{i,j}}$はBのi行j列目のエントリであり、${\textstyle M_{i,j}}$は、 Bの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 つの解釈があります。

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

定義を用いたパーマネントの計算という単純なアプローチは、比較的小さな行列であっても計算上実行不可能である。最も高速な既知のアルゴリズムの1つは、HJ Ryserによるものである。^{[ 24 ]} Ryserの方法は、次のように表される包含排除の公式に基づいている。 ^{[ 25 ]}${\displaystyle A_{k}}$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の要素が非負の場合、パーマネントは、誤差を除いて、確率的多項式時間で近似的に計算できます。    ${\displaystyle \varepsilon M}$、 どこ${\displaystyle M}$永久の価値と${\displaystyle \varepsilon >0}$は任意である。^{[ 26 ]}特定の正定値半正定値行列のパーマネントは、任意の準指数因子内で近似するのがNP困難である。^{[ 27 ]}スペクトルにさらに条件を課すと、パーマネントは確率的多項式時間で近似できる。この近似で達成可能な最良の誤差は${\displaystyle \varepsilon {\sqrt {M}}}$（${\displaystyle M}$（これは再びパーマネントの値である）。^{[ 28 ]}これらの場合の硬さは、ボソンサンプリング実験のシミュレーションの難しさと密接に関連している。

パーマネントを考察するもう一つの方法は、多変数生成関数を用いることである。${\displaystyle A=(a_{ij})}$n次の正方行列とする。多変数生成関数を考える。 $${\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})}$は perm( A ) です。^{[ 29 ]}

一般化として、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}}.}$

マクマホンのパーマネントと行列式に関するマスター定理は次のとおりです。^{[ 30 ]}$${\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)}},}$$ ここで、Iはn 次単位行列であり、 Xは対角行列で、${\displaystyle [x_{1},x_{2},\dots ,x_{n}].}$

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

Ryserのパーマネントに関する計算結果も一般化される。Aがm  × n行列でm≤nである場合、   ${\displaystyle A_{k}}$Aからk列を削除して得られるものとする。${\displaystyle P(A_{k})}$行和の積である${\displaystyle A_{k}}$、そして${\displaystyle \sigma _{k}}$の値の合計${\displaystyle P(A_{k})}$全体的に可能な限り${\displaystyle A_{k}}$.それから^{[ 10 ]}$${\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{m-1}(-1)^{k}{\binom {n-m+k}{k}}\sigma _{n-m+k}.}$$

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

• ブルアルディ、リチャード A. (2006).組み合わせ行列クラス. 数学とその応用百科事典、第 108 巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-86565-4. Zbl 1106.05001 . 
• ミンツ、ヘンリク (1978)。パーマネント。数学とその応用百科事典。第 6 巻。マービン・マーカス による序文付き。マサチューセッツ州レディング: アディソン・ウェスリー。ISSN 0953-4806。OCLC 3980645。Zbl 0401.15005。   
• ミュア、トーマス；メッツラー、ウィリアム H. (1960) [ 1882].行列式の理論に関する論文. ニューヨーク：ドーバー。OCLC 535903。 
• Percus, JK (1971),組合せ論的方法、応用数学科学第4巻、ニューヨーク：Springer-Verlag、ISBN 978-0-387-90027-8
• ライザー、ハーバート・ジョン（1963）『組合せ数学』、カルス数学モノグラフ第14巻、アメリカ数学協会
• van Lint, JH; Wilson, RM (2001), A Course in Combinatorics , Cambridge University Press, ISBN 978-0-521-42260-4

• Hall Jr., Marshall (1986), 『組合せ論』（第2 版）、ニューヨーク：John Wiley & Sons、pp. 56–72、ISBN  978-0-471-09138-7Van der Waerden 予想の証明が含まれています。
• Marcus, M.; Minc, H. (1965)、「パーマネント」、The American Mathematical Monthly、72 (6): 577–591、doi : 10.2307/2313846、JSTOR 2313846 

• PlanetMathの正社員。
• PlanetMathにおけるVan der Waerden の永久予想。