I was able to show that the eigenvalues of a normalized graph Laplacian matrix for some graph $G$ are in the range $[0,2]$. However, I have no idea how to show that the graph $G$ must be bipartite if $\lambda_n = 2$.
[Math] Largest eigenvalue of a normalized graph Laplacian
bipartite-graphseigenvalues-eigenvectorsgraph-laplacian
Related Solutions
This is a quick exercise in matrix algebra:
$$ D^{-1/2} (D- A) D^{-1/2} = I - D^{-1/2} A D^{-1/2} $$
Then notice $\lambda$ is an eigenvalue of $M$ if and only if $1-\lambda$ is an eigenvalue of $I-M$. In fact the eigenvectors corresponding to $\lambda$ for $M$ are the same as the eigenvectors corresponding to $1-\lambda$ for $I-M$, and vice versa.
If I haven't made any error in my code, the answer is no
Here is a counter example:
$L=\begin{bmatrix} 1 & 0 & 0 & -1 & 0 & 0\\ 0 & 3 & 0 & -1 & -1 & -1\\ 0 & 0 & 2 & 0 & -1 & -1\\ -1 & -1 & 0 & 2 & 0 & 0\\ 0 & -1 & -1 & 0 & 2 & 0\\ 0 & -1 & -1 & 0 & 0 & 2\\ \end{bmatrix} $
This graph is connected, and the Laplacian has eigenvalues $\left({(5 + \sqrt{17})/2, 3, 2, 2, (5 - \sqrt{17})/2, 0}\right)$
Now take the weights:
$L_w= \begin{bmatrix} 1. & 0. & 0. & -1. & 0. & 0.\\ 0. & 1. & 0. & 2. & -4. & 1.\\ 0. & 0. & -3. & 0. & 4. & -1.\\ -1. & 2. & 0. & -1. & 0. & 0.\\ 0. & -4. & 4. & 0. & 0. & 0.\\ 0. & 1. & -1. & 0. & 0. & 0.\\ \end{bmatrix} $
this has eigenvalues $({-6.82741, 5.88255, -2.55556, 1.50042, 0, 0})$.
for completeness, here is the python code I used to find the counterexample:
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
#magic
import warnings
warnings.filterwarnings('ignore')
import random
np.set_printoptions(precision=3)
import math
def randomWeightLaplacian(A):
#given an adjacency matrix, give random symetric weights between -10 and 10 (avoiding 0)
#return the weighted Laplacian and the Laplacian of the unweighted graph
n=A.shape[0] #order of the graph
L=np.zeros((n,n)) #weighted Laplacian
Lb=np.zeros((n,n),int) #unweighted Laplacian
for i in range(n):
for j in range(i+1,n):
if A[i][j]==1:
w=random.choice([-1,1])*random.choice([i for i in range(1,10)])
L[i][j]=w
L[j][i]=w
Lb[i][j]=-1
Lb[j][i]=-1
for i in range(n): #diagonal
L[i][i]=-sum(L[i][:])
Lb[i][i]=-sum(Lb[i][:])
return L,Lb
def numberSmall(array,pres=1e-5):
#number of small element in the array
cc=0
for i in array:
#print(i)
if math.isclose(i, 0., abs_tol=pres):
#print(i)
cc=cc+1
return cc
n,m=3,3 #size of the partition
ccw,ccb=0,0 #multiplicity of 0 in L and Lb
i=1
while ccw==ccb:
print(i)
i=i+1
G=nx.bipartite.random_graph(n,m, 1/3)
A=nx.to_numpy_array(G)
#networkx function giving the adjacency matrix of a random bipartite graph
L,Lb=randomWeightLaplacian(A)
G=nx.from_numpy_array(A)
eigenval,eigenvect=np.linalg.eig(L)
eigenvalb,eigenvectb=np.linalg.eig(Lb)
ccw=numberSmall(eigenval)
ccb=numberSmall(eigenvalb)
nx.draw(G)
print("number of connected components:",ccb," mutliplicity of 0 in the weighted graph:",ccw,"\n")
print(L)
print(Lb)
Edit
my example has a diagonal element $0$ artificially (some weights cancel out) but this is not necessary. One can adapt the code adding/replacing with this piece, and still get counterexamples
L,Lb=randomWeightLaplacian(A)
flag=True
for i in range(n+m):
if L[i][i]==0 and Lb[i][i]!=0:
flag=False
if flag:
eigenval,eigenvect=np.linalg.eig(L)
eigenvalb,eigenvectb=np.linalg.eig(Lb)
ccw=numberSmall(eigenval)
ccb=numberSmall(eigenvalb)
Best Answer
If $\lambda_n$ is the largest eigenvalue of the normalized Laplacian matrix of a graph $G$, then $$\lambda_n=\sup_x\frac{\sum_{u\sim v}\big(x(u)-x(v)\big)^2}{\sum_v\big(x(v)\big)^2\deg(v)}\le2$$ since $$\big(x(u)-x(v)\big)^2\le2\bigg(\big(x(u)\big)^2+\big(x(v)\big)^2\bigg).$$ Therefore, equality holds only when $x(u)=-x(v)$ for every edge $\{u,v\}$ in $G$. Now, since $x\ne0$, $G$ has a connected component.
On the other hand, if $G$ has a connected bipartite component, then we can choose $x$ so as to make $\lambda_n=2$.