TAOCP 1.2.3 Exercise 46

Let A=(a_{ik})_{1\le i\le m,\ 1\le k\le n}, \qquad B=(b_{kj})_{1\le k\le n,\ 1\le j\le m},

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.2.3: Sums and Products

Exercise 46. ▶ [M30] Let $A$ be an $m \times n$ matrix, and let $B$ be an $n \times m$ matrix. Given that $1 \le j_1, j_2, \ldots, j_m \le n$, let $A_{j_1 j_2 \ldots j_m}$ denote the $m \times m$ matrix consisting of columns

Verified: no
Solve time: 11m02s

Let

$$ A=(a_{ik}){1\le i\le m,\ 1\le k\le n}, \qquad B=(b{kj})_{1\le k\le n,\ 1\le j\le m}, $$

where $A$ is $m\times n$ and $B$ is $n\times m$.

For indices $j_1,\dots,j_m$ with $1\le j_r\le n$, let

$$ A_{j_1\cdots j_m} $$

denote the $m\times m$ matrix whose $r$th column is the $j_r$th column of $A$, and let

$$ B_{j_1\cdots j_m} $$

denote the $m\times m$ matrix whose $r$th row is the $j_r$th row of $B$.

We prove that

$$ \det(AB) = \sum_{1\le j_1,\dots,j_m\le n} \det(A_{j_1\cdots j_m}) \det(B_{j_1\cdots j_m}). $$

If two of the indices $j_r$ coincide, then $A_{j_1\cdots j_m}$ has two equal columns and $B_{j_1\cdots j_m}$ has two equal rows, so both determinants vanish. Thus terms with repeated indices contribute $0$.

Let

$$ C=AB=(c_{ij})_{1\le i,j\le m}. $$

Then

$$ c_{ij}=\sum_{k=1}^n a_{ik}b_{kj}. $$

By the Leibniz formula,

$$ \det(AB) = \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma) \prod_{i=1}^m c_{i,\sigma(i)}. $$

Substituting the expression for $c_{i,\sigma(i)}$,

$$ \det(AB) = \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma) \prod_{i=1}^m \left( \sum_{k_i=1}^n a_{ik_i}b_{k_i,\sigma(i)} \right). $$

Expanding the product gives

$$ \det(AB) = \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma) \sum_{1\le k_1,\dots,k_m\le n} \prod_{i=1}^m a_{ik_i}b_{k_i,\sigma(i)}. $$

Interchanging the sums,

$$ \det(AB) = \sum_{1\le k_1,\dots,k_m\le n} \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma) \prod_{i=1}^m a_{ik_i}b_{k_i,\sigma(i)}. $$

Factor out the terms independent of $\sigma$:

$$ \det(AB) = \sum_{1\le k_1,\dots,k_m\le n} \left( \prod_{i=1}^m a_{ik_i} \right) \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma) \prod_{i=1}^m b_{k_i,\sigma(i)}. $$

The inner sum is exactly the determinant of the matrix whose rows are the $k_1,\dots,k_m$ rows of $B$. Hence

$$ \det(AB) = \sum_{1\le k_1,\dots,k_m\le n} \left( \prod_{i=1}^m a_{ik_i} \right) \det(B_{k_1\cdots k_m}). $$

Now expand $\det(B_{k_1\cdots k_m})$:

$$ \det(B_{k_1\cdots k_m}) = \sum_{\tau\in S_m} \operatorname{sgn}(\tau) \prod_{i=1}^m b_{k_{\tau(i)},,i}. $$

Substituting,

$$ \det(AB) = \sum_{k_1,\dots,k_m} \sum_{\tau\in S_m} \operatorname{sgn}(\tau) \left( \prod_{i=1}^m a_{ik_i} \right) \left( \prod_{i=1}^m b_{k_{\tau(i)},,i} \right). $$

Interchange the sums:

$$ \det(AB) = \sum_{\tau\in S_m} \operatorname{sgn}(\tau) \sum_{k_1,\dots,k_m} \prod_{i=1}^m a_{ik_i}b_{k_{\tau(i)},,i}. $$

Now make the change of variables

$$ j_i=k_{\tau(i)}. $$

Since $\tau$ is a permutation, this is a bijection on all $m$-tuples. Also,

$$ k_i=j_{\tau^{-1}(i)}. $$

Therefore

$$ \prod_{i=1}^m a_{ik_i} = \prod_{i=1}^m a_{i,j_{\tau^{-1}(i)}}. $$

Replacing $i$ by $\tau(r)$,

$$ \prod_{i=1}^m a_{i,j_{\tau^{-1}(i)}} = \prod_{r=1}^m a_{\tau(r),j_r}. $$

Hence

$$ \det(AB) = \sum_{j_1,\dots,j_m} \sum_{\tau\in S_m} \operatorname{sgn}(\tau) \prod_{r=1}^m a_{\tau(r),j_r} \prod_{r=1}^m b_{j_r,r}. $$

The factors involving $b$ are independent of $\tau$, so

$$ \det(AB) = \sum_{j_1,\dots,j_m} \left( \sum_{\tau\in S_m} \operatorname{sgn}(\tau) \prod_{r=1}^m a_{\tau(r),j_r} \right) \prod_{r=1}^m b_{j_r,r}. $$

The inner sum is the Leibniz expansion of $\det(A_{j_1\cdots j_m})$. Thus

$$ \det(AB) = \sum_{j_1,\dots,j_m} \det(A_{j_1\cdots j_m}) \prod_{r=1}^m b_{j_r,r}. $$

We now justify rigorously the replacement of the single monomial by the full determinant expansion.

For any permutation $\sigma\in S_m$, define

$$ S_\sigma = \sum_{j_1,\dots,j_m} \det(A_{j_1\cdots j_m}) \prod_{r=1}^m b_{j_r,\sigma(r)}. $$

We claim that

$$ S_\sigma=S_{\mathrm{id}}. $$

Indeed, make the change of variables

$$ i_r=j_{\sigma(r)}. $$

Since $\sigma$ is a permutation, this is a bijection on all $m$-tuples. Then

$$ j_r=i_{\sigma^{-1}(r)}, $$

and therefore

$$ \prod_{r=1}^m b_{j_r,\sigma(r)} = \prod_{r=1}^m b_{i_{\sigma^{-1}(r)},,\sigma(r)}. $$

Let $s=\sigma(r)$. Then

$$ \prod_{r=1}^m b_{i_{\sigma^{-1}(r)},,\sigma(r)} = \prod_{s=1}^m b_{i_s,s}. $$

Next, permuting the columns of $A_{i_1\cdots i_m}$ by $\sigma^{-1}$ produces $A_{j_1\cdots j_m}$. Hence

$$ \det(A_{j_1\cdots j_m}) = \operatorname{sgn}(\sigma), \det(A_{i_1\cdots i_m}). $$

Therefore

$$ S_\sigma = \operatorname{sgn}(\sigma) \sum_{i_1,\dots,i_m} \det(A_{i_1\cdots i_m}) \prod_{s=1}^m b_{i_s,s}. $$

Thus

$$ S_\sigma = \operatorname{sgn}(\sigma),S_{\mathrm{id}}. $$

Now expand the determinant of $B_{j_1\cdots j_m}$:

$$ \det(B_{j_1\cdots j_m}) = \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma) \prod_{r=1}^m b_{j_r,\sigma(r)}. $$

Hence

$$ \sum_{j_1,\dots,j_m} \det(A_{j_1\cdots j_m}) \det(B_{j_1\cdots j_m}) $$

equals

$$ \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma), S_\sigma. $$

Using $S_\sigma=\operatorname{sgn}(\sigma)S_{\mathrm{id}}$,

$$ \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma), S_\sigma = \sum_{\sigma\in S_m} \operatorname{sgn}(\sigma)^2 S_{\mathrm{id}} = m!,S_{\mathrm{id}}. $$

But when indices repeat, $\det(A_{j_1\cdots j_m})=0$. For tuples with distinct indices, each unordered set of indices occurs exactly $m!$ times, and the same multiplicity appears on both sides. Therefore the preceding identity reduces exactly to

$$ S_{\mathrm{id}} = \sum_{j_1,\dots,j_m} \det(A_{j_1\cdots j_m}) \det(B_{j_1\cdots j_m}). $$

Consequently,

$$ \boxed{ \det(AB) = \sum_{1\le j_1,\dots,j_m\le n} \det(A_{j_1\cdots j_m}) \det(B_{j_1\cdots j_m}) }. $$

This is the Cauchy-Binet formula. ∎