Is the product of graph Laplacians positive semidefinite

Question

For any weighted directed graph $G = (V,E,w)$ we can define the weighted Laplacian matrix $L=D-A$, where $A=[a_{ij}]$ is the adjacency matrix and $D=\text{diag}( d_1, …, d_n )$ is the in-degree matrix with $d_i = \sum_j a_{ij}$.

However, $L$ is not in general positive semi-definite. If we include the out-degree through the out-Laplacian matrix $L^o = D^o – A^\top$, where $D^o=\text{diag}( d_1^o, …, d_n^o )$ is the out-degree matrix with $d_i^o = \sum_j a_{ji}$, the quadratic form $x^\top ( L + L^o )x$ is positive semidefinite since,

$$ x^\top ( L + L^o )x = \sum_i\sum_j a_{ij}(x_i-x_j)^2 \geq 0.$$

If we define $Q=L+L^o$, I want to proof if $(Qx)^\top(-Lx) \leq 0$. This is equivalent to
\begin{align*}
(Qx)^\top(-Lx) \leq 0 &\iff -x^\top QLx \leq 0 \\
&\iff x^\top QLx \geq 0 \\
&\iff x^\top ( QL + L^\top Q )x \geq 0 \\
&\iff QL + L^\top Q \succeq 0
\end{align*}

Some properties that I have found

• $Q=Q^\top$ is positive semidefinite.

• By Gershgorin's Theorem we know that all the eigenvalues of $L$ have positive real part.

• Both, $L$ and $Q$ are diagonally dominant.

• $QL + L^\top Q \succeq 0$ is very similar to Lyapunov equation. This can be useful since $-L$ is a Hurwitz matrix and $Q\succeq 0 $.

Answer 1

What you're trying to prove is unfortunately not true. A counterexample will be given at the end; I'll explain how I got there.

First of all, the statement makes sense in a world where all matrices are normal:

Normal case

For simplicity, we work over the complex numbers. Let $M^*$ (resp. $x^*$) denote the Hermitian adjoint of a matrix $M$ (resp. column vector $x$). Recall that a matrix $M$ is normal if and only if it is unitarily equivalent to a diagonal matrix; that is, there exists a unitary matrix $U$ and a diagonal matrix $D$ such that $M = U^*DU$.

Proposition. If $M \in \mathbb{C}^{n\times n}$ is normal, then $\text{Re}(x^* M x) \geq 0$ for all $x\in \mathbb{C}^n$ if and only if all eigenvalues of $M$ lie in the closed right half-plane $\{z \in \mathbb{C} \, : \, \text{Re}(z) \geq 0\}$.

Proof. Note that $$ 2\cdot\text{Re}(x^*Mx) = x^*Mx + (x^*Mx)^* = x^*Mx +x^*M^*x = x^*(M + M^*) x. $$ Therefore we have $\text{Re}(x^*Mx) \geq 0$ for all $x \in \mathbb{C}^n$ if and only if $M + M^*$ is positive semidefinite. Let $M = U^*DU$; then $M + M^* = U^* (D + D^*) U$, so $M + M^*$ is positive semidefinite if and only if all eigenvalues of $M$ (i.e. the entries of $D$) lie in the closed right half-plane. $\quad\Box$

If $M$ is real and $x,y\in\mathbb{R}^n$, then $(x - iy)^\top M (x + iy) = x^\top M x + y^\top M y + ix^\top My - iy^\top M x$, so $\text{Re}((x + iy)^* M (x + iy)) = x^\top M x + y^\top M y$. Therefore:

Corollary. If $M \in \mathbb{R}^{n\times n}$ is normal, then $x^\top Mx \geq 0$ for all $x \in \mathbb{R}^n$ if and only if all eigenvalues of $M$ lie in the closed right half-plane $\{z \in \mathbb{C} \, : \, \text{Re}(z) \geq 0\}$.

Now for a solution in a world where all matrices are normal. As you observed, all eigenvalues of $L$ lie in the closed right half-plane, so if $L$ is normal then $x^\top L x \geq 0$ for all $x \in \mathbb{R}^n$. Let $Q^{1/2}$ denote the unique positive semidefinite square root of $Q$. Then for all $y \in \mathbb{R}^n$ we have $$ y^\top Q^{1/2} L Q^{1/2}y = (Q^{1/2}y)^\top L \, Q^{1/2}y \geq 0, $$ so if $Q^{1/2} L Q^{1/2}$ is normal then all eigenvalues of $Q^{1/2} L Q^{1/2}$ lie in the closed right half-plane. Now we use that $AB$ and $BA$ have the same eigenvalues (where $A = Q^{1/2}L$ and $B = Q^{1/2}$), so we find that the eigenvalues of $QL = Q^{1/2} Q^{1/2} L$ also lie in the closed right half-plane. Thus, if $QL$ is also normal, the conclusion follows.

The crucial property of normal matrices that we used can be formulated in terms of the numerical range: if $M$ is normal, then the numerical range of $M$ is the convex hull of the eigenvalues of $M$. However, this is not always true if $M$ is not normal, and if $n \leq 4$ then this fails for all non-normal matrices (see [MM55] and [Joh76]). In particular, this means that we may have $x^\top Mx < 0$ even if all eigenvalues have positive real part.

Matrices that arise from directed graphs are not typically normal. Furthermore, even if $L$ is normal, the same might not be true for $Q^{1/2}LQ^{1/2}$ or $QL$.¹ So we should start looking for counterexamples. Indeed, after trying a few small cases, I found the following counterexample: $$ A = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix},\quad L = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 2 & 1 \\ 0 & 0 & 0 \end{pmatrix},\quad Q = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix},\quad x = \begin{pmatrix} 2 \\ 1 \\ -4 \end{pmatrix}. $$ Then $x^\top QL x = -2$.

_{¹: The product of normal matrices is not necessarily normal. In fact, every square matrix is a product of two normal matrices: polar decomposition.}

References.

[MM55]: B. N. Moyls, M. D. Marcus, Field convexity of a square matrix, Proceedings of the American Mathematical Society, vol. 6 (1955), issue 6, pp. 981–983. DOI: 10.1090/S0002-9939-1955-0075921-5

[Joh76]: Charles R. Johnson, Normality and the numerical range, Linear Algebra and Its Applications, vol. 15 (1976), issue 1, pp. 89–94. DOI: 10.1016/0024-3795(76)90080-X