Cauchy-Binet Identity

(AB) = _S (A_S) (B_S) — determinants of products via minors.

The idea

The Cauchy-Binet formula computes the determinant of a product of two rectangular matrices from the determinants of their square submatrices.

Theorem (Cauchy-Binet formula).

Let $A$ be $m \times n$ and $B$ be $n \times m$ with $m \leq n$, so that the product $AB$ is square. Then $\det(AB) = \sum_{|S| = m} \det(A_S)\,\det(B_S),$ where $S$ runs over the $m$-element subsets of $\{1, \ldots, n\}$, the matrix $A_S$ is $A$ restricted to the columns indexed by $S$, and $B_S$ is $B$ restricted to the rows indexed by $S$.

The formula extends the product rule to rectangular factors. For square $A$ and $B$ we have $\det(AB) = \det(A)\det(B)$; when the factors are rectangular, the left side still makes sense but neither factor has a determinant of its own. Cauchy-Binet replaces the two missing determinants with the determinants of all the square submatrices the factors do contain, paired off one subset $S$ at a time, so the sum has $\binom{n}{m}$ terms. When $m = n$ the only subset is $\{1, \ldots, n\}$, and the formula reduces to the product rule.

Taking $B = A^{\top}$ gives $B_S = (A_S)^{\top}$, so every term becomes a square.

Corollary.

For every $m \times n$ matrix $A$ with $m \leq n$, $\det(AA^{\top}) = \sum_{|S| = m} \det(A_S)^2 \geq 0.$

Ways to work on it

• Walkthrough. Verify Cauchy-Binet on a concrete 2 × 3 / 3 × 2 product.
• Practice. Compute a Gram determinant via the Lagrange identity, the two-vector case.
• Hardest. Answer conceptual questions about the identity's structure and what it implies for Gram determinants.

Not sure where to start? Take the ten-question placement test.