9a. Finite groups
We have seen that the study of the graphs [math]X[/math] is usually best done via the study of their adjacency matrices [math]d\in M_N(0,1)[/math], and with this latter study being typically a mix of linear algebra, combinatorics, calculus, probability, and some computer programming too. We will be back of course to this general principle, on numerous occasions.
However, as another interesting thing that we discovered, the group actions [math]G\curvearrowright X[/math] are something important too, making various group theoretical tools, coming from the study of the permutation groups [math]G\subset S_N[/math], useful for our graph questions. Remember for instance how many things we could say in the case where we have a transitive action [math]G\curvearrowright X[/math] of a cyclic or abelian group [math]G[/math], by using discrete Fourier analysis tools.
In this chapter, and in this whole Part III of this book, and in fact in the remainder of the whole book, we will take such things very seriously, and systematically develop the study of the group actions [math]G\curvearrowright X[/math], our aim being to solve the following question:
\begin{question}
Given a graph [math]X[/math], which groups [math]G[/math] act on it, [math]G\curvearrowright X[/math], and what can be said about [math]X[/math] itself, coming from the group theory of [math]G[/math]?
\end{question}
As already mentioned, we have a whole 100 pages, and later even more, for dealing with this question. So, we will go very slowly, at least in the beginning.
Let us start with some generalities. We already met groups [math]G[/math] and actions [math]G\curvearrowright X[/math] in Part I, and notably in chapter 4, which was dedicated to the transitive graphs. So, we are certainly not new to this subject. However, since there is no hurry with anything, let us first have a crash course in group theory. The starting point is of course:
A group is a set [math]G[/math] endowed with a multiplication operation
- Associativity: we have [math](gh)k=g(hk)[/math], for any [math]g,h,k\in G[/math].
- Unit: there is an element [math]1\in G[/math] such that [math]g1=1g=g[/math], for any [math]g\in G[/math].
- Inverses: for any [math]g\in G[/math] there is [math]g^{-1}\in G[/math] such that [math]gg^{-1}=g^{-1}g=1[/math].
As a first comment, the multiplication law is not necessarily commutative. In the case where it is, [math]gh=hg[/math] for any [math]g,h\in G[/math], we call [math]G[/math] abelian, and we usually denote its multiplication, unit and inverse operation in an additive way, as follows:
However, this is not a general rule, and rather the converse is true, in the sense that if a group is denoted as above, this means that the group must be abelian.
Let us first look at the abelian groups. Here as basic examples we have various groups of numbers, such as [math]\mathbb Z,\mathbb Q,\mathbb R,\mathbb C[/math], with the addition operation [math]+[/math]. Observe that we have as well as [math]\mathbb Q^*,\mathbb R^*,\mathbb C^*[/math], and the unit circle [math]\mathbb T[/math] too, with the multiplication operation [math]\times[/math].
In order to reach to some theory, let us look into the finite group case, [math]|G| \lt \infty[/math]. Here as basic examples we have the cyclic groups, constructed as follows:
The following constructions produce the same group, denoted [math]\mathbb Z_N[/math], which is finite and abelian, and is called cyclic group of order [math]N[/math]:
- [math]\mathbb Z_N[/math] is the set of remainders modulo [math]N[/math], with operation [math]+[/math].
- [math]\mathbb Z_N\subset\mathbb T[/math] is the group of [math]N[/math]-th roots of unity, with operation [math]\times[/math].
Here the equivalence between (1) and (2) is obvious. More complicated, however, is the question of finding the good philosophy and notation for this group. In what concerns us, we will be rather geometers, as usual, and we will often prefer the interpretation (2). As for the notation, we will use [math]\mathbb Z_N[/math], which is very natural.
As a comment here, some algebraists prefer to reserve the notation [math]\mathbb Z_N[/math] for the ring of [math]p[/math]-adic integers, when [math]N=p[/math] is prime, and use other notations for the cyclic group. Personally, although having a long love story with number theory, back in the days, I consider that the cyclic group is far more important, and gets the right to be denoted [math]\mathbb Z_N[/math]. As for the [math]p[/math]-adic integers, a reasonable notation for them, which does the job, is [math]\mathbf Z_N[/math].
As a basic thing to be known, about the abelian groups, still in the finite case, we can construct further examples of such groups by making products between various cyclic groups [math]\mathbb Z_N[/math]. Quite remarkably, we obtain in this way all the finite abelian groups:
The finite abelian groups are precisely the products of cyclic groups:
This is something that we already discussed in chapter 4, with the main ideas of the proof, and for further details on this, and for the technical extensions to the infinite groups as well, we recommend a solid algebra book, such as Lang [1].
Moving forward, let us look now into the general, non-abelian case. The first thought goes here to the [math]N\times N[/math] matrices with their multiplication, but these do not form a group, because we must assume [math]\det A\neq0[/math] in order for our matrix to be invertible.
So, let us call [math]GL_N(\mathbb C)[/math] the group formed by these latter matrices, with nonzero determinant, with [math]GL[/math] standing for “general linear”. By further imposing the condition [math]\det A=1[/math] we obtain a subgroup [math]SL_N(\mathbb C)[/math], with [math]SL[/math] standing for “special linear”, and then we can talk as well about the real versions of these groups, and also intersect everything with the group of unitary matrices [math]U_N[/math]. We obtain in this way 8 groups, as follows:
We have groups of invertible matrices as follows,
This is clear indeed from the above discussion. As a comment, we can talk in fact about [math]GL_N(F)[/math] and [math]SL_N(F)[/math], once we have a ground field [math]F[/math], but in what regards the corresponding orthogonal and unitary groups, things here are more complicated.
There are many other groups of matrices, besides the above ones, as for instance the symplectic groups [math]Sp_N\subset U_N[/math], appearing at [math]N\in2\mathbb N[/math]. Generally speaking, the theory of Lie groups and algebras is in charge with the classification of such beasts.
Finally, and getting now to the point, let us discuss the general finite groups. As basic example here you have the symmetric group [math]S_N[/math], whose main properties are as follows:
The permutations of [math]\{1,\ldots,N\}[/math] form a group, denoted [math]S_N[/math], and called symmetric group. This group has [math]N![/math] elements. The signature map
The group property is indeed clear, and the count is clear as well, by recurrence on [math]N\in\mathbb N[/math]. As for the last assertion, recall here the following formula for the signature of the permutations, which is something elementary to establish:
But this tells us precisely that [math]\varepsilon[/math] is a group morphism, as stated.
As graph theorists, we will be particularly interested in the subgroups [math]G\subset S_N[/math]. We have already met a few such subgroups, as follows:
We have finite non-abelian groups, as follows:
- [math]S_N[/math], the group of permutations of [math]\{1,\ldots,N\}[/math].
- [math]A_N\subset S_N[/math], the permutations having signature [math]1[/math].
- [math]D_N\subset S_N[/math], the group of symmetries of the regular [math]N[/math]-gon.
The fact that we have indeed groups is clear from definitions, and the non-abelianity of these groups is clear as well, provided of course that in each case [math]N[/math] is chosen big enough, and with exercise for you to work out all this, with full details.
For constructing further examples of finite non-abelian groups, the best is to “look up”, by regarding [math]S_N[/math] as being the permutation group of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math]. Indeed, this suggests looking at the symmetry groups of other geometric beasts inside [math]\mathbb R^N[/math], or even [math]\mathbb C^N[/math], and we end up with a whole menagery of groups, as follows:
We have groups of unitary matrices as follows,
This statement is of course something informal, and here are explanations on all this, including definitions for all the groups involved:
(1) To start with, [math]S_N[/math] is the symmetric group [math]S_N[/math] that we know, but regarded now as permutation group of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math], and so as subgroup [math]S_N\subset O_N[/math].
(2) Similarly, [math]A_N[/math] is the alternating group [math]A_N[/math] that we know, but coming now geometrically, as [math]A_N=S_N\cap SO_N[/math], with the intersection being computed inside [math]O_N[/math].
(3) Regarding [math]H_N\subset O_N[/math], this is a famous group, called hyperoctahedral group, appearing as the symmetry group of the hypercube [math]\square_N\subset\mathbb R^N[/math].
(4) Regarding [math]K_N\subset U_N[/math], this is the complex analogue of [math]H_N[/math], consisting of the unitary matrices [math]U\in U_N[/math] having exactly one nonzero entry, on each row and each column.
(5) We have as well on our diagram the groups [math]SH_N,SK_N[/math], with [math]S[/math] standing as usual for “special”, that is, consisting of the matrices in [math]H_N,K_N[/math] having determinant 1.
(6) In what regards now the diagram itself, sure I can see that [math]S_N,A_N[/math] appear twice, but nothing can be done here, after thinking a bit, at how the diagram works.
(7) Let us mention too that the groups [math]\mathbb Z_N,D_N[/math] have their place here, in [math]N[/math]-dimensional geometry, but not exactly on our diagram, as being the symmetry groups of the oriented cycle, and unoriented cycle, with vertices at the simplex [math]X_N=\{e_i\}\subset\mathbb R^N[/math].
(8) Finally, in what regards the finiteness, non-abelianity, and also the name “complex reflection groups”, many things to be checked here, left to you as an exercise.
Very nice all this. Let us summarize this group theory discussion as follows: \begin{conclusion} All groups, or almost, are best seen as being groups of matrices. And even as groups of unitary matrices, in most cases. \end{conclusion} Observe in particular that this justifies our choice in Definition 9.2, for the group operation to be denoted multiplicatively, [math]\times[/math]. Indeed, in most cases, in view of the above general principle, that abstract multiplication is in fact a matrix multiplication.
Thinking a bit at the above principle, that is so useful in practice, taking us away from the abstraction of Definition 9.2, that we would like to have it as a theorem:
\begin{question}
Can we make our general “most groups are in fact groups of matrices” principle, into an abstract theorem?
\end{question}
In general, this is a quite subtle question, related to advanced group theory, such as Lie groups and algebras, and representation theory for them, and we will have a taste of such things in chapter 11 below, when developing the Peter-Weyl theory for the finite groups, that we will need at that time, in connection with our regular graph business.
The point however is that, in the finite group case that we are interested in, the answer to Question 9.10 is indeed “yes”, thanks to two well-known theorems, which are both elementary. First we have the Cayley embedding theorem, which is as follows:
Given a finite group [math]G[/math], we have an embedding as follows,
Given a group element [math]g\in G[/math], we can associate to it the following map:
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 a map as follows:
Our first claim is that this is a group morphism. Indeed, this follows from:
It remains to prove that this group morphism is injective. But this follows from:
Thus, we are led to the conclusion in the statement.
As a comment, the above Cayley embedding theorem, while being certainly very beautiful at the theoretical level, has two weaknesses. First is the fact that 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]. Which in practice, is of course something which is not very good.
As a second point of criticism, the Cayley theorem often provides us with a “wrong embedding” of our group. Indeed, as an illustration here, for the basic examples of groups that we know, the Cayley theorem provides us with embeddings as follows:
And, compare this with the “good embeddings” of these groups, which are:
Thus, the first Cayley 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 obviously useless. So, as a conclusion, the Cayley theorem remains something quite theoretical.
Nevermind. We will fix this, once we will know more. Going ahead now, as previously mentioned, the Cayley theorem is just half of the story, the other half being:
We have a group embedding as follows, obtained by regarding [math]S_N[/math] as permutation group of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math],
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:
Thus, the permutation matrix corresponding to [math]\sigma[/math] is given by:
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, of obvious theoretical importance:
Given a finite group [math]G[/math], we have an embedding as follows,
The Cayley theorem gives an embedding as follows:
On the other hand, Theorem 9.12 provides us with an embedding as follows:
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:
And, compare this with the “good embeddings” of these groups, which are:
As before with the abstract group embeddings [math]G\subset S_N[/math] coming from Cayley, the first abstract embedding is the good one, the second one is not the best possible one, but can be useful, and the third and fourth abstract embeddings are obviously useless.
The problem is now, how to fix this, as to have a theorem providing us with good embeddings? And a bit of thinking at all the above leads to the following conclusion:
\begin{conclusion}
The weak point in all the above is Cayley.
\end{conclusion}
So, leaving aside now Cayley, or rather putting it in our pocket, matter of having it there, handy when meeting abstract questions, let us focus on Theorem 9.12, which is the only reasonable theorem that we have. In relation with the basic groups, we have:
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.
This is something self-explanatory, the idea being that Theorem 9.12 provides us with embeddings as follows, given by the permutation matrices:
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]:
(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.12 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.8 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:
The complex reflection group [math]H_N^s\subset U_N[/math], depending on parameters
Observe that at [math]s \lt \infty[/math], the above groups are finite. Also, at [math]s=1,2,\infty[/math] we obtain the following groups, that we already met in the above:
We will be back later in this chapter with more details about [math]H_N^s[/math]. However, at the philosophical level, we have extended our basic series of finite groups, as follows:
But all this looks a bit complicated, so for being even more philosophers, let restrict the attention to the cases [math]s=1,2,\infty[/math], with [math]H_N^\infty=K_N[/math] having already been adopted, as a kind of “almost” finite group. With this convention, the conclusion is that we have extended our series of basic finite groups, regarded as unitary groups, as follows:
And good news, this will be our final say on the subject. Time now to formulate a grand conclusion to what we did so far in this chapter, as follows:
\begin{grandconclusion}
Group theory can be understood as follows:
- Most interesting groups are groups of matrices, [math]G\subset GL_N(\mathbb C)[/math].
- Quite often, these matrices can be chosen to be unitaries, [math]G\subset U_N[/math].
- The Cayley theorem tells us that [math]G\subset S_N\subset O_N[/math], with [math]N=|G|[/math].
- Most interesting finite groups appear as [math]G\subset U_N[/math], with [math]N \lt \lt |G|[/math].
\end{grandconclusion} Which is very nice, at least we know one thing, and with this type of talisman, we can now safely navigate through the abstractions of group theory. Of course, we will be back to this, once we will know more about groups, and regularly update our conclusions.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].