トップQs
タイムライン
チャット
視点

パーマネント (数学)

ウィキペディアから

Remove ads

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

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

定義

要約
視点

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

Remove ads

性質

要約
視点

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

Remove ads

応用

要約
視点

行列式の場合とは違い、パーマネントは平易な幾何学的解釈はない。主な応用先として、組合せ論量子力学におけるボソンのグリーン関数の扱いにおいて、およびボソンサンプリング英語版システムの状態可能性の決定において[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次正方行列 A のパーマネントの定義

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

完全マッチング

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

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

Remove ads

二値行列のパーマネント

要約
視点

数え上げ

多くの数え上げ問題に 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次正方行列で、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 があるものとするとき、

が成り立つ。

Remove ads

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

Van der Waerden (1926)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]

Remove ads

マクマホンの基本定理

要約
視点

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

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

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

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

矩形行列のパーマネント

要約
視点

パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合と見るものがある[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]
Remove ads

関連項目

参考文献

関連文献

外部リンク

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads