Cauchy-Binet formula


Let A be an m×n matrix and B an n×m matrix. Then the determinantDlmfMathworldPlanetmath of their product C=AB can be written as a sum of products of minors of A and B:

|C|=1k1<k2<<kmnA(12mk1k2km)B(k1k2km12m).

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 cij=k=1naikbkj. Then its determinant is

|C| =|k1=1na1k1bk11km=1na1kmbkmmk1=1namk1bk11km=1namkmbkmm|
=k1,,km=1n|a1k1bk11a1kmbkmmamk1bk11amkmbkmm|
=k1,,km=1nA(12mk1k2km)bk11bk22bkmm.

In both steps above, we have used the property that the determinant is multilinearMathworldPlanetmath in the colums of a matrix.

Note that the terms in the last sum with any two k’s the same will make the minor of A vanish. And, for {k1,,km}’s that differ only by a permutationMathworldPlanetmath, the minor of A will simply change sign according to the parity of the permutation. Hence the determinant of C can be rewritten as

|C| =1k1<<kmnA(12mk1k2km)σSmsgn(σ)bkσ(1)1bkσ(2)2bkσ(m)m,

where Sm is the permutation groupMathworldPlanetmath on m elements. But the last sum is none other than the determinant B(k1k2km12m). Hence we write

|C|=1k1<<kmnA(12mk1k2km)B(k1k2km12m),

which is the Cauchy-Binet formula. ∎

Title Cauchy-Binet formula
Canonical name CauchyBinetFormula
Date of creation 2013-03-22 14:07:04
Last modified on 2013-03-22 14:07:04
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 11
Author CWoo (3771)
Entry type Theorem
Classification msc 15A15
Synonym Binet-Cauchy formula
Related topic MinorOfAMatrix