5
$\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 adjacent 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=\left[\begin{array}{c|c} B-A & -A \\ \hline A-B & D \end{array}\right]$. 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 have positive real parts. Anyone can help prove or disprove it? (Gershgorin Circle Theorem does not apply here because $M$ is not diagonally dominate)

1 Answers 1

1

I think we can simplify it a bit.

I understand you want to know whether the matrix has non-negative eigen values (ie >=0). Another way to look at it is, you want to know if the matrix is positive semi-definite or not. For a block matrix, this happens if and only if, the left-upper corner matrix (in your case B-A) and its schur complement is positive semi definite.

ie B-A is positive semidefinite and schur(B-A)=D-(inv(A-B)(B-A)(-A)) is positive semidefinite.

simplifying, schur(B-A)=D-A.

ie (B-A) and (D-A) should be positive semi definite.

  • 0
    B-A and D-A are not positive semi definite for the strongly connected graph. The rank of B-A is n-1, and it is not revertible at all.2012-09-21