In mathematics, specifically linear algebra, the Cauchy–Binet formula, named after Augustin-Louis Cauchy and Jacques Philippe Marie Binet, is an identity for the determinant of the product of two rectangular matrices of transpose shapes (so that the product is well-defined and square).
The formula is valid for matrices with the entries from any commutative ring.
, write A[m],S for the m×m matrix whose columns are the columns of A at indices from S, and BS,[m] for the m×m matrix whose rows are the rows of B at indices from S. The Cauchy–Binet formula then states Example: Taking m = 2 and n = 3, and matrices
is the empty set, and the formula says that det(AB) = 0 (its right hand side is an empty sum); indeed in this case the rank of the m×m matrix AB is at most n, which implies that its determinant is zero.
For m = 0, A and B are empty matrices (but of different shapes if n > 0), as is their product AB; the summation involves a single term S = Ø, and the formula states 1 = 1, with both sides given by the determinant of the 0×0 matrix.
of the n different singletons taken from [n], and both sides of the formula give
, the dot product of the pair of vectors represented by the matrices.
The smallest value of m for which the formula states a non-trivial equality is m = 2; it is discussed in the article on the Binet–Cauchy identity.
The following simple proof relies on two facts that can be proven in several different ways:[1] Now, if we compare the coefficient of
, the left hand side will give the sum of the principal minors of
while the right hand side will give the constant term of
The proof below is based on formal manipulations only, and avoids using any particular interpretation of determinants, which may be taken to be defined by the Leibniz formula.
Only their multilinearity with respect to rows and columns, and their alternating property (vanishing in the presence of equal rows or columns) are used; in particular the multiplicative property of determinants for square matrices is not used, but is rather established (the case n = m).
The proof is valid for arbitrary commutative coefficient rings.
The formula can be proved in two steps: For step 1, observe that for each row of A or column of B, and for each m-combination S, the values of det(AB) and det(A[m],S)det(BS,[m]) indeed depend linearly on the row or column.
For the latter this is immediate from the multilinear property of the determinant; for the former one must in addition check that taking a linear combination for the row of A or column of B while leaving the rest unchanged only affects the corresponding row or column of the product AB, and by the same linear combination.
Thus one can work out both sides of the Cauchy−Binet formula by linearity for every row of A and then also every column of B, writing each of the rows and columns as a linear combination of standard basis vectors.
The resulting multiple summations are huge, but they have the same form for both sides: corresponding terms involve the same scalar factor (each is a product of entries of A and of B), and these terms only differ by involving two different expressions in terms of constant matrices of the kind described above, which expressions should be equal according to the Cauchy−Binet formula.
" is the Kronecker delta, and the Cauchy−Binet formula to prove has been rewritten as where p(f,g) denotes the scalar factor
It remains to prove the Cauchy−Binet formula for A = Lf and B = Rg, for all f,g:[m] → [n].
For this step 2, if f fails to be injective then Lf and LfRg both have two identical rows, and if g fails to be injective then Rg and LfRg both have two identical columns; in either case both sides of the identity are zero.
So if the images of f and g are different, the right hand side has only null terms, and the left hand side is zero as well since LfRg has a null row (for i with
In the remaining case where the images of f and g are the same, say f([m]) = S = g([m]), we need to prove that Let h be the unique increasing bijection [m] → S, and π,σ the permutations of [m] such that
As we have seen, the Cauchy–Binet formula is equivalent to the following: where In terms of generalized Kronecker delta, we can derive the formula equivalent to the Cauchy–Binet formula: If A is a real m×n matrix, then det(A AT) is equal to the square of the m-dimensional volume of the parallelotope spanned in Rn by the m rows of A. Binet's formula states that this is equal to the sum of the squares of the volumes that arise if the parallelepiped is orthogonally projected onto the m-dimensional coordinate planes (of which there are
In the case m = 1 the parallelotope is reduced to a single vector and its volume is its length.
The above statement then states that the square of the length of a vector is the sum of the squares of its coordinates; this is indeed the case by the definition of that length, which is based on the Pythagorean theorem.
of dimension n, the Cauchy–Binet formula defines an induced inner product on the exterior algebra
Context for the formula is given in the article on minors, but the idea is that both the formula for ordinary matrix multiplication and the Cauchy–Binet formula for the determinant of the product of two matrices are special cases of the following general statement about the minors of a product of two matrices.
A continuous version of the Cauchy–Binet formula, known as the Andréief-Heine identity[2] or Andréief identity appears commonly in random matrix theory.
Forrester[4] describes how to recover the usual Cauchy–Binet formula as a discretisation of the above identity.