Eigenvector of Laplacian of ring graph

Question

I know the eigenvectors of the Laplacian of a ring graph with $n$ vertices are

$$x_k(u) = \sin \left( \frac{2 \pi k u}{n} \right)$$

and

$$y_k(u) = \cos \left( \frac{2 \pi k u}{n} \right)$$

for $1 \leq k \leq \frac n2$. However, I can't understand which one is an eigenvector of the Laplacian of the ring graph. Actually, what is the value of the $i$-th element of the $j$-th eigenvector of the Laplacian of a ring graph with $n$ vertices?

I couldn't find anything that directly explains this issue.

Answer 1

This notation can be a bit hard to decipher. The $i$th component of a vector $X\in\mathbb K^n$ is denoted by $X(i)$, in keeping with the interpretation of $X$ as a function $X:\{1,\dots,n\}\to\mathbb K$. So, these are component-by-component formulas for two families of vectors, $x_k$ and $y_k$. Quoting in full from the MIT OCW course notes for 18.409 (“An Algorithmist’s Toolkit”) where these formulas appear:

Lemma 16 (Ring graph) The Laplacian for the ring graph $R_n$ of $n$ vertices has eigenvectors $$\begin{align} x_k(u) &= \sin(2\pi ku/n), \text{ and} \\ y_k(u) &= \cos(2\pi ku/n) \end{align}$$ for $0\le k\le n/2$. Both $x_k$ and $y_k$ have eigenvalue $2-2\cos(2\pi k/n)$. Note that, $x_0=\mathbf 0$ should be ignored and $y_0=\mathbf 1$, and when $n$ is even $x_{n/2}=\mathbf 0$ should be ignored and we only have $y_{n/2}$.

So, for the five-node example you tried, besides $y_0=\mathbf 1$, which is a null vector of the Laplacian, we have $$\begin{align} x_1 &= \left(\sin\frac25\pi, \sin\frac45\pi, \sin\frac65\pi, \sin\frac85\pi, 0 \right)^T \\ y_1 &= \left( \cos\frac25\pi, \cos\frac45\pi, \cos\frac65\pi, \cos\frac85\pi, 1 \right)^T \\ x_2 &= \left( \sin\frac45\pi, \sin\frac85\pi, \sin\frac25\pi, \sin\frac65\pi, 0 \right)^T \\ y_2 &= \left( \cos\frac45\pi, \cos\frac85\pi, \cos\frac25\pi, \cos\frac65\pi, 1 \right)^T \end{align}$$ with $\lambda_1=2-2\cos(2/5\,\pi)$ and $\lambda_2=2-2\cos(4/5\,\pi)$. You can verify that these are indeed eigenvectors of the Laplacian matrix for $R_n$.

Most of the eigenvalues have multiplicity 2, so these eigenvectors may well be different from ones computed by other means. For example, when I compute a basis for the null space of $L-\lambda_1I$ via row-reduction, one of the vectors I get has a $0$ for its fourth element, which doesn’t match either $x_1$ or $y_1$ above.