Other meanings of Cauchy–Binet formula
Mathematics
The Cauchy–Binet formula is a theorem in linear algebra that expresses a minor of a matrix product as a sum of products of minors. Specifically, if A is an m×n matrix and B is an n×m matrix, then for any subset S of {1,…,m} of size k, the k×k minor of AB corresponding to S equals the sum over all k-element subsets T of {1,…,n} of the product of the minor of A with rows S and columns T and the minor of B with rows T and columns S. It generalizes the fact that the determinant of a product of square matrices is the product of their determinants, and it underpins the Cauchy–Binet expansion used in combinatorics and statistics.
The formula states that for an m×n matrix A and an n×m matrix B, with m ≤ n, the determinant of the product AB can be written as a sum over all m-element subsets S of {1,…,n} of det(A_S) det(B_S), where A_S is the m×m submatrix of A with columns in S and B_S is the m×m submatrix of B with rows in S.1 When m = n, the sum reduces to a single term, recovering the multiplicative property of determinants.
A standard proof uses the Cauchy–Binet expansion of the determinant as a sum over permutations, then groups permutations by their image sets.2 Alternatively, one can prove it by induction on m or by applying the exterior algebra functor, where the formula reflects the functoriality of the kth exterior power.3
The formula is essential in the theory of totally positive matrices, where it ensures that the product of two totally positive matrices is totally positive, because every minor of the product is a sum of products of nonnegative minors.4 It also appears in the computation of the volume of a parallelepiped in higher dimensions and in the study of random matrices, where it helps derive joint eigenvalue densities.
In statistics, the Cauchy–Binet formula is used to compute the determinant of a sample covariance matrix when the data matrix is rectangular, and it underlies the distribution theory of the Wishart distribution. In combinatorics, it provides a generating function for spanning trees of a graph via the matrix-tree theorem.
The formula extends to rectangular matrices where the number of rows of A is less than the number of columns, and to the case where the product is replaced by a product of several matrices, yielding a sum over tuples of index sets. A further generalization, the Cauchy–Binet formula for permanents, replaces determinants by permanents, but it holds only under restrictive conditions, such as when one matrix is a diagonal matrix.
In the context of exterior algebra, the formula is a manifestation of the fact that the kth exterior power of a composition is the composition of the kth exterior powers, which is a natural isomorphism.3 This viewpoint leads to generalizations in the theory of Schur functors and representation theory.
Augustin-Louis Cauchy published the formula in 1812, and Jacques Binet independently discovered it around the same time; their rivalry over priority is a noted episode in the history of mathematics.5 The formula is also known as the Cauchy–Binet theorem or the Binet–Cauchy identity.
An edge case occurs when m > n: the sum over subsets is empty, so the determinant of AB is zero, which is consistent with the rank-nullity theorem. Another subtlety is that the formula holds over any commutative ring, not just the real or complex numbers, which is crucial for applications in algebraic combinatorics.6 The formula also appears in the theory of determinantal point processes, where it gives the joint intensities of a random point process.
The formula is named after Augustin-Louis Cauchy and Jacques Binet, who both published it in 1812.
Help improve the encyclopedia. Reports go straight to the site manager.