Eigenvalues of Laplacian Matrix

Gold Member
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

Last edited:

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

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.

Gold Member
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.

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.

joshmccraney
Gold Member
Thanks so much! I really appreciate this Hawkeye!