2
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – user1551 Nov 7 '18 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.