# Max and min eigenvalues of the “normalized” adjacency matrix of a path

Setup: Let $A$ be the $n \times n$ adjacency matrix of a path with $n$ nodes, so the $ij^\text{th}$ element of $A$ is $a_{ij} = 1(|i-j|=1)$. I.e. the elements just off the main diagonal are $1$, and everything else is $0$.

Now define $B$ as equal to $A$, but with row sums normalized to equal $1$. I.e., $b_{ij} = a_{ij} / a_{i+}$, where $a_{i+}$ is the $i^\text{th}$ row sum of $A$. Here are the matrices:

$$A = \begin{bmatrix} 0&1 \\ 1&0&1&& \mathbf 0 \\ &1&0& \ddots \\ &&\ddots&\ddots &1& \\ & \mathbf 0&&1&0&1 \\ &&&&1&0 \end{bmatrix},\,\,\,\, B = \begin{bmatrix} 0&1 \\ 1/2&0&1/2&& \mathbf 0 \\ &1/2&0& \ddots \\ &&\ddots&\ddots &1/2& \\ & \mathbf 0&&1/2&0&1/2 \\ &&&&1&0 \end{bmatrix}.$$

Note that the 1st and last rows have 1 non-zero element (since the nodes at the ends of the path have only 1 neighbor), while the middle rows have two non-zero elements (since the middle nodes have a neighbor on each side).

My question: Can you prove that the max and min eigenvalues of $B$ are $1$ and $-1$, respectively, for any $n \ge 2$? I've checked that this is true (with a computer program) for all $n$ from 2 to 500. So I'm pretty confident that it's true in general, but I'm wondering if there's a proof.

Context: The reason I care about this is that $B$ appears in a statistical model I'm using (a CAR spatial model), and the max and min eigenvalues of $B$ determine the parameter space for a parameter in the model.

This is clearly closely related to the following asked-and-answered question: Computing eigenvalue of the adjacency matrix of a path. There they wanted all eigenvalues of $A$, whereas I want the max and min eigenvalues of $B$.

Also, although this might not be helpful, here's a plot of all $n$ eigenvalues of $B$, for $n = 2,\ldots,16$.

• An interestng problem indeed. I wish I had a better linear background because it seems like something to ask that's pretty second-nature to someone who knows the trickery. After trying to work out a roundabout proof (but to no avail yet), here's my insight (in the next comment) to you or anyone else trying to solve this problem: – Logician6 Oct 25 '16 at 18:38
• 1) Brute force induction involving the characteristic polynomial seems like a bridge to nowhere. 2) Pretty sure the matrix is normal. In that case, you do have the Spectral Theorem (i.e. an orthonormal basis of eigenvectors) at your disposal, but there's a catch: Some of the eigenvalues are complex-valued, because the row sum normalization causes it to lose self-adjointness. Still might be helpful. – Logician6 Oct 25 '16 at 18:49
• 3) This is the strategy I'm leaning towards. I think the property to exploit might be that given an eigenvalue $\lambda$ and eigenvector $(a_1, \dots, a_n)$, you have $a_2= \lambda a_1$ and $a_k=2\lambda a_{k-1}-a_{k-2}$ for $2<k \leq n$. You also have $a_{n-1}=\lambda a_n$, and $a_{n-k}=2 \lambda a_{n-k+1}-a_{n-k+2}$ for $2<k \leq n$. I think there might be an inductive trick to be found, here. – Logician6 Oct 25 '16 at 18:57

The row sums of your matrix are 1 and by Gersgorin's theorem this will be the largest eigenvalue. There is a diagonal matrix $D$ such that $DBD^{-1}$ is symmetric. (Exercise.) The matrix $B$ is a weighted adjacency matrix of a bipartite graph, so its spectrum is symmetric about zero, whence $-1$ is an eigenvalue.

• I can follow the first part about Gersgorin's theorem (after consulting Wikipedia) -- very helpful. And I found a matrix $D$ that meets your criterion: $D = c \cdot diag(1/\sqrt{2},1,1,\dots,1,1,1/\sqrt{2})$, for any non-zero $c$. I don't see the relevance of this, though. I've seen elsewhere on the web that $A$, being the adjacency matrix of a bipartite graph, has a symmetric spectrum. Could you please explain or give a reference for why this still holds for $B$? – Dagremu Oct 26 '16 at 17:09
• I figured it out, after some reading on bipartite graphs. For posterity: Since a path is a bipartite graph, the rows and columns of $B$ can be arranged so that $B$ is a block matrix, with 0-matrices on the diagonal and 2 non-zero subblocks $B_1$ and $B_2$ off-diagonal, both of which have row sums = 1. Now let $v = [\textbf{1}, -\textbf{1}]^T$, where the two 1-vectors have appropriate dimension. Then $B v = [-B_1 \textbf{1}, B_2 \textbf{1}]^T = [-\textbf{1}, \textbf{1}]^T = -v$. So -1 is an eigenvalue of $B$, and by Gersgorin it's the minimum eigenvalue. – Dagremu Oct 26 '16 at 21:26

Ok, after a lot of brainstorming, I came up with a proof. The advantages are that it's very constructive, gives a bit of an algorithmic picture of what goes on with the Eigenvalues, and uses nothing abstract (no graph theory!). The disadvantages?...Well...it's pretty dang technical/inefficient--you may even want to go as far as say that this is "brute force". The first answer gives the more "eloquent use of pretty theorems" approach.

Let $B_n$ denote the normalized $n \times n$ adjacency matrix. We will begin by proving the following claims.

Claim 1. Given an eigenvalue $\lambda$ of $B_n$ and an eigenvector $\left[\begin{matrix} a_1 \\ \vdots \\ a_n \end{matrix}\right]$, we have $a_2=\lambda a_1$, $a_{n-1}=\lambda a_n$ and $a_k=2\lambda a_{k-1}-a_{k-2}$ for $2<k \leq n$.

Proof. Observe the recursive pattern \begin{align*} \left[\begin{matrix} a_2 \\ \frac{a_1}{2}+\frac{a_3}{2} \\ \vdots \\ \frac{a_{n-2}}{2}+\frac{a_n}{2} \\ a_{n-1} \end{matrix}\right]=B_n\left[\begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{n-1} \\ a_n \end{matrix}\right]=\lambda \left[\begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{n-1} \\ a_n \end{matrix}\right]. \quad \square \end{align*}

Claim 2. Given an eigenvalue $\lambda$ of $B_n$, define \begin{align*} p_k(\lambda)=\begin{cases} 1, & \text{if $k=1$,} \\ \lambda, & \text{if $k=2$,} \\ 2\lambda p_{k-1}(\lambda)-p_{k-2}(\lambda), & \text{if $k>2$.} \end{cases} \end{align*} We find $\left[\begin{matrix} p_1(\lambda) \\ \vdots \\ p_n(\lambda) \end{matrix}\right]$ is an eigenvector.

Proof. choose an eigenvector $\left[\begin{matrix} a_1 \\ \vdots \\ a_n \end{matrix}\right]$ of $\lambda$. Using Claim 1, one can show that $\left[\begin{matrix} a_1 \\ \vdots \\ a_n \end{matrix}\right]=a_1 \left[\begin{matrix} p_1(\lambda) \\ \vdots \\ p_n(\lambda) \end{matrix}\right]$, which means $a_1$ must be non-zero. Our conclusion follows. $\quad \square$

Claim 3. $\lambda$ is an eigenvalue of $B_n$ if and only if $\lambda$ is a solution to $0=\lambda p_n(\lambda)-p_{n-1}(\lambda)$. (we have more generally found that $\lambda p_n(\lambda)-p_{n-1}(\lambda)$ is the "characteristic polynomial" of $B_n$)

Proof. $\implies$ Follows from applying Claim 1 to the eigenvector $\left[\begin{matrix} p_1(\lambda) \\ \vdots \\ p_n(\lambda) \end{matrix}\right]$ obtained from Claim 2 and getting $p_{n-1}(\lambda)=\lambda p_n(\lambda)$.

$\impliedby$ Follows from the fact that \begin{align*} \left[\begin{matrix} p_2(\lambda) \\ \frac{p_1(\lambda)+p_3(\lambda)}{2}\\ \vdots \\ \frac{p_{n-2}(\lambda)+p_n(\lambda)}{2} \\ p_{n-1}(\lambda) \end{matrix}\right]=B_n \left[\begin{matrix} p_1(\lambda) \\ p_{n-1}(\lambda) \\ \vdots \\ p_{n-1}(\lambda) \\ p_n(\lambda) \end{matrix}\right]=\lambda \left[\begin{matrix} p_1(\lambda) \\ p_2(\lambda) \\ \vdots \\ p_{n-1}(\lambda) \\ p_n(\lambda) \end{matrix}\right], \end{align*} by our converse hypothesis (the hypothesis is applied to the $n$th entry in particular). $\quad \square$

Final Proof. It shall suffice by Claim 3 to show that all real solutions to $0=\lambda p_n(\lambda)-p_{n-1}(\lambda)$ are within the bounds of $[-1, 1]$. It is easy to verify using our recursive construction that $-1, 1$ is a solution to $0=\lambda p_n(\lambda)-p_{n-1}(\lambda)$, for all $n \geq 2$. Next, we check that all zero solutions are bounded by $[-1, 1]$. This is done by just using calculus and recursion to show that $\lambda p_n(\lambda)-p_{n-1}(\lambda)$ never hits zero outside of $[-1, 1]$. $\quad \square$
The final step is rather inconvenient, but I believe it's do-able since $\lambda p_n(\lambda)-p_{n-1}(\lambda)$ turns out to be monotonic outside of $[-1, 1]$. I'll leave it up to you unless you find it too hard/tedious and rather have me cook it up.
• Very interesting! Regarding Claim 3, how does this jibe with the fact that 0 is an eigenvalue of $B_n$ whenever $n$ is odd? – Dagremu Oct 26 '16 at 17:31
• My bad. I thought $0$ wasn't an eigenvalue by definition of "eigenvalue". Now I realize only the eigenvector has to be nonzero. If that's the case, claim 3 becomes: "$\lambda$ is an eigenvalue of $B_{n \times n}$ if and only if $\lambda$ is a solution to $0=\lambda p_n(\lambda)−p_{n-1}(\lambda)$." I don't think zero disrupts anything inherently. I just got the definition mixed up. – Logician6 Oct 26 '16 at 19:21