Group theory -- mathematics of symmetries

[lpetrich]

I decided on a separate thread because there are lots of interesting things here. A group generalizes certain properties of addition and multiplication:

Associative: (a*b)*c = a*(b*c)
Identity: a*e = e*a = a
Inverse: a*inv(a) = inv(a)*a = e

The operation can also be commutative -- a*b = b*a -- and a commutative group is often called an abelian one, after Norwegian mathematician Niels Henrik Abel (1802 - 1829). Does that make a noncommutative group a cainian one?


Groups can be finite or infinite, and infinite ones can be discrete or continuous. Continuous ones are often called Lie groups ("Lee"), after Norwegian mathematician Marius Sophus Lie (1842 - 1899). Lie groups are generated by "Lie algebras", formed from directions of departure of the group's elements from the identity element.

I have written a big Lie-algebra calculator, and you can download it from My Science and Math Stuff. It's in Mathematica, Python, and C++.

 

[lpetrich]

I should mention another condition for defining a group: closure. For all a and b in a group's set, a*b must also be in that set.


Group theory is useful for analyzing symmetries, ways of transforming some entity that makes it look the same. In fact, the name "group" comes from groups of such transforms.

I will illustrate with some examples.

Consider rotations and reflections. They can be combined to make new ones, and thus this combination operation is the group operator for a set of r's and r's. Since r's and r's can be expressed as matrices, and since combination maps onto multiplication of these matrices, combination is thus associative. It need not be commutative, however. The zero rotation is an identity operation, and every r-and-r group therefore includes it. Every r-and-r group also contains inverses, and these can be constructed with matrix inversion.

Start with a circle. Every rotation around its center will be a symmetry of it, and every reflection about a line going through its center will also be a symmetry of it. Their inverses are simple: reverse angle of rotation and the same reflection again.

An interesting feature of these rotations and reflections, is that combining any one reflection with all the rotations gives all the reflections.

Now consider a square. Its eymmetries are rotations with angles 0d, 90d, 180d, and 270d in some direction, and also opposite-side-interchange reflections and diagonal reflections. This is a total of 8 symmetries, and 4 of them are rotations and 4 reflections -- the same number.

A rectangle's symmetries are 0d and 180d rotations, and opposite-side reflections. A rhombus has 0d and 180d rotations and diagonal reflections. A parallelogram has 0d and 180d rotations, and a trapezoid can have and opposite-side reflection. But general quadrangles have only the trivial symmetry: a 0d rotation.

Notice how the symmetries get reduced as one goes to less and less symmetric shapes.

Circle - Square
(all rotations, all reflections) - (0d, 90d, 180d, 270d rotations, both opposite-side and diagonal reflections)

Square - Rectangle
(0d, 90d, 180d, 270d rotations, both opposite-side and diagonal reflections) - (0d, 90d rotations, both opposite-side reflections)

Square - Rhombus
(0d, 90d, 180d, 270d rotations, both opposite-side and diagonal reflections) - (0d, 90d rotations, both diagonal reflections)

Rectangle - Parallelogram
(0d, 90d rotations, both opposite-side reflections) - (0d, 90d rotations)

Rhombus - Parallelogram
(0d, 90d rotations, both diagonal reflections) - (0d, 90d rotations)

Parallelogram - General Quad
(0d, 90d rotations) - (0d rotation)

 

[lpetrich]

A group's number of elements is often called its order. Each element also has a number associated with it that is called that element's order.

Start with that element, combine it with itself, and repeat until one reaches the identity. The number of times that that element appears in this product is the element's order. The identity has order 1, and all other elements orders greater than 1. In finite groups, every element has a finite order, by counting arguments, while in infinite groups, some elements may have infinite orders.

This repeated combination forms a group: {e, a, a*a, a*a*a, ... a^(n-1)}, the "cyclic group", Z_n or Z. It is also the group of addition of numbers 0, 1, ..., n-1 modulo n. Not surprisingly, it is abelian. All the subgroups Z(m) of cyclic group Z have n evenly divisible by m.

A cyclic group can be generated by a single generator element, though in most cases, there will be several elements that can serve as generators. The group (rotations 0d, 90d, 180d, 270d) is group Z4, and it can be generated by 90d or 270d.

An infinite group can have a finite number of generators. For instance, the integers under addition, Z, is generated by one element, 1 or -1, if one includes combining with itself zero and negative numbers of times. Zero giving identity and negative meaning inversion.

 

[lpetrich]

Writing || to denote the order or number of elements, the quad-symmetry groups have

sq = |square group| = 8
rc = |rectangle group| = 4
rh = |rhombus group| = 4
pl = |parallelogram group| = 2
qd = |quad group| = 1

sq/rc = 2, sq/rh = 2, rc/pl = 2, rh/pl = 2, pl/qd = 2

Notice all this even divisibility. That is a general property of subgroups of finite groups. Their orders always evenly divides the orders of their containing groups. Something called Lagrange's theorem.

The proof is rather interest. For a subgroup H of group G, construct all its "left cosets" a*H for a in G. They will cover G, they will be disjoint, and they will all have |H| elements. Thus, |G| = (some positive integer) * |H|. One can the same with "right cosets" H*a. These may equal left cosets, though they need not do so. The ratio |G|/|H| is called the "index" of the the subgroup in the original group.


If the left cosets equal the right cosets, then the subgroup is called a "normal subgroup". Every index-2 subgroup is a normal one, as can easily be shown. The original group G is divided into two cosets: H and C, and since there is only one C, it is both a left coset and a right coset.

One can form a coset-combining operation: (a*H) * (b*H) = (c*H) for some c as a function of a and b. The cosets and this operation form a group, the "quotient group" (G/H) of G and H. Its order |G/H| = |G|/|H|, the index of H in G.

For index 2, H*H = H, H*C = C, C*H = C, and C*C = H. This is equivalent to the operation table for Z2: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 all mod 2. So this quotient group is Z2.

Let's look at it for the square symmetry group and its subsets.
Square to rectangle: (0d and 180d rotations, opposite-side reflections) + (90d and 270d rotations, diagonal reflections)
Square to rhombus: (0d and 180d rotations, diagonal reflections) + (90d and 270d rotations, opposite-side reflections)
Rectangle to parallelogram: (0d and 180d rotations) + (opposite-side reflections)
Rhombus to parallelogram: (0d and 180d rotations) + (diagonal reflections)
Parallelogram to quad: (0d rotation) + (180d rotation)

For some added fun, jump from square to parallelogram. Its cosets are
(0d and 180d rotations) + (90d and 270d rotations) + (opposite-side reflections) + (diagonal reflections)
Its quotient group turns out to be Z2*Z2, the product of two instances of Z2.

Product groups are easy: G1*G2 has elements (a1,a2) for all a1 in G1 and a2 in G2. The group operation: (a1,a2)*(b1,b2) = (a1*a2,b1*b2).

 

[lpetrich]

A rotation-reflection group can be divided up into (pure rotations) and (reflections), which I will call R and S (German "Spiegel": mirror). R is a subgroup of the original group, with S its coset. They have multiplication table
R*R = R, R*S = S, S*R = S, S*S = R, giving quotient group Z2.

Now for a non-normal subgroup, (0d rotation, one opposite-side reflection). It is a version of Z2.

Its left cosets and right cosets are distinct:
(0d rotation, one opposite-side reflection) + (180d rotation, the other opposite-side reflection) + (90d, one diagonal reflection) + (270d, the other diagonal reflection)
(0d rotation, one opposite-side reflection) + (180d rotation, the other opposite-side reflection) + (270d, one diagonal reflection) + (90d, the other diagonal reflection)

Let us define an operation, conjugation: cjg of a by b = b*a*inv(b)

I will give names to that non-normal subgroup and a related one:
S1 = (0d rotation, one opposite-side reflection)
S2 = (0d rotation, the other opposite-side reflection)
When conjugated by any of (0d and 180d rotations, opposite-side reflections), S1 -> S1 and S2 -> S2.
But when conjugated by any of (90d and 270d rotations, diagonal reflections), S1 -> S2 and S2 -> S1, interchanging the two.
Thus, S1 and S2 form a family of conjugate subgroups of the square-symmetry group.


Another application of conjugation of conjugating an element by every element in a group. This produces "conjugacy classes" of elements. It is easy to show that every abelian group has a separate conjugacy class for each element.

All these subsets of the square group are abelian:
Rectangle: Z2*Z2
Rhombus: Z2*Z2
Parallelogram: Z2
Quad: identity group Z1

But the square group is nonabelian:
(90d rotation).(one opposite-side reflection) = (one diagonal reflection)
(one opposite-side reflection).(90d rotation) = (the other diagonal reflection)

Its conjugacy classes are (0d rotation), (180d rotation), (90d and 270d rotations), (opposite-side reflections), (diagonal reflections)

 

[lpetrich]

A rotation/reflection acting on a vector x can easily be represented as some matrix D multiplying x: D.x

The vector's length must remain unchanged: (D.x).(D.x) = x.x, and this gives us the condition that D^T.D = I (raised T = transpose, I = identity matrix). Taking determinants, (det D)² = 1, meaning that det D = 1 or -1, rotations or reflections.

A group RS with both rotations R and reflections S has operation table R*R = R, R*S = S, S*R = S, S*S = R, a version of Z2. This means that R forms a subgroup of RS, and also that the elements of R and S have a bijection between them. Something true of infinite as well as finite r-r groups.

The group of all rotations and reflections in n dimensions is called O and its rotations-only subgroup SO.


For one dimension, D = {{1 or -1}}, the only rotation and the only reflection. Simplifying the D's into 1 and -1 with ordinary multiplication, the only r-r groups are
{1} - pure rotation -- identity group Z1
{1,-1} -- rotation and reflection -- Z2


For two dimensions, we need a rotation angle a:
D(R,a) = {{cos(a), -sin(a)}, {sin(a), cos(a)}}
D(S,a) = {{cos(a), sin(a)}, {sin(a), -cos(a)}}

It is easy to show that det(D(R,a)) = 1 and that det(D(S,a)) = -1

One gets multiplication laws
D(R,a).D(R,b) = D(R,a+b) ... D(R,a).D(S,b) = D(S,a+b) ... D(S,a).D(R,b) = D(S,a-b) ... D(S,a).D(S,b) = D(R,a-b)
identity D(R,0)
inverses
inv(D(R,a)) = D(R,-a) ... inv(D(S,a)) = D(S,a)

Here are all the finite 2D rotation-reflection groups.

Rotations only: C = {rotation angles a = (2pi)*(k/n) for k from 0 to n-1} -- a version of Z, the cyclic group
Rotations and reflections: C with {reflection angles a = a0 + (2pi)*(k/n) for k from 0 to n-1 for some a0} -- a group called the dihedral group

A regular polygon with n sides has r-r symmetry group D with C for rotations only. The square group that I've been discussing is D4. The rectangle and rhombus groups are versions of D2, the parallelogram group C2, the trapezoid group D1, and the general quad group C1.

 

[lpetrich]

I will now consider the symmetries of standard playing cards. Playing Card Frequencies has a picture of them. I'll be ignoring their corner labels (all C2) and their backs (varies).

The symbols or pips:
Spades: D1
Hearts: D1
Diamonds: D2
Clubs: D1
The aces have these symmetries.

The number cards, (general, diamonds), and (spades, hearts, clubs):
2: D2, D2
3: D2, D1
4: D2, D2
5: D2, D1
6: D2, D1
7: D1, D1
8: D2, D1
9: D2, D1
10: D2, D2

The face cards: all C2


The capital letters of the Roman alphabet, in sans-serif block style:
C1: FGJLPQR
C2: NSZ
D1(h): AMTUVWY
D1(v): BCDEK
D2: HIOX

The Greek alphabet:
C1: ΓΡ
C2: ΖΝ
D1(h): ΑΔΛΜΠΤΥΨΩ
D1(v): ΒΕΚΣ
D2: ΗΘΙΞΟΦΧ

The Cyrillic alphabet (Russian version with extra marks ignored):
C1: БГЛРУЦЧЩЪЫЬЯ
C2: ЗИ
D1(h):АДМПТШ
D1(v):ВЕКСЭЮ
D2: ЖНОФХ

The decimal digits:
C1: 245679
C2: 3
D1(h) :
D1(v) :
D2: 018

 

[lpetrich]

Now for permutations. These are rearrangements of ordered lists of symbols. For example, permutation (2,3,1) or 231 for short does:
Second item becomes first item, third item becomes second item, first item becomes third item.

One can combine permutations by doing the first one on the second one's contents. Thus, 231 * 132 = 321.

One can express permutations as matrices, with matrix D(P) having D_k,P(k) = 1 for k = 1 to length(P) and all others being zero. Thus,
231 = {{0,1,0},{0,0,1},{1,0,0}}

The identity permutation with length n is (1,2,3,...,n), and every permutation has an inverse. Thus a set of permutations that is closed under combination of permutations is a group.

Taking an element of a group and doing the group operation on an ordered list of a group's elements gives a permutation of that elements. Thus, if a*b = c and b has position j and c has position i, then the resulting permutation replaces element i with element j.

Here is Z3.
e*e = e, e*a = a, e*b = b
e = 123
a*e = a, a*a = b, a*b = e
a = 231
b*e = b, b*a = e, b*b = a
b = 312


Needless to say, one can do permutations on other entities. Like vertices of regular polygons. For a square, with vertices numbers 1,2,3,4 going around it:
Rotations = 1234 2341 3412 4123
Opposite-side reflections = 2143 4321
Diagonal reflections = 1432 3214

For a regular triangle, an equilateral one,
Rotations = 123 231 312
Reflections = 132 321 213

For D2, use a rectangle with the same vertex numbering as the square:
Rotations = 1234 3412
Reflections = 2143 4321

For D1, use a line segment:
Rotations = 12
Reflections = 21

 

[lpetrich]

The group of all possible permutations is called the symmetric group. For n symbols, Sym has order n!

Permutations can be even or odd, depending on whether one needs an even or an odd number of symbol interchanges to make them. Sym(1) has only one permutation, (1), an even one. But for n > 1, Sym contains equal numbers of even and odd permutations, and the even ones form a subgroup, the alternating group Alt. As one would expect, Sym/Alt = Z2

For an equilateral triangle, its vertex-permutation group is equal to its rotation-reflection group, but that is not the case for more vertices, like for a square. In that case, the vertex-permutation group has 24 elements, its rotation-reflection group 8 elements. The remaining vertex-permutation elements do things like interchange one pair of neighboring vertices but not the other one.


Permutations can be decomposed into cycles. Each member of a cycle gets mapped onto the next one, with the last one wrapping around. Here are some decompositions:
1 (1)
12 (1)(2) ... 21 (12)

123 (1)(2)(3) ... 231 (123) ... 312 (132)
132 (1)(23) ... 321 (13)(2) ... 213 (12)(3)

1234 (1)(2)(3)(4) ... 2341 (1234) ... 3412 (13)(24) ... 4123 (1432)
2143 (12)(34) ... 4321 (14)(23)
1432 (1)(24)(3) ... 3214 (13)(2)(4)

Notice that the cycle lengths evenly divide the order of each element.


A length-n cycle requires (n-1) interchanges to create it. That means that the permutation parity, whether even or odd, is determined by how many even-length cycles there are. Is that number even or odd?

When I implemented  Dodgson's method of preference voting, I implemented it as doing permutations on preference lists and checking on who was the Condorcet winner, if any, for each permutation. Each permutation I scored with a "permutation distance" from the identity permutation:

(length of permutation) - (number of cycles)

That is a count of how many interchanges that is necessary to make that permutation.

For each candidate, I recorded the minimum permutation distance for all permutations that made that candidate a Condorcet winner, and (number of candidates) if no permutation did. One can find my implementation in Voting Algorithms; it's in Python.

 

[lpetrich]

Going from 2D to 3D rotation-reflection groups, we find an interesting difference. While the identity matrix is the identity for all numbers of dimensions, minus the identity matrix is a rotation in the even case and a reflection in the odd case. Furthermore, like the identity, it commutes with every other rotation-reflection matrix, making it relatively easy to work with.

So while minus the identity is a rotation in 2D -- a 180d rotation -- it is a reflection in 3D. This gives us two simple ways of constructing rotation-reflection groups in 3D if one has a pure-rotation one.

For rotation group R, construct {R, -R}.

If R has a subgroup R' with half its size (index 2), then that subgroup has only one coset, C, giving R = {R',C}. Construct {R',-C}.

So to find all the finite 3D rotation-reflection groups, one can first find all the finite rotation ones, and then go from there to add reflections.

 

[lpetrich]

Let us consider what elements a 3D rotation group has. Rotations in three dimensions can be described in axis-angle fashion: (n,a) with unit-vector rotation axis n and rotation angle a. This designation has a sign ambiguity: (n,a) is equivalent to (-n,-a). For n the same, one gets a simple addition law: R(n,a1).R(n,a2) = R(n,a1+a2). For n different, it is much more complicated. But the identity rotation is (n,0) for all n, and the inverse of (n,a) is (n,-a). Here is the axis-angle expression for a rotation matrix:
\(R(n,a)_{ij} = \cos a \delta_{ij} + (1 - \cos a) n_i n_j - \sin a \epsilon_{ijk} n_k\)

Rotations can be expressed as squares of a unit quaternion q with scalar and vector parts qs = cos(a/2), qv = n*sin(a/2):
\(R(q) = (q_s{}^2 - q_v \cdot q_v) \delta_{ij} + 2 q_{v,i} q_{v,j} - 2 q_s \epsilon_{ijk} q_{v,k} \)

Multiplication of rotations directly translates into multiplication of their corresponding quaternions.


To find what possible finite groups of 3D rotations there are, we need to do some group theory. We start with conjugation of rotations: R'.R(n,a).R'^(-1) = R(R'.n,a) -- it rotates the axis and leaves the angle unchanged. Rotating n to -n makes the inverse, so an element and its inverse can be conjugate.

The value of (order of group)/(number of elements in a class) is called the index of the class. It is equal to the order of the "centralizer" subgroup for each element in the class. An element's centralizer is all the elements that commute with it: a*b = b*a. It includes e and a itself. One can define a centralizer for a subset of a group, and for the group itself, it is called the group's center. An abelian group's center is the entire group.

The only elements that commute with rotation (n,a) are elements (n,a') within sign ambiguity. Since we want finite groups, all these groups' subgroups must also be finite, and this means that all elements (n,a') form a finite subgroup.

To see what of this type of group is possible, consider addition modulo 1. A rational number m/n is generated by 1/n, for relatively prime m and n. There is a theorem that states for such m and n, there are integers a and b such that a*m - b*n = 1. That gives that generator result, along with another result that we will use. Two elements 1/m and 1/n will be generated by 1/lcm(m,n) where lcm = least common multiple. Thus, thus type of group is cyclic.

Thus, for axis n, the centralizer of every element (n,a) is the elements (n, (2pi)*k/m) where k = 0 to m-1 for some positive integer m > 1. With the identity, they form a version of Z(m), with order m. For total number of elements N, there are thus (N/m) of the conjugates of axis n in its conjugacy class.

(Number of conjugates of axis n) * (number of non-identity rotations around each axis) = (N/m) * (m-1)

But since an element and its inverse can be in the same class, and since 180d rotations have a sign ambiguity in their axes, so we divide by 2: (1/2) (N/m) * (m - 1)

Summing over all the classes and including the identity gives the order of the group as
N = 1 + sum over m of (1/2)*(N/m)*(m-1)

This gives a very nice-looking expression:
\( \left( 1 - \frac1N \right) = \frac12 \sum_m \left( 1 - \frac1m \right) \)

with the constraint that cycle lengths m must evenly divide N.

 

[lpetrich]

One can now do simple algebra to find which finite 3D rotation groups there are.

First, only one of the m's. This gives us N = (2*m)/(m+1). Since 1 < m < oo, 2 > N > 1, and this case is not possible.


Next, two of them: m1, m2. This gives us N = (2*m1*m2)/(m1+m2). Since both m1 and m2 evenly divide N, we divide both sides by m2:
(N/m2) = (2*m1)/(m1 + m2)

This decreases as m2 increases, being 2 for m2 = 0, 1 for m2 = m1, and 0 for m2 -> oo. Thus, m2 = m1, and N = m1 = m2. This is the group of rotations around one axis.


Now, three of them. Taking (1 - 1/N) = (1/2) * sum of (1-1/m) over the m values, we can start off by supposing the m's to be >= some m0. Then,
(1 - 1/N) >= (3/2) * (1 - 1/m0)

Since N is positive, we get
1 > (3/2)*(1 - 1/m0)

or m0 < 3. Thus, the smallest value of the m's must be 2. Doing this argument with the remaining two m0 values gives
(3/4) > (1 - 1/m0)

or m0 < 4. This means the second m0 must be either 2 or 3. For two m's equal to 2, this gives us
(1 - 1/N) = (1/2) (1/2 + 1/2 + (1-1/m))
or N = 2m. This gives us the 3D-rotation dihedral group. It is the cyclic group with additional 180d rotations around axes perpendicular to the cyclic group's axis.

For two m's being 2 and 3, we find N = (12m)/(6 - m). Using m >= 3, we have m = 3, 4, and 5 as possible values:
m = 3 ... N = 12 ... Tetrahedral group
m = 4 ... N = 24 ... Octahedral group
m = 5 ... N = 60 ... Icosahedral group


Finally four m's. Finding the minimum value m0 as before, we have
1 > 2*(1 - 1/m0)

or m0 < 2. This is not possible, and a solution is also not possible for more than four m's. Thus, we have the complete set of 3D rotation groups. Two infinite families of axial groups: cyclic and dihedral, and three quasi-spherical groups: tetrahedral, octahedral, and icosahedral.

 

[lpetrich]

Adding reflections to these 3D groups, one finds 7 infinite families of axial groups and 7 quasi-spherical groups.

Here are the 7 axial families. I've made the axis vertical and its perpendicular plane horizontal. The groups are built out of vertical reflections and horizontal 2D cyclic and dihedral groups C and D. Vertical reflections and lack of reflection I will call rfl and non

C: C non
C(n,h): C non and C rfl
S(2n): C(2n) alternating between non and rfl
C(n,v): D non
D: D rotations non, reflections rfl
D(n,h): D non and D rfl
D(n,d): D(2n) alternating between non and rfl

S is "Spiegel", German for mirror. I would have preferred something like C(n,s) or C(n,d).

Here are the 7 quasi-spherical ones.

T: tetrahedron rotations
Th: T with reflection (multiplication by -1)
Td: tetrahedron rotations and reflections
O: octahedron rotations
Oh: O with reflection
I: icosahedron rotations
Ih: I with reflection

The abstract groups are:

C: Z ... C(n,h): Z*Z2 ... S(2n): Z ... C(n,v): Dih ... D: Dih ... D(n,h): Dih*Z2 ... D(n,d): Dih(2n)

T: Alt(4) ... Th: Alt(4)*Z2 ...Td: Sym(4) ... O: Sym(4) ... Oh: Sym(4)*Z2 ... I: Alt(5) ... Ih: Alt(5)*Z2

The group T, the tetrahedral rotation group, is the group of even permutations of the vertices of a regular tetrahedron. Adding the odd permutations of those vertices gives Td, the tetrahedral rotation-reflection group. The group Th is a different one, because its reflections make an inversion of the tetrahedron. It is sometimes called the pyritohedral group.

 

[lpetrich]

Having discussed a lot of finite groups, one may want to ask what finite groups are there. That is a big problem, and one that has only partially been solved. But some of its simpler parts of the solution can easily be derived.

All the finite abelian groups are known. They are products of cyclic groups. In fact, some cyclic groups can be decomposed into products of other ones. Consider Z(m*n) where m and n are relatively prime. Consider generator a of the group. One can get a generator of Z(m) with a^n and a generator of Z with a^m. There is a theorem that states that x*m + y*n = 1 for integer x and y, so one finds this combined element of Z(m)*Z: (a^n)^y * (a^m)^x. It equals a^(n*y+m*x) = a, and that generates Z(m*n). So every abelian group is a product of Z(some power of some prime number).

The smallest nonabelian group is Sym(3) = Dih(3), the symmetry group of a regular triangle. It has 6 elements. The other 6-element group is Z6 = Z2*Z3.


All the finite simple groups are also known. These are groups with no nontrivial normal subgroups, none other than the identity subgroup and themselves. There is a simple result for simple groups: no product group is simple.

Consider a group G = G1*G2. Its elements are (a1,a2) where a1 is in G1 and a2 in G2. Now consider subgroup (a,e) where a is in G1 and e is the identity of G2. It is easy to show that that group is a normal subgroup of G. Take (b1,b2).(a,e),
(inv(b1),inv(b2)) = (b1.a.inv(b1),b2.e.inv(b2)) = (b1.a.inv(b1),e). It can also be shown that this subgroup's quotient group is G2, so its quotient group is well-defined.


The abelian finite simple groups are all Z(prime number). For Z(p^n), one finds normal subgroups Z(p^k), where 0 <= k <= n. The nontrivial ones are for 0 < k < n, and they will exist unless n = 1.

For nonabelian finite simple groups, it took a massive effort by some 100 mathematicians over half a century, and the proof is tens of thousands of pages in hundreds of journal articles. Some mathematicians have been working on a simplified proof, but that proof is not quite complete, though it is estimated that it will be about 5,000 pages long.


There are several infinite families of simple groups, and 26 "sporadic" ones. The largest of these is the "monster" group, with order
808017424794512875886459904961710757005754368000000000

That is
2^46 · 3^20 · 5^9 · 7^6 · 11^2 · 13^3 · 17 · 19 · 23 · 29 · 31 · 41 · 47 · 59 · 71

Needless to say, with that many elements, that group has never been constructed, but instead probed with group-theory techniques.


Turning to permutation groups, Sym is not simple for n > 1, since it has Alt as a normal subgroup. But for n >= 5, Alt is simple. The simplicity of Alt(5) may seem like a very arcane result, but it has a very interesting consequence: that a general degree-5 polynomial's roots cannot be found using nth roots.

Let's look at Alt for n <= 4. Alt(2) is the identity group, Alt(3) is Z3, and Alt(4) has normal subgroup Z2*Z2 with quotient group Z3.

In fact, if a finite group has a chain of subgroups extending to the identity group, where each pair of neighbors has a cyclic group as its quotient group, then that group is called "solvable". All finite abelian groups are solvable, but only some finite non-simple nonabelian groups. Alt for n = 2, 3, 4 is solvable, as are all the finite dihedral groups. I added "finite" because I'm not sure about how solvability generalizes to infinite groups.

 

[lpetrich]

The infinite families are the prime-order cyclic groups, the alternating groups of permutations, and the "groups of Lie type".

The smallest ones of some of the nonabelian ones are solvable, ones like Alt(2), Alt(3), and Alt(4).


Here is a (relatively) simple example of the finite groups of Lie type.

The general linear group GL(n,F) for some algebraic field F is composed of n*n matrices of F elements that are invertible. This means that the determinant of each element must be different from 0, the field's additive identity. Matrix multiplication carries over into F's analogs of addition and multiplication.

The special linear group SL(n,F) is a normal subgroup of it. Its elements' determinant values are all 1, the field's multiplicative identity.

The projective linear group PGL(n,F) is the quotient group of GL(n,F) with respect to its subgroup {a*I} for all nonzero a in F and I being the identity matrix. The "projective" part of its name comes from being able to express the group's elements as bilinear projection operators on a vector with length (n-1):
{x1,x2}' = {a11*x1 + a12*x2 + a13, a21*x1 + a22*x2 + a23} / (a31*x1 + a32*x2 + a33)

The projective special group PSL(n,F) is like PGL(n,F), but the elements in all its sets of elements have determinant 1.

In summary:
GL(n,q) has normal subgroup SL(n,q) with quotient group (nonzero in GF(q): Z(q-1))
GL(n,q) has normal subgroup (nonzero in GF(q): Z(q-1))*I with quotient group PGL(n,q)
SL(n,q) has normal subgroup (nonzero in GF(q) with nth power = 1: Z(gcd(q-1,n)))*I with quotient group PSL(n,q)
PGL(n,q) has normal subgroup PSL(n,q) with quotient group (nonzero in GF(q) with nth power = 1: Z(gcd(q-1,n)))

Using field GF(2), GL(n,2) = SL(n,2) = PGL(n,2) = PSL(n,2), because that field has only one nonzero value.

GL(2,2) = Sym(3), the smallest nonabelian group. Its elements:
identity: {{1, 0}, {0, 1}}
order 3: {{0, 1}, {1, 1}} ... {{1, 1}, {1, 0}}
order 2: {{0, 1}, {1, 0}} ... {{1, 0}, {1, 1}} ... {{1, 1}, {0, 1}}

GL(2,3) has order 48. SL(2,3) and PGL(2,3) have order 24. PSL(2,3) has order 12 and equals Alt(4).
Etc.

In general,
|GL(n,q)| = q^(n*(n-1)/2) * sum over k from 1 to n of q^k - 1
|SL(n,q)| = |PGL(n,q)| = 1/(q-1)*|GL(n,q)|
|PSL(n,q)| = 1/gcd(n,q-1)*|SL(n,q)|

All its special cases:
PSL(2,2) = Sym(3)
PSL(2,3) = Alt(4)
PSL(2,4) = PSL(2,5) = Alt(5)
PSL(2,7) = PSL(3,2)
PSL(2,9) = Alt(6)
PSL(4,2) = Alt(8)

Some of the other groups of Lie type have some similar special cases.

 

[lpetrich]

Now for a group's commutator. The commutator is a kind of operator that measures departure from being commutative. For matrices, it has a well-known form:
[a,b] = a.b - b.a

This can be generalized to any abstract-algebra ring, but a group has only one operation and not two. Here it is for a group:
[a,b] = a*b*inv(a)*inv(b)

With a and b drawn from a group G, the [a,b] values generator the "commutator subgroup" of G: [G,G]. One can define commutators for subgroups in similar fashion: [G1,G2] for a in G1 and b in G2.

A group's commutator subgroup is normal, and its quotient group is the largest possible abelian quotient group for the original group. The commutator subgroup of a product group is the product of the individual groups' commutator subgroups. An abelian group has the identity group as its commutator subgroup.

One can repeat the commutation operation in two ways. The first is to repeatedly take commutator subgroups, producing the "derived series":
G1 = [G,G]
G2 = [G1,G1]
G3 = [G2,G2]
until [Gx,Gx] = Gx. If it stops at the identity group, then G is solvable.

Another way is with the original group also in it. This produces the "lower central series":
G1 = [G,G]
G2 = [G,G1]
G3 = [G,G2]
until [G,Gx] = Gx. If it stops at the identity group, then G is nilpotent.

Let us consider the derived series of the dihedral group, Dih. It is generated by elements a and n that satisfy a^n = b^2 = e and b*a*inv(b) = inv(a)

Its commutator subgroup is generated by a^2, giving us
Dih(2n) -> Z with quotient Z2*Z2
Dih(2n+1) -> Z(2n+1) with quotient Z2

Since Z is abelian, that means that the dihedral group is solvable. Along with the cyclic group being solvable, this means that all 1D, 2D, and infinite-family 3D rotation groups are also solvable.

Let's now consider the extra seven 3D rotation groups. T = Alt(4), Th = Alt(4)*Z2, Td = Sym(4), O = Sym(4), Oh = Sym(4)*Z2, I = Alt(5), Ih = Alt(5)*Z2.

Constructing the derived series for Sym(4) gives
Sym(4) -> Alt(4) with quotient Z2
Alt(4) -> Z2*Z2 with quotient Z3
Z2*Z2 is abelian

But the derived series for Alt(5) ends at Alt(5), because that group is simple.

 

[lpetrich]

Now for a group's commutator. The commutator is a kind of operator that measures departure from being commutative. For matrices, it has a well-known form:
[a,b] = a.b - b.a

This can be generalized to any abstract-algebra ring, but a group has only one operation and not two. Here it is for a group:
[a,b] = a*b*inv(a)*inv(b)

With a and b drawn from a group G, the [a,b] values generator the "commutator subgroup" of G: [G,G]. One can define commutators for subgroups in similar fashion: [G1,G2] for a in G1 and b in G2.

A group's commutator subgroup is normal, and its quotient group is the largest possible abelian quotient group for the original group. The commutator subgroup of a product group is the product of the individual groups' commutator subgroups. An abelian group has the identity group as its commutator subgroup.

One can repeat the commutation operation in two ways. The first is to repeatedly take commutator subgroups, producing the "derived series":
G1 = [G,G]
G2 = [G1,G1]
G3 = [G2,G2]
until [Gx,Gx] = Gx. If it stops at the identity group, then G is solvable.

Another way is with the original group also in it. This produces the "lower central series":
G1 = [G,G]
G2 = [G,G1]
G3 = [G,G2]
until [G,Gx] = Gx. If it stops at the identity group, then G is "nilpotent", close to being commutative.

Let us consider the derived series of the dihedral group, Dih. It is generated by elements a and n that satisfy a^n = b^2 = e and b*a*inv(b) = inv(a)

Its commutator subgroup is generated by a^2, giving us
Dih(2n) -> Z with quotient Z2*Z2
Dih(2n+1) -> Z(2n+1) with quotient Z2

Since Z is abelian, that means that the dihedral group is solvable. Along with the cyclic group being solvable, this means that all 1D, 2D, and infinite-family 3D rotation groups are also solvable.

Let's now consider the extra seven 3D rotation groups. T = Alt(4), Th = Alt(4)*Z2, Td = Sym(4), O = Sym(4), Oh = Sym(4)*Z2, I = Alt(5), Ih = Alt(5)*Z2.

Constructing the derived series for Sym(4) gives
Sym(4) -> Alt(4) with quotient Z2
Alt(4) -> Z2*Z2 with quotient Z3
Z2*Z2 is abelian

But the derived series for Alt(5) ends at Alt(5), because that group is simple.

 

[lpetrich]

The Tyger by William Blake | Poetry Foundation

Tyger Tyger, burning bright,
In the forests of the night;
What immortal hand or eye,
Could frame thy fearful symmetry?

written in 1795. William Blake seems to have meant "symmetry" in some poetic sense, rather than in a mathematical sense. A tiger's most obvious mathematical symmetry is bilateral symmetry, and that is D1, not very impressive. The animal has various other approximate symmetries, like its stripes (repeat in one direction, extend in the other), and some features of its internal organs, its cells, and its molecules. Even its genome has an approximate symmetry in it. But most of those symmetries do not have much structure in them.

But many viruses have an impressive kind of symmetry: icosahedral symmetry. The icosahedral rotation group has one identity, 15 180d rotations, 20 120d rotations, 24 72d rotations, and 24 144d rotations. This group is simple, meaning that it does not have any nontrivial normal subgroups. Thus, all its nontrivial subgroups come in families of subgroups related by conjugation.

Virus, virus, burning bright?

 

[lpetrich]

Many of the groups that I have discussed are groups expressed as matrices. This is always possible in general when one uses matrices of complex numbers. Such sets of matrices are called group representations, matrices R(a) for group elements a where
R(a).R(b) = R(a*b)

Permutations can easily be expressed as matrices of 1's and 0's, thus making permutation representations, and the representation from element-operation permutations is called the "regular representation".

Let us consider 2D rotations. Their contents can be "rotated" in complex space, making them diagonal:
{{cos(a), -sin(a)}, {sin{a), cos(a)}} = umat.diag({e^(i*a), e^(-i*a)}).inv(umat)

where umat = 1/sqrt(2) * {{1, -i}, {-i, 1}}

So the 2*2 matrix form is a block-diagonal combination of 1*1 matrix forms. So the usual form of a 2D pure rotation group can be reduced to two 1D forms, meaning that that representation can be reduced to two smaller ones. One cannot get smaller than 1D, so those 1D reps are irreducible, thus being irreps. Formally, a rep is irreducible if some X that satisfies
X.R(a) = R(a).X

for all a in the group, then X is proportional to the identity matrix. That is obviously the case for a 1*1 matrix. In fact, every abelian group has only 1D irreps, something that can easily be proved.

R(a).R(b) = R(b).R(a)

means that R(a) = r(a)*I for all a, and any general X can satisfy X.R(a) = R(a).X. To make X proportional to the idenitity, one has to restrict to only one dimension.

For reflection,
{{cos(a), sin(a)}, {sin{a), -cos(a)}} = umat.({0,-i*e^(i*a)},{i*e^(-i*a),0}}.inv(umat)

and it can be shown that this representation of a rotation-reflection group is irreducible, except for D1 and D2.



Pure rotations lead to the question of representations of cyclic groups in general. Consider Z. It has a representation with form
R(a) = w^a
where w = e^(i*(2pi)/n)

But R(a) also has reps w*(c*a) for every c, including c = 0. That rep is 1 -- the identity rep. In fact, every group has an identity rep. So we express the cyclic group's reps as
R(c,a) = w^(c*a)
where c is for the rep and a for the group element.

For finite abelian groups in general, one multiples the reps of its component cyclic groups. Thus,
R(c,a) = R(c1,a1)*R(c2,a2)*...

for Z(n1)*Z(n2)*... with rep label c = (c1,c2,...) and element a = (a1,a2,...)

 

[lpetrich]

For nonabelian groups, it seems much more difficult, because at least one irrep will have dimension greater than 1, but there is a convenient shortcut. Group characters χ, which I will write X:

X(a) = trace(R(a)) where trace(matrix M) = sum over k of M(k,k)

This is a great simplification, since for every a in some conjugacy class A, X(a) is the same. Thus, we can talk about X(A). Also, X(a) is the sum of the eigenvalues of matrix R(a), and for element order n, these are all nth roots of unity: exp(i*(2pi)*k/n). Also, if b = a^n,
(eigenvalues of R(b)) = (eigenvalues of R(a))^n.

Furthermore, the number of classes = the number of irreps, so X is a square matrix. X also has orthogonality properties, for reps x and y:

sum over classes A of n(A)*X(x,A)*X(y,A)^* = N * δ(x,y)
sum over irreps x of X(x,A)*X(x,B)^* = (N / n(A)) * δ(a,b)

for group order N and class size n(A) for class A.

The dimension of irrep x is, not surprisingly, X(x,e). It evenly divides N. Also, N = sum over x of X(x,e)^2.

If a group has a quotient group, then the group's irreps include the quotient group's irreps, using the quotient-group elements that each original-group element is associated with. So a group's characters include its quotient groups' characters.

Thus, we get several constraints on the possible values of group characters, and I myself have used that to find character tables for several groups.


One can compose a product rep:
R(a)(i,j) = R1(a)(i1,j1)*R2(a)(i2,j2) where i = (i1,i2) and j = (j1,j2)

Its characters are X(a) = X1(a)*X2(a).

If the reps are the same, then one can construct (anti)symmetrized products:

R(a)(i,j) = (1/2) * (R0(a)(i1,j1)*R0(a)(i2,j2) +- R0(a)(i1,j2)*R0(a)(i2,j1))
giving
X(a) = (1/2) * (X0(a)^2 +- X0(a^2)) where a^2 = a*a

One can extend this to products of more instances of the same rep. I have also used these results to construct character tables of groups.