## Almost Decouplability of any Directed Weighted Network Topology

Cai, Ning 1 Khan, M. Junaid 2

1

College of Electrical Engineering, Northwest University for Nationalities, Lanzhou, China 2 PN Engineering College, National University of Sciences and Technology, Karachi, Pakistan

Abstract: This paper  introduces  a  conception  that  any  weighted  directed  network topology is almost decouplable, which can help to transform the topology into a similar form being composed of uncoupled vertices, and thus reduce the complexity of analysis for  networked  dynamical  systems.  As  an  example  of  its  application,  the  consensus problem  of linear multi-agent systems with time-varying network topologies is addressed.  As  a  result,  a  necessary  and  sufficient  condition  for  uniform  consensus  is proposed.

Key Words: Network; Consensus; Multi-Agent Systems

## 1. Introduction

We  are  entering  a  networked  world.  The  notion  of  complex  and  dynamical networks keeps on influencing nearly all kinds of disciplines, ranging from communication  networks,  power  networks, biological networks, and economic networks,  etc.  Its  impact  on  modern  engineering  and  science  has  already  been prominent, and will potentially be even far-reaching.

The graph topology of a network corresponds to certain matrix [1]. For dynamical networked systems, it is a fundamental technique to transform the network topology into similar canonical forms which are equivalent to the original network in the sense of system dynamics but are more convenient to analyze. It is usually expected that a complex network could be transformed into a similar diagonal canonical form, being composed of a number of uncoupled vertices [2]. Unfortunately, such a consideration does not always seem applicable, since a directed network is generally not guaranteed to be decouplable.

1 Corresponding author: Cai, Ning (e-mail: caining91@tsinghua.org.cn)

This paper will show that any given weighted directed network topology is almost decouplable, despite the diagonalizability of the associated matrix.

The  motivation  of  the  current  work  originated  from  our  study  on  consensus problems  for  dynamical  multi-agent  systems  [3-6].  Consensus  implicates  that  a system  achieves  certain  asymptotic  stability  even  if  there  are  no  equilibria,  and  it actually plays the role like equilibrium of isolated dynamical systems [3-5]. Due to its theoretical  importance,  the  consensus  problem  has  been  paid  extensive  attention  by scholars  in  the  area  of  control  theory  from  various  perspectives;  see  [7-11]  and references  therein.  Particularly,  a  general  framework  of  the  consensus  problem  for first-order systems is initially proposed in [8]. A necessary and sufficient condition for consensus of LTI first-order systems is given in [9]. Consensus problem of high-order systems is earlier addressed in [12-13]. Both observer-based dynamical protocol and robust  consensus  are  dealt  with  in  [14].  A  noticeable  approach  about  oblique decomposition of the state space is devised in [15-16]. The consensus condition of a class of systems with switching graph topology is shown in [17]. A method based on relative  Lyapunov  function  is  proposed  in  [6],  which  could  potentially  handle  both consensus and non-consensus stability problems for systems composed of nonlinear or even heterogeneous agents.

It is a natural tendency to diagonalize the Laplacian matrix of the graph topology while addressing the consensus problems of multi-agent systems with linear high-order inter-agent protocols. However, due to the requirement of diagonalizability, many discussions are limited only to the case of bidirectional networks [13, 17].

We shall endeavor to reveal a fact that it is essentially not a problem whether or not a weighted directed network is decouplable. With this fact known, in many cases one  can  easily  analyze  the  dynamics  of  multi-agent  systems  via  the  technique  of decoupling the directed  network  through  similarity  transformation,  with  no  need  to consider the actual diagonalizability of associated matrix. The computational complexity  might  be  reduced  significantly,  since  a  high-dimensional  large-scale system  could  thus  be  converted  into  a  series  of  independent  low-dimensional subsystems. So far as we know, this idea is especially advantageous in dealing with the consensus problems of systems with uncertain or time-varying network topologies.

This paper includes two major parts. The first part is purely mathematical, and it theoretically analyzes the concept of almost decouplability. As an example to illustrate

the  application  of  the  main  theory,  the  consensus  problem  of  linear  high-order multi-agent  systems  with  time-varying  graph  topologies  is  concerned  in  the  second part of the paper.

It is worthy to mention that some of the propositions may seem lesser novel alone. Some analogous arguments could also exist in the literature, e.g. [18]. However, by systematically  clarifying  and  integrating  the relevant  considerations,  both  from Mathematics and systems theory viewpoints, a novel and effective methodology can be yielded to deal with many problems in dynamical networked systems, especially stability problems. This is the essential contribution of the current paper.

The  rest  of  this  paper  is  organized  as  follows.  Section  2  depicts  the  almost decouplability concept, providing the main theoretical result. Section 3 deals with the stability  problem  of  general  dynamical  systems  as  preparation  for  the  next  section. Section  4  discusses  the  uniform  consensus  for  multi-agent  systems,  based  on  the results shown in previous sections. Finally, the concluding remarks form Section 5.

## 2. Almost decouplatility of directed weighted networks

As the most important part of the paper, the current section expounds the almost decouplability conception. We can see that the meaning of this conception is twofold, which  will  be  reflected  by  Proposition  1  &amp;  Theorem  1,  respectively:  1)  Without considering the limitation of structure, the Lebesgue  measure  for  the set of undiagonalizable square matrices is zero; 2) For any given directed weighted graph, there exists an arbitrarily close graph with diagonalizable Laplacian matrix, which has a prescribed structure limitation.

Proposition  1: Any  asymmetric  real-valued  square  matrix N N L R   is  almost diagonalizable, i.e. the Lebesgue measure for the set of undiagonalizable matrices in N N R  is zero.

The subsequent theoretical grounds are essential for proving Proposition 1, which are quoted from linear algebra.

Definition 1 (Resultant) [19]: Suppose that 1 0 1 ( ) m m m f x a x a x a      ( 0 0 ) a  and 1 0 1 ( ) n n n g x b x b x b      ( 0 0 ), b  with their roots being 1 2 , , , m    and 1 2 , , , n    respectively. The resultant of the two polynomials is defined as follows:

$$R ( f, g ) = a _ { 0 } ^ { n } b _ { 0 } ^ { m } \prod _ { i = 1 } ^ { m } \prod _ { j = 1 } ^ { n } ( \alpha _ { i } - \beta _ { j } )$$

With the following formula [19], one can directly compute the resultant of two polynomials by their coefficients:

$$R ( f, g ) = \Delta ( m, n ) = \begin{vmatrix} a _ { 0 } & a _ { 1 } & \cdots & a _ { m } & & & \\ & a _ { 0 } & a _ { 1 } & \cdots & a _ { m } & & \\ & & & \ddots & & \\ & & & & a _ { 0 } & a _ { 1 } & \cdots & a _ { m } \\ b _ { 0 } & b _ { 1 } & \cdots & b _ { n } & & & \\ & b _ { 0 } & b _ { 1 } & \cdots & b _ { n } & & \\ & & & & \ddots & & \\ & & & & b _ { 0 } & b _ { 1 } & \cdots & b _ { n } \end{vmatrix} \\. \ \cdots \cdots \. \ \cdots \. \ \cdots \. \ \cdots \. \ \cdots \. \ \cdots \. \ \cdots \. \ \cdots \. \ \end{vmatrix}$$

Lemma  1 [19]: An  irreducible polynomial ( )   is p x a multiple factor of polynomial ( )   if  and  only  if f x ( ) p x is  a  common  factor  of ( )   and f x '( ) , f x where '( )   is the derivative of f x ( ) . f x

Lemma 2 [19]: There exists a common factor of polynomials ( )   and f x ( )   if g x and only if the resultant ( , ) 0. R f g 

Proof of Proposition 1: Consider any arbitrary matrix N N ij L l R        .  Suppose that its characteristic polynomial is

$$f ( x ) = | x I - L | = x ^ { N } + a _ { 1 } x ^ { N - 1 } + \cdots + a _ { _ { N } }$$

with the coefficient vector   1 2 T N N a a a R  . The derivative of ( ) f x is

$$f \, ^ { \prime } ( x ) = N x ^ { N - 1 } + a _ { 1 } ( N - 1 ) x ^ { N - 2 } + \cdots + a _ { N - 1 }$$

According to Lemmas 1 &amp; 2, there exists a multiple factor of ( )   if  and  only  if f x ( , ') 0, i.e. the coefficients of R f f  ( )   must satisfy the following equation: f x

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0355v1-figure-8f819cab-53c4-4fb0-abb7-b7d180b5a761.jpg)

Evidently,  the  set  of  variables 1 , , N a a satisfying  the  above  algebraic  equation

forms a manifold of dimension 1. N 

Equation (2) determines the relationship between the coefficient vector   1 2 T N a a a and the values of entries in L , which are N scalar functions:

$$\begin{cases} a _ { 1 } = \varphi _ { 1 } ( l _ { 1 1 }, l _ { 1 2 }, \cdots, l _ { N N } ) \\ a _ { 2 } = \varphi _ { 2 } ( l _ { 1 1 }, l _ { 1 2 }, \cdots, l _ { N N } ) \\ \vdots \\ a _ { N } = \varphi _ { N } ( l _ { 1 1 }, l _ { 1 2 }, \cdots, l _ { N N } ) \end{cases}$$

Substituting 1 , , N a a in  (2)  by  (3)  will  result  in  an  equation  taking  the  following form:

$$\Gamma ( l _ { 1 1 }, l _ { 1 2 }, \cdots, l _ { _ { N N } } ) = 0$$

with ( )   being a scalar function. It is evident that the set of matrices that satisfy (4)   forms a manifold of lesser dimension in N N R  and therefore its Lebesgue measure is zero.  All  the  matrices  in N N R  except  this  set  have  distinct  eigenvalues  and  are surely diagonalizable. □

Example 1: Consider any matrix in 2 2 R  , which is

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix}$$

with , , a b c and d as some arbitrary real numbers. Its characteristic polynomial is

$$\begin{vmatrix} x - a & - b \\ - c & x - d \end{vmatrix} = x ^ { 2 } - ( a + d ) x + a d - b c$$

The polynomial has multiple roots if and only if

$$( a + d ) ^ { 2 } = 4 ( a d - b c )$$

which determines a manifold of measure 0 in 2 2 R  .□

Remark 1: The zero Lebesgue measure for the set of undiagonalizable matrices also  implies  that  the  diagonalizable  set  is  dense.  However,  the  former  condition  is stronger than the mere density. As a well-known instance, the set of rational numbers is dense in R whereas its measure is still zero.

Remark 2: The analysis in practical scenarios can be much convenient, with the knowledge that the Lebesgue measure of the set of undiagonalizable matrices is zero. Because  deviations  always  exist  between  models  and  the  real  systems,  usually  a matrix  encountered  in  an  engineering  scenario,  such  as  an  adjacency  matrix  or Laplacian matrix of a specific network topology, can be regarded as being

diagonalizable  according  to  Proposition  1.  In  most  cases,  it  is  not  necessary  to consider the undiagonalizable exceptions.

If the graph topology of a network is denoted by its adjacency matrix for the sake of analysis, then there is a one-to-one correspondence between any graph and a matrix in real number domain; thus, Proposition 1 is sufficient to interpret the idea that the graph  topology  is  almost  decouplability.  However,  while  concerning  the  dynamical multi-agent  systems  with  linear  inter-agent  protocols,  Laplacian  matrices  are  more frequently  adopted to  represent  the  graph  topologies.  Laplacian  matrix  is  a  specific type of matrix with structure limitation, i.e. the sum of elements in any row is zero. It cannot  guarantee  that  Proposition  1  is  still  valid  if  the  matrix  has  certain  structure limitation. The next theorem deals with such a situation. The lemmas that follow are theoretical preparations for the theorem.

Definition  2 (Laplacian  Matrix) [1]:  The  Laplacian  matrix  of  a  given  directed weighted network topology is

L

D

W





where W is the adjacency matrix and D is the in-degree matrix with ( ) . Note that D diag W     1 1 1 T   denotes a vector with all entries being 1.

Lemma 3:  is  an eigenvector of any Laplacian matrix L with the associated eigenvalue being 0.

$$\text{Proo} \colon \text{Because } \ D \phi = d i a g ( W \phi ) \phi = W \phi, \text{ } L \phi = 0 \,. \Box$$

Lemma 3 can be regarded as a structural limitation or a criterion to check whether a matrix is a Laplacian matrix of certain network topology.

Lemma  4 [20]: (Schur's Unitary Triangularization Theorem) With given n n A R   , there exists a unitary matrix U such that * UAU is upper triangular.

Lemma  5 [20]: If  two  matrices [ ] ij A a  and [ ] ij B b  in n n R  are  unitarily equivalent, i.e. there is a unitary matrix U such that * UAU B  , then

$$\sum _ { i, \, j = 1 } ^ { n } a _ { i j } ^ { 2 } = \sum _ { i, \, j = 1 } ^ { n } b _ { i j } ^ { 2 }$$

Theorem 1: For any directed graph G of N th order and any value 0, there   exists a graph ( ) G  that is decouplable, i.e. its Laplacian matrix ( ( )) [ ( )] ij L G l    is diagonalizable, meanwhile

$$\sum _ { i, j = 1 } ^ { N } \left ( l _ { i j } - l _ { i j } \left ( \varepsilon \right ) \right ) ^ { 2 } < \varepsilon$$

Proof: Suppose  that  the  eigenvalues  of L are 2 0, ,..., N   .  Let N N U R   be unitary  such  that * U LU is upper  triangular.  Select  an  upper  triangular  matrix N N E R   in which the elements satisfy

$$| e _ { i j } | < \sqrt { 2 } \varepsilon / N ( N + 1 ) \ ( i = 1, 2, \dots, N \ j = i, \dots, N )$$

such that 2 22 ,..., N NN e e     are different from each other. Besides, let the elements in E also jointly satisfy (6):

$$U E U ^ { ^ { * } } \phi = 0$$

Equation (6) is a system of equations with N equations and (1 ) / 2 N N  independent variables, so there must exist feasible solutions since ( 1) / 2 . N N N   With such an E satisfying (6), let * ( ( )) L G L UEU    , then * ( ( ))-= L G L UEU  and according to Lemma 5 and (5),

$$\sum _ { i, j = 1 } ^ { N } ( l _ { i j } - l _ { i j } ( \varepsilon ) ) ^ { 2 } = \sum _ { i = 1 } ^ { N } \sum _ { j = i } ^ { N } e _ { i j } ^ { 2 } < \varepsilon$$

Evidently, ( ) L  is  diagonalizable  because  its  spectrum  is  {0, 2 22 ,..., }, N NN e e     without identical eigenvalues. □

Remark 3: Proposition 1 &amp; Theorem 1 play different roles, and are compensating each  other.  They  jointly  constitute  the  interpretation  for  the  almost  decouplability conception  proposed  in  this  paper.  Proposition  1  implicates  a  fact  that  the  set  of diagonalizable  matrices  is  dense,  including  most  of  the  matrices;  while  Theorem  1 concentrates  on  the  diagonalizability  of  Laplacian  matrices,  which  is  the  case  with structure limitation.

The idea of almost decouplability elaborated in this section may seem obvious, but it can truly help to reduce the complexity of analysis. The next two sections will illustrate  the  effectiveness  of  this  idea  by  an  example  on  the  consensus  problem  of dynamical multi-agent systems with time-varying network topologies.

## 3. Uniform  asymptotic  stability of slightly perturbed time-varying dynamical systems

This  section  discusses  some  general  problems  in  control  theory,  leading  to  two

main  propositions  which  collectively  imply  a  fact  that  the  uniform  asymptotic stability  is  robust  to  sufficiently  minor  uncertainties  of  system  dynamics  across  the entire  time  horizon.  As  a  result,  it  is  feasible  to  study  the  stability  of  a  dynamical system  via  replacing  it  by  another  system  with  just  slight  variation,  but  with remarkably  simplified  analysis.  The  current  section  is  essentially  independent  of Section 2, and its main purpose is to provide necessary theoretical basis to support the analysis on the consensus problem in the next section.

Definition 3 (Positive Definite Function): A real-valued, continuously differentiable function ( )   is  said to be f x positive definite in  a  neighborhood of the origin D if (0) 0  and f  ( ) 0  for  any  nonzero f x  x D  . A  function ( , ) f t x ([0, ) D R    )  is  said  to  be positive  definite if ( ,0) 0  and f t  ( , ) ( )   in f t x v x  [0, ) D   for some positive definite function ( ) . v x

Lemma 6 [21]: Let 0  be a uniformly asymptotically stable equilibrium point x  for the nonlinear system

$$\dot { x } = f ( t, x )$$

where :[0, ) n f D R    (   n D x R x r    )  is  continuously differentiable both in t and x . Then,  there  exist a positive real value 0 r and  a continuously differentiable function 0 :[0, ) n V D R    (   0 0 n D x R x r    ) that satisfies the following series of inequalities

$$\alpha _ { _ { 1 } } ( \| x \| ) \leq V ( t, x ) \leq \alpha _ { _ { 2 } } ( \| x \| )$$

$$\frac { \partial V } { \partial t } + \frac { \partial V } { \partial x } \, f ( t, x ) \leq - \alpha _ { 3 } ( \| x \| )$$

$$\left \| \frac { \partial V } { \partial x } \right \| \leq \alpha _ { _ { 4 } } ( \| x \| )$$

where 1  , 2  , 3  , and 4  are class K functions.

Proposition 2: Suppose that 0   is x  a uniformly asymptotically stable equilibrium  point  of  a  nonlinear  time-varying  system ( , ) ,  where x f t x  ( , )   is f t x continuously differentiable both in t and x , then there must exist a positive definite function ( , )   such  that t x  0  is  also  uniformly  asymptotically stable for all the x  systems:

$$\dot { x } = f ( t, x ) + \delta ( t, x )$$

where ( , )   is any vector function in t x  R

$$\| \delta ( t, x ) \| \leq \gamma ( t, x )$$

n that satisfies )

Proof: It is simple to verify that the origin 0  is also an equilibrium point for x  any  system  (10).  According  to  Lemma  6,  there  exists  a  continuously  differentiable function ( , )   satisfying V t x inequalities (7)~(9). Let ( , )   be V t x the Lyapunov function candidate for system (10). Then its derivative along the trajectory of (10) is

$$& \dot { V } = \frac { \partial V } { \partial t } + \frac { \partial V } { \partial x } \, \dot { x } \\ & = \frac { \partial V } { \partial t } + \frac { \partial V } { \partial x } \, f ( t, x ) + \frac { \partial V } { \partial x } \, \delta ( t, x )$$

In (11) above,

$$\left | \frac { \partial V } { \partial x } \delta ( t, x ) \right | \leq \left \| \frac { \partial V } { \partial x } \right \| \| \delta ( t, x ) \|$$

Let ( , ) t x  be a positive definite function satisfying

$$\gamma ( t, x ) < \alpha _ { 3 } ( \| x \| ) / \left \| \frac { \partial V } { \partial x } \right \| \ ( x \neq 0 )$$

Then, because ( , ) ( , ) , t x t x   

$$- \alpha _ { 3 } ( \| x \| ) < \frac { \partial V } { \partial x } \, \delta ( t, x ) < \alpha _ { 3 } ( \| x \| )$$

Considering both (13) and (8), it is evident to know that (11) is negative for 0. x   Thus, 0  is uniformly asymptotically stable for any system (10). □ x 

Proposition  3: Suppose  that 0   is x  an  equilibrium  point  of  a  nonlinear time-varying  system ( , ) ,  then  there  must  exist  a  positive  definite  function x f t x  ( , )   such that t x  0  is uniformly asymptotically stable for system x  ( , ) x f t x  if and only if 0  is also uniformly asymptotically stable for system x 

$$\dot { x } = f ( t, x ) + \delta ( t, x )$$

where ( , )   is any vector function with proper dimension satisfying t x 

$$\| \delta ( t, x ) \| \leq \gamma ( t, x )$$

Proof: According  to  Proposition  2,  for  any  nonlinear  system  with  origin  its uniformly asymptotically stable equilibrium point, there is a positive definite function indicating the bound of permitted variation preserving stability. Thus, there is a map between a system and a positive definite function:

$$\dot { x } = f ( t, x ) \rightarrow \gamma ( t, x )$$

Assume  that 0 x  is uniformly asymptotically stable for a specific system 0 ( , ) , then there exists a positive definite function x f t x  0 ( , ) t x  such that 0  is x  uniformly asymptotically stable for the set of systems

$$\left \{ \dot { x } = f _ { 0 } ( t, x ) + \delta ( t, x ) \| \| \delta ( t, x ) \| < \gamma _ { 0 } ( t, x ) \right \}$$

Each element in the above set can also induce a positive definite function, e.g.

$$\dot { x } = f _ { 0 } ( t, x ) + \delta _ { 0 } ( t, x ) \rightarrow \hat { \gamma } _ { 0 } ( t, x )$$

with 0 ( , ) t x  being  a  specific  vector  function  satisfying 0 0 ( , ) ( , ) . t x t x    As  a result, 0  is uniformly asymptotically stable for the set of systems x 

$$\left \{ \dot { x } = f _ { 0 } ( t, x ) + \delta _ { 0 } ( t, x ) + \Delta ( t, x ) \left \| \Delta ( t, x ) \right \| < \hat { \gamma } _ { 0 } ( t, x ) \right \}$$

if 0  is uniformly asymptotically stable for the system x  0 0 ( , ) ( , ) . It is x f t x t x    simple to construct a positive definite function ( , )   satisfying t x 

$$\gamma ( t, x ) \leq \hat { \gamma } _ { 0 } ( t, x )$$

for all such 0 ˆ ( , )   induced by map (16) from elements in the set (15). Evidently, t x  0 x  is  uniformly  asymptotically  stable  for  the  specific  system 0 ( , ) x f t x  if  and only if 0 x  is uniformly asymptotically stable for all the elements in

$$\left \{ \dot { x } & = f _ { 0 } ( t, x ) + \delta ( t, x ) \left \| \delta ( t, x ) \right \| < \gamma ( t, x ) \right \} & & \Box$$

Combining the theoretical results in Sections 2 &amp; 3, the methodology for stability analysis of networked systems based on almost decouplability is clearly established here.  The process  can be summarized as follows. First, let an approximate network topology ( ) G  with diagonalizable Laplacian matrix or adjacency matrix replace the original G , no  matter  whether  it  is  actually  diagonalizable.  Then,  decouple  the network  via  a  nonsingular  transformation  and  a  system  composed  of  independent low-dimensional  subsystems  is  thus  derived,  which  has  the  same  stability  with  the original system.

## 4. Uniform consensus of multi-agent systems with time-varying network topologies

The  major  purpose  of  this  section  is  to  provide  an  example  to  show  the effectiveness of the main theory introduced previously. As the example, the consensus problem  will  be  analyzed  for  dynamical  multi-agent  systems  with  time-varying network  topologies,  by  approaches  based  on  the  idea  of  almost  decouplability.  A

necessary and sufficient condition will be derived for the uniform consensus.

The dynamic multi-agent system model concerned here comprises of N agents, and  each  agent  has  dynamics  of d th  order.  The  state  of  agent i is  denoted  by 1 2 [ , ,..., ] T d i i i id x x x x R   . The communication architecture among agents is represented by a graph topology G of order N , with each agent corresponding to a vertex.  The  arc  weight  of G between  agents i and j is  denoted  by 0 , ij w  which  can  be  regarded  as  the  strength  of  information  link.  The  graph G in  this section is time-varying, which is sufficiently smooth in t and can be denoted by its adjacency matrix ( ) : W t

$$G \colon W = \begin{bmatrix} w _ { 1 1 } & w _ { 1 2 } & \dots & w _ { 1 N } \\ w _ { 2 1 } & w _ { 2 2 } & \dots & w _ { 2 N } \\ \vdots & \vdots & & \vdots \\ w _ { N 1 } & w _ { N 2 } & \dots & w _ { N N } \end{bmatrix} \\ \dots \dots \end{bmatrix}$$

Suppose the dynamics of each agent can be described as:

$$\dot { x } _ { i } = A x _ { i } + F \sum _ { j = 1 } ^ { N } w _ { i j } ( t ) ( x _ { j } - x _ { i } ) \ \ ( i \in \{ 1, 2, \dots, N \} )$$

where d d A R   and d d F R   . If a stack of state vectors is defined as 1 2 T T T T N x x x x      , then the system dynamics can be described by

$$\dot { x } = ( I _ { _ { N } } \otimes A - L ( t ) \otimes F ) x$$

with ( )   being the time-varying Laplacian matrix of graph L t G .

As the theme of the current section, consensus is essentially a stability problem. The  following  definitions  clearly  indicate  the  relationship  between  consensus  and stability.  With  these  definitions,  the  two  equivalent  terms consensus and asymptotic swarm stability will be used indiscriminately later.

Definition  4 [4]: (Swarm  Stability) For  a  time-varying  dynamical  multi-agent system with 1 ,..., d N x x R  as the states of N agents, if for 0 ,    ( ) 0 ,     s.t. ( ) ( ) i j x t x t    ( 0 ) t  as (0) (0) ( )   ( i j x x     , {1, 2,..., } ), i j N   then  the system  is  uniformly swarm  stable . If lim ( )       , the  system  is  globally uniformly swarm stable.

Definition  5 [4]: (Asymptotic  Swarm  Stability) If  a  time-varying  dynamical multi-agent system is globally uniformly swarm stable and for , 0 , c    ( , ) 0 T T c     s.t.

$$\left \| x _ { i } ( t ) - x _ { j } ( t ) \right \| < \varepsilon \\ \sim 1 1 \sim$$

as ( , ) t T c   and (0) (0) i j x x c   ( , {1, 2,..., } ), i j N   then the system is globally uniformly asymptotically swarm stable .

Lemma  7 [9]: The  Laplacian  matrix L of  a  directed  graph G has  exactly  a single  zero  eigenvalue 1 0  iff   G has  a  spanning  tree,  with  the  corresponding eigenvector   1 1 1 T   .

Lemma  8 [4]:  For  the  time-varying  dynamic  multi-agent  system  (17),  if  it  is uniformly asymptotic swarm stable, then as t  , the trajectory of each agent tends to be regulated by the equation A    .

Lemma 9 [4]:  For  system  (17),  if A is  Hurwitz,  then  the  system  is  uniformly asymptotically  swarm  stable  iff  it  is  uniformly  asymptotically  Lyapunov  stable. Besides, the consensus state must be zero.

Theorem 2: For the multi-agent system (17), with 1 2 0, ( ), , ( ) N t t C      the time-varying  eigenvalues  of ( ( )) , L G t if A is unstable,  the overall system  is uniformly asymptotically swarm stable iff both 1) and 2) below are true:

- 1) 0 T   s.t. there do not exist any two values 1 t and 2 t ( 2 1 t t T   ) while ( ) G t includes no spanning tree during 1 2 [ , ] ; t t t 
- 2) All the following d -dimensional dynamic systems

$$\dot { \xi } = ( A - \lambda _ { \tilde { t } } ( t ) F ) \xi \ ( \lambda _ { \tilde { t } } \neq 0 )$$

are uniformly asymptotically stable.

If A is  Hurwitz,  then  the  multi-agent  system  is  uniformly  asymptotically  swarm stable iff 2) is true.

## Proof: Part I ( A is unstable)

Assume  that  1)  does  not  hold  but  the  multi-agent  system  is  still  uniformly asymptotically  swarm  stable.  Suppose  that G has  no  spanning  tree  for 1 2 [ , ] , t t t  where 1 t and 2 t can  be  arbitrarily  large,  then G must  contain 2   distinct k  subgraphs 1 ˆ G , 2 ˆ G ,…, ˆ k G , each receiving no information during 1 2 [ , ] t t t  . According to Lemma 8, as t is sufficiently large, the consentaneous trajectory 1 ( ) t  of  the  agents  associated  with 1 ˆ G approaches  the  solution  of  equation 1 1 A    , whereas  the  consentaneous  trajectory 2 ( )   associated  with t  2 ˆ G approaches  the solution  of 2 2 A    . The  two  trajectories  are  independent  because  there  is  no information  exchanged.  Thus, 1 2 1 2 ( ) . A        Since A is  unstable, 1 2    tends to increase during 1 2 [ , ] . t t t  This contradicts the assumption that the

multi-agent  system  is  asymptotically  swarm  stable.  Therefore,  1)  is  a  necessary condition. Note that the condition ( ) G t possessing no spanning tree is permitted at any particular instant t T  due to the continuity of the system.

Suppose that 1 2 0, ( )..., ( ) N t t C      are the eigenvalues of ( ) . According to L t Proposition  1  and  Theorem  1,  let  an  approximate ( , ) G t  ( 0)  replace   ( ) , G t with ( , ) L t  replacing ( ) L t , which is uniformly diagonalizable. Hence, an alternative system of (18) is derived as:

$$\dot { x } = ( I _ { _ { N } } \otimes A - L ( \varepsilon, t ) \otimes F ) x$$

Considering  the  continuity  of  the  eigenvalues  of  matrices,  one  can  infer  that  the eigenvalues of ( , )   also approach L t  1 2 0, ( )..., ( )   as N t t     0.  

Now let us consider the swarm stability of (19). Suppose that 1 ( ) ( , ) ( ) ( )   and let T t L t T t t     ( ( ) ) d x T t I x   , then (19) is transformed into

$$\dot { \tilde { x } } = ( I _ { _ { N } } \otimes A - \Lambda ( t ) \otimes F ) \tilde { x }$$

According to Propositions 2 &amp; 3, the uniform asymptotic stability of system (20) is  equivalent  to  that  of  system  (18),  with 2 3 ( ) (0, ( ), ( ), , ( )) .  The N t diag t t t      structure of ( ) N I A t F    is of the form

$$\dots \dots \dots \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N }\dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ { N } \dots _ N }$$

Let the auxiliary variables

$$\eta _ { i } = \sum _ { j = 1 } ^ { N } w _ { i j } ( \varepsilon, t ) ( x _ { j } - x _ { i } ) \ \ ( i = 1, 2, \dots, N )$$

and their stack vector be 1 2 T T T T N          . It follows that

$$\eta = ( L ( \varepsilon, t ) \otimes I _ { _ { d } } ) x$$

With condition 1), according to Lemma 7, any vector in the null space of ( , ) d L t I   is of  the  form   when t T  , where   1 1 1 T N R    and d R   . Therefore, 1 2 N x x x    in  (19)  iff 0   when t T  . Because  of  (21)  and 1 ( ) d x T I x    ,

$$( T \otimes I _ { _ { d } } ) \eta = ( T L ( \varepsilon ) \otimes I _ { _ { d } } ) x = ( T L ( \varepsilon ) \otimes I _ { _ { d } } ) ( T ^ { - 1 } \otimes I _ { _ { d } } ) \tilde { x } = ( \Lambda \otimes I _ { _ { d } } ) \tilde { x }$$

According to Lemma 7, all the values 2 , , N   are nonzero as t T  , thus from the linear equation (23), one can infer that 0   iff   2 0   with N x x    considering the structure of ( ) . By (21), it is clearly known that t  2 3 , , , 0 N x x x  iff  condition  2)  holds.  According  to  Propositions  2  &amp;  3,  the  uniform  asymptotic

stability of (19) is identical with that of (18); therefore condition 2) is also appropriate for the system (18).

## Part II ( A is Hurwitz)

As A is Hurwitz, according to Lemma 9, the system is uniformly asymptotically swarm stable iff it is uniformly asymptotically Lyapunov stable. The stability of system (17) is equivalent to that of (21). It is clear that (21) is uniformly asymptotically stable iff condition 2) is true.□

Remark 4: If without the almost decouplability conception introduced in previous sections, it would be difficult or even impossible to handle the proof and obtain the result of Theorem 2, since the network topology here is not only asymmetric but also time-varying.

Remark 5: Admittedly,  Theorem 2 is  relatively  theoretic,  since  eigenvalues  are usually  not  easy  to  obtain.  Its  main  role  is  to  demonstrate  the  effectiveness  of  the approach based on the idea of almost decouplability. Nonetheless, this theorem itself still has theoretical significance. First, it provides a necessary and sufficient condition without additional technical hypothesis. Second, the consensus of a large-scale system is transformed into the stability of a series of independent low-dimensional systems, and  the  computational  complexity  is  thus  reduced  significantly.  Besides,  this  result separates the consideration of network topology from the dynamics of agents.

## 5. Conclusions

This paper introduces a conception that any weighted directed network topology is almost decouplable, i.e.  there always exists an arbitrarily close digraph which can be transformed into a similar form, consisting of independent vertices. This conception could  help  to  reduce  the  complexity  of  analysis  because  a  large  scale  networked system  can  thereby  be  decoupled  into  numerous  independent  low-dimensional systems through similarity transformations. As an example to illustrate the validity of the methodology proposed, the uniform consensus problem of dynamical multi-agent systems with time-varying network topologies is discussed, leading to establishing a necessary  and  sufficient  condition.  Evidently,  the  almost  decouplability  conception should also be applicable in other problems, e.g. the robust consensus problem, which will be investigated in our future work.

## Acknowledgments

This  work  is  supported  by  Program  for  Young  Talents  of  State  Ethnic  Affairs Commission  (SEAC)  China  (Grant  [2013]  231),  and  by  National  Natural  Science Foundation (NNSF) of China (Grants 61174067, 61263002, &amp; 61374054).

## References

- [1] C. Godsil, G. Royle, Algebraic Graph Theory , Springer-Verlag: Berlin, 2001.
- [2] G.  Chen,  X.  Wang,  X.  Li, Introduction  to  Complex  Networks:  Models,  Structure  and Dynamics , Higher Education Press: Beijing, 2012.
- [3] N.  Cai, Swarm  Stability  and  Controllability  of  High-Order  Swarm  Systems , Doctoral Dissertation, Tsinghua University, 2010.    (In Chinese)
- [4] N. Cai, J. Xi, Y. Zhong, 'Swarm stability of high order linear time-invariant swarm systems', IET Control Theory Appl. , vol. 5, pp. 402-408, 2011.
- [5] N.  Cai,  J.  Xi,  Y .  Zhong,  'Asymptotic  swarm  stability  of  high  order  dynamical  multi-agent systems:  Condition  and  application', Control  and  Intelligent  Systems ,  vol.  40,  pp.  33-39, 2012.
- [6] N.  Cai,  J.  Cao,  H.  Ma,  C.  Wang,  'Swarm  stability  analysis  of  nonlinear  dynamical multi-agent  systems  via  relative  Lyapunov  function', Arab.  J.  Sci.  Eng. , vol.  39,  pp. 2427-2434, 2014.
- [7] N. Cai, M. Liu, X. Wei, H. Ma, 'On uniform consensus of linear multi-agent systems with time-varying graph topologies', Proc. Chinese Control Conf. , pp. 6896-6899, 2013.
- [8] A. Jadbabaie, J. Lin, A. Morse, 'Coordination of groups of mobile autonomous agents using nearest neighbor rules', IEEE Trans. Autom. Control , vol. 48, pp. 988-1001, 2003.
- [9] R.  Olfati-Saber,  R.  Murray,  'Consensus  problems  in  networks  of  agents  with  switching topology and time-delays', IEEE Trans. Autom. Control , vol. 49, pp. 1520-1533, 2004.
- [10] W. Ren, R. Beard, 'Consensus seeking in multiagent systems under dynamically changing interaction topologies', IEEE Trans. Autom. Control , vol. 50, pp. 655-661, 2005.
- [11] H. Hu, W. Yu, Q. Xuan, L. Yu, G. Xie, 'Consensus for second-order agent dynamics with velocity  estimators  via  pinning  control', IET Control Theory Appl. ,  vol.  7,  pp.  1196-1205, 2013.
- [12] H. Hu, A. Liu, Q. Xuan, L. Yu, G. Xie, 'Second-order consensus of multi-agent systems in the  cooperation-competition  network  with  switching  topologies:  A  time-delayed  impulsive control approach', Syst. Control Lett. , vol. 62, pp. 1125-1135, 2013.

- [13] F.  Xiao,  L.  Wang,  'Consensus  problems  for  high-dimensional  multi-agent  systems', IET Control Theory Appl. , vol. 1, pp. 830-837, 2007.
- [14] J.  Wang,  D.  Cheng,  X.  Hu,  'Consensus  of  multi-agent  linear  dynamic  systems', Asian  J. Control , vol. 10, pp. 144-155, 2008.
- [15] Z. Li, Z. Duan, G. Chen, L. Huang, 'Consensus of multiagent systems and synchronization of complex networks: A unified viewpoint', IEEE Trans Circuit. Syst. I: Regular Papers ,  vol. 57, pp. 213-224, 2010.
- [16] J. Xi, Z. Shi, Y. Zhong, 'Consensus analysis and design for high-order linear swarm systems with time-varying delays', Physica A , vol. 390, pp. 4114-4123, 2011.
- [17] J. Xi, Z. Shi, Y. Zhong, 'Output consensus analysis and design for high-order linear swarm systems: Partial stability method', Automatica , vol. 48, pp. 2335-2343, 2012.
- [18] W.  Ni,  D.  Cheng,  'Leader-following  consensus  of  multi-agent  systems  under  fixed  and switching topologies', Syst. Control Lett. , vol. 59, pp. 209-217, 2010.
- [19] D.J. Hartfiel,  'Dense sets of diagonalizable matrices', Proc. Am. Math. Soc. ,  vol.  123,  pp. 1669-1672, 1995.
- [20] B. Feng, Polynomials and Irrational Numbers , Harbin Institute of Technology Press: Harbin, 2008. (In Chinese)
- [21] R.A. Horn, C.R. Johnson, Matrix Analysis , Cambridge University Press: Cambridge, 1985.
- [21] H.K. Khalil, Nonlinear Systems (3rd Edition), Prentice Hall: Upper Saddle River, 2002.
Ning Cai M. Junaid Khan
Almost Decouplability of any Directed Weighted Network Topology
This paper introduces a conception that any weighted directed network
topology is almost decouplable, which can help to transform the topology into a
similar form being composed of uncoupled vertices, and thus reduce the
complexity of analysis for networked dynamical systems. As an example of its
application, the consensus problem of linear multi-agent systems with
time-varying network topologies is addressed. As a result, a necessary and
sufficient condition for uniform consensus is proposed.