Transactions of the American Mathematical Society

Author(s): Martin Malandro; Dan Rockmore
Journal: Trans. Amer. Math. Soc. 362 (2010), 1009-1045.
MSC (2000): Primary 20C40, 20M18, 43A30; Secondary 20M30, 68W40
Posted: September 17, 2009
Retrieve article in: PDF

Abstract: We define the notion of the Fourier transform for the rook monoid (also called the symmetric inverse semigroup) and provide two efficient divide-and-conquer algorithms (fast Fourier transforms, or FFTs) for computing it. This paper marks the first extension of group FFTs to nongroup semigroups.

1.: U. Baum, Existence and efficient construction of fast Fourier transforms for supersolvable groups, Comput. Complex. 1/3 (1992), 235-256. MR 1165193 (93d:20031)
2.: L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics 18 (1970), no. 4, 451-455.
3.: M. Clausen and U. Baum, Fast Fourier transforms for symmetric groups: Theory and implementation, Math. Comput. 61 (1993), no. 204, 833-847. MR 1192969 (94a:20028)
4.: A. H. Clifford, Matrix representations of completely simple semigroups, Amer. J. Math. 64 (1942), no. 1, 327-342. MR 0006551 (4:4a)
5.: A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, vol. 1, Mathematical Surveys No. 7, AMS, Providence, RI, 1961. MR 0132791 (24:A2627)
6.: -, The Algebraic Theory of Semigroups, vol. 2, Mathematical Surveys No. 7, AMS, Providence, RI, 1967. MR 0218472 (36:1558)
7.: J. W. Cooley and J. W. Tukey, An algorithm for machine calculation of complex Fourier series, Math. Comput. 19 (1965), 297-301. MR 0178586 (31:2843)
8.: C. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras, John Wiley and Sons, New York, 1962. MR 0144979 (26:2519)
9.: P. Diaconis, A generalization of spectral analysis with application to ranked data, Ann. Statist. 17 (1989), no. 3, 949-979. MR 1015133 (91a:60025)
10.: P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), no. 2, 297-332. MR 1030655 (92g:20024)
11.: -, Efficient computation of isotypic projections for the symmetric group, DIMACS Series in Disc. Math. and Theor. Comp. Sci. 11 (1993), 87-104. MR 1235796 (94g:20022)
12.: B. Farb and R. K. Dennis, Noncommutative Algebra, Graduate Texts in Mathematics, vol. 144, Springer-Verlag, New York-Heidelberg, 1993. MR 1233388 (94j:16001)
13.: C. Grood, A Specht module analog for the rook monoid, Electron. J. Combin. 9 (2002). MR 1887083 (2003a:05150)
14.: T. Halverson, Representations of the q-rook monoid, J. Algebra 273 (2004), 227-251. MR 2032458 (2005f:20011)
15.: R. B. Holmes, Mathematical foundation of signal processing II. The role of group theory, Massachusetts Institute of Technology Technical Report 781 (October 13, 1987).
16.: G. D. James, The representation theory of the symmetric groups, Lect. Notes Math., Springer-Verlag, Berlin 682 (1978). MR 513828 (80g:20019)
17.: S. Janson and V. Mazorchuk, Some remarks on the combinatorics of , Semigroup Forum 70 (2005), no. 3, 391-405. MR 2148152 (2006c:20123)
18.: M. V. Lawson, Inverse Semigroups: The Theory of Partial Symmetries, World Scientific, Singapore, 1998. MR 1694900 (2000g:20123)
19.: M. Malandro, Fast Fourier Transforms for Inverse Semigroups, Thesis, Dartmouth College (2008).
20.: D. K. Maslen, The efficient computation of Fourier transforms on the symmetric group, Math. Comput. 67 (1998), no. 223, 1121-1147. MR 1468943 (99a:20009)
21.: D. K. Maslen and D. N. Rockmore, Adapted diameters and FFTs on groups, Proc. 6th ACM-SIAM SODA, 253-262. MR 1321855 (95k:65131)
22.: -, Generalized FFTs--A survey of some recent results, Proc. 1995 DIMACS Workshop on Groups and Computation 28 (1997), 183-238. MR 1444138 (98k:20020)
23.: -, Separation of variables and the computation of Fourier transforms on finite groups, I, J. Amer. Math. Soc. 10 (1997), no. 1, 169-214. MR 1396896 (97i:20019)
24.: -, The Cooley-Tukey FFT and group theory, Notices of the AMS 48 (2001), no. 10, 1151-1161. MR 1861656 (2002k:20022)
25.: W. D. Munn, On semigroup algebras, Proc. Cambridge Philos. Soc. 51 (1955), 1-15. MR 0066355 (16:561c)
26.: -, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13-18. MR 0081910 (18:465d)
27.: -, Matrix representations of semigroups, Proc. Cambridge Philos. Soc. 53 (1957), 5-12. MR 0082050 (18:489g)
28.: J. Rhodes and Y. Zalcstein, Elementary representation and character theory of finite semigroups and its application, Monoids and Semigroups with Applications, pp. 334-367, World Sci. Publishing, River Edge, NJ, 1991. MR 1142387 (92k:20129)
29.: D. N. Rockmore, Recent progress and applications in group FFTs, NATO Science Series, Computational Noncommutative Algebra and Applications, vol. 136, pp. 227-254, Kluwer Acad. Publ., Dordrecht, 2004. MR 2159215 (2007j:43012)
30.: J. P. Serre, Linear Representations of Finite Groups, Graduate Texts in Mathematics, vol. 42, Springer-Verlag, New York-Heidelberg, 1977. MR 0450380 (56:8675)
31.: L. Solomon, Representations of the rook monoid, J. Algebra 256 (2002), 309-342. MR 1939108 (2003m:20091)
32.: R. Stanley, Enumerative Combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, 1997. MR 1442260 (98a:05001)
33.: B. Steinberg, Mobius functions and semigroup representation theory, J. Comb. Theor. Ser. A. 113 (2006), 866-881. MR 2231092 (2007c:20144)
34.: -, Möbius functions and semigroup representation theory II: Character formulas and multiplicities, Adv. In Math. 217 (2008), 1521-1557. MR 2382734
35.: F. Yates, The design and analysis of factorial experiments, Imp. Bur. Soil Sci. Tech. Comm. 35 (1937).

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20C40, 20M18, 43A30, 20M30, 68W40

Martin Malandro
Affiliation: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hanover, New Hampshire 03755
Address at time of publication: Department of Mathematics and Statistics, Sam Houston State University, Box 2206, Huntsville, Texas 77341-2206
Email: malandro@shsu.edu

Dan Rockmore
Affiliation: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hanover, New Hampshire 03755
Email: rockmore@cs.dartmouth.edu

DOI: 10.1090/S0002-9947-09-04838-7
PII: S 0002-9947(09)04838-7
Keywords: Rook monoid, fast Fourier transform, FFT, inverse semigroup, partially ranked data
Received by editor(s): September 25, 2007
Received by editor(s) in revised form: June 2, 2008
Posted: September 17, 2009
Additional Notes: The first author was supported by a graduate fellowship.
The second author was supported by AFOSR under grant FA9550-06-1-0027.
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS