At the beginning of the section 4 of Fast Quantum Fourier Transforms for a Class of Non-abelian Groups, it is said that,
... calculating a Fourier transform for a group $G$ is the same as decomposing a regular representation $\phi$ of $G$ with a matrix $A$ into irreducibles $\rho_i$ up to a permutation $P$ such that equivalent irreducible summands are equal, i.e. $$ \phi^A = A^{−1} · \phi · A = (\rho_1 \oplus \ldots \oplus \rho_k )^P $$ fulfilling $\rho_i \cong \rho_j \Rightarrow \rho_i = \rho_j $.
I have the following questions:
- What kind of matrix is $A$?
- What does it mean by decomposing a regular (i.e. permutation) representation with a matrix?
- How do we exponentiate a representation, $\phi$, with a matrix?
- How do we exponentiate a matrix, (\rho_1 \oplus \ldots \oplus \rho_k ), with a permutation $P$?
What you call "exponentiation" means conjugacy: $\phi$ is a homomorphism $G\rightarrow Aut(V)$ for some vector space $V$; an (invertible) matrix is an automorphism of $V$ (once you choose a basis), and $\phi^A$ is the representation $x\mapsto A\phi(x)A^{-1}$ (or replace $A$ with $A^{-1}$ depending on the author's conventions). In other words, it's just the representation with respect to a different basis.
Since you have a complex representation of a finite group, it is semisimple. That is to say, every representation is isomorphic to a direct sum of irreducibles. This means that there is a basis in which $\phi$ is of the form $\rho_1\oplus\cdots\oplus\rho_n$ for $\rho_i$ irreducible.
Now "exponentiating" by a permutation $P$ is much as before: you let whatever the appropriate symmetric group is act on your representation. If $\phi=\rho_1\oplus\cdots\rho_n$ is a representation and $P$ is a permutation on $n$ letters, then $\phi^P$ is the representation $\rho_{P(1)}\oplus\cdots\rho_{P(n)}$.
(Note that these two "exponentiations" are really the same thing: they're the action of a group; this is a fairly standard notation in group theory in my experience).