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

352 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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.