Math laboratory
Character tables of S3, S4, D4 and Q8 from scratch
Builds S3, S4, D4 and Q8 explicitly, finds their conjugacy classes, and extracts the irreducible characters from permutation characters on cosets of cyclic subgroups by repeatedly subtracting components and testing <chi, chi> = 1. It checks that the number of irreducibles equals the number of classes, that squared degrees sum to |G|, and that D4 and Q8 share a table though they are not isomorphic.
Back to the labExact computation
"""Character tables of S3, S4, D4 and Q8 found from permutation characters.
Each group is built concretely (permutations, or 2 x 2 complex matrices for
the quaternion group Q8). We compute conjugacy classes by brute force and the
permutation characters of G acting on the cosets of each cyclic subgroup,
plus the trace of a natural matrix representation. Using the inner product
<a, b> = (1/|G|) sum_g a(g) b(g)^*, we strip off known irreducible components
and keep any remainder with <chi, chi> = 1 (an irreducible character, by the
orthogonality relations), also trying products of characters, until there are
as many irreducibles as classes. We then check sum of squares of degrees = |G|
and compare the tables of D4 and Q8. Exact rational arithmetic.
"""
from fractions import Fraction
from itertools import permutations
def compose(p, q):
"""Permutation composite p after q (tuples)."""
return tuple(p[i] for i in q)
def perm_group(gens):
"""Closure of a list of permutations under composition."""
elems = {tuple(range(len(gens[0])))}
frontier = list(elems)
while frontier:
new = []
for x in frontier:
for g in gens:
y = compose(g, x)
if y not in elems:
elems.add(y)
new.append(y)
frontier = new
return sorted(elems)
def matmul2(a, b):
"""Product of 2 x 2 complex matrices stored as 4-tuples."""
return (a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3],
a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3])
def quaternion_group():
"""Q8 as matrices generated by i = diag(i, -i) and j = [[0, 1], [-1, 0]]."""
gens = [(1j, 0, 0, -1j), (0, 1, -1, 0)]
elems = {(1, 0, 0, 1)}
frontier = list(elems)
while frontier:
new = [matmul2(g, x) for x in frontier for g in gens]
new = [y for y in new if y not in elems]
elems.update(new)
frontier = new
return sorted(elems, key=str)
class Group:
"""A finite group given by its elements and multiplication."""
def __init__(self, elems, mul):
self.elems, self.mul = list(elems), mul
self.one = next(e for e in self.elems
if all(mul(e, x) == x for x in self.elems))
self.inv = {x: next(y for y in self.elems if mul(x, y) == self.one)
for x in self.elems}
self.classes = []
seen = set()
for x in self.elems:
if x not in seen:
cls = {mul(mul(g, x), self.inv[g]) for g in self.elems}
seen |= cls
self.classes.append(sorted(cls, key=str))
self.classes.sort(key=lambda c: (self.order(c[0]), len(c)))
self.class_of = {x: i for i, c in enumerate(self.classes) for x in c}
def order(self, x):
"""Order of an element."""
k, y = 1, x
while y != self.one:
y, k = self.mul(y, x), k + 1
return k
def cyclic_subgroup(self, x):
"""The subgroup generated by x."""
out, y = [self.one], x
while y != self.one:
out.append(y)
y = self.mul(y, x)
return out
def coset_character(self, sub):
"""Permutation character of G acting on the left cosets of sub."""
cosets = {frozenset(self.mul(x, h) for h in sub) for x in self.elems}
return tuple(sum(1 for c in cosets
if frozenset(self.mul(cls[0], y) for y in c) == c)
for cls in self.classes)
def inner(self, a, b):
"""<a, b> = (1/|G|) sum over classes |C| a(C) b(C) (real characters)."""
total = sum(len(c) * a[i] * b[i] for i, c in enumerate(self.classes))
return Fraction(total, len(self.elems))
def irreducibles(group, candidates):
"""Irreducible characters extracted from candidates and their products."""
irr, pool = [], list(candidates)
while len(irr) < len(group.classes) and pool:
progress = False
for chi in pool + [tuple(a * b for a, b in zip(x, y))
for x in irr for y in pool]:
rest = list(chi)
for psi in irr:
m = group.inner(chi, psi)
rest = [r - m * p for r, p in zip(rest, psi)]
rest = tuple(int(r) for r in rest)
if any(rest) and group.inner(rest, rest) == 1:
if rest[0] < 0:
rest = tuple(-r for r in rest)
if rest not in irr:
irr.append(rest)
progress = True
if not progress:
break
return sorted(irr, key=lambda c: (c[0], [-v for v in c]))
def fs_indicator(group, chi):
"""Frobenius-Schur indicator (1/|G|) sum_g chi(g^2): +1 real,
-1 quaternionic, 0 not real-valued."""
total = sum(chi[group.class_of[group.mul(x, x)]] for x in group.elems)
return Fraction(total, len(group.elems))
def same_table(g, h, tg, th):
"""Equal character tables up to reordering rows and same-size columns."""
if sorted(len(c) for c in g.classes) != sorted(len(c) for c in h.classes):
return False
n = len(g.classes)
for perm in permutations(range(n)):
if all(len(g.classes[i]) == len(h.classes[perm[i]]) for i in range(n)):
rows = {tuple(row[perm[i]] for i in range(n)) for row in th}
if rows == set(tg):
return True
return False
def sign(p):
"""Sign of a permutation, by counting inversions."""
inv = sum(1 for i in range(len(p)) for j in range(i + 1, len(p))
if p[i] > p[j])
return -1 if inv % 2 else 1
def natural_characters(group, kind):
"""Sign and fixed-point characters of a permutation group, or the trace
of the defining 2 x 2 matrices of Q8."""
reps = [c[0] for c in group.classes]
if kind == "perm":
return [tuple(sign(x) for x in reps),
tuple(sum(1 for i, v in enumerate(x) if i == v) for x in reps)]
return [tuple(int((x[0] + x[3]).real) for x in reps)]
def build_groups():
"""The four groups, with the kind of their natural representation."""
return {"S3": (Group(perm_group([(1, 0, 2), (1, 2, 0)]), compose), "perm"),
"S4": (Group(perm_group([(1, 0, 2, 3), (1, 2, 3, 0)]), compose),
"perm"),
"D4": (Group(perm_group([(1, 2, 3, 0), (0, 3, 2, 1)]), compose),
"perm"),
"Q8": (Group(quaternion_group(), matmul2), "matrix")}
def character_table(group, kind):
"""Irreducible characters of the group, from coset and natural
characters."""
cands = [group.coset_character(group.elems)] # trivial character
cands += [group.coset_character(group.cyclic_subgroup(x))
for x in group.elems]
cands += natural_characters(group, kind)
return irreducibles(group, list(dict.fromkeys(cands)))
def main():
groups = {name: g for name, (g, _) in build_groups().items()}
kinds = {name: kind for name, (_, kind) in build_groups().items()}
tables = {}
for name, g in groups.items():
t = character_table(g, kinds[name])
tables[name] = t
sizes = [len(c) for c in g.classes]
degrees = [row[0] for row in t]
print(f"{name}: |G| = {len(g.elems)}, class sizes {sizes}, "
f"degrees {degrees}")
print(f" irreducibles = classes: {len(t) == len(sizes)}; "
f"sum of squares = |G|: {sum(d * d for d in degrees) == len(g.elems)}")
if name in ("S3", "S4", "Q8"):
for row in t:
print(" ", row)
d4, q8 = groups["D4"], groups["Q8"]
print("D4 and Q8 have the same character table:",
same_table(d4, q8, tables["D4"], tables["Q8"]))
inv_d4 = sum(1 for x in d4.elems if d4.order(x) == 2)
inv_q8 = sum(1 for x in q8.elems if q8.order(x) == 2)
print(f" but elements of order 2: D4 has {inv_d4}, Q8 has {inv_q8}")
two = {name: next(r for r in tables[name] if r[0] == 2) for name in tables
if name in ("D4", "Q8")}
print(" Frobenius-Schur indicator (1/|G|) sum chi(g^2) of the 2-dim "
"character:")
print(f" D4: {fs_indicator(d4, two['D4'])} (real), "
f"Q8: {fs_indicator(q8, two['Q8'])} (quaternionic)")
print()
print("Epistemic status: exact computations for four specific groups; "
"the extraction\nuses the orthogonality relations (proved in the "
"lesson) to certify each\ncharacter as irreducible. It does not "
"prove anything about other groups.")
if __name__ == "__main__":
main()Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.