# 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}

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

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

which is the Cauchy-Binet formula. ∎

Title Cauchy-Binet formula CauchyBinetFormula 2013-03-22 14:07:04 2013-03-22 14:07:04 CWoo (3771) CWoo (3771) 11 CWoo (3771) Theorem msc 15A15 Binet-Cauchy formula MinorOfAMatrix