1. Linear algebra and group theory
  2. Finite groups
  3. 9c. Cayley embeddings

9c. Cayley embeddings

[math] \newcommand{\mathds}{\mathbb}[/math]

At the level of the general theory now, we have the following fundamental result regarding the finite groups, due to Cayley:

Theorem

Given a finite group [math]G[/math], we have an embedding as follows,

[[math]] G\subset S_N\quad,\quad g\to(h\to gh) [[/math]]
with [math]N=|G|[/math]. Thus, any finite group is a permutation group.


Show Proof

Given a group element [math]g\in G[/math], we can associate to it the following map:

[[math]] \sigma_g:G\to G\quad,\quad h\to gh [[/math]]

Since [math]gh=gh'[/math] implies [math]h=h'[/math], this map is bijective, and so is a permutation of [math]G[/math], viewed as a set. Thus, with [math]N=|G|[/math], we can view this map as a usual permutation, [math]\sigma_G\in S_N[/math]. Summarizing, we have constructed so far a map as follows:

[[math]] G\to S_N\quad,\quad g\to\sigma_g [[/math]]

Our first claim is that this is a group morphism. Indeed, this follows from:

[[math]] \sigma_g\sigma_h(k) =\sigma_g(hk) =ghk =\sigma_{gh}(k) [[/math]]

It remains to prove that this group morphism is injective. But this follows from:

[[math]] \begin{eqnarray*} g\neq h &\implies&\sigma_g(1)\neq\sigma_h(1)\\ &\implies&\sigma_g\neq\sigma_h \end{eqnarray*} [[/math]]


Thus, we are led to the conclusion in the statement.

■

Observe that in the above statement the embedding [math]G\subset S_N[/math] that we constructed depends on a particular writing [math]G=\{g_1,\ldots,g_N\}[/math], which is needed in order to identify the permutations of [math]G[/math] with the elements of the symmetric group [math]S_N[/math]. This is not very good, in practice, and as an illustration, for the basic examples of groups that we know, the Cayley theorem provides us with embeddings as follows:

[[math]] \mathbb Z_N\subset S_N\quad,\quad D_N\subset S_{2N}\quad,\quad S_N\subset S_{N!}\quad,\quad H_N\subset S_{2^NN!} [[/math]]

And here the first embedding is the good one, the second one is not the best possible one, but can be useful, and the third and fourth embeddings are useless. Thus, as a conclusion, the Cayley theorem remains something quite theoretical. We will be back to this later on, with a systematic study of the “representation” problem.


Getting back now to our main series of finite groups, [math]\mathbb Z_N\subset D_N\subset S_N\subset H_N[/math], these are of course permutation groups, according to the above. However, and perhaps even more interestingly, these are as well subgroups of the orthogonal group [math]O_N[/math]:

[[math]] \mathbb Z_N\subset D_N\subset S_N\subset H_N\subset O_N [[/math]]

Indeed, we have [math]H_N\subset O_N[/math], because any transformation of the unit cube in [math]\mathbb R^N[/math] must extend into an isometry of the whole [math]\mathbb R^N[/math], in the obvious way. Now in view of this, it makes sense to look at the finite subgroups [math]G\subset O_N[/math]. With two remarks, namely:


(1) Although we do not have examples yet, following our general “complex is better than real” philosophy, it is better to look at the general subgroups [math]G\subset U_N[/math].


(2) Also, it is better to upgrade our study to the case where [math]G[/math] is compact, and this in order to cover some interesting continuous groups, such as [math]O_N,U_N,SO_N,SU_N[/math].


Long story short, we are led in this way to the study of the closed subgroups [math]G\subset U_N[/math]. Let us start our discussion here with the following simple fact:

Proposition

The closed subgroups [math]G\subset U_N[/math] are precisely the closed sets of matrices [math]G\subset U_N[/math] satisfying the following conditions:

  • [math]U,V\in G\implies UV\in G[/math].
  • [math]1\in G[/math].
  • [math]U\in G\implies U^{-1}\in G[/math].


Show Proof

This is clear from definitions, the only point with this statement being the fact that a subset [math]G\subset U_N[/math] can be a group or not, as indicated above.

■

It is possible to get beyond this, first with a result stating that any closed subgroup [math]G\subset U_N[/math] is a smooth manifold, and then with a result stating that, conversely, any smooth compact group appears as a closed subgroup [math]G\subset U_N[/math] of some unitary group. However, all this is quite advanced, and we will not need it, in what follows.


As a second result now regarding the closed subgroups [math]G\subset U_N[/math], let us prove that any finite group [math]G[/math] appears in this way. This is something more or less clear from what we have, but let us make this precise. We first have the following key result:

Theorem

We have a group embedding as follows, obtained by regarding [math]S_N[/math] as the permutation group of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math],

[[math]] S_N\subset O_N [[/math]]
which makes [math]\sigma\in S_N[/math] correspond to the matrix having [math]1[/math] on row [math]i[/math] and column [math]\sigma(i)[/math], for any [math]i[/math], and having [math]0[/math] entries elsewhere.


Show Proof

The first assertion is clear, because the permutations of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math] are isometries. Regarding now the explicit formula, we have by definition:

[[math]] \sigma(e_j)=e_{\sigma(j)} [[/math]]

Thus, the permutation matrix corresponding to [math]\sigma[/math] is given by:

[[math]] \sigma_{ij}= \begin{cases} 1&{\rm if}\ \sigma(j)=i\\ 0&{\rm otherwise} \end{cases} [[/math]]

Thus, we are led to the formula in the statement.

■

We can combine the above result with the Cayley theorem, and we obtain the following result, which is something very nice, having theoretical importance:

Theorem

Given a finite group [math]G[/math], we have an embedding as follows,

[[math]] G\subset O_N\quad,\quad g\to(e_h\to e_{gh}) [[/math]]
with [math]N=|G|[/math]. Thus, any finite group is an orthogonal matrix group.


Show Proof

The Cayley theorem gives an embedding as follows:

[[math]] G\subset S_N\quad,\quad g\to(h\to gh) [[/math]]

On the other hand, Theorem 9.18 provides us with an embedding as follows:

[[math]] S_N\subset O_N\quad,\quad \sigma\to(e_i\to e_{\sigma(i)}) [[/math]]

Thus, we are led to the conclusion in the statement.

■

The same remarks as for the Cayley theorem apply. First, the embedding [math]G\subset O_N[/math] that we constructed depends on a particular writing [math]G=\{g_1,\ldots,g_N\}[/math]. And also, for the basic examples of groups that we know, the embeddings that we obtain are as follows:

[[math]] \mathbb Z_N\subset O_N\quad,\quad D_N\subset O_{2N}\quad,\quad S_N\subset O_{N!}\quad,\quad H_N\subset O_{2^NN!} [[/math]]

As before, here the first embedding is the good one, the second one is not the best possible one, but can be useful, and the third and fourth embeddings are useless.


Summarizing, in order to advance, it is better to forget about the Cayley theorem, and build on Theorem 9.18 instead. In relation with the basic groups, we have:

Theorem

We have the following finite groups of matrices:

  • [math]\mathbb Z_N\subset O_N[/math], the cyclic permutation matrices.
  • [math]D_N\subset O_N[/math], the dihedral permutation matrices.
  • [math]S_N\subset O_N[/math], the permutation matrices.
  • [math]H_N\subset O_N[/math], the signed permutation matrices.


Show Proof

This is something self-explanatory, the idea being that Theorem 9.18 provides us with embeddings as follows, given by the permutation matrices:

[[math]] \mathbb Z_N\subset D_N\subset S_N\subset O_N [[/math]]

In addition, looking back at the definition of [math]H_N[/math], this group inserts into the embedding on the right, [math]S_N\subset H_N\subset O_N[/math]. Thus, we are led to the conclusion that all our 4 groups appear as groups of suitable “permutation type matrices”. To be more precise:


(1) The cyclic permutation matrices are by definition the matrices as follows, with 0 entries elsewhere, and form a group, which is isomorphic to the cyclic group [math]\mathbb Z_N[/math]:

[[math]] U=\begin{pmatrix} &&&1&&&\\ &&&&1&&\\ &&&&&\ddots&\\ &&&&&&1\\ 1&&&&&\\ &\ddots&&&&&\\ &&1&&& \end{pmatrix} [[/math]]

(2) The dihedral matrices are the above cyclic permutation matrices, plus some suitable symmetry permutation matrices, and form a group which is isomorphic to [math]D_N[/math].


(3) The permutation matrices, which by Theorem 9.18 form a group which is isomorphic to [math]S_N[/math], are the [math]0-1[/math] matrices having exactly one 1 on each row and column.


(4) Finally, regarding the signed permutation matrices, these are by definition the [math](-1)-0-1[/math] matrices having exactly one nonzero entry on each row and column, and by Theorem 9.14 these matrices form a group, which is isomorphic to [math]H_N[/math].

■

The above groups are all groups of orthogonal matrices. When looking into general unitary matrices, we led to the following interesting class of groups:

Definition

The complex reflection group [math]H_N^s\subset U_N[/math], depending on parameters

[[math]] N\in\mathbb N\quad,\quad s\in\mathbb N\cup\{\infty\} [[/math]]
is the group of permutation-type matrices with [math]s[/math]-th roots of unity as entries,

[[math]] H_N^s=M_N(\mathbb Z_s\cup\{0\})\cap U_N [[/math]]
with the convention [math]\mathbb Z_\infty=\mathbb T[/math], at [math]s=\infty[/math].

Observe that at [math]s=1,2[/math] we obtain the following groups:

[[math]] H_N^1=S_N\quad,\quad H_N^2=H_N [[/math]]

Another important particular case is [math]s=\infty[/math], where we obtain a group which is actually not finite, but is still compact, denoted as follows:

[[math]] K_N\subset U_N [[/math]]

In general, in analogy with what we know about [math]S_N,H_N[/math], we first have:

Proposition

The number of elements of [math]H_N^s[/math] with [math]s\in\mathbb N[/math] is:

[[math]] |H_N^s|=s^NN! [[/math]]
At [math]s=\infty[/math], the group [math]K_N=H_N^\infty[/math] that we obtain is infinite.


Show Proof

This is indeed clear from our definition of [math]H_N^s[/math], as a matrix group as above, because there are [math]N![/math] choices for a permutation-type matrix, and then [math]s^N[/math] choices for the corresponding [math]s[/math]-roots of unity, which must decorate the [math]N[/math] nonzero entries.

■

Once again in analogy with what we know at [math]s=1,2[/math], we have as well:

Theorem

We have a wreath product decomposition as follows,

[[math]] H_N^s=\mathbb Z_s\wr S_N [[/math]]
which means by definition that we have a crossed product decomposition

[[math]] H_N^s=\mathbb Z_s^N\rtimes S_N [[/math]]
with the permutations [math]\sigma\in S_N[/math] acting on the elements [math]e\in\mathbb Z_s^N[/math] as follows:

[[math]] \sigma(e_1,\ldots,e_k)=(e_{\sigma(1)},\ldots,e_{\sigma(k)}) [[/math]]


Show Proof

As explained in the proof of Proposition 9.22, the elements of [math]H_N^s[/math] can be identified with the pairs [math]g=(e,\sigma)[/math] consisting of a permutation [math]\sigma\in S_N[/math], and a decorating vector [math]e\in\mathbb Z_s^N[/math], so that at the level of the cardinalities, we have:

[[math]] |H_N|=|\mathbb Z_s^N\times S_N| [[/math]]

Now observe that the product formula for two such pairs [math]g=(e,\sigma)[/math] is as follows, with the permutations [math]\sigma\in S_N[/math] acting on the elements [math]f\in\mathbb Z_s^N[/math] as in the statement:

[[math]] (e,\sigma)(f,\tau)=(ef^\sigma,\sigma\tau) [[/math]]

Thus, we are in the framework of Definition 9.10, and we obtain [math]H_N^s=\mathbb Z_s^N\rtimes S_N[/math]. But this can be written, by definition, as [math]H_N^s=\mathbb Z_s\wr S_N[/math], and we are done.

■

Summarizing, and by focusing now on the cases [math]s=1,2,\infty[/math], which are the most important, we have extended our series of basic unitary groups, as follows:

[[math]] \mathbb Z_N\subset D_N\subset S_N\subset H_N\subset K_N [[/math]]

In addition to this, we have the groups [math]H_N^s[/math] with [math]s\in\{3,4,\ldots,\}[/math]. However, these will not fit well into the above series of inclusions, because we only have:

[[math]] s|t\implies H_N^s\subset H_N^t [[/math]]

Thus, we can only extend our series of inclusions as follows:

[[math]] \mathbb Z_N\subset D_N\subset S_N\subset H_N\subset H_N^4\subset H_N^8\subset\ldots\ldots\subset K_N [[/math]]

We will be back later to [math]H_N^s[/math], with more theory, and some generalizations as well.


General references

Banica, Teo (2024). "Linear algebra and group theory". arXiv:2206.09283 [math.CO].