MathOverflow is a question and answer site for professional mathematicians. 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 adjacency 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 = \begin{bmatrix} B-A, & -A \\\\ A-B, & D \end{bmatrix}\in \mathbb{R}^{2n\times 2n}$$ 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 all have positive real parts. Anyone can help prove or disprove the above claim? (Gershgorin Circle Theorem does not apply here because $M$ is not diagonally dominate)

Some facts: Both $(B-A)$ and $(D-A)$ have exactly one zero eigenvalue and all the rest eigenvalues lie in the open right half complex plane because the directed graph is strongly connected. In particular, $(B-A)$ is called the Laplacian matrix of the graph.

share|cite|improve this question

the answer was essentially correct but i believe H should be defined as H11=H21=H22=1 and H12=0.

the resulting matrix HMH^T is block upper triangular with B-A and D-A on the diagonal, hence is hurwitz stable.

although the eigenvalues change, the inertia theorem guarantees that their stability type cannot change, i.e. they cannot cross the imaginary axis.

share|cite|improve this answer
But $M$ is non-symmetric. I don't think you can apply the inertia theorem. There ought to be some way to fix the argument, but I haven't figured it out yet. – Felix Goldberg Sep 19 '12 at 20:22
Hi, Felix. Do you have any suggestions on how to handle this problem? All the answers posted here are not correct. – Zhang Changhe Sep 25 '12 at 9:31

I think I have a counterexample. Try this:

$A=\begin{bmatrix}1 & 1 & 0 & 1 \\\\ 0 & 1 & 1 & 0 \\\\ 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \end{bmatrix}$.

When I construct $M$ I get a pair of conjugate complex eigenvalues in its spectrum.

share|cite|improve this answer
Hi, Felix. Thanks again. I calculate the eigenvalues of M by the following matlab code %% A = [1 1 0 1; 0 1 1 0; 1 0 1 0; 0 1 0 1]; B = diag([3,2,2,2]); D = diag([2,3,2,2]); M = [B-A, -A; A-B, D]; eig(M) %% The result is -0.0000 0.3501 + 0.8344i 0.3501 - 0.8344i 1.3820 2.0000 2.7600 3.6180 3.5398 %% Yes, the eigenvalues have a pair of conjugate complex eigenvalues. But all the eigenvalues have positive real parts except the zero eigenvalue. So this is not a counterexample. – Zhang Changhe Jan 2 '13 at 11:36
@ZhangChanghe: Oops, my bad. I'll look again. – Felix Goldberg Jan 2 '13 at 16:46

I think your claim is true. Taking your matrix $M$ and multiplying from the left by $$H=\begin{bmatrix} I, & 0 \\\ -I, & I \end{bmatrix},$$ and from the right by its transpose, $$H^t=\begin{bmatrix} I, & -I \\\ 0, & I \end{bmatrix},$$ the eigenvalues don't change, yet the matrix you get is $$HMH^t=\begin{bmatrix} B-A, &B \\\ 0, & D-A \end{bmatrix}.$$ The eigen values of the above matrix are those of $B-A$ and those of $D-A$ and are all non-negative as you already explained.

share|cite|improve this answer
Something seems to be amiss here: $HMH^{T}$ has the same inertia as $M$ but the eigenvalues do change. Maybe you meant $H^{-1}$, which is also a nice block matrix? – Felix Goldberg Sep 19 '12 at 13:20
Sorry, I wasn't completely awake when writing my comment. It has several quite embarrassing mistakes.. – puzne Sep 19 '12 at 16:40

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.