Is the Laplacian matrix of a directed graph positive semi-definite?

Question

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?

For positive semi-definiteness I meant $x^{T}Lx\geq0$ for all $x\in\mathbb{R}^n\setminus{0}$. — MarcosDNMaia, Jun 07 '15 at 15:57
It becomes positive definite if for $D$ you use the sum of in and out degrees. — N. S., Jun 07 '15 at 17:30

score 4 · Accepted Answer · answered Jun 07 '15 at 17:23

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$.

score 2 · Answer 2 · answered Jun 07 '15 at 17:34

Note that with your definition, the Laplacian corresponds to the quadratic form $$\sum_{ij \, \mbox{arc in D}} x_i^2-x_ix_j$$

It is easy to construct examples of such forms which are not positive semi-definite.

Now, if for $D$ you use the sum of in and out degree, the "new" Laplacian is corresponding to $$\sum_{ij \, \mbox{arc in D}} x_i^2-x_ix_j+x_j^2$$ which is positive definite as $$x_i^2-x_ix_j+x_j^2=(x_i-\frac{1}{2}x_j)^2 +\frac{3}{4} x_j^2$$

Is the Laplacian matrix of a directed graph positive semi-definite?

2 Answers2