Fast Fourier Transforms for the Rook Monoid

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 non-group semigroups.

Cited by in corpus (3)

• Quivers of monoids with basic algebras
• Fast Fourier Transforms for Finite Inverse Semigroups
• Inverse semigroup spectral analysis for partially ranked data