Eigenvalues of laplacean matrix of directed graph are all non-zero when calculated in mathematica

Question

I have a problem where I am given the incidence matrix of a directed graph, and need to calculate its Laplacean matrix and respective eigenvalues. Since it is a relatively large graph, it's reasonably suggested to do this using software. The incidence matrix I am given, formatted for input in mathematica, is:

{{0,0,0,0,0,0,1,0,0,0},{1,0,0,0,0,0,0,0,0,0},{0,1,-1,0,-1,0,0,1,0,0},{-1,0,0,0,0,1,0,0,0,1}, 
{0,0,0,0,0,-1,-1,0,1,0},{0,-1,0,0,0,0,0,0,0,0},{0,0,0,-1,0,0,0,0,0,0},{0,0,1,0,0,0,0,0,0,0}, 
{0,0,0,1,1,0,0,0,0,-1},{0,0,0,0,0,0,0,0,-1,0},{0,0,0,0,0,0,0,-1,0,0}} 

It's my understanding that the Laplacean matrix should have at least one zero eigenvalue. But when I calculate in Mathematica, the set of eigenvalues I get is {4,3,3,3,1,1,1,1,1,1,1}. I do this by:

m = {{0,0,0,0,0,0,1,0,0,0},{1,0,0,0,0,0,0,0,0,0},{0,1,-1,0,-1,0,0,1,0,0},{-1,0,0,0,0,1,0,0,0,1}, 
    {0,0,0,0,0,-1,-1,0,1,0},{0,-1,0,0,0,0,0,0,0,0},{0,0,0,-1,0,0,0,0,0,0},{0,0,1,0,0,0,0,0,0,0}, 
    {0,0,0,1,1,0,0,0,0,-1},{0,0,0,0,0,0,0,0,-1,0},{0,0,0,0,0,0,0,-1,0,0}} 
g = IncidenceGraph[m]
k = KirchoffMatrix[g]
Eigenvalues[k]

Some of my colleagues have tried this in different mathematical software (Sagemath, numpy) and we have all arrived at different results for the eigenvalues, despite checking that we didn't have any typographical errors. What is behind this discrepancy, and what is the correct method to approach this problem using software?

Answer 1

You are arriving at different results that don't have the properties you expect because the Laplacian matrix of a directed graph

1. does not have a standard definition, and
2. does not have all the nice properties we expect from the Laplacian matrix of an undirected graph.

For an undirected graph, the definition of the Laplacian matrix is straightforward: its $(i,i)$ entry is the degree of vertex $i$, and its $(i,j)$ entry for $i\ne j$ is $-1$ if there is an edge $ij$ and $0$ otherwise. There are lots of ways we can try to generalize this to directed graphs:

• When we have an edge $i \to j$, should we put a $-1$ in the $(i,j)$ entry and a $0$ in the $(j,i)$ entry? Or a $+1$ in the $(i,j)$ entry? Or maybe $-1$ in both? (Mathematica makes the first choice.)
• Should the $(i,i)$ entry record the out-degree of vertex $i$? Or the in-degree? Or maybe their sum, or their difference? (Mathematica takes the sum.)

In the case of the undirected Laplacian, there is an eigenvalue of $0$ because the all-$1$ vector is an eigenvector: to put it differently, the sum of every row is $0$. If each edge $i \to j$ puts a $-1$ in entry $(i,j)$ and a $0$ in entry $(j,i)$, then the diagonal should record only the out-degree for this to work.

But we might have to make different design decisions to preserve different properties of the undirected Laplacian matrix. So you should first decide what you want the Laplacian matrix to do, and then figure out if there is a way to define it so that it has those properties.