Eigenvalues of a special block matrix associated with strongly connected graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:47:41Z http://mathoverflow.net/feeds/question/107437 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107437/eigenvalues-of-a-special-block-matrix-associated-with-strongly-connected-graph Eigenvalues of a special block matrix associated with strongly connected graph Zhang Changhe 2012-09-18T05:40:24Z 2013-06-08T06:22:00Z <h2>Definition</h2> <p>Let $G=(V,E,A)$ be a <strong>strongly connected</strong> 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. </p> <p>$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$. </p> <h2>Problem</h2> <p>Now define a new matrix $$M = \begin{bmatrix} B-A, &amp; -A \\ A-B, &amp; 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 <strong>claim</strong> that the rest eigenvalues all have positive real parts?</p> <p>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)</p> <p>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. </p> http://mathoverflow.net/questions/107437/eigenvalues-of-a-special-block-matrix-associated-with-strongly-connected-graph/107555#107555 Answer by puzne for Eigenvalues of a special block matrix associated with strongly connected graph puzne 2012-09-19T12:28:53Z 2013-04-05T21:56:20Z <p>I think your claim is true. Taking your matrix $M$ and multiplying from the left by $$H=\begin{bmatrix} I, &amp; 0 \\ -I, &amp; I \end{bmatrix},$$ and from the right by its transpose, $$H^t=\begin{bmatrix} I, &amp; -I \\ 0, &amp; I \end{bmatrix},$$ the eigenvalues don't change, yet the matrix you get is $$HMH^t=\begin{bmatrix} B-A, &amp;B \\ 0, &amp; 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. </p> http://mathoverflow.net/questions/107437/eigenvalues-of-a-special-block-matrix-associated-with-strongly-connected-graph/107584#107584 Answer by nir cohen for Eigenvalues of a special block matrix associated with strongly connected graph nir cohen 2012-09-19T16:00:47Z 2012-09-19T16:00:47Z <p>the answer was essentially correct but i believe H should be defined as H11=H21=H22=1 and H12=0.</p> <p>the resulting matrix HMH^T is block upper triangular with B-A and D-A on the diagonal, hence is hurwitz stable.</p> <p>although the eigenvalues change, the inertia theorem guarantees that their stability type cannot change, i.e. they cannot cross the imaginary axis.</p> http://mathoverflow.net/questions/107437/eigenvalues-of-a-special-block-matrix-associated-with-strongly-connected-graph/117400#117400 Answer by Felix Goldberg for Eigenvalues of a special block matrix associated with strongly connected graph Felix Goldberg 2012-12-28T11:02:29Z 2012-12-28T11:02:29Z <p>I think I have a counterexample. Try this:</p> <p>$A=\begin{bmatrix}1 &amp; 1 &amp; 0 &amp; 1 \\ 0 &amp; 1 &amp; 1 &amp; 0 \\ 1 &amp; 0 &amp; 1 &amp; 0 \\ 0 &amp; 1 &amp; 0 &amp; 1 \end{bmatrix}$.</p> <p>When I construct $M$ I get a pair of conjugate complex eigenvalues in its spectrum.</p>