Robinson-Schensted-Knuth insertion and characters of symmetric groups and Iwahori-Hecke algebras of type A

Arun Ram* Department of Mathematics Princeton University Princeton, NJ 08544

Dedicated to Gian-Carlo Rota

0. Introduction

The purpose of this note is to give an insertion scheme proof of the formula, [Mac] Ch. I (7.8),

p_{μ} = ∑_{λ⊢k} χ^{λ}(μ)s_{λ},  (0.1)

where p_{μ} is the power sum symmetric function, s_{λ} is the Schur function and χ^{λ}(μ) is the irreducible character of the symmetric group S_{k} indexed by the partition λ and evaluated at a permutation of cycle type μ = (μ_{1}, …, μ_{ℓ}). The proof of this formula will be by direct application of the Robinson-Schensted-Knuth insertion scheme and the following beautiful formula of Roichman [Ro],

χ^{λ}(μ) = ∑_{Q} rw_{1}^{μ}(Q),  (0.2)

where the sum is over all standard tableaux Q of shape λ and the μ-weight of a standard tableau is given by

rw_{q}^{μ}(Q) = ∏_{{1≤j≤k \atop j∉B(μ)}} f_{μ}(j, Q), where B(μ) = \{μ_{1} + ⋯ + μ_{r} | 1 ≤ r ≤ ℓ\}, and  (0.3)

f_{μ}(j, Q) = \{ \begin{matrix}−1, & if j + 1 is southwest of j in Q, \\ 0, & if j + 1 is northeast of j in Q, j + 1 ∉ B(μ), \\ & and j + 2 is southwest of j + 1 in Q, \\ q, & otherwise. \end{matrix}  (0.4)

* Research supported by an Australian Research Council Fellowship. 1991 Mathematics Subject Classification. Primary 20C30, 05E05. Secondary 05E10. Key words: Insertion schemes, symmetric functions, symmetric groups.

The notation rw_{1}^{μ}(Q) denotes the weight rw_{q}^{μ}(Q) when q = 1. The notations and direction for partitions and their Ferrers diagrams are as in [Mac], and “north” means in the same row or in a higher row.

Alternatively, one may assume the Frobenius formula in (0.1) and interpret this note as an elementary proof of Roichman’s formula. One should note that Roichman’s formula is actually more general than what I have stated above, I am considering only the Type A case, and I have stated it above only in the q = 1 case. D. White [Wh] has also analyzed the characters of the symmetric group by an analogue of the RSK insertion scheme. His methods are different from those used in this paper.

1. Symmetric functions

Fix a positive integer n, let x_{1}, …, x_{n} be commuting variables and let q be an indeterminate. If λ is a partition let s_{λ} = s_{λ}(x_{1}, …, x_{n}) denote the Schur function associated to λ [Mac]. Define

q_{r} = q_{r}(x_{1}, x_{2}, …, x_{n}; q) = ∑_{1≤i_{1}≤···≤i_{r}≤n} x_{i_{1}} ⋯ x_{i_{r}}q^{(# of i_{j}=i_{j+1})}(q−1)^{(# of i_{j}<i_{j+1})}, (1.1)

and for a partition μ = (μ_{1}, …, μ_{ℓ}) define q_{μ} = q_{μ}(x_{1}, …, x_{n}; q) = q_{μ_{1}}q_{μ_{2}} ⋯ q_{μ_{ℓ}}. The following are well known facts:

(1.2) If μ ⊢ k then

p_{μ} = ∑_{λ⊢k} χ^{λ}(μ)s_{λ}

where χ^{λ}(μ) is the character of the symmetric group S_{k} associated to the partition λ evaluated at an element of cycle type μ.

(1.3) [Ra] If μ ⊢ k then

q_{μ} = ∑_{λ⊢k} χ_{q}^{λ}(μ)s_{λ}

where χ_{q}^{λ}(μ) is the character of the Iwahori-Hecke algebra of type A associated to the partition λ evaluated at the element T_{γ_{μ}} where γ_{μ} = γ_{μ_{1}} × ⋯ × γ_{μ_{ℓ}} ∈ S_{μ_{1}} × ⋯ × S_{μ_{ℓ}} and γ_{r} = (1, 2, …, r) ∈ S_{r} (in cycle notation).

(1.4) χ^{λ}(μ) = χ_{q}^{λ}(μ)|_{q=1} and q_{μ}(x_{1}, …, x_{n}; 1) = p_{μ}(x_{1}, …, x_{n}), where p_{μ} is the power sum symmetric function.

Lemma 1.5. If (i_{1}, …, i_{r}) is a sequence 1 ≤ i_{1}, …, i_{r} ≤ n, define

wt_{q}(i_{1}, …, i_{r}) = \{ \begin{matrix}(−1)^{s}q^{r−1−s}, & if there exists an s, 0 ≤ s < r, \\ & such that i_{1} < ⋯ < i_{s} < i_{s+1} ≥ ⋯ ≥ i_{r}, \\ 0, & otherwise. \end{matrix}

Then q_{r}(x_{1}, …, x_{n}; q) = ∑_{1≤i_{1},...,i_{r}≤n} x_{i_{1}} ⋯ x_{i_{r}}wt_{q}(i_{1}, …, i_{r}).

Proof. Let 1 ≤ j_{1} ≤ j_{2} ≤ ⋯ ≤ j_{r} ≤ n be an increasing sequence and let us show that

∑_{1≤i_{1},...,i_{r}≤n} x_{i_{1}} ⋯ x_{i_{r}}wt_{q}(i_{1}, …, i_{r})|_{x_{j_{1}} ···x_{jr}} = q^{r−ℓ}(q − 1)^{ℓ−1},

where ℓ is the number of j_{k} < j_{k+1} in the sequence j_{1} ≤ j_{2} ≤ … ≤ j_{r}.

Let D be the set of distinct elements in the sequence j_{1} ≤ ⋯ ≤ j_{r}, let m be the maximal element of D and let D′ = D\{m}. For each subset S of D′ let

s = Card(S),

i_{1} < i_{2} < ⋯ < i_{s} be the elements of S in increasing order,

i_{s+1} = m, and let

i_{s+2} ≥ i_{s+3} ≥ ⋯ ≥ i_{r} be the remainder of the elements of the sequence j_{1}, … j_{r} arranged in decreasing order.

Then x_{i_{1}} ⋯ x_{i_{r}} = x_{j_{1}} ⋯ x_{j_{r}} and wt(i_{1}, …, i_{r}) = (−1)^{s}q^{r−1−s}.

We have x_{i_{1}} ⋯ x_{i_{r}} = x_{j_{1}} ⋯ x_{j_{r}} and wt_{q}(i_{1}, …, i_{r}) ≠ 0 if and only if

(1) there exists a permutation σ ∈ S_{r} such that (i_{1}, …, i_{r}) = (j_{σ(1)}, …, j_{σ(r)}) and (2) there exists an s such that 0 ≤ s < r and

j_{σ(1)} < ⋯ < j_{σ(2)} < ⋯ < j_{σ(s)} < j_{σ(s+1)} ≥ j_{σ(s+2)} ≥ ⋯ ≥ j_{σ(r)}.

It follows from this that every sequence 1 ≤ i_{1}, …, i_{r} ≤ n such that x_{i_{1}} ⋯ x_{i_{r}} = x_{j_{1}} ⋯ x_{j_{r}} and wt_{q}(i_{1}, …, i_{r}) ≠ 0 is of the form given in the previous paragraph for a unique subset S of D′. Thus

\begin{aligned}∑_{1≤i_{1},...,i_{r}≤n} x_{i_{1}} ⋯ x_{i_{r}} & wt_{q}(i_{1}, …, i_{r})|_{x_{j_{1}} ···x_{jr}} = ∑_{S⊆D′} q^{r−|S|−1}(−1)^{|S|} \\ & = ∑_{s=0}^{ℓ−1} \binom{ℓ − 1}{s}(−1)^{s}q^{r−s−1} = q^{r−ℓ}(q − 1)^{ℓ−1}, \end{aligned}

where ℓ = Card(D) = (# of j_{k} < j_{k+1} in j_{1} ≤ ⋯ ≤ j_{r}).

Corollary 1.6. Let μ = (μ_{1}, …, μ_{ℓ}) be a partition of k and let B(μ) = {μ_{1}+⋯+μ_{r} | 1 ≤ r ≤ ℓ}. Then

q_{μ} = ∑_{i_{1},...,i_{k}} x_{i_{1}} ⋯ x_{i_{k}}wt_{q}^{μ}(i_{1}, …, i_{k})

where the sum is over all 1 ≤ i_{1}, … i_{k} ≤ n,

wt_{q}^{μ}(i_{1}, …, i_{k}) = ∏_{{1≤j≤k \atop j∉B(μ)}} ϕ_{μ}(j; i_{1}, …, i_{k}), and

ϕ_{μ}(j; i_{1}, …, i_{k}) = \{ \begin{matrix}−1, & if i_{j} < i_{j+1}, \\ 0, & if i_{j} ≥ i_{j+1} < i_{j+2} and j + 1 ∉ B(μ), \\ q, & otherwise. \end{matrix}

Proof. The result follows immediately from the previous lemma once we note that with wt_{q}(i_{1}, …, i_{r}) defined as in Lemma 1.5 we have

wt_{q}(i_{1}, …, i_{r}) = ∏_{j=1}^{r} ϕ(j; i_{1}, …, i_{r}), where

ϕ(j; i_{1}, …, i_{r}) = \{ \begin{matrix}−1, & if i_{j} < i_{j+1}, \\ 0, & if i_{j} ≥ i_{j+1} < i_{j+2} and j + 1 ≠ r. \\ q, & otherwise. \end{matrix}

The following corollary follows from the last one by setting q = 1.

Corollary 1.7.

p_{μ} = ∑_{i_{1},...,i_{k}} x_{i_{1}} ⋯ x_{i_{k}}wt_{1}^{μ}(i_{1}, …, i_{k})

where the sum is over all 1 ≤ i_{1}, …, i_{k} ≤ n, and wt_{1}^{μ} is as given in Corollary 1.6 except with q = 1.

2. Insertion

Let us assume that the variables x_{1}, …, x_{n} are ordered so that x_{1} < x_{2} < ⋯ < x_{n}. A column strict tableau of shape λ is a filling of the boxes of the Ferrers diagram of λ with entries from {x_{1}, …, x_{n}} such that

(1) The entries in the rows are weakly increasing, left to right, and

(2) The entries in the columns are increasing, top to bottom.

If P is a column strict tableau let x^{P} be the product of the entries in P. One has s_{λ} = ∑_{P} x^{P}, where the sum is over all column strict tableaux P of shape λ.

The Robinson-Schensted-Knuth (RSK) insertion scheme gives a bijection between sequences (x_{i_{1}}, …, x_{i_{k}}) and pairs (P, Q) where P is a column strict tableau and Q is a standard tableau and P and Q are the same shape. (The original references for the RSK insertion scheme are [Sz], [Sch] and [Kn], for an expository treatment see [Sag]). The pair of tableaux obtained by RSK insertion of the sequence x_{i_{1}}, …, x_{i_{k}} is the pair (P, Q) = (P_{k}, Q) determined recursively by setting

P_{0} = ∅, P_{j} = (P_{j−1} ← x_{i_{j}}), and

the box of Q containing k is the box created upon the insertion of x_{i_{j}} into P_{j−1}. Here P_{j−1} ← x_{i_{j}} denotes the column strict tableau obtained by column insertion of the letter x_{i_{j}} into the column strict tableau P_{j−1}. The following proposition is a well known fact about RSK-insertion.

Proposition 2.1. Let P_{j−1} be a column strict tableau and consider the insertions (P_{j−1} ← x_{i_{j}}) ← x_{i_{j+1}}.

(1) If x_{i_{j}} < x_{i_{j+1}} then the box created upon insertion of x_{i_{j+1}} into P_{j} = (P_{j−1} ← x_{i_{j}}) appears southwest of the box created upon insertion of x_{i_{j}} into P_{j−1}.

(2) If x_{i_{j}} ≥ x_{i_{j+1}} then the box created upon insertion of x_{i_{j+1}} into P_{j} = (P_{j−1} ← x_{i_{j}}) appears northeast of the box created upon insertion of x_{i_{j}} into P_{j−1}.

Our goal now is to prove Roichman’s formula. For each pair of partitions λ, μ ⊢ k define a polynomial η_{q}^{λ}(μ) ∈ ℤ[q] by (the q-version of) the right hand side of Roichman’s formula (0.2), i.e. define

η_{q}^{λ}(μ) = ∑_{Q} rw_{q}^{μ}(Q),  (2.2)

where the sum is over all standard tableaux Q of shape λ and the μ-weight of a standard tableau is as given in (0.3).

Theorem 2.3. If μ ⊢ k, then q_{μ} = ∑_{λ⊢k} η_{q}^{λ}(μ)s_{λ}.

Proof. RSK-insertion of a sequence x_{i_{1}}, …, x_{i_{k}} produces a pair (P, Q) consisting of a column-strict tableau P and a standard tableau Q where the shape λ of the tableau P is a partition with k boxes. Thus RSK-insertion combined with Proposition 2.1 implies the following identity

\begin{aligned}q_{μ} & = ∑_{i_{1},...,i_{k}} x_{i_{1}} ⋯ x_{i_{k}}wt_{q}^{μ}(i_{1}, …, i_{k}) = ∑_{(P,Q)} x^{P} rw_{q}^{μ}(Q) \\ & = ∑_{λ⊢k} (∑_{Q} rw_{q}^{μ}(Q)) (∑_{P} x^{P} ) = ∑_{λ⊢k} η_{q}^{λ}(μ)s_{λ}. \end{aligned}

In view of the previous theorem we have that (1.3) is equivalent to Roichman’s theorem where Roichman’s theorem is the statement that

χ_{q}^{λ}(μ) = η_{q}^{λ}(μ).

We get the following corollary of Theorem 2.3 by setting q = 1.

Corollary 2.4.

(a) If μ ⊢ k then p_{μ} = ∑_{λ⊢k} η_{1}^{λ}(μ)s_{λ}.

(b) For λ, μ ⊢ k the character of the symmetric group S_{k} associated to the partition λ evaluated at an element of cycle type μ is given by

χ^{λ}(μ) = ∑_{Q} rw_{1}^{μ}(Q),

where the sum is over all standard tableaux Q of shape λ and rw_{1}^{μ}(Q) is as given in (0.3) except with q = 1.

3. References

[Kn] D.E. Knuth, Permutations, matrices and generalized Young tableaux, Pacific J. Math. 34, No. 3 (1970).

[Mac] I.G. Macdonald, “Symmetric Functions and Hall Polynomials”, Second Edition, Oxford Univ. Press, Oxford, 1995.

[Ra] A. Ram, A Frobenius formula for the characters of the Hecke algebras, Invent. Math. 106 (1991), 461-488.

[Ro] Y. Roichman, A recursive rule for Kazhdan-Lusztig characters, preprint 1996.

[Sag] B. Sagan, “The symmetric group”, Wadsworth and Brooks, Pacific Grove, California, 1991.

[Sch] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179-191.

[Sz] M.P. Schützenberger, La correspondance de Robinson, in “Combinatoire et Représentation du Groupe Symétrique”, 1976 (D. Foata, Ed.), 59-113. Lecture Notes in Math. 579 Springer-Verlag, 1977.

[Wh] D. White, A bijection proving the orthogonality of the characters of S_{n}, Advances in Math. 50 (1983), 160-186.