パーマネント (数学)

線型代数学における正方行列のパーマネント（英: Permanent）は、行列式 (determinant) によく似た行列変数の函数（英語版）である。パーマネントは、行列式と同様に、行列の成分を変数とする多項式である^[1]。Permutation（置換）と determinant（行列式）を合成したカバン語をもじったものである。英単語の「Permanent」から永久式^[2]または恒久式^[3]と訳されたこともある。中国語の名称は積和式。

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

定義編集

$n$ 次正方行列 $A ≔ (a i,j)$ のパーマネントは

\operatorname {perm} (A):=\textstyle \sum \limits _{\sigma \in S_{n}}\prod \limits _{i=1}^{n}a_{i,\sigma (i)}

で与えられる。右辺の和は、対称群 $S n$ の任意の元 $σ$ （つまり、番号 $1, 2, \dots, n$ の置換）に亙ってとるものとする。

例えば、二次正方行列に対しては

\operatorname {perm} \!{\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc

であり、三次正方行列に対しては

\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 (1984) は $A$ が矩形行列の場合に $Per(A)$ , 正方行列には $per(A)$ と使い分けている。Muir (1882) は ${\overset {+}{|}}\quad {\overset {+}{|}}$ で括る記法を用いている。

術語「パーマネント」は元々はコーシーが1812年に “fonctions symétriques permanentes” として関連する函数の一種に対して用いた^[4]。より特定した現代的な意味での使用は Muir (1882) による^[5]^:108。

性質編集

パーマネントを $n$ 本の列（または行）ベクトルを引数にとる写像と見るとき、多重線型対称形式（英語版）（引数となるベクトルの順番を入れ替えても結果は変わらない）である。より具体的に、 $n$ 次正方行列 $A = (a ij)$ に対して以下が成り立つ^[6]^:25-26：

$perm(A)$ は $A$ の行または列ベクトルに関する任意の置換の下で不変である。この性質を任意の置換行列 $P, Q$ を用いて $perm(A) = perm(PAQ)$ という形で記号的に表せる。
$A$ の任意の一つの行または列にスカラー $s$ を掛けるとき、 $perm(A)$ は $s \cdotperm(A)$ に写る。
$perm(A)$ は転置の下で不変： $perm(A) = perm(A ⊤)$ .

$n$ 次正方行列 $A ≔ (a ij), B ≔ (b ij)$ に対し

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

が成立する^[7]^:2。ただし、 $s, t$ は ${1, 2, \dots, n}$ の同じサイズの部分集合で、 $s, t$ はそれぞれの補集合である。

これと対照に、行列式の基本性質である乗法性はパーマネントでは成り立たない^[6]^:26^{[注釈 1]}。

行列式に対するラプラス展開と同様に、パーマネントを行、列または対角線にそって展開することができる^[7]^:12（行列式の場合には各余因子に交代符号が付いたが、パーマネントの場合には符号は付かない）。^{[注釈 2]}

応用編集

行列式の場合とは違い、パーマネントは平易な幾何学的解釈はない。主な応用先として、組合せ論、量子力学におけるボソンのグリーン関数の扱いにおいて、およびボソンサンプリング（英語版）システムの状態可能性の決定において^[8]などがある。ただし、2種類のグラフ理論的解釈をもつ（有向グラフの閉路被覆（英語版）の重み付き和、および二部グラフにおける完全マッチングの重み付き和）。

対称テンソル編集

パーマネントはヒルベルト空間上の対称テンソル冪の研究において自然に生じてくる^[9]。具体的に、 $H$ をヒルベルト空間とし、その対称テンソル全体の成す空間である対称テンソル冪を $\bigvee ^{k}H$ と書くと、特に $\bigvee ^{k}H$ は $H$ の元からなる対称（テンソル）積によって生成されることに注意する。 $x 1, x 2, \dots, x k \in H$ の対称積は

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)}

と定義される。 $\bigvee ^{k}H$ を（ $H$ の $k$ 次テンソル冪（英語版） $\bigotimes ^{k}H$ の部分空間として）考えるとき、その上に内積 $⟨, ⟩$ が定義されれば、それに応じて

\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\leq i,j\leq k})\qquad (x_{j},y_{j}\in H)

となることが分かる。コーシー＝シュワルツの不等式を適用すれば、 $\operatorname {perm} ((\langle x_{i},x_{j}\rangle )_{1\leq i,j\leq k})\geq 0$ および

{\Bigl |}\operatorname {perm} ((\langle x_{i},y_{j}\rangle )_{1\leq i,j\leq k}){\Bigr |}^{2}\leq \operatorname {perm} ((\langle x_{i},x_{j}\rangle )_{1\leq i,j\leq k})\cdot \operatorname {perm} ((\langle y_{i},y_{j}\rangle )_{1\leq i,j\leq k})

が確かめられる。

閉路被覆編集

任意の正方行列 $A ≔ (a ij)$ は適当な重み付き有向グラフの隣接行列と見なすことができて、各 $a ij$ は頂点 $i$ から $j$ へ結ぶ弧の重み付けを表す。重み付き有向グラフの閉路被覆（英語版）とは、その有向グラフの点素 (vertex-disjoint) な有向閉路の集まりで、グラフの全ての頂点を被覆するものをいう。このとき、有向グラフの各頂点 $i$ は、その閉路被覆において一意的な「後続点」 $σ (i)$ を持ち、 $σ$ は ${1, 2, \dots, n}$ （ $n$ はグラフの頂点数）の置換となる。逆に、 ${1, 2, \dots, n}$ 上の任意の置換 $σ$ は、各 $i$ に対して頂点 $i$ から $σ (i)$ へ結ぶ弧がある閉路被覆に対応する。

「閉路被覆の重み」を各閉路における重みの総乗と定めるならば、

\operatorname {weight} (\sigma ):=\textstyle \prod \limits _{i=1}^{n}a_{i,\sigma (i)}

と書ける。 $n$ 次正方行列 $A$ のパーマネントの定義

\operatorname {perm} (A)=\textstyle \sum \limits _{\sigma }\prod \limits _{i=1}^{n}a_{i,\sigma (i)}

（ $σ$ は ${1, 2, \dots, n}$ 上の置換）と比較すれば、隣接行列 $A$ のパーマネントが、対応する有向グラフの閉路被覆全てに亙る重み付き和に等しいことが分かる。

完全マッチング編集

正方行列 $A ≔ (a ij)$ を、頂点集合 ${x 1, x 2, \dots, x n}$ および ${y 1, y 2, \dots, y n}$ を持つ二部グラフで、頂点 $x i$ から頂点 $y j$ へ結んだ辺の重みが $a ij$ であるものの隣接行列と見ることもできる。 $x i$ を $y j$ にマッチさせる完全マッチング（英語版） $σ$ の重みを、このマッチングに現れる辺全ての重みの総乗と定義するならば

\operatorname {weight} (\sigma ):=\textstyle \prod \limits _{i=1}^{n}a_{i,\sigma (i)}

と書けるから、 $A$ のパーマネントはこの二部グラフの完全マッチング全てに亙る重み付き和に等しいことが分かる。

二値行列のパーマネント編集

数え上げ編集

多くの数え上げ問題に $0$ と $1$ のみを成分とする行列のパーマネントを計算することで答えることができる。

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

定理: $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, \dots, n}$ に対して、 $A = (a ij)$ を、各 $a ij$ は素の置換で $i \to j$ と写せるならば $1$ , さもなくば $0$ と定めて得られる $(0, 1)$ -行列とするとき、 $perm(A)$ は標準 $n$ -元集合上でこれらの制限を全て満たす置換の総数に等しい^[7]^:12。このような例としてよく知られた特別の場合が、完全順列問題（不動点を全く持たない場合）とメナージュの問題（英語版）（problème des ménages: 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める）である。完全順列の場合、 $n$ 元-集合において不動点が一つもない置換の総数は

\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!}}

で与えられる。ただし $J$ は全ての成分が $1$ の $n$ 次正方行列で、 $I$ は $n$ 次単位行列である。一方、メナージュ問題の場合の数（メナージュ数（英語版））は

{\begin{aligned}\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{aligned}}

で与えられる。ただし、 $I'$ は $(i, i + 1)$ 成分および $(n, 1)$ 成分のみが非零である $(0, 1)$ -行列とする。

上界編集

ブレグマン–ミンク不等式（英語版）（H. Minc (1963)^[10]で予想され、ブレグマン（英語版）が1973年に証明した^[5]^:101）は $n$ 次 $(0, 1)$ -行列の上界を与える。

定理 (Bregman–Minc inequality): 各 $1 \leq i \leq n$ に対して、 $A$ の第 $i$ 行には $r i$ 個の $1$ があるものとするとき、; $\operatorname {perm} A\leq \textstyle \prod \limits _{i=1}^{n}(r_{i})!^{\tfrac {1}{r_{i}}}$

が成り立つ。

ファンデルヴェルデンの予想編集

Van der Waerden (1926) は $n$ 次二重確率行列の中で最小のパーマネントは $n!/ n n$ で、それは全ての成分が $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/n$ に等しい行列によって達成されると予想した^[11]。この予想の証明は、(B. Gyires 1980)^[12] および (G. P. Egorychev 1980, 1981)^[13]^[14] および (D. I. Falikman 1981)^[15]として出版された。Egorychev の証明はアレクサンドロフ–フェンケル不等式（英語版）の一つの応用である^[16]。この業績により Egorychev と Falikman はファルカーソン賞を1982年に受賞している^[17]。

計算編集

詳細は「パーマネントの計算（英語版）」および「01値パーマネントの♯P完全性（英語版）」を参照

定義通りに素朴にパーマネントを計算しようとすれば、比較的小さい行列に対してさえ計算量的に不可能である。知られている最も速いアルゴリズムの一つは H. J. Ryser (1963) による包除原理に基づいたRyser法（英語版）で、以下のように与えられる^[5]^:99:

主張: $A k$ は $A$ から $k$ 個の列を取り除いて得られる任意の行列とする。 $P (A k)$ は $A k$ の行和の総乗とし、 $A k$ として考え得る全ての行列に亙って $P (A k)$ を加えた和を $Σ k$ と書けば、; $\operatorname {perm} (A)=\textstyle \sum \limits _{k=0}^{n-1}(-1)^{k}\Sigma _{k}$

が成り立つ。あるいはこれを行列の成分を陽に出して書けば

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

と書ける。

パーマネントの計算は行列式の場合に比べて複雑になると信じられている（例えば、行列式はガウスの消去法を用いて多項式時間で計算できるが、パーマネントはガウス消去では計算できない）。もっと言えば、 $(0, 1)$ -行列のパーマネントの計算は#P完全（英語版）である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、FP（英語版） = #P となるが、これは P = NP よりもいっそう強い主張である。しかし、 $A$ の成分が全て非負の場合、パーマネントは確率的多項式時間で近似的に計算することができる（その誤差は、パーマネントの値 $M$ と任意の $ε > 0$ に対する $εM$ に関するオーダーでとる）^[18]。半正定値行列のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる（この近似で達成可能な最良の誤差は $ε \sqrt M$ である。 $M$ はやはりパーマネントの値とする）^[19]。

マクマホンの基本定理編集

詳細は「マクマホンの基本定理（英語版）」を参照

パーマネントを多変数母函数を通じて解釈する視点もある。 $n$ 次正方行列 $A = (a ij)$ に対して、多変数母函数

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 )}

を考えると、 $F (x 1, x 2, \dots, x n)$ における $x_{1}x_{2}\dots x_{n}$ の係数は $perm(A)$ に等しい^[7]^:14。

このことの一般化として、

定義: 任意の長さ $n$ の非負整数列 $s_{1},s_{2},\dotsc ,s_{n}$ に対して
$\operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)$ を $\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}}$ における ${x_{1}}^{s_{1}}{x_{2}}^{s_{2}}\cdots {x_{n}}^{s_{n}}$ の係数
と定める。

定理 (MacMahon's Master Theorem): パーマネントと行列式の間の関係として、
「 $\operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)$ は ${\frac {1}{\det(I-XA)}}$ における ${x_{1}}^{s_{1}}{x_{2}}^{s_{2}}\cdots {x_{n}}^{s_{n}}$ の係数に等しい」
が成り立つ^[7]^:17。ただし、 $I$ は $n$ 次単位行列で、 $X$ は対角成分が $(x 1, x 2, \dots, x n)$ である対角行列とする。

矩形行列のパーマネント編集

パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合と見るものがある^[20]。具体的には、 $m \times n$ 行列 $A = (a ij)$ で $m \leq n$ とするとき、

\operatorname {perm} (A):=\textstyle \sum \limits _{\sigma \in P(n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\dotsc a_{m\sigma (m)}

と定める。ただし、 $P (n, m)$ は $n$ 元-集合 ${1, 2, \dots, n}$ から $m$ 元選ぶ部分置換（順列）全体の成す集合である^[6]^:25。

パーマネントに対するRyserの計算論的結果も一般化できる。 $A$ が $m \times n$ 行列 ( $m \leq n$ ) のとき、 $A$ から $k$ 個の列を取り除いて $A k$ が得られるとすると、 $A k$ の行和の積を $P (A k)$ , 可能な全ての $A k$ に対する $P (A k)$ の総和を $σ k$ と書けば、

\operatorname {perm} (A)=\textstyle \sum \limits _{k=0}^{m-1}(-1)^{k}{\dbinom {n-m+k}{k}}\sigma _{n-m+k}

が成り立つ^[6]^:26。

完全代表系編集

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

命題: （相異なるとは限らない） $S 1, S 2, \dots, S m$ は $n$ 元-集合の部分集合で、 $m \leq n$ とする。この部分集合族の接続行列 $A$ は $m \times n$ の $(0, 1)$ -行列である。この族の完全代表系（英語版）（systems of distinct representatives; 相異なる代表系、個別代表系; SDR）総数は $perm(A)$ である^[6]^:54。^{[注釈 3]}

注編集

[脚注の使い方]

注釈編集

^ 簡単な例を以下に示す:
${\begin{aligned}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{aligned}}$
^ 例えば、第一列に沿った展開：
${\begin{aligned}\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{aligned}}$
あるいは最終行に沿った展開：
${\begin{aligned}\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{aligned}}$
^ ホールの結婚定理も参照

出典編集

^ Marcus, Marvin; Minc, Henryk (1965). “Permanents”. Amer. Math. Monthly 72: 577-591. doi:10.2307/2313846.
^ 李磊、友田敏章、緑川章一、堀端孝俊「制限付き占有問題の簡単な計数公式」『日本応用数理学会論文誌』第7巻第4号、1997年、321-331頁、doi:10.11540/jsiamt.7.4_321。
^ 田端亮 (2014) (PDF). Immanant不等式とImmanantal Polynomials. 第19回代数若手研究会報告書.
^ Cauchy, A. L. (1815), “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.”, Journal de l'École Polytechnique 10: 91–169
^ ^a ^b ^c van Lint & Wilson 2001.
^ ^a ^b ^c ^d ^e ^f ^g ^h Ryser 1963.
^ ^a ^b ^c ^d ^e Percus 1971.
^ Aaronson, Scott (14 November 2010). "The Computational Complexity of Linear Optics". arXiv:1011.3245。
^ Bhatia, Rajendra (1997). Matrix Analysis. New York: Springer-Verlag. pp. 16-19. ISBN 0-387-94846-5
^ Minc, Henryk (1963), “Upper bounds for permanents of (0,1)-matrices”, Bulletin of the American Mathematical Society 69: 789-791, doi:10.1090/s0002-9904-1963-11031-9
^ van der Waerden, B. L. (1926), “Aufgabe 45”, Jber. Deutsch. Math.-Verein. 35: 117 .
^ Gyires, B. (1980), “The common source of several inequalities concerning doubly stochastic matrices”, Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis 27 (3-4): 291–304, MR604006 .
^ Egoryčev, G. P. (1980) (Russian), Reshenie problemy van-der-Vardena dlya permanentov, Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR602332 . Egorychev, G. P. (1981), “Proof of the van der Waerden conjecture for permanents” (Russian), Akademiya Nauk SSSR 22 (6): 65–71, 225, MR638007
^ Egorychev, G. P. (1981), “The solution of van der Waerden's problem for permanents”, Advances in Mathematics 42 (3): 299-305, doi:10.1016/0001-8708(81)90044-X, MR642395 .
^ Falikman, D. I. (1981), “Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix” (Russian), Akademiya Nauk Soyuza SSR 29 (6): 931-938, 957, MR625097 .
^ Brualdi 2006, p. 487.
^ Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
^ Jerrum, M.; Sinclair, A.; Vigoda, E. (2004), “A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries”, Journal of the ACM 51: 671-697, doi:10.1145/1008731.1008738
^ Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (2017). “A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices”. Phys. Rev. A 96 (2): 022329. arXiv:1609.02416. Bibcode: 2017PhRvA..96b2329C. doi:10.1103/PhysRevA.96.022329.
^ 特に Minc (1984) や Ryser (1963) ではそうなっている。

参考文献編集

Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001
Minc, Henryk (1978). Permanents. Encyclopedia of Mathematics and its Applications. 6. With a foreword by Marvin Marcus. Reading, MA: Addison–Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005
Muir, Thomas; William H. Metzler. (1960) [1882]. A Treatise on the Theory of Determinants. New York: Dover. OCLC 535903
Percus, J.K. (1971), Combinatorial Methods, Applied Mathematical Sciences #4, New York: Springer-Verlag, ISBN 0-387-90027-6
Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, The Mathematical Association of America
van Lint, J.H.; Wilson, R.M. (2001), A Course in Combinatorics, Cambridge University Press, ISBN 0521422604

外部リンク編集

『行列のパフィアン，パーマネント，ハフニアン』 - 高校数学の美しい物語
Weisstein, Eric W. "Permanent". mathworld.wolfram.com (英語).
permanent - PlanetMath.（英語）
Van der Waerden's permanent conjecture - PlanetMath.（英語）
Definition:Permanent at ProofWiki
Tarakanov, V. E. (2001), “Permanent”, in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

[8] 簡単な例を以下に示す:
${\begin{aligned}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{aligned}}$

[9] 例えば、第一列に沿った展開：
${\begin{aligned}\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{aligned}}$
あるいは最終行に沿った展開：
${\begin{aligned}\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{aligned}}$

[23] ホールの結婚定理も参照

[1] Marcus, Marvin; Minc, Henryk (1965). “Permanents”. Amer. Math. Monthly 72: 577-591. doi:10.2307/2313846.

[2] 李磊、友田敏章、緑川章一、堀端孝俊「制限付き占有問題の簡単な計数公式」『日本応用数理学会論文誌』第7巻第4号、1997年、321-331頁、doi:10.11540/jsiamt.7.4_321。

[3] 田端亮 (2014) (PDF). Immanant不等式とImmanantal Polynomials. 第19回代数若手研究会報告書.

[4] Cauchy, A. L. (1815), “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.”, Journal de l'École Polytechnique 10: 91–169

[FOOTNOTEvan_LintWilson2001-5] van Lint & Wilson 2001.

[FOOTNOTERyser1963-6] ^ ^a ^b ^c ^d ^e ^f ^g ^h Ryser 1963.

[FOOTNOTEPercus1971-7] Percus 1971.

[10] Aaronson, Scott (14 November 2010). "The Computational Complexity of Linear Optics". arXiv:1011.3245。

[11] Bhatia, Rajendra (1997). Matrix Analysis. New York: Springer-Verlag. pp. 16-19. ISBN 0-387-94846-5

[12] Minc, Henryk (1963), “Upper bounds for permanents of (0,1)-matrices”, Bulletin of the American Mathematical Society 69: 789-791, doi:10.1090/s0002-9904-1963-11031-9

[13] van der Waerden, B. L. (1926), “Aufgabe 45”, Jber. Deutsch. Math.-Verein. 35: 117 .

[14] Gyires, B. (1980), “The common source of several inequalities concerning doubly stochastic matrices”, Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis 27 (3-4): 291–304, MR604006 .

[15] Egoryčev, G. P. (1980) (Russian), Reshenie problemy van-der-Vardena dlya permanentov, Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., p. 12, MR602332 . Egorychev, G. P. (1981), “Proof of the van der Waerden conjecture for permanents” (Russian), Akademiya Nauk SSSR 22 (6): 65–71, 225, MR638007

[16] Egorychev, G. P. (1981), “The solution of van der Waerden's problem for permanents”, Advances in Mathematics 42 (3): 299-305, doi:10.1016/0001-8708(81)90044-X, MR642395 .

[17] Falikman, D. I. (1981), “Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix” (Russian), Akademiya Nauk Soyuza SSR 29 (6): 931-938, 957, MR625097 .

[FOOTNOTEBrualdi2006487-18] Brualdi 2006, p. 487.

[19] Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.

[20] Jerrum, M.; Sinclair, A.; Vigoda, E. (2004), “A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries”, Journal of the ACM 51: 671-697, doi:10.1145/1008731.1008738

[21] Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (2017). “A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices”. Phys. Rev. A 96 (2): 022329. arXiv:1609.02416. Bibcode: 2017PhRvA..96b2329C. doi:10.1103/PhysRevA.96.022329.

[22] 特に Minc (1984) や Ryser (1963) ではそうなっている。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[注釈 1]

[注釈 2]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

99

[18]

[19]

[20]

[注釈 3]

パーマネント (数学)

目次

定義編集

性質編集