Fast Fourier Transform on Symmetric Group

Maso Koyama

Abstract:

Discrete Fourier Transform (DFT) is a popular tool used in many fields of 
physical science to convert a signal in the time domain to a signal in the 
frequency domain. Fast Fourier Transform is an efficient implementation of 
DFT. In this talk, we will interpret DFT as change of basis in group 
algebra $\mathbb{C}G$. In particular, we will consider the case in which 
$G =S_n.$ I would introduce Specht module, and describe a specific method 
of FFT on $\mathbb{C}S_n.$