KindiakMath

The Power of Permutations

Let \mathbb K be a field and V = \mathbb K^n. Last time, we derived several properties of multilinear and alternative functions T : V^n \to \mathbb K.

We ended our discussions last time noting the key role that transpositions play in helping us extend these properties. Their big brother—permutations—will ultimately turn into the main star of the show.

Denote K := \{1,\dots,n\}.

Theorem 1. Any permutation f \in \mathrm{Sym}(K) can be written as a composition of transpositions.

Proof. For any permutation f : K \to K, define the predicate \Phi_f on K by \Phi_f(i) = (f(i) \neq i). We will perform strong induction on the number of elements that satisfy \Phi_f. If there are exactly 0 such elements, then we have the identity permutation f = \mathrm{id}_K = \begin{pmatrix} 1 & 2 \end{pmatrix}\begin{pmatrix} 1 & 2 \end{pmatrix}.

For the induction step, suppose that for any permutation g such that \Phi_g holds for exactly k < n elements, g can be written as a product of transpositions. Let f be a permutation such that exactly k+1 \leq n elements satisfy \Phi_f. Suppose for 1 \leq i \leq k, f(i) = i+1 without loss of generality. If f(k+1) = k+2, then f being bijective precludes f(k+2) = k+2, so that f has at least k + 2 elements that satisfy \Phi_f, a contradiction. Hence, f(k+1) = 1. Define the permutation

h = \begin{pmatrix} 1 & k+1 \end{pmatrix} \circ f.

Then h(k+1) = \begin{pmatrix} 1 & k+1 \end{pmatrix} (f(k+1)) = \begin{pmatrix} 1 & k+1 \end{pmatrix}(1) = k+1. Furthermore,

h(k) =\begin{pmatrix} 1 & k+1 \end{pmatrix} (f(k)) = \begin{pmatrix} 1 & k+1 \end{pmatrix}(k+1) = 1.

Therefore, with some more bookkeeping, h will be a permutation with exactly k elements that satisfy \Phi_h. By the induction hypothesis, there exist transpositions \phi_1,\dots,\phi_j such that

h = \phi_j \circ \cdots \circ \phi_1.

Consequently,

f = \begin{pmatrix} 1 & k+1 \end{pmatrix} \circ h = \begin{pmatrix} 1 & k+1 \end{pmatrix} \circ \phi_j \circ \cdots \circ \phi_1.

Therefore, we have proven the induction hypothesis, and have shown that every permutation f : K \to K can be written as a product of transpositions.

Since any permutation f can be written as a composition of f = \phi_j \circ \cdots \circ \phi_1, we have basically defined the determinant of the permutation of the standard basis vectors in the following sense:

\det(\mathbf e_{f(1)},\dots,\mathbf e_{f(n)}) = (-1)^j.

There is one potential ambiguity that arises in this definition: if f = \phi_j \circ \cdots \circ \phi_1, then \begin{pmatrix}1 & 2\end{pmatrix} \circ \begin{pmatrix}1 & 2\end{pmatrix} = \mathrm{id}_K yields

\begin{aligned} f &= \begin{pmatrix}1 & 2\end{pmatrix} \circ \begin{pmatrix}1 & 2\end{pmatrix} \circ \phi_j \circ \cdots \circ \phi_1\\ &= \phi_{j+2} \circ \phi_{j+1} \circ \cdots \circ \phi_1.\end{aligned}

Thankfully though, since (-1)^2,

\det(\mathbf e_{f(1)},\dots,\mathbf e_{f(n)}) = (-1)^{j+2} = (-1)^2(-1)^j = (-1)^j.

Therefore, the determinant equals 1 (resp. -1) if f is comprised of an even (resp. odd) number of transpositions. We formalise this observation below.

Definition 1. For any permutation f : K \to K, we call f even (resp. odd) if it is a product of even (resp. odd) transpositions.

Lemma 1. The set \{f \in \mathrm{Sym}(K): f\ \text{is even}\} forms a group under function composition.

Lemma 2. Let f be a composition of transpositions. Then f cannot be even and odd at the same time.

Proof. Suppose f is odd, so that it is a product of 2k+1 transpositions, with the last transposition being \begin{pmatrix} 1 & 2\end{pmatrix} without loss of generality. Then g := \begin{pmatrix} 1 & 2\end{pmatrix} \circ f is a product of 2(k+1) transpositions and is thus even. If f is even, then Lemma 1 yields an even permutation f^{-1}, so that \begin{pmatrix} 1 & 2 \end{pmatrix} = g \circ f^{-1} is even, a contradiction.

Theorem 2. The signature \sigma : \mathrm{Sym}(K) \to \{-1, 1\} defined by

\sigma(f) := \begin{cases} 1, & f\ \text{is even}, \\ -1, & f\ \text{is odd}, \end{cases}

is a well-defined function.

Corollary 1. For any f, g \in \mathrm{Sym}(K), \sigma(f \circ g) = \sigma(f)\sigma(g).

We now have all the tools that we need to derive the formula if T : V^n \to \mathbb K is multilinear, alternative, and normalised.

Theorem 3. If T : V^n \to \mathbb K is multilinear, alternative, and normalised, then

\displaystyle T(\mathbf v_1,\dots,\mathbf v_n) = \sum_{\phi \in \mathrm{Sym}(K)} \sigma(\phi) v_{1,\phi(1)} \cdots v_{n,\phi(n)}.

Proof. For each i, find unique scalars v_{i, 1},\dots, v_{i,n} \in \mathbb K such that

\displaystyle \mathbf v_i = v_{i,1} \mathbf e_1 + \cdots + v_{i,n} \mathbf e_n = \sum_{j=1}^n v_{i,j} \mathbf e_j.

By the multilinear and alternative property in the previous post,

\displaystyle \begin{aligned} T(\mathbf v_1,\dots,\mathbf v_n) &= \sum_{f \in \mathrm{Sym}(K)} v_{1,f(1)} \cdot \dots \cdot v_{n,f(n)} T( \mathbf e_{f(1)} ,\dots, \mathbf e_{f(n)} ). \end{aligned}

By the alternative property and Lemma 2,

T( \mathbf e_{f(1)} ,\dots, \mathbf e_{f(n)} ) = \sigma(f) T( \mathbf e_{1} ,\dots, \mathbf e_{n} ).

By the normalised property, T( \mathbf e_{1} ,\dots, \mathbf e_{n} ) =1. Therefore,

\displaystyle \begin{aligned} T(\mathbf v_1,\dots,\mathbf v_n) &= \sum_{f \in \mathrm{Sym}(K)} \sigma(f) v_{1,f(1)} \cdot \dots \cdot v_{n,f(n)}. \end{aligned}

yielding the desired result.

This right-hand side is what we will define to be the determinant.

Definition 2. Define the determinant \det : \mathcal M_{n \times n}(\mathbb K) \to \mathbb K of an n \times n matrix by

\begin{aligned} \left| \begin{matrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{matrix} \right| &\equiv \det \left( \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{bmatrix} \right) \\ &\equiv \det\left(\begin{bmatrix} a_{11} \\ a_{12} \\ \vdots \\ a_{1n} \end{bmatrix}, \begin{bmatrix} a_{21} \\ a_{22} \\ \vdots \\ a_{2n} \end{bmatrix}, \cdots, \begin{bmatrix} a_{n1} \\ a_{n2} \\ \vdots \\ a_{nn} \end{bmatrix}\right) \\ &:= \sum_{f\in \mathrm{Sym}(\{1,\dots,n\})} \sigma(f) a_{1, f(1)}\cdot \cdots \cdot a_{n, f(n)}. \end{aligned}

The sum on the right-hand side is finite, and thus well-defined, since there are n!:= n \times (n-1) \times \cdots \times 2 \times 1 permutations in \mathrm{Sym}(\{1,\dots,n\}) (this can be established using induction).

As a sanity check, let’s make sure this determinant really does satisfy the three conditions that defined it.

Theorem 2. The determinant \det : V^n \to \mathbb K is multilinear, alternating, and normalised.

Proof. It is obvious that \det is multilinear. For the alternating property, we will aim to establish

\det(\mathbf v_2,\mathbf v_1,\dots , \mathbf v_n)=- \det(\mathbf v_1,\mathbf v_2,\dots , \mathbf v_n)

without loss of generality. We observe that denoting \phi = \begin{pmatrix} 1 & 2\end{pmatrix}, the left-hand side simplifies to

\displaystyle \det( \mathbf v_{\phi(1)}, \mathbf v_{\phi(2)},\dots , \mathbf v_{\phi(n)} ) = \sum_{f \in \mathrm{Sym}(K)} \sigma(f) v_{\phi(1),f(1)} \cdots v_{\phi(n),f(n)}.

We leave it as an exercise to verify that \mathrm{Sym}(K) = \{f \circ \phi : f \in \mathrm{Sym}(K)\} so that the right-hand side can be re-indexed into

\begin{aligned} \displaystyle \det(\mathbf v_2,\mathbf v_1,\dots,\mathbf v_n) &= \det( \mathbf v_{\phi(1)}, \mathbf v_{\phi(2)},\dots , \mathbf v_{\phi(n)} ) \\ &= \sum_{f \in \mathrm{Sym}(K)} \sigma(f \circ \phi) v_{\phi(1),f(\phi(1))} \cdots v_{\phi(n), f(\phi(n))} \\ &= -\sum_{f\in \mathrm{Sym}(K)} \sigma(f) v_{\phi(1),f(\phi(1))} \cdots v_{\phi(n),f(\phi(n))} \\ &= -\sum_{f \in \mathrm{Sym}(K)} \sigma(f) v_{1, f(1)} \cdots v_{n,f(n)} \\ &= -\det(\mathbf v_1, \mathbf v_2, \dots, \mathbf v_n). \end{aligned}

where

\sigma(\phi \circ \psi) = \sigma(\phi)\sigma(\psi) = \sigma(\phi) \cdot(-1) = -\sigma(\phi).

For the normalising property, we observe that v_{i, f(i)} = 1 if and only if f(i)=1. Hence,

v_{1,f(1)} \cdots v_{n,f(n))} \neq 0 \quad \iff \quad f= \mathrm{id}_K.

Since \sigma(\mathrm{id}_K) = 1,

\displaystyle \det(\mathbf v_1,\dots , \mathbf v_n) = \sum_{f\in \mathrm{Sym}(K)} \sigma(f) v_{1,f(1)} \cdots v_{n,f(n)} = 1\cdot v_{1,1} \cdots v_{n,n} = 1.

What we have done is remarkable. We have actually defined the determinant function and proved it satisfies three crucial properties that are fundamental to finite-dimensional vector spaces.

That said, for a 5 \times 5 matrix, we will require 5! = 120 summands. This number starts to grow exceedingly large, and is actually rather impractical to compute the determinant of an actual matrix. The definition certainly satisfies our theoretical concerns—yes, a determinant actually exists and does many of the things we want it to do. But our job is clearly not done—we need to learn how to manipulate them.

Therefore, in the next post, we will learn to manipulate determinants.

—Joel Kindiak, 5 Mar 25, 2245H

,

Published by

joelkindiak

Leave a comment