Permutations

Matrix calculus: Determinants

Permutations

In order to be able to deal with higher-dimensional determinants, we briefly discuss the essentials needed on permutations.

A permutation of $\{1,\ldots,n\}$ is a list of the numbers $1,\ldots,n$ in a specific order. The permutation $\sigma$ is considered as a map from $\{1,\ldots,n\}$ to itself determined by $\sigma(i) = \sigma[i]$ .

This means that the image of $i$ under $\sigma$ is the $i$ -th number of the list $\sigma$ . Thus $\sigma = \rv{1,2}$ is the identity on $\{1,2\}$ and $\sigma = \rv{2,1}$ interchanges $1$ and $2$ . We denote this permutation by $(1,2)$ .

More generally, we denote by $(i,j)$ the permutation of $\{1,\ldots,n\}$ interchanging $i$ and $j$ and fixing all other numbers. (So the notation does not specify the number of elements $n$ .) It is called a transposition. We have $(i,j)=(j,i)$ .

If $\sigma(i) = i$ , then we say that $\sigma$ fixes the number $i$ ; if this is not the case, then we say that $\sigma$ moves $i$ .

The permutation matrix $P_\sigma$ corresponding to $\sigma$ is the $(n\times n)$ -matrix of which the $(\sigma(i),i)$ -entries for $i=1,\ldots,n$ are equal to $1$ and all other entries are $0$ .

For example, $\rv{1,5,3,4,2}$ is the transposition $(2,5)$ , but $\rv{5,4,3,2,1}$ is not a transposition. The latter is the composition $(1,5)(2,4)$ of two transpositions.

The permutation $\rv{5,4,1,3,2}$ is the composition $(1,5)(2,4)(3,5)(4,5)$ of four transpositions. The corresponding matrix is $P_{\rv{5,4,1,3,2}}= \matrix{0&0&1&0&0\\0&0&0&0&1\\0&0&0&1&0\\0&1&0&0&0\\1&0&0&0&0}$

Product We will deal a lot with the composition of permutations. This is the usual composition of maps. Thus, for instance,

$\rv{2,3,1} =\rv{2,1,3} \rv{1,3,2} =(1,2) (2,3)$

We often refer to the composition as a product. In particular, it is customary to say that a permutation is a product of transpositions rather than a composition.

The inverse of a transposition $\tau=(i,j)$ is equal to itself $\tau^{-1}=\tau$ from which it follows that the inverse of a product of $k$ transpositions $\tau_1\tau_2\cdots\tau_k$ equals: $\left(\tau_1\tau_2\cdots\tau_{k-1}\tau_k\right)^{-1}=\tau_k\tau_{k-1}\cdots\tau_2\tau_1$

Example: $[2,3,1]^{-1} = \left((1,2)(2,3)\right)^{-1} = (2,3)(1,2) = [3,1,2]$

Transpositions satisfy the following commutation rules: $\begin{array}{rclccc}(i,j)(k,l)&=&(k,l)(i,j)&\phantom{xx}&\text{ for }& k,l\neq i,j\\ (i,k)(i,j)&=&(i,j)(j,k)=(j,k)(i,k)&\phantom{}&\text{ for }&k\neq i,j\end{array}$ We can therefore interchange the order of two transpositions in such a way that at least one of the transpositions remains unchanged. In the first case even both transpositions remain the same, and we call them commuting transpositions.

Example: $\begin{array}{rcl}(1,2)(2,3) &=& (2,3)(1,3) = (1,3)(1,2)\\ &&\phantom{xx}\color{blue}{(1,2)\text{ and }(2,3)\text{ do not commute}}\\ (1,2)(3,4) &=& (3,4)(1,2)\\ &&\phantom{xx}\color{blue}{(1,2)\text{ and }(3,4)\text{ do commute}}\end{array}$

Matrices The permutation matrix $P_{\sigma}$ satisfies $P_{\sigma}(\vec{e}_i) =\vec{e}_{\sigma(i)}$ , where $\basis{\vec{e}_1,\ldots,\vec{e}_n}$ is the standard basis for $\mathbb{R}^n$ . This implies that the product of two permutation matrices is the permutation matrix corresponding to the product of the two permutations: if $\sigma$ and $\tau$ are both permutations of $\{1,\ldots,n\}$ , then we have $P_\sigma\, P_\tau = P_{\sigma\,\tau}$ After all, $P_\sigma\,P_\tau (\vec{e}_i) = P_\sigma(\vec{e}_{\tau (i)}) = \vec{e}_{\sigma\,\tau(i)} = P_{\sigma\,\tau}(\vec{e}_i)$ Since $P_\sigma\,P_\tau$ and $P_{\sigma\,\tau}$ have the same images on the vectors of the standard basis, they are identical. This also follows immediately from the theorem Composition of maps defined by matrices.

Convention

In this course we choose to define the permutation matrix corresponding to $\sigma$ as the $(n\times n)$ -matrix of which the $(\sigma(i),i)$ -entries for $i=1,\ldots,n$ are equal to $1$ and all other entries are $0$ . The advantage of this choice is that $P_{\sigma}$ satisfies $P_{\sigma}(\vec{e}_i) = \vec{e}_{\sigma(i)}$ so that we can easily write down the images of the standard basis vectors of $\mathbb{R}^n$ . Column $i$ of $P_\sigma$ equals $\vec{e}_{\sigma(i)}$ .

Outside of this course you can also find the convention in which the permutation matrix corresponding to $\sigma$ is the $(n\times n)$ -matrix of which the $(i,\sigma(i))$ -entries for $i=1,\ldots,n$ are equal to $1$ and all other entries are $0$ . In this case, not the $i$ -th column but the $i$ -th row of $P_\sigma$ equals $\vec{e}_{\sigma(i)}$ . The advantage of this choice is that $P_{\sigma}$ satisfies $\left(P_{\sigma}(\vec{v})\right)_i=v_{\sigma(i)}$ for a vector $\vec{v}=\rv{v_1,v_2,\ldots,v_n}$ .

De permutation matrix in one convention equals the transpose of the permutation matrix in the other convention.

We can replace $\{1,\ldots,n\}$ by an arbitrary set $X$ of $n$ elements and speak of a permutation of $X$ . Once we have enumerated the elements of $X$ by $1,2,\ldots,n$ , we come back to a permutation of $\{1,\ldots,n\}$ . Just as for the coordinatization of linear maps, different enumerations lead to conjugate permutations. Here, we will not pursue this further.

We will need to be able to distinguish between products of even and odd length.

The sign of a permutation

A map $\{1,\ldots,n\}\to\{1,\ldots,n\}$ is a permutation of $\{1,\ldots,n\}$ if and only if it is a bijective map.
The number of permutations of $\{1,\ldots,n\}$ is equal to $1\cdot 2\cdots (n-1)\cdot n$ . This number is often denoted by $n!$ and called $n$ factorial.
Every permutation can be written as a product of transpositions. (The composition of $0$ permutations is defined to be the identity map $\rv{1,2,\ldots,n}$ .)
If a permutation can be written in two ways as a product of transpositions, then both products have even length or both products have odd length.

The sign of a permutation $\sigma$ is $1$ if $\sigma$ is the product of an even number of transpositions and $-1$ otherwise. It is denoted $\text{sg}(\sigma)$ .

1. The theorem Invertibility with the same dimensions for domain and codomain says that a map $f: \{1,\ldots,n\}\to\{1,\ldots,n\}$ is bijective if and only if it is surjective, in which case the list $\rv{f(1),f(2),\ldots,f(n)}$ consists of $n$ different numbers in $\{1,\ldots,n\}$ . This is the case if and only if $f$ is a permutation.

2. We use the notation $n!=1\cdot 2\cdots (n-1)\cdot n$ and show by induction on $n$ that $n!$ is the number of ways to fill a list of length $n$ with elements from $\{1,2,\ldots,n\}$ such that each element occurs exactly once. This will suffice for the proof.

For $n=1$ , the number of ways to fill a list of length $1$ with $1$ is indeed $1!=1$ .

For the induction step in our proof using induction on $n$ we now assume $n\gt 1$ . There are $n$ possibilities of filling the first place of the list with a number $k\in \{1,\ldots,n\}$ . Once we have done so for a fixed $k$ , we can complete the list of length $n-1$ of the remaining places by putting each of the $n-1$ numbers $1,\ldots,k-1,k+1,\ldots,n$ at one place. By the induction hypothesis, the number of ways this can be done, is $(n-1)!$ (it does not matter what the $n-1$ integers are called, as long as they are mutually distinct). We conclude that $n! = n\cdot (n-1)! = n\cdot (n-1)\cdot n \cdots 2 \cdot 1$ is the number of ways we can fill a list of length $n$ with elements from $\{1,2,\ldots,n\}$ such that each element occurs exactly once.

3. Let $\sigma$ be a permutation. If $\sigma$ is the identity, that is, $\sigma =\rv{1,2,\ldots,n}$ , then $\sigma$ is the product of $0$ transpositions.

If not, then there are integers that are moved by $\sigma$ . Let $v$ be the number of integers in $\{1,\ldots,n\}$ moved by $\sigma$ . We prove the statement by induction on $v$ . If $v=0$ , then $\sigma$ must be the identity, which we have already treated. Suppose now $v\gt0$ . Then there is an integer $\ell\in \{1,\ldots,n\}$ with $\sigma(\ell)\ne\ell$ . Write $m=\sigma(\ell)$ . Then also $\sigma(m)\ne m$ , for otherwise we would have $\sigma(m)=m=\sigma(\ell)$ and $m\ne\ell$ , contradicting that $\sigma$ is injective. Thus, both $\ell$ and $m$ contribute to the number $v$ of integers moved by $\sigma$ . Now consider the product $\tau=\sigma\,(\ell,m)$ of $\sigma$ and the transposition $(\ell,m)$ . If $k\in\{1,\ldots,n\}$ is distinct from $\ell$ and $m$ , then $\tau(k)=\sigma(k)$ , so the number $v-2$ of integers distinct from $\ell$ and $m$ moved by $\sigma$ equals the number of integers distinct from $\ell$ and $m$ moved by $\tau$ . In addition, we have $\tau[m]=\sigma(\ell,m)[m]= \sigma[\ell]=m$ so $m$ is not moved by $\tau$ . As a consequence, $\tau$ moves fewer integers than $\sigma$ . By the induction hypothesis, $\tau$ is a product of transpositions. Therefore $\sigma = \tau\, (\ell,m)$ is also a product of transpositions.

4. Suppose the permutation $g$ can be written as the product of transpositions $\mu_1\cdots\mu_p$ with $p$ even, and suppose that $g$ can also be written as the product of transpositions $\nu_1\cdots\nu_q$ with $q$ odd. Then the identity $e$ can be written as $e=gg^{-1}=\mu_1\cdots\mu_p\left(\nu_1\cdots \nu_q\right)^{-1}=\mu_1\cdots\mu_p\nu_q\cdots \nu_1$ in which the number of transpositions in the last product is odd. We show that this is impossible.

Suppose we can write the identity as the product of $m\geq 2$ transpositions: $e=\tau_1\cdots \tau_m$ in which $m$ can be either even or odd. We show that there exists an algorithm to simplifiy this product to a product of $m-2$ transpositions. For even $m$ , we can simplify the product by repeated application of the algorithm to a product of zero transpositions, which equals the identity by definition. For odd $m$ , we could simplify the product by repeated application of the algorithm to a single transposition, which contradicts the assumption that the product equals the identity. In the rest of the proof we describe the algorithm.

We may assume that $\tau_1=(1,2)$ . After all, if $\tau_1 = (i,j)$ is not equal to $(1,2)$ then we define $\kappa\equiv(1,i)(2,j)$ and write: $\begin{array}{rcl}e&=& \kappa\kappa^{-1}\\&=& \kappa e\kappa^{-1}\\ &=&\kappa\tau_1\cdots \tau_m\kappa^{-1}\\&=&\kappa\tau_1e\tau_2e\tau_3\cdots e\tau_{m-1}e\tau_m\kappa^{-1}\\&=&\kappa\tau_1\left(\kappa^{-1}\kappa\right)\tau_2\left(\kappa^{-1}\kappa\right)\tau_3\cdots\left(\kappa^{-1}\kappa\right)\tau_{m-1}\left(\kappa^{-1}\kappa\right)\tau_m\kappa^{-1}\\&=&\left(\kappa\tau_1\kappa^{-1}\right)\left(\kappa \tau_2\kappa^{-1}\right)\left(\kappa \tau_3\kappa^{-1}\right)\cdots \left(\kappa\tau_{m-1}\kappa^{-1}\right)\left(\kappa\tau_m\kappa^{-1}\right)\\ &=&\rho_1\cdots\rho_m\end{array}$ where we have defined $\rho_k\equiv\kappa\tau_k\kappa^{-1}$ for all $k$ in $\{1,\ldots,m\}$ . For each possible value of $k$ we apply the commutation rules to $\kappa$ and $\tau_k$ in such a way that the transpositions in $\kappa$ remain unchanged so that, thanks to $\kappa\kappa^{-1}=e$ , each permutation $\rho_k$ simplifies to a transposition. In particular (we follow the changes in $\tau_1$ in green): $\begin{array}{rcll}\rho_1&=&\kappa\color{green}{\tau_1}\kappa^{-1}&\phantom{xyzuvw}\color{blue}{\text{definition }\rho_1}\\ &=&(1,i)(2,j)\color{green}{(i,j)}(2,j)(1,i)&\phantom{xyzuvw}\color{blue}{\kappa\equiv(1,i)(2,j), \tau_1=(i,j)}\\ &=&(1,i)\color{green}{(2,i)}(2,j)(2,j)(1,i)&\phantom{xyzuvw}\color{blue}{(2,j)(i,j)=(2,i)(2,j)}\\ &=&(1,i)\color{green}{(2,i)}(1,i)&\phantom{xyzuvw}\color{blue}{(2,j)(2,j)=e}\\ &=&\color{green}{(1,2)}(1,i)(1,i)&\phantom{xyzuvw}\color{blue}{(1,i)(2,i)=(1,2)(1,i)}\\&=&\color{green}{(1,2)}&\phantom{xyzuvw}\color{blue}{(1,i)(1,i)=e}\end{array}$ A product of transpositions can thus always be rewritten as a product of the same number of transpositions whose first one is $(1,2)$ . We may therefore assume that this rewriting has already taken place in the original product $\tau_1\cdots\tau_m$ so that we may assume that $\tau_1=(1,2)$ .

We may further assume that there exists a natural number $\ell$ in $\{1,\ldots,m\}$ for which each of the transpositions $\tau_1,\ldots,\tau_\ell$ move $1$ (that is, have the form $(1,a)$ with $a$ in $\{2,\ldots,n\}$ ) and, in case $\ell\lt m$ , each of the transpositions $\tau_{\ell+1},\ldots,\tau_m$ fix $1$ . After all, we can apply the commutation rules repeatedly to neighbouring transpositions in the product $\tau_1\cdots\tau_m$ such that all transpositions that move $1$ end up on the left relative to all transpositions that fix $1$ . We do not change the total number of transpositions in the product by not applying possible simplifications. We assume that this separation has already taken place in the original product $\tau_1\cdots \tau_m$ .

We have $\ell\geq 2$ . After all, for $\ell=1$ we find $\begin{array}{rcll}\tau_1(1)&=&\tau_1\tau_2\cdots\tau_m(1)&\phantom{xyzuvw}\color{blue}{m\geq 2\text{ and }\tau_2,\ldots,\tau_m\text{ fix }1}\\&=&e(1)&\phantom{xyzuvw}\color{blue}{\tau_1\cdots\tau_m=e}\\&=&1&\phantom{xyzuvw}\color{blue}{\text{identity fixes all integers}}\end{array}$ in contradiction to $\tau_1(1)=2$ .

Thanks to $\ell\geq 2$ the product $\tau_2\cdots\tau_\ell$ is well defined, so we can apply it to $1$ : $\begin{array}{rcll}\tau_2\cdots\tau_\ell(1)&=& \tau_1\tau_1\tau_2\cdots\tau_\ell(1)&\phantom{xyzuvw}\color{blue}{\tau_1\tau_1=e}\\&=&\tau_1\tau_1\tau_2\cdots\tau_m(1)&\phantom{xyzuvw}\color{blue}{\ell=m\text{ or }\tau_{\ell+1},\ldots,\tau_m\text{ fix }1}\\&=&\tau_1(1)&\phantom{xyzuvw}\color{blue}{\tau_1\cdots\tau_m=e}\\&=&2&\phantom{xyzuvw}\color{blue}{\tau_1=(1,2)}\end{array}$ This means there must exist at least one index $j$ with $2\le j\le\ell$ such that $\tau_j=(1,2)=\tau_1$ . Let $j$ be the smallest index for which this is true. For $j=2$ we find: $\begin{array}{rcll}e&=&\tau_1\tau_1\tau_3\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\text{substituted }\tau_2=\tau_1}\\&=&\tau_3\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_1^2=e}\end{array}$ so that the total number of transpositions reduces by two. For $j\geq 3$ we find: $\begin{array}{rcll}e&=&\tau_1\cdots \tau_{j-1}\tau_1\tau_{j+1}\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\text{substituted }\tau_j=\tau_1}\\&=&\left(\tau_1\tau_2\tau_1\right)\left(\tau_1\tau_3\tau_1\right)\cdots \left(\tau_1\tau_{j-1}\tau_1\right)\tau_{j+1}\cdots\tau_m&\phantom{xyzuvw}\color{blue}{\tau_1^2=e}\\&=&\sigma_2\sigma_3\cdots \sigma_{j-1}\tau_{j+1}\cdots\tau_m&\phantom{xyzuvw}\color{blue}{\sigma_i\equiv\tau_1\tau_i\tau_1}\end{array}$ where we defined $\sigma_i\equiv\tau_1\tau_i\tau_1$ for all $i$ in $\{2,\ldots,j-1\}$ . For all these values of $i$ we apply the commutation rules to $\tau_1$ and $\tau_i$ while keeping $\tau_1$ unchanged, thereby simplifying, thanks to $\tau_1\tau_1=e$ , each $\sigma_i$ to a single transposition. We will now show that explicitly. The ordering $i\lt j\leq\ell$ implies that there exist $j-2$ numbers $a_i\neq 2$ such that $\tau_i=(1,a_i)$ and $\begin{array}{rcll}\sigma_i&\equiv&\tau_1\tau_i\tau_1&\phantom{xyzuvw}\color{blue}{\text{definition }\sigma_i\text{ for }i\in\{2,\ldots,j-1\}}\\&=&(1,2)(1,a_i)(1,2)&\phantom{xyzuvw}\color{blue}{\tau_1=(1,2),\tau_i=(1,a_i)\text{ since }i\lt\ell}\\&=&(2,a_i)(1,2)(1,2)&\phantom{xyzuvw}\color{blue}{a_i\neq 2\text{ since }i\lt j}\\&=&(2,a_i)&\phantom{xyzuvw}\color{blue}{(1,2)(1,2)=e}\end{array}$ We see that, in all cases, the identity can be written as a product of $m-2$ transpositions: $e=\underbrace{\sigma_2\sigma_3\cdots \sigma_{j-1}}_{j-2\text{ factors}}\underbrace{\tau_{j+1}\cdots\tau_m}_{m-j\text{ factors}}\qquad 2\leq j\leq m$ After all, $(j-2)+(m-j)=m-2$ .

Thanks to statements three and four, the notion of "sign of a permutation" is well defined.

If $\sigma$ and $\tau$ are permutations of the same set, then $\text{sg}(\sigma\,\tau)=\text{sg}(\sigma)\cdot\text{sg}(\tau)$ This follows directly from the definition of the sign in terms of the number of transpositions occurring in an expression of the permutation as a product of transpositions.

Write the permutation $\sigma=\left[ 3 , 5 , 1 , 2 , 4 \right]$ as a product of transpositions.

Give your answer as a product of transpositions without multiplication signs.

$\left[ 3 , 5 , 1 , 2 , 4 \right] =$ $(1,3)(2,5)(4,5)$

Since $\sigma$ maps the element $1$ onto $3$ , the permutation $\sigma$ is the product of the transposition $(1,3)$ and the permutation $\tau=[1,5,3,2,4]$ that fixes $1$ . Next we write $\tau$ as a product of a transposition of the form $(2,a)$ for suitable $a$ and a permutation fixing $1$ and $2$ , and so on. This way we can write $\left[ 3 , 5 , 1 , 2 , 4 \right]$ as the product of at most $4$ transpositions.

We find
$\begin{array}{rcl} \left[ 3 , 5 , 1 , 2 , 4 \right] &=& (1,3)\,[1,5,3,2,4]\\ &=& (1,3)\,(2,5)\,[1,2,3,5,4]\\ &=& (1,3)\,(2,5)\,(4,5)\,[1,2,3,4,5] \\ &=& (1,3)(2,5)(4,5) \end{array}$

There are many ways of writing the permutation as a product of transpositions.

New example