Linear equivalence and identical Young tableau bijections for the conjugation symmetry of Littlewood-Richardson coefficients

Linear equivalence and identical Young tableau bijections for the conjugation symmetry of

Littlewood-Richardson coefficients

O. Azenhas, A. Conflitti, R. Mamede

CMUC

Centre for Mathematics, University of Coimbra

March 31, 2008

Overview

1 The conjugation symmetry map

2 Calculus on words and tableaux

3 Hanlon-Sundaram bijectionξ^HS, Benkart-Sottile-Stroomer bijection ξ^BSS, and Azenhas-Zaballa bijectionξ^AZ

4 Linear equivalence

[HS] Philip Hanlon, Sheila Sundaram, On a bijection between

Littlewood-Richardson fillings of conjugate shape J. Combin. Theory Ser. A 60 (1992), no. 1, 1–18.

[BSS] Georgia Benkart, Frank Sottile, Jeffrey Stroomer, Tableau switching:

algorithms and applications, J. of Combin. Theory Ser. A 76 (1996), no.1, 11–34.

[Z] Ion Zaballa, Increasing and decreasing Littlewood-Richardson sequences and duality, preprint, University of Basque Country, 1996.

[A] Olga Azenhas, The admissible interval for the invariant factors of a product of matrices, Linear and Multilinear Algebra 46 (1999), no. 1-2, 51–99.

[PV] Igor Pak, Ernesto Vallejo, Reductions of Young tableau bijections, available

1. Conjugation symmetry map

ν= (4,3,2) = ^partition,Y(ν) =¹¹¹¹222

33 Yamanouchi tableau µ= (2)⊆λ= (5,3,3), λ/µ=, (λ/µ)^t :=λ^t/µ^t =

T =122¹¹¹

233 , w(T) =111221332 lattice permutation T ≡^k Y(ν)if and only ifw(T)is a lattice permutation

ξ:LR(λ/µ, ν) −→ LR(λ^t/µ^t, ν^t) T 7→ ξ(T) = [Y(ν^t)]_k∩[bT^t]_d

2. Calculus on words and tableaux

λ/µ=

LR-readingλ/µ: 6 5 4^{3 2 1}

9 8 7 , column LR-readingλ/µ: 8 6 4^{3 2 1} 9 7 5 α_λ/µ= (5 6 8 7)∈ S₈

T =¹²²¹¹¹

233 , w(T) =111221332, w_col(T) =111232312 P(w(T)) =P(w_col(T)) =Y(ν) =¹¹¹¹222

33

Q(w(T)) =¹²³⁶459

78 , Q(w_col(T)) =¹²³⁸469 57 T tableau,

(i)w(T)≡^k w_col(T).

(ii)α_λ/µQ(w(T)) =Q(w_col(T))[Fulton, Young Tableaux, Appendix A.3].

Tableau switching

LetT = 2 2¹

3 4 , with shapeλ/µand letS =^{1 1}₂ with shapeµover the alphabet{1,2}.

S∪T =^{1 1}22 2¹ 3 4

−→s A ∪B =^{1 2}2 4¹2 31 . Note: S =Bⁿ andA =Tⁿ.

Theorem (BSS) S ∪T →^s A ∪B. Then:

(i)A andB are tableaux, the shape ofA is the inner shape ofB. (ii)A ∪B has the same shape asS∪T.

(iii)B ≡^k S andA ≡^k T. (v)A ∪B →^s S∪T.

Tableau switching

LetT = 2 2¹

3 4 , with shapeλ/µand letS =^{1 1}₂ with shapeµover the alphabet{1,2}.

S∪T =^{1 1}22 2¹ 3 4

−→s A ∪B =^{1 2}2 4¹2 31 . Note: S =Bⁿ andA =Tⁿ.

Theorem (BSS) S ∪T →^s A ∪B. Then:

(i)A andB are tableaux, the shape ofA is the inner shape ofB.

(ii)A ∪B has the same shape asS∪T. (iii)B ≡^k S andA ≡^k T.

(v)A ∪B →^s S∪T.

Dual Knuth equivalence

Two tableauxT andUof the same shape are dual equivalent,T ≡^d U, if any sequence of jeu de taquin slides that can be applied to one of them can also be applied to the other, and the sequence of shape changes is the same for both.

T = ² 1 3 6

4 5 7 −→ 1 3^{2 6} 4 5 7

U= ¹ 2 2 2

3 3 4 −→ 2 2^{1 2} 3 3 4

Theorem

LetT andUbe tableaux of the same shape. Then,T ≡^d Uif and only if Q(w(T)) =Q(w(U)).

Corollary

Two tableaux of the same normal shape are dual equivalent.

Theorem (Haiman1992)

LetT andQ be tableaux with the same normal shape and letW be a tableau whose inner shape is the shape ofT. Then,

T∪W →^s Z∪X Q∪W→^s Z ∪Y











⇒ X ≡^d Y

Knuth and dual Knuth equivalence

Theorem (Haiman1992)

LetDbe a dual Knuth equivalence class andK be a Knuth equivalence class, both corresponding to the same normal shape. Then, there is a unique tableau inD ∩ K.

Algorithm to constructD ∩ K:

LetU ∈ Dand letV ∈ K be the only tableau with normal shape in this class.

W∪U W∪X

s↓ ↑s

Uⁿ∪Z → V∪Z X ≡^d UandX ≡^k V.

D ∩ K ={X}.

BSS bijection

ξ^BSS : LR(λ/µ, ν) → LR(λ^t/µ^t, ν^t) T 7→ ξ^BSS(T)∈[Y(ν^t)]K∩[bT^t]d

(1) T =1 2 2^{1 1 1}

2 3 3 →bT =1 6 7^{2 3 4}

5 8 9 →bT^t = 1 5 6 8 2 7 9 3 4

, ν= (4,3,2) (2)

W∪bT^t = 11 5 26 8 2 7 9 34

11 1 22 2 1 3 3 24

=W∪ξ^BSS(T)

s↓ ↑s

(bT^t)ⁿ∪Z = 1 5 8 2 6 9 3 71 4 2

−→

1 1 1 2 2 2 3 31 4 2

=Y(ν^t)∪Z

Evacuation and reversal

λ/µ=

rotate

←→ (λ/µ)^∗=

Dual word: givenw =w₁w₂· · ·w_{`</sub> ∈ {1, . . . ,t}<sup>∗</sup>letw<sup>∗</sup>:=w<sub>`}^∗· · ·w₂^∗w₁^∗, wherei^∗=t −i+1.

w =1113213↔^∗ w^∗=1321333

S = 1 2 3^{1 1 1} 3

rotate

←→ 3 2 1³ 1 1 1

↔∗ S^∗= 1 2 3¹ 3 3 3

T =^{1 1 2}2 3 3

rotate

←→

3 3 2 2 1 1

↔∗ T^∗= 1 2¹ 2 3 3

Evacuation: T tableau of normal shape,T^E:=T^∗n

T^E =T^a∗

Sch ¨utzenberger involution

Evacuation and reversal

λ/µ=

rotate

←→ (λ/µ)^∗=

Dual word: givenw =w₁w₂· · ·w_{`</sub> ∈ {1, . . . ,t}<sup>∗</sup>letw<sup>∗</sup>:=w<sub>`}^∗· · ·w₂^∗w₁^∗, wherei^∗=t −i+1.

w =1113213↔^∗ w^∗=1321333

S = 1 2 3^{1 1 1} 3

rotate

←→ 3 2 1³ 1 1 1

↔∗ S^∗= 1 2 3¹ 3 3 3

T =^{1 1 2}2 3 3

rotate

←→

3 3 2 2 1 1

↔∗ T^∗= 1 2¹

2 3 3→T^∗n =^{1 1 3}2 2 3

Evacuation: T tableau of normal shape,T^E:=T^∗n

T^E =T^a∗

Sch ¨utzenberger involution

Evacuation and reversal

λ/µ=

rotate

←→ (λ/µ)^∗=

Dual word: givenw =w₁w₂· · ·w_{`</sub> ∈ {1, . . . ,t}<sup>∗</sup>letw<sup>∗</sup>:=w<sub>`}^∗· · ·w₂^∗w₁^∗, wherei^∗=t −i+1.

w =1113213↔^∗ w^∗=1321333

S = 1 2 3^{1 1 1} 3

rotate

←→ 3 2 1³ 1 1 1

↔∗ S^∗= 1 2 3¹ 3 3 3

T =^{1 1 2}2 3 3

rotate

←→

3 3 2 2 1 1

↔∗ T^∗= 1 2¹

2 3 3→T^∗n =^{1 1 3}2 2 3

Evacuation: T tableau of normal shape,T^E:=T^∗n T^E =T^a∗

Sch ¨utzenberger involution

Reversal: T tableau of any shape,T^eis the only tableau in[T^∗]_k ∩[T]_d Note: [T^∗]_k∩[T]_d = [T^nE]_k∩[T]_d. IfT has normal shape thenT^E =T^e. Reversal in the case of LR tableaux:

•Crystal reflection operators on lattice permutations

w =1(1(12)2)(1332)→^σ1 σ₁(w) =211221332 Q(w) =Q(σ₁(w))

σ0(w) =σ1σ2σ1(w) =311222333 σ₀(Y) =Y^E

T =1 2 2^{1 1 1} 2 3 3

−→e 2 2 2^{1 1 3} 3 3 3 =T^e

Note: In general,σ₀(w).^{k w∗}

Reversal: T tableau of any shape,T^eis the only tableau in[T^∗]_k ∩[T]_d Note: [T^∗]_k∩[T]_d = [T^nE]_k∩[T]_d. IfT has normal shape thenT^E =T^e. Reversal in the case of LR tableaux:

•Crystal reflection operators on lattice permutations

w =1(1(12)2)(1332)→^σ1 σ₁(w) =211221332 Q(w) =Q(σ₁(w))

σ₀(w) =σ₁σ₂σ₁(w) =311222333≡^k w^∗=211322333 σ₀(Y) =Y^E

T =1 2 2^{1 1 1} 2 3 3

−→e 2 2 2^{1 1 3} 3 3 3 =T^e

Note: In general,σ₀(w).^{k w∗}

Jeu de taquin on two row/column tableaux

^{1 3}

1 2 3 4 ! ¹³ 1 2 3 4

←→θ ^{1 1 3 3}

²⁴ !^{1 1 3 3} 2 4

T =1 2 2^{1 1 1}

2 3 3 , LR-reading:

3 2 1 6 5 4

9 8 7 , Q(w(T)) =L =^{1 2 3 6}4 5 9 7 8

θ₀(L) =θ₁θ₂θ₁(L) =L^a = 4 5 6^{2 3}

1 7 8 9↔T^e =2 2 2^{1 1 3} 3 3 3

T ↔ σ₀(T) ↔ T^e

l l l

L ↔ θ₀(L) ↔ L^a

λ/µ=

rotate

−→ (λ/µ)^∗=

−→t (λ/µ) := (λ/µ)^∗t =

Zaballa map: operationon lattice permutation words:

w =111221332−→ w =123124123

U= ^{1 1 1}2 2 2 1 3 3

→ ^{3 2 1}3 2 1 4 2 1

−→t rotate

1 12 2 1 3 3 2 4

=U

w_col(U) =w(U) Lemma

[Y(ν)]_k → [Y(ν^t)]_k

w 7→ w such thatw ≡^k Y(ν^t)andQ(w) =Q(w)^t.

ξ

and ξ

T −→ T^e −→ T^e∗=U −→ U

Q(T) =L −→ L^a −→ L^E −→ (α_(λ/µ)^∗L^E)^t

where(L^a)^∗=L^E =Q(U)and

Q(U)=Q(w_col(U))^t = (α_(λ/µ)^∗Q(U))^t =(α_(λ/µ)^∗Q(T)^E)^t

(α_(λ/µ)^∗Q(T)^E)^t = ((α_λ/µQ(T))^E)^t = (Q(w_col(T))^E)^t = (Q(w_col(bT))^E)^t = Q(w_col(bT)^rev) =Q(bT^t)

Theorem

Given the LR tableauT of shapeλ/µand weightν,ξ^SH(T) =ξ^AZ(T)is the unique tableau Knuth equivalent toY(ν^t)and dual equivalent tobT^t,

ξ^X :LR(λ/µ, ν) −→ LR(λ^t/µ^t, ν^t) T 7→ ξ^X(T)∈[Y(ν^t)]_k∩[bT^t]_d

Linear equivalence

I. Pak, E. Vallejo, Reductions of Young tableau bijections, available at arXiv:math/0408171

We view a bijectionτ:A −→ Bas an algorithm which inputsA ∈ Aand outputsB =τ(A)∈ B. The computational complexity is, roughly, the number of steps in the bijection.

αreduces linearly toβ: α ,→β⇔C(α)≤aC(β) +b αlinear equivalent toβ: α∼β⇔α ,→β ,→α

D = (d₁, . . . ,d_n)array of integers,m=m(D) :=max_id_i. Thebit–sizeof D, denoted byhDi, is the amount of space required to storeD; for simplicity from now on we assume thathDi=ndlog₂m+1e.

Elementary circuits

Supposeδ₁ :A₁ −→ X₁,γ:X₁−→ X₂andδ₂ :X₂−→ B, such that δ₁andδ₂have linear cost, and considerχ=δ₂◦γ◦δ₁ :A −→ B. We call this circuittrivialand denote it byI(δ₁, γ, δ₂).

Supposeγ₁ :A −→ Xandγ₂ :X −→ B, and let

χ=γ₂◦γ₁ :A −→ B. We call this circuitsequentialand denote it by S(γ₁, γ₂).

Supposeδ₁ :A −→ X₁× X₂,γ₁ :X₁ −→ Y₁,γ₂ :X₂ −→ Y₂, and δ₁:Y₁× Y₂ −→ B, such thatδ₁andδ₁have linear cost. Consider χ=δ₂◦(γ₁×γ₂)◦δ₁:A −→ B: we call this circuitparalleland denote it byP(δ1, γ1, γ2, δ2).

Parallel-sequencial circuits

For a fixed bijectionα, we say thati^{is an}α–based ps–circuitif one of the following holds:

i=δ, whereδis a bijection having linear cost.

i=I(δ₁, α, δ₂), whereδ₁, δ₂are bijections having linear cost.

i=P(δ₁, γ₁, γ₂, δ₂), whereγ₁, γ₂ areα–based ps–circuits andδ₁, δ₂ are bijections having linear cost.

i=S(γ₁, γ₂), whereγ₁, γ₂ areα–based ps–circuits.

A mapβislinearly reducibletoα, writeβ ,→α, if there exist a finite α–based ps-circuitiwhich computesβ. We say that mapsαandβare linearly equivalent, writeα∼β, ifαis linearly reducible toβ, andβis linearly reducible toα.

Theorem (PV)

The following maps are linearly equivalent:

(1)RSK correspondence.

(2)Jeu de Taquin map.

(3)Littlewood-Robinson map.

(4)Tableau switching maps.

(5)Evacuation for normal shapes (Sch ¨utzenberger involution)E.

(6)Reversale.

(7)First and Second Fundamental Symmetry mapsρ₁ andρ₂.

Theorem

(8)First and Second Fundamental Symmetry mapsρ₁ andρ₂are identical [Danilov-Koshevoy].

(9)First and Third Fundamental Symmetry mapsρ1andρ3are identical [A.].

(10)ξ^AZ,ξ^BSS,ξ^HSare identical and ξ^AZ ,→E :T ^RSK→ L →^E L^{E RSK}

−1

→ U→U_k ◦ · · · ◦U₁ ^RSK→ Q(w_col(U))→ Q(w_col(U))^{t RSK}

−1

→ U.

Theorem (PV)

The following maps are linearly equivalent:

(1)RSK correspondence.

(2)Jeu de Taquin map.

(3)Littlewood-Robinson map.

(4)Tableau switching maps.

(5)Evacuation for normal shapes (Sch ¨utzenberger involution)E.

(6)Reversale.

(7)First and Second Fundamental Symmetry mapsρ₁ andρ₂. Theorem

(8)First and Second Fundamental Symmetry mapsρ₁ andρ₂are identical [Danilov-Koshevoy].

(9)First and Third Fundamental Symmetry mapsρ1andρ3are identical [A.].

(10)ξ^AZ,ξ^BSS,ξ^HSare identical and

ξ^AZ ,→E :T ^RSK→ L →^E L^{E RSK}

−1

→ U→U_k ◦ · · · ◦U₁ ^RSK→ Q(w_col(U))→ Q(w_col(U))^{t RSK}

−1

→ U.

Theorem (PV)

The following maps are linearly equivalent:

(1)RSK correspondence.

(2)Jeu de Taquin map.

(3)Littlewood-Robinson map.

(4)Tableau switching maps.

(5)Evacuation for normal shapes (Sch ¨utzenberger involution)E.

(6)Reversale.

(7)First and Second Fundamental Symmetry mapsρ₁ andρ₂. Theorem

(8)First and Second Fundamental Symmetry mapsρ₁ andρ₂are identical [Danilov-Koshevoy].

(9)First and Third Fundamental Symmetry mapsρ1andρ3are identical [A.].

(10)ξ^AZ,ξ^BSS,ξ^HSare identical and ξ^AZ ,→E :T ^RSK→ L →^E L^{E RSK}

−1

→ U→U_k ◦ · · · ◦U₁ ^RSK→ Q(w_col(U))→

−1