The problem I am trying to solve is
Find the Fourier matrix that diagonalizes the matrix
$A = \begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}$
The diagonalization that I am familiar with is $A = PDP^{-1}$ which in this case,
$P = \begin{bmatrix}1&-1+\sqrt{3}i&-1-\sqrt{3}\\1&-1-\sqrt{3}&-1+\sqrt{3}\\1&2&2\end{bmatrix}$
$D = \begin{bmatrix}1&0&0\\0&-\frac{1}{2}+\frac{\sqrt{3}}{2}i&0\\0&0&-\frac{1}{2}-\frac{\sqrt{3}}{2}i\end{bmatrix}$
$P^{-1} = \begin{bmatrix}\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\-\frac{1}{12}-\frac{\sqrt{3}}{12}i&-\frac{1}{12}+\frac{\sqrt{3}}{12}i&\frac{1}{6}\\-\frac{1}{12}+\frac{\sqrt{3}}{12}i&-\frac{1}{12}-\frac{\sqrt{3}}{12}i&\frac{1}{6}\end{bmatrix}$
I am not exactly sure how Fourier matrix comes into play for this
diagonalization process. Is the question asking me to diagonlize in such
a way that one of the three matrix is in a form of Fourier matrix?
Any help would be appreciated.
Thank you for reading.
It's because the matrix has a special form.
In general, if $a_0, \dotsc, a_{n - 1}$ are complex numbers, then we may form this "cyclic" matrix: $$A = \begin{bmatrix}a_0 & a_1 & \dotsc & a_{n - 1}\\a_{n - 1} & a_0 & \dotsc & a_{n - 2}\\\dotsc & \dotsc &\dotsc & \dotsc \\ a_1 & a_2 & \dotsc & a_0\end{bmatrix},$$ i.e. the entry at $i$-th row and $j$-th column is $a_{j - i}$, where our index for everything are viewed as element of $\mathbb Z / n \mathbb Z$ and always starts with $0$.
What does this have to do with Fourier?
Let's consider the space $\mathbb C^n$, which we view as the space of functions from $\mathbb Z/n \mathbb Z$ to $\mathbb C$.
Left multiplication by $A$ gives a linear endomorphism on this space, which sends a vector $\begin{bmatrix}b_0 \\ b_1\\ \dotsc\\ b_{n - 1}\end{bmatrix}$ to the vector $\begin{bmatrix}c_0 \\ c_1\\ \dotsc\\ c_{n - 1}\end{bmatrix}$, where $c_i = \sum_{j \in \mathbb Z/n\mathbb Z}a_j b_{i + j}$.
This is then a convolution of functions on $\mathbb Z / n \mathbb Z$.
Therefore, if we do Fourier transform for the group $\mathbb Z/n\mathbb Z$, convolutions will become pointwise multiplications, i.e. the matrix representation of $A$ becomes a diagonal matrix under the Fourier base.
Written down explicitly, we let $T = (\zeta^{ij})_{i, j}$ be the matrix such that the entry at $i$-th row and $j$-th column is $\zeta^{ij}$, where $\zeta = e^{\frac{2\pi i}{n}}$, then we have: $$T^{-1}AT = \begin{bmatrix}a_0 + a_1 + \dotsc + a_{n - 1} & & & \\ & a_0 + \zeta a_1 + \dotsc + \zeta^{n -1}a_{n- 1} & & \\ & & \dotsc & \\ & & & a_0 + \zeta^{n - 1} a_1 + \dotsc + \zeta^{(n - 1)^2}a_{n - 1} \end{bmatrix}.$$ This diagonalizes the matrix $A$.