This paper (page 157) diagonalized circulant matrix $S$ like this where $\psi$ is an eigenvalue and $\Omega$ is composed of the eigenvectors as columns:
$$
\Omega^{-1}S\Omega =
\begin{bmatrix}
\psi_0 & 0 & \dots & 0 \\
0 & \psi_1 & \dots & 0 \\
\vdots & & \ddots & \vdots \\
0 & \dots & 0 & \psi_{n – 1}
\end{bmatrix}
$$
It was then stated that this is a bijective and linear transformation between 3 algebras:
- The algebra of columns of $\mathbb{C}^n$, identified with the maps from $\mathbb{Z}_n$ to $\mathbb{C}$
- The algebra of circulating matrices
- The algebra of diagonal matrices
It is said that the product in the first algebra is the convolution product. It is also stated that the last isomorphism stems from the fact that all circulant matrices are polynomials in
$$
J = \begin{bmatrix}
0 & 0 & \dots & 1 \\
1 & 0 & 0 \ \dots & 0 \\
0 & 1 & \dots & 0 \\
\vdots & & \ddots & \vdots \\
0 & & \dots & 0
\end{bmatrix}
$$
since $J^n = I_n$, its eigenvalues will be the $n$th roots of unity that appear in the DFT formula, and the eigenvectors of $J$ remain eigenvectors for every polynomial in $J$, e.g. for every circulating matrix $S_v = \sum_{k = 0}^{n – 1}v_kJ^k$.
Firstly, I don't exactly understand what the paper means to be a bijective and linear transformation here and how we should even go on about proving how algebras are isomorphic. I also don't understand what it means for a matrix to be a polynomial in another matrix. In particular, the fact that circulant matrices are polynomials in the permutation matrix $J$. In linear algebra, the only polynomials I've come across are characteristic polynomials of matrices.
I probably need to learn more topics to understand exactly what is going on here. But I would like to make sense of this and get a grasp of it if possible.
Best Answer
The first algebra is the vector space $\operatorname{Map}(\mathbb{Z}_n, \mathbb{C})$ of functions $f \colon \mathbb{Z}_n \to \mathbb{C}$. The set $\mathbb{Z}_n$ is a group under addition, and so we can equip $\operatorname{Map}(\mathbb{Z}_n, \mathbb{C})$ with a convolution product $\star$, defined by either of these two familiar formulas: $$ (f \star g)(z) = \sum_{\substack{x, y \in \mathbb{Z}_n \\ x + y = z}} f(x) f(y) = \sum_{x \in \mathbb{Z}_n} f(x) f(z - x).$$ The convolution product is commutative and associative, and the indicator function $\delta_0 \colon \mathbb{Z}_n \to \mathbb{C}$ defined by $\delta_0(0) = 1$ and $\delta_0(n) = 0$ for $n \neq 0$ is the unit for the product. On indicator functions in general, we have for all $x, y \in \mathbb{Z}_n$ that $\delta_x \star \delta_y = \delta_{x + y}$.
The second algebra is the algebra of $n \times n$ circulant matrices, which we will call $\operatorname{Circ}_n$. By polynomials in $J$, they mean simply that any $n \times n$ circulant matrix $C$ may be written as $C = c_0 + c_1 J + c_2 J^2 + \cdots + c_{n - 1} J^{n-1}$, in other words the vectors $I, J, J^2, \ldots, J^{n-1}$ form a basis for the vector space of circulant matrices. Hence the circulant matrices form a vector space, but more is true: multiplying two circulant matrices produces another circulant matrix. If $C = c_0 + c_1J + \cdots + c_{n-1}J^{n-1}$ and $D = d_0 + d_1 J + \cdots + d_{n-1} J^{n-1}$, then $CD$ is again a polynomial in $J$, with at most $n-1$ terms because $J^n = I$. Let $CD = E = e_0 + e_1 J + \cdots + e_{n-1}J^{n-1}$, then just from the product of polynomials and $J^n = I$ we get $$ e_z = \sum_{\substack{x, y \in \mathbb{Z}_n \\ x + y = z}} c_x d_y,$$ which looks like the convolution product.
In order to show that the first and second algebras are isomorphic, we must give a bijective linear map $\varphi \colon \operatorname{Map}(\mathbb{Z}_n, \mathbb{C}) \to \operatorname{Circ}_n$ such that $\varphi(f \star g) = \varphi(f) \varphi(g)$ for all $f, g \in \operatorname{Map}(\mathbb{Z}_n, \mathbb{C})$. This shows that the vector spaces and products are really the same, and all that has changed is our labelling. After the discussion above, the natural map to try is $$ \varphi(f) = \sum_{x = 0}^{n-1} f(x) J^x.$$ We now try to show that $\varphi(f) \varphi(g) = \varphi(f \star g)$: $$ \begin{aligned} \varphi(f) \varphi(g) &= \left(\sum_{x \in \mathbb{Z}_n} f(x) J^x \right) \left(\sum_{y \in \mathbb{Z}_n} f(y) J^y \right) \\ &= \sum_{x, y \in \mathbb{Z}_n} f(x)f(y) J^{x + y} \\ &= \sum_{z \in \mathbb{Z}_n} \left(\sum_{\substack{x, y \in \mathbb{Z}_n \\ x + y = z}} f(x) f(y)\right) J^z \\ &= \sum_{z \in \mathbb{Z}_n} (f \star g)(z) J^z \\ &= \varphi(f \star g). \end{aligned} $$ Since $\varphi$ is a bijection preserving the product, the algebras are isomorphic.
Can you take it from here to try to show that the third algebra is isomorphic to either of these two? The third algebra is basically just noticing that all circulant matrices have the same eigenvectors, but different eigenvalues, so rather than writing $C = c_0 + c_1 J + \cdots + c_{n-1} J^{n-1}$, instead you can pick some ordering $v_0, \ldots, v_{n-1}$ of the circulant eigenvectors and write down the list of eigenvalues of $C$.