Distance between permutations

Imagine a space whose points, or vertices, are the elements of ${S_n}$, and each vertex ${\sigma}$ is connected by an edge to each of its neighbors ${\tau \sigma}$, where ${\tau}$ is any transposition.

This picture gives a natural notion of distance between two permutations: it is the smallest number of edges that must be traversed to go from one permutation to the other. More formally,

${ \displaystyle d(\sigma,\pi)=k}$ means that ${k}$ is the smallest integer for which there exist transpositions ${\tau_1,\ldots,\tau_k}$ satisfying

${ \displaystyle \tau_1 \ldots \tau_k\,\sigma=\pi.}$

(Of course, we take ${k=0}$ to mean that ${\sigma=\pi}$.) A pleasant few moments’ thought convinces you that ${d(\cdot,\cdot)}$ is indeed a metric on ${S_n}$.

The definition of ${d}$ can be restated in terms of the length function:

${ \displaystyle d(\sigma, \pi)= l(\pi\sigma^{-1}).}$

A full cycle in ${S_n}$, that is a permutation with exactly one orbit, is at maximum distance from the identity ${\iota}$: ${ \displaystyle d\left(\iota, (1\,2\,\ldots\,n)\right)= l(1\,2\,\ldots\,n)=n-1.}$

Recall that for any transposition ${\tau}$, the length of ${\tau\sigma}$ is ${l(\sigma)+1}$ if ${\tau}$ transposes elements in different orbits of ${\sigma}$, and is ${l(\sigma)-1}$ if it transposes elements within one orbit of ${\sigma}$. Thus, ${\tau\sigma}$ is either ${1}$ unit distance further from ${\iota}$ or ${1}$ unit distance closer to $\iota$.

Signature of a permutation

We have seen that a permutation ${\sigma\in S_n}$ can always be expressed as a product of transpositions. Moreover, for any transposition ${\tau}$ and permutation ${\pi}$ the length of ${\tau \pi}$ is either ${1}$ more or ${1}$ less than the length of ${\pi}$:

${ \displaystyle l(\tau\pi) =l(\pi)\pm 1.}$

Hence

${ \displaystyle (-1)^{l(\pi\tau)}=(-1)\cdot (-1)^{l(\pi)}.}$

Hence writing ${\sigma}$ as a product

${ \displaystyle \sigma=\tau_1\ldots\tau_k,}$

where each ${\tau_j}$ is a transposition, we have

${ \displaystyle (-1)^{l(\sigma)}= (-1) (-1)^{l(\tau_2\ldots\tau_k)}=\underbrace{(-1)(-1)\ldots(-1)}_{k\, {\rm terms}} = (-1)^k.}$

Being ${+1}$ if ${k}$ is even and is ${-1}$ if ${k}$ is odd, it is just the signature of ${\sigma}$.

Thus, the signature of ${\sigma}$ is equal to

${ \displaystyle \epsilon(\sigma)=(-1)^{l(\sigma)}.}$

Displaying permutations ${\sigma}$ and ${\pi}$ each as a product of transpositions produces a display of ${\sigma\pi}$ as a product of transpositions; from this we see that ${ \displaystyle \epsilon(\sigma\pi)=\epsilon(\sigma)\epsilon(\pi).}$ We can understand the signature further by considering the relationship between permutations and reflections. For any ${\sigma\in S_n}$ let ${R(\sigma)}$ be the linear map on ${{\mathbf F}^n}$ (with ${{\mathbf F}}$ being some field) given by ${ \displaystyle R(\sigma)(x_1,\ldots, x_n)=\Bigl(x_{\sigma^{-1}(1)},\ldots, x_{\sigma^{-1}(n)}\Bigr).}$ For a transposition ${ (j\,k)}$ we see that ${R(j\,k)}$ is reflection across the hyperplane ${x_j=x_k}$. Thus, taking a field ${{\mathbf F}}$ in which ${2\neq 0}$, we see that

${ \displaystyle \epsilon(\sigma) =\det R(\sigma),}$

essentially detecting whether ${R(\sigma)}$ is a `rotation’ or a reflection.

Length of a permutation

Introductory texts that discuss permutations don’t seem to stress the notion of length of a permutation. In my book I tried to stress this useful notion, but the treatment in my book is confusing at points, so let me try here to give a very short and hopefully clearer account.

Fix an integer ${ n\geq 1}$ and let ${ S_n}$ be the set of all bijections of the set ${ [n]=\{1,2,3,\ldots, n\}}$. Since the composition of bijections is a bijection, and the inverse of a bijection is also a bijection, ${ S_n}$ is a group under composition. The elements of ${ S_n}$ are called permutations of ${ [n]}$. Sometimes it is convenient to display a permutation by listing the elements ${ 1,2, \ldots, n}$ in a row and the images ${ \sigma(1),\sigma(2),\ldots, \sigma(n)}$ below:

${ \displaystyle \left(\begin{matrix} 1 & 2 & \ldots & n \\ \sigma(1) & \sigma(2) &\ldots &\sigma(n) \end{matrix}\right) }$

For any ${ \sigma\in S_n}$ and ${ x\in [n]}$, the orbit of ${ x}$ is the set

${ \displaystyle \{x, \sigma(x),\sigma^2(x),\ldots\}.}$

For example, the orbits of

${ \displaystyle \left( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 3& 1 & 2 &5 &6 &4&7\end{matrix}\right)}$

are

${ \displaystyle \{1,2,3\}, \{4,5,6\}, \{7\}.}$

Let

${ \displaystyle {\rm Orb}(\sigma)}$

denote the set of all orbits of ${ \sigma}$. The length of ${ \sigma}$ is

${ \displaystyle l(\sigma)= n-|{\rm Orb}(\sigma)|.}$

Thus, in our example above,

${ \displaystyle l\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 3& 1 & 2 &5 &6 &4&7\end{matrix}\right)=7-3=4.}$

Notice that the length does not change if we view a permutation in ${ S_7}$ as a permutation of ${ [9]}$, keeping ${ 8}$ and ${ 9}$ fixed.

The notation

${ c=\displaystyle (a_1\,a_2\,\ldots, a_k),}$

means a permutation that takes ${ a_1}$ to ${ a_2}$, ${ a_2}$ to ${ a_3}$, and so on, with ${ a_k}$ being taken to ${ a_1}$, and all other elements are held fixed. Such a permutation is called a cycle. (Whether you view the identity permutation as a cycle or not is up to you; one could make it less ambiguous by using the term cycle only for those permutations that have exactly one orbit.) Thus,

${ (1\,3\,8)}$

is a cycle. The notation does not require we specify which set this permutation acts on (of course, the set must contain ${ 1,3, 8}$.) If ${ c}$ as above is in ${ S_n}$ then

${ \displaystyle l(c)= n-[1+\underbrace{1+\cdots +1}_{n-k \, {\rm terms}}]=k-1.}$

Notice that ${ n}$ dropped out of this calculation. The length of a cycle is just the number of elements in the orbit of this cycle minus ${ 1}$. (“The orbit” having the obvious interpretation.)

Every permutation is a product of the cycles that correspond to its orbits, the distinct orbits being disjoint.

transposition is a permutation that exchanges two elements, and holds all others fixed. For example,

${ (1\, 3)}$

is a transposition. Clearly, a permutation is a transposition if and only if its length is ${ 1}$. Moreover, every transposition is equal to its own inverse.

If we multiply a permutation ${ \sigma\in S_n}$ by a transposition ${ \tau=(a\,b) \in S_n}$ to form ${ \tau\sigma}$ then there are exactly two possibilities:

(1) if ${ a}$ and ${ b}$ are both in the same orbit of ${ \sigma}$ then that orbit is split into two orbits for ${ \tau\sigma}$;

(2) if ${ a}$ and ${ b}$ are in different orbits of ${ \sigma}$ then these orbits are combined into one orbit for ${ \tau\sigma}$.

All other orbits of ${ \sigma}$ remain orbits of ${ \tau\sigma}$.

For example,

${ \displaystyle (1\,2)\, (1\,3\,4\,5)(2\,6\,7)=(1\,3\,4\,5\,2\,6\,7)}$

and, multiplying on the left by ${ (1\,2)}$, we have

${ \displaystyle (1\,2)\, (1\,3\,4\,5\,2\,6\,7)=(1\,3\,4\,5)(2\,6\,7).}$

A consequence of this very nice fact is the effect on the length of a permutation under multiplication by a transposition:

${ \displaystyle l(\tau\sigma)=\begin{cases}l(\sigma)+1 & \hbox{if } \tau \hbox{ transposes elements in different orbits of} \sigma ; \\ l(\sigma)-1 & \hbox{if } \tau \hbox{ transposes elements in the same orbit of } \sigma \end{cases}}$

where the first case occurs when ${ \tau}$ transposes elements in different orbits of ${ \sigma}$, and the second case occurs when ${ \tau}$ transposes elements within one orbit of ${ \sigma}$.

Thus for any permutation ${ \sigma}$ we can systematically break down each of its cycles (orbits) by hitting them with transpositions: there is a sequence of transpositions ${ \tau_1,\ldots,\tau_k}$ such that the length of ${ \tau_k\ldots\tau_1\,\sigma}$ is ${ 0}$, which means that

${ \displaystyle \tau_k\ldots\tau_1\,\sigma=\iota,}$

the identity. Note that this is equivalent to

${ \displaystyle \sigma=\tau_1\ldots\tau_k,}$

because each ${\tau_j}$ is a transposition (hence equal to its inverse).

Thus, every permutation ${ \sigma}$ is a product of transpositions, and the smallest such number of transpositions is the length of ${ \sigma}$.

As consequence,

${ \displaystyle l(\sigma\pi) \leq l(\sigma) + l(\pi),}$

for all permutations ${\sigma}$ and ${\pi}$.

The orbits of ${\sigma^{-1}}$ are exactly the orbits of ${\sigma}$, and so both ${\sigma}$ and ${\sigma^{-1}}$ have the same number of orbits. Hence they have the same length:

${\displaystyle l(\sigma^{-1})=l(\sigma).}$

Next for any permutations ${\sigma}$ and ${\pi}$, the orbits of ${\pi\sigma\pi^{-1}}$ are exactly of the form ${\pi(O)}$ where ${O}$ runs over the orbits of ${\sigma}$. Hence

${\displaystyle l(\pi\sigma \pi^{-1})=l(\sigma).}$

Posted in Uncategorized | 1 Comment

Charlie Egedy

Last evening a celebration was held at the LSU mathematics department in honor of Charlie Egedy’s life. Charlie was kind enough to allow me to include his beautiful poem “A Reckoning” in my book.  I also had the opportunity to serve on his doctoral committee and recall how much I enjoyed his mathematical work and presentation. He was a man of many talents and interests, ranging from mathematics and chess to baseball and poetry. His warm personality was recalled through many stories and memories from those who were enriched by having known him.

Let me quote the first few lines from his poem:

A Reckoning

He sits in a seamless room

staring

into the depths

of a wall that is not a wall,

opaque,

unfathomable.

Though deep understanding

lies

just beyond that wall,

the vision he desires

can be seen

only from within the room.

Chapter on Clifford algebras

This is an old version of the manuscript. It was not  proof read but this version has a chapter 14 on Clifford algebras (part of which survived into the print version published in 2012).

Posted in Uncategorized | 1 Comment

Representing finite groups, semisimply

This blog is devoted to stray thoughts and comments on representations of finite groups, were finite may mean “not necessarily infinite”, to turn the tables on the more widely used convention.

Some of this blog relates to my book Representing Finite Groups: A Semisimple Introduction

It is rarely acknowledged how much of the theory of representations of finite groups, and so much of what flowed from this theory, was discovered by Frobenius, starting with his 1896 paper.  For example, Frobenius’s counting formulas for solutions of equations in finite groups contain the essence of the discrete analog of Witten’s formula for the volume of the moduli space of flat connections.