# strongly connected $L$, then what are the eigenvalues of $L+L^T$?

I asked a similar question before. Now things become a bit different here.

Suppose $$L$$ is a non-symmetric Laplacian matrix, of which the corresponding graph is strongly connected. Is it true that $$L+L^T$$ (note that $$L+L^T$$ is symmetric) has at most one negative eigenvalue? I try many examples using Matlab numerically to find out that there is at most one negative eigenvalues, but I am not sure it is true or not.

Preliminaries on Graph Theory:

$$\textit{Graph}$$ is essentially a concept from the set theory. A graph containing $$n$$ nodes can be denoted by $$\mathcal{G}_n = (\mathcal{V}_n, \mathcal{E}_n)$$, where $$\mathcal{V}_n=\{v_1,\dots,v_n\}$$ is the $$\textit{node set}$$ and $$\mathcal{E}_n \subseteqq \mathcal{V}_n \times \mathcal{V}_n$$ is the $$\textit{edge set}$$. $$\epsilon_{ij}=(v_i,v_j), ~i,j \in \{1,\dots,n\}$$ represents an $$\textit{edge}$$ connecting nodes $$v_i$$ and $$v_j$$. When the elements in the edge set $$\mathcal{E}_n$$ are ordered pairs, $$\mathcal{G}_n$$ is a $$\textit{directed graph}$$ (or $$\textit{digraph}$$). Node $$i$$ of $$\epsilon_{ij}$$ is called the $$\textit{parent node}$$ and node $$j$$ is the $$\textit{child node}$$. A $$\textit{directed path}$$ is an ordered set of edges such that the child node of the previous edge is the parent node of the next edge, such as $${(v_1, v_2), (v_2, v_3),\dots}$$. A directed graph is called $$\textit{strongly connected}$$ if for every pair of nodes there is a directed path between them. The corresponding $$\textit{adjacent matrix}$$ to graph $$\mathcal{G}_n = (\mathcal{V}_n, \mathcal{E}_n)$$ is denoted by $$A_n=[a_{ij}] \in M_n, i,j \in {1,\dots, n}$$. It represents whether there is an edge between any two nodes, that is, $$a_{ji} > 0$$ when the edge $$(i,j) \in \mathcal{E}_n$$ and $$a_{ji} = 0$$ when the edge $$(i,j) \notin \mathcal{E}_n$$. The $$\textit{Laplacian matrix}$$ is denoted by $$L_n=[l_{ij}] \in M_n$$, where $$l_{ij} = \sum_{k=1, k \ne i}^{n}a_{ik}, i=j; ~ l_{ij} = -a_{ij}, i \ne j$$.

To generate a random strongly directed graph, one can image a graph where every two nodes are connected. However, the weights of the edges are different. For example, the weight of the edge from node $$i$$ to node $$j$$ is $$1$$ while that of the edge from node $$j$$ to node $$i$$ is $$10$$. So the ajacency matrix can be something like: $$\begin{bmatrix}0 & 1 & 2 \\ 10 & 0 & 3 \\ 3 & 4 & 0\end{bmatrix}$$ and the corresponding Laplacian matrix is $$\begin{bmatrix}3 & -1 & -2 \\ -10 & 13 & -3 \\ -3 & -4 & 7\end{bmatrix}$$

• Maybe we can participate if you tell us how to generate a random strongly connected Laplacian matrix. – Arash Nov 3 '18 at 3:43
• Please see the updated question. @Arash – winston Nov 3 '18 at 19:55

I do not think there is a reason for this property to be true. I was playing around and I think I found a counterexample. Consider the Laplacian matrix $$L=\left[\matrix{1 & 0 & -1& 0& 0\\-2 &2 & 0 & 0 & 0\\ 0 & -2 & 3 & -1 & 0\\-5 & 0 & 0 & 6 & -1\\0 & 0 & -150 & 0 &150}\right]$$ It is easy to see that the associated graph is strongly connected but the eigenvalues of $$L+L^T$$ are $$-57.1216$$, $$-0.7257$$, $$4.6800$$, $$14.1430$$ and $$363.0243$$ i.e. the matrix $$L+L^T$$ has two negative eigenvalues.
• As this answer shows, if two nodes can be connected by multiple arcs in the same direction, $L+L^T$ can have multiple negative eigenvalues. There is actually a simpler example: consider $$L=\pmatrix{ a&-a& 0&0\\ 0&1&-1&0\\ 0&0&a&-a\\ -1&0&0&1}.$$ Then $L+L^T=\pmatrix{A&C\\ C&A}$ where $A=\pmatrix{2a&-a\\ -a&2}$ and $C$ is constant. As $$\lim_{a\to+\infty}\frac1a(L+L^T)=\pmatrix{2&-1\\ -1&0}\oplus\pmatrix{2&-1\\ -1&0},$$ when $a$ is large, $\frac1a(L+L^T)$ will have two negative eigenvalues and so will $L+L^T$. One can verify that the first feasible $a$ is $6$. – user1551 Nov 7 '18 at 14:26