$$ \newcommand\ketbra[1]{\lvert #1 \rangle \langle #1 \lvert} \renewcommand\braket[2]{\langle #1 \lvert #2 \rangle} \newcommand\ket[1]{\lvert #1 \rangle} \newcommand\bra[1]{\langle #1 \lvert} \newcommand\Tr{\text{Tr}} $$

Visualizing commutative structure in groups

Introducing the commutativity plot to explain basic concepts related to commutativity

Introduction

I built a simple visualization tool, the commutativity plot, that I used to better understand commutativity in finite groups as I was learning about group theory this semester. By the end of this post, I aim to summarize a couple of concepts leading up to two theorems illustrated with this visualization. Namely, we’ll touch on group action, orbits and stabilizers of an element, the permutation representation of groups, conjugation, conjugacy classes, centralizers, and we’ll derive the formula for the number of conjugacy classes. We will also look at why the probability that two randomly picked elements commute in a finite group is a maximum of 5/8 in non-abelian groups, which I find fascinating.

Disclaimer: the function implementation and Mathematica syntax used is very naive, and blows up with larger groups. I am open to PRs, contributions, suggestions for improvements!

Groups acting on sets

One of the most important things you can do with a group is to have it act on a set. The group action has to be valid operations on the set. For example, if the set is the group itself, the action can be left/right multiplication or conjugation (defined later) as well. When we’re talking about an action of an element gg of the group GG on a set element aa in abstract, i.e. without specifying exactly what we mean, we denote it by gag \centerdot a.

If we apply a group action defined by all elements of GG on an element aa, we get a set: Oa={gagG} O_a = \{ g \centerdot a \lvert g \in G \} , the orbit of aa. The elements in GG that keep aa the same are called the stabilizer of aa in GG, denoted GS(a)={gGga=a}G_S(a)=\{g \in G \lvert g \centerdot a = a\}. The stabilizer of any element is a subgroup of GG. In fact the orbit of aa is an equivalence class for aa, and the group action divides GG into disjoint equivalence classes. It is also provable that the order of (the number of elements in) the orbit equals to the index of the stabilizer G:Ga\lvert G : G_a\lvert.

Permutation representation

By Cayley’s theorem, every group of order nn is isomorphic to some subgroup of SnS_n, the symmetric group of order nn. We are going to assume that for the group in question you can generate the permutation representation, specifically the permutation cycle notation of the elements. For example, for the quaternion group Q8Q_8, we can list the elements of the group itself using the Quaternions package:

<<Quaternions`
(* Code to generate a group based on its generators and composition 
rule, this is brute force, can easily blow up if your generators are 
not closed under multiplication, or are too big *)

GenerateGroupElements[generators_, compose_] := 
  FixedPoint[Union[#, compose @@@ Tuples[#, 2]] &, generators];

(* Q8 group = <i,j,k>, composition: quaternion product *)

quaternionGroupElements = GenerateGroupElements[
   
   {Quaternion[0, 1, 0, 0],  (* i *)
   Quaternion[0, 0, 1, 0],   (* j *)
    Quaternion[0, 0, 0, 1]}, (* k *)
   (#1 ** #2) & (* quaternion product *)
   ];


(* A nice example of Cayley's theorem, where we are acting on G by itself with 
left multiplication *)

quaternionGroupPermutations = (el = #;
     FindPermutation[
      quaternionGroupElements, (el ** #) & /@ 
       quaternionGroupElements]
     ) &  /@ quaternionGroupElements;

(* storing the result in a PermutationGroup object *)
QuaternionGroup = PermutationGroup[quaternionGroupPermutations ]

The above results in:

PermutationGroup[{Cycles[{}], 
  Cycles[{{1, 2}, {3, 4}, {5, 6}, {7, 8}}], 
  Cycles[{{1, 4, 2, 3}, {5, 8, 6, 7}}], 
  Cycles[{{1, 3, 2, 4}, {5, 7, 6, 8}}], 
  Cycles[{{1, 6, 2, 5}, {3, 7, 4, 8}}], 
  Cycles[{{1, 5, 2, 6}, {3, 8, 4, 7}}], 
  Cycles[{{1, 8, 2, 7}, {3, 6, 4, 5}}], 
  Cycles[{{1, 7, 2, 8}, {3, 5, 4, 6}}]}]

The permutation representation for groups is akin to the matrix representation of operators on a vector space in a given basis. We can see in this chosen labeling that 11 keeps the elements in place, 1-1 is a quadruple of transpositions (swaps), and ii permutes 1234567812345678 into 4312875643128756.

One thing we get with this representation is stable, deterministic ordering between permutations, which will allow for seeing subgroup structure clearly in larger groups.

Conjugacy classes

Fun things happen when a group GG acts on itself! Two elements, g,hGg, h \in G commute when hg=ghhg = gh. This is the same as saying g=h1ghg=h^{-1}gh, i.e. that gg is fixed by conjugation by hh.

If we have GG act on itself by conjugation, the orbit of an element gg, a.k.a the disjoint equivalence class, is called the conjugacy class of gg. The stabilizer subgroup under conjugation for gg is the subgroup that fixes gg by conjugation. What does that mean? It means that it’s all the elements gg commutes with. There is a special name for that: the centralizer of gg in GG, denoted CG(g)C_G(g). The elements that commute with everything are called the center of GG, Z(G)Z(G) - it is easy to see that the center is the intersection of all the centralizers and hence it is also a subgroup.

It is easy to prove (p 125 in (Dummit & Foote, 2003)) that conjugation preserves the length of the cycles of a permutation, i.e. all the conjugates within a conjugacy class have the same cycle lengths. In Mathematica, you could write a function called CycleLengths that does this calculation.


In[1]:= CycleLengths[c_]:=Sort[Length/@c[[1]]];
CycleLengths[Cycles[{{1,2},{3,4},{5,6},{7,8}}]]
CycleLengths[Cycles[{{1,2},{3,4,5}}]]
Out[2]= {2,2,2,2}
Out[3]= {2,3}

However, even though elements in the same conjugacy class have the same cycle lengths, it doesn’t necessarily work the other direction. To see this there are two examples in mind: abelian groups and the Q8Q_8 quaternion group.

As everything commutes with everything in abelian groups, the conjugacy class for each element is going to contain only that element. But in a cyclic group of prime order for example all non-trivial elements are of order pp, their permutation representation looks like (1234p)(1234…p). How is that possible? Well, there are no other elements to conjugate them into each other…or to put it another way all elements fix each other by conjugation.

In the quaternion group Q8Q_8, i,j,ki, j, k have the same cycle lengths but you can only get as far as an element and its inverse in the conjugacy classes. There are no elements in the group that can do the conjugation.

To summarize - conjugacy classes split up GG into disjoint sets, and while cycle lengths are the same within a conjugacy class, the property of being in a conjugacy class is inherently connected to the group you are in.

The commutativity plot: commuting visibly

To visualize all the ideas above, I coded up a function called CommutativityPlot in this gist. If we order the elements of the group by their conjugacy class and then their natural sorting order (defined by Mathematica), and we plot whether they commute or not, we’ll get a graph plot like this for our quaternion group, Q8Q_8:

Let’s dissect this!

Each row and column contains the elements that are either commute (blue) or don’t commute (red) with the given element corresponding to that row. The blue squares in a row (or column) are the centralizer CG(g)C_G(g) for each gg. If the full row (column) is blue, that means that the gg element is in the center, Z(G)Z(G).

We know that every element commutes with:

In the case of Q8Q_8, some of the elements are not self-inverse, e.g. i1=ii^{-1} = -i, and we know that the elements commute with their inverse. In the current labeling, the inverses are next to each other, that’s why we see the 2x2 blue squares on the diagonal.

Also, notice the yellow grid. As we organized the elements by conjugacy class, a conjugacy class will be a contiguous interval of rows and columns. The intersection of these regions is where the inter-class commutation relations are visible. We can see intra-class commutativity relations outside of the block diagonal squares.

As I mentioned in the previous part, cyclic groups are abelian, every element commutes with each other, thus in the commutativity plot we will have

As an example see below the (pretty boring) commutativity plot for the C4C_4 group.

Number of conjugacy classes

Within a conjugacy class (i.e. between two yellow lines), the number of blue squares is going to be the number of elements in the group! Why?

To see this, let’s line up our concepts next to each other in the different “languages” we talk about them:

Conjugation Group acting on itself by conjugation commutativity plot
element aGa \in G the target aGa \in G of the group action a row / a column
centralizer of aa, CG(a)C_G(a), things that commute with aa stabilizer of aa, SG(a)S_G(a) the elements corresponding to the blue squares in a row / column
conjugacy class of aa orbit of aa, OaO_a the rows/cols within the same yellow grid interval as aa’s row/col
number of conjugates / size of conjugacy class size of orbit the number of rows/cols within the same yellow grid interval as aa’s row/col
number of conjugacy classes number of orbits number of yellow grid intervals

Now, the centralizer for each element is a subgroup, in fact, the stabilizer for the element when we consider the group acting on itself by conjugation. As we noted, the size of the orbit is exactly the index of the stabilizer, which means exactly that the blue squares will add up to G\lvert G \lvert within the yellow lines. In the case of Q8Q_8 above, if we add up all the blue squares and divide it by GG, then we get the number of conjugacy classes, which is 5!

Hopefully, now it is more clear why the equation holds for the number of conjugacy classes:

k=gGCG(g)G k = \frac{\sum_{g \in G} |C_G(g)|}{|G|}

Another example is the Pauli group (or Heisenberg-Weyl group), which is of fundamental importance in quantum mechanics and quantum computing. It is generated by the Pauli matrices X,Y,ZX, Y, Z:

X=(0110)Y=(0ii0)Z=(1001) X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}

These 3 matrices generate 16 elements, so our permutation representation will be the result of permuting 16 symbols, they get pretty lengthy.

We can see that the center of the Pauli group is {±I,±iI}\{\pm I, \pm i I\}, each element there has its own conjugacy class, and then, interestingly each element has only one conjugate, which is -1 times the element itself.

The probability that two elements commute

The commutativity plot almost intuitively leads to this question: how dense can the blue squares be? In probabilistic terms, the proportion of the blue vs the full area is equivalent to the probability that two random elements commute from GG. Of course, we are interested in non-abelian groups, as abelian groups have a boring full-blue plot. In the case of S6S_6, the plot becomes very large (6! x 6!), but we can see that it is very sparse (also has some cool structure in there):

The Pauli group above and the quaternion group have much more blue in them. Let’s quantify this probability exactly.

CommutationProbability[group_] := 
 Count[Tuples[GroupElements[group], 2], 
   x_ /; 
    PermutationProduct[x[[1]], x[[2]]] == 
     PermutationProduct[x[[2]], x[[1]]]]/GroupOrder[group]^2

With the function above (again, very slow, brute force implementation, careful), we can see that our groups have the following probabilities of two of their elements to commute:

Can we go higher? It turns out that two random elements in a non-abelian group can’t have more than a 5/8 chance to commute!

The proof is relatively simple: given that the centralizer CG(g)C_G(g) for any element gGg \in G in a non-abelian group is a proper subgroup, it can only be of order G/2\lvert G \lvert/2 at most (due to Lagrange the subgroup’s order has to divide the group’s order). But, the same is true for the center of the group itself, Z(G)Z(G) is a subgroup of all the centralizers, and as such, it must be up to half the size of the centralizers, and as such, it must be that Z(G)G/4\lvert Z(G) \lvert \leq \lvert G \lvert /4. We can see in the Pauli group that the center has 4 elements, out of the 16, we are hitting this limit.

Now, let’s use these bounds. We’ll simply add all the blue squares - that’s going to be all the orders of the centralizers of all the elements, and divide by all the squares, which is simply G2\lvert G \lvert^2.

p(g,hG commute)=gGCG(g)G2 p(g,h \in G \text{ commute}) = \frac{\sum_{g \in G} |C_G(g)|}{|G|^2}

For elements in the center, the centralizer is the group itself (they commute with every element), so we can separate those out from the sum:

p(g,hG commute)=gZ(G)GG2+gZ(G)CG(g)G2 p(g,h \in G \text{ commute}) = \frac{\sum_{g \in Z(G)} |G|}{|G|^2} + \frac{\sum_{g \notin Z(G)} |C_G(g)|}{|G|^2}

Let’s divide in with the order of GG:

p(g,hG commute)=gZ(G)G/GG+gZ(G)CG(g)/GG p(g,h \in G \text{ commute}) = \frac{\sum_{g \in Z(G)} |G|/|G|}{|G|} + \frac{\sum_{g \notin Z(G)} |C_G(g)|/|G|}{|G|}

And let’s use our bounds: Z(G)/G1/4\lvert Z(G) \lvert / \lvert G \lvert \leq 1/4 and CG(g)/G1/2\lvert C_G(g) \lvert / \lvert G \lvert \leq 1/2 for all gGg \in G:

p(g,hG commute)gZ(G)1G+gZ(G)1/2G==Z(G)G+GZ(G)G1/21/4+GZ(G)G1/2 p(g,h \in G \text{ commute}) \leq \frac{\sum_{g \in Z(G)} 1 }{|G|} + \frac{\sum_{g \notin Z(G)} 1/2}{|G|} = \\ =\frac{|Z(G)|}{|G|} + \frac{|G|-|Z(G)|}{|G|}1/2 \leq 1/4 + \frac{|G|-|Z(G)|}{|G|}1/2

Here we can use the bounds again!

p(g,hG commute)1/4+GZ(G)G1/21/4+(11/4)1/2=5/8 p(g,h \in G \text{ commute}) \leq 1/4 + \frac{|G|-|Z(G)|}{|G|}1/2 \leq 1/4 + (1-1/4) * 1/2 = 5/8

When I first saw this, my mind was blown - group theory seems like this area of infinite possibilities, but it seems like it contains a lot more structure than we’d think at first.

Conclusion

We demonstrated a simple tool to visualize commutation relationships within finite groups. It leverages the permutation representation of groups, which allows for a natural ordering that simplifies grouping conjugation classes together. We demonstrated proofs aided by this visual language for two theorems. I hope you enjoyed it, learned something from it!

Further things to explore and improve

This is probably just the tip of the iceberg. If I had an infinite amount of time I would explore a couple of ideas:

If you find issues with the post, please open an issue or PR to fix it!

Comments

Comments are provided by giscus and Github Discussions. You will have to login with your Github account to comment.

  1. Dummit, D. S., & Foote, R. M. (2003). Abstract Algebra. Wiley. https://books.google.com/books?id=KIGbCgAAQBAJ