[Math] Is the Laplacian matrix of a directed graph positive semi-definite

graph-laplacian

Define the Laplacian matrix as $L = D – A$. Here $A$ is the adjacency matrix of the directed graph so that the entries $A_{ij}$ of $A$ are equal to $1$ if there is an arrow form the vertex $j$ to $i$ and $0$ otherwise, and $D = \operatorname{diag}(\sum_{j=1}^n A_{1j},\cdots,\sum_{j=1}^n A_{nj})$.

My question is: $L$ is positive semi-definite?

By Gershgorin's Theorem is known that all eigenvalues of L has their real part larger or equal to $0$. But that doesn't implies positive semi-definiteness, right? So, is $L$ is positive semi-definite, and how to prove it?

Best Answer

The two vertex graph with one directed edge provides a counterexample. In that case the Laplacian is given by $$\left( \begin{array}{cc} 1 & -1 \\ 0 & 0 \\ \end{array} \right)$$ For the vector $x = (x_1, x_2)$ we have that $$x^TLx = x_1(x_1 - x_2)$$ We can make this negative by choosing $x_2 > x_1 > 0$.

Related Solutions

[Math] Laplacian matrix of the weighted graph

It is not strictly positive definite because the constant vector has eigenvalue 0. But it is non-negative definite. Let D denote the diagonal matrix of total edge weights, and denote the diagonal entries by $d_i$. For any vector $v$, we have

$v^t(D-W)v=v^tDv-v^tWv=\sum_iv_i^2d_i-\sum_{ij}w_{ij}v_iv_j$

Now I assume that $w_{ii}=0$ and $w_{ij}=w_{ji}$. Then the second term is equal to $2*\sum_{i<j} w_{ij}v_iv_j$. Furthermore, we can rewrite the first term as $\sum_{i}v_i^2(\sum_{j>i}w_{ij}+\sum_{j<i}w_{ij})=\sum_{i<j} v_i^2w_{ij}+\sum_{i>j}v_i^2w_{ij}=\sum_{i<j}(v_i^2+v_j^2)w_{ij}$ where the last equality follow by interchanging i and j in the second sum. Putting it together, we see $v^tLv=\sum_{i<j} (v_i^2+v_j^2-2v_iv_j)w_{ij}=\sum_{i<j} (v_i-v_j)^2w_{ij}\ge 0$, as desired.

Left kernel of directed Laplacian of a graph

[This answer is an extended version of my comment, with more references.]

Let $V$ be the set of vertices of your digraph. Let $A$ be the transpose adjacency matrix of $V$ (that is, the $V \times V$-matrix whose $\left(i,j\right)$-entry is the number of edges from $j$ to $i$). Let $D$ be the diagonal $V \times V$-matrix whose $\left(i,i\right)$-th entry is the outdegree of vertex $i$. Depending on whom you ask, the Laplacian $L$ of the digraph is either $D - A$ or $A - D$ or $\left(D - A\right)^T$ or $\left(A - D\right)^T$. Of course, any statement about one of these four Laplacians can easily be translated into a statement about the other three, so it does not matter which one we take to be "the" Laplacian. In the following, I shall define the Laplacian $L$ to be $A - D$. It is easy to see that the row vector $e := \left(1\right)_{v \in V} \in \mathbb{Z}^V$ satisfies $eL = 0$.

Your claim is that if the digraph is strongly connected, then we can find a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$ and whose entries are positive.

Here are three sources that prove this:

Siddhartha Sahi, Harmonic vectors and matrix tree theorems, arXiv:1309.4047v1. (Sahi defines the Laplacian $L$ to be $D - A$ rather than $A - D$, but this is of course insubstantial, since it's just a matter of replacing $D$ by $-D$. Also, instead of allowing multiple edges, Sahi puts weights on the edges of the digraph; this is a more general setting, to which you can easily reduce yours because you can replace $k$ parallel edges by a single edge with weight $k$.) Sahi defines a "harmonic vector" as a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$; then he explicitly constructs a certain vector (called the "weight vector"), and proves that it is harmonic (in his Theorem 1). The entries of this weight vector count "$i$-trees" (= directed spanning trees with root $i$); it is easy to see that when the digraph is strongly connected, these entries are all positive integers (i.e., for each vertex $i$, there exists at least one $i$-tree). So this weight vector is a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$ and whose entries are positive.
Arash Asadi, Spencer Backman, Chip-Firing and Riemann-Roch Theory for Directed Graphs, arXiv:1012.0287v2 . Lemma 3.1 here shows that if the digraph is strongly connected, then there exists a vector $R \in \mathbb{Z}^V$ such that $\overrightarrow{Q}^T R = 0$, where their matrix $\overrightarrow{Q}^T$ is easily seen to be our $D - A = -L$. Note that the proof of Lemma 3.1 in this paper omits explaining why there exists any nonzero vector $R\in \mathbb{Q}^V$ satisfying $\overrightarrow{Q}^{T}R=0$; but this is easy to see: We already know that the nonzero row vector $e$ satisfies $eL = 0$, and thus the matrix $L$ is singular; hence, there exists a nonzero vector $R\in \mathbb{Q}^V$ satisfying $LR = 0$. This vector $R$ thus must also satisfy $\overrightarrow{Q}^T R = 0$, since $\overrightarrow{Q}^T = -L$.
A. Björner and L. Lovasz, Chip-firing games on directed graphs, J. Algebraic Combin., 1(4), 1992, pp. 305–328. Proposition 4.1 (i) proves that the digraph has a strictly positive period vector -- which is defined to be a column vector $v \in \mathbb{Z}^V$ that satisfies $Lv = 0$ and whose entries are positive. The proof here is a bit of an overkill, due to the authors showing several things at once.

Best Answer

Related Solutions

[Math] Laplacian matrix of the weighted graph

Left kernel of directed Laplacian of a graph

Related Question