パーマネント (数学)
↑ 例えば、第一列に沿った展開: perm ( 1 1 1 1 2 1 0 0 3 0 1 0 4 0 0 1 ) = 1 ⋅ perm ( 1 0 0 0 1 0 0 0 1 ) + 2 ⋅ perm ( 1 1 1 0 1 0 0 0 1 ) + 3 ⋅ perm ( 1 1 1 1 0 0 0 0 1 ) + 4 ⋅ perm ( 1 1 1 1 0 0 0 1 0 ) = 1 ( 1 ) + 2 ( 1 ) + 3 ( 1 ) + 4 ( 1 ) = 10 , {\displaystyle {\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}}} あるいは最終行に沿った展開: perm ( 1 1 1 1 2 1 0 0 3 0 1 0 4 0 0 1 ) = 4 ⋅ perm ( 1 1 1 1 0 0 0 1 0 ) + 0 ⋅ perm ( 1 1 1 2 0 0 3 1 0 ) + 0 ⋅ perm ( 1 1 1 2 1 0 3 0 0 ) + 1 ⋅ perm ( 1 1 1 2 1 0 3 0 1 ) = 4 ( 1 ) + 0 + 0 + 1 ( 6 ) = 10.
完全順列の場合、n元-集合において不動点が一つもない置換の総数は
perm  ( J − I ) = perm ( 0 1 1 ... 1 1 0 1 ... 1 1 1 0 ... 1 ⋮ ⋮ ⋮ ⋱ ⋮ 1 1 1 ... 0 ) = n ! ∑ i = 0 n ( − 1 ) i i ! {\displaystyle \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次単位行列である。一方、メナージュ問題の場合の数(メナージュ数(英語版))は
perm  ( J − I − I ′ ) = perm ( 0 0 1 .
↑ 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) ではそうなっている。
bnf.fr/ark:/12148/bpt6k90193x/f97
1 2 3 van Lint & Wilson 2001.
1 2 3 4 5 6 7 8 Ryser 1963.
1 2 3 4 5 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 .
n次正方行列 A ≔ (ai,j) のパーマネントは
perm  ( A ) := ∑ σ ∈ S n ∏ i = 1 n a i , σ ( i ) {\displaystyle \operatorname {perm} (A):=\textstyle \sum \limits _{\sigma \in S_{n}}\prod \limits _{i=1}^{n}a_{i,\sigma (i)}}
で与えられる。右辺の和は、対称群 Sn の任意の元 σ(つまり、番号 1, 2, ..., n の置換)に亙ってとるものとする。
例えば、二次正方行列に対しては
perm ( a b c d ) = a d + b c {\displaystyle \operatorname {perm} \!{\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc}
であり、三次正方行列に対しては
perm ( a b c d e f g h i ) = a e i + b f g + c d h + c e g + b d i + a f h {\displaystyle \operatorname {perm} \!{\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh}
パーマネントを n本の列(または行)ベクトルを引数にとる写像と見るとき、多重線型対称形式(英語版)(引数となるベクトルの順番を入れ替えても結果は変わらない)である。より具体的に、n次正方行列 A = (aij) に対して以下が成り立つ:
perm(A) は A の行または列ベクトルに関する任意の置換の下で不変である。この性質を任意の置換行列 P, Q を用いて perm(A) = perm(PAQ) という形で記号的に表せる。
A の任意の一つの行または列にスカラー s を掛けるとき、perm(A) は s⋅perm(A) に写る。
perm(A) は転置の下で不変:perm(A) = perm(A).
n次正方行列 A ≔ (aij), B ≔ (bij) に対し