We study the complexity of performing Fourier
analysis for the group $\SL_2(\fq)$, where $\fq$ is the finite
field of $q$ elements. Direct computation of a complete set of Fourier
transforms for a complex-valued function $f$ on $\SL_2(\fq)$ requires
$q^6$ operations. A similar bound holds for performing Fourier
inversion. Here we show that for both operations this
naive upper bound may be reduced to $O(q^4\log q)$, where
the implied constant is universal, depending only
on the complexity of the "classical'' fast Fourier transform. The techniques
we use depend strongly on explicit constructions of
matrix representations of the group.
¶ Additionally, the
ability to construct the matrix representations permits
certain numerical experiments.
By quite general methods, recent work of others has shown
that certain families of Cayley graphs on $\SL_2(\fq)$ are expanders.
However, little is known about their exact spectra.
Computation of the relevant Fourier transform permits
extensive numerical investigations of the spectra of these Cayley graphs.
We explain the associated calculation and
include illustrative figures.