Eigenvalues of Path Graphs

The Adjacency Eigenvalues of a Path

For a path, each interior vertex has two neighbors and each endpoint has one. That simple pattern turns the adjacency eigenvalue equation into a second-order recurrence, with the endpoints supplying boundary conditions. Solving the recurrence and satisfying both endpoint conditions gives an explicit formula for every adjacency eigenvalue of the path.

Throughout, graphs are finite and simple. For $n\ge 1$, let $P_n$ have vertex set $V(P_n)=\{1,2,\ldots,n\}$ and edge set $E(P_n)=\{i(i+1):1\le i<n\}$. Thus $P_1$ has one vertex and no edges. In this tutorial, an adjacency eigenvalue of a graph is a scalar $\lambda$ for which $\mathbf A(G)x=\lambda x$ for some nonzero vector $x$, where $\mathbf A(G)$ is the adjacency matrix. We order the coordinates by the displayed vertex labels.

Theorem: For every integer $n\ge 1$, the adjacency eigenvalues of $P_n$ are $$ \lambda_k=2\cos\left(\frac{k\pi}{n+1}\right),\qquad 1\le k\le n. $$ These $n$ values are distinct, so each occurs once in the spectrum.

From the Eigenvalue Equation to Boundary Conditions

Let $x=(x_1,\ldots,x_n)^{\mathsf T}$ be a vector. The $j$-th coordinate of $\mathbf A(P_n)x$ is the sum of the coordinates at vertices adjacent to $j$. For an interior vertex $1<j<n$, this sum is $x_{j-1}+x_{j+1}$. At the left endpoint it is $x_2$, and at the right endpoint it is $x_{n-1}$, when those endpoints have other vertices. It is convenient to express all these equations in one form by setting the boundary coordinates $x_0=x_{n+1}=0$. Then the eigenvalue equation is exactly

x_{j-1}+x_{j+1}=\lambda x_j\qquad(1\le j\le n).

This convention also handles $P_1$: its only coordinate equation is $0=\lambda x_1$. The two boundary coordinates are not vertices of the graph; they encode the fact that there is no neighbor beyond either endpoint.

To find vectors satisfying this recurrence, consider a real angle $\theta$ and define an extended sequence $y_j=\sin(j\theta)$ for every integer $j$ from $0$ to $n+1$. The sine addition identity gives, for each $1\le j\le n$,

y_{j-1}+y_{j+1} =\sin((j-1)\theta)+\sin((j+1)\theta) =2\cos(\theta)\sin(j\theta) =2\cos(\theta)y_j.

This identity is an identity for the sine sequence, including its values $y_0$ and $y_{n+1}$. To make the coordinates $x_j=y_j$, for $1\le j\le n$, satisfy the path equations, the sequence must also match the graph’s boundary convention. At the left endpoint, $y_0=\sin(0)=0$, as required. At the right endpoint, it must satisfy $y_{n+1}=0$, which is exactly the condition $\sin((n+1)\theta)=0$.

Choose $\theta_k=k\pi/(n+1)$ for $k=1,\ldots,n$. Then $(n+1)\theta_k=k\pi$, so $y_{n+1}=\sin(k\pi)=0$, and the left boundary value is also zero. The interior coordinates are not all zero: $y_1=\sin(\theta_k)\ne 0$, since $0<\theta_k<\pi$. Thus $x_j=\sin(j\theta_k)$, for $1\le j\le n$, is a nonzero vector satisfying the eigenvalue equation with $\lambda=2\cos(\theta_k)$.

Why These Are All the Eigenvalues

Producing eigenvectors gives $n$ candidate eigenvalues, but completeness requires checking that the candidates are distinct and that no additional eigenvalues have been missed.

Proof. For each $k\in\{1,\ldots,n\}$, define $x^{(k)}$ by $x^{(k)}_j=\sin(jk\pi/(n+1))$ for $1\le j\le n$. The left boundary value of its extended sine sequence is $\sin(0)=0$, and the right boundary value is $\sin((n+1)k\pi/(n+1))=\sin(k\pi)=0$. The sine addition identity therefore gives the path eigenvalue equation at every coordinate, with eigenvalue $\lambda_k=2\cos(k\pi/(n+1))$. Moreover, $x^{(k)}_1=\sin(k\pi/(n+1))\ne0$, so $x^{(k)}$ is nonzero.

The angles $k\pi/(n+1)$, as $k$ ranges from $1$ to $n$, are strictly increasing and lie in $(0,\pi)$. Cosine is strictly decreasing on this interval. Hence the $n$ values $\lambda_k$ are distinct. Eigenvectors for distinct eigenvalues are linearly independent: to see this, suppose a shortest nontrivial linear relation among such eigenvectors is $\sum_{i=1}^{r}a_i v_i=0$, with distinct eigenvalues $\mu_i$ and all $a_i\ne0$. Applying $\mathbf A(P_n)-\mu_r I$ gives $\sum_{i=1}^{r-1}a_i(\mu_i-\mu_r)v_i=0$. Each coefficient is nonzero, contradicting the minimality of the relation. Thus the $n$ vectors $x^{(1)},\ldots,x^{(n)}$ are linearly independent in the $n$-dimensional coordinate space, and hence form a basis. In this basis the matrix acts diagonally with the displayed eigenvalues, so there are no others and each occurs once. $\square$

Worked Examples

Worked Example: The Single-Vertex Path

Let $P_1$ have $V(P_1)=\{1\}$ and $E(P_1)=\varnothing$. Its adjacency matrix is the $1$ by $1$ zero matrix, so its only eigenvalue is $0$: the eigenvalue equation is $0\cdot x_1=\lambda x_1$, and for a nonzero vector $x_1$, this forces $\lambda=0$.

The formula gives just $k=1$, and therefore $\lambda_1=2\cos(\pi/2)=2\cdot0=0$. The corresponding coordinate from the sine construction is $x_1=\sin(\pi/2)=1$. Substitution into the matrix equation gives $0\cdot1=0\cdot1$, verifying the result directly.

Check: The graph has no edges, so its adjacency matrix is zero. The computed spectrum consists of the single eigenvalue $0$, as required.

Worked Example: The Path on Two Vertices

Let $P_2$ have $V(P_2)=\{1,2\}$ and $E(P_2)=\{12\}$. Its adjacency matrix and characteristic determinant are

\mathbf A(P_2)= \begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad \det(\lambda I-\mathbf A(P_2)) =\det\begin{pmatrix}\lambda&-1\\-1&\lambda\end{pmatrix} =\lambda^2-1.

The determinant factors as $(\lambda-1)(\lambda+1)$, giving eigenvalues $1$ and $-1$. The formula independently gives $\lambda_1=2\cos(\pi/3)=2(1/2)=1$ and $\lambda_2=2\cos(2\pi/3)=2(-1/2)=-1$.

The recurrence also verifies both values. For $k=1$, $\theta_1=\pi/3$, so $x_1=\sin(\pi/3)=\sqrt3/2$ and $x_2=\sin(2\pi/3)=\sqrt3/2$; the adjacency matrix exchanges these coordinates, leaving the vector unchanged. For $k=2$, $\theta_2=2\pi/3$, so $x_1=\sqrt3/2$ and $x_2=-\sqrt3/2$; exchanging them multiplies the vector by $-1$.

Check: The characteristic polynomial has exactly the two roots $1,-1$, and both agree with the formula.

Worked Example: The Path on Three Vertices

Let $P_3$ have $V(P_3)=\{1,2,3\}$ and $E(P_3)=\{12,23\}$. Expanding the determinant along the first row gives

\det(\lambda I-\mathbf A(P_3)) = \det\begin{pmatrix} \lambda&-1&0\\ -1&\lambda&-1\\ 0&-1&\lambda \end{pmatrix} =\lambda(\lambda^2-1)-\lambda =\lambda^3-2\lambda =\lambda(\lambda^2-2).

Thus the eigenvalues are $0,\sqrt2,-\sqrt2$. The formula gives $\lambda_1=2\cos(\pi/4)=2(\sqrt2/2)=\sqrt2$, $\lambda_2=2\cos(2\pi/4)=2\cos(\pi/2)=0$, and $\lambda_3=2\cos(3\pi/4)=2(-\sqrt2/2)=-\sqrt2$.

As one direct recurrence check, for $k=2$ we have $\theta_2=\pi/2$, giving $x_1=\sin(\pi/2)=1$, $x_2=\sin(\pi)=0$, and $x_3=\sin(3\pi/2)=-1$. Multiplication by the adjacency matrix sends $(1,0,-1)^{\mathsf T}$ to $(0,0,0)^{\mathsf T}$, so this vector has eigenvalue $0$.

Check: The determinant factors into one linear factor and a quadratic with roots $\sqrt2$ and $-\sqrt2$; these are exactly the three distinct values from the formula.

Worked Example: The Path on Five Vertices

Let $P_5$ have $V(P_5)=\{1,2,3,4,5\}$ and $E(P_5)=\{12,23,34,45\}$. The formula gives the following values, evaluating each cosine at its angle:

\begin{aligned} \lambda_1&=2\cos(\pi/6)=2(\sqrt3/2)=\sqrt3,\\ \lambda_2&=2\cos(2\pi/6)=2\cos(\pi/3)=1,\\ \lambda_3&=2\cos(3\pi/6)=2\cos(\pi/2)=0,\\ \lambda_4&=2\cos(4\pi/6)=2\cos(2\pi/3)=-1,\\ \lambda_5&=2\cos(5\pi/6)=2(-\sqrt3/2)=-\sqrt3. \end{aligned}

For an independent check, write $D_r=\det(\lambda I-\mathbf A(P_r))$. Expansion of the tridiagonal determinant at the final row gives $D_r=\lambda D_{r-1}-D_{r-2}$, with $D_1=\lambda$ and $D_2=\lambda^2-1$. Applying this recurrence, $D_3=\lambda(\lambda^2-1)-\lambda=\lambda^3-2\lambda$, $D_4=\lambda(\lambda^3-2\lambda)-(\lambda^2-1)=\lambda^4-3\lambda^2+1$, and $D_5=\lambda(\lambda^4-3\lambda^2+1)-(\lambda^3-2\lambda)=\lambda^5-4\lambda^3+3\lambda$. Factoring gives $D_5=\lambda(\lambda^2-1)(\lambda^2-3)$, whose roots are $0,1,-1,\sqrt3,-\sqrt3$, exactly the five values above.

Check: The determinant is degree five and its five listed roots are distinct. Its factorization independently confirms the formula for this path.

A Common Endpoint Error

The boundary condition at the right endpoint must be applied to the extended sine sequence, not by changing one of its sine values before using the sine addition identity. For a concrete example, take $n=2$ and $\theta=\pi/2$. The actual sine sequence has $y_1=\sin(\pi/2)=1$, $y_2=\sin(\pi)=0$, and $y_3=\sin(3\pi/2)=-1$. The identity gives $y_1+y_3=1+(-1)=0=2\cos(\pi/2)y_2$. If one instead sets a new boundary value $x_3=0$ and then claims the sine identity gives $x_1+x_3=2\cos(\theta)x_2$, the left side is $1+0=1$, while the right side is $0$. That claimed equality is false.

The correction is to keep $y_j=\sin(j\theta)$ throughout the trigonometric identity. The graph equation at the right endpoint agrees with that identity only when $y_{n+1}=0$. In the example, $\theta=\pi/2$ does not meet this condition because $y_3=-1$; it is not one of the permitted angles for $P_2$. The valid choices are $\pi/3$ and $2\pi/3$, both of which make $\sin(3\theta)=0$.

The endpoint condition is what selects a finite list from the possible sine sequences. The recurrence alone does not make every angle an eigenvalue: both boundary values must agree with the path equations. Once they do, the resulting $n$ distinct eigenvalues exhaust the spectrum.

Check Your Understanding

Use the recurrence and both endpoint conditions in your reasoning.

Write the adjacency eigenvalue equations for $P_4$, including the endpoint equations.
For $P_4$, what angles $\theta$ satisfy $\sin(5\theta)=0$ with $0<\theta<\pi$?
Explain why the sine vector for an allowed angle is nonzero.
Why does producing $n$ distinct eigenvalues suffice to show that there are no other eigenvalues for $P_n$?
For $P_2$ and $\theta=\pi/2$, compare the actual sine value $y_3$ with the boundary value required by the graph.

What You'll Learn