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

## Problem

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.

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.

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

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

• 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