ラプラス展開

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

係数${\displaystyle (-1)^{i+j}m_{i,j}}$の${\displaystyle b_{i,j}}$上記の和では、はのコファクターと呼ばれます。${\displaystyle b_{i,j}}$Bにおいて。

ラプラス展開は、例えば行列のサイズに関する再帰を可能にするなど、証明においてしばしば有用です。また、その簡潔さや、行列式を視覚化・計算する複数の方法の一つとして、教育的な観点からも興味深いものです。しかし、大きな行列の場合、ガウス消去法と比較すると、計算効率が著しく低下します。

行列を考える

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

この行列の行列式は、その行または列のいずれか1つに沿ってラプラス展開を用いることで計算できます。例えば、1行目に沿って展開すると次のようになります。

${\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倍であるため特異行列であり、したがって行列式はゼロになります。

仮定する${\displaystyle B}$n × n行列であり、${\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に対して${\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\}.}$コーシーの2行記法 を用いると、 と の間の明示的な関係は次のようになる。${\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}}}$

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

置換τはσから次のように導出できる。${\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}}}$

さて、適用する操作は${\displaystyle (\leftarrow )_{i}}$まず適用し、次に適用します${\displaystyle \sigma '}$（AをBの前に適用することは、2行表記でBの上段にAの逆演算を適用することと同等であることに注意してください。）

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

上記２つは等しいので、

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

そこから結果が導かれる。同様に、外側の総和のインデックスを に置き換えた場合も結果は成り立つ。${\displaystyle j}$[ ^{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}$決定要因

• デイビッド・プール著：線形代数：現代的入門。Cengage Learning、2005年、ISBN 0-534-99845-3、265～267ページ （Googleブックスでは265ページのみ閲覧可能）
• ハーヴェイ・E・ローズ：線形代数。純粋数学的アプローチ。シュプリンガー、2002年、ISBN 3-7643-6905-1、57～60ページ （Googleブックスでは57ページのみ閲覧可能）