# Eigenvalues of a special block matrix associated with strongly connected graph

## Definition

Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, that is $a_{i,j}=1$ if $(j,i)\in E$, and $a_{i,j}=0$ otherwise.

$B$ and $D$ are two diagonal matrices, where $b_{ii}=\sum_{j=1}^na_{i,j}$ and $d_{ii}=\sum_{j=1}^na_{j,i}$. In other words, the diagonal entries of $B$ are the row sum of $A$, and the diagonal entries of $D$ are the column sum of $A$.

## Problem

Now define a new matrix $M=\left[\begin{array}{c|c} B-A & -A \\ \hline A-B & D \end{array}\right]$. Since the column sum of $M$ are identical zeros, zero must be one of its eigenvalue. Can I claim that the rest eigenvalues all have positive real parts?

I tried many numerical examples, the rest eigenvalues have positive real parts. Anyone can help prove or disprove it? (Gershgorin Circle Theorem does not apply here because $M$ is not diagonally dominate)

-

I think we can simplify it a bit.

I understand you want to know whether the matrix has non-negative eigen values (ie >=0). Another way to look at it is, you want to know if the matrix is positive semi-definite or not. For a block matrix, this happens if and only if, the left-upper corner matrix (in your case B-A) and its schur complement is positive semi definite.

ie B-A is positive semidefinite and schur(B-A)=D-(inv(A-B)(B-A)(-A)) is positive semidefinite.

simplifying, schur(B-A)=D-A.

ie (B-A) and (D-A) should be positive semi definite.

-
Thanks so much for your reply. I am sorry I did not state the question clearly. The eigenvalue of M may be complex since the M is not symmetric. M is not a positive semi-definite matrix in most case. To my best knowledge, both (B-A) and (D-A) have exactly one zero eigenvalue, and all the rest eigenvalues have positive real part. (B-A) is called the Laplacian matrix of a graph. – Zhang Changhe Sep 17 '12 at 12:15
B-A and D-A are not positive semi definite for the strongly connected graph. The rank of B-A is n-1, and it is not revertible at all. – Zhang Changhe Sep 21 '12 at 7:23