Group theory -- mathematics of symmetries

[lpetrich]

As an example, I will find the character table of the dihedral group. Its class and irrep content is somewhat different between even and odd parameter values, so I will be careful about that.

Its class content is:
r(0) = {e}
r(k) = {a^k, a^(n-k)} for 0 < k < n/2
For even n, r(n/2) = {a^(n/2)}
s = {b*a^k for 0 <= k < n}
For even n, s0 = {b*a^k for even k} and s1 = {b*a^k for odd k}

That gives n+3 classes for Dih(2n) and n+2 classes for Dih(2n+1)

The characters are:
Identity: X = 1
Reflection flip: X(r(k)) = 1, X(s) = -1
Even-n alternation X(r(k)) = (-1)^k, X(s0) = 1, X(s1) = -1
Also X(r(k)) = (-1)^k, X(s0) = -1, X(s1) = 1
Rotation-reflection matrices: for 0 < x < n/2:
X(r(k)) = 2*cos((2pi)*x*k/n), X(s) = 0

Group
Class content
Class sizes: total size
Irreps

Dih(1):
r s
1 1: 2
1 1
1 -1
Dih(2):
r0 r1 s0 s1
1 1 1 1: 4
1 1 1 1
1 1 -1 -1
1 -1 1 -1
1 -1 -1 1
Dih(3):
r0 r1 s
1 2 3: 6
1 1 1
1 1 -1
2 -1 0
Dih(4):
r0 r1 r2 s0 s1
1 2 1 2 2: 8
1 1 1 1 1
1 1 1 -1 -1
1 -1 1 1 -1
1 -1 1 -1 1
2 0 -2 0 0

One can also do this analysis for the tetrahedral, octahedral, and icosahedral groups.

 

[lpetrich]

As I'd mentioned earlier, 3D rotations are related to quaternions. But quaternions can also be expressed in matrix form, though real-number ones require complex-number matrices:

(scalar part)*(2*2 identity) + i * (vector part).(Pauli matrices)

Or -i, depending on the multiplication convention.

Quaternionic versions of all the 3D rotation groups exist. Here are all the finite ones:

Quaternionic cyclic: scalar + vector quaternion: {cos(a), 0, 0, sin(a)}

QC(2n+1) maps directly onto C(2n+1)

However, QC(2n) maps onto C by C being the quotient group relative to subgroup {I,-I}. All the other finite quaternionic rotation groups also do that. As abstract groups, Z(2n) has subgroup Z2 with quotient Z.

The quaternionic dihedral or dicyclic group is Dic, with the same elements as Dih(2n), but with b^2 = a^n. It has the same class and irrep composition as Dih(2n). For the main axis in the z direction, the group has quaternion elements
{cos(a), 0, 0, sin(a)}
{0,cos(a), sin(a), 0}

Dic maps onto Dih

The quaternionic tetrahedral group has quaternions
{+-1, 0, 0, 0} and all its permutations
(1/2)*{+-1, +-1, +-1, +-1}

Class content: (quaternionic) rotation angle
The ' denotes the second half of the 120d rotations.
w = (-1+sqrt(-3))/2, w' = w^2 = (-1-sqrt(-3))/2

Tetrahedral
0d 180d 120d 120d'
1 3 4 4: 12
1 1 1 1
1 1 w w'
1 1 w' w
3 -1 0 0

Quaternionic Tetrahedral
0d 180d 90d 60d 120d 60d' 120d'
1 1 6 4 4 4 4: 24
1 1 1 1 1 1 1
1 1 1 w w w' w'
1 1 1 w' w' w w
3 3 -1 0 0 0 0
2 -2 0 1 -1 1 -1
2 -2 0 w -w w' -w'
2 -2 0 w' -w' w -w

 

[lpetrich]

The octahedral group has the tetrahedral group's quaternions with
1/sqrt(2) * {+-1, +-1, 0, 0} and all its permutations
Will use r = sqrt(2) for convenience.

Octahedral
0d 180d 120d 90d 180d'
1 3 8 6 6: 24
1 1 1 1 1
1 1 1 -1 -1
2 2 -1 0 0
3 -1 0 1 -1
3 -1 0 -1 1

Quaternionic octahedral
0d 180d 90d 60d 120d 45d 135d 90d'
1 1 6 8 8 . 6 6 12: 48
1 1 1 1 1 . 1 1 1
1 1 1 1 1 . -1 -1 -1
2 2 2 -1 -1 . 0 0 0
3 3 -1 0 0 . 1 1 -1
3 3 -1 0 0 . -1 -1 1
2 -2 0 1 -1 . r -r 0
2 -2 0 1 -1 . -r r 0
4 -4 0 -1 1 . 0 0 0

The icosahedral group has the tetrahedral group's quaternions with
1/2 * {+-q1, +-1, +-q2 0} and all its *even* permutations
where q = sqrt(5)
and q1 = (1+q)/2 and q2 = (1-q)/2

0d 180d 120d . 72d 144d
1 15 20 12 12: 60
1 1 1 1 1
3 -1 0 q1 q2
3 -1 0 q2 q1
4 0 1 -1 -1
5 1 -1 0 0

0d 180d 90d 60d 120d . 36d 144d 72d 108d
1 1 30 20 20 . 12 12 12 12
1 1 1 1 1 . 1 1 1 1
3 3 -1 0 0 . q1 q1 q2 q2
3 3 -1 0 0 . q2 q2 q1 q1
4 4 0 1 1 . -1 -1 -1 -1
5 5 1 -1 -1 . 0 0 0 0
2 -2 0 1 -1 . q1 -q1 -q2 q2
2 -2 0 1 -1 . q2 -q2 -q1 q1
4 -4 0 -1 1 . 1 -1 -1 1
6 -6 0 0 0 . -1 1 1 -1

Note that some of these irreps are related by sign reversals in their square roots: tetrahedral sqrt(-3) octahedral sqrt(2) icosahedral sqrt(5).

 

[lpetrich]

Having discussed finite groups in gory detail, I turn to infinite ones.

Integers under addition are a discrete example, and real numbers under addition are a continuous example.

Nonzero real numbers under multiplication are also a group, a group whose elements are in two separate continuous parts: positive real numbers and negative real numbers.

Summing over elements must be turned into integration over element parameters for continuous groups. There is a standard weighting of the parameter integration called the "Haar measure". Consider element a(p) with parameters p, and an element a(p') with new parameters p', formed with element b:
a(p') = b*a(p)

Then the Haar measure w(p) dp satisfies
w(p) dp = w(p') dp'

to within overall scaling. The overall "count" of elements is an integral:
W = integral of w(p) dp

If W is finite, then the group is "compact", and some properties of finite groups carry over to compact ones.


I will now consider 2D rotation and reflection groups. Their elements are
R(a,s) = {{cos(a), -s*sin(a)}, {sin(a), s*cos(a)}}
where s = +1 (rotation) or -1 (reflection)

The angle a varies in [0,2pi), and the Haar measure is integral weight w(a) = 1

The pure-rotation irreps are
D(n,a) = exp(i*n*a)
for all integers n. This is an infinite number of them, though a countably infinite number, a typical feature of compact infinite groups.

The rotation-reflection irreps are
D0(a,s) = 1
D1(a,s) = s
D(n,a,s) = R(n*a,s) for positive-integer n

The characters of the last one are
X(n,a,+) = 2*cos(n*a)
X(n,a,-) = 0

 

[lpetrich]

There is a hyperbolic or Lorentz-boost version of the 2D rotation group. The rotation-reflection matrices are
R(a,s1,s2) = {{s1*cosh(a), s2*sinh(a)}, {s1*sinh(a), s2*cosh(a)}}

where both s1 and s2 are +1 or -1, and its Haar-measure weight is w(a) = 1.

Pure rotation is easy. Its irreps D(q,a) = exp(q*a) for arbitrary real q, thus giving uncountably many irreps.

While the ordinary rotation-reflection group has 2 disconnected continuous parts, this group has 4 such parts.

It has irreps
D00(a,s1,s2) = 1
D01(a,s1,s2) = s2
D10(a,s1,s2) = s1
D11(a,s1,s2) = s1*s2
D1(q,a,s1,s2) = R(q*a,s1,s2)
D2(q,a,s1,s2) = s1*s2*R(q*a,s1,s2)

with characters
X1,2(q,a,+,+) = 2*cosh(q*a)
X1,2(q,a,+,-) = 0
X1,2(q,a,-,+) = 0
X1(q,a,-,-) = -2*cosh(q*a)
X2(q,a,-,-) = 2*cosh(q*a)

The parameter q is a positive real number, thus also giving uncountably many irreps.

Neither this pure-rotation group or this rotation-reflection one is compact, as one might expect.

Having four parts is shared by the Lorentz group of space-time rotations and boosts. Its four parts correspond to the identity, space reflection (parity), time reflection, and both space and time reflection. It's a consequence of time having a different kind of direction than space. For time difference t and space differences x1, x2, and x3, the space-time distance squared is
S = - t^2 + x1^2 + x2^2 + x3^2
If S > 0, then the interval is spacelike, with length sqrt(S)
If S = 0, then the interval is null
If S < 0, then the interval is timelike, with time sqrt(-S) with the sign of t

We can express a space-time interval as a four-vector: x = (t, x1, x2, x3) and S as a vector-matrix-vector product:
S = x.g.x

with "metric tensor" g = diagonal(-1,1,1,1)

A rotation-reflection matrix R does x' = R.x, and thus it must satisfy R^T.g.R = g. That is rather complicated in four dimensions, but in two dimensions, g = diagonal(-1,1), and one gets the hyperbolic 2D rotation-reflection group of earlier in this post.

 

[lpetrich]

Going to three dimensions, we use the simplification that (3D reflection) = - (3D rotation). So once one finds the 3D rotations, one's work is done.

To find the 3D rotation group's irreps, it is easiest to start from the unit quaternions. Using angles a, ap, and az,
scalar part = cos(a)
vector part = sin(a)*{sin(ap)*cos(az), sin(ap)*sin(az), cos(ap)}

The Haar measure becomes
sin(a)^2 * sin(ap) * da * d(ap) * d(az)

Orthonormality for irrep characters is given by
integral of X(x,a) * X(y,a)^* dm(a) = δ(x,y) * integral dm(a)
with Haar measure dm(a)

The irreps themselves are rather complicated to construct, but their characters are rather simple:
X(n,a) = sin((n+1)*a)/sin(a)

with direction angles ap and az dropping out. The identity quaternion has a = 0, and thus, X(n,e) = (n+1).
n = 0: identity rep
n = 1: unit quaternions
n = 2: 3D rotations: sort of square of quaternions
Greater n's: sort of nth power of quaternions


This is part of the quantum-mechanical theory of angular momentum, where n = 2j, for angular momentum j. Physicist Wolfgang Pauli had reinvented quaternions when he developed his Pauli matrices for describing the angular momentum of a spin-1/2 particle like an electron.

 

[lpetrich]

One can continue with four dimensions, but the rotation-reflection group there is rather gruesomely complicated -- it must be constructed from a pair of quaternions. For more than four dimensions, it is even worse.

Now for some notation. The n-dimensional rotation-reflection group is called O, and its pure-rotation subgroup SO. If it preserves a metric tensor with n1 + signs and n2 - signs, then those groups are O(n1,n2) and SO(n1,n2). The hyperbolic 2D rotation group is O(1,1) and its pure-rotation subgroup SO(1,1). The Lorentz space-time symmetry group is O(3,1) with space-time reflections and SO(3,1) with rotations and boosts only, though they may be combined.

If instead of orthogonal matrices, the matrices are "unitary", we get group U with subgroup SU for determinant 1.
Unitary: inverse = Hermitian conjugate
Hermitian conjugate: transpose + complex conjugate
A Hermitian matrix is equal to its Hermitian conjugate.

The unit-quaternion group = SU(2).

One can use a metric with the unitary-group matrices: R⁺.g.R = g where the superscript + means herm. conj. This gives us U(n1,n2) and SU(n1,n2).

U and SU are related to general linear matrices GL(n,R) and SL(n,R) by analytic continuation. This also relates SO and SO(n1,n2), and (S)U and (S)U(n1,n2).

One can use an antisymmetric metric: g = {{0, -I},{I, 0}}. That gives us the "symplectic" groups, Sp(2n).

 

[lpetrich]

Rotation groups and their relatives become very difficult to work with very fast as one increases their dimension, but there is a shortcut: using their Lie algebras ("Lee") instead. A Lie-group element R can be expressed in terms of its algebra element L:
R = exp(L)

This element is a combination of the algebra's basis vectors L_i:
L(c) = sum over i of c_i L_i
or simply
L(c) = c_i L_i
assuming summation over repeated indices, a common convention.

Lie algebras are closed under commutation: [L1,L2] = L3, also in the algebra. Though they are not associative, they satisfy another identity in its place, the "Jacobi identity":
[[L1,L2],L3] + [[L2,L3],L1] + [[L3,L1],L2] = 0

For basis elements L_i, [L_i,L_j] = f_ij^k * L_k
where the f's are the algebra's structure constants. The Jacobi identity becomes
f_ij^a*f_ak^l + f_jk^a*f_ai^l + f_ki^a*f_aj^l= 0

Lie algebras have counterparts of several features of groups.

Like groups, some algebras are product algebras. They can be sorted out into two or more sets of basis elements, with each set commuting with each other set.

Lie algebras have a counterpart of normal subgroups: ideals. An ideal is a subalgebra M with this commutation with the original algebra L:
[L,M] = M

The group of exp(elements of M) is a normal subgroup of the group of exp(elements of L).

Every algebra has two trivial ideals: the empty algebra and the original algebra.

Composition series also carry over into Lie algebras, though instead of the identity group as a possible end, they have the empty algebra.

Derived series: L1 = [L,L], L2 = [L1,L1], ... -- if it ends in the empty algebra, then L is solvable
Lower central series: L1 = [L,L], L2 = [L,L1], ... -- if it ends in the empty algebra, then L is nilpotent

If an algebra is not a product algebra and if it contains no nontrivial ideals, then it is "simple". Like a simple group containing no normal subgroups. A "semisimple" one is a product of simple ones.

 

[lpetrich]

The next question is what Lie algebras there are. Like with groups, this is a problem that has only been partially solved. But as with groups, all the finite simple Lie algebras are known, finite meaning having a finite-sized basis space of algebra "generators". They come in four infinite families with five additional "exceptional" algebras. Here they are with how many generators and the sizes of some special representations of them.

• A - SU(n+1) - n*(n+2) - fundamental: two of (n+1)
• B - SO(2n+1) - n*(2n+1) - vector: (2n+1) spinor: 2^n
• C - Sp(2n) - n*(2n+1) - fundamental: 2n
• D - SO(2n) - n*(2n-1) - vector: 2n spinor: two of 2^(n-1)
• G2 - 14 - fundamental: 7
• F4 - 52 - fundamental: 26
• E6 - 78 - fundamental: two of 27
• E7 - 133 - fundamental: 56
• E8 - 248 - also fundamental

"Fundamental" means an irrep that all others can be built out of with product irreps. "Vector" is for doing rotation groups, and "spinor" is a generalization of the spin-1/2 case for 3D rotations.

There is a special representation that is built from the algebra generators themselves, using them as a basis set. That is the "adjoint representation", and it has the number of generators as its number of dimensions. The algebra E8 is unique in having its adjoint rep be its fundamental rep.

Construction of representations of Lie algebras is a rather complicated procedure, even if one restricts oneself to the reps' basis sets. But if you have ever worked through quantum-mechanical angular momentum, you have constructed the basis sets of reps of SO(3). I myself have written software for doing so, software in My Science and Math Stuff ("Semisimple Lie Algebras").


The smaller Lie algebras have some interrelationships:
SO(2) ~ U(1)
SO(3) ~ SU(2) ~ Sp(2)
SO(4) ~ SO(3) * SO(3)
SO(5) ~ Sp(4)
SO(6) ~ SU(4)

The E series of algebras can be extended downward in this fashion:
E5 ~ SO(10)
E4 ~ SU(5)
E3 ~ SU(3) * SU(2)

There is something very odd about this. The Standard Model of particle physics has a "gauge symmetry" that is SU(3) * SU(2) * U(1). E3 is most of this. Some proposed Grand Unified Theories have symmetries SU(5): E4, SO(10): E5, E6, and E8. What would make our Universe have the E series of gauge-symmetry groups?

 

[lpetrich]

Here is an infinite Lie algebra, the Witt algebra. Its generators are L_n for integer n, and its commutation is
[L_n,L_m] = (n - m) * L_n+m


I have been discussing rotational symmetry and its generalizations, but what about translational symmetry? How might it interact with rotations? Let us consider them together, with translation (shift in position) D and rotation-reflection R:

x' = R.x + D

That can be interpreted as a matrix with form {{R, D}, {0, 1}}, and it is easy to show that all the group properties hold. The translations for the identity rotation form a normal subgroup, with the rotation-reflection part its quotient group.

Rotation-reflection-translation groups are often called space groups for short, and rotation-reflection ones point groups.

The r-r-t group with ordinary r-r is called the Euclidean group, from it being the symmetries of the kind of space described by Euclidean geometry, flat space. For n dimensions, it may be called Euc, though I've seen E for it.

Euc has normal subgroup (translation)^n with quotient group O

For a distance metric with n1 positive signs and n2 negative signs, the r-r part is modified accordingly, and the group may be called Euc(n1,n2).

Euc(n1,n2) has normal subgroup (translation)^n with quotient group O(n1,n2)

Flat spacetime has symmetry Euc(3,1), the Poincaré group. Its r-r symmetry group is, as I'd mentioned, O(3,1), the Lorentz group.


One can go from group to Lie algebra for the Euclidean group, and one finds commutation that can be summarized as
R = rotation-group generators
T = translation-group generators
[R,R] = R
[R,T] = T

Thus, translations are an ideal in this algebra, corresponding to being a normal subgroup in the group.

 

[lpetrich]

For translation over all the dimensions in a space, the r-r part is not constrained by the translations. But that is not the case for subsets of translations, like translations in fewer dimensions. In that case the r-r part is the product (r-r for the translations) * (r-r for the non-translated parts) or any of its subgroups.

For 2D space, let us consider translational symmetry in only one direction, thus making a line group. The only nontrivial rotations or reflections that do not change the direction of this line are (parallel reflection), (perpendicular reflection), and (180d rotation). However, the third one is the product of the first two, so the total group is a product of the parallel-reflection group and the perpendicular-reflection one. So
D2(para/perp) = D1(para) * D1(perp)


Going from continuous to discrete spaces, we get lattices of points. These are important not only in artistry, where one often has repeating or semi-repeating patterns, but also in crystallography, because crystals' molecules are in repeating patterns.

Points in a lattice are specified as
x(k1,k2,...) = k1*e1 + k2*e2 + ...

multiples of vectors e1, e2, ... for each of the lattice directions. For 1D, it is plain old integers, while for 2D, there are several types of lattices.

The most general one is the parallelogram. It has possible symmetries C1, C2 (180d rotation).

It can be specialized to a rectangle, giving possible symmetries C1, C2, D1, D2 (along each side)

It can also be specialized to a rhombus, giving possible symmetries C1, C2, D1, D2 (along each diagonal)

Both of these two can be specialized to a square, giving possible symmetries C1, C2, D1, D2, C4, D4

The rhombus can be specialized to a pair of equilateral triangles, giving a triangular or hexagonal grid. It has possible symmetries C1, C2, D1, D2, C3, D3, C6, D6

Note the lack of pentagonal symmetry. Also note that one can get a rhombic grid by taking a rectangular grid and putting points in the centers of the rectangles.

Though these lattices are all full-2D lattices, the possible r-r symmetry groups are very limited: C1, C2, C3, C4, C6, and D1, D2, D3, D4, D6. This is a result of the "crystallographic restriction theorem", a theorem that states that symmetry-group rotations may only be 0d, 60d, 90d, 120d, or 180d.


For 3D, the lattices are similar to the 2D ones, though more complicated. By crystallographic restriction r-r groups are limited to these 32 groups:
C1, C2, C3, C4, C6
C1h, C2h, C3h, C4h, C6h
S2, S4, S6
C1v=C1h, C2v, C3v, C4v, C6v
D1=C2, D2, D3, D4, D6
D1h=C2v, D2h, D3h, D4h, D6h
D1d=C2h, D2d, D3d
T, Th, Td, O, Oh

Note the lack of pentagonal or icosahedral symmetry.

 

[lpetrich]

Now some specific lattice groups.

For one dimension, the possible group elements are very simple. For coordinate x,
(+): x' = x + n for integer n
(-): x' = - x + n for integer n
The two groups:
p = {+}
pm = {+,-}
I'm using something called Hermann-Mauguin notation here.

For two dimensions, I will first do a one-dimensional lattice, giving the seven frieze groups.

For x along the line and y perpendicular to it, their possible elements are
x' = sx*x + n + a/2, y = sy*y
where sx and sy are both +-1 and a is 0 or 1. The possible elements:

++0:
x' = x + n, y' = y

-+0: parallel reflection, reflection line perpendicular
x' = -x + n, y' = y

+-0: perpendicular reflection, reflection line along lattice line
x' = x + n, y' = -y

+-1: like previous, but shifted along lattice line ("glide")
x' = x + n + 1/2, y' = -y

--0: both reflections: 180d rotation
x' = -x + n, y' = -y

--1: like previous, but with a glide
x' = -x + n + 1/2, y' = -y

The seven frieze groups correspond to the seven infinite families of axial rotation-reflection groups. They correspond by being some number of lattice repeats around the group axis. Here are the groups, with Hermann-Mauguin labels, Schoenflies labels for 3D axial r-r groups with n repeats, 2D r-r group label, group elements, and ASCII-art depictions

p1 C(n) C1 ++0
b b b b

p11m C(n,h) D1 ++0 +-0
b b b b
p p p p

p11g S(2n) D1 ++0 +-1
b b b b
 p p p p

p1m1 C(n,v) D1 ++0 -+0
bdbdbdbd

p2 D(n) C2 ++0 --0
b b b b
 q q q q

p2mm D(n,h) D2 ++0 -+0 +-0 --0
bdbdbdbd
pqpqpqpq

p2mg D(n,d) D2 ++0 -+0 +-1 --1
bdbdbdbd
qpqpqpqp

 

[lpetrich]

For a full-2D lattice, the groups are the seventeen wallpaper groups.

Some of them also contain glide reflections, reflections with translation along the line of reflection. That's the "g" in the groups' names, as opposed to plain-reflection "m". Here are abbreviated Hermann-Mauguin labels, the lattice type, and the associated 2D r-r groups, along with ASCII-art depictions of some of them:

p1 Para C1
b

p2 Para C2
bq

pm Rect D1
bd

pg Rect D1
bp

cm Rhomb D1
<bd>

pmm Rect D2
bd
pq

pmg Rect D2
bd
qp

pgg Rect D2
bp
dq

cmm Rhomb D2
/bd\
\pq/

p4 Sqr C4

p4m Sqr D4

p4g Sqr D4

p3 Hex C3

p3m1 Hex D3

p31m Hex D3

p6 Hex C6

p6m Hex D6

As with frieze groups wrapping to make 3D axial r-r groups, some of these groups wrap to make 3D line groups. The frieze groups themselves are 2D line groups.

Its 13 infinite families of groups are made by wrapping these wallpaper groups around some axis. Some of them are duplicated because their reflections are either parallel to the axis or perpendicular to it: p1, pm (para, perp), pg (para, perp), cm (para, perp), p2, pmm, pmg (para, perp), pgg, cmm

 

[lpetrich]

I have a page on Symmetries, a page that includes Frieze Groups, Wallpaper Groups, a 2D Point-Group Demo, an Organism-Symmetry Demo, and an Organism-Symmetry Gallery.

That gallery has lots of pictures of organisms and parts and products that exemplify various symmetries. Its table of contents:

1. One-Dimensional
   1. 1D point group: bilateral
   2. 1D space groups: line
   3. Helix
   4. Logarithmic spiral, cone
   5. Frieze
2. Two-Dimensional
   1. 2D point groups: rosette
   2. Discrete 2D space groups: wallpaper
3. Three-Dimensional
   1. 3D point groups: crystallographic
   2. Discrete 3D space groups: crystallographic
4. Fractal

 

[lpetrich]

Now to determining what groups there are.

It seems like a simple way is to find what operation tables are possible. But the combinatorics of doing so get very horrible very quickly. Without group-property constraints, an n-element group has n^{n^2} possible tables.

With the existence of inverses, one can go a long way. One gets "Latin squares", as they are called. They are square grids where all of some set of symbols is represented only once in each row and in each column. Here are some simple ones:

1

1 2
2 1

1 2 3
2 3 1
3 1 2

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

1 2 3 4
2 1 4 3
3 4 2 1
4 3 1 2

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1

(the last three are equivalent to within row and column rearrangements and relabeling)

Here is how inversion yields the Latin-square property, at least for finite groups. Consider a row element r and distinct column elements c1 and c2. Then table elements t1 = r.c1 and t2 = r.c2. One can get column elements from table elements with c1 = r^-1.t1 and c2 = r^-1.t2. If t1 = t2, then c1 = c2. But c1 != c2, and therefore t1 != t2. A similar proof establishes this result for columns.

But in practice, finding Latin squares gets very difficult very quickly, so one must use other techniques.


BTW, Latin squares got their name because mathematician Leonhard Euler used letters in them instead of numbers -- Roman-alphabet ones.

 

[lpetrich]

First, let us consider groups with prime order p. A non-identity element in it will generate a subgroup, a cyclic group of order n. From Lagrange's theorem, n must divide p, and for n > 1, that is only possible if n = p. Thus, every prime-order group is cyclic: Z(p).

Let us now consider the smallest possible nonabelian group. How big is it? Take two distinct non-identity elements a and b and find their products: a.b and b.a. By the premise, b.a != a.b. So the group must contain e, a, b, a.b, and b.a.

If a.b = e, then b = inv(a) and b.a = e also. If a.b = a, then b = e. If a.b = b, then a = e. Thus, e, a, b, a.b, and b.a are all distinct, giving the group an order that is at least 5. But the only order-5 group is the cyclic group Z5, so the smallest nonabelian group must have an order at least 6. In fact, the smallest nonabelian group has order 6.


Lagrange's theorem has the consequence that every element's order must evenly divide the group's order. An element's order is the smallest power of it that gives the identity. It has a partial converse, Cauchy's theorem, that states that for every prime factor of the group order, there is at least one element with that order.

Lagrange's theorem itself has a converse, that for every divisor of the group's order, there is a subgroup with that order. But that hypothesis has counterevidence, and the smallest source of counterevidence is the group Alt(4). It has subgroups with sizes 1, 2, 3, 4, and 12, but not 6.

Here is a proof.

An order-6 subgroup of Alt(4) will have index 2, and every index-2 subgroup is normal.

In every normal subgroup, every parent group's conjugacy class is either all-in or all-out. No halfway ones. So one can see if one can get 6 from adding some combination of the class sizes. Here goes:

It must have the identity in it, and the identity always has class size 1.

Adding the other class sizes gives 4 or 5, with 2 or 1 left to go. Thus, the class sizes won't fit, and Alt(4) has no order-6 subgroup.


A further consequence is that Alt(5) has no nontrivial normal subgroups. Its class sizes are 1, 15, 20, 12, and 12, and their combinations that include the identity are 1, 13, 16, 21, 25, 28, 33, 36, 40, 45, 48, 60. The only ones that evenly divide Alt(5)'s order, 60, are the trivial ones, 1 and 60 itself. Thus, this group is "simple".

This has the consequence that general quintic equations cannot be solved with radicals, nth roots.

 

[lpetrich]

Turning to the symmetric group Sym, the elements are every length-n permutation, and their classes are all sets of permutations that share the lengths of their cycles. Thus, for Sym(3), the class content is:

111 ... 123
12 ... 132 321 213
3 ... 231 312

For n_k permutations with length k, the size of the class is
\( N({n_k}) = \frac{n!}{\prod_k n_k! k^{n_k}} ,\ n = \sum_k n_k k \)

Every permutation can be constructed from some number of interchange permutations. If an even number, the permutation is even. If an odd number, the permutation is odd. Being even or odd is a permutation's parity. A cycle with length n needs (n-1) interchanges to construct it. Thus, the parity of a permutation is the number of even cycle lengths modulo 2 (0 = even, 1 = odd).

The alternating group Alt has only the even permutations in Sym. The Sym classes carry over into Alt, though those classes with all distinct odd cycle lengths get split into two equal-sized ones.

Thus, Alt(3) has separate classes for 123, 231, and 312.


The permutations have this operation table for their parities:
even odd
odd even

Also, for more than one symbol, the numbers of even and odd permutations are equal.

Thus, while Sym has n! elements, Alt has n!/2 elements for n > 1.

 

[lpetrich]

I'll work out the class content of the lowest-order symmetric and alternating groups. The classes will be labeled with the lengths of their cycles, and I will include their parity (even or odd), and how many of the group elements that they have. I will also mention what other designations the groups have.

Sym(1), Alt(1): Z1, identity group
1 e 1

Sym(2): Z2
11 e 1 ... 2 o 1

Alt(2): identity group
11 - 1

Sym(3): Dih(3)
111 e 1 ... 12 o 3 ... 3 e 2

Alt(3): Z3
111 - 1 ... 3 - 1 1

Sym(4): octahedral group
1111 e 1 ... 112 o 6 ... 22 e 3 ... 13 e 8 ... 4 e 6

Alt(4): tetrahedral group
1111 - 1 ... 22 - 3 ... 13 - 4 4

Sym(5)
11111 e 1 ... 1112 o 10 ... 122 e 15 ... 113 e 20 ... 23 o 20 ... 14 o 30 ... 5 e 24

Alt(5): icosahedral group
11111 - 1 ... 122 - 15 ... 113 - 20 ... 5 - 12 12

 

[lpetrich]

I will now get into p-groups, groups with prime-power order: order pⁿ for some prime p and positive integer n.

Its conjugacy classes' sizes are also powers of p, and we get an interesting result: its center is also a p-group. That is because the non-center classes have sizes at least p, and their total size is therefore a multiple of p. Since the group's order is also a multiple of p, the center's order must also be a multiple of p. Thus, the center of every p-group is some abelian p-group.

The order-p p-group is the cyclic group Z(p).

I will now consider groups with order p². There are two abelian ones, Z(p²) and Z(p)*Z(p). Are there any nonabelian ones? The group's center has a size at least p. So it contains Z(p): e, a, a², ..., a^p-1. Consider an element outside it, b. Its order must be p for the group to be nonabelian. The cosets of the "a group" are for each power of b separately, as can easily be shown. This means that the elements of the group all have the form a^k.b^l. Since a commutes with b and powers of b commute with each other, we conclude that all order-p² groups are abelian. However, some groups with higher powers of p are nonabelian.


If all non-identity elements of a group have order 2, then that group is abelian. Take two distinct elements a and b. From the problem statement: abab = e. Multiply on the right by b: aba = b. Multiply on the right by a: ab = ba. Thus, the group is abelian, and is (Z2)ⁿ.

 

[lpetrich]

For more general groups, p-groups are relevant in a way, as is evident from Sylow's theorems:

1. Every finite group whose order contains power n of prime p has a p-group subgroup with order pⁿ, a "Sylow p-subgroup".
2. All Sylow p-subgroups are conjugate. That is, related by (subgroup)' = g.(subgroup).g^-1 where g is some element of the parent group.
3. • The number of Sylow sp-ubgroups is 1 mod p.
   • That number evenly divides the order of the group.
   • That number equals (order of group) / (order of the "normalizer" of one of these subgroups) -- the normalizer is all the group elements for which a subset is self-conjugate. The "centralizer" is related but different: it is all the group elements that commute with that subset.

Now for an application of Sylow's theorems to groups whose order is a product of two distinct primes, p and q, with q > p. There is only one abelian group with that order, Z(p*q) = Z(p)*Z(q), and Sylow's theorems will tell us what nonabelian groups there are with that order.

For the Sylow q-subgroups, there are k*q+1 of them, and that is only possible if k = 0. That is, there is only one Sylow q-subgroup. For Sylow p-subgroups, there are two possibilities: k = 0 and k makes possible q = k*p+1. The first possibility leads to Z(p*q), while the second one leads to a nonabelian group.

For p = 2, q can be any odd prime, and we get Dih(q). For p = 3, the first one is q = 7 and the next ones are q = 13, 19, 31, 37, ... for p = 5, q = 11, 31, ..., for p = 7, q = 29, 43, ...

The q-group is divided up into the identity class and k classes that each have p elements. The p-groups have the identity class and each other element in a class that spans all the p-groups. That is, one element from each of the q p-groups, making q in all.

For a generating one of the p-groups and b generating the q-group, we have a.b = b^r.a, where r^p = 1 mod q.

r = 1 is the abelian case.

For p = 2, r can also equal q-1, making the dihedral groups.

In general, the conjugacy classes are:

• The identity class
• For each k from 1 to p-1, a^k.b^m for m = 0 to q-1 (the "a classes")
• For each m from 1 to q-1, b^{m*r^k} for k = 0 to p-1, to within multiple counting of the classes (the "b classes")

For the dihedral case, there is only one a class, {a, a.b, a.b², ..., a.b^q-1}, and the b classes are {b^m, b^q-m} for m = 1 to (q-1)/2.

For p = 3 and q = 7, the b classes are {b, b², b⁴}, {b³, b⁵, b⁶}