Permutations, transpositions, and gender

Este artículo también está disponible en español.

Introduction

In the presentation of this blog, it was mentioned the mathematical meaning of transposition as rearranging the rows or columns of a matrix, but this is only a particularization of a more general meaning in the context of permutations when the indices permuted represent the rows or columns of said matrix.

In this post, I shall introduce first permutations, then transpositions in the context of permutations, and finally an application of them to gender-identity. I will start as in a first-term Mathematics lesson at college, but will also mark some examples as advanced for the benefit of this kind of readers.

Introduction to permutations

Let us consider a non-empty set $\Omega$ , that is, an unsorted collection of elements counted without repetition. For many considerations, it doesn’t matter if $\Omega$ is finite or infinite, but most of the interesting applications restrict to $\Omega$ finite, especially $\Omega=\{1,\dots,n\}$ taken as set of indices pointing to other objects.

What is a permutation

A permutation over $\Omega$ is defined as a bijective mapping from $\Omega$ into $\Omega$ , in other words, a function $\sigma$ that assigns to every element $\omega\in\Omega$ another element $\sigma(\omega)\in\Omega$ in a reversible way. What do we mean by “bijective” or “a reversible way”? Well, $\sigma$ is invertible if there exists another function $\sigma^{-1}$ of the same kind such that $\sigma(\sigma^{-1}(\omega))=\sigma^{-1}(\sigma(\omega))=\omega$ for every element $\omega\in\Omega$ .

For the purist, I’m taking advantage that domain and the range of $\sigma$ is the same $\Omega$ , but this is a core feature of permutations: they just rearrange the elements of $\Omega$ .

So, essentially, a permutation is a rearrangement of the elements of $\Omega$ , where every element $\omega\in\Omega$ points to another element $\sigma(\omega)\in\Omega$ in such a way that we can retrieve $\omega$ given $\sigma(\omega)$ .

How we write a permutation

For a finite $\Omega$ , we can represent a permutation as a two-row table enclosed in parentheses (in matrix notation but not subject to the matrix operations, for the advanced reader) listing $\Omega$ above and the respective images below. For instance, the permutation over 4 elements

$\alpha=\left( \begin{array}[pos]{cccc} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{array}\right)$

maps each number in the upper row to the corresponding number in the lower row.

Such a permutation $\alpha$ belongs to a particular kind, since it maps cyclically $1\mapsto 2\mapsto 4\mapsto 1$ and leaves $3$ fixed. When a permutation maps cyclically an ordered subset of $\Omega$ and leaves the rest of $\Omega$ fixed, we call this a cycle and, if $\Omega$ is assumed, we can note them in a single row

$\alpha=\left( \begin{array}[pos]{ccc} 1 & 2 & 4 \end{array}\right)$

where each element is mapped to the next one, the last one to the first one, and the absent left fixed.

Operations with permutations

For any $\Omega$ , we have always a special permutation, called the identity-permutation, that assigns every element to itself, in other words, it keeps all $\Omega$ fixed. In formulae, we write $\mathrm{id}(\omega)=\omega$ for every $\omega\in\Omega$ .

Before proceeding, I recall the composition of functions, usually noted by $\circ$ . Given two functions $f$ and $g$ , we define the composite function $f\circ g$ such that the formula $(f\circ g)(x)=f(g(x))$ holds when it makes sense. It is remarkable that the composition, when it makes sense, is associative but not necessarily commutative. In formulae, the associative property for an operation $\ast$ is $(f\ast g)\ast h=f\ast(g\ast h)$ , while the commutative property is $f\ast g=g\ast f$ , where the latter may fail for $\ast=\circ$ .

By being associative, we can get rid of the parentheses in long products of composition like

$f_1\circ f_2\circ f_3\circ f_4,$

since any valid arrangement of them yields the same result. However, by not necessarily being commutative, the order of the factors matters in principle. In other words, $f\circ g$ is not always equal to $g\circ f$ .

In the case of permutations over the same $\Omega$ , it always makes sense to compose them, with the operation $\circ$ being associative but not necessarily commutative. As we have the identity-permutation as the neutral element of this operation, as well as inverses of every permutation, the reader acquainted with Abstract Algebra may recognize the structure of a group in the family of all the permutations over $\Omega$ with the usual composition.

Examples on commutativity

If we take the permutation $\alpha$ above and the cycle

$\beta=\left( \begin{array}[pos]{cc} 3 & 4 \end{array}\right),$

we have

$\alpha\circ\beta =\left(\begin{array}[pos]{cccc} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{array}\right) =\left(\begin{array}[pos]{cccc} 1 & 2 & 4 & 3 \end{array}\right)$

and

$\beta\circ\alpha =\left(\begin{array}[pos]{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{array}\right) =\left(\begin{array}[pos]{cccc} 1 & 2 & 3 & 4 \end{array}\right),$

which are clearly different permutations.

Nevertheless, when we have disjoint subsets of the elements shifted by two cycles, these particular cycles do commute, where by disjoint we mean “having no element in common.” This feature is key for a relevant theorem: “any permutation over finite $\Omega$ can be factored into disjoint cycles, and this family of factors (empty in the case of the identity-permutation) is unique taken unsorted.” As disjoint cycles commute, we can retrieve the original permutation from these factors by multiplying them in any order.

This decomposition is even constructive. We pick any element $\omega_1\in\Omega$ and compute the sequence of the iterated images by $\sigma$ until $\omega_1$ appears again. In formulae, when we get $\sigma^\ell(\omega_1)=\omega_1$ , we write the cycle

$c_1=\left(\begin{array}[pos]{cccc} \omega_1 & \sigma(\omega_1) & \dots & \sigma^{\ell-1}(\omega_1) \end{array}\right)$

unless $\sigma(\omega_1)=\omega_1$ , when $\omega_1$ is fixed and yields no cycle. Anyway, we discard from $\Omega$ both $\omega_1$ and all its iterated images and proceed with the remaining elements.

Introduction to transpositions

In the context of permutations, a transposition is a very particular kind of cycle, precisely one of length 2, which just swaps two elements of $\Omega$ , keeping the rest fixed.

Decomposition into transpositions

In the same way that we could factor a permutation into cycles, a permutation can be also factored into transpositions, but not in a unique way. For instance,

$\alpha =\left(\begin{array}[pos]{cc} 1 & 4 \end{array}\right) \left(\begin{array}[pos]{cc} 1 & 2 \end{array}\right) =\left(\begin{array}[pos]{cc} 2 & 4 \end{array}\right) \left(\begin{array}[pos]{cc} 1 & 4 \end{array}\right)$

and even

$\alpha =\left(\begin{array}[pos]{cc} 1 & 3 \end{array}\right) \left(\begin{array}[pos]{cc} 3 & 4 \end{array}\right) \left(\begin{array}[pos]{cc} 1 & 3 \end{array}\right) \left(\begin{array}[pos]{cc} 1 & 2 \end{array}\right),$

but what remains is the parity of the numbers of factors, in other words, if we have an even or odd number of transpositions in the list of factors, counted with their repetition and taking 0 as even.

According to its parity, each permutation is assigned a sign $\pm1$ , which is $+1$ for even permutations and $-1$ for odd ones. A cycle of length $\ell$ has the sign $(-1)^{\ell-1}$ , since the factorization

$\left(\begin{array}[pos]{cccc} \omega_1 & \omega_2 & \dots & \omega_\ell \end{array}\right) =\left(\begin{array}[pos]{cc} \omega_1 & \omega_\ell \end{array}\right) \cdots\left(\begin{array}[pos]{cc} \omega_1 & \omega_2 \end{array}\right)$

always holds and yields $\ell-1$ transpositions. The sign of a composition is the product of the signs of the factors, which makes easy to compute the sign of a permutation factored into cycles.

Relevant applications

As a first application, when a permutation represents the rearrangement of the rows or columns of a square matrix, the sign of said permutation is precisely the sign that multiplies the transformed determinant. Recall that a matrix is a table of numbers (or other objects assimilable) surrounded by parentheses, which can be added and multiplied depending on certain matches in the number of rows and columns. If a matrix is square, having the same number of rows and columns, we can define its determinant as certain operation on the entries of the matrix involving permutations. The determinant of a matrix is noted by substituting the parentheses of the matrix by vertical bars. Both matrices and determinants are very useful in Linear Algebra and Geometry, but depending on the high-school curriculum, they may be introduced or not.

For instance, if we have a $4\times4$ matrix given by columns and apply the permutation $\alpha$ above, as it is an even permutation, the determinant is the same:

$\left|\begin{array}[pos]{cccc} C_1 & C_2 & C_3 & C_4 \end{array}\right| =\left|\begin{array}[pos]{cccc} C_2 & C_4 & C_3 & C_1 \end{array}\right|.$

Contrary, if the permutation applied is the transposition $\beta$ above,

$\left|\begin{array}[pos]{cccc} C_1 & C_2 & C_3 & C_4 \end{array}\right| =-\left|\begin{array}[pos]{cccc} C_1 & C_2 & C_4 & C_3 \end{array}\right|$

because $\beta$ is an odd permutation.

As a more advanced application, for those acquainted with Group Theory, the even permutations form a subgroup of the group of all the permutations over a finite set. The former is called the alternating subgroup and the latter is the symmetric group. Symmetric and alternating groups are very relevant in general Group Theory.

An application to gender

Let us consider $\Omega$ the space of gender values where permutations act on. Then someone’s gender assigned at birth (AGAB) and gender-identity (GI) would be nullary operations on this space, in other words, ways of choosing from $\Omega$ one of these gender values $\mathrm{AGAB}()$ as their AGAB and another $\mathrm{GI}()$ as their gender-identity, equal (cis) or different (trans). For a reader acquainted with computer programming, a nullary operation is just a function that has no input but returns an output.

The group of permutations over $\Omega$ acts on the left by composition with nullary operations like AGAB or GI. Given a permutation $\sigma$ and a nullary operation $N$ , the composition $M=\sigma\circ N$ is just another nullary operation picking $M()=\sigma(N())$ .

With this background, we can always consider $\mathrm{GI}=\sigma\circ\mathrm{AGAB}$ for a suitable permutation $\sigma$ over $\Omega$ . In the Trans case, we just take $\sigma$ the transposition that swaps $\mathrm{AGAB}()$ and $\mathrm{GI}()$ , and it happens that this is the only transposition doing the work. Moreover, it satisfies that $\mathrm{AGAB}=\sigma\circ\mathrm{GI}$ because any transposition is self-inverse. In the Cis case, we can just take $\sigma$ the identity-permutation and the last property still holds.

Conclusion

I must recall the polysemy (multiple meanings) of the word “identity,” which appear both in “identity-permutation” and in “gender-identity,” so one should be careful when speaking of “the identity” in this context. Moreover, the only nullary operation $N$ that makes $\mathrm{GI}=\sigma\circ N$ for $\sigma=\mathrm{id}$ is $N=\mathrm{GI}$ . The last claim, despite being almost a tautology, is also a strong political claim: “the only way to retrieve the gender-identity is though by the value of GI,” in other words, “the only way to know the gender-identity is asking for it,” rather than inferring or guessing it.