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.

-

3 Answers

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.

-

1
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 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 at 9:31

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 at 11:36
@ZhangChanghe: Oops, my bad. I'll look again. – Felix Goldberg Jan 2 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.

-

1
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 at 13:20
Sorry, I wasn't completely awake when writing my comment. It has several quite embarrassing mistakes.. – puzne Sep 19 at 16:40
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 30, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9124969244003296, "perplexity_flag": "head"}