Laplacian of bipartite graph

bipartite-graphsgraph theorygraph-laplacian

It is well know that in the case of weighted graph with positive weights, the dimension of the kernel of the Laplacian is the number of connected components of the corresponding graph.

This fails when negative weights are allowed, but I was wondering if this remained true if we restrained ourselves to bipartite graph?

In other words, for bipartite graphs with possibly negative weights, is the number of connected components the dimension of the kernel of the associated Laplacian?

Best Answer

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)
Related Question