More About Partitions
Recall that a partition is a sequence of weakly decreasing non-negative integers, where appending or dropping ending zeros gives us the same partition. A partition is usually represented graphically as a table of boxes or dots:
We will be using the left diagram – this is called the Young diagram of .
We will also use notations and write for the largest for which . If , we also say For example if , then:
- is a partition of 11, or .
Definition. If is a partition, its transpose is the partition obtained by flipping the Young diagram about the main diagonal.
We will be labeling variables with partitions so it helps to have an ordering on the set of all partitions of d. The lexicographical order (or dictionary order) on the set is given as follows: if and only if there is an such that
For example, the set of all partitions of 5 is ordered as follows:
(1, 1, 1, 1, 1) < (2, 1, 1, 1) < (2, 2, 1) < (3, 1, 1) < (3, 2) < (4, 1) < (5).
However, algorithmically it is easier to generate the set of partitions in the reverse lexicographical order, so in labeling we will use that instead.
Dominance Ordering of Partitions
Now, the lexicographical ordering is total (i.e. any two partitions can be compared), but the problem is that taking the transpose does not give us any discernible result. E.g. for partitions of 6, we have:
- (2,2,1,1) < (2,2,2) and taking the transpose gives (4,2) > (3,3).
- (2,2,2) < (3,1,1,1) but taking the transpose gives (3,3) < (4,1,1).
Thus, we consider the following partial ordering instead.
Definition. Given partitions of d, we write if for each i we have
Although the definition makes sense for any two partitions, in practice we only use them to compare cases where We have the following.
Proposition. For , we have if and only if
Suppose . We first claim that, for each , we have:
where is the largest value for which ; equivalently, is the largest value for which The claim can be readily seen from the diagram below:
Now Let . We have two cases.
- If , then this sum is at most since there are more non-negative terms in the sum.
- If , the sum is still at most since the excess terms are negative.
Hence which gives:
So ; replacing by their transposes we get the reverse implication. ♦
Thus, in our above example, and the transpose gives . On the other hand
Previously, we saw that the elementary symmetric polynomial can be expressed as:
In the case where , the monomial vanishes. Now, we write the above expression vectorially.
Lemma 1. For each partition , we have
We claim that the unique binary matrix is obtained from the Young diagram by replacing boxes (or dots) with 1’s. E.g. for and , the matrix must be:
Indeed, the first row must be filled with all 1’s since the number of columns is exactly Removing the first row and dropping trailing zeros in the number of remaining columns is exactly so the second row must be filled with all 1’s. And so on. ♦
Lemma 2. For any partitions of , if then
Suppose is a binary matrix whose row sums are and column sums are Erase the 0’s and replace the 1’s in the matrix by consecutive 1, 2, …, d, where E.g. if and , pick:
Left-justify the resulting matrix to obtain a matrix. Similarly, top-justify it to obtain another matrix:
Note that and have shapes and respectively, i.e. there are terms in row i of and terms in row i of By construction, if an element occurs in row i of then it must occur in row i or above in Thus, the number of elements in rows 1-k of is at most the number of elements in rows 1-k of and we have:
as desired. ♦
Elementary Symmetric Polynomials as Basis
Now let be the permutation matrix which switches with its transpose The prior two lemmas show that is upper-triangular, with all 1’s on the main diagonal. Hence is invertible over the integers, and so is .
Example: n=3, d=4.
Since we know that
gives a Z-basis of , we see that
gives a Z-basis as well, since J (taking transpose) gives a bijection between partitions
As a result:
Corollary. We have , where the RHS is a freely generated commutative ring. The isomorphism preserves the grading, where
Work out the matrices J and N for the cases of (n, d) = (4, 4), (3, 5), (4, 5), (5, 5).