19.4 Determinants

There are many way to think about determinants.

19.4.1 Combinatorial approach

Definition 19.4.1

We define the set SnS_{n} as the set of bijective maps from [n][n][n]\to[n].

Theorem 19.4.1

The algebra (Sn,)(S_{n},\circ) is a group (where \circ is the function composition operator).

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][n]e:[n]\to[n] where e(i)=ie(i)=i for all e[n]e\in[n]) and then prove that all permutations are invertible (which we get for free because we know that all σSn\sigma\in S_{n} are bijective, and thus are invertible).

To show that ee is a neutral element, consider some σSn\sigma\in S_{n} for which,

(eσ)(x)\displaystyle(e\circ\sigma)(x) =e(σ(x))\displaystyle=e(\sigma(x)) (19.114)
=σ(x)\displaystyle=\sigma(x) As ee maps every function to the same point. (19.115)

The other way is proven in the same way.

Definition 19.4.2

The length of a permutation is the number of \sayinversions in the permutation. TODO: finish

Definition 19.4.3

One way to define the determinant is using \saypermutations, that is as

det(A)=σSn(1)σ1inAi,σ(i)\det(A)=\sum_{\sigma\in S_{n}}(-1)^{\sigma}\prod_{1\leqq i\leqq n}A_{i,\sigma(% i)} (19.116)

Multiplicatively of the determinant

This is a very important property of the determinant.

The basic result we are after is that

Theorem 19.4.2

Let AA and BB be matrices, then

det(AB)=det(A)det(B)\det(AB)=\det(A)\det(B) (19.117)

Proof: todo.

Block multiplication property

Theorem 19.4.3

Let 𝕂\mathbb{K} be a field, and let A𝕂m×mA\in\mathbb{K}^{m\times m}, B𝕂(m)×(nm)B\in\mathbb{K}^{(m)\times(n-m)}, C𝕂(nm)×(nm)C\in\mathbb{K}^{(n-m)\times(n-m)} and 0𝕂(nm)×m0\in\mathbb{K}^{(n-m)\times m} such that all entries in 0 are (surprise!) the zero element.

Let MM be the matrix whose entries come from the field 𝕂\mathbb{K} defined by

M:=(AB0C).M:=\begin{pmatrix}A&B\\ 0&C\\ \end{pmatrix}. (19.118)


det(M)=det(A)×det(C)\displaystyle\det(M)=\det(A)\times\det(C) (19.119)

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)\det(M),

det(M)\displaystyle\det(M) =σSn+m[(1)σM1,σ(1)M2,σ(2)Mn+m,σ(n+m)]\displaystyle=\sum_{\sigma\in S_{n+m}}\left[(-1)^{\sigma}M_{1,\sigma(1)}M_{2,% \sigma(2)}...M_{n+m,\sigma(n+m)}\right] (19.120)

If we think carefully about what we want, we’d like to end up with something that looks a bit like det(A)×det(C)\det(A)\times\det(C), and thus we should try to split this into two parts - one for det(A)\det(A) and one for det(C)\det(C). We can try something like

=σSn+m[(1)σ1imMi,σ(i)to line up with Am<jn+mMj,σ(j)to line up with B]\displaystyle=\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] (19.121)

Here we have something which is close to what we want. Ideally (or, as they say \sayif there is any fairness in the universe) we would have a permutation σ\sigma such that 1σ(i)m1\leqq\sigma(i)\leqq m (note: this is the same ii, with the same bounds as the one in the sum), as that way the index 1,σ(i)1,\sigma(i) will be in AA (as AA is in the top-left corner and is an m×mm\times m matrix) and such that m<σ(j)n+mm<\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 rigorousTM\text{rigorous}^{\text{TM}} formulation. We really want to define a set XSn+mX\subseteq S_{n+m} such that for all pXp\in X, we have for all 1im1\leqq i\leqq m that 1p(i)n1\leqq p(i)\leqq n and also for all m<jn+mm<j\leqq n+m it is the case that m<p(j)n+mm<p(j)\leqq n+m. Then, we can partition Sn+mS_{n+m} as Sn+m=XXS_{n+m}=X\cup X^{\complement} where XX^{\complement} denotes all the items in Sn+mS_{n+m} that are not in XX (which means XX=∅︀X\cap X^{\complement}=\emptyset). Therefore,

det(M)\displaystyle\det(M) =σX[(1)σ1imMi,σ(i)m<jn+mMj,σ(j)]\displaystyle=\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] (19.123)
+σX[(1)σ1inMi,σ(i)n<jn+mMj,σ(j)]\displaystyle\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]

Note that the right-hand part of the sum is zero, as for each term in the sum there exists some jj such that m<jn+mm<j\leqq n+m where 1σ(j)m1\leqq\sigma(j)\leqq m, that is we have some Mj,σ(j)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

det(M)\displaystyle\det(M) =σX[(1)σ1imMi,σ(i)m<jn+mMj,σ(j)]\displaystyle=\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] (19.124)

Let us consider some permutation σX\sigma\in X. Note that we can write σ=σaσb\sigma=\sigma_{a}\circ\sigma_{b} where a:[m][m]a:[m]\to[m], σa=(a(1),a(2),,a(m),m+1,,m+n)\sigma_{a}=(a(1),a(2),...,a(m),m+1,...,m+n), b:[nm][nm]b:[n-m]\to[n-m] and (1,2,,m,b(m+1),,b(m+n))(1,2,...,m,b(m+1),...,b(m+n)), therefore we can write the sum as

det(M)\displaystyle\det(M) =aSmbSnm[(1)a(1)b1imMi,a(i)m<jn+mMj,b(j)]\displaystyle=\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] (19.125)
=aSmbSnm[(1)a(1)b1imMi,a(i)m<jn+mMj,b(j)]\displaystyle=\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] (19.126)
=aSm[bSnm[(1)a(1)b1imMi,a(i)m<jn+mMj,b(j)]]\displaystyle=\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] (19.127)
=aSm[(1)a1imMi,a(i)σbSnm[(1)bm<jn+mMj,b(j)]]\displaystyle=\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] (19.128)
=(aSm[(1)a1imMi,a(i)])(σbSnm[(1)bm<jn+mMj,b(j)])\displaystyle=\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) (19.129)
=det(A)×det(B)\displaystyle=\det(A)\times\det(B) (19.130)

19.4.2 Using matrices

If you consider how differentiation from \sayfirst principles is not the most exciting thing (it’s definitely useful to know how to do it, but in general, from first principles is not how people differentiate), we have a similar thing with determinants.

This is illustrated by this example/theorem hybrid.

Theorem 19.4.4

For any A𝖬n×n(𝕂)A\in\textsf{M}_{n\times n}(\mathbb{K}) (read: any n×nn\times n matrix with entries in a field 𝐊\mathbf{K},

det(A)=det(AT)\det(A)=\det(A^{T}) (19.131)
Example 19.4.1

Prove Theorem 19.4.4.

We could do this by considering the definition in Definition 19.116, but it’s easier to prove this by using elementary matrices.

We know that if AA is invertible, then using elementary row-operations we can reduce it to the identity matrix; i.e. there exist elementary matrices E1,E2,,EkE_{1},E_{2},...,E_{k} such that

A(E1E2Ek)=IA(E_{1}E_{2}...E_{k})=I (19.132)

As elementary matrices are invertible, from this we can infer that

A\displaystyle A =(E1E2Ek)1\displaystyle=(E_{1}E_{2}...E_{k})^{-1} (19.133)
=(Ek)1(E2)1(E1)1.\displaystyle=(E_{k})^{-1}(E_{2})^{-1}...(E_{1})^{-1}. (19.134)

Then, considering ATA^{T}, we get

AT\displaystyle A^{T} =((Ek)1(Ek1)1(E1)1)T\displaystyle=\Big{(}(E_{k})^{-1}(E_{k-1})^{-1}...(E_{1})^{-1}\Big{)}^{T} (19.135)
=((E1)1)T((Ek1)1)T((Ek)1)T.\displaystyle=((E_{1})^{-1})^{T}...((E_{k-1})^{-1})^{T}((E_{k})^{-1})^{T}. (19.136)

These expressions are pretty similar; we know (todo: add proof) that the determinant of any elementary matrix is equal to its determinant, so applying the multiplicative property of determinants, we have shown that

det(A)=det(AT).\det(A)=\det(A^{T}). (19.137)