Cauchy–Binet formula

Write $[n]$ for the set $\{1,2,\ldots,n\}$ and $\binom{[n]}{k}$ for the family of all subets of $[n]$ and size $k$. Also, for an $m \times n$ matrix $X$, $I \subseteq [m]$, and $J \subseteq [n]$, let $X_{I,J}$ denote the submatrix obtained from $X$ by deleting row $i$ for each $i \notin I$ and column $j$ for each $j\notin [J]$.

Theorem. (Cauchy–Binet formula) Let $A$ be a $k\times n$ matrix and $B$ be an $n\times k$ matrix over the field $F$. Then $$\det(AB) = \sum_{S\subseteq\binom{[n]}{k}} \det(A_{[k],S}B_{S,[k]}).$$

1^st Proof. Let $(e_1,\ldots, e_m)$ denote the standard basis of $F^m$. (For convenience, we will abuse the notation so $e_i$ stands for the $i$th standard basis vector in any of $F^m$, $m \geq i$.) Then $$\begin{align*} \det(AB)(e_1 \wedge \cdots \wedge e_k) &= \bigl( {\textstyle\bigwedge}^k AB \bigr)(e_1 \wedge \cdots \wedge e_k) \\ &= \bigl( {\textstyle\bigwedge}^k A \bigr)[(Be_1) \wedge \cdots \wedge (Be_k)]. \end{align*}$$ Now by noting that $Be_j = \sum_{i=1}^{n} B_{ij} e_i$ is the $j$th column of $B$, we may expand the exterior product in the last line as $$\begin{align*} &[(Be_1) \wedge \cdots \wedge (Be_k)] \\ &= \sum_{\substack{\rho : [k] \to [n] \\ \sigma \text{ injective} }} (B_{\rho(1),1} e_{\rho(1)}) \wedge \cdots \wedge (B_{\rho(k),k} e_{\rho(k)} ) \\ &= \sum_{\substack{\sigma : [k] \to [n] \\ \sigma \text{ increasing} }} \sum_{\substack{\tau : [k] \to [k] \\ \tau \text{ bijective}}} \left( \prod_{i=1}^{k} B_{\sigma(\tau(i)),i} \right) (e_{\sigma(\tau(1))} \wedge \cdots \wedge e_{\sigma(\tau(k))} ) \\ &= \sum_{\substack{\sigma : [k] \to [n] \\ \sigma \text{ increasing} }} \sum_{\substack{\tau : [k] \to [k] \\ \tau \text{ bijective}}} \operatorname{sgn}(\tau) \left( \prod_{i=1}^{k} B_{\sigma(\tau(i)),i} \right) (e_{\sigma(1)} \wedge \cdots \wedge e_{\sigma(k)} ) \\ &= \sum_{\substack{\sigma : [k] \to [n] \\ \sigma \text{ increasing} }} \det(B_{\sigma([k]),[k]}) (e_{\sigma(1)} \wedge \cdots \wedge e_{\sigma(k)} ) \end{align*}$$ Plugginb this back, we therefore get $$\begin{align*} &\det(AB)(e_1 \wedge \cdots \wedge e_k) \\ &= \sum_{\substack{\sigma : [k] \to [n] \\ \sigma \text{ increasing} }} \det(B_{\sigma([k]),[k]}) [(Ae_{\sigma(1)}) \wedge \cdots \wedge (Ae_{\sigma(k)}) ] \\ &= \sum_{\substack{\sigma : [k] \to [n] \\ \sigma \text{ increasing} }} \det(B_{\sigma([k]),[k]}) \det(A_{[k],\sigma([k])}) (e_1 \wedge \cdots \wedge e_k) \\ &= \sum_{S \in \binom{[n]}{k}} \det(A_{[k],S}) \det(B_{S,[k]}) (e_1 \wedge \cdots \wedge e_k). \end{align*}$$ This completes the proof. $\square$

2^nd Proof. We specialize in the case $F = \mathbb{C}$. Also, for each index set $I$, we abbreviate $\wedge_{i\in I} e_i = \wedge I$. Then using inner product between multivectors, we get $$\begin{align*} \det(AB) &= \left\langle (\wedge^k A^*)(\wedge [k]), (\wedge^k B)(\wedge [k]) \right\rangle \\ &= \sum_{S \in \binom{[n]}{k}} \left\langle (\wedge^k A^*)(\wedge [k]), \wedge S \right\rangle \left\langle \wedge S, (\wedge^k B)(\wedge [k]) \right\rangle \\ &= \sum_{S \in \binom{[n]}{k}} \det(A_{[k],S})\det(B_{S,[k]}) \end{align*}$$

A similar technique shows:

Proposition. (Coefficients of a characteristic Polynomial) Let $A$ be an $n\times n$ matrix. Then $$\det(zI_n + A) = \sum_{k=0}^{n} z^{n-k} \sum_{S\subseteq\binom{[n]}{k}} \det(A_{S,S}).$$

Proposition. Let $a_1, \ldots, a_p \in \mathbb{C}$ and $v_1, \ldots, v_p \in \mathbb{C}^n$. Then $$\det\left( \sum_{j=1}^{p} a_j v_j v_j^{*} \right) = \sum_{\{j_1 \lt \ldots \lt j_n \} \subseteq [p]} (a_{j_1} \cdots a_{j_n}) \left| \det( v_{j_1}, \ldots, v_{j_n} ) \right|^2.$$