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 , that is, an unsorted collection of elements counted without repetition. For many considerations, it doesn’t matter if is finite or infinite, but most of the interesting applications restrict to finite, especially taken as set of indices pointing to other objects.
What is a permutation
A permutation over is defined as a bijective mapping from into , in other words, a function that assigns to every element $\omega\in\Omega$ another element in a reversible way. What do we mean by “bijective” or “a reversible way”? Well, is invertible if there exists another function of the same kind such that for every element .
For the purist, I’m taking advantage that domain and the range of is the same , but this is a core feature of permutations: they just rearrange the elements of .
So, essentially, a permutation is a rearrangement of the elements of , where every element points to another element in such a way that we can retrieve given .
How we write a permutation
For a finite , 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 above and the respective images below. For instance, the permutation over 4 elements
maps each number in the upper row to the corresponding number in the lower row.
Such a permutation belongs to a particular kind, since it maps cyclically and leaves fixed. When a permutation maps cyclically an ordered subset of and leaves the rest of fixed, we call this a cycle and, if is assumed, we can note them in a single row
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 , we have always a special permutation, called the identity-permutation, that assigns every element to itself, in other words, it keeps all fixed. In formulae, we write for every .
Before proceeding, I recall the composition of functions, usually noted by . Given two functions and , we define the composite function such that the formula 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 is , while the commutative property is , where the latter may fail for .
By being associative, we can get rid of the parentheses in long products of composition like
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, is not always equal to .
In the case of permutations over the same , it always makes sense to compose them, with the operation 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 with the usual composition.
Examples on commutativity
If we take the permutation above and the cycle
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 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 and compute the sequence of the iterated images by until appears again. In formulae, when we get , we write the cycle
unless , when is fixed and yields no cycle. Anyway, we discard from both 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 , 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,
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 , which is for even permutations and for odd ones. A cycle of length has the sign , since the factorization
always holds and yields 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.
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 matrix given by columns and apply the permutation above, as it is an even permutation, the determinant is the same:
Contrary, if the permutation applied is the transposition above,
because 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 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 one of these gender values as their AGAB and another 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 acts on the left by composition with nullary operations like AGAB or GI. Given a permutation and a nullary operation , the composition is just another nullary operation picking .
With this background, we can always consider for a suitable permutation over . In the Trans case, we just take the transposition that swaps and , and it happens that this is the only transposition doing the work. Moreover, it satisfies that because any transposition is self-inverse. In the Cis case, we can just take 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 that makes for is . 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.