I am reading the following book/notes on Graph Representation Learning (here) and have a number of questions from Chapter 7.
Context: In section 7.1.3 of the notes, we have the following bit of the notes.
The book has the following block of text:
so the eigenfunctions of $\Delta$ are the same complex exponentials that make up the modes of the frequency domain in the Fourier transform (i.e., the sinusoidal plane waves), with the corresponding eigenvalue indicating the frequency. In fact, one can even verify that the eigenvectors $\mathbf{u_1} , ..., \mathbf{u_n}$ of the circulant Laplacian $\mathbf{L_c} ∈ R^{n×n}$ for the chain graph are $\mathbf{u_j} = \frac{1}{\sqrt n} [1, \omega_j , \omega_j ^2 , ..., \omega_j ^n ] $ where $\omega_j = e^{\frac{2πj}{n}} $
Question: Do these eigenvectors only hold if the Laplacian matrix is a circulant matrix? This document (link) from a response to another post shows the derivation for circulant matrices, so it led me to wonder whether the Laplacian has to take a specific form.
If the eigenvectors of $L$ are as given, it is a circulant. Let $W$ be the matrix with entries $\omega^{(i-1)(j-1)}$. The columns of $W$ are a basis for $\mathbb{C}^n$. If $P$ is the permutation matrix representing the $n$-cycle, then the columns of $W$ are eigenvectors for $P$ and therefore, relative to this basis, $P$ is diagonal. If $L$ is a second matrix with the columns of $W$ as eigenvectors, then in the columns-of-$W$ basis, it is diagonal too. Since diagonal matrices commute, this implies that $LP=PL$ and so $L$ is a circulant.