In this post, we’ll implement an algorithm for decomposing representations that Dixon published in 1970.

As a motivating example, I’ll use the permutation matrix representation of $D_4$ that we saw in an earlier post. To make the code more generally applicable, let’s call the group $G$ and the representation $\rho$:

(The Sage cells in this post are linked, so things may not work if you don’t execute them in order.)

We’ll see that this is decomposable, and find out what its irreducible components are.

Unitary representations

A short remark before we begin: The algorithm assumes that $\rho$ is a unitary representation

i.e. for all $g \in G$,

\[\rho(g)^* \rho(g) = \rho(g) \rho(g)^* = I,\]

where $A*$ is the conjugate transpose of a matrix $A$. For $G$ a finite group, all representations can be made unitary under an appropriate change of basis, so we need not be too concerned about this. In any case, permutation representations are always unitary, so we can proceed with our example.

Finding non-scalar, commuting matrices

At the end of the previous post we saw that in order to decompose a representation $(V,\rho)$, it is enough to find a non-scalar matrix $T$ that commutes with $\rho(g)$ for every $g \in G$. This first step finds a Hermitian non-scalar $H$ that commutes with $\rho(G)$ (if there is one to be found).

Let $E_{rs}$ denote the $n \times n$ matrix with a $1$ in the $(r,s)$th entry and zeros everywhere else. Here $n$ is the dimension of $V$ in the representation $(V,\rho)$. Define

\[H_{rs} = \begin{cases} E_{rr} &\text{if } r = s \\ E_{rs} + E_{sr} &\text{if } r > s \\ i(E_{rs} - E_{sr}) &\text{if } r < s, \end{cases}\]

then the set of matrices $H_{rs}$ forms a Hermitian basis for the $n \times n$ matrices over $\mathbb{C}$.

Now for each $r,s$, compute the sum

\[H = \frac{1}{|G|} \sum_{g \in G} \,\, \rho(g)^* \, H_{rs} \, \rho(g).\]

Observe that $H$ has the following properties:

• it is hermitian
• it commutes with $\rho(g)$ for all $g \in G$

If $\rho$ is irreducible, then $H$ is a scalar matrix for all $r,s$. Otherwise, it turns out that there will be some $r,s$ such that $H$ is non-scalar (this is due to the fact that the $H_{rs}$ matrices form a basis of the $n \times n$ matrices$).

Let’s test this algorithm on our permutation representation of $D_4$:

We get a non-scalar $H$! So the permutation representation of $D_4$ is reducible!

Using $H$ to decompose $\rho$

Our next step is to use the eigenspaces of $H$ to decompose $\rho$. At the end of the previous post, we saw that $\rho(g)$ preserves the eigenspaces of $H$, so we need only find the eigenspaces of $H$ to decompose $\rho$.

Since $H$ is hermitian, it is diagonalizable, so its eigenvectors form a basis of $V$. In fact, the eigenbasis can be chosen to be orthonormal.

We can find this basis by computing the Jordan decomposition of $H$, and then orthonormalizing it:

It’s important that we orthonormalize $P$ so that $P$ becomes unitary. This will ensure that the subrepresentations remain unitary.

Observe that $P^{-1} \rho(g) P$ has the same block-diagonal form for each $g \in G$:

We have thus decomposed $\rho$ into two 1-dimensional representations and one 2-dimensional one!

Decomposing into irreducibles

Finally, to get a decomposition into irreducibles, we can apply the algorithm recursively on each of the subrepresentations to see if they further decompose.

Here’s a stand-alone script that decomposes a representation into its irreducible components:

Getting all irreducible representations

Now we know how to test for irreducibility and decompose reducible representations. But we still don’t know how many irreducible representations a group has.

It turns out that finite groups have finitely many irreducible representations! In the next post, we’ll construct a representation for any finite group $G$ that contains all the irreducible representations of $G$.