A calculus of the absurd

22.5 Determinants

There are many way to think about determinants.

22.5.1 Combinatorial approach

Proof: function composition is associative (todo: link to proof) so all we must do is show that there exists a neutral element, which it is not unreasonable to guess would be the identity function (i.e. \(e : [n] \to [n]\) where \(e(i) = i\) for all \(e \in [n]\)) and then prove that all permutations are invertible (which we get for free because we know that all \(\sigma \in S_n\) are bijective, and thus are invertible).

To show that \(e\) is a neutral element, consider some \(\sigma \in S_n\) for which,

\begin{align} (e \circ \sigma )(x) &= e(\sigma (x)) \\ &= \sigma (x) & \text {As $e$ maps every function to the same point.} \end{align}

The other way is proven in the same way.

22.5.1.1 Multiplicatively of the determinant

This is a very important property of the determinant.

The basic result we are after is that

Proof: todo.

22.5.1.2 Block multiplication property

Proof: we use the standard method for proving identities (if it looks like an identity, walks like an identity, and quacks like an identity then it probably is an identity). We start by considering \(\det (M)\),

\begin{align} \det (M) &= \sum _{\sigma \in S_{n + m}} \left [ (-1)^{\sigma } M_{1, \sigma (1)} M_{2, \sigma (2)} ... M_{n + m, \sigma (n + m)} \right ] \end{align} If we think carefully about what we want, we’d like to end up with something that looks a bit like \(\det (A) \times \det (C)\), and thus we should try to split this into two parts - one for \(\det (A)\) and one for \(\det (C)\). We can try something like

\begin{align} &= \sum _{\sigma \in S_{n + m}} \left [ (-1)^{\sigma } \underbrace {\prod _{1 \leqq i \leqq m} M_{i, \sigma (i)}} _{\text {to line up with $A$}} \underbrace {\prod _{m < j \leqq n + m} M_{j, \sigma (j)}} _{\text {to line up with $B$}} \right ] \\ \end{align} Here we have something which is close to what we want. Ideally (or, as they say “if there is any fairness in the universe”) we would have a permutation \(\sigma \) such that \(1 \leqq \sigma (i) \leqq m\) (note: this is the same \(i\), with the same bounds as the one in the sum), as that way the index \(1, \sigma (i)\) will be in \(A\) (as \(A\) is in the top-left corner and is an \(m \times m\) matrix) and such that \(m < \sigma (j) \leqq n + m\) (for the same reasons as the first). We can have this!

What we can do is split the sum into two parts; in the first part we will sum over all the desirable permutations, and in the second part we will sum over all the undesirable permutations. This is of course not a \(\text {rigorous}^{\text {TM}}\) formulation. We really want to define a set \(X \subseteq S_{n + m}\) such that for all \(p \in X\), we have for all \(1 \leqq i \leqq m\) that \(1 \leqq p(i) \leqq n\) and also for all \(m < j \leqq n + m\) it is the case that \(m < p(j) \leqq n + m\). Then, we can partition \(S_{n+m}\) as \(S_{n+m} = X \cup X^{\complement }\) where \(X^{\complement }\) denotes all the items in \(S_{n + m}\) that are not in \(X\) (which means \(X \cap X^{\complement } = \emptyset \)). Therefore,

\begin{align} \det (M) &= \sum _{\sigma \in X} \left [ (-1)^{\sigma } \prod _{1 \leqq i \leqq m} M_{i, \sigma (i)} \prod _{m < j \leqq n + m} M_{j, \sigma (j)} \right ] \\ &\quad + \sum _{\sigma \in X^{\complement }} \left [ (-1)^{\sigma } \prod _{1 \leqq i \leqq n} M_{i, \sigma (i)} \prod _{n < j \leqq n + m} M_{j, \sigma (j)} \right ] \notag \end{align}

Note that the right-hand part of the sum is zero, as for each term in the sum there exists some \(j\) such that \(m < j \leqq n + m\) where \(1 \leqq \sigma (j) \leqq m\), that is we have some \(M_{j, \sigma (j)}\) in the product such that this entry is \(0\), i.e. the whole term must therefore be zero, so all the terms are zero, so the sum is zero, and thus this is the same as

\begin{align} \det (M) &= \sum _{\sigma \in X} \left [ (-1)^{\sigma } \prod _{1 \leqq i \leqq m} M_{i, \sigma (i)} \prod _{m < j \leqq n + m} M_{j, \sigma (j)} \right ] \end{align} Let us consider some permutation \(\sigma \in X\). Note that we can write \(\sigma = \sigma _{a} \circ \sigma _{b}\) where \(a: [m] \to [m]\), \(\sigma _a = (a(1), a(2), ..., a(m), m+1, ..., m+n)\), \(b: [n - m] \to [n - m]\) and \((1, 2, ..., m, b(m+1), ..., b(m+n))\), therefore we can write the sum as

\begin{align} \det (M) &= \sum _{a \in S_m \land b \in S_{n - m}} \left [ (-1)^{a} (-1)^{b} \prod _{1 \leqq i \leqq m} M_{i, a(i)} \prod _{m < j \leqq n + m} M_{j, b(j)} \right ] \\ &= \sum _{a \in S_m \land b \in S_{n - m}} \left [ (-1)^{a} (-1)^{b} \prod _{1 \leqq i \leqq m} M_{i, a(i)} \prod _{m < j \leqq n + m} M_{j, b(j)} \right ] \\ &= \sum _{a \in S_m} \left [ \sum _{b \in S_{n - m}} \left [ (-1)^{a} (-1)^{b} \prod _{1 \leqq i \leqq m} M_{i, a(i)} \prod _{m < j \leqq n + m} M_{j, b(j)} \right ] \right ] \\ &= \sum _{a \in S_m} \left [ (-1)^{a} \prod _{1 \leqq i \leqq m} M_{i, a(i)} \sum _{\sigma _b \in S_{n - m}} \left [ (-1)^{b} \prod _{m < j \leqq n + m} M_{j, b(j)} \right ] \right ] \\ &= \left ( \sum _{a \in S_m} \left [ (-1)^{a} \prod _{1 \leqq i \leqq m} M_{i, a(i)} \right ] \right ) \left ( \sum _{\sigma _b \in S_{n - m}} \left [ (-1)^{b} \prod _{m < j \leqq n + m} M_{j, b(j)} \right ] \right ) \\ &= \det (A) \times \det (B) \end{align}