Permutations, transpositions, and gender

Mathematical diagram with the numbers 1, 2, 3, 4 arranged vertically on the left and right sides, with blue ovals encircling each side. Horizontal red arrows go from 1 on the left to 1 on the right, and from 2 to 2, 3 to 4, and 4 to 3.

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


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)


\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.


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.

%d bloggers like this: