INTERSECTION CARDINALITY MATRICES

AND REPRESENTATIONS OF S_{n}

Murray Gerstenhaber

April 30, 1998

Abstract. “Intersection Cardinality Matrices” (ICM’s) have rows and columns indexed by the k element subsets of an n element set (n and k fixed), and entries which are functions only of the cardinality of the intersection of the sets marking the row and column. These form a k + 1 dimensional commutative algebra, and those ICM’s whose entries are integers have integer eigenvalues. We reprove this theorem about ICM’s and compute their eigenvalues using the representation theory of the symmetric group in a way that generalizes to the quantized case.

Let U be a set of n elements and fix some integer k between 0 and n. A matrix with complex entries whose rows and columns are indexed by the k-element subsets S, T of U will be called an intersection cardinality matrix or ICM if its entry in the S, T place depends only on the cardinality of the intersection S ∩ T. These have dimensions \binom{n}{k} × \binom{n}{k} and are symmetric. The following is well-known and stated explicitly by, e.g., Knuth [K] and Lovász [L]; it can also be extracted from Stanley [Sy].

Theorem 1. ICM’s commute, are simultaneously diagonalizable, and form an algebra. In general they have k + 1 distinct eigenvalues whose multiplicities are 1, \binom{n}{1} − 1, \binom{n}{2} − \binom{n}{1}, …, \binom{n}{k} − \binom{n}{k−1}. If the entries of an ICM are integers, then so are all of its eigenvalues.

ICM’s without a name appear in an early work of Wilf, [Wf], who gave a remarkable formula for their determinants and first suggested a group-theoretic approach. Knuth calls them “combinatorial matrices”. Lovász seems to have been led to the result by problems in information theory, but related matrices also appear in deep purely algebraic situations, cf. Brown and Lorenz, [BL].

There are various combinatorial approaches to the proof of Theorem 1 including, e.g., use of the finite Radon transform. However, it also follows, as we show, from elementary facts (i.e.., not using characters) in the representation theory of the symmetric group, S_{n}. Using these we also compute the eigenvectors of ICM’s and obtain a simple expression for their eigenvalues, Theorem 2. Although not the quickest approach this has the advantage of being adaptable to the quantized case. The present paper was actually the first in a series of three, the second and third of which [G1, G2] exhibit the quantizations in the finite and infinite cases, respectively. The infinite case is particularly interesting since there the unquantized case behaves very differently from the finite one while the quantized case preserves all its essential

Typeset by AMS-TEX

properties. The fundamental issue of quantization is mentioned here briefly at the end. It gives the theorem a new level of significance. (For a beautiful exposition of group theory adapted to physics, cf. Sternberg, [Sg].)

Throughout G will be a finite group, k will be a commutative unital coefficient ring which later will simply be ℂ, and V, W, … will be k modules which later will be finite dimensional vector spaces over ℂ.

1. Some elementary facts about group representations. Suppose that k is a commutative unital ring and V is a k module. A representation of G on V or G module structure on V is a morphism ρ : G → GL(V), the group of invertible k linear maps from V to itself. This makes V into a module over the group algebra kG and conversely, so once the coefficient ring k is fixed the category of G modules can be identified with that of modules over the algebra kG. In this context, a module morphism f : V → W, i.e., a k linear map such that f(gv) = g(fv), all g ∈ G, v ∈ V, is frequently called an intertwining operator. (We have written simply gv for ρ(g)v.) Isomorphic representations are often called equivalent. Suppose now that A is an arbitrary k algebra and V an A module (hence in particular a k module) and W a submodule. A k module complement to W is a k submodule W′ such that W + W′ = V, W ∩ W′ = 0, so V ≅ W ⊕ W′ but only as k modules; A is separable over k if whenever W has a k module complement it has one which is an A submodule. (The condition of having a k module coplement is vacuous if k is a field.) A basic result of representation theory is Maschke’s^{1} Theorem: If the order of G is invertible in k then kG is separable. For proof, denote the order of G by #G and whenever we have a k module morphism f : U → V between two kG modules define f̄: U → V by f̄(u) = (1/#G) ∑_{g∈G} g^{−1}f(gu). It is easy to check that f̄ is now a G module morphism, that if f already was a G module morphism then f̄ = f, and that if ϕ is any G module morphism then \overline{ϕf} = ϕf̄ and similarly for fϕ. Now if W is a G submodule of a G module V amd W has a k module complement W′ then the canonical G module mapping ϕ : V → V/W carries W′ isomorphically as a k module onto V/W, so there is a k module monomorphism f : V/W → V carrying V/W onto W′. Then f̄(V/W) is the desired G module complement to W.

A simple or irreducible module is one with no proper submodules. For these there is the indispensable Schur’s^{2} Lemma: A morphism between simple modules is either an isomorphism or the zero morphism. It follows that if the coefficient ring k is an algebraically closed field then an endomorphism of a simple module is just a scalar multiple of the identity.

We will suppose henceforth that k is a field and modules will tacitly be finite dimensional over k. Suppose for the moment that k is a field and A an algebra over k. An A module V is semisimple or completely reducible if every A submodule W has a complementary A module W′ (generally not unique) such that V = W ⊕ W′; V can then be written as a direct sum of simple submodules, and conversely, such a direct sum is semisimple. Maschke’s Theorem implies that if the characteristic of k does not divide the order of G then every G module is completely reducible.^{3} The expression of a semisimple V as a direct sum of simple submodules is not unique whenever some simple direct summand appears more than once in the decomposition. A semisimple module is isotypical if all its simple submodules are isomorphic. A general semisimple module can always be written as a direct sum of isotypical modules by gathering together isomorphic simple summands; by Schur’s lemma, this coarser decomposition is unique. A semisimple module V is called multiplicity-free or is said to have simple spectrum if its simple summands all have multiplicity one, i.e., if its isotypical components are simple. In this case the full decomposition into simple summands is unique. Assuming V multiplicity free, let V = V_{1} ⊕ ⋯ ⊕ V_{r} be its decomposition into simple summands. Schur’s lemma then implies that any endomorphism f of V must carry each V_{i} into itself, and if k is algebraically closed that the restriction of f to V_{i} is just multiplication by a scalar λ_{i}. It follows that all endomorphisms of V commute, that each has no more than r distinct eigenvalues, and that some (and thus the ‘general’) endomorphism has exactly r distinct eigenvalues. If dim V_{i} = n_{i} and one takes a basis for V by combining bases for the various V_{i}, then the matrix of f will be diagonal, with diagonal entry λ_{1} repeated n_{1} times, λ_{2} repeated n_{2} times, etc.. ICM’s, as we shall see, are just endomorphisms of a particular S_{n} module with simple spectrum.

1One of Maschke’s students was L. E. Dickson, who trained A. A. Albert, who was the author’s thesis adviser.

2Issai Schur: b. Jan 10, 1875, Mogilev, driven from professorship in Berlin by the Nazis, escaped 1939 to Palestine, d. Jan. 10, 1941, Tel Aviv; Richard Brauer was one of his students.

Note that a module which is simple may become reducible when the coefficient field is extended unless the field is already algebraically closed. A remarkable property of the symmetric groups S_{n} (which we will not prove) is that this does not happen: Every irreducible representation V of S_{n} is ‘rational’ in the sense that we can always find a basis of V with respect to which the matrices representing the elements of S_{n} all have rational entries. See e.g., Hermann Weyl [W] (dedicated to the memory of Issai Schur), or the more reader-friendly text by Fulton and Harris [FH] which although assuming coefficients in ℂ actually operates over the rationals when dealing with the symmetric group.

The dual vector space V^{∗} of a G module becomes a G module by setting < gv^{∗}, v >=< v^{∗}, g^{−1}v >, where < v^{∗}, v > denotes the value of v^{∗} ∈ V^{∗} on v ∈ V. One makes the tensor product V ⊗ W of G modules into a G module by ‘diagonal operation’, i.e., by setting g(v ⊗ w) = gv ⊗ gw, and the space Hom_{ℂ}(V, W) of ℂ linear maps from f : V → W becomes a G module by setting (gf)(v) = g(f(g^{−1}v)). There is a natural vector space isomorphism V^{∗} ⊗ W → Hom_{ℂ}(V, W) in which an element of the form v^{∗} ⊗ w sends v ∈ V to < v∗, v > w ∈ W. One can check that this is a G module morphism. Notice that a linear map f : V → W is a G module morphism if and only if gf = f for all g, i.e., if f is fixed under the operation of G.

For simplicity, our coefficient field will henceforth be ℂ. A finite group G (more generally, any finite dimensional associative algebra) has only a finite number of inequivalent simple modules. For ℂG is a module over itself and as such decomposes, by Maschke’s Theorem, into a finite direct sum of simple modules. But it also has a morphism onto any simple G module V: if v is any non-zero element of V, extend linearly the map sending g ∈ G to gv.

3The classic proof of Maschke’s Theorem when k = ℂ constructs an invariant inner product in V and then takes the orthogonal complement to a submodule W. This fails in positive characteristics and obscures the real point of the theorem which is the construction of the separability idempotent, whose presence the sophisticated reader may recognize in the proof we have given.

In general, the dual of a G module V is not isomorphic to the original. For if we choose a basis {v_{i}} for V and take the dual basis {v_{i}^{∗}} for V^{∗}, then the matrix representing the operation of g on V^{∗} is the transpose inverse of the matrix of its operation on V; for the representations to be isomorphic there would have to be a single matrix which simultaneously conjugates all the matrices representing operations of G into their transpose inverses. Suppose, however, that N is a finite set on which G operates as a group of permutations and let V be the space ℂN of formal linear combinations ∑ c_{x}x of the elements x ∈ N with coefficients c_{x} ∈ ℂ. The operation of G on N makes this into a G module by g(∑ c_{x}x) = ∑ c_{x}gx. The dual module V^{∗} may be identified with the space of ℂ valued functions on N, which we will denote by F(N). Taking the elements of N as a basis for V, the dual basis consists of the functions δ_{x} which have the value 1 at x and 0 at every y ≠ x. The group operations are represented on V by permutation matrices and on V^{∗} by their transpose inverses. But the transpose inverse of a permutation matrix is itself, so unlike the general case, ℂN is isomorphic to its dual F(N). One can also see this by observing that gδ_{x} = δ_{gx} since δ_{x}(g^{−1}x′) = 1 when x′ = gx.

Suppose that G operates simultaneously as permutations of sets N and M. Then it operates on N × M ‘diagonally’, setting g(x, y) = (gx, gy) for (x, y) ∈ N × M. From the preceding we have canonical isomorphisms Hom_{ℂ}(F(N), F(M)) = F(N)^{∗} ⊗F(M) = F(N)⊗F(M). The last module is also canonically isomorphic to F(N × M), where we let δ_{(x,y)} correspond to δ_{x} ⊗ δ_{y}. The elements ϕ of F(N × M) have the form ∑ c(x, y)δ_{(x,y)}. Now ϕ is sent by g ∈ G to ∑ c(x, y)δ_{(gx,gy)}. Therefore, ϕ is fixed by all g, and hence corresponds to a G module morphism F(N) → F(M), if and only if c(x, y) = c(gx, gy) for all g. So module morphisms correspond to functions c(x, y) which are constant on the orbits of G in N × M. This gives the following.

Lemma. The dimension of the space of G module morphisms Hom_{G}(F(N), F(M)) is equal to the number of orbits of G operating on N × M. □

The lemma is useful when examining morphisms from one direct sum of G modules to another. Let V and W be G modules and suppose that both are given as direct sums of smaller modules, V = V_{1} ⊕… V_{p}, W = W_{1} ⊕⋯⊕W_{q}. We may think of the elements of V as column vectors of length p in which the jth component is in V_{j}, and similarly for W. A morphism f : V → W may then be viewed as a q × p matrix whose i, j entry f_{i,j} is a morphism from V_{j} to W_{i}. Consider two extreme cases: First suppose that p = q = (the number of distinct simple G modules), and that all V_{i} and W_{i} are isotypical, consisting of sums of copies of the ith simple G module exclusively. (Here V_{i} and W_{i} need not have the same number of simple components; in fact some may be zero.) Then by Schur’s lemma all f_{i,j} with i ≠ j must be 0 so f has a ‘block diagonal’ form. This leads to the second extreme case where the V_{j} and W_{i} are all copies of the same simple G module. (Here p and q may be different.) By Schur’s lemma each f_{i,j} is then just a scalar multiple of the identity matrix. These p × q scalars determine the morphism so the dimension of the set of these morphisms is pq.

Returning to the case where G operates on N and on M, suppose that the ith irreducible representation of G occurs p_{i} times in F(N) and q_{i} times in F(M). Then the dimension of the set of G module morphisms from F(N) to F(M) is p_{1}q_{1} + p_{2}q_{2} + ⋯ + p_{r}q_{r} where r is the number of different simple G modules. This gives the folowing.

Lemma. Suppose that G operates simultaneously as permutations of two sets, N and M, and suppose that the ith simple G module appears p_{i} times in F(N) and q_{i} times in F(M). Then dim Hom_{G}(F(N), F(M)) = ∑ p_{i}q_{i} and this is equal to the number of orbits of G operating on N × M. □

As an example, suppose that N = M, that the number of orbits of G on N × N is s, and that we know that F(N) is a direct sum of s submodules. Then these submodules are in fact simple and no two are isomorphic, so F(N) and its dual ℂN have simple spectrum. For if we decompose F(N) into simple modules (of which there must be at least s) and apply the preceding (where now p_{i} = q_{i}) then ∑ p_{i} ≥ s. The only way we can have ∑ p_{i}^{2} = s is if each p_{i} = 1 and the number of summands is s. This observation will be crucial later.

Here is a simple application. Suppose that the symmetric group S_{n} operates as the full group of permutations of a set N of n objects x_{1}, …, x_{n}. There are two obvious complementary submodules in ℂN. The first consists of all multiples of x_{1} + ⋯ + x_{n}. This element is fixed by all the permutations, so it spans a onedimensional submodule V_{1}, and being one-dimensional, it is necessarily simple. The second, V_{2} consists of all elements of the form c_{1}x_{1}+⋯+c_{n}x_{n} with c_{1}+⋯+c_{n} = 0. This submodule is complementary to the first but it is not obvious that it is simple. Consider, however, the orbits of S_{n} on N × N. Any pair of equal objects (x_{i}, x_{i}) must be sent to another of the same form, while any pair (x_{i}, x_{j}) with i ≠ j can be sent by some permutation in S_{n} to any other pair of distinct objects. There are therefore precisely two orbits, so V_{2} is also simple. It is also not isomorphic to V_{1} since S_{n} acts trivially on V_{1} but not on V_{2}, so V has simple spectrum. Its endomorphisms therefore commute and each has at most two eigenvalues, the first with multiplicity 1 and the second repeated n − 1 times. (They can, of course, coincide.) This is the case k = 1 of Theorem 1.

2. Proof of Theorem 1. Let U be, as before, a set with n elements and N be the family of its k-element subsets. Set V = ℂN, in which the elements of N are a natural basis. Now S_{n} permutes U and every permutation σ of U induces one of N, still denoted by σ, so V becomes an S_{n} module. A matrix A = A_{S,T} with rows and columns indexed by the sets in N commutes with all σ operating on V if and only if A_{σS,σT} = A_{S,T} for all σ. Clearly #(S ∩ T) = #(σS ∩ σT) for all σ. In fact, it is easy to see that if (S′, T′) is a second pair of sets in N then there is a σ with σS = S′, σT = T′ if and only if #(S ∩ T) = #(S′ ∩ T′). The ICM’s are therefore precisely the matrices of endomorphisms of the S_{n} module ℂN. This module, we show, has simple spectrum.

Without loss of generality we may assume that k ≤ n/2 since otherwise we can replace every set in N by its complement and get the same representation and the same ICM’s. From what has just been said, the orbit of (S, T) depends only on #(S ∩ T), which can take any value from 0 to k, so there are exactly k + 1 orbits orbits of S_{n} operating on N × N.. Consequently, the S_{n} module ℂN can not have more than k + 1 simple summands, so it can not have more than k + 1 direct summands of any kind. If it has this many then they must be simple and distinct, so the spectrum will be simple. In Proposition 1 we exhibit a decomposition of ℂN into k +1 direct summands, which must then be simple and distinct. We will adopt a device of representing subsets of U by monomials in two variables. This will be convenient in giving a concise expression for certain eigenvectors of ICM’s and is also adaptable to quantization..

To fix the ideas, let U = {1, …, n}. To describe the subsets of U, let V henceforth denote a two-dimensional vector space in which we have chosen fixed basis elements x and y. Then the nth tensor power of V, which we will write simply as V^{n}, has dimension 2^{n}. Omitting the ⊗ sign, we may view it as spanned by the noncommutative monomials of total degree n in x and y. To every such monomial μ we can assign a subset of {1, …, n} by saying that j is in the subset if and only if the jth factor of μ is y. The symmetric group operates on V^{n} by permutation of its tensor factors, and in so doing carries any monomial of total degree i in y (and hence of degree n−i in x) into another with the same degrees. Denote the linear span of those monomials of degree n−i in x and i in y by V (n−i, i). Then S_{n} operates on each of these, and in particular on V (n−k, k). The point of this device is that we now clearly have (up to equivalence) the same representation of S_{n} as that obtained from its operation on the k-element subsets of {1, …, n}. Our strategy is to show that V (n− k, k) has k + 1 non-zero direct summands; these must then be simple and distinct. Therefore, ℂN will also have simple spectrum, so our ICM’s must commute. To state Proposition 1 it is convenient to introduce the tensor algebra T V of V; this is the direct sum of all its tensor powers, T V = ℂ + V + V^{2} + …. Multiplication here is just the tensor product which, since we have eliminated the symbol ⊗, is now just concatenation. One may also view T V as the non-commutative polynomial algebra in the two variables x and y. On T V one has the following derivations: X := x∂/∂y, Y := y∂/∂x, and H := [X, Y] := XY − Y X = x∂/∂x − y∂/∂y. (A derivation of a not necessarily commutative ring is just a mapping D of the ring into itself such that D(ab) = (Da)b+a(Db) for all a and b in the ring. Here, for example, X(yyxy) = (Xy)yxy + y(Xy)xy + yy(Xx)y + yyx(Xy) = xyxy + yxxy + 0 + yyxx. One can check that if μ is a monomial of total degree n with degree i in y and n − i in x then Hμ = (n − 2i)μ. Clearly Y V (n − i, i) ⊂ V (n − i − 1, i + 1) and XV (n − i − 1, i + 1) ⊂ V (n − i, i). The derivations X, Y, H commute with the operation of S_{n} and therefore carry S_{n} submodules to S_{n} submodules. One can check that [H, X] = 2X and [H, Y] = −2Y. (We have, therefore, a representation of the simple Lie algebra 𝔰𝔩(2, ℂ).) In what follows we will denote the kernel of X | V (n − i, i) by V (n − i, i; 0). Being the kernel of a module morphism, it is a submodule.

Proposition 1. For all k ≤ n/2 we have: 1) Y | V (n − k + 1, k − 1) → V (n − k, k) is a monomorphism, 2) V (n − k, k; 0) ≠ 0, and 3) V (n − k, k) = Y V (n − k + 1, k − 1) ⊕ V (n − k, k; 0). Therefore, V (n − k, k) = ⨁_{j=0}^{k} Y^{k−j}V (n − j, j; 0) ≅ ⨁_{j=0}^{k} V (n − j, j; 0). This is a direct sum of k + 1 non- zero summands which are therefore simple and distinct. In particular, V (n − k, k) has simple spectrum.

Proof. This will be by induction. The assertion is trivial for k = 0. Assume that it holds for all i < k. The relations between X, Y, and H imply that for all m > 0 we have

XY^{m} − Y^{m}X = HY^{m−1} + Y HY^{m−2} + ⋯ + Y^{m−1}H.

Now suppose that j < n/2 and that v ∈ V (n − j, j; 0). Since Xv = 0 we have

XY^{m}v = [(n−2j)+(n−2j−2)+⋯+(n−2j−2m+1)]Y^{m−1}v = m(n−2j−m+1)Y^{m−1}v.

Thus if Y^{m−1}v ≠ 0 and m < n − 2j + 1 then also Y^{m}v ≠ 0. (Note that m = 1 is allowed.) Now if Y annihilates any element v in V (n − k + 1, k − 1), which from the induction hypothesis has simple spectrum, then we may assume without loss of generality that v lies in one of the simple summands of that module. By the induction hypothesis, these are of the form Y^{k−1−j}V (n − j, j; 0) for some j with 0 ≤ j ≤ k − 1, so taking m = k − j in the preceding relation we see that in fact Y v ≠ 0. This proves 1). The same relation shows that on each simple summand of V (n−k+1, k−1) the product XY acts as some non-zero multiple of the identity, so the kernel of X on V (n−k, k) can not intersect Y V (n−k +1, k −1). Moreover, this kernel can not be 0; otherwise XY would be an isomorphism V (n − k + 1, k − 1) → V (n − k, k), which is impossible since the dimension of the former, \binom{n−k+1}{k−1}, is less than that of the latter, \binom{n−k}{k}. Therefore V (n − k, k) contains the direct sum of Y V (n − k + 1, k − 1) which by the induction already has k non-zero summands, and V (n − k, k; 0), and thus has k + 1 non- zero summands. □

This concludes the proof of Theorem 1 except for the assertion that an ICM with integer entries has integer eigenvalues. Although this will be evident in the next section when we compute these eigenvalues, it also follows from the following simple argument. If a square matrix has integer entries then its characteristic polynomial is a monic polynomial with integer coefficients. (The roots of such a polynomial are called algebraic integers.) The operations we used to construct the basis in which all ICM’s become diagonal produce only rational numbers, since we only needed to solve linear equations. That is, the eigenvectors are all rational. Therefore, if an ICM has integer entries and we change the basis of ℂN to the diagonalizing one just constructed then any integer ICM will be conjugated into a diagonal matrix with rational entries on the diagonal. These rational numbers are the eigenvalues. But it is easy to see that if a root of a monic polynomial with integer coefficients is rational then it must in fact be an integer. (That is, an algebraic integer which is an ordinary rational number is an ordinary integer.)

3. The eigenvectors and eigenvalues. We have not yet taken full advantage of the representation of subsets of U by monomials but this will now be very useful in computing the eigenvectors and eigenvalues of ICM’s. The first step is to define certain “admissible monomials” in V (n − i, i) and certain skew-symmetrizing operators; these will enable us to construct a basis for V (n−i, i; 0) = ker X | V (n−i, i). Write V (n − i, i; j) := Y^{j}V (n − i + j, i − j; 0) and call this the ‘jth summand’ of V (n − i, i). We have seen that these are the simple direct summands of V (n − i, i), and hence are the eigenspaces for the different eigenvalues of the ICM’s. Therefore, if we can give a basis for each V (n − i, i; j) then we will have a complete set of eigenvectors. The 0th summand of V (n − i, i), namely V (n − i, i; 0) will be called the “top” summand and Y^{i}V (n, 0) will be called the “bottom”. Recall that the the dimension of the top is \binom{n}{i} − \binom{n}{i−1}. To construct a basis for the top summand, call a monomial μ in V (n − i, i) admissible if in any factorization μ = μ_{1}μ_{2} the degree of μ_{2} in y is not more than its degree in x. For example, yyxx and yxyx are admissible, but xyyx is not.

Lemma. The number of admissible monomials in V (n − i, i) is \binom{n}{i} − \binom{n}{i−1}.

Proof. This is a simple induction on n. Consider first the case where n = 2i. Then an admissible monomial μ must have the form μ = yν, where ν is an admissible monomial lying in V (n − i, i − 1). Therefore, the number of admissible monomials in V (n − i, i) is the same as that in V (n − i, i − 1). By the inductive hypothesis, the latter is \binom{n−1}{i−1} − \binom{n−1}{i−2}, but one can check that if n = 2i then this is the same as \binom{n}{i} − \binom{n}{i−1}. If 2i < n then every admissible monomial in V (n − i, i) is either of the form yν with ν an admissible monomial in V (n − i, i − 1), or of the form xν′ with ν′ an admissible monomial in V (n − i − 1, i). The total number of admissible monomials in V (n−i, i) is therefore (\binom{n−1}{i−1}−\binom{n−1}{i−2})+(\binom{n−1}{i}−\binom{n−1}{i−1}) = (\binom{n−1}{i−1} + \binom{n−1}{i}) − (\binom{n−1}{i−2} + \binom{n−1}{i−1}) = \binom{n}{i} − \binom{n}{i−1}. □

The number of admissible monomials in V (n − i, i) thus equals the dimension of the top summand V (n − i, i; 0). To construct a basis using them, we define for each admissible monomial a skew-symmetrizing operator Sk_{μ} . (Each monomial gives rise to a different operator). These operators are then tacitly extended linearly to the whole space. The operators will be elements of the group ring ℂS_{n} of the symmetric group, so we must first define the operation of an element σ ∈ S_{n} on a monomial ν with n factors. Write ν = z_{1}z_{2} ⋯ z_{n}. (In our case, each z is either an x or a y.) Then σν = z_{σ^{−1}1}z_{σ^{−1}2} ⋯ z_{σ^{−1}n}. (One needs σ^{−1} to have (στ)ν = σ(τν).) Suppose now that an admissible μ ∈ V (n − i, i) is given. Pair the last y appearing in μ with the x immediately following, the next-to-last y with the closest following unpaired x, and so forth. Because μ is admissible, each y is paired with some x coming later in μ, but if n > 2i then some of the x remain unpaired. Suppose that the y factors in μ are in places p_{1}, p_{2}, …, p_{i} and that they are paired, respectively with x factors in places q_{1}, q_{2}, …, q_{i}. Denoting the unit element of the symmetric group S_{n} simply by 1, set Sk_{μ} := (1 − (p_{1}, q_{1}))(1 − (p_{2}, q_{2})) ⋯ (1 − (p_{i}, q_{i})). The transpositions (p_{j}, q_{j}) all commute, so if this is applied to μ then the result will be a sum of 2^{j} terms which is skew in the places p_{j}, q_{j} for all j.

Lemma. The Sk_{μ} μ lie in V (n − i, i; 0) and are linearly independent. Hence they form a basis for V (n − i, i; 0).

Proof. Clearly 1 − (p, q) annihilates any expression which is symmetric in places p and q. Therefore, Sk_{μ} will annihilate any expression which is symmetric in any of the paired places p_{j}, q_{j} of μ. It follows that X Sk_{μ} = 0 for every admissible μ in V (n−i, i). For recall that X commutes with the operations of the symmetric group and hence also with Sk_{μ}, so it will be sufficient to show that Sk_{μ} Xμ = 0. Now Xμ is a sum of i terms in each of which one of the y’s in μ has been changed to x. The term in which the jth y is changed to an x is now symmetric in places p_{j}, q_{j}. Thus all the Sk_{μ} μ lie in V (n − i, i; 0). To show that they are independent, linearly order all the admissible monomials in V (n−i, i) by putting μ before μ′ if in the first place where they differ μ has a factor y and μ′ has a factor x. Now suppose, if possible, that some non-trivial linear combination of the Sk_{μ} μ vanishes, where the μ are all admissible. Let ν be the first of the μ that appear in this linear combination. Since each of the skew-symmetrizing operators only replaces a y with some x following it, ν itself appears exactly once in the expression which is supposed to vanish, and therefore can not be canceled, a contradiction. □

This gives a basis of eigenvectors for the ICM’s determined by the k-element subsets of our n-element set U. For recall that each monomial μ ∈ V (n − k, k) represents a set, namely that which contains the jth element of U if and only if the jth place of μ is y. A linear combination of monomials can therefore be read as an element of ℂN (where N was the family of all k-element subsets). We can also view it as a column vector of length \binom{n}{k} whose component corresponding to a particular set in N is the coefficient of the corresponding monomial in the linear combination. We have now shown, in particular, that if μ is admissible then Sk_{μ} μ is an eigenvector. The actual computation of these eigenvectors is made a little easier, however, by the following observation, which we will use in computing the eigenvalues. The last (in our ordering) admissible monomial in V (n − i, i) is x^{n−2i}(yx)^{i}. It is easy to see that skew-symmetrizing this according to our procedure gives x^{n−2i}(yx − xy)^{i}. Now Y (xy − yx) = 0 and Y is a derivation, so applying Y^{k−i} gives (Y^{k−i}x^{n−2i})(yx − xy)^{i}. That is, any powers of Y will affect only the first factor, x^{n−2i}. This contains all the x’s which are not paired with some y and hence are not involved in the skew-symmetrization. One can see similarly, that if a power of Y is applied to any Sk_{μ} μ then (after cancelations) it will actually affect only those x which are not involved in the skew-symmetrization. To compute the eigenvalues of an ICM, we need only compute its effect on the k + 1 eigenvectors (Y^{k−i}x^{n−2i})(yx − xy)^{i}, since each lies in a different eigenspace. We make a minor change in numbering and notation. Notice that Y^{p}x^{q} can be described as follows: choose in all possible ways p distinct places in x_{q}, replace these by y, add the results and multiply by p!. To avoid carrying the factor p! we therefore set Y_{p} = (1/p!)Y^{p}. Now define k+1 “special” eigenvectors by v_{i} := Y_{i}x^{n−2k+2i}(yx−xy)^{k−i}, i = 0, …, k. Then v_{i} ∈ V (n − k, k; i) and y^{i}x^{n−2k+i}(yx)^{k−i} appears in it with coefficient 1. Let J_{r} = J_{r}(n, k), r = 0, …, k be the ICM whose S, T entry is 1 when the k-element subsets S and T have precisely r elements in common, and is 0 otherwise. These form a basis for the ICM’s, and because they are simultaneously diagonalizable, it is sufficient to find their eigenvalues. Now suppose that v = ∑ c_{m}S_{m} is an eigenvector of J_{r}, where the c_{m} are constants and S_{m} ranges over the family N of all the k-element subsets of U.

Choose any “test set” S_{p} with c_{p} ≠ 0. Then S_{p} appears in J_{r}v with coefficient ∑ c′_{m} where c′_{m} = 1 if S_{p} and S_{m} have exactly r elements in common and is 0 otherwise. Therefore, the eigenvalue corresponding to v is (∑ c′_{m})/c_{p}. Denote the eigenvalue of J_{r}(n, k) on V (n − k, k; i) by λ_{r,i}(n, k).

We compute first the eigenvalues of J_{r} on the top and botttom eigenspaces since the general case reduces to these two. The top special eigenvector is v_{0} = x^{n−2k}(yx − xy)^{k}. As test set choose the set represented by x^{n−2k}(yx)^{k}, which appears with coefficient 1 in V_{0}. Now if μ and ν are monomials representing sets in the family N then the number of elements the sets have in common is just the number of places where μ and ν both have the factor y. Then it is immediate that λ_{r,0} = (−1)^{k−r}\binom{k}{r}. The bottom eigenvector is v_{k} = Y_{k}x^{n}. As test set choose y^{k}x^{n−k}, which appears with coefficient 1. The eigenvalue of J_{r} is now the number of ways of simultaneously choosing r elements from a set of k and k − r elements from a set of n − k, so λ_{r,k} = \binom{k}{r} × \binom{n−k}{k−r}.

In the general case v_{i} is a product Y_{i}x^{n−2k+2i} × (yx − xy)^{k−i} of top and bottom eigenvectors for smaller values of n and k. Correspondingly, λ_{r,i} will be a sum of products, the sum being indexed by the ways of writing r = r_{1} + r_{2}. So finally we have

Theorem 2.

λ_{r,i}(n, k) = ∑_{r_{1}+r_{2}=r} λ_{r_{1},i}(n − 2k + 2i, i) × λ_{r_{2},k−i}(2k − 2i, k − i)

= ∑_{r_{1}+r_{2}=r} \binom{i}{r_{1}}\binom{n − 2k + i}{i − r_{1}} × (−1)^{k−i−r_{2}} \binom{k − i}{r_{2}}.

(Here 0 ≤ r_{1} ≤ i, 0 ≤ r_{2} ≤ k − i.) □

The reader familiar with the representation theory of the symmetric group will probably recognize in our skew-symmetrization the classical computation of primitive idempotents in the group ring, which in the special case treated here takes a very simple form. Our admissible monomials correspond to standard Young tableaux, cf. [GSs].

After the theory it may be useful to look at a concrete example. The smallest with three distinct eigenspaces is n = 4, k = 2, so take U = {a, b, c, d} and N = {ab, ac, ad, bc, bd, cd} where ab stands for the two-element subset {a, b}, etc.. The dimensions of the eigenspaces V (4, 2; i), i = 0, 1, 2, are 2, 3, 1, respectively. We compute first the three special eigenvectors v_{i} ∈ V (4, 2; i). From our formulas, v_{0} = (yx − xy)^{2} = yxyx − yxxy − xyyx + xyxy. Since yxyx represents the subset consisting of the first and third elements of U, this eigenvector is ac − ad − bc − bd. Here ab and cd each have coefficient 0, so as a numerical column vector v_{0} is the transpose of (0, 1, −1, −1, 1, 0). The eigenvector v_{1} = (Y x^{2})(yx − xy) = (yx + xy)(yx − xy) = yxyx − yxxy + xyyx − xyxy = ac − ad + bc − bd, so v_{1} is the transpose of (0, 1, −1, 1, −1, 0). Finally, v_{2} = Y_{2}x^{4}. Here one takes all possible pairs of factors out of x^{4} and replaces them with y, so the eigenvector is just the sum of all the elements of N. It is easy to see that this is always the case for the bottom eigenvector. Numerically, v_{2} is the transpose of (1, 1, 1, 1, 1, 1).

Now J_{2} is the 6×6 identity, J_{0} is the matrix with 1 everywhere on the antidiagonal and zero elsewhere, and

J_{1} = ( \begin{matrix}0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \end{matrix} ) .

For r = 2 one must therefore verify that Theorem 1 yields the eigenvalue 1 for i = 0, 1, 2. In each case the summation has exactly one term. For when i = 0 we must have r_{1} = 0 so r_{2} = 2, when i = 1 we must have r_{1} ≤ 1 and r_{2} ≤ 1 so both are equal to 1, and when i = 2 we must have r_{2} = 0 so r_{1} = 2. It is trivial to check that in all three cases the value of the single term is 1. For r = 0 we can only have r_{1} = r_{2} = 0, so again for every i there is but a single term. The formula values for i = 0, 1, 2 are 1, −1, 1, and v_{0}, v_{1}, v_{2} do lie in the corresponding eigenspaces. Here two of the eigenvalues have coalesced, and +1 and −1 each appear with the correct multiplicity, 3. The most interesting case is r = 1. For i = 0 the formula has only one term: one must have r_{1} = 0, r_{2} = 1, so the value is 1 × (−1)^{1}\binom{2}{1} = −2. One can check readily that J_{1}v_{0} = (−2)v_{0}. For i = 1 there are two terms; (r_{1}, r_{2}) can be either (0, 1) or (1, 0). The value in the first case is +1 and in the second −1 so the eigenvalue is 0 and J_{1} indeed annihilates v_{1}. For i = 2 one sees that J_{1}v_{2} = 4v_{2} so we must verify that eigenvalue given by the formula is 4. In this case k − i = 0, so r_{2} = 0 and therefore r_{1} = 1. There is thus only one term and the eigenvalue given by the formula is \binom{2}{1}\binom{2}{1} × 1 = 4. Since the eigenvalues −2, 0, 4 have multiplicities 2, 3, 1, respectively, the predicted trace is 0, which is obviously correct.

4. Some generalizations. The conjugacy classes of S_{n} are in natural 1–1 correspondence with the (non-increasing) partitions of n. Even though for an arbitrary finite group G there is no natural correspondence between conjugacy classes and simple modules, one does exist for S_{n}. The simple modules V (n − k, k; 0) encountered above are those corresponding to non-increasing partitions (n−k, k) of n into not more than two non-zero parts. One way to view Theorem 1 is to say that we have chosen a two-element partition (n_{1}, n_{2}) of n and have formed all partitions of our n-element set U into two subsets (U_{1}, U_{2}) of corresponding sizes. The symmetric group acts on the family N(n_{1}, n_{2}) of these partitions of U and we have shown that the induced representation of S_{n} on ℂN(n_{1}, n_{2}) has simple spectrum. A natural generalization would be to choose a partition (n_{1}, …, n_{r}) of n into r parts in nonincreasing order, and to form the family N(n_{1}, …, n_{r}) of all partitions (U_{1}, …, U_{r}) of U with #U_{i} = n_{i}. The operation of S_{n} on U again induces an operation on N(n_{1}, …, n_{r}) and we may consider matrices A_{X,Y} with rows and columns indexed by sets in N(n_{1}, …, n_{r}) with the property that A_{σX,σY} = A_{X,Y} for all σ ∈ S_{n}. This is harder to express in terms of intersections, but these matrices generalize ICM’s in the sense that they represent the endomorphisms of ℂN(n_{1}, …, n_{r}). Unfortunately, for r > 2 the spectrum of the latter module is no longer simple, so these generalized ICM’s no longer commute. On the other hand, there is a method, (Young’s rule) of finding the multiplicity with which any simple module appears in ℂN(n_{1}, …, n_{r}) as well as a formula (the ‘hook length’ formula) giving the dimension of any simple S_{n} module. So we do still have some important information about eigenvalues and eigenspaces of these generalized ICM’s. However, one of the most natural and interesting genralizations is the following.

Let N be the family of all subsets of U. The operation of S_{n} on U again induces a representation on ℂN. This representation does not have simple spectrum, the ICM’s (whose dimensions are 2^{n} × 2^{n}) do not commute, and the product of two ICM’s is generally no longer an ICM, but the representation is easily computable. If V_{1}, …, V_{r} are inequivalent simple modules, denote the direct sum containing each V_{i} exactly m_{i} times by m_{1}V_{1} + ⋯ + m_{r}V_{r}. We leave it as an exercise to show that, with our previous notation, the representation of S_{n} on ℂN is now equivalent to ∑_{i≤n/2}(n+1−2i)V (n−i, i; 0). If n is odd, say n = 2m+1, then the sum terminates with 2 · V (m + 1, m; 0), while if n = 2m then it terminates with 1 · V (m, m; 0). Correspondingly, the characteristic polynomial of an ICM is a product of factors of

the form f_{i}^{\binom{n}{i}−\binom{n}{i−1}} where f_{i} is generally irreducible of degree n + 1 − 2i. (When n = 2m the presence of the linear factor in the characteristic polynomial shows that if the ICM has integer entries then it has an integer eigenvalue with multiplicity \binom{2m}{m} − \binom{2m}{m−1}.) In special cases the characteristic polynomial may factor further. For example, Wilf has shown that for the “disjointness matrix” whose entry in the S, T place is 1 when S and T are disjoint and 0 otherwise, the f_{i} factor into quadratic factors related to Fibonacci numbers. There are many interesting open questions about the ICM’s which one obtains here.

5. Quantization. Algebraic deformation theory was introduced by the author in a series of papers beginning in 1963, although specific examples of deformations of algebras were previously known; for later work and summaries, cf. [GSk1,2]. The basic idea is to replace the original multiplication in an algebra A by a new “star product”

a ∗ b = ab + tα_{1}(a, b) + t^{2}α_{2}(a, b) + …

where ab is the original product, t is a formal parameter, and the α_{i} are bilinear maps A × A → A. When t = 0 one has the original algebra. Sometimes it is more convenient to introduce instead of t a parameter q such that one gets the original algebra when q = 1, and when this is done the process is frequently called quantization. It is the same idea: simply set q = 1 + t. (When the coefficient field is ℂ it is more common to set q = e^{t}. In quantum mechanics, the parameter t is usually Planck’s constant ℏ.)

A classic example of quantization (predating use of the word) is the Hecke algebra H_{n}(q) of the symmetric group S_{n}. This is a deformation of the group algebra ℂS_{n} whose underlying vector space is the same as that of ℂS_{n}, but to avoid confusion, for each w ∈ S_{n} take a basis element denoted T_{w} of H_{n}(q). Now any w ∈ S_{n} can be expressed in some way as a product of the transpositions σ_{1} = (12), …, σ_{n−1} = (n − 1, n). Its length ℓ(w) is the minimal number of factors in such an expression. The deformed multiplication is defined as follows. If σ is one of the generators (12), …, (n − 1, n) and ℓ(σw) > ℓ(w) then set T_{σw} = T_{σ}T_{w} but set T_{σ}^{2} = (q − q^{−1})T_{σ} + 1. This is in fact enough to define the multiplication completely, cf. [H]. The method we used here to analyze ℂS_{n} modules in effect used the universal enveloping algebra U of the Lie algebra 𝔰𝔩(2). This can also be quantized (cf., e.g., the exposition by Takhtajan [T]) and can be used to analyze modules over H_{n}(q) in exactly the same way that we have done here, cf. [GSs]. The quantized ICM’s, in the finite case, are endomorphisms of certain H_{n}(q) modules. Remarkably, as shown in [G1], the quantized ICM’s are all conjugates of the standard ICM’s by a fixed orthogonal matrix, and in particular, have the same eigenvalues, but look quite different. The symmetric group itself is now replaced by an infinite ‘quantum’ symmetric group. The rotation through 2π/3 of an object with a three-fold symmetry, for example, is now replaced by one through a slightly larger angle; the rotation precesses, something which may have implications for the spectrum of a molecule with such symmetry. In the infinite case, an inductive limit of the finite cases, ICM’s are replaced by certain functions. There are various topologies to consider and the results are different, cf. [G1,2]. It is the existence of the quantization of U (and of more general universal enveloping algebras and Hopf algebras) which makes the method used here to prove Theorem 1 adaptable to the quantized case.

References

[BL] K. A. Brown and M. Lorenz, Grothendieck groups of invariant rings and of group rings, J. Alg. 166 (1994), 423–454.

[FH] W. Fulton and J. Harris, Representation Theory, A First Course, Springer–Verlag, New York, Berlin, 1991.

[G1] M. Gerstenhaber, Quantized intersection cardinalities, Deformation Theory and Symplectic Geometry (Daniel Sternheimer, John Rawnsley, Simone Gutt, eds.), Proceedings of the Ascona Conference, June 1986, Kluwer, Dordrecht, 1997, pp. 85–102.

[G2] , Deformation of towers of algebras and quantized intersection cardinality functions, Letters in Math. Phys. 43 (1998), 87–103.

[GSk1] M. Gerstenhaber and S. D. Schack, Algebraic cohomology and deformation theory, Deformation Theory of Algebras and Structures (M. Hazewinkel and M. Gerstenhaber, eds.), Proceedings of the NATO Advanced Study Institute, Castelvecchio–Pascoli, June, 1986, Kluwer, Dordrecht, 1988, pp. 11-264.

[GSk2] , Algebras, bialgebras, quantum groups, and deformations, Deformation Theory and Quantum Groups with Applications to Mathematical Physics (M. Gerstenhaber and J. Stasheff, eds.), Proceedings of a joint AMS–IMS–SIAM Summer Summer Research Conference, Amherst, 1990; Contemporary Mathematics 134, American Mathematical Society, Providence, 1992, pp. 51–92.

[GSs] M. Gerstenhaber and Mary E. Schaps, Hecke algebras, U_{q}sl_{n}, and the Donald–Flanigan conjecture for S_{n}, Trans. Amer. Math. Soc. 349 (1997), 3353–3371.

[H] James E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge studies in advanced mathematics 29, Cambridge, 1990.

[K] D. E. Knuth, Combinatorial matrices, http://www-cs-staff.Stanford.EDU(go to Knuth’s home page).

[L] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. in Information Theory 25 (1979), 1–7.

[Sg] S. Sternberg, Group theory and physics, Cambridge University Press, New York, Cambridge, 1994.

[Sy] R. Stanley, Variations on differential posets, Invariant Theory and Tableaux (D. Stanton, ed.), IMA Volumes in Mathematics and its Applications, 19, 1990, pp. 145–165.

[T] L.A. Takhtajan, Lecture on quantum groups, Introduction to Quantum Group and Integrable Massive Models of Quantum Field Theory (M.–L. Ge and B.–H. Zhao, eds.), World Scientific, Singapore/New Jersey/London/Hong Kong, 1990, pp. 69–197.

[Wf] H. S. Wilf, Hadamard determinants, Möbius functions, and the chromatic number of a graph, Bull. Amer. Math. Soc. 74 (1968), 960–964.

[Wl] H. Weyl, The Classical Groups (Second edition), Princeton Uiversity Press, Princeton, NJ, 1938 (1946).

Dept. of Mathematics, University of Pennsylvania, Philadelphia, PA 19104-6395 E-mail address: mgersten@math.upenn.edu