ラプラス展開

Expression of a determinant in terms of minors

線型代数において、ピエール・シモン・ラプラスにちなんで名付けられたラプラス展開は、コファクター展開とも呼ばれ、 n × n行列Bの行列式を、Bのいくつかの( n − 1) × ( n − 1)部分行列の行列式である小行列式の重み付き和として表したものです。具体的には、すべてのiについて、i行目のラプラス展開は次の等式となります。ここで、 はBのi行目とj列目の要素であり、 はBのi行目とj列目を削除することによって得られる部分行列の行列式です。同様に、j列目のラプラス展開は次の等式となります(行列とその転置の行列式は同じなので、それぞれの恒等式は他方を意味します)。 $${\displaystyle {\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j},\end{aligned}}}$$ ${\displaystyle b_{i,j}}$ ${\displaystyle m_{i,j}}$ $${\displaystyle {\begin{aligned}\det(B)&=\sum _{i=1}^{n}(-1)^{i+j}b_{i,j}m_{i,j}.\end{aligned}}}$$

上記の合計におけるの係数は、 Bにおけるの余因子と呼ばれます。 ${\displaystyle (-1)^{i+j}m_{i,j}}$ ${\displaystyle b_{i,j}}$ ${\displaystyle b_{i,j}}$

ラプラス展開は、例えば行列の大きさに関する再帰的な計算を可能にするなど、証明においてしばしば有用です。また、その単純さ、そして行列式を考察し計算する複数の方法の一つとして、教育的にも興味深いものです。大きな行列の場合、ガウス消去法と比較すると、計算効率が急速に低下します。

例

マトリックスを考えてみましょう

${\displaystyle B={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.}$

この行列の行列式は、任意の行または列に沿ったラプラス展開を用いて計算できます。例えば、最初の行に沿った展開は次のようになります。

${\displaystyle {\begin{aligned}|B|&=1\cdot {\begin{vmatrix}5&6\\8&9\end{vmatrix}}-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+3\cdot {\begin{vmatrix}4&5\\7&8\end{vmatrix}}\\[5pt]&=1\cdot (-3)-2\cdot (-6)+3\cdot (-3)=0.\end{aligned}}}$

2列目に沿ったラプラス展開でも同じ結果が得られます。

${\displaystyle {\begin{aligned}|B|&=-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+5\cdot {\begin{vmatrix}1&3\\7&9\end{vmatrix}}-8\cdot {\begin{vmatrix}1&3\\4&6\end{vmatrix}}\\[5pt]&=-2\cdot (-6)+5\cdot (-12)-8\cdot (-6)=0.\end{aligned}}}$

結果が正しいことは簡単に確認できます。行列は、第 1 列と第 3 列の合計が第 2 列の 2 倍であるため特異であり、したがって行列式はゼロです。

証拠

はn × n行列であり、わかりやすくするために、その小行列を構成する要素を次のように ラベル付けする。 ${\displaystyle B}$ ${\displaystyle i,j\in \{1,2,\dots ,n\}.}$ ${\displaystyle B}$ ${\displaystyle i,j}$ ${\displaystyle M_{ij}}$

${\displaystyle (a_{st})}$のために ${\displaystyle 1\leq s,t\leq n-1.}$

を因数とする展開式の項を考えてみましょう。それぞれの項は次のようになります。 ${\displaystyle |B|}$ ${\displaystyle b_{ij}}$

${\displaystyle \operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{i,j}\cdots b_{n,\tau (n)}=\operatorname {sgn} \tau \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}}$

となるような何らかの順列 τ ∈ S _nに対して、τと同じマイナーエントリを選択する一意かつ明らかに関連のある順列が与えられる。同様に、 σの各選択は対応するτ を決定する。すなわち、対応はとの間の一対一対応である。コーシーの2行記法を用いると、との間の明示的な関係は次のように書ける。 ${\displaystyle \tau (i)=j}$ ${\displaystyle \sigma \in S_{n-1}}$ ${\displaystyle \sigma \leftrightarrow \tau }$ ${\displaystyle S_{n-1}}$ ${\displaystyle \{\tau \in S_{n}\colon \tau (i)=j\}.}$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$

${\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))\end{pmatrix}}}$

ここで、はサイクルの一時的な略記法です。この演算は、jより大きいすべてのインデックスをデクリメントし、すべてのインデックスが集合{1,2,...,n-1}に収まるようにします。 ${\displaystyle (\leftarrow )_{j}}$ ${\displaystyle (n,n-1,\cdots ,j+1,j)}$

順列τはσから以下のように導出できる。およびについてで定義する。すると は以下のように表される 。 ${\displaystyle \sigma '\in S_{n}}$ ${\displaystyle \sigma '(k)=\sigma (k)}$ ${\displaystyle 1\leq k\leq n-1}$ ${\displaystyle \sigma '(n)=n}$ ${\displaystyle \sigma '}$

${\displaystyle \sigma '={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}}$

さて、最初に適用してから適用する操作は（AをBの前に適用することは、2行表記でAの逆をBの上行に適用することと同じであることに注意してください） ${\displaystyle (\leftarrow )_{i}}$ ${\displaystyle \sigma '}$

${\displaystyle \sigma '(\leftarrow )_{i}={\begin{pmatrix}1&2&\cdots &i+1&\cdots &n&i\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}}$

ここで、 は の一時的な省略表記です。 ${\displaystyle (\leftarrow )_{i}}$ ${\displaystyle (n,n-1,\cdots ,i+1,i)}$

最初に適用され、次に適用される操作は ${\displaystyle \tau }$ ${\displaystyle (\leftarrow )_{j}}$

${\displaystyle (\leftarrow )_{j}\tau ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &n&\cdots &(\leftarrow )_{j}(\tau (n-1))&(\leftarrow )_{j}(\tau (n))\end{pmatrix}}}$

上記の2つは等しいので、

${\displaystyle (\leftarrow )_{j}\tau =\sigma '(\leftarrow )_{i}}$

${\displaystyle \tau =(\rightarrow )_{j}\sigma '(\leftarrow )_{i}}$

ここでは の逆数であり、は です。 ${\displaystyle (\rightarrow )_{j}}$ ${\displaystyle (\leftarrow )_{j}}$ ${\displaystyle (j,j+1,\cdots ,n)}$

したがって

${\displaystyle \tau \,=(j,j+1,\ldots ,n)\sigma '(n,n-1,\ldots ,i)}$

2つのサイクルはそれぞれ転置と書き表すことができるので、 ${\displaystyle n-i}$ ${\displaystyle n-j}$

${\displaystyle \operatorname {sgn} \tau \,=(-1)^{2n-(i+j)}\operatorname {sgn} \sigma '\,=(-1)^{i+j}\operatorname {sgn} \sigma .}$

そして、写像は単射なので、 ${\displaystyle \sigma \leftrightarrow \tau }$

${\displaystyle {\begin{aligned}\sum _{i=1}^{n}\sum _{\tau \in S_{n}:\tau (i)=j}\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{n,\tau (n)}&=\sum _{i=1}^{n}\sum _{\sigma \in S_{n-1}}(-1)^{i+j}\operatorname {sgn} \sigma \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}\sum _{\sigma \in S_{n-1}}\operatorname {sgn} \sigma \,a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}M_{ij}\end{aligned}}}$

そこから結果が導かれる。同様に、外側の和の添え字を に置き換えても結果は成り立つ。^[1] ${\displaystyle j}$

補小行列式による行列式のラプラス展開

ラプラスの余因子展開は次のように一般化できます。

例

マトリックスを考えてみましょう

${\displaystyle A={\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}}.}$

この行列の行列式は、最初の2行に沿ってラプラスの余因子展開を用いることで、以下のように計算できます。まず、{1, 2, 3, 4}には2つの異なる数の集合が6つあることに注意してください。つまり、{1, 2, 3, 4}を前述の集合とします。 ${\displaystyle S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}}$

相補的補因子を次のように定義することにより

${\displaystyle b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}},}$

${\displaystyle c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}},}$

そしてそれらの順列の符号は

${\displaystyle \varepsilon ^{\{j,k\},\{p,q\}}=\operatorname {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ where }}p\neq j,q\neq k.}$

Aの行列式は次のように表される。

${\displaystyle |A|=\sum _{H\in S}\varepsilon ^{H,H^{\prime }}b_{H}c_{H^{\prime }},}$

ここでは の補集合です。 ${\displaystyle H^{\prime }}$ ${\displaystyle H}$

明示的な例では、

${\displaystyle {\begin{aligned}|A|&=b_{\{1,2\}}c_{\{3,4\}}-b_{\{1,3\}}c_{\{2,4\}}+b_{\{1,4\}}c_{\{2,3\}}+b_{\{2,3\}}c_{\{1,4\}}-b_{\{2,4\}}c_{\{1,3\}}+b_{\{3,4\}}c_{\{1,2\}}\\[5pt]&={\begin{vmatrix}1&2\\5&6\end{vmatrix}}\cdot {\begin{vmatrix}11&12\\15&16\end{vmatrix}}-{\begin{vmatrix}1&3\\5&7\end{vmatrix}}\cdot {\begin{vmatrix}10&12\\14&16\end{vmatrix}}+{\begin{vmatrix}1&4\\5&8\end{vmatrix}}\cdot {\begin{vmatrix}10&11\\14&15\end{vmatrix}}+{\begin{vmatrix}2&3\\6&7\end{vmatrix}}\cdot {\begin{vmatrix}9&12\\13&16\end{vmatrix}}-{\begin{vmatrix}2&4\\6&8\end{vmatrix}}\cdot {\begin{vmatrix}9&11\\13&15\end{vmatrix}}+{\begin{vmatrix}3&4\\7&8\end{vmatrix}}\cdot {\begin{vmatrix}9&10\\13&14\end{vmatrix}}\\[5pt]&=-4\cdot (-4)-(-8)\cdot (-8)+(-12)\cdot (-4)+(-4)\cdot (-12)-(-8)\cdot (-8)+(-4)\cdot (-4)\\[5pt]&=16-64+48+48-64+16=0.\end{aligned}}}$

上記のように、結果が正しいことは簡単に確認できます。行列は、第 1 列と第 3 列の合計が第 2 列の 2 倍であるため特異であり、したがって行列式はゼロです。

一般的な声明

n × n行列と、{ 1, 2, ... , n }のk要素部分集合の集合をその要素とする。すると、 の行列式は、によって識別されるk行に沿って次のように展開できる。 ${\displaystyle B=[b_{ij}]}$ ${\displaystyle S}$ ${\displaystyle H}$ ${\displaystyle B}$ ${\displaystyle H}$

${\displaystyle |B|=\sum _{L\in S}\varepsilon ^{H,L}b_{H,L}c_{H,L}}$

ここで、 は、によって決定される置換の符号であり、 に等しく、の行と列から を削除することによって得られるの平方小数点であり、（ の補集合と呼ばれる）は と定義され、はそれぞれと の補集合です。 ${\displaystyle \varepsilon ^{H,L}}$ ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle (-1)^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ell \right)}}$ ${\displaystyle b_{H,L}}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle c_{H,L}}$ ${\displaystyle b_{H,L}}$ ${\displaystyle b_{H',L'}}$ ${\displaystyle H'}$ ${\displaystyle L'}$ ${\displaystyle H}$ ${\displaystyle L}$

これは、 のときの上記の定理と一致します。任意の固定されたk列に対しても同じことが当てはまります。 ${\displaystyle k=1}$

計算コスト

ラプラス展開は高次元行列に対しては計算効率が悪く、大文字小文字表記では計算時間がO ( n !)となります。一方、 LU分解のように三角行列への分解を用いると、計算時間がO ( n ³ )の行列式を得ることができます。^[2]以下のPythonコードはラプラス展開を実装しています。

def determinant ( M ): # 再帰関数の基本ケース: 1x1行列if len ( M ) == 1 : return M [ 0 ][ 0 ]         total  =  0  for  column ,  element  in  enumerate ( M [ 0 ]):  # 最初の行と現在の列を除外します。 K  =  [ x [: column ]  +  x [ column  +  1  :]  for  x  in  M [ 1 :]]  s  =  1  if  column  %  2  ==  0  else  - 1  total  +=  s  *  element  *  determinant ( K )  return  total

参照

• 数学ポータル

• 行列式のライプニッツ公式
• 行列式に関するサラスの法則 ${\displaystyle 3\times 3}$

参考文献

1. ウォルター, ダン; タイタン, アレックス (1949). 「初等問題834」.アメリカ数学月刊. 56 (6). アメリカ数学会誌: 409. doi :10.2307/2306289. JSTOR  2306289.
2. Stoer Bulirsch: 数値数学入門

• デイヴィッド・プール：線形代数 現代入門 センゲージ・ラーニング 2005年ISBN 0-534-99845-3、pp. 265–267（オンライン限定コピー、p. 265、Google Books）
• ハーヴェイ・E・ローズ『線形代数：純粋数学的アプローチ』Springer 2002年、ISBN 3-7643-6905-1、pp. 57–60（限定オンラインコピー、p. 57、Googleブックス）

Retrieved from "https://en.wikipedia.org/w/index.php?title=Laplace_expansion&oldid=1325325296"