Definition 8 [Wu 2006a]
μ(G) is defined as the supremum of the set of real numbers μ such that U(G-μI) is positive semidefinite for some real matrix U that is symmetric, irreducible, have zero row sums and nonpositive offdiagonal elements.
Lemma 2 [Wu and Chua 1995]
If A is a symmetric and irreducible real matrix with zero row sums and nonpositive offdiagonal elements and either AX is positive semidefinite or AX is negative semidefinite, then X is a matrix with constant row sums.
Since U is positive semidefinite, this implies that if U(G-μI) is positive semidefinite, then U(G-λI) is positive semidefinite for all λ≤μ. Lemma 2 indicates that μ(G) is only defined if G is a matrix with constant row sums.
Definition 9
The Laplacian matrix of a directed (simple) graph is defined as a zero row sums matrix L such that for i ≠ j, Lij = -1 if there is a directed edge from vertex i to vertex j and Lij = 0 otherwise.
It can alternatively be defined as L = D-A, where A is the adjacency matrix and D is the diagonal matrix with the outdegrees on the diagonal.
Definition 10
A square matrix A is normal if AA* = A*A.
Lemma 3 [Wu and Chua 1995]
If A is a real normal matrix and has constant row sum ε, then A has constant column sum ε.
Definition 11
A vertex of a directed graph is balanced if the indegree is equal to the outdegree. A graph is vertex-balanced if all vertices are balanced.
The definition above implies that a graph is balanced if and only if the Laplacian matrix has zero column sums. Lemma 3 indicates that directed graphs with normal Laplacian matrices are balanced [Wu 2005a, Lemma 20]. Examples of normal Laplacian matrices include circulant matrices.
Lemma 4 [Wu and Chua 1995]
If L is a normal Laplacian matrix, then L is irreducible if and only if L+LT is irreducible, i.e. the corresponding graph is connected if and only if it is strongly connected.
Lemma 5 [Wu 2006a]
If L is a normal Laplacian matrix, then μ(L) = minx≠0,∑xi = 0, xTWLx/xTx = minλRe(λ) where λ ranges over all eigenvalues of L not corresponding to the eigenvector of all 1's.
As Theorem 10 in this section indicates, μ(G) is a useful quantity that determines sufficient conditions for a network of dynamical systems to synchronize. Lemma 5 relates this quantity to eigenvalues of the matrix.
Lemma 6 [Wu 2005a]
If the algebraic connectivity of a directed graph G is strictly positive, then G has a vertex such that every other vertex has a directed path to it.
Lemma 7 [Wu 2005a]
For a balanced graph G with algebraic connectivity a, we have a > 0 ⇔ G is connected ⇔ G is strongly connected.
[Wu and Chua 1995] C. W. Wu and L. O. Chua. Synchronization in an array of linearly coupled dynamical systems. IEEE Transactions on Circuits and Systems, Part I, 42(8):430-447, 1995.
[Wu 2005a] C. W. Wu. Algebraic connectivity of directed graphs. Linear and Multilinear Algebra. 53(3):203-223, 2005.
[Wu 2006a] C. W. Wu. On a matrix inequality and its application to the synchronization in coupled chaotic systems. Complex Computing-Networks: Brain-like and Wave-oriented Electrodynamic Algorithms, Springer Proceedings in Physics. 104:279-288, 2006.
Copyright 2010 by Chai Wah Wu.