There are various overused terms in mathematics. “Normal” is one of them. Perhaps the four commonest uses are the following:
- A complex square matrix is normal if it commutes with its conjugate transpose. Normal matrices are precisely the ones which can be diagonalised by a unitary matrix (that is, have an orthonormal basis of eigenvectors).
- A topological space is normal if two disjoint closed sets have disjoint open neighbourhoods.
- A field extension L/K is normal if every polynomial over K which has a linear factor over L splits completely into linear factors over L.
- A subgroup H of a group G is normal in G if it is mapped to itself by conjugation by elements of G; equivalently, its left and right cosets coincide.
Most of these uses seem completely unconnected. But the use of the same term for the last two is not coincidence, but comes from Galois theory. If L is a Galois extension of a base field E, and K an intermediate field, then L/K is a normal extension if and only if the Galois group of L over K is a normal subgroup of its Galois group over E. (If this happens, the Galois group of K over E is the quotient group.)
But this also hides some mystery. The most important property of normal subgroups is that they are kernels of homomorphisms (and conversely). But step outside group theory, to semigroup theory or universal algebra, and you learn that the kernel of a homomorphism is a partition, not a subalgebra: two elements are in the same part if they have the same image under the homomorphism. It just happens that, in groups, the kernel partition of a homomorphism is precisely the partition into cosets (left or right, it doesn’t matter) of the kernel subgroup.
Indeed, in German, one talks of a “normal divisor” rather than “normal subgroup”, which presumably arises from this interpretation as partition (but I am guessing, I don’t know the etymology).
You can see kernels of homomorphisms in the Galois connection. If L/K is a normal extension, with L Galois over the subfield E, then any E-automorphism of L fixes K setwise, and so induces an E automorphism of K. So we have a homomorphism from Gal(L/E) (the group of E-automorphisms of L) to Gal(K/E). The kernel of this homomorphism consists of the automorphisms which act trivially on K; these are the K-automorphisms of L, the elements of Gal(L/K). [An E-automorphism of L is a field automorphism of L fixing E elementwise.]
In group theory, the term “normal” could be, and sometimes is, replaced by “invariant”. An invariant subgroup is one mapped to itself by all conjugations; this fits in with the notion of fully invariant subgroup, mapped to itself by all endomorphisms. Indeed, for the notion that most people call “subnormal subgroup” (a term in a series of subgroups, each normal in the next, with top element the whole group) was called by Marshall Hall a “subinvariant subgroup”; he remarked in a footnote that he found the term subnormal “unnecessarily distracting”. [Footnote on p.124 of his book The Theory of Groups, published in 1959. He says “The more colorful term subnormal series has been urged on the writer by Irving Kaplansky”, suggesting that it wasn’t yet in common use in 1959.]
All well and good, if a little confusing so far; the first three uses mentioned above are so well separated that probably mathematical papers using each of them form disjoint open neighbourhoods.
But when we come to Cayley graphs, there is real confusion.
Let G be a group, and S an inverse-closed subset of G not containing the identity. The Cayley graph Cay(G,S) is the graph with vertex set G, in which two elements g and h are joined if and only if hg−1∈S. The fact that S is inverse-closed makes the graph undirected, and the fact that it doesn’t contain the identity makes the graph loopless. The group G acts on itself by right multiplication; this action embeds G into the automorphism group of the Cayley graph.
Now each of the following two definitions occurs in the literature:
- The Cayley graph Cay(G,S) is normal if the set S is closed under conjugation in G; equivalently, the action of G by left multiplication is also contained in the automorphism group of the Cayley graph.
- The Cayley graph Cay(G,S) is normal if G (embedded by the right action as before) is a normal subgroup of the automorphism group of the graph.
These two definitions are quite different. Indeed, the second one restricts the symmetry of the graph (its automorphisms are all contained in the normaliser of G in the symmetric group), while the second expands it (the left, as well as the right, action of G consists of automorphisms).
The complete graph on G is a Cayley graph for any group G; it is normal in the first sense but not the second (if the order of G is greater than 4). On the other hand, the Cayley graph of S3 with respect to two of its transpositions is a 6-cycle, and its automorphism group contains S3 as a (normal) subgroup of index 2; so it is normal in the second sense but not the first (since the three transpositions are conjugate).
Both terms, as I said, are well-established, and it is probably too late to change the terminology now.
This was on my mind because of recent events. The argument about synchronization for groups with regular subgroups mentioned in the last-but-one post depends on a relevant graph being a normal Cayley graph (in the first sense); but I learned about the result of Cai and Zhang at the conference in Shenzhen, which also had a talk about normal Cayley graphs (in the second sense).
Philosophers of mathematics argue about whether mathematics is discovered or invented. In the book of Genesis we read that God created the animals but Adam gave them their names. I think what the examples above show is that, whether mathematics is discovered or invented, the names we give to the concepts are our own invention.