 |
Abstract: We define the notion of an inverse semigroup S and the notion of the Fourier transform on S. We exhibit a method for constructing Fast Fourier transforms for finite inverse semigroups. Our construction uses partially ordered sets, Mobius inversion, and group-based FFTs. We give an explicit construction for the rook monoid, which is the collection of placements of non-attacking rooks (1's) on an nxn chessboard (i.e., in an nxn matrix, with all other entries being 0), under the operation of matrix multiplication.
This talk will be accessible to graduate students.
|