In Lecture 2, we established the following unique factorization result for the symmetric group
Theorem 1 (Jucys): Every permutation admits a unique factorization
into transpositions , such that
Moreover, the number of factors in this decomposition is
We now consider some algebraic ramifications of Jucys’ result. Let denote the group algebra of the symmetric group. As you know from Math 202B, this is the -dimensional Hilbert space in which sits as an orthonormal basis, and which supports the bilinear product inherited from the group law on . In fact, is a -algebra, with antilinear involution given by All of this is true for arbitrary groups, and indeed you can view as a functor from the category of groups to the category of unital associative -algebras which transports each group to its corresponding group algebra
Any subset of may be identified with a vector in simply by identifying it with the sum of its elements, and any family of disjoint subsets of is linearly independent, since any two of its members are orthogonal in In particular, for each we may view the corresponding conjugacy class as an element of , the sum of all permutations of cycle type and consider the linearly independent set in the group algebra,
Let denote the subspace of spanned by the conjugacy classes, the dimension of which is the number of partitions of . Given , we have
Th number in fact depends only on the conjugacy class of , for if then for any Thus is a subalgebra of called the class algebra, which is a particularly appropriate name for something encountered in an algebra class. We thus have
The numbers are called the connection coefficients (aka structure constants) of the class algebra ; they are the entries of the multiplication table for conjugacy classes. More generally, we can take arbitrary polynomials in conjugacy classes, and write them as linear combinations of conjugacy classes, and this often has enumerative meaning. For example, consider the class of transpositions. For any , we have
and each term in the sum corresponds uniquely to an -step walk on the Cayley graph of beginning at Thus,
which says that the combinatorial problem of counting -step walks on the graph from the identity permutation to a permutation of cycle type is the same thing as the algebraic problem of resolving into a linear combination of conjugacy classes.
For any , we have
where both sums are over , and the two sums are in fact the same since Thus, the class algebra is a subalgebra of the center of the group algebra. Conversely, if is a central element, then whence is a linear combination of conjugacy classes, and we conclude that the class algebra coincides with the center of the group algebra Again, all of the above is true for any group, and you can view as a functor from groups to commutative, unital -algebras which transports each group to its class algebra
In addition to the conjugacy class themselves, the levels of the Cayley graph of belong to the class algebra, and are -linear combinations of conjugacy classes,
Lifted to the group algebra, Theorem 1 says that these central elements are given by the sums
where is the set of functions from to Equivalently, we have
where are the sums
Note that is an empty sum, hence equal to the zero element in A nice way to picture these sums is to take the conjugacy class of transpositions and view it as the strictly upper triangular matrix over whose entry in row and column is the transposition whenever and when not. Then is simply the th column sum of the matrix . For example, in the case we have
The transpositions sums are known as the Young-Jucys-Murphy elements of the group algebra Note that the YJM elements are non-central, since they correspond to proper subsets of a conjugacy class (namely, the class ), and therefore cannot be expressed as linear combinations of conjugacy classes. Nevertheless, we have the following.
Proposition 2: The YJM elements commute with one another.
Proof: Problem set 2.
In view of the commutativity of the elements , we may equivalently write Theorem 1 as
which says that is the sum of all squarefree monomials of degree in the commuting elements . But this is a polynomial you know from Math 202B: it is the elementary symmetric polynomial of degree in variables. In particular, Theorem 1 is equivalent to the following polynomial identity in the class algebra .
As you know from Math 202B, the elementary symmetric polynomials are important because they express the coefficients of a polynomial as functions of its roots (the inverse problem, expressing the roots as functions of the coefficients, is harder). Thus Theorem 2 is equivalent to the following factorization in the class algebra.
Theorem 3: For any , we have
In addition to being a direct incarnation of the relationship between the roots of a polynomial and its coefficients, there is another reason why the elementary symmetric polynomials are deserving of their name. Let be commuting indeterminates, and consider the corresponding polynomial algebra As you know from Math 202B, polynomials satisfying
are called symmetric polynomials, and their totality forms a subalgebra of denoted This subalgebra is itself a polynomial algebra.
Theorem 3 (Newton): We have
Theorem 3 is often referred to as the fundamental theorem on symmetric polynomials. A proof is given in Professor Sam’s 202B notes (Theorem 3.3.4). Combining Theorem 3 with Theorem 2, we learn the following: even though the JM elements do not themselves belong to the class algebra , any symmetric function of them does.
Theorem 4: For any the group algebra element is central.
Theorem 4 is quite remarkable, and has many interesting consequences. Here is one. Suppose we weaken our definition of strictly monotone walks on the edge-labeled Cayley graph of the symmetric group to just plain monotone walks, meaning walks which have the feature that the labels of the edges they traverse form a weakly increasing sequence.
Theorem 5: The number depends only on the conjugacy class of .
Proof: The complete homogeneous symmetric polynomial of degree in commuting variables is the sum of all monomials of degree in these variables (hence the name “complete”). Equivalently,
Evaluating on the YJM elements, we obtain
which is precisely the sum of all weakly monotone walks on beginning at Thus,
But since is a symmetric polynomial, Theorem 4 guarantees that , so that we must have for all as claimed.
No direct combinatorial proof of Theorem 5 is known.
Exercise: In the symmetric group , write down all factorizations of the full cycle into three transpositions; identify the factorizations which are weakly monotone, and those which are strictly monotone. Repeat this procedure with the full cycle