Cauchy-Binet formula

Let $A$ be an $m\\times n$ matrix and $B$ an $n\\times m$ matrix. Thenthe determinant of their product $C=AB$ can be written as a sum of products ofminors 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 ismultilinear in the colums of a matrix.

Note that the terms in the last sum with any two $k$ ’s the same willmake the minor of $A$ vanish. And, for $\\{k_{1},\\cdots,k_{m}\\}$ ’sthat differ only by a permutation, the minor of $A$ will simply changesign 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.∎