Cauchy–Binetの公式

同義語：Binet–Cauchyの公式Cauchy–Binet formulaBinet–Cauchy theoremCauchy–Binet theorem

概要

前提知識: 行列式, 置換の符号

Cauchy–Binetの公式（Cauchy–Binet formula）とは、$p\times q$ 行列 $A$ と $q\times p$ 行列 $B$ の積 $AB$（$p$ 次の正方行列）の行列式を、$A$ と $B$ の $p$ 次の小行列式の積の和として表す公式である。成分は可換環にあればよく、$p\le q$ のとき
$$ \det(AB)=\sum_{S}\det A[\,\cdot\,,S]\ \det B[S,\,\cdot\,] $$
が成り立つ。和は $\{1,\dots,q\}$ の $p$ 元部分集合 $S$ すべてにわたり、$A[\,\cdot\,,S]$ は $A$ の $S$ に属する列だけを残した $p$ 次の正方行列、$B[S,\,\cdot\,]$ は $B$ の $S$ に属する行だけを残した $p$ 次の正方行列である。$p>q$ のときは $\det(AB)=0$ である。
$p=q$ なら和は 1 項だけで、積の行列式の公式 $\det(AB)=\det A\det B$ になる。$p=1$ なら $AB$ は $1\times1$ 行列で、公式は $\sum_kA_{1k}B_{k1}$ という積の定義そのものである。その間の $p$ では、$B$ で $p$ 次元の空間から $q$ 次元の空間へ移り、$A$ で $p$ 次元の空間へ戻る写像 $AB$ の体積の拡大率 $\det(AB)$ を、$q$ 次元の空間の座標の $p$ 次元部分空間ごとに分けて足し合わせる式と見られる。実行列 $A$ について $B=A^{\top}$ とおくと、$A$ の行である $p$ 本のベクトルの張る平行体の体積の 2 乗が、座標の $p$ 次元部分空間への射影の体積の 2 乗の和に等しいという、三平方の定理の高次元版が得られる。
この記事では、行列式の多重線形性と交代性だけを使って公式を証明し、任意の小行列式についての一般形、Gram 行列式の小行列式による表示を導く。グラフの全域木を数える行列木定理や、$p=2$ の場合のLagrangeの恒等式は、この公式の使われ方の代表例である。

記号

以下、$R$ は可換環とし、行列の成分はすべて $R$ に属するとする。$[m]:=\{1,\dots,m\}$ と書く。行列式は Leibniz の公式
$$ \det M=\sum_{\sigma\in S_p}\operatorname{sgn}(\sigma)\,M_{1\sigma(1)}M_{2\sigma(2)}\cdots M_{p\sigma(p)} $$
で定める（行列式の定義「Leibnizの公式による定義」。成分が可換環でも同じ定義と基本性質が使えることは同記事の注意「可換環上の行列式」にある）。

小行列と小行列式

$A$ を $m\times n$ 行列とし、$I\subset[m]$、$J\subset[n]$ を元の個数が等しい部分集合とする。$I=\{i_1< \dots< i_r\}$、$J=\{j_1< \dots< j_r\}$ と番号順に並べ、$(a,b)$ 成分が $A_{i_aj_b}$ の $r$ 次正方行列を $A[I,J]$ と書き、$A$ の 小行列（submatrix）という。その行列式 $\det A[I,J]$ を $A$ の $r$ 次の 小行列式（minor）という。$I=[m]$ のときは $A[\,\cdot\,,J]$、$J=[n]$ のときは $A[I,\,\cdot\,]$ と書く。

行と列は、もとの行列での順番を保ったまま残す。この約束が符号を決めるので、公式の中で $A$ の列と $B$ の行を 同じ順 に並べることが大事になる（下の反例の表の 3 行目）。行列木定理の記事は $A[\,\cdot\,,S]$ を $A_{\bullet S}$、$B[S,\,\cdot\,]$ を $B_{S\bullet}$ と書いている。

主定理

証明では、行を並べ替えた行列の行列式を使う。

行の並べ替えと行列式

$M$ を $p$ 次の正方行列、$\sigma\in S_p$ とし、第 $i$ 行が $M$ の第 $\sigma(i)$ 行である行列を $M_\sigma$ とする（$(M_\sigma)_{ij}=M_{\sigma(i)j}$）。このとき $\det M_\sigma=\operatorname{sgn}(\sigma)\det M$ である。

Leibniz の公式で添字を付け替える

Leibniz の公式により
$$ \det M_\sigma=\sum_{\tau\in S_p}\operatorname{sgn}(\tau)\prod_{i=1}^pM_{\sigma(i)\,\tau(i)} $$
である。積の添字を $l=\sigma(i)$ で付け替えると $\prod_iM_{\sigma(i)\tau(i)}=\prod_lM_{l\,\rho(l)}$（$\rho:=\tau\sigma^{-1}$）となる。$\tau\mapsto\rho=\tau\sigma^{-1}$ は $S_p$ の全単射で、置換の符号の乗法性から $\operatorname{sgn}(\tau)=\operatorname{sgn}(\rho)\operatorname{sgn}(\sigma)$ である。よって $\det M_\sigma=\operatorname{sgn}(\sigma)\sum_\rho\operatorname{sgn}(\rho)\prod_lM_{l\rho(l)}=\operatorname{sgn}(\sigma)\det M$ である。$\square$

Cauchy–Binet の公式

$R$ を可換環、$A$ を $R$ の元を成分とする $p\times q$ 行列、$B$ を $q\times p$ 行列とする。

$p\le q$ なら
$$ \det(AB)=\sum_{S\subset[q],\ |S|=p}\det A[\,\cdot\,,S]\ \det B[S,\,\cdot\,] $$
である。
$p>q$ なら $\det(AB)=0$ である。

積の各行を B の行の 1 次結合として展開する

$B$ の第 $k$ 行を $b_k$（$1\times p$ の行ベクトル）と書く。$AB$ の第 $i$ 行は
$$ (AB)_{i,\,\cdot}=\sum_{k=1}^qA_{ik}\,b_k $$
である。行列式は各行について線形なので（行列式の定理「多重線形性と交代性」の 1）、第 1 行から第 $p$ 行まで順に展開すると
$$ \det(AB)=\sum_{(k_1,\dots,k_p)\in[q]^p}A_{1k_1}A_{2k_2}\cdots A_{pk_p}\ \det\begin{pmatrix}b_{k_1}\\\vdots\\b_{k_p}\end{pmatrix}\qquad(\ast) $$
となる。和は $[q]$ の元の列 $(k_1,\dots,k_p)$ すべてにわたる。
$k_1,\dots,k_p$ に等しいものが 2 つあれば、右端の行列は等しい行を 2 つもつので行列式は $0$ である（同定理の 2）。$p>q$ なら、$[q]$ の元を $p$ 個並べると必ず重複が生じるので、$(\ast)$ のすべての項が $0$ になり、2 が示される。
$p\le q$ とし、重複のない列 $(k_1,\dots,k_p)$ だけを考える。その値の集合を $S=\{s_1< \dots< s_p\}$ とすると、$k_i=s_{\sigma(i)}$ を満たす $\sigma\in S_p$ がただ 1 つある。逆に、$p$ 元部分集合 $S$ と $\sigma\in S_p$ を与えると、重複のない列 $(s_{\sigma(1)},\dots,s_{\sigma(p)})$ が 1 つ決まる。この対応は全単射である。
このとき、$(\ast)$ の右端の行列の第 $i$ 行は $b_{s_{\sigma(i)}}$、すなわち $B[S,\,\cdot\,]$ の第 $\sigma(i)$ 行なので、lem-cb-permute によりその行列式は $\operatorname{sgn}(\sigma)\det B[S,\,\cdot\,]$ である。よって
$$ \det(AB)=\sum_{S}\det B[S,\,\cdot\,]\sum_{\sigma\in S_p}\operatorname{sgn}(\sigma)\prod_{i=1}^pA_{i\,s_{\sigma(i)}} $$
である。$A[\,\cdot\,,S]$ の $(i,j)$ 成分は $A_{is_j}$ なので、内側の和は $A[\,\cdot\,,S]$ の Leibniz の公式そのものであり、$\det A[\,\cdot\,,S]$ に等しい。これで 1 が示された。$\square$

証明は、行列式が多重線形で交代的であることと、行の並べ替えで符号がつくことだけを使っている。積の行列式の公式 $\det(AB)=\det A\det B$ は使っていないので、$p=q$ の場合の 1 は積の公式の 1 つの証明にもなっている。$A$ の列について展開しても同じ証明ができ、それが行列木定理の記事の証明である。
公式は Sta13 Theorem 9.4（p. 171）に、$m\times n$ 行列と $n\times m$ 行列の形で述べられている。BH11 Proposition 1.3.5（p. 6）は、同じ大きさの $m\times n$ 行列 $A,B$ について $\det(AB^{\top})=\sum_S\det A_S\det B_S$（$A_S$・$B_S$ は列を $S$ に制限した行列）の形で述べている。$B^{\top}$ の行は $B$ の列なので、この記事の 1 で $B$ を $B^{\top}$ に替えたものと同じである。

特別な場合と例

$p=q$．$S=[p]$ の 1 項だけが残り、$\det(AB)=\det A\det B$ になる。
$p=1$．$S$ は 1 元集合 $\{k\}$ で、$\det A[\,\cdot\,,\{k\}]=A_{1k}$、$\det B[\{k\},\,\cdot\,]=B_{k1}$ なので、公式は $AB=\sum_kA_{1k}B_{k1}$ である。
$p>q$．$AB$ は $p$ 次の正方行列だが、2 により行列式は $0$ である。成分が体にあるときは、$AB$ の階数が $q$ 以下で $p$ より小さいことからもわかる。
$p=2$．$A$ の 2 行を $a,b$、$B$ の 2 列を $c,d$ とすると、$\det(AB)=(a\cdot c)(b\cdot d)-(a\cdot d)(b\cdot c)$（$a\cdot c:=\sum_ka_kc_k$）であり、公式は
$$ (a\cdot c)(b\cdot d)-(a\cdot d)(b\cdot c)=\sum_{i< j}(a_ib_j-a_jb_i)(c_id_j-c_jd_i) $$
という恒等式になる。$c=a$、$d=b$ とおいたものが Lagrangeの恒等式である。

$2\times3$ 行列と $3\times2$ 行列

$$ A=\begin{pmatrix}1&2&0\\0&1&3\end{pmatrix},\qquad B=\begin{pmatrix}1&0\\1&1\\2&1\end{pmatrix} $$
とすると $AB=\begin{pmatrix}3&2\\7&4\end{pmatrix}$ で、$\det(AB)=12-14=-2$ である。$[3]$ の 2 元部分集合は 3 つあり、

$S$	$A[\,\cdot\,,S]$	$\det$	$B[S,\,\cdot\,]$	$\det$	積
$\{1,2\}$	$\begin{pmatrix}1&2\\0&1\end{pmatrix}$	$1$	$\begin{pmatrix}1&0\\1&1\end{pmatrix}$	$1$	$1$
$\{1,3\}$	$\begin{pmatrix}1&0\\0&3\end{pmatrix}$	$3$	$\begin{pmatrix}1&0\\2&1\end{pmatrix}$	$1$	$3$
$\{2,3\}$	$\begin{pmatrix}2&0\\1&3\end{pmatrix}$	$6$	$\begin{pmatrix}1&1\\2&1\end{pmatrix}$	$-1$	$-6$

である。積の和は $1+3-6=-2$ で、$\det(AB)$ に一致する。逆順の積 $BA$ は $3$ 次の正方行列で、その行列式は 2 により $0$ である（$q=3>2=p$ の役割を入れ替えて使う）。

任意の小行列式についての形

$AB$ の正方でない部分の情報も、同じ公式から取り出せる。

積の小行列式

$R$ を可換環、$A$ を $m\times q$ 行列、$B$ を $q\times n$ 行列とし、$I\subset[m]$、$J\subset[n]$ を $r$ 元部分集合とする。$r\le q$ なら
$$ \det\,(AB)[I,J]=\sum_{K\subset[q],\ |K|=r}\det A[I,K]\ \det B[K,J] $$
であり、$r>q$ なら $\det\,(AB)[I,J]=0$ である。

行と列を先に選んでから掛ける

$(AB)[I,J]$ の $(a,b)$ 成分は $\sum_kA_{i_ak}B_{kj_b}$ なので、$(AB)[I,J]=A[I,\,\cdot\,]\,B[\,\cdot\,,J]$ である。$A[I,\,\cdot\,]$ は $r\times q$ 行列、$B[\,\cdot\,,J]$ は $q\times r$ 行列なので、thm-cb-main を当てればよい。$A[I,\,\cdot\,]$ から列 $K$ を選んだ行列は $A[I,K]$、$B[\,\cdot\,,J]$ から行 $K$ を選んだ行列は $B[K,J]$ である。$\square$

$n$ 次正方行列 $A,B$（$n\ge2$）について $r=n-1$ の場合を使うと、余因子行列の積の公式 $\operatorname{adj}(AB)=\operatorname{adj}B\,\operatorname{adj}A$ が直接得られる。$\operatorname{adj}M$ の $(i,j)$ 成分は、$M$ から第 $j$ 行と第 $i$ 列を除いた小行列式に $(-1)^{i+j}$ を掛けたものだからである。

計算を開く

$\hat\imath:=[n]\setminus\{i\}$ と書く。$\operatorname{adj}(AB)_{ij}=(-1)^{i+j}\det\,(AB)[\hat\jmath,\hat\imath]$ に cor-cb-minors を使うと、$(n-1)$ 元部分集合 $K$ は $\hat k$（$k\in[n]$）の形なので $$\det\,(AB)[\hat\jmath,\hat\imath]=\sum_{k=1}^n\det A[\hat\jmath,\hat k]\,\det B[\hat k,\hat\imath]=\sum_{k=1}^n(-1)^{j+k}\operatorname{adj}(A)_{kj}\cdot(-1)^{k+i}\operatorname{adj}(B)_{ik}$$ である。$(-1)^{j+k}(-1)^{k+i}=(-1)^{i+j}$ なので、$\operatorname{adj}(AB)_{ij}=\sum_k\operatorname{adj}(B)_{ik}\operatorname{adj}(A)_{kj}=(\operatorname{adj}B\,\operatorname{adj}A)_{ij}$ である。余因子行列の命題「積・転置・反復の恒等式」の 2 は、同じ等式を普遍行列への帰着で示している。

$r$ 元部分集合を辞書式の順に並べ、$(I,J)$ 成分が $\det A[I,J]$ の行列を $A$ の第 $r$ 複合行列（compound matrix）$C_r(A)$ という。cor-cb-minors は $C_r(AB)=C_r(A)\,C_r(B)$ と書ける。$r=1$ では $C_1(A)=A$ で、ただの積である。座標を使わずにいえば、$C_r(A)$ は $A$ の定める線形写像が外積代数の $r$ 次の部分に引き起こす写像の、標準基底 $e_{k_1}\wedge\dots\wedge e_{k_r}$（$k_1< \dots< k_r$）に関する行列であり、cor-cb-minors は「$r$ 次の外冪をとる操作が合成を保つ」こと（外積代数の系「関手性」）を成分で書いたものになっている。

Gram 行列式と小行列式の 2 乗の和

$B$ として $A$ の共役転置をとると、和の各項が絶対値の 2 乗になる。

行列とその共役転置の積

$A$ を $p\times q$ の複素行列（$p\le q$）とし、$A^*:=\overline{A}^{\top}$ とする。このとき
$$ \det(AA^*)=\sum_{S\subset[q],\ |S|=p}\bigl|\det A[\,\cdot\,,S]\bigr|^2 $$
である。とくに $\det(AA^*)\ge0$ であり、$\det(AA^*)=0$ となるのは $A$ のすべての $p$ 次の小行列式が $0$ のとき、すなわち $A$ の階数が $p$ より小さいときに限る。$A$ が実行列なら $A^*=A^{\top}$ で、右辺は $(\det A[\,\cdot\,,S])^2$ の和である。

共役転置の小行列式は小行列式の共役

$A^*[S,\,\cdot\,]=\bigl(A[\,\cdot\,,S]\bigr)^*$ である（$A^*$ の第 $s$ 行は $A$ の第 $s$ 列の共役）。正方行列 $M$ について $\det M^*=\overline{\det M}$ である。実際、行列式の命題「転置と行列式」により $\det M^{\top}=\det M$ であり、Leibniz の公式は成分の和と積だけからなるので、成分をすべて共役にすると行列式も共役になる。よって thm-cb-main の 1 の各項は $\det A[\,\cdot\,,S]\,\overline{\det A[\,\cdot\,,S]}=|\det A[\,\cdot\,,S]|^2$ である。
右辺は $0$ 以上で、$0$ になるのはすべての項が $0$ のときに限る。$A$ の列は $\mathbb{C}^p$ のベクトルなので、$A$ の階数（列の張る部分空間の次元）が $p$ であることは、列の中に線形独立な $p$ 本があることと同値である。$\mathbb{C}^p$ の $p$ 本のベクトルが線形独立であることは、それを並べた $p$ 次正方行列の行列式が $0$ でないことと同値である（行列式の定理「正則性の判定」）。よって、階数が $p$ であることは、ある $S$ で $\det A[\,\cdot\,,S]\ne0$ となることと同値である。$\square$

$A$ の行を $v_1,\dots,v_p\in\mathbb{C}^q$ とすると、$AA^*$ の $(i,j)$ 成分は $\sum_kA_{ik}\overline{A_{jk}}=\langle v_i,v_j\rangle$ である。したがって $\det(AA^*)$ は $v_1,\dots,v_p$ の Gram行列の行列式（Gram 行列式）に等しい（添字の流儀によって転置が入るが、行列式は変わらない）。cor-cb-gram は、Gram 行列式が「$p$ 本のベクトルの座標から $p$ 個を選んでできる小行列式」の絶対値の 2 乗の和であることを述べている。
幾何学的な意味．$A$ が実行列のとき、Gram行列の定理「Gram 行列式は高さの 2 乗の積」により、$\det(AA^{\top})$ は $v_1,\dots,v_p$ の張る $p$ 次元の平行体の体積の 2 乗である。一方、$v_1,\dots,v_p$ を座標の部分空間 $\mathbb{R}^S$（$s\in S$ の座標だけを残す）へ射影したベクトルは $A[\,\cdot\,,S]$ の行であり、その張る平行体の体積は $|\det A[\,\cdot\,,S]|$ である（同記事の系「平行体の体積と行列式」）。よって

平行体の体積の 2 乗＝座標の $p$ 次元部分空間への射影の体積の 2 乗の和
が成り立つ。$p=1$ では、ベクトルの長さの 2 乗が座標の 2 乗の和であること（三平方の定理）にほかならない。$p=2$、$q=3$ では、空間の平行四辺形の面積の 2 乗が、3 つの座標平面への射影の面積の 2 乗の和に等しいことになる（de Guaの定理、正射影と面積）。

空間の平行四辺形

$v_1=(1,0,1)$、$v_2=(0,1,1)$ を行とする $A=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$ では、$AA^{\top}=\begin{pmatrix}2&1\\1&2\end{pmatrix}$、$\det(AA^{\top})=3$ である。2 次の小行列式は、列 $\{1,2\}$ で $1$、列 $\{1,3\}$ で $1\cdot1-1\cdot0=1$、列 $\{2,3\}$ で $0\cdot1-1\cdot1=-1$ であり、2 乗の和は $1+1+1=3$ で一致する。平行四辺形の面積は $\sqrt3$ で、3 つの座標平面への射影はどれも面積 $1$ である。

応用

全域木の数え上げ．グラフの向き付き接続行列 $N$ から 1 行を除いた行列 $N_x$ について、Laplacian 行列の小行列式は $\det(N_xN_x^{\top})$ と書ける。cor-cb-gram の実の場合により、これは $N_x$ の最大次の小行列式の 2 乗の和であり、各小行列式は対応する辺の集合が全域木なら $\pm1$、そうでなければ $0$ になる。これが行列木定理の証明の骨組みである（BH11 Proposition 1.3.5 の後にある Proposition 1.3.4 の第 2 の証明の概略、p. 6）。
交わらない道の組．Lindström–Gessel–Viennotの補題は、有向グラフの交わらない道の組の重みの和を行列式で表す。始点・中間点・終点の 3 段だけからなるグラフに当てると、道の重みの行列が $AB$ になり、Cauchy–Binet の公式がもう 1 つの証明とともに得られる（同記事の命題「Cauchy–Binet の公式」）。
2 本のベクトルの恒等式．$p=2$ の場合は、上の「特別な場合と例」の恒等式であり、Lagrangeの恒等式の記事で、$\mathbb{R}^3$ のベクトル積との関係とともに扱う。

仮定を外すと成り立たなくなること

外す条件・替える条件	反例	成り立たなくなること
$p$ 次の正方行列 $AB$ の行列式をとること（$BA$ に替える）	$A=\begin{pmatrix}1&0\end{pmatrix}$、$B=\begin{pmatrix}1\\0\end{pmatrix}$	$\det(AB)=1=\sum_S\det A[\,\cdot\,,S]\det B[S,\,\cdot\,]$ だが、$\det(BA)=0$ で、同じ右辺には等しくない
行列式の交代性（行列式を permanent に替える）	$A=B=\begin{pmatrix}1&1\\1&1\end{pmatrix}$	$\operatorname{per}(AB)=8$ だが $\operatorname{per}A\operatorname{per}B=4$
$A$ の列と $B$ の行を同じ順に並べること	$A=B=I_2$ で、$A$ の列だけ $(2,1)$ の順に並べる	右辺が $-1$ になり、$\det(AB)=1$ に一致しない

反例の表の確かめ

各行で破れている条件と、崩れる結論を確かめる。

各行の確かめを開く

1 行目：$p=1$、$q=2$ で、$AB=(1)$、右辺は $S=\{1\}$ の項 $1\cdot1$ と $S=\{2\}$ の項 $0\cdot0$ の和 $1$ である。$BA=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ は $2$ 次の正方行列で、行列式は $0$ である。$BA$ に thm-cb-main を当てるには、$B$ を $2\times1$、$A$ を $1\times2$ とみて $2>1$ の場合の 2 を使う。公式の左辺は「小さい方」の積 $AB$ でなければならない。

2 行目：$n$ 次正方行列 $M$ の permanent を $\operatorname{per}M:=\sum_{\sigma\in S_n}M_{1\sigma(1)}\cdots M_{n\sigma(n)}$（Leibniz の公式から符号を除いたもの）と定める。$AB=\begin{pmatrix}2&2\\2&2\end{pmatrix}$ なので $\operatorname{per}(AB)=4+4=8$、$\operatorname{per}A=\operatorname{per}B=2$ である。$p=q=2$ なので、公式の右辺は $\operatorname{per}A\operatorname{per}B$ の 1 項だけである。permanent は多重線形だが、等しい行が 2 つあっても $0$ にならない（$\operatorname{per}A=2$）。証明で重複のある項を $0$ にした段と、並べ替えの符号の段がどちらも使えない。

3 行目：$S=\{1,2\}$ の 1 項だけで、$B[S,\,\cdot\,]=I_2$ の行は番号順である。$A$ の列を $(2,1)$ の順に並べた行列は $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ で、行列式は $-1$ である。$A[\,\cdot\,,S]$ を作るときに列を番号順に残すという def-cb-minor の約束（$A$ と $B$ で同じ順に並べること）が、符号を正しく合わせている。

補足

区分けした行列による別の証明

Sta13 Theorem 9.4 の証明の概略（pp. 172–173）は、区分けした行列の等式
$$ \begin{pmatrix}I_p&A\\O&I_q\end{pmatrix}\begin{pmatrix}A&O\\-I_q&B\end{pmatrix}=\begin{pmatrix}O&AB\\-I_q&B\end{pmatrix} $$
の両辺の行列式を比べる。左の第 1 因子の行列式は $1$ で、右辺の行列式は $\pm\det(AB)$ である。$\begin{pmatrix}A&O\\-I_q&B\end{pmatrix}$ の行列式を Leibniz の公式で展開すると、項は「$-I_q$ のどの $-1$ を使うか」で分類でき、使わない行の集合 $S$ ごとの寄与が $\pm\det A[\,\cdot\,,S]\det B[S,\,\cdot\,]$ になる。同書は符号がすべて $+$ になることの確かめを省いている。この記事の証明は、符号を lem-cb-permute で 1 か所にまとめて処理している。