Cauchy-Binet formula

Let $A$ be an $m\times n$ matrix and $B$ an $n\times m$ matrix. Then the determinant of their product $C=AB$ can be written as a sum of products of minors of $A$ and $B$ :

|C|=\sum_{1\leq k_{1}<k_{2}<\cdots<k_{m}\leq n}A\begin{pmatrix}1&2&\cdots&m\\ k_{1}&k_{2}&\cdots&k_{m}\end{pmatrix}B\begin{pmatrix}k_{1}&k_{2}&\cdots&k_{m}% \\ 1&2&\cdots&m\end{pmatrix}.

Basically, the sum is over the maximal ( $m$ -th order) minors of $A$ and $B$ . See the entry on minors (http://planetmath.org/MinorOfAMatrix) for notation.

If $m>n$ , then neither $A$ nor $B$ have minors of rank $m$ , so $|C|=0$ . If $m=n$ , this formula reduces to the usual multiplicativity of determinants $|C|=|AB|=|A||B|$ .

Proof.

Since $C=AB$ , we can write its elements as $c_{ij}=\sum_{k=1}^{n}a_{ik}b_{kj}$ . Then its determinant is

	$\displaystyle\|C\|$	$\displaystyle=\begin{vmatrix}\sum_{k_{1}=1}^{n}a_{1k_{1}}b_{k_{1}1}&\cdots&% \sum_{k_{m}=1}^{n}a_{1k_{m}}b_{k_{m}m}\\ \vdots&\ddots&\vdots\\ \sum_{k_{1}=1}^{n}a_{mk_{1}}b_{k_{1}1}&\cdots&\sum_{k_{m}=1}^{n}a_{mk_{m}}b_{k% _{m}m}\end{vmatrix}$
		$\displaystyle=\sum_{k_{1},\ldots,k_{m}=1}^{n}\begin{vmatrix}a_{1k_{1}}b_{k_{1}% 1}&\cdots&a_{1k_{m}}b_{k_{m}m}\\ \vdots&\ddots&\vdots\\ a_{mk_{1}}b_{k_{1}1}&\cdots&a_{mk_{m}}b_{k_{m}m}\end{vmatrix}$
		$\displaystyle=\sum_{k_{1},\ldots,k_{m}=1}^{n}A\begin{pmatrix}1&2&\cdots&m\\ k_{1}&k_{2}&\cdots&k_{m}\end{pmatrix}b_{k_{1}1}b_{k_{2}2}\cdots b_{k_{m}m}.$

In both steps above, we have used the property that the determinant is multilinear in the colums of a matrix.

Note that the terms in the last sum with any two $k$ ’s the same will make the minor of $A$ vanish. And, for $\{k_{1},\cdots,k_{m}\}$ ’s that differ only by a permutation, the minor of $A$ will simply change sign according to the parity of the permutation. Hence the determinant of $C$ can be rewritten as

\displaystyle|C|

\displaystyle=\sum_{1\leq k_{1}<\cdots<k_{m}\leq n}A\begin{pmatrix}1&2&\cdots&% m\\ k_{1}&k_{2}&\cdots&k_{m}\end{pmatrix}\sum_{\sigma\in S_{m}}\operatorname{sgn}(% \sigma)\,b_{k_{\sigma(1)}1}b_{k_{\sigma(2)}2}\cdots b_{k_{\sigma(m)}m},

where $S_{m}$ is the permutation group on $m$ elements. But the last sum is none other than the determinant $B\left(\begin{smallmatrix}k_{1}&k_{2}&\cdots&k_{m}\\ 1&2&\cdots&m\end{smallmatrix}\right)$ . Hence we write

|C|=\sum_{1\leq k_{1}<\cdots<k_{m}\leq n}A\begin{pmatrix}1&2&\cdots&m\\ k_{1}&k_{2}&\cdots&k_{m}\end{pmatrix}B\begin{pmatrix}k_{1}&k_{2}&\cdots&k_{m}% \\ 1&2&\cdots&m\end{pmatrix},

which is the Cauchy-Binet formula. ∎

Title	Cauchy-Binet formula
Canonical name	CauchyBinetFormula
Date of creation	2013-03-22 14:07:04
Last modified on	2013-03-22 14:07:04
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	11
Author	CWoo (3771)
Entry type	Theorem
Classification	msc 15A15
Synonym	Binet-Cauchy formula
Related topic	MinorOfAMatrix