パーマネント (数学)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

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

定義[編集]

n × n 行列 A := (ai,j) のパーマネントは

で与えられる。右辺の和は、対称群 Sn の任意の元 σ(つまり、番号 1, 2, …, n置換)に亙ってとるものとする。

例えば、任意の二次正方行列に対して

であり、任意の三次正方行列に対して
となる。

A のパーマネントの定義において、A の行列式のそれと異なる点は、各置換(に対応する項)に対して行列式が置換の符号を考慮するのに対してパーマネントは考慮しないことである。

行列 A のパーマネントは記号で per A, perm A, Per A などと書く(引数をパーレンで括ることもある)。Minc (1984)A が矩形行列の場合に Per(A), 正方行列には per(A) と使い分けている。Muir (1882) で括る記法を用いている。

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

性質[編集]

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

  • 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) に対し

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

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

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

応用[編集]

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

対称テンソル[編集]

パーマネントはヒルベルト空間上の対称テンソル冪の研究において自然に生じてくる[9]。具体的に、H をヒルベルト空間とし、その対称テンソル全体の成す空間である対称テンソル冪を と書くと、特に H の元からなる対称(テンソル)積によって生成されることに注意する。x1, x2, …, xkH の対称積は

と定義される。 を(Hk-次テンソル冪英語版 の部分空間として)考えるとき、その上に内積 , が定義されれば、それに応じて
となることが分かる。コーシー–シュヴァルツの不等式を適用すれば、 および
が確かめられる。

閉路被覆[編集]

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

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

と書ける。n × n 行列 A のパーマネントの定義
σ{1, 2, …, n} 上の置換)と比較すれば、隣接行列 A のパーマネントが、対応する有向グラフの閉路被覆すべてに亙る重み付き和に等しいことが分かる。

完全マッチング[編集]

任意の正方行列 A := (aij) を、頂点集合 {x1, x2, xn} および {y1, y2, …, yn} を持つ二部グラフで、頂点 xi から頂点 yj へ結んだ辺の重みが aij であるようなものの隣接行列と見ることもできる。xiyj にマッチさせる 完全マッチング英語版 σ の重みを、このマッチングに現れる辺すべての重みの総乗と定義するならば

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

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

数え上げ[編集]

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

Ω(n,k)n-次 (0, 1)-値の行列で各行各列の成分の和が k に等しいもの全体の成すクラスとする。このクラスに属する任意の行列 Aperm(A) > 0 である[6]:124射影平面接続行列は、適当な整数 n > 1 に対するクラス Ω(n2 + n + 1, n + 1) に属する。最小の射影平面に対応するパーマネントは計算されており、n = 2, 3, 4 に対してその値はそれぞれ 24, 3852, 18,534,400 となる[6]:124n = 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 を行列 Ze 個のコピーの直和の形にすることができて、したがって n = 7e および perm(A) = 24e となる。

位置の制限(禁止)を含む置換の総数の計算にもパーマネント は利用できる。標準 n-元集合 {1, 2, …, n} に対して、A = (aij) を、各 aij は素の置換で ij と写せるならば 1, さもなくば 0 と定めて得られる (0, 1)-行列とするとき、perm(A) は標準 n-元集合上でこれらの制限をすべて満足する置換の総数に等しい[7]:12。このような例としてよく知られた特別の場合が、完全順列問題(不動点を全く持たない場合)とメナージュの問題英語版problème des ménages: 複数の男女カップルがどの組もパートナー同士が隣り合うことなく円卓に着席する場合の数を求める)である。完全順列の場合、n-元集合において不動点が一つもないような置換の総数は

で与えられる。ただし J は全ての成分が 1n × n 行列で、In-次単位行列である。いっぽう、メナージュ問題の場合の数(メナージュ数英語版)は
で与えられる。ただし、I′(i, i + 1)-成分および (n, 1)-成分のみが非零であるような (0, 1)-行列とする。

上界[編集]

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

定理 (Bregman–Minc inequality)
1 ≤ in に対して、A の第 i-行には ri 個の 1 があるものとするとき、
が成り立つ。

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

Van der Waerden (1926)n × n 二重確率行列の中で最小のパーマネントは n!/nn で、それは全ての成分が 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]

計算[編集]

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

主張
AkA から k 個の列を取り除いて得られる任意の行列とする。P(Ak)Ak の行和の総乗とし、Ak として考え得るすべての行列に亙って P(Ak) を加えた和を Σk と書けば、
が成り立つ。あるいはこれを行列の成分を陽に出して書けば
と書ける。

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

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

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

を考えると、F(x1, x2, …, xn) における の係数は perm(A) に等しい[7]:14

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

定義
任意の長さ n の非負整数列 に対して
における の係数
と定める。
定理 (MacMahon's Master Theorem)
パーマネントと行列式の間の関係として、
における の係数に等しい」
が成り立つ[7]:17。ただし、In-次単位行列で、X は対角成分が (x1, x2, …, xn) である対角行列とする。

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

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

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

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

が成り立つ[6]:26

完全代表系[編集]

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

命題
(相異なるとは限らない)S1, S2, …, Smn-元集合の部分集合で、mn とする。この部分集合族の接続行列 Am × n(0, 1)-行列である。この族の完全代表系英語版 (systems of distinct representatives; 相異なる代表系、個別代表系; SDR) の総数は perm(A) である[6]:54[注釈 3]

関連項目[編集]

[編集]

[ヘルプ]

注釈[編集]

  1. ^ 簡単な例を以下に示す:
  2. ^ 例えば、第一列に沿った展開:
    あるいは最終行に沿った展開:
  3. ^ ホールの結婚定理も参照

出典[編集]

  1. ^ Marcus, Marvin; Minc, Henryk (1965). “Permanents”. Amer. Math. Monthly 72: 577–591. doi:10.2307/2313846. http://www.maa.org/programs/maa-awards/writing-awards/permanents. 
  2. ^ 李 磊, 友田 敏章, 緑川 章一, 堀端 孝俊「制限付き占有問題の簡単な計数公式」『日本応用数理学会論文誌』第7巻第4号、1997年、 321-331頁、 doi:10.11540/jsiamt.7.4_321
  3. ^ 田端亮 (2014) (PDF). Immanant不等式とImmanantal Polynomials. 第19回代数若手研究会 報告書. http://math.shinshu-u.ac.jp/~maekawa/wakate2014/proceedings/tabata_proceedings.pdf. 
  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, http://gallica.bnf.fr/ark:/12148/bpt6k90193x/f97 
  5. ^ a b c van Lint & Wilson 2001.
  6. ^ a b c d e f g h Ryser 1963.
  7. ^ a b c d e Percus 1971.
  8. ^ Aaronson, Scott (2010年11月14日). “The Computational Complexity of Linear Optics”. arXiv:1011.3245. 
  9. ^ Bhatia, Rajendra (1997). Matrix Analysis. New York: Springer-Verlag. pp. 16–19. ISBN 0-387-94846-5. 
  10. ^ 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 
  11. ^ van der Waerden, B. L. (1926), “Aufgabe 45”, Jber. Deutsch. Math.-Verein. 35: 117 .
  12. ^ 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 .
  13. ^ 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 
  14. ^ 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 .
  15. ^ 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 .
  16. ^ Brualdi 2006, p. 487.
  17. ^ Fulkerson Prize, Mathematical Optimization Society, retrieved 2012-08-19.
  18. ^ 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 
  19. ^ 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. Bibcode2017PhRvA..96b2329C. doi:10.1103/PhysRevA.96.022329. 
  20. ^ 特に 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 

関連文献[編集]

  • Hall, Jr., Marshall (1986), Combinatorial Theory (2nd ed.), New York: John Wiley & Sons, pp. 56–72, ISBN 0-471-09138-3  Contains a proof of the Van der Waerden conjecture.
  • Marcus, M.; Minc, H. (1965), “Permanents”, The American Mathematical Monthly 72: 577–591, doi:10.2307/2313846 

外部リンク[編集]