2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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: $\endgroup$ – Logician6 Oct 25 '16 at 18:38
  • $\begingroup$ 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. $\endgroup$ – Logician6 Oct 25 '16 at 18:49
  • $\begingroup$ 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. $\endgroup$ – Logician6 Oct 25 '16 at 18:57
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Dagremu Oct 26 '16 at 17:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Dagremu Oct 26 '16 at 21:26
1
$\begingroup$

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$

Now to prove your question:

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.

UPDATE: Corrected my mistake on Claim 3. Should have written "solution", not "nonzero solution".

$\endgroup$
  • $\begingroup$ Very interesting! Regarding Claim 3, how does this jibe with the fact that 0 is an eigenvalue of $B_n$ whenever $n$ is odd? $\endgroup$ – Dagremu Oct 26 '16 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Logician6 Oct 26 '16 at 19:21
  • 1
    $\begingroup$ While your answer is awesome and I thank you for it, I'm accepting the "pretty theorem" approach because I'm a lazy ingrate :) $\endgroup$ – Dagremu Oct 26 '16 at 20:58
  • $\begingroup$ Understandable. Just know that this answer wasn't for nothing. I might have stumbled upon a non-determinant approach to compute the characteristic polynomial. The drawback is the generated polynomial is of course very recursive...and well...very vague from a computation standpoint. But it might do a nice theoretical job (as something that exists) considering it took no real colossal theoretical work (only a love for induction) to create. $\endgroup$ – Logician6 Oct 27 '16 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.