When the label may be a matrix

The rung about the sign asks which functions from the permutations to a commutative group respect composition, and answers exactly two: the constant one, and the sign. Read as a result about permutations it is a dead end — one bit, and nothing else to find. Read as a result about the question, it is an invitation, because the restriction doing all the work is commutativity, and the most familiar things that fail to commute are matrices.

So let the label be a matrix. Send each permutation to an invertible matrix of some fixed size, so that composing permutations multiplies the matrices. There is one obvious such assignment — the permutation matrix itself — and the question is what else there is, and whether the answer is again a short list.

It is. It is a table with a few rows, it can be computed rather than looked up, and the sign is one of its rows.

What a matrix-valued label is #

A representation of a group is a rule sending each element to an invertible matrix of a fixed size, such that the matrix of a composition is the product of the matrices. For permutations the size is the representation’s dimension, and a one-dimensional representation is a number that multiplies correctly — which is exactly the object the rung below characterised.

Two representations that differ by a change of basis are the same representation wearing different coordinates, so the objects being classified are representations up to a change of basis. That is a nuisance if one plans to compare matrices and a relief if one does not, because the same map in a better basis has different entries and the same trace.

The trace is the whole of what a change of basis leaves alone, and it is enough. Attach to a representation the function sending each group element to the trace of its matrix, and call that function the representation’s character. Two representations are the same up to a change of basis exactly when their characters agree — which is a theorem, not a definition, and it is the reason a table of numbers can stand in for a collection of matrix families.

A character is constant on conjugacy classes, because conjugate elements have conjugate matrices and conjugate matrices have equal traces. So a character has one value per class rather than one per element, and the table has as many columns as there are cycle shapes.

The representations, built rather than named #

Four of the five rows above come from objects already on this ladder, and the fifth from an operation on one of them.

The trivial representation sends everything to the number one. The sign sends each permutation to $+1$ or $-1$ according to its crossing parity. Both are one-dimensional and both are labels into a commutative target, so the rung below already found them and proved there are no others of that width.

The permutation matrix is the obvious representation: put a one in row $i$, column $j$ when the permutation sends $j$ to $i$. Its trace is the number of places left alone. It is not irreducible, though — the vector with every entry one is fixed by every permutation matrix, so the representation contains a copy of the trivial one and splits. Removing that copy leaves the standard representation, of dimension one less than the number of places, whose character is the number of fixed points minus one.

Multiplying the standard character by the sign gives a fourth. And the fifth comes from an operation on matrices rather than on permutations: the second exterior power, whose character at $g$ is $(\chi(g)^2 - \chi(g^2))/2$, a formula about matrices applied to a character already computed.

Every entry in the table was produced that way. Nothing was read off a reference and then drawn, which matters here more than usual, because a character table is exactly the kind of object that is easy to copy and impossible to check by eye.

One row, read slowly #

The standard representation is worth following in full, because it is the one row of the table that is a picture rather than a formula.

Take the four coordinates of space and let a permutation move them about. That is the permutation matrix, four by four. The vector $(1, 1, 1, 1)$ never moves, so the whole of the line through it is fixed — and everything perpendicular to that line is carried to itself as well, because a permutation matrix preserves the sum of the coordinates and therefore the set of vectors whose coordinates sum to zero.

So the four-dimensional space splits into a line and a three-dimensional slab, and each permutation acts on both. On the line it does nothing, which is the trivial representation. On the slab it acts as the standard representation, and the slab is a familiar object: the four points at distance one from the origin along the four axes, projected into it, are the vertices of a regular tetrahedron, and the permutations of four places are exactly its rotations and reflections.

The trace works out without any matrix being written. The permutation matrix’s trace is the number of places left alone, since a one sits on the diagonal exactly at a fixed place. The line contributes one to that. So the slab contributes the number of fixed places minus one, which is the standard character, and it can be read off a cycle shape by inspection: three, one, minus one, zero, minus one, down the row.

Every other row of the table except the trivial one is built out of that one by multiplication and by an operation on matrices, so the tetrahedron is doing more of the work here than any other single object.

What makes the list stop #

The list is finite and closes at five for a reason that is checkable in the same breath as the table: a representation is irreducible — has no smaller one hiding inside it — exactly when its character has length one under the group’s own average.

Take two characters, multiply them pointwise, average over all twenty-four permutations. The result is one when the two are the same irreducible character and zero when they are different, and that single sentence is the orthogonality relation. It is the sharpest tool in the subject and it is entirely computational: the figures average over every element of the group, for all twenty-five pairs of rows, and the assertions inside them refuse to draw a table whose rows are not orthonormal.

So the construction above is not a hopeful list. It is a filter. Eight candidates are built, each is measured against itself, the ones of length other than one are discarded as reducible, and duplicates are removed by measuring candidates against each other. What survives is what the figure draws.

That identity — the squares of the dimensions adding to the size of the group — is the reason the filter can be trusted to have finished. Once the squares add up, there is no room for another row, and the search can stop without an argument that it has looked everywhere.

Where the sign went #

The rung below is now visible as one line of the table, and it is worth reading the two statements against each other because the second is strictly stronger and the first is not thereby made redundant.

That rung says: exactly two labels into a commutative group. This one says: exactly two rows of width one. They are the same statement, since a one-dimensional representation is a label into the non-zero numbers, which commute.

What the wider question buys is everything else in the table. The standard representation of dimension three is a genuine invariant of a permutation that the sign cannot see: it distinguishes the three-cycles from the double transpositions, which the sign calls both even. Its character takes four different values across the five classes, so a great deal more than a bit survives — provided one is willing to record it as a matrix rather than as a number.

The obstruction was never the permutations. It was the target.

As many rows as classes #

The table is square, and that is not an accident of four places.

There are as many irreducible representations as there are conjugacy classes, always, for any finite group. Here that is five and five; for five places it is seven and seven. The proof is that the characters form a basis of the functions constant on classes, and the count follows from a dimension count in that space.

What the theorem does not supply is a reason to pair a particular row with a particular column. The two sets have the same size and no natural bijection between them, and for most groups none is known. For the symmetric groups there is one, and it is the pleasant surprise of the subject: both the classes and the representations are indexed by the partitions of the number of places — the classes by cycle shape, obviously, and the representations by a construction that is not obvious at all. Four places has five partitions, five places has seven, and the counts in the two tables below are those numbers.

The pattern in the dimensions #

The two tables together show what a character table looks like as a group grows, and the shape is worth naming.

The one-dimensional rows stay at two, for the reason the rung below gives and for no other. Everything else grows, and it grows fast: three places has dimensions 1, 1 and 2; four places 1, 1, 2, 3, 3; five places 1, 1, 4, 4, 5, 5, 6.

The rows come in pairs, one being the other multiplied by the sign, except for the row that is its own partner. That pairing is the sign acting on the whole table rather than sitting inside it, and it is the last appearance on this ladder of the bit the first rung established: multiplying by the sign is an involution on the set of representations, and its fixed points are the self-paired rows.

Why the entries are whole numbers #

Every number in both tables is an integer, and that is a fact about permutations rather than about characters in general.

A character value is a sum of roots of unity — the eigenvalues of a matrix of finite order — so there is no reason to expect it to be rational, and for most groups it is not. The smallest group whose table needs irrational entries is the rotations of a regular pentagon, where the golden ratio appears; the alternating group on five places needs the same numbers.

For the symmetric groups the entries are always integers, and the reason is a statement about conjugacy: in a symmetric group, every element is conjugate to every power of itself that generates the same cyclic subgroup, because both have the same cycle shape and cycle shape is the whole of conjugacy there. That forces each character value to be fixed by the arithmetic symmetries that could otherwise move it, and a sum of roots of unity fixed by all of them is rational — and an algebraic integer that is rational is an integer.

So the integrality is the cycle-shape criterion again, one level up. The first rung on this ladder found that the sign is well defined because it depends only on the cycle shape; the classes are cycle shapes for the same reason; and here the same fact is what keeps an entire table inside the whole numbers. It is worth knowing that this is exceptional, because a reader who meets these tables first and other groups’ tables second will otherwise take a coincidence for a rule.

What the table is for #

A character table is not a curiosity, and the two uses worth naming are both about counting.

The first is the one Burnside’s counting already meets: the number of orbits of a group acting on a set is the average number of points each element fixes, which is the inner product of the permutation character with the trivial one. Written that way, the counting lemma is a single entry of a table, and the whole apparatus of orthogonality is available to compute variations of it that the lemma alone does not reach.

The second is that characters are the right notion of frequency for a group that does not commute. On the whole numbers modulo $n$, the one-dimensional characters are the powers of a root of unity and expanding a function in them is the Fourier transform. On a group that does not commute the one-dimensional characters are too few to expand anything — here there are two of them — and the irreducible characters are what replaces them. The orthogonality relation is the same relation that makes Fourier coefficients computable, and the sum-of-squares identity is the same completeness statement.

So the table is a Fourier basis, and the reason a permutation gives up only one bit to a commutative target is that a commutative target can only see two of its frequencies.

What the pictures cannot show #

The tables are computed for three, four and five places, which is where a figure can carry every entry. The general construction — one irreducible representation per partition, built from tableaux — is not drawn, and the pleasant coincidence that the two indexings agree is asserted rather than exhibited.

The orthogonality is checked over the group, which is a verification and not a proof. Nothing here derives the relation; the figures use it as a filter and confirm it on every pair of rows they draw, which is the honest thing a finite check can do.

And the representations themselves are absent. The figure draws characters, which are traces, and a trace is a shadow of a matrix family. Two representations with equal characters are equivalent, so nothing is lost in principle — but the objects that actually act, and the subspaces they act on, do not appear in any figure here.

Where the ladder goes next #

Named here as debts. The construction from partitions — Specht modules, and the rule that reads a representation’s dimension off a diagram — which is what makes the coincidence above a theorem rather than a numerical accident. And the branching rule, which says what happens to a representation when one place is forgotten, and which is the mechanism behind the whole subject’s inductive style.

Sideways, the bit this generalises is the sign, the uniqueness that pins it down is the rung below, the orbits a character counts are Burnside’s, and the invariance of the trace under a change of coordinates is what a better basis is for.

What is worth carrying away #

When a classification comes out small, check whether the smallness is a fact about the objects or about the question.

One bit is all a permutation gives to a commutative group, and the sentence is true and complete. It is also entirely about the target: widen it to matrices and the same permutations give up a table with seven rows and a dimension of six in it. Nothing about permutations changed between the two sentences.

The habit worth taking is to ask what a uniqueness theorem’s hypotheses are doing. A theorem that says there is only one such thing is often a theorem about the category the thing was required to live in, and moving the requirement is more productive than accepting the answer.

The corollary is about how to recognise the moment. The rung below proved its uniqueness by computing a commutator subgroup — that is, by measuring exactly how far the group is from commuting, and finding it far. A proof whose engine is the failure of a hypothesis is a proof advertising which hypothesis to drop.