Foulkes characters, Eulerian idempotents, and an amazing matrix
Persi Diaconis
and Jason Fulman
Department of Mathematics, Stanford University, Stanford, CA, USA
DOI: 10.1007/s10801-012-0343-7
Abstract
John Holte (Am. Math. Mon. 104:138-149, 1997) introduced a family of “amazing matrices” which give the transition probabilities of “carries” when adding a list of numbers. It was subsequently shown that these same matrices arise in the combinatorics of the Veronese embedding of commutative algebra (Brenti and Welker, Adv. Appl. Math. 42:545-556, 2009; Diaconis and Fulman, Am. Math. Mon. 116:788-803, 2009; Adv. Appl. Math. 43:176-196, 2009) and in the analysis of riffle shuffling (Diaconis and Fulman, Am. Math. Mon. 116:788-803, 2009; Adv. Appl. Math. 43:176-196, 2009). We find that the left eigenvectors of these matrices form the Foulkes character table of the symmetric group and the right eigenvectors are the Eulerian idempotents introduced by Loday (Cyclic Homology, 1992) in work on Hochschild homology. The connections give new closed formulae for Foulkes characters and allow explicit computation of natural correlation functions in the original carries problem.
Pages: 425–440
Keywords: foulkes character; carry; Eulerian idempotent; symmetric group
Full Text: PDF
References
Aguiar, M., Andre, C., Benedetti, C., Bergeron, N., Chen, Z., Diaconis, P., Hendrickson, A., Hsiao, S., Isaacs, I.M., Jedwab, A., Johnson, K., Karaali, G., Lauve, A., Le, T., Lewis, S., Li, H., Magaard, K., Marberg, E., Novelli, J., Pang, A., Saliola, F., Tevlin, L., Thibon, J., Thiem, N., Venkateswaran, V., Vinroot, C.R., Yan, N., Zabrocki, M.: Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras. Adv. Math. (2010, to appear). ArXiv e-prints 1009.4134 Bayer, D., Diaconis, P.: Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2, 294-313 (1992) CrossRef Billera, L.J., Thomas, H., van Willigenburg, S.: Decomposable compositions, symmetric quasisymmetric functions and equality of ribbon Schur functions. Adv. Math. 204, 204-240 (2006). doi:10.1016/j.aim.2005.05.014 CrossRef Brenti, F., Welker, V.: The Veronese construction for formal power series and graded algebras. Adv. Appl. Math. 42, 545-556 (2009). doi:10.1016/j.aam.2009.01.001 CrossRef Carlitz, L., Kurtz, D., Scoville, R., Stackelberg, O.: Asymptotic properties of Eulerian numbers. Z. Wahrscheinlichkeitstheor. Verw. Geb. 23, 47-54 (1972) CrossRef Denham, G.: Eigenvectors for a random walk on a hyperplane arrangement. Adv. Appl. Math. (2010, to appear). ArXiv e-prints 1010.0232 Diaconis, P., Fulman, J.: Carries, shuffling, and an amazing matrix. Am. Math. Mon. 116, 788-803 (2009a). doi:10.4169/000298909X474864 CrossRef Diaconis, P., Fulman, J.: Carries, shuffling, and symmetric functions. Adv. Appl. Math. 43, 176-196 (2009b). doi:10.1016/j.aam.2009.02.002 CrossRef Diaconis, P., McGrath, M., Pitman, J.: Riffle shuffles, cycles, and descents. Combinatorica 15, 11-29 (1995) CrossRef Diaconis, P., Pang, A., Ram, A.: Hopf algebras and Markov chains: two examples and a theory. Preprint, Department of Mathematics, Stanford University (2011) Foulkes, H.O.: Eulerian numbers, Newcomb's problem and representations of symmetric groups. Discrete Math. 30, 3-49 (1980). doi:10.1016/0012-$365X(80)90061$-8 CrossRef Fulman, J.: Applications of symmetric functions to cycle and increasing subsequence structure after shuffles. J. Algebr. Comb. 16, 165-194 (2002) CrossRef Garsia, A.M., Reutenauer, C.: A decomposition of Solomon's descent algebra. Adv. Math. 77, 189-262 (1989). doi:10.1016/0001-$8708(89)90020$-0 CrossRef Gerstenhaber, M., Schack, S.D.: A Hodge-type decomposition for commutative algebra cohomology. J. Pure Appl. Algebra 48, 229-247 (1987). doi:10.1016/0022-$4049(87)90112$-5 CrossRef Gessel, I.M., Reutenauer, C.: Counting permutations with given cycle structure and descent set. J. Comb. Theory, Ser. A 64, 189-215 (1993). doi:10.1016/0097-$3165(93)90095$-P CrossRef Hanlon, P.: The action of Sn on the components of the Hodge decomposition of Hochschild homology. Mich. Math. J. 37, 105-124 (1990) CrossRef Holte, J.M.: Carries, combinatorics, and an amazing matrix. Am. Math. Mon. 104, 138-149 (1997) CrossRef Kerber, A.: Applied Finite Group Actions. Algorithms and Combinatorics, vol. 19, 2nd edn. Springer, Berlin (1999) Kerber, A., Thürlings, K.-J.: Eulerian numbers, Foulkes characters and Lefschetz characters of S $_{ n }$. Sémin. Lothar. 8, 31-36 (1984) Lascoux, A., Pragacz, P.: Ribbon Schur functions. Eur. J. Comb. 9, 561-574 (1988) Loday, J.-L.: Cyclic Homology. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol.
301. Springer, Berlin (1992). Appendix E by María O. Ronco Macdonald, I.G.: Symmetric Functions and Hall Polynomials, 2nd edn. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York (1995). With contributions by A. Zelevinsky, Oxford Science Publications Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and an amazing matrix. ArXiv e-prints 1110.3209 (2011) Patras, F.: Construction géométrique des idempotents Eulériens. Filtration des groupes de polytopes et des groupes d'homologie de Hochschild. Bull. Soc. Math. Fr. 119, 173-198 (1991) Solomon, L.: A decomposition of the group algebra of a finite Coxeter group. J. Algebra 9, 220-239 (1968) CrossRef Stanley, R.P.: Enumerative Combinatorics, vol.
1. Cambridge Studies in Advanced Mathematics, vol.
49. Cambridge University Press, Cambridge (1997). With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original CrossRef Stanley, R.P.: Enumerative Combinatorics, vol.
2. Cambridge Studies in Advanced Mathematics, vol.
62. Cambridge University Press, Cambridge (1999). With a foreword by Gian-Carlo Rota and Appendix 1 by Sergey Fomin CrossRef Stanley, R.P.: Alternating permutations and symmetric functions. J. Comb. Theory, Ser. A 114, 436-460 (2007). doi:10.1016/j.jcta.2006.06.008 CrossRef Weibel, C.A.: An Introduction to Homological Algebra. Cambridge Studies in Advanced Mathematics, vol.
38. Cambridge University Press, Cambridge (1994)
301. Springer, Berlin (1992). Appendix E by María O. Ronco Macdonald, I.G.: Symmetric Functions and Hall Polynomials, 2nd edn. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York (1995). With contributions by A. Zelevinsky, Oxford Science Publications Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and an amazing matrix. ArXiv e-prints 1110.3209 (2011) Patras, F.: Construction géométrique des idempotents Eulériens. Filtration des groupes de polytopes et des groupes d'homologie de Hochschild. Bull. Soc. Math. Fr. 119, 173-198 (1991) Solomon, L.: A decomposition of the group algebra of a finite Coxeter group. J. Algebra 9, 220-239 (1968) CrossRef Stanley, R.P.: Enumerative Combinatorics, vol.
1. Cambridge Studies in Advanced Mathematics, vol.
49. Cambridge University Press, Cambridge (1997). With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original CrossRef Stanley, R.P.: Enumerative Combinatorics, vol.
2. Cambridge Studies in Advanced Mathematics, vol.
62. Cambridge University Press, Cambridge (1999). With a foreword by Gian-Carlo Rota and Appendix 1 by Sergey Fomin CrossRef Stanley, R.P.: Alternating permutations and symmetric functions. J. Comb. Theory, Ser. A 114, 436-460 (2007). doi:10.1016/j.jcta.2006.06.008 CrossRef Weibel, C.A.: An Introduction to Homological Algebra. Cambridge Studies in Advanced Mathematics, vol.
38. Cambridge University Press, Cambridge (1994)