This will be an "ML-oriented" introduction to representation theory of finite groups. It is an introductory sketch that orients towards both a language and a result (the "real semisimplicity" result) that is useful for thinking about the subject in an interpretability context.

This is a somewhat low-effort math post (subbing in for a planned post I'm running late on). It isn't a prerequisite for anything, but will be useful background for a future discussion of how NN's learn associative group multiplication (a joint project with Louis Jaburi). I'm hoping for this to be readable by people with a very small amount of background in abstract algebra: it is meant to fill in some very basic knowledge gaps. I'd be very interested in comments about what is confusing or difficult about this post, to help focus on the right exposition directions when writing about this in the future.

I'm not going to assume much abstract algebra, other than the notions of a group and an algebra (always assumed to be a unital, associative algebra).

Algebras of note

Recall that all the set ${\text{Mat}}_{n\times n}$ of $n\times n$ (real-valued) matrices forms an algebra (it's a vector space with an associative product that distributes across addition). For any field F, there is a notion of a matrix algebra over F and ${\text{Mat}}_{n\times n}$ is naturally an algebra over $R$. The set  ${\text{Mat}}_{n\times n}\left(C\right)$ of complex-valued matrices forms an algebra over $C$, but it can also be viewed as an algebra over $R$, in the same way as $C$ can be viewed as a two-dimensional vector space.

We will be interested in understanding the "algebra" associated to a finite group G. It turns out that working with algebras over $C$ is easier than working with algebras over $R$ from a theoretical viewpoint (this is of course because $C$ is algebraically closed, i.e., any polynomial equation has a solution. We'll start out looking at such representations. However unfortunately, neural nets don't care about theoretical ease: instead they care about compression and efficiency, and this will necessitate also understanding a bit of representation theory over $R$.

For starters, we work over $C$. We'll need one more useful algebra that will be one of the main characters in our discussion: namely, the group algebra of G, written $$C\left[G\right]$$. This is the algebra whose elements are formal complex linear combinations of elements of $G$, and where product is induced from the product on $G$ distributively. We analogously have the real-valued group algebra $R\left[G\right]$. When we don't want to commit to either real or complex coefficients and want to treat them simultaneously, we'll write $F\left[G\right]$ for F one of our fields $R$ or $C$ (a bit of the analysis here carries over to more general fields, though usually one should require the characteristic of the field to be relatively prime to the order $|G|$ of the group for the theory to have comparable niceness).

So for example if $G=C_n$ is the cyclic group on n elements ($C_n$ is better notation for the group that is sometimes written $Z_n$ or $Z/n$), then an element of $C\left[G\right]$ is a sum $${\lambda }_{0}0+{\lambda }_{1}1+{\lambda }_{2}2+\dots {\lambda }_{n-1}n-1.$$ Here the "bolded" numbers are group elements. Note of course that since we're viewing it as a group, multiplication in $C_n$ corresponds to addition of numbers: i.e., $a\cdot b=a+b\mathrm{mod}n.$ (This is another reason why $C_n$ is better notation -- since $Z/n$ could also mean the ring, multiplicative and additive notions can be more confusing.) To see how group multiplication in this algebra works, let's work out an example with $G=C_3$: $$(4\cdot 1+5\cdot 2)\cdot (-3\cdot 0+2)=$$ $$-121\cdot 0+41\cdot 2-15\cdot 2\cdot 0+10\cdot 2\cdot 2=$$ $$4\cdot 0+(-12+10)\cdot 1-15\cdot 2.$$ (Here remember that we're writing the group multiplicatively, so for example $2\cdot 2=1$ since $2+2\equiv 1\mathrm{mod}3$.)

Representations

Now for the purposes of this note we define an n-dimensional representation of $G$ to be a map of algebras from the group algebra to a matrix algebra: $\rho :F\left[G\right]\to {\text{Mat}}_{n\times n}\left(F\right).$ Here F can either be the field $R$ ("real-valued representations") or the field $C$ ("complex-valued representations").

Of course by linearity, it's enough to specify $\rho \left(g\right)$ for elements $g\in F\left[G\right]$, which are the standard basis for the group algebra: i.e., $\rho$ can be recovered from its restriction $\rho {\mid }_G:G\to {\text{Mat}}_{n\times n}$. Conversely, any map ${\rho }_0:G\to {\text{Mat}}_{n\times n}$ leads to a map of algebras if it's

• Unital, i.e. ${\rho }_0\left(1\right)=1$ and
• A multiplicative homomorphism, i.e., $\rho \left(gh\right)=\rho \left(g\right)\rho \left(h\right)$ (product of matrices on the RHS). 

Note that setting $h=g^{-1}$ and using the homomrphism property tells us that $\rho \left(g\right)$ must always be invertible, i.e., an element of the group of invertible matrices $G{L}_n\left(F\right)\subset {\text{Mat}}_{n\times n}\left(F\right)$; this shows that our notion of representation is equivalent to the usual notion of group homomorphism ${\rho }_0:G\to G{L}_n\left(F\right)$. We say that two representations ${\rho }_1,{\rho }_2$ are equivalent if 

• they have the same dimension (i.e., both n-dimensional for the same n) and
• they are conjugate: so there exists some other invertible matrix $\gamma \in G{L}_n\left(F\right)$ such that, for all $g\in G$, we have the identity $${\rho }_2\left(g\right)=\gamma {\rho }_1\left(g\right){\gamma }^{-1}$$ (if you haven't seen expressions like this, convince yourself that the formula on the right defines a new representation of $G$ for any fixed invertible $\gamma$.) In this case we think of ${\rho }_1$ and ${\rho }_2$ to act "via the same symmetries", just expressed in different bases (the standard basis in the case of ${\rho }_1$ and the basis given by $\gamma$ in the case of ${\rho }_2$). 

If you've ever heard of group representations, you've heard of the notion of irreducibility. A representation $\rho$ is irreducible if it cannot be decomposed into smaller components: i.e., if it isn't conjugate to a block-diagonal representation of the form 

$$g\mapsto \left(\begin{array}{cc}{\rho }_1\left(g\right)& 0\\ 0& {\rho }_2\left(g\right)\end{array}\right),$$ for ${\rho }_1,{\rho }_2$ nonzero representations.

The "reducible" representation above (check this is a representation if you don't believe me!) is denoted ${\rho }_1\oplus {\rho }_2$. 

Now the big secret point of representation theory is that the set of irreducible representations (up to isomorphism) "contain all the algebraic information" about G. This is encompassed by a series of results; an appealing consequence of these results (and a way of condensing much of the information contained in them) is the semisimplicity theorem below.

Let $${\rho }_1:C\left[G\right]\to {\text{Mat}}_{n_1\times n_1}\left(C\right),\dots {\rho }_k:G\to {\text{Mat}}_{n_k\times n_k}\left(G\right)$$ be a collection of representations that contains each irreducible representation exactly once up to conjugacy. (Usually, since conjugacy, i.e., "isomorphism", simply corresponds to choosing a different basis, people will use "sum of all irreducible representations" to mean this object). Here $n_1,\dots ,n_k$ are the dimensions of the irreducible representations. The classification of (complex) representations of G and the eigenvalues of the matrices ${\rho }_i\left(g\right)$ is called character theory (something that gets covered in a first course on representation theory, but that we won't get into here). Character theory in particular implies that the number (k) of distinct irreducible complex representations is equal to the number of conjugacy classes of G, i.e., the number of elements on the set obtained from G by identifying $g$ and $\gamma g{\gamma }^{-1}$ for any G. If G is commutative, then each conjugacy class just has a single element (each element g above only gets identified with itself), so in the special case of commutative groups (also known as "abelian" groups), the number of conjugacy classes is equal to the number of elements, i.e., $k=|G|$.

Theorem (semisimplicity of the group algebra): 

$${\rho }_1\oplus {\rho }_2\oplus \dots \oplus {\rho }_k$$ be the direct sum of all irreducible representations of G. Then the map 

$$C\left[G\right]\to {\text{Mat}}_{n_1+n_2+\cdots +n_k}\left(C\right)$$

is injective, and identifies $C\left[G\right]$ with the set of all block diagonal matrices 

$$\left(\begin{array}{cccc}{M}_1& 0& \cdots & 0\\ 0& M_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & M_k\end{array}\right).$$

(Here the $M_i$ are $n_i\times n_i$ complex-valued matrices). In other words if we only care about the algebra $C\left[G\right]$, then all of its structure is fully determined by the (unordered) collection of irreducible representation dimensions $n_1,\dots ,n_k$. Since there are a lot of groups, this implies that there are some pairs of distinct groups G, H that have isomorphic matrix algebras! I.e., while the groups cannot be identified with each other, every element of G can be identified with a linear combination of elements of H in a way that respects multiplication and admits an inverse (once again linear combination-valued): indeed, if the representation dimensions of G and H coincide, then as algebras, we can identify both group algebras with the same algebra of block-diagonal matrices. A simple example of a pair of distinct groups with isomorphic group algebras are the groups $C_9$ and $C_3\times C_3$^[1].

Real reprsentation theory, and "representation type".

But once again, if we want to understand how NN's process groups, we need to understand the "more efficient" representation theory over $R$. Here we can start our analysis by looking at the same picture as before: namely, while we have no guarantee that the matrix coefficients of a matrix $\rho \left(g\right)$ in a complex representation has real coefficients, we do have a real subring $R\left[G\right]\subset C\left[G\right]$, namely real-valued formal linear combinations of group elements viewed as a subring of complex-valued ones. Since each complex linear combination can be uniquely identified with a unique block-diagonal matrix $${\text{Block}}_C:=\left(\begin{array}{ccc}{M}_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & M_k\end{array}\right),$$ we want to understand what kinds of subrings we can obtain. This must be a "decomplexification" (more standardly called "real form") of ${\text{Block}}_C$, a subring $${\text{Block}}_R\subset {\text{Block}}_C.$$ which has the following properties: 

• ${\text{Block}}_R$ is closed under multiplication by real scalars (but not necessarily complex scalars),
• ${\text{Block}}_R$ has half the dimension of the real vector space ${\text{Block}}_C$.
• each block-diagonal matrix $M\in {\text{Block}}_C$ can be expressed as $M_0+i{M}_1,$ for $M_0,M_1$ in ${\text{Block}}_R$.

Of course, one "real form" is the set of block-diagonal matrices as above with real coefficients, and sometimes this does correctly capture the image of the real group algebra (this is the case, for example, for the symmetric group $S_n$). However, there exist other possibilities for the real form. The property of being "real" (i.e., having real coefficients as a formal linear combination of group elements) as a group algebra vector may not be compatible (even after allowing a fixed conjugation) with the property of being "real" (i.e., having real coefficients as a matrix) as a block-diagonal matrix. In other words, the group G (and its real group algebra) "chooses" a specific real form of the algebra of block diagonal matrices.

Such real forms can be fully classified, and there are exactly three things that can happen to some $n\times n$ block ${\text{Mat}}_{n\times n}\left(C\right).$

1. It gets replaced by (a conjugate of) $${\text{Mat}}_{n\times n}\left(R\right)\subset {\text{Mat}}_{n\times n}\left(C\right).$$ Irreducible representations ${\rho }_i$ for which this happens for the corresponding block are said to be of "real type" (note that being of real type is a property of a complex-valued representation!).
2. It gets combined with another $n\times n$ block and (again up to conjugating by some invertible matrix $\gamma$), a block-diagonal matrix spanning these two blocks $$\left(\begin{array}{cc}A& 0\\ 0& B\end{array}\right)\in {\text{Block}}_R$$ is "real" if and only if A and B are (coordinatewise) complex conjugates: i.e., coordinatewise, $A=\overline{B}$. Pairs of representations ${\rho }_i,{\rho }_j$ for which this happens are said to be of "complex type", and they always satisfy ${\rho }_i\left(g\right)={\overline{\rho }}_j\left(g\right)$ (after possibly replacing one of ${\rho }_i,{\rho }_j$ by a conjugate). 

3. The dimension n of the corresponding block is even and, up to conjugation, the matrices $M_i\in {\text{Mat}}_{n\times n}\left(R\right)$ in the real form associated to this block can be split into $2\times 2$ blocks:

   $$M_i=\left(\begin{array}{ccc}{h}_{0,0}& \cdots & h_{0,n/2}\\ ⋮& \ddots & ⋮\\ h_{n/2,0}& \cdots & h_{n/2,n/2}\end{array}\right),$$

   where each $h_{ij}\in {\text{Mat}}_{2\times 2}\left(C\right)$ above is a complex-valued $2\times 2$ quaternion matrix, i.e., a matrix of the form 

   $h_{ij}$ = a1 + bi + ci + dj, where $a,\dots ,d$ are real numbers and 1 =$\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ is the usual unit matrix, and we have 

   i = $\left(\begin{array}{cc}i& 0\\ 0& i\end{array}\right)$,

   j = $\left(\begin{array}{cc}0& 1\\ -1& 0\end{array}\right)$ and

   k = $\left(\begin{array}{cc}0& i\\ -i& 0\end{array}\right)$

   (These matrices are known in physics as the Pauli matrices.)

   The resulting 4-dimensional real subalgebra of ${\text{Mat}}_{2\times 2}$ is called the quaternion algebra, denoted $H$. It has the wonderful property of being the only (finite-dimensional) division algebra over $R$ (i.e. algebra all of whose nonzero elements are invertible) except for $C$ and $R$ itself, and the only non-commutative one. Representations ${\rho }_i$ whose associated block exhibits this behavior are said to be of "quaternionic type". 

Together, these results imply that whereas the complex group algebra $C\left[G\right]$ is always (isomorphic to) a direct sum of matrix algebras $${\text{Mat}}_{n_1\times n_1}\oplus \cdots \oplus {\text{Mat}}_{n_k\times n_k}$$ (this expression, with the symbol $\oplus$ denoting "direct sum", is the standard mathematical notation for the block-diagonal algebra), the real group algebra $R\left[G\right]$ is isomorphic to a direct sum of matrix algebras of three forms:

1. Real matrix algebras ${\text{Mat}}_{n\times n}\left(R\right)$ (each is associated to a single complex representation of dimension n).
2. Complex matrix algebras ${\text{Mat}}_{n\times n}\left(C\right)$ (but viewed as an algebra over $R$). These components of the real-valued group algebra "combine" two complex representations, so there are half as many such components as there are irreducible (complex-valued) representations of complex type.
3. Quaternionic matrix algebras ${\text{Mat}}_{n\times n}\left(H\right)$ (each is associated to a single complex representation of dimension 2n). 

Examples

We conclude by giving some explicit examples of the comparison between the group algebra the block-diagonal matrix algebra associated to irreducible representations.

Complex representations of cyclic groups

Let $G=C_n$ be the cyclic group on n elements. In this case it turns out each irreducible representation of G is one-dimensional and there are n of these. By our semisimplicity result above, this is equivalent to the fact that the group algebra $C\left[G\right]$ is isomorphic to the algebra of diagonal $n\times n$ complex matrices. To see this it is enough to construct an isomorphism. 

Let $$\zeta :=\exp \left(2\pi i/n\right)$$ be the elementary nth root of unity. For any residue \[a\in C_n\], we write $$M\left(a\right)=\text{diag}(1,{\zeta }^a,{\zeta }^{2a},\dots ,{\zeta }^{(n-1)a}).$$

Here in order to make sense of ${\zeta }^a$ where a is a residue (rather than an integer), we're implicitly using the fact that ${\zeta }^n=1$ (and so exponents of $\zeta$ only depend on their residue mod n). The mapping above is obviously a homomorphism (i.e., compatible with multiplicaiton). It's a standard fact that the above diagonal matrices are linearly independent as a ranges over the group elements. Since both the algebra of $n\times n$ diagonal matrices is n-dimensional, these n linearly independent vectors must form a basis; since we have identified a basis of the group algebra $C\left[G\right]$ with a basis of the block-diagonal matrix algebra, this is an isomorphism. If we look at the diagonal matrix associated to the linear combination $${\lambda }_{0}0+\dots +{\lambda }_{n-1}n-1,$$ its kth element is $${\lambda }_0+{\lambda }_1\zeta +{\lambda }_2{\zeta }^2+\dots +{\lambda }_{n-1}{\zeta }^{n-1}.$$ Looking at this formula, we see that we have rediscovered the finite Fourier transform: indeed, if we view the coefficients $n\mapsto {\lambda }_n$ as a complex-valued function $\lambda$ on \the group elements $0,\dots ,n-1$,  then the (k,k)th matrix coefficient of the associated diagonal matrix is the Fourier transform $\hat{\lambda }\left(k\right)$. The homomorphism property in this case is equivalent to observing that the convolution product (which is equivalent to the group algebra product -- checking this is a nice exercise) maps to the elementwise product after Fourier transform (and of course multiplying diagonal matrices multiplies their coefficients elementwise). 

Real representations of cyclic groups

Here there is a difference between even and odd n. The results of the previous section tell us that there are n different complex one-dimensional representations ${\rho }_i$ (with the kth representation corresponding to taking an element of the group algebra to the kth diagonal element). A one-dimensional representation just takes each element of $a\in C_n$ to an (invertible) element ${\rho }_k\left(a\right)\in C,$ and is given by the formula ${\rho }_k\left(a\right)={\zeta }^{ka}.$ For all n, the representation ${\rho }_0$ is of real type: indeed, it takes every element of G to 1, which is a real-valued $1\times 1$ matrix. If n is even, then the representation ${\rho }_{n/2}$ is also real-valued, as it takes each element a to $(-1{)}^a\in \pm 1$. And whether n is even or odd, all other ${\rho }_k$ are of complex type: we can check this simply by seeing that ${\rho }_k$ is not isomorphic to the complex conjugate representation ${\overline{\rho }}_k={\rho }_{-k}$. (Note since two matrix representations are isomorphic if and only if they're conjugate by some fixed matrix $\gamma$, any 1-dimensional representation will be conjugate only to itself. Thus it's enough to observe that for $k\ne 0,n/2$, $${\overline{\rho }}_k\left(1\right)=\overline{{\zeta }^k}={\zeta }^{-k}\ne {\rho }_k\left(1\right)$$ to see that ${\rho }_k$ is of complex type. Thus semisimplicity in the real case tells us that the group algebra $R\left[C_n\right]$ is isomorphic 

• $R\oplus C^{\frac{n-1}{2}},$ if n is odd and
• $R^2\oplus C^{\frac{n-2}{2}},$ if n is even.

(Here an "exponent" d is the direct sum expression is shorthand for taking the direct sum of d copies of the same component).

The group of elementary quaternions

Unspurprisingly (since the quaternions are a noncommutative division ring), no commutative group has representations of quaternionic type. The smallest group with a representation of quaternionic type is the group $$G=Q_8$$ of elementary quaternions, with the 8 elements 1, -1, i, -i, j, -j, k, -k. We can identify each of these elements with the corresponding $2\times 2$ "Pauli" matrix above, and then they form a group with identity 1 and the following multiplication table: 

• (-1)$\pm \alpha =\mp \alpha$ for $\alpha$ one of the symbols 1, i, j, k;
• i^2 = j^2 = k^2 = -1;
• ij = k, ji = -k, jk = i, kj = -i, ki = j, ik = -j.

This group has one 2-dimensional complex representation of quaternionic type, thus giving a map $Q_8\to {\text{Mat}}_{1\times 1}H=H$ (remember that the quaternionic dimension is half the complex dimension). This is the obvious map, taking each element of the group to the corresponding quaternion; it also has 4 different 1-dimensional real representations: one is (as for any group) the trivial representation, taking every $g\in G$ to 1, and the other three factoring through one of three surjective homomorphisms $Q_8\to C_2,$ which ignore sign and take 2 of the three letters i, j, k to -1. There are no other representations, so we see that the real group algebra $R\left[Q_8\right]$ is isomorphic to the direct sum $$H\oplus R^4.$$ In particular, $Q_8$ has no representations of complex type.

1. ^{^}

   In fact, these two algebras have the same group algebras over $R$, which is a stronger result. Similarly, the Klein 4-group $C_2\times C_2$ has the same complex group algebra as the cyclic group $C_4$, but these have nonisomorphic group algebras over $R$.