Eigenvalues of a special block matrix associated with strongly connected graph - MathOverflow

Eigenvalues of a special block matrix associated with strongly connected graph

2012-09-18T05:40:24Z

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.

Answer by puzne for Eigenvalues of a special block matrix associated with strongly connected graph

2012-09-19T12:28:53Z

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.

Answer by nir cohen for Eigenvalues of a special block matrix associated with strongly connected graph

2012-09-19T16:00:47Z

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.

Answer by Felix Goldberg for Eigenvalues of a special block matrix associated with strongly connected graph

2012-12-28T11:02:29Z

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.