How to find all the eigen values of the graph (Laplacian):
$G=(V(G),E(G))$ where $V(G)=\{1,2,\ldots n\}$ and $E(G)=\{(i,i+1):1\le i<n\}$
On finding the Laplacian Matrix of the graph I found that it is of the form:
$L$=
\begin{array}{cccccccccccccccccccccc} 1 & -1 &0 &0\ldots &0\\ -1 &2 &-1&0\ldots & 0\\ 0 & -1 &2 &-1\ldots &0\\ \ldots &\ldots &\ldots \\ \ldots &\ldots &\ldots\\ \ldots &\ldots &\ldots\\ 0 & \ldots &\ldots&\ldots -1&1 \end{array}
The question now reduces in solving the characteristic polynomial of $L$ How should I proceed to find the eigen values from here?
It is impossible to solve the characteristic polynomial here?Please help.
Treat the path graph $P_n$ as a quotient of the ring graph $R_{2n}$ by identifying each node $(u)$ of $P_n$ with the pair of nodes $(u)$ and $(2n-1-u)$ of $R_{2n}$. You can visualize this by laying out $R_{2n}$ with its nodes in two parallel rows.
First, suppose that $w$ is an eigenvector of $L_{R_{2n}}$ with $w(u)=w(2n-1-u)$ for $0\le u\lt n$ and let $z=(w(0),\cdots,w(n-1))^T$. For $0<u<n-1$, $$\begin{align} [L_{P_n}z](u) &= 2z(u)-\sum_{j\in N_{P_n}(u)}z(j) \\ &= 2w(u)-\sum_{j\in N_{R_{2n}}(u)}w(j) \\ &= \frac12\left(2w(u)-\sum_{j\in N_{R_{2n}}(u)}w(j)+2w(2n-1-u)-\sum_{j\in N_{R_{2n}}(2n-1-u)}w(j)\right) \\ &= \frac12\left([L_{R_{2n}}w](u)+[L_{R_{2n}}w](2n-1-u)\right) \\ &= \frac12\left(\lambda w(u)+\lambda w(2n-1-u)\right) \\ &= \lambda w(u) \\ &= \lambda z(u). \end{align}$$ For $i=0$, $$\begin{align}[L_{P_n}z](0) &= z(0)-z(1) \\ &= 2z(0)-z(1)+z(0) \\ &= 2w(0)-w(1)+w(0) \\ &= 2w(0)-w(1)+w(2n-1) \\ &= \lambda w(0) \\ &= \lambda z(0) \end{align}$$ and the other end is similar. Thus, $z$ is an eigenvector of $L_{P_n}$, with the same eigenvalue as $w$.
It remains to be shown that such eigenvectors exist. Let $v_k$ be the eigenvector of $L_{R_{2n}}$ generated by $\omega^k$ as in this answer, with eigenvalue $\lambda_k=2\left(1-\cos{k\pi\over n}\right)$. For $0\lt k\lt n$, observe that $\lambda_{2n-k}=\lambda_k$, so $v_{2n-k}$ is also an eigenvector of $\lambda_k$. We seek scalars $a$ and $b$ such that $$av_k(u)+bv_{2n-k}(u)=av_k(2n-1-u)+bv_{2n-k}(2n-1-u)$$ for all $0\le u\lt n$. Since $v_{2n-k}(u)={\overline v}_k(u)$, this can be rewritten as $$a\left(v_k(u)-v_k(2n-1-u)\right)=b\left({\overline v}_k(2n-1-u)-{\overline v}_k(u)\right).$$ It is enough to examine the case $u=0$ as the other cases can be obtained from it by multiplying both sides of the equation by a scalar (by a positive real number, in fact): $$a\left(1-e^{ik(2n-1)\pi/n}\right)=b\left(e^{-ik(2n-1)\pi/n}-1\right) \\ a\left(1-e^{-ik\pi/n}\right)=b\left(e^{ik\pi/n}-1\right)$$ which has $a=\frac12e^{ik\pi/(2n)}$ and $b=\frac12e^{-ik\pi/(2n)}$ as a solution. So, $$w_k = \frac12e^{ik\pi/(2n)}v_k+\frac12e^{-ik\pi/(2n)}{\overline v}_k = \Re\left(e^{ik\pi/(2n)}v_k\right)$$ is an eigenvector of $\lambda_k$ with the required property. For $\lambda_0=0$, $v_0=\mathbf 1$ and the above formula yields $w_0=\mathbf 1$ as well. (You can also derive this eigenvector by finding a suitable linear combination of $\Re(v_k)$ and $\Im(v_k)$, which are also eigenvectors of $\lambda_k$. Plotting the elements of $v_k$ on the complex plane makes what’s going on here clearer—the sets of points are being rotated to vertically align $v_k(u)$ and $v_k(2n-u)$.)
So, the eigenvalues of the path graph $P_n$ are $$\lambda_k=2\left(1-\cos\frac{k\pi}{n}\right), \quad k=1,2,\ldots,n$$ with associated eigenvectors $$v_k(u)=\cos\left({\pi ku\over n}+{\pi k\over2n}\right).$$