Why Is the Index Shifted in Laplacian Eigenvalues?

[member 428835]

hi pf!

I am reading a text and am stuck at a part. this is what is being said:

If $g$ is a graph we have $L(g) + L(\bar{g}) = nI - J$ where $J$ is the matrix of ones. Let $f^1,...f^n$ be an orthogonal system of eigenvectors to $L(g) : f^1 = \mathbb{1}$ and $L(g)f^i = \lambda_i f^i$. Evidently $L(g) + L(\bar{g}) = nI - J$ implies $L(\bar{g}) f^1 = 0$.

Now for $2 \leq i \leq n$ we have $L(\bar{g}) f^i = (n-\lambda_i)f^i$

The text continues by saying $\lambda_1(\bar{g}) = 0$

Thus we have that $\lambda_i(\bar{g}) = n - \lambda_{n-i+2}(g) : i \geq 2$. This is the part I don't understand. If eigenvalues of $L(g)$ are eigenvalues to $L(\bar{g})$ then I see that $\lambda_i (\bar{g})f^i = (n-\lambda_i)f^i \implies \lambda_i (\bar{g}) = n-\lambda_i(g)$ but the index is now wrong...please help me out!

Thanks so much!

Josh

 

[member 428835]

Can anyone help me out? Am I in the wrong section?

 

[Hawkeye18]

That is because the author puts eigenvalues in the increasing (non-decreasing, to be precise) order. You are correct that $L(\overline g) f^i = (n-\lambda_i) f^i$ for $i\ge2$, so $n-\lambda_i$, $i\ge 2$ are eigenvectors of $L(\overline g)$. Putting them into non-decreasing order you get exactly the formula you quoted.

 

[member 428835]

That is because the author puts eigenvalues in the increasing (non-decreasing, to be precise) order. You are correct that $L(\overline g) f^i = (n-\lambda_i) f^i$ for $i\ge2$, so $n-\lambda_i$, $i\ge 2$ are eigenvectors of $L(\overline g)$. Putting them into non-decreasing order you get exactly the formula you quoted.

Could you elaborate a little? I'm a little confused on what you mean by "putting" them in non-decreasing order.

 

[Hawkeye18]

The eigenvalues of $L(g)$ are $0=\lambda_1\le \lambda_2\le\lambda_3 \le \ldots \le \lambda_n$. The eigenvalues of $L(\overline g)$ are $0, n-\lambda_1, n-\lambda_2, \ldots, n-\lambda_n$. From the above inequalities for $\lambda_i$ we can write $n-\lambda_n\le n-\lambda_{n-1}\le\ldots\le n-\lambda_2$. A Laplacian is always positive semidefinite, so all eigenvalues are non-negative. So, $0=\lambda_1\le n-\lambda_n\le n-\lambda_{n-1}\le\ldots\le n-\lambda_2$ gives us all eigenvalues of $L(\overline g)$ in non-decreasing order. And by $\lambda_k(\overline g)$ the author means item # $k$ on this list.

 

[member 428835]

Thanks so much! I really appreciate this Hawkeye!