Tropical representations and identities of plactic monoids

Johnson, Marianne; Kambites, Mark

doi:10.1090/tran/8355

Tropical representations and identities of plactic monoids
HTML articles powered by AMS MathViewer

by Marianne Johnson and Mark Kambites PDF

Trans. Amer. Math. Soc. 374 (2021), 4423-4447 Request permission

Abstract:

We exhibit a faithful representation of the plactic monoid of every finite rank as a monoid of upper triangular matrices over the tropical semiring. This answers a question first posed by Izhakian and subsequently studied by several authors. A consequence is a proof of a conjecture of Kubat and Okniński that every plactic monoid of finite rank satisfies a non-trivial semigroup identity. In the converse direction, we show that every identity satisfied by the plactic monoid of rank $n$ is satisfied by the monoid of $n \times n$ upper triangular tropical matrices. In particular this implies that the variety generated by the $3 \times 3$ upper triangular tropical matrices coincides with that generated by the plactic monoid of rank $3$, answering another question of Izhakian.

References

Marianne Akian, Stéphane Gaubert, and Alexander Guterman, Tropical polyhedra are equivalent to mean payoff games, Internat. J. Algebra Comput. 22 (2012), no. 1, 1250001, 43. MR 2900854, DOI 10.1142/S0218196711006674
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig, Tropicalizing the simplex algorithm, SIAM J. Discrete Math. 29 (2015), no. 2, 751–795. MR 3336300, DOI 10.1137/130936464
Alan J. Cain, Robert D. Gray, and António Malheiro, Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids, J. Algebra 423 (2015), 37–53. MR 3283708, DOI 10.1016/j.jalgebra.2014.09.037
Alan J. Cain, Robert D. Gray, and António Malheiro, Crystal monoids & crystal bases: rewriting systems and biautomatic structures for plactic monoids of types $A_n$, $B_n$, $C_n$, $D_n$, and $G_2$, J. Combin. Theory Ser. A 162 (2019), 406–466. MR 3876235, DOI 10.1016/j.jcta.2018.11.010
Alan J. Cain and António Malheiro, Identities in plactic, hypoplactic, sylvester, Baxter, and related monoids, Electron. J. Combin. 25 (2018), no. 3, Paper No. 3.30, 19. MR 3853882, DOI 10.37236/6873
A. J. Cain, G. Klein, L. Kubat, A. Malheiro and J. Okniński. A note on identities in plactic monoids and monoids of upper-triangular tropical matrices. Preprint at arXiv:1705.04596.
Alan J. Cain, António Malheiro, and Fábio M. Silva, The monoids of the patience sorting algorithm, Internat. J. Algebra Comput. 29 (2019), no. 1, 85–125. MR 3918055, DOI 10.1142/S0218196718500649
Ferran Cedó, Łukasz Kubat, and Jan Okniński, Irreducible representations of the plactic algebra of rank four, J. Algebra 488 (2017), 403–441. MR 3680925, DOI 10.1016/j.jalgebra.2016.03.046
Filip Cools, Jan Draisma, Sam Payne, and Elina Robeva, A tropical proof of the Brill-Noether theorem, Adv. Math. 230 (2012), no. 2, 759–776. MR 2914965, DOI 10.1016/j.aim.2012.02.019
Laure Daviaud, Marianne Johnson, and Mark Kambites, Identities in upper triangular tropical matrix semigroups and the bicyclic monoid, J. Algebra 501 (2018), 503–525. MR 3768147, DOI 10.1016/j.jalgebra.2017.12.032
William Fulton, Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR 1464693
Jeffrey Giansiracusa and Noah Giansiracusa, Equations of tropical varieties, Duke Math. J. 165 (2016), no. 18, 3379–3433. MR 3577368, DOI 10.1215/00127094-3645544
S. Margolis and B. Steinberg, The algebra of the Catalan monoid as an incidence algebra: A simple proof, Preprint at arXiv:1806.06531.
Pierre Guillon, Zur Izhakian, Jean Mairesse, and Glenn Merlet, The ultimate rank of tropical matrices, J. Algebra 437 (2015), 222–248. MR 3351964, DOI 10.1016/j.jalgebra.2015.02.026
Christopher Hollings and Mark Kambites, Tropical matrix duality and Green’s $\scr D$ relation, J. Lond. Math. Soc. (2) 86 (2012), no. 2, 520–538. MR 2980923, DOI 10.1112/jlms/jds015
Zur Izhakian, Semigroup identities in the monoid of triangular tropical matrices, Semigroup Forum 88 (2014), no. 1, 145–161. MR 3164156, DOI 10.1007/s00233-013-9507-6
Zur Izhakian and Stuart W. Margolis, Semigroup identities in the monoid of two-by-two tropical matrices, Semigroup Forum 80 (2010), no. 2, 191–218. MR 2601760, DOI 10.1007/s00233-009-9203-8
Zur Izhakian, Semigroup identities of tropical matrix semigroups of maximal rank, Semigroup Forum 92 (2016), no. 3, 712–732. MR 3500264, DOI 10.1007/s00233-015-9765-6
Zur Izhakian, Tropical plactic algebra, the cloaktic monoid, and semigroup representations, J. Algebra 524 (2019), 290–366. MR 3908267, DOI 10.1016/j.jalgebra.2018.12.014
Zur Izhakian, Marianne Johnson, and Mark Kambites, Pure dimension and projectivity of tropical polytopes, Adv. Math. 303 (2016), 1236–1263. MR 3552549, DOI 10.1016/j.aim.2016.08.033
Zur Izhakian, Marianne Johnson, and Mark Kambites, Tropical matrix groups, Semigroup Forum 96 (2018), no. 1, 178–196. MR 3750353, DOI 10.1007/s00233-017-9894-1
Marianne Johnson and Peter Fenner, Identities in unitriangular and gossip monoids, Semigroup Forum 98 (2019), no. 2, 338–354. MR 3917968, DOI 10.1007/s00233-019-09996-x
Marianne Johnson and Mark Kambites, Green’s $\scr {J}$-order and the rank of tropical matrices, J. Pure Appl. Algebra 217 (2013), no. 2, 280–292. MR 2969253, DOI 10.1016/j.jpaa.2012.06.003
Marianne Johnson and Ngoc Mai Tran, Geometry and algorithms for upper triangular tropical matrix identities, J. Algebra 530 (2019), 470–507. MR 3957959, DOI 10.1016/j.jalgebra.2019.03.024
M. Kambites, Free objects in triangular matrix varieties and quiver algebras over semirings, Preprint at arXiv:1904.06094.
M. Kashiwara, On crystal bases of the $Q$-analogue of universal enveloping algebras, Duke Math. J. 63 (1991), no. 2, 465–516. MR 1115118, DOI 10.1215/S0012-7094-91-06321-0
Donald E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727. MR 272654
Łukasz Kubat and Jan Okniński, Plactic algebra of rank 3, Semigroup Forum 84 (2012), no. 2, 241–266. MR 2898759, DOI 10.1007/s00233-011-9337-3
Łukasz Kubat and Jan Okniński, Gröbner-Shirshov bases for plactic algebras, Algebra Colloq. 21 (2014), no. 4, 591–596. MR 3266510, DOI 10.1142/S1005386714000534
Łukasz Kubat and Jan Okniński, Identities of the plactic monoid, Semigroup Forum 90 (2015), no. 1, 100–112. MR 3297811, DOI 10.1007/s00233-014-9609-9
Alain Lascoux and Marcel-Paul Schützenberger, Sur une conjecture de H. O. Foulkes, C. R. Acad. Sci. Paris Sér. A-B 286 (1978), no. 7, A323–A324 (French, with English summary). MR 472993
Alain Lascoux and Marcel-P. Schützenberger, Le monoïde plaxique, Noncommutative structures in algebra and geometric combinatorics (Naples, 1978) Quad. “Ricerca Sci.”, vol. 109, CNR, Rome, 1981, pp. 129–156 (French, with Italian summary). MR 646486
M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski; With a preface by Berstel and Perrin. MR 1905123, DOI 10.1017/CBO9781107326019
Grigory Mikhalkin, Enumerative tropical algebraic geometry in $\Bbb R^2$, J. Amer. Math. Soc. 18 (2005), no. 2, 313–377. MR 2137980, DOI 10.1090/S0894-0347-05-00477-7
Jan Okniński, Identities of the semigroup of upper triangular tropical matrices, Comm. Algebra 43 (2015), no. 10, 4422–4426. MR 3366585, DOI 10.1080/00927872.2014.946141
J. Okniński, Plactic monoids satisfy nontrivial identities, Preprint at arXiv:1902.06251v2. Retraction notice at arXiv:1902.06251v3.
Jean-Eric Pin, Tropical semirings, Idempotency (Bristol, 1994) Publ. Newton Inst., vol. 11, Cambridge Univ. Press, Cambridge, 1998, pp. 50–69. MR 1608374, DOI 10.1017/CBO9780511662508.004
C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179–191. MR 121305, DOI 10.4153/CJM-1961-015-3
M.-P. Schützenberger, La correspondance de Robinson, Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976) Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977, pp. 59–113 (French). MR 0498826
Yaroslav Shitov, The complexity of tropical matrix factorization, Adv. Math. 254 (2014), 138–156. MR 3161095, DOI 10.1016/j.aim.2013.12.013
Imre Simon, On semigroups of matrices over the tropical semiring, RAIRO Inform. Théor. Appl. 28 (1994), no. 3-4, 277–294. MR 1282449, DOI 10.1051/ita/1994283-402771
M. Taylor, On upper triangular tropical matrix semigroups, tropical matrix identities and T-modules, Ph.D. thesis, University of Manchester, 2017.