# Proving determinant product rule combinatorially

One of definitions of the determinant is:

$\det ({\mathbf C}) =\sum_{\lambda \in S_n} ({\operatorname {sgn} ({\lambda}) \prod_{k=1}^n C_{k \lambda ({k})}})$

I want to prove from this that

$\det \left({\mathbf {AB}}\right) = \det({\mathbf A})\det({\mathbf B})$

What I have so far:

$(AB)_{k\lambda ({k})} = \sum_{j=1}^n A_{kj}B_{j\lambda(k)}$

so we have for the determinant of $\mathbf {AB}$

$\det ({\mathbf {AB}}) =\sum_{\lambda \in S_n} ({\operatorname {sgn} ({\lambda}) \prod_{k=1}^n \sum_{j=1}^n A_{kj}B_{j\lambda(k)}})$

Now I'm not sure how to denote this, but the product of the sum I think is the sum over all combinations of n terms, each ranging from 1 to n, so I'll denote this set of all combinations $C_n(n)$ for n terms each ranging from 1 to n, analogous to the permutation set, but all combinations instead of permutations.

then I get

$\det ({\mathbf {AB}}) =\sum_{\lambda \in S_n} ({\operatorname {sgn} ({\lambda}) \sum_{\gamma \in C_n(n)} \prod_{k=1}^n A_{k\gamma(k)}B_{\gamma(k)\lambda(k)}} )$

then I can at least seperate the product:

$\det ({\mathbf {AB}}) =\sum_{\lambda \in S_n} ({\operatorname {sgn} ({\lambda}) \sum_{\gamma \in C_n(n)} \prod_{k=1}^n A_{k\gamma(k)} \prod_{r=1}^n B_{\gamma(r)\lambda(r)}} )$

I changed the k to an r in one product because it's a dummy variable so I think it doesn't matter, I don't really know if this thing is helpful but this is my attempt at a solution so far.

Thanks to anyone who helps!

-
+1 for showing your efforts in solving the problem –  Alexander Thumm Aug 1 '12 at 13:41

From $$\det ({\mathbf {AB}}) =\sum_{\lambda \in S_n} \operatorname {sgn} (\lambda) \sum_{\gamma \in C_n(n)} \left(\prod_{k=1}^n A_{k\gamma(k)} \right) \left(\prod_{r=1}^n B_{\gamma(r)\lambda(r)} \right)$$ reorder the sums and factor out the first product : $$\det (\mathbf {AB}) =\sum_{\gamma \in C_n(n)} \left(\prod_{k=1}^n A_{k\gamma(k)} \right) \left( \sum_{\lambda \in S_n} \operatorname {sgn} (\lambda) \prod_{r=1}^n B_{\gamma(r)\lambda(r)} \right)$$
For $\gamma \in C_n(n)$, suppose that $\gamma$ is not a permutation : there are two indices $i,j$ such that $\gamma(i) = \gamma(j)$. Let $\tau$ be the transposition swapping $i$ and $j$. In particular, $\gamma \circ \tau = \gamma$. For any $\lambda \in S_n$, by reordering the product, we get : $$\operatorname {sgn} (\lambda)\prod_{r=1}^n B_{\gamma(r)\lambda(r)} = \operatorname {sgn} (\lambda)\prod_{r=1}^n B_{\gamma(\tau(r))\lambda(\tau(r))} = - \operatorname {sgn} (\lambda \circ \tau)\prod_{r=1}^n B_{\gamma(r)\lambda \circ \tau(r)}$$ Thus, by duplicating and reorganizing the sum, $$\sum_{\lambda \in S_n} \operatorname {sgn} (\lambda) \prod_{r=1}^n B_{\gamma(r)\lambda(r)} = \frac 12 \sum_{\lambda \in S_n} \left( \operatorname {sgn} (\lambda) \prod_{r=1}^n B_{\gamma(r)\lambda(r)} + \operatorname {sgn} (\lambda \circ \tau) \prod_{r=1}^n B_{\gamma(r)\lambda \circ \tau(r)(r)}\right) = 0$$ Therefore we may only keep the $\gamma$ that are permutations, and by reordering the second product, we have : $$\det (\mathbf {AB}) =\sum_{\gamma \in S_n} \left(\prod_{k=1}^n A_{k\gamma(k)} \right) \left( \sum_{\lambda \in S_n} \operatorname {sgn} (\lambda) \prod_{r=1}^n B_{r\lambda\circ\gamma^{-1}(r)} \right)$$ By reorganizing the second sum, we get : $$\det (\mathbf {AB}) =\sum_{\gamma \in S_n} \left(\prod_{k=1}^n A_{k\gamma(k)} \right) \left( \sum_{\lambda \in S_n} \operatorname {sgn} (\lambda) \operatorname {sgn} (\gamma)\prod_{r=1}^n B_{r\lambda(r)} \right)$$ We can factor out $\operatorname{sgn}(\gamma)$ from the second sum, then factor out the whole second sum from the first sum, to get $$\det (\mathbf {AB}) = \left( \sum_{\gamma \in S_n} \operatorname {sgn} (\gamma) \prod_{k=1}^n A_{k\gamma(k)} \right) \left( \sum_{\lambda \in S_n} \operatorname {sgn} (\lambda) \prod_{r=1}^n B_{r\lambda(r)} \right) = \det (\mathbf {A})\det (\mathbf {B})$$