余因子展開(cofactor expansion)とは、可換環上の $n$ 次正方行列 $A$ の行列式を、ある行または列の成分とその余因子 $C_{ij}=(-1)^{i+j}\det M_{ij}$ の積の和 $\det A=\sum_ja_{ij}C_{ij}$ として表す公式である。ここで $M_{ij}$ は第 $i$ 行と第 $j$ 列を除いた行列である。$k$ 本の行をまとめて、$k$ 次の小行列式と補小行列式の積の和で表す一般の Laplace 展開もある。$n$ 次の行列式を低い次数に帰着させ、余因子行列による逆行列の公式の基礎になる。
$3$ 次の行列式は、第 1 行の成分に $2$ 次の行列式を掛けて足すことで計算できる。
$$
\det\begin{pmatrix}2&0&1\\1&3&0\\0&5&4\end{pmatrix}
=2\det\begin{pmatrix}3&0\\5&4\end{pmatrix}-0\det\begin{pmatrix}1&0\\0&4\end{pmatrix}+1\det\begin{pmatrix}1&3\\0&5\end{pmatrix}=24+5=29
$$
各成分には、その行と列を取り除いた行列の行列式が掛かり、符号が $+,-,+$ と交互に付く。同じことは、どの行でも、どの列でもできる。第 2 列なら、$0$ が 1 つあるので項が 2 つで済み、$3\cdot8+5\cdot1=29$ となる。これを 余因子展開(cofactor expansion)といい、Laplace 展開ともいう。
余因子展開は、$n$ 次の行列式を $n-1$ 次の行列式に帰着させる公式である。$0$ の多い行や列を選べば手計算が楽になり、理論の上では、三重対角の行列式の漸化式や、余因子行列による逆行列の公式の出発点になる。複数の行をまとめて同時に展開する一般の形もある。
この記事では、Leibniz の公式の項を行と列の位置で分類して、$1$ 本の行・列についての展開と、複数の行・列についての一般の Laplace 展開を証明する。成分は可換環にあればよい。余因子を並べた行列と逆行列の公式は 余因子行列 の記事が扱う。
以下、$R$ は単位元をもつ可換環、$A=(a_{ij})$ は $R$ の元を成分とする $n$ 次正方行列で、$n\ge2$ とする。行列式は Leibniz の公式
$$
\det A=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\,a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}
$$
で定め、符号は転倒数で $\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}$ と定める(置換の符号 の定義「転倒数と置換の符号」)。
$A$ から第 $i$ 行と第 $j$ 列を取り除いた $n-1$ 次正方行列を $M_{ij}$ と書く。その行列式 $\det M_{ij}$ が $A$ の $(i,j)$ 小行列式であり、
$$
C_{ij}:=(-1)^{i+j}\det M_{ij}
$$
を $A$ の $(i,j)$ 余因子(cofactor)という。
符号 $(-1)^{i+j}$ は、$(1,1)$ 成分の位置を $+$ とする市松模様である。$M_{ij}$ の行と列はもとの順番のまま並べる。
$$
\begin{pmatrix}+&-&+&\cdots\\-&+&-&\cdots\\+&-&+&\cdots\\\vdots&\vdots&\vdots&\ddots\end{pmatrix}
$$
余因子は、Leibniz の公式の項のうち特定の成分を含むものをまとめたものである。これがすべての出発点になる。
$1\le i,j\le n$ について
$$
\sum_{\sigma\in S_n,\ \sigma(i)=j}\operatorname{sgn}(\sigma)\prod_{k=1}^na_{k\sigma(k)}=a_{ij}C_{ij}
$$
である。
$\alpha\colon[n-1]\to[n]\setminus\{i\}$、$\beta\colon[n-1]\to[n]\setminus\{j\}$ を増加する全単射とする。$M_{ij}$ の $(l,t)$ 成分は $a_{\alpha(l)\beta(t)}$ である。$\sigma(i)=j$ となる $\sigma$ に $\tau:=\beta^{-1}\sigma\alpha\in S_{n-1}$ を対応させると、これは $\{\sigma\mid\sigma(i)=j\}$ から $S_{n-1}$ への全単射で、
$$
\prod_{k\ne i}a_{k\sigma(k)}=\prod_{l=1}^{n-1}(M_{ij})_{l\tau(l)}
$$
である。
$\sigma$ の転倒のうち、番号 $i$ を含まないものは、$\alpha,\beta$ が順序を保つので $\tau$ の転倒と 1 対 1 に対応する。番号 $i$ を含む転倒の個数は $p+q$ である。ここで
$$
p:=\#\{k< i\mid\sigma(k)>j\},\qquad q:=\#\{k>i\mid\sigma(k)< j\}
$$
とおいた。$\sigma(k)< j$ となる $k$ はちょうど $j-1$ 個で、そのうち $k< i$ のものは $(i-1)-p$ 個、$k>i$ のものは $q$ 個である。よって $j-1=i-1-p+q$、すなわち $q-p=j-i$ であり、$p+q\equiv i+j\pmod2$ である。したがって $\operatorname{sgn}(\sigma)=(-1)^{i+j}\operatorname{sgn}(\tau)$ であり、
$$
\sum_{\sigma(i)=j}\operatorname{sgn}(\sigma)\prod_ka_{k\sigma(k)}=a_{ij}(-1)^{i+j}\sum_{\tau\in S_{n-1}}\operatorname{sgn}(\tau)\prod_l(M_{ij})_{l\tau(l)}=a_{ij}C_{ij}
$$
である。$\square$
任意の $i$ について、第 $i$ 行についての展開
$$
\det A=\sum_{j=1}^na_{ij}C_{ij}
$$
が成り立ち、任意の $j$ について、第 $j$ 列についての展開
$$
\det A=\sum_{i=1}^na_{ij}C_{ij}
$$
が成り立つ。
$i$ を固定すると、各 $\sigma\in S_n$ について $j:=\sigma(i)$ がただ 1 つ定まるので、$S_n$ は $\{\sigma\mid\sigma(i)=j\}$($j=1,\dots,n$)に分割される。Leibniz の公式の和をこの分割に沿って分け、lem-ce-key を使うと第 $i$ 行についての展開を得る。
$j$ を固定すると、各 $\sigma$ について $\sigma(i)=j$ となる $i$ がただ 1 つ定まるので、$S_n$ は $\{\sigma\mid\sigma(i)=j\}$($i=1,\dots,n$)に分割される。同じく lem-ce-key から第 $j$ 列についての展開を得る。$\square$
lem-ce-key の証明は体の性質を使っていないので、定理は任意の可換環の上で成り立つ。
定理は DF04 §11.4 の Theorem 29(pp. 439–440)に行の形で、Lan02 Ch. XIII §4 の Proposition 4.10(p. 516)に行と列の形である。Lan02 p. 515 は、展開の右辺で行列式を帰納的に構成し、多重線形で交代的であることを確かめている。Leibniz の公式を使わない行列式の作り方である。DF04 も、右辺が行列式の公理を満たすことを $n$ についての帰納法で示している。
lem-ce-key は、$a_{ij}C_{ij}$ が行列式の中で $a_{ij}$ を含む項のすべてであることを述べている。$C_{ij}$ は第 $i$ 行と第 $j$ 列の成分を含まないので、次のように言い換えられる。
$\det A$ を成分 $a_{kl}$ の多項式とみると、$a_{ij}$ について 1 次以下で、$a_{ij}$ の係数が $C_{ij}$ である。すなわち $\det A=a_{ij}C_{ij}+(a_{ij}$ を含まない項$)$ であり、$\partial\det A/\partial a_{ij}=C_{ij}$ である。
Leibniz の公式の各項は第 $i$ 行の成分をちょうど 1 つ含むので、$a_{ij}$ を含む項は $\sigma(i)=j$ となる項に限られる。それらの和は lem-ce-key により $a_{ij}C_{ij}$ で、$C_{ij}$ は第 $i$ 行の成分を含まない。$\square$
行列の成分が変数 $t$ の関数のときの微分の公式は、余因子行列 の命題「行列式の偏微分と Jacobi の公式」にある。
対角成分が $a_1,\dots,a_k$、そのすぐ上の成分が $b_1,\dots,b_{k-1}$、すぐ下の成分が $c_1,\dots,c_{k-1}$、ほかの成分が $0$ である $k$ 次正方行列の行列式を $D_k$ とする($D_0:=1$、$D_1=a_1$)。$k\ge2$ のとき、最後の行についての展開で
$$
D_k=a_kD_{k-1}-b_{k-1}c_{k-1}D_{k-2}
$$
である。実際、最後の行の $0$ でない成分は $(k,k)$ 成分 $a_k$ と $(k,k-1)$ 成分 $c_{k-1}$ だけである。$(k,k-1)$ 余因子は符号が $-1$ で、第 $k$ 行と第 $k-1$ 列を除いた行列の最後の列は $b_{k-1}$ を最後の成分にもつ以外は $0$ なので、もう一度展開すると $b_{k-1}D_{k-2}$ になる。
たとえば $a_l=1$、$b_l=1$、$c_l=-1$ なら $D_k=D_{k-1}+D_{k-2}$ で、$D_k$ は Fibonacci数 $F_{k+1}$ に等しい。$a_l=2$、$b_l=c_l=-1$ なら $D_k=2D_{k-1}-D_{k-2}$ で、$D_k=k+1$ である。
第 2 行に $0$ が多い行列
$$
A=\begin{pmatrix}1&2&0&3\\0&0&2&0\\4&1&5&0\\1&0&0&1\end{pmatrix}
$$
では、第 2 行についての展開は $(2,3)$ 成分の項だけが残り、$\det A=2\cdot(-1)^{2+3}\det M_{23}=-2\det\begin{pmatrix}1&2&3\\4&1&0\\1&0&1\end{pmatrix}$ である。右の行列式を第 2 列について展開すると $-2\det\begin{pmatrix}4&0\\1&1\end{pmatrix}+\det\begin{pmatrix}1&3\\1&1\end{pmatrix}=-8-2=-10$ なので、$\det A=20$ である。
$1$ 本の行の代わりに $k$ 本の行をまとめて選ぶと、$k$ 次の小行列式とその補小行列式の積の和で行列式が表せる。部分集合 $I\subset[n]$ について、$s(I):=\sum_{i\in I}i$、$I^{c}:=[n]\setminus I$ と書く。$A[I,J]$ は第 $I$ 行と第 $J$ 列を番号順に残した小行列である(小行列式 の定義「小行列と小行列式」)。
$1\le k\le n-1$ とする。$k$ 元部分集合 $I\subset[n]$ を固定すると
$$
\det A=\sum_{J\subset[n],\ |J|=k}(-1)^{s(I)+s(J)}\det A[I,J]\,\det A[I^{c},J^{c}]
$$
であり、$k$ 元部分集合 $J$ を固定すると
$$
\det A=\sum_{I\subset[n],\ |I|=k}(-1)^{s(I)+s(J)}\det A[I,J]\,\det A[I^{c},J^{c}]
$$
である。
$I=\{i_1< \dots< i_k\}$、$I^{c}=\{c_1< \dots< c_{n-k}\}$ とし、$\pi_I\in S_n$ を $\pi_I(a):=i_a$($a\le k$)、$\pi_I(k+b):=c_b$ で定める。$\pi_I$ の転倒は $a\le k< k+b$ で $i_a>c_b$ となる組であり、$i_a$ より小さい $I^{c}$ の元は $i_a-a$ 個なので、$\operatorname{inv}(\pi_I)=\sum_a(i_a-a)=s(I)-k(k+1)/2$ である。
$\sigma(I)=J$ となる $\sigma$ について、$\rho:=\pi_J^{-1}\sigma\pi_I$ は $[k]$ をそれ自身に写す。したがって $\rho$ は、$\rho_1\in S_k$ と、$\rho(k+b)=k+\rho_2(b)$ で定まる $\rho_2\in S_{n-k}$ の組に対応し、これは $\{\sigma\mid\sigma(I)=J\}$ から $S_k\times S_{n-k}$ への全単射である。$\rho$ には前半と後半にまたがる転倒がないので $\operatorname{sgn}(\rho)=\operatorname{sgn}(\rho_1)\operatorname{sgn}(\rho_2)$ であり、符号の乗法性から
$$
\operatorname{sgn}(\sigma)=\operatorname{sgn}(\pi_J)\operatorname{sgn}(\rho)\operatorname{sgn}(\pi_I)=(-1)^{s(I)+s(J)-k(k+1)}\operatorname{sgn}(\rho_1)\operatorname{sgn}(\rho_2)=(-1)^{s(I)+s(J)}\operatorname{sgn}(\rho_1)\operatorname{sgn}(\rho_2)
$$
である。$J=\{j_1< \dots< j_k\}$、$J^{c}=\{d_1< \dots< d_{n-k}\}$ と書くと、$\sigma\pi_I=\pi_J\rho$ から $\sigma(i_a)=j_{\rho_1(a)}$、$\sigma(c_b)=d_{\rho_2(b)}$ なので
$$
\prod_{l=1}^na_{l\sigma(l)}=\prod_{a=1}^ka_{i_aj_{\rho_1(a)}}\prod_{b=1}^{n-k}a_{c_bd_{\rho_2(b)}}
$$
である。$(\rho_1,\rho_2)$ について足すと
$$
\sum_{\sigma(I)=J}\operatorname{sgn}(\sigma)\prod_la_{l\sigma(l)}=(-1)^{s(I)+s(J)}\det A[I,J]\,\det A[I^{c},J^{c}]
$$
を得る。$I$ を固定すれば $S_n$ は $J=\sigma(I)$ で分割され、$J$ を固定すれば $I=\sigma^{-1}(J)$ で分割されるので、どちらの展開も Leibniz の公式から従う。$\square$
$k=1$、$I=\{i\}$、$J=\{j\}$ では $(-1)^{i+j}a_{ij}\det M_{ij}$ となり、thm-ce-main に戻る。
Bou89 Ch. III §8 no. 6 の式 (21) が、外積代数を使って導いた同じ公式で、$k$ 本の列についての Laplace 展開と呼んでいる。
$$
A=\begin{pmatrix}1&0&2&0\\0&1&0&3\\1&1&1&0\\0&2&1&1\end{pmatrix}
$$
で $I=\{1,2\}$ とする。$s(I)=3$ である。第 1・2 行の $2$ 次の小行列式と、第 3・4 行の補小行列式は次のとおりである。
| $J$ | 符号 | $\det A[I,J]$ | $\det A[I^{c},J^{c}]$ | 積 |
|---|---|---|---|---|
| $\{1,2\}$ | $+$ | $1$ | $1$ | $1$ |
| $\{1,3\}$ | $-$ | $0$ | $1$ | $0$ |
| $\{1,4\}$ | $+$ | $3$ | $-1$ | $-3$ |
| $\{2,3\}$ | $+$ | $-2$ | $1$ | $-2$ |
| $\{2,4\}$ | $-$ | $0$ | $1$ | $0$ |
| $\{3,4\}$ | $+$ | $6$ | $2$ | $12$ |
積の和は $\det A=8$ である。$24$ 項の Leibniz の公式が、$2$ 次の行列式の組 $6$ つに整理されている。
$B$ を $p$ 次、$D$ を $q$ 次の正方行列とする。$A=\begin{pmatrix}B&E\\O&D\end{pmatrix}$ を第 $1,\dots,p$ 列について展開する($J=[p]$)。$I\ne[p]$ なら、$I$ は $p$ より大きい番号を含み、$A[I,J]$ は成分がすべて $0$ の行を含むので小行列式は $0$ である。$I=[p]$ の項だけが残り、$s(I)+s(J)$ は偶数なので $\det A=\det B\det D$ である。
thm-ce-laplace で、小行列式と補小行列式を別の行の組からとると、和は $0$ になる。
$I\ne I'$ を $[n]$ の $k$ 元部分集合とすると
$$
\sum_{J\subset[n],\ |J|=k}(-1)^{s(J)}\det A[I,J]\,\det A[I'^{c},J^{c}]=0
$$
である。とくに $i\ne i'$ なら $\sum_{j=1}^na_{ij}C_{i'j}=0$ である。
$|I|=|I'|$ で $I\ne I'$ なので、$I$ に属し $I'$ に属さない番号 $i$ がある。第 $I$ 行を番号順に並べ、続けて第 $I'^{c}$ 行を番号順に並べた $n$ 次正方行列を $B$ とする。$B$ には $A$ の第 $i$ 行が 2 回現れるので $\det B=0$ である(行列式 の定理「多重線形性と交代性」の 2)。$B$ を第 $1,\dots,k$ 行について thm-ce-laplace で展開すると、$B[\,[k],J\,]=A[I,J]$、$B[\,[k]^{c},J^{c}\,]=A[I'^{c},J^{c}]$ なので、左辺の $(-1)^{s([k])}$ 倍が $0$ に等しい。
$k=1$、$I=\{i\}$、$I'=\{i'\}$ の場合は、左辺の式は $\sum_j(-1)^ja_{ij}\det M_{i'j}=0$ であり、両辺に $(-1)^{i'}$ を掛ければ $\sum_ja_{ij}C_{i'j}=0$ を得る。$\square$
列について同じ形の等式が Bou89 Ch. III §8 no. 6 の式 (22) である。$k=1$ の場合と thm-ce-main をまとめて行列の積の形に書いたものが、余因子行列 の定理「余因子行列の基本等式」$A\operatorname{adj}A=(\det A)I_n$ である。
余因子展開は手計算では便利だが、一般の行列にそのまま繰り返すと手間が階乗で増える。
$n\ge2$ 次の行列式を、$2$ 以上の次数で必ず 1 つの行について余因子展開して計算するとき($1$ 次は成分そのもの)、掛け算の回数 $m(n)$ は
$$
m(n)=n!\sum_{k=1}^{n-1}\frac1{k!}
$$
である。とくに $n\to\infty$ で $m(n)/n!\to e-1$ である。
$n$ 個の成分それぞれに、$n-1$ 次の行列式と $1$ 回の掛け算が要るので、$m(n)=n(m(n-1)+1)$、$m(1)=0$ である。両辺を $n!$ で割ると $m(n)/n!=m(n-1)/(n-1)!+1/(n-1)!$ であり、足し合わせれば公式を得る。$\square$
$m(2)=2$、$m(3)=9$、$m(4)=40$ で、$m(10)=6235300$ である。一方、行基本変形で三角行列に直す方法(LU分解)の演算回数は $n^3$ 程度で、$n=10$ なら $1000$ 回程度である。ただし消去法は割り算を使う。余因子展開は掛け算と足し算と引き算だけでできるので、成分が割り算のできない環にあるときにもそのまま使える。
下の表の各行は、それぞれ 1 つの条件を外すと展開の式が成り立たなくなることを示す。
| 外す条件 | 例 | 成り立たなくなること |
|---|---|---|
| 符号 $(-1)^{i+j}$ | $A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ | 第 1 行で符号なしに足すと $0\cdot0+1\cdot1=1$ だが、$\det A=-1$ である($-1=1$ となる環を除く) |
| 同じ行の余因子と組む | $A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ | 第 1 行の成分と第 2 行の余因子を組むと $1\cdot(-2)+2\cdot1=0$ で、$\det A=-2$ ではない |
| $J$ について全部足す | $A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$、$I=J=\{1\}$ | 1 項だけなら $1\cdot4=4$ で、$\det A=-2$ ではない(区分三角でない) |
| 成分が可換である | 四元数の $\mathbf{i},\mathbf{j}$ で $\begin{pmatrix}0&\mathbf{i}\\\mathbf{j}&0\end{pmatrix}$ | 第 1 行の展開の形は $0\cdot0-\mathbf{i}\mathbf{j}=-\mathbf{k}$、第 1 列の展開の形は $0\cdot0-\mathbf{j}\mathbf{i}=\mathbf{k}$ で、値が違う |
符号をすべて取り除いた Leibniz の公式は permanent と呼ばれる別の量で、同じ形の展開 $\operatorname{per}A=\sum_ja_{ij}\operatorname{per}M_{ij}$ をもつが、行の入れ替えで符号を変えず、積の公式も成り立たない。$0,1$ 行列の permanent の行和による上界は Bregmanの定理 で述べる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する