×

Inverse semigroup spectral analysis for partially ranked data. (English) Zbl 1297.62197

Summary: Motivated by the notion of symmetric group spectral analysis developed by Diaconis, we introduce the notion of spectral analysis on the rook monoid (also called the symmetric inverse semigroup), characterize its output in terms of symmetric group spectral analysis, and provide an application to the statistical analysis of partially ranked (voting) data. We also discuss generalizations to arbitrary finite inverse semigroups. This paper marks the first non-group semigroup development of spectral analysis.

MSC:

62M15 Inference from stochastic processes and spectral analysis
62F07 Statistical ranking and selection procedures
20M18 Inverse semigroups
91B14 Social choice
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baum, U., Existence and efficient construction of fast Fourier transforms for supersolvable groups, Comput. Complexity, 1, 3, 235-256 (1992) · Zbl 0778.65092
[2] Chevalley, C., Fundamental Concepts of Algebra (1956), Academic Press Inc. · Zbl 0074.01502
[3] Clausen, M.; Baum, U., Fast Fourier transforms for symmetric groups: Theory and implementation, Math. Comp., 61, 204, 833-847 (1993) · Zbl 0804.20007
[4] Clifford, A. H.; Preston, G. B., The Algebraic Theory of Semigroups, vol. 1, Math. Surveys, vol. 7 (1961), AMS: AMS Providence, RI · Zbl 0111.03403
[5] Cooley, J. W.; Tukey, J. W., An algorithm for machine calculation of complex Fourier series, Math. Comp., 19, 297-301 (1965) · Zbl 0127.09002
[6] Diaconis, P., A generalization of spectral analysis with application to ranked data, Ann. Statist., 17, 3, 949-979 (1989) · Zbl 0688.62005
[7] Diaconis, P.; Rockmore, D., Efficient computation of isotypic projections for the symmetric group, (DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11 (1993), AMS), 87-104 · Zbl 0826.20019
[8] Farb, B.; Dennis, R. K., Noncommutative Algebra, Grad. Texts in Math., vol. 144 (1993), Springer-Verlag: Springer-Verlag New York, Heidelberg · Zbl 0797.16001
[9] Green, J. A., On the structure of semigroups, Ann. of Math., 54, 163-172 (1951) · Zbl 0043.25601
[10] James, G.; Kerber, A., The Representation Theory of the Symmetric Group, Encyclopedia Math. Appl., vol. 16 (1984), Cambridge University Press
[11] Malandro, M.; Rockmore, D., Fast Fourier transforms for the rook monoid, Trans. Amer. Math. Soc., 362, 2, 1009-1045 (2010) · Zbl 1264.65220
[12] Malandro, M. E., Fast Fourier transforms for finite inverse semigroups, J. Algebra, 324, 2, 282-312 (2010) · Zbl 1197.65235
[13] Maslen, D. K., The efficient computation of Fourier transforms on the symmetric group, Math. Comp., 67, 223, 1121-1147 (1998) · Zbl 0902.20005
[15] Maslen, D. K.; Rockmore, D. N., Separation of variables and the computation of Fourier transforms on finite groups, I, J. Amer. Math. Soc., 10, 1, 169-214 (1997) · Zbl 0860.20016
[16] Mitsch, H., A natural partial order for semigroups, Proc. Amer. Math. Soc., 97, 3, 384-388 (1986) · Zbl 0596.06015
[17] Munn, W. D., The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc., 53, 13-18 (1957) · Zbl 0077.02703
[18] Munn, W. D., Matrix representations of semigroups, Proc. Cambridge Philos. Soc., 53, 5-12 (1957) · Zbl 0077.02702
[19] Rhodes, J.; Zalcstein, Y., Elementary representation and character theory of finite semigroups and its application, (Monoids and Semigroups with Applications (1991), World Sci. Publishing: World Sci. Publishing River Edge, NJ), 334-367 · Zbl 0799.20062
[20] Ringel, C. M., The representation type of the full transformation semigroup T4, Semigroup Forum, 61, 429-434 (2000) · Zbl 0967.20037
[21] Rockmore, D. N., Fast Fourier transforms for wreath products, Appl. Comput. Harmon. Anal., 2, 279-292 (1995) · Zbl 0841.65141
[22] Serre, J. P., Linear Representations of Finite Groups, Grad. Texts in Math., vol. 42 (1977), Springer-Verlag: Springer-Verlag New York, Heidelberg
[23] Solomon, L., Representations of the rook monoid, J. Algebra, 256, 309-342 (2002) · Zbl 1034.20056
[24] Stanley, R., Enumerative Combinatorics, vol. 1, Cambridge Stud. Adv. Math., vol. 49 (1997), Cambridge University Press · Zbl 0889.05001
[25] Steinberg, B., Möbius functions and semigroup representation theory II: Character formulas and multiplicities, Adv. Math., 217, 1521-1557 (2008) · Zbl 1155.20057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.