8
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 19, 2012 at 20:22
  • $\begingroup$ Hi, Felix. Do you have any suggestions on how to handle this problem? All the answers posted here are not correct. $\endgroup$ Sep 25, 2012 at 9:31
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 2, 2013 at 11:36
  • $\begingroup$ @ZhangChanghe: Oops, my bad. I'll look again. $\endgroup$ Jan 2, 2013 at 16:46
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Sep 19, 2012 at 13:20
  • $\begingroup$ Sorry, I wasn't completely awake when writing my comment. It has several quite embarrassing mistakes.. $\endgroup$
    – puzne
    Sep 19, 2012 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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