Computation of Determinant for Eigenvalues of Adjacency Matrix of Permutation

Question

Problem Let $P$ be a path with the vertex set $[n]$ and the edges $\{i,i-1\}$ for $1\le i\le n-1$.

Find all eigenvalues of adjacency matrix of P.

---

Solution The graph given representend as follow: $$1-2-3-4-5-6-\cdot\cdot\cdot - n-1-n$$

And its adjacency matrix $A$ computed as:

$$A =\begin{bmatrix}0&1&0&0&...&0\\1&0&1&0&...&0\\0&1&0&1&...&0\\...\\0&...&0&1&0&1&\\0&...&0&0&1&0\end{bmatrix}$$

Now, with this matrix A, to compute eigenvalues:

$$det(A-\lambda I) = 0$$

Then $$A-\lambda I =\begin{bmatrix}-\lambda &1&0&0&...&0\\1&-\lambda&1&0&...&0\\0&1&-\lambda&1&...&0\\...\\0&...&0&1&-\lambda&1&\\0&...&0&0&1&-\lambda\end{bmatrix}$$

---

Question: How can I compute the $det(A-\lambda I)$ easily?

Answer 1

Here's a rather different approach using cofactor expansion and induction.

---

One can compute the determinants $S_n = \det(A-\lambda I_n)$ recursively, using the following method (I'll demonstrate the first few, and you'll see the pattern):

$S_1 = -\lambda$

$S_2 = \det(A-\lambda I_2) = \det\left(\begin{array}{cc} -\lambda & 1\\ 1 & -\lambda \end{array}\right) = \lambda^2-1$

\begin{align}\begin{aligned} S_3 &= \det(A-\lambda I_3) = \det\left(\begin{array}{ccc} -\lambda & 1 & 0\\ 1 & -\lambda & 1\\ 0 & 1 & -\lambda \end{array}\right)\\ &= -\lambda\det\left(\begin{array}{ccc} -\lambda & 1\\ 1 & -\lambda \end{array}\right) - \det\left(\begin{array}{ccc} 1 & 1\\ 0 & -\lambda\\ \end{array}\right) \quad\text{ (cofactor expand along first row)}\\&= -\lambda S_2 - S_1 \quad \text{ (cofactor expand second term along first column)} \end{aligned}\end{align}

\begin{align}\begin{aligned} S_4 &= \det(A-\lambda I_4) = \det\left(\begin{array}{cccccc} -\lambda & 1 & 0 & 0 \\ 1 & -\lambda & 1 & 0 \\ 0 & 1 & -\lambda & 1\\ 0 & 0 & 1 & -\lambda \end{array}\right)\\ &= -\lambda \det\left(\begin{array}{cccccc} -\lambda & 1 & 0 \\ 1 & -\lambda & 1 \\ 0 & 1 & -\lambda \end{array}\right) - \det\left(\begin{array}{cccccc} 1 & 1 & 0 \\ 0 & -\lambda & 1 \\ 0 & 1 & -\lambda \end{array}\right) \quad\text{ (cofactor expand along first row)}\\ &= -\lambda S_3 - \det\left(\begin{array}{cccccc} -\lambda & 1 \\ 1 & -\lambda \end{array}\right) \quad \text{ (cofactor expand second term along first column)}\\ &= -\lambda S_3 - S_2 \end{aligned}\end{align}

\begin{align}\begin{aligned} S_5 &= \det(A-\lambda I_5) = \det\left(\begin{array}{cccccc} -\lambda & 1 & 0 & 0 & 0\\ 1 & -\lambda & 1 & 0 & 0 \\ 0 & 1 & -\lambda & 1 & 0\\ 0 & 0 & 1 & -\lambda & 1\\ 0 & 0 & 0 & 1 & -\lambda \end{array}\right)\\ &= -\lambda \det\left(\begin{array}{cccccc} -\lambda & 1 & 0 & 0\\ 1 & -\lambda & 1 & 0 \\ 0 & 1 & -\lambda & 1\\ 0 & 0 & 1 & -\lambda \end{array}\right) - \det\left(\begin{array}{cccccc} 1 & 1 & 0 & 0\\ 0 & -\lambda & 1 & 0 \\ 0 & 1 & -\lambda & 1\\ 0 & 0 & 1 & -\lambda \end{array}\right)\\ &= -\lambda S_4 - \det\left(\begin{array}{cccccc} -\lambda & 1 & 0 \\ 1 & -\lambda & 1\\ 0 & 1 & -\lambda \end{array}\right)\\ &= -\lambda S_4 - S_3 \end{aligned}\end{align}

---

By induction, one can derive the following recursive relation between the terms of the sequence $S_n = \det(A-\lambda I_n)$:

\begin{align}\begin{aligned} S_1 &= -\lambda\\ S_2 &= \lambda^2-1\\ S_n &= -\lambda S_{n-1} - S_{n-2},\quad \text{ for all }n\geq 3 \end{aligned}\end{align}

To prove this, one only needs use what I did in the first few terms as a guideline:

First, cofactor expansion of $S_{n}$ along the first row, which yields two determinants, the first of which you should recognize as $S_{n-1}$ (it will have a multiplicative factor of $(-\lambda)$ out front from the cofactor expansion). Second, cofactor expansion of the second term along the first column, and the second term should now be recognizable as $S_{n-2}$.

---

In response to the comment, the recurrence is the easy part. If you have access to a symbolic mathematics engine (like Mathematica), you can implement the recurrence easily and compute it for your desired $n$. However, once you need to solve it, there aren't a lot of easy ways to do this. One reference I might point you to is this paper about Toeplitz matrices (your matrix is a special case of this).

In this, they state (Proposition 2.1, with $a=0$) the eigenvalues are (adapting to your specific case) $$\lambda_k = -2\cos(k\pi/(n+1))$$ where $n$ is the same $n$ from the recurrence relation and $1\leq k \leq n$. However, their proof relies on a working knowledge of Chebyshev polynomials of the first kind, which may not be that helpful.

Additionally, they provide a number of references which may or may not be helpful, but what you're looking for specifically is the eigenvalues of a Toeplitz matrix.

Also, this might be relevant.

This post from MO might be relevant.

Answer 2

The matrix $A$ can be written as the product of three matrices as follows:

$$A=\begin{pmatrix} e_2 & e_1 & e_4 & e_3 & e_6 & e_5 & \dots \end{pmatrix} \begin{pmatrix} e_1\\ e_2\\ e_3\\ e_2+e_4\\ e_5\\ e_4 + e_6\\ \vdots \end{pmatrix} \begin{pmatrix} e_1 + e_3\\ e_2\\ e_3+ e_4 \\ e_4\\ e_5+e_5\\e_6\\\vdots \end{pmatrix}$$

where $e_n$ is the standard $nth$ vector.

The first matrix is orthogonal matrix, the second matrix is lower triangular and the third is upper triangular. Can you figure out the eigenvalues now (hint: look at the diagonal of the 2nd and 3rd matrix)