Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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


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)

share|cite|improve this question

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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