Digraphs with Distinguishable Dynamics under the Multi-Agent
Agreement Protocol

arXiv:1611.09987v1 [] 30 Nov 2016

M. Amin Rahimian, Amir Ajorlou, and Amir G. Aghdam
ABSTRACT
In this work the ability to distinguish digraphs from the output response of
some observing agents in a multi-agent network under the agreement protocol
has been studied. Given a fixed observation point, it is desired to find sufficient
graphical conditions under which the failure of a set of edges in the network
information flow digraph is distinguishable from another set. When the latter
is empty, this corresponds to the detectability of the former link set given the
response of the observing agent. In developing the results, a powerful extension
of the all-minors matrix tree theorem in algebraic graph theory is proved
which relates the minors of the transformed Laplacian of a directed graph to
the number and length of the shortest paths between its vertices. The results
reveal an intricate relationship between the ability to distinguish the responses
of a healthy and a faulty multi-agent network and the inter-nodal paths in
their information flow digraphs. The results have direct implications for the
operation and design of multi-agent systems subject to multiple link losses.
Simulations and examples are presented to illustrate the analytic findings.
Key Words: Directed graphs; Graph theory; Distributed control; Networks;
Linear systems.

The authors are with the Department of Electrical and Computer Engineering, Concordia University, 1455 De Maisonneuve Blvd.
W., Montréal, Québec, H3G 1M8, Canada (email: aghdam@ece.concordia.ca). This work has been supported by the Natural
Sciences and Engineering Research Council of Canada (NSERC) under grant RGPIN-262127-12.

I. INTRODUCTION
Multi-agent network systems consist of a group of dynamic agents, which interact according to a given
information flow structure [10]. These systems have found promising applications in areas such as formation control
of satellite clusters and motion coordination of robots [6, 12]. Distributed and cooperative control for these networked
dynamic systems employs various concepts from different fields including parallel processing, distributed algorithms,
control, and estimation [2]. Popular research problems related to multi-agent network control include connectivity,
containment, consensus, rendezvous, formation, flocking, and controllability [13, 5, 19, 27, 9]. Such cooperative
dynamics over a network may be strongly affected by the network failures, and this has motivated the study of
network dynamics following the removal of some links or nodes [7, 16], as well as the related studies focusing on
switching network topologies [9]. By and large, the study of failures is an important topic in network science and it
has various practical implications [8].
Agreement protocols have been extensively investigated in the recent literature as a fundamental evolution
law for multi-agent networks in both continuous and discrete-time, using probabilistic and deterministic models
[14, 15, 20, 21, 22, 25]. Earlier results on adjacency-based agreement rules can be traced back to Vicsek’s model [24].
In [26], the authors calculate the single-input single-output transfer functions between pairs of nodes acting as the
control input and measurement nodes for cyclic consensus systems. They also point out the interesting implications
of the length of the shortest path between the input and measurement nodes on the stability margins and the relative
degree of the calculated transfer functions. The issues of identification and infiltration in consensus-type networks
is investigated in [4], where the authors consider additional observation and excitation nodes and make use of the
available system identification techniques to derive bounds on the eigenvalues of the network graph.
This paper focuses on the cooperative control of a multi-agent system under the linear agreement protocol and
subject to multiple communication link failures. The mathematical characterization of simultaneous link failures in
the paper leads to useful design guidelines for realization of reliable and fault-tolerant multi-agent networks. Detection
and isolation of faults are crucial to the cooperative and reliable control of multi-agent networks, and the chief aim
of this paper is to address these two important concepts. The results are therefore of both theoretical and practical
interest.
The remainder of this paper is organized as follows. Section II gives some preliminaries on sets and graph theory,
and introduces the notation that is used throughout the paper. The background provided in this section is then used in
Section III, where topological conditions for producing distinguishable dynamics in the observed response of an agent
are investigated. Next, in Section IV, the detectability of link failures is considered as a special case and sufficient
conditions are derived accordingly. Finally, concluding remarks are provided in Section V.

II. PRELIMINARIES AND NOTATION
Throughout the paper, ∅ is the empty set, N denotes the set of all natural numbers, R denotes the set of all real
numbers, and C denotes the set of all complex numbers. Also, the set of integers {1, 2, . . . , k} is denoted by Nk , and
any other set is represented by a curved capital letter. The cardinality of a set X , which is the number of its elements, is
denoted by |X |. The difference of two sets X and Y is denoted by X KY and is defined as {x; x ∈ X ∧ x ∈
/ Y}, where
∧ is the logical conjunction. Matrices are represented by capital letters, vectors are expressed by boldface lower-case
letters, and the superscript T denotes the matrix transpose. Moreover, I , 1, and 0 denote the identity matrix and
column vectors with all one and all zero entries, respectively; and their dimensions are clear from the context. The
determinant of a matrix M is denoted by det(M ), while [M ]ij indicates the element of M which is located at its i−th
row and j−th column.
2.1. Directed Graphs and the Associated Algebraic Entities
A directed graph or digraph is defined as an ordered pair of sets: G = (V, E), where V = {ν1 , . . . , νn } is a set of
n = |V| vertices and E ⊆ V × V is a set of directed edges. In the graphical representations, each edge  := (τ, ν) ∈ E
is denoted by a directed arc from vertex τ ∈ V to vertex ν ∈ V . Vertices ν and τ are referred to as the head and tail
of the edge , respectively. Given a set of vertices X ⊂ V , the set of all edges for which the tails belong to X but the
heads do not, is termed the out-cut of X , and is denoted by ∂G+ X ⊂ E . Similarly, the set of all edges for which the

Rahimian et al.: Distinguishable Agreement Dynamics

3

heads belong to X but the tails do not, is referred to as the in-cut of X , and is denoted by ∂G− X ⊂ E . The cardinality
−
of ∂G− X is called the in-degree of X , and is characterized as d−
G X = |∂G X |. Notice that the definition of E does not
allow for the existence of parallel arcs in the graphical representation of G . In other words, if two edges share the
same pair of head and tail, then they are identical.
Given an integer k ∈ Nn−2 , a permutation (α1 , α2 , . . . , αk ) of all members of the set Nk , and two vertices
τ, ν ∈ V , a sequence of distinct edges of the form P := (τ, να1 ), (να1 , να2 ), . . . , (ναk−1 , ναk ), (ναk , ν) is called a τ ν
path with length k + 1 if for any two edges (τ̄ , ν̄), (τ̂ , ν̂) of this sequence, ν̄ 6= ν̂ ←→ τ̄ 6= τ̂ . For a given vertex ν ∈ V ,
a νν path is called a directed circle. Moreover, the shortest length for all τ ν paths is referred to as the distance from
τ to ν , and is denoted by d(τ, ν). Likewise, the number of τ ν paths with length k , denoted by ck (τ, ν), is called the
k−th order topological connectivity of τ to ν . Notably, ck (τ, ν) = 0 for k < d(τ, ν), and by convention d(ν, ν) = 0,
c0 (ν, ν) = 1, and if ∀k ∈ N, ck (τ, ν) = 0, then d(τ, ν) = ∞.
For a given digraph G = (V, E) and two vertices νi , νj ∈ V, the edge-index of (νi , νj ) is defined as a |V| × |V|
matrix whose only non-zero element is 1, which is located at its j−th row and i−th column. This matrix is represented
by Γ((νi , νj )). Similarly, the vertex-index of any νi ∈ V is defined as a |V| × 1 column vector whose only non-zero
element P
is 1, which is located at its i-th row. This vector is denoted
by σ(νi ). The adjacency matrix of G is given by
P
A(G) = ∈E Γ(), its degree matrix is defined as ∆(G) = ν∈V d−
G {ν}Γ((ν, ν)), and the corresponding in-degree
graph Laplacian is given by L(G) = ∆(G) − A(G).
For a given digraph G = (V, E), a vertex τ ∈ V is called an out-branching root if there exists a τ ν path for every
ν ∈ VK {τ }. Furthermore, a digraph G̃ = (V, Ẽ), Ẽ ⊆ E with an out-branching root τ̃ ∈ V is a τ̃ -rooted spanning
out-branching of G if G̃ does not contain any directed circle and τ̄ 6= τ̂ −→ ν̄ 6= ν̂ for any {(τ̄ , ν̄), (τ̂ , ν̂)} ⊂ Ẽ .
The following Theorem is known as the all-minors matrix tree theorem in algebraic graph theory, and is a
generalization of the Matrix Tree Theorem for the case of directed graphs [23].
Theorem 1 For a given digraph G = (V, E) and a vertex νi ∈ V , the number of νi -rooted spanning out-branchings
of G is equal to any cofactor in the i−th row of L(G).
The next lemma is a significant extension to Theorem 1. This lemma relates the minors of the Laplacetransformed graph Laplacian to the length and number of inter-nodal paths in the digraph. Its proof uses the
permutation expansion of the determinants and follows the steps of the combinatorial proof of the all-minors matrix
tree theorem in [3], by relating the sum of the products of the entries of the graph Laplacian over some class of
permutations to the topological connectivity of the graph nodes.
Lemma 1 Given a digraph G = (V, E), let H = sI + L(G), s ∈ C. For any i, j ∈ N|V| and i 6= j , define Cij as the
matrix that results from removing the i−th row and j−th column of H . Then det(Cij ) is a polynomial of degree
|V| − d(νi , νj ) − 1 in s, whose leading coefficient has an absolute value equal to cd(νi ,νj ) (νi , νj ).
Proof: det(Cij ) can be written as a summation over the product of all possible permutations on the choice of
|V| − 1 matrix elements [11], as given below:
det(Cij ) =

X

ψ∈Ξ|V|−1

(−1)ι(ψ)

|V|−1

Y

[Cij ]kψ(k) ,

(1)

k=1

where Ξ|V|−1 is the finite group formed by the (|V| − 1)! permutations on the set N|V|−1 . Moreover, for a permutation
ψ(.) on the set N|V|−1 , ι(ψ) denotes its length and is defined as the number of pairs i, j ∈ N|V|−1 , i < j , such that
ψ(i) > ψ(j). Consider the case where d(νi , νj ) = 1, which implies that there exists an edge (νi , νj ) ∈ E . Hence,
[L(G)]ji = −1 and det(Cij ) is a polynomial of degree |V| − 2 in s. Moreover, the only term in det(Cij ) which
includes s|V|−2 in the right-hand side of (1) is the one corresponding to the elements [H]rr , r ∈ N|V| K{i, j} and
[H]ji = [L(G)]ji . Accordingly, (1) can be rewritten as:


Y
det(Cij ) = (−1)κ [L(G)]ji 
(s + din (ν)) + w1 (s) = −(−1)κ s|V|−2 + w2 (s),
(2)
ν∈VK{νi ,νj }

for some {w1 (s), w2 (s)} ⊂ W|V|−3 (s), where W|V|−3 (s) denotes the set of all polynomials in s with degrees less
than or equal to |V| − 3 and a permutation length κ ∈ N that depends on i, j and |V|. This corroborates (1) for
d(νi , νj ) = 1. Next, let [L(G)]mn = Lmn , {m, n} ⊂ N|V| and consider the expression for det(Cij ) in the general case
of d(νi , νj ) ∈ N|V|−1 K{1}. From d(νi , νj ) > 1, it follows that [L(G)]ji = 0 and (1) can be expanded as:


|V|
|V|
X
Y
Ljr Lri
det(Cij ) = (−1)κ2
(s + din (νk )) +
r=1,r6=i,j

(−1)κ3

|V|

X

|V|

X

r=1,r6=i,j t=1,t6=i,j,r

k=1,k6=i,j,r



Ljr Lrt Lti

|V|
Y

k=1,k6=i,j,r,t



(s + din (νk )) + . . . ,

(3)

for some κl , l ∈ N|V|−2 K{1}, which depend on the indices i and j and vary with the length of the permutations.
To express (2) in a more compact manner, let Θ = {θ1 , θ2 , . . . , θ|Θ| }, Π = {Θ; Θ ⊆ N|V| K{i, j} ∧ Θ 6= ∅} so that
|Π| = 2|V|−2 − 1, and let Ξ|Θ| be the finite group formed by the (|Θ|)! permutations on the set Θ. Furthermore, for
Θ ∈ Π and ψ ∈ Ξ|Θ| define:
Y
S(Θ) =
(s + din (νk )),
(4a)
k∈N|V| K({i,j}∪Θ)



P (Θ, ψ) = Ljθψ(1) 

|Θ|−1

Y
l=1



Lθψ(l) θψ(l+1)  Lθψ(|Θ|) i .

Using (4), for d(νi , νj ) > 1, (3) can be rewritten as:
det(Cij ) =

X



(−1)κ|Θ| 

Θ∈Π

X

ψ∈Ξ|Θ|

(4b)



P (Θ, ψ) S(Θ),

(5)

for some κ|Θ| ∈ N that depend on i and j . Breaking the first summation over |Θ| = k for k = 1, . . . , |V| − 2 and using
the notation Πk = {Θ; Θ ⊂ N|V| K{i, j} ∧ |Θ| = k} in (5) yields:


|V|−2
X
X
X

(−1)κk (i,j)
P (Θ, ψ) S(Θ).
(6)
det(Cij ) =
Θ∈Πk

k=1

ψ∈Ξk

Next, note that given k ∈ N|V| , two vertices {νi , νj } ⊂ V and |{νi , νj }| = 2, the k−th order topological connectivity
of νj to νi can be expressed in terms of [L(G)]mn = Lmn , {m, n} ⊂ N|V| as follows:


!
k−2
X
X
Y

ck (νj , νi ) = (−1)k ×
Liθψ(1)
Lθψ(l) θψ(l+1) Lθψ(k−1) j  ,
(7)
Θ∈Πk−1

ψ∈Ξk−1

l=1

where Ξk−1 is the finite group formed by the (k − 1)! permutations on the set Nk−1 , Θ = {θ1 , θ2 , . . . , θk−1 } ⊂
N|V| K{i, j}, and Πk−1 = {Θ; Θ ⊂ N|V| K{i, j} ∧ |Θ| = k − 1}. Now from (7) and (4b) it follows that:


X
X

ck (νi , νj ) = (−1)k
P (Θ, ψ) .
(8)
Θ∈Πk−1

ψ∈Ξk−1

The fact that S(Θ) is a polynomial of degree |V| − |Θ| − 2 in s with leading coefficient 1, together with (2), (6) and
(8), leads to:
det(Cij ) = K +

|V|−2

X
k=1

(−1)κk (i,j) ck (νi , νj )w|V|−k−1 (s),

(9)

5

Rahimian et al.: Distinguishable Agreement Dynamics

where wl (s), l ∈ N|V|−2 are degree l polynomials in s whose leading coefficients are unity, and |K| ∈ N is a constant.
The proof follows immediately from (9) and upon noting that ck (νi , νj ) = 0 for k < d(νi , νj ).

2.2. Multi-Agent Systems under the Agreement Protocol
Consider a multi-agent system comprised of a set S = {x1 , x2 , . . . , xn } of n single integrator agents, where xi ,
i ∈ Nn is the state of agent i, which is assumed to be scalar. Further, for all i ∈ Nn assume that the control input of
agent i is constructed according to the following nearest neighbor law:
X
ẋi (t) =
(xj (t) − xi (t)), t > 0.
(10)
−
(νj ,νi )∈∂G
{νi }

The interaction structure between the agents in (10) can be described by a directed information flow graph
G = (V, E), where each vertex ν ∈ V corresponds to an agent x ∈ S and |V| = n. A directed edge from vertex νk to
vertex νi implies that the term xk (t) − xi (t) appears in the control law of the agent xi given by (10). As discussed in
Section 3.2 of [10], the existence of an out-branching root τ ∈ V is a necessary and sufficient condition for the states
in (10) to converge to a common value. This correspondence is often referred to as the agreement protocol.
For a multi-agent system S and its associated digraph G = (V, E), the in-degree graph Laplacian can be used to
represent the dynamic equations in (10) in compact matrix form as follows:
ẋ(t) = −L(G)x(t), t > 0,

(11)

where x(t) = (x1 (t), x2 (t), . . . , xn (t))T . The matrix exponential solution to (11) is then expressed as:
x(t) = e−L(G)t x(0), t > 0,

(12)

and for a particular agent xi ∈ S represented by the vertex νi ∈ V , the temporal evolution of its state is given by:
xi (t) = σ(νi )T e−L(G)t x(0), t > 0.

(13)

III. DIGRAPHS WITH DISTINGUISHABLE DYNAMICS
The notion of distinguishable digraphs is formally defined next. This notion provides a mathematical
characterization of link failures according to the state of an agent after the failure of a certain set of links in
the information flow structure, and it is motivated by the fact that different link failures in the original digraph
G = (V, E1 ∪ E2 ) can lead to distinct digraphs G1 = (V, E1 ) and G2 = (V, E2 ) which share the same set of vertices V
but have different sets of edges E1 and E2 .
Definition 1 Consider a multi-agent system S and two distinct digraphs G1 = (V, E1 ) and G2 = (V, E2 ) associated
with it. Digraphs G1 and G2 are said to be distinguishable from an agent x ∈ S if there exists x(0) ∈ R|V| such that
xG1 (t) − xG2 (t) 6≡ 0, t > 0, where xG1 (t) and xG2 (t) denote the state of the agent x calculated in the digraphs G1
and G2 , respectively, with the same initial condition x(0).
Example 1 Consider the digraph G1 depicted in Fig. 1, and let G2 denote the digraph obtained by removing the edge
(ν3 , ν2 ). The in-degree graph Laplacians of G1 and G2 are:


1 0 −1
L(G1 ) =  −1 2 −1  ,
(14)
−1 0
1
and



1
L(G2 ) =  −1
−1

0
1
0


−1
0 .
1

(15)

Fig. 1. The above digraph with or without edge  produce identical dynamics in either of the nodes ν1 and ν3 .

The in-degree graph Laplacians in (14) and (15) can be used to calculate the matrix exponential in (12) for G1 and
G2 , as follows:
 1

−2t
)
0 12 (1 − e−2t )
2 (1 + e
e−L(G1 )t =  12 (1 − e−2t ) e−2t 12 (1 − e−2t )  ,
(16)
1
1
−2t
−2t
(1
−
e
)
0
(1
+
e
)
2
2
and

e−L(G2 )t =
 1
−2t
)
2 (1 + e
 1 (1 − e−2t )
2
1
−2t
)
2 (1 − e

0
e−t
0

1
2 (1

1
−2t
)
2 (1 − e
−2t
−t

+e

1
2 (1



) − e .
+ e−2t )

(17)

It is evident from the expressions in (16) and (17) that G1 and G2 are distinguishable from x2 , but not from x1 and x3 .
3.1. Choice of Initial Conditions
A second look at matrices in (16) and (17) of Example 1 reveals that although the two digraphs are
distinguishable from the second agent, any initial conditions x(0) belonging to the span of the vectors (1, 0, 0)T
or (1, 1, 1)T induces the same response in the second agent. The latter is in fact in the null space of the Laplacian
matrix L(G) for any digraph G ; thence,
x(t) = e−L(G)t x(0) = 0,

(18)

for any x(0) = α1, α ∈ R. This gives rise to the interesting question that given two digraphs that are distinguishable
from a certain agent what more can be said about the choice of initial conditions leading to non-identical dynamics
in the particular agent. The following theorem indicates that the ability to distinguish two digraphs from an agent is a
generic property that can be studied independently of the choice of initial condition x(0).
Theorem 2 Given a multi-agent system S and two distinct digraphs G1 = (V, E1 ) and G2 = (V, E2 ) associated with
it, consider a vertex νi ∈ V corresponding to agent xi ∈ S . If G1 and G2 are distinguishable from xi , then for almost
all x(0) ∈ R|V| , xGi 1 (t) − xGi 2 (t) 6≡ 0, t > 0, where xGi 1 (t) and xGi 2 (t) denote the state of agent xi calculated in the
digraphs G1 and G2 , respectively, with the same initial condition x(0).
Proof. From the agent response given by (13), it follows that any initial condition x(0) for which xGi 1 (t) −
≡ 0, t > 0 should satisfy σ(νi )T (L(G1 )m − L(G2 )m )x(0) = 0 for all m ∈ N. This expression constitutes a
set of measure zero in R|V| , because G1 and G2 being distinguishable from xi implies that there exists an m ∈ N such
that σ(νi )T (L(G1 )m − L(G2 )m ) 6= 0.

As a consequence of Theorem 2, any randomly chosen initial conditions will induce different dynamics in an
agent from which the digraphs are distinguishable. Of particular interest are the cases, where certain graph symmetries
compromise the designer’s ability to distinguish between some network failures [18]. One such case is considered in
the next example.

xGi 2 (t)

7

Rahimian et al.: Distinguishable Agreement Dynamics

(a) G

(b) G1

(c) G2

Fig. 2. The digraphs of Example 2.

Example 2 Consider a multi-agent system S = {x1 , x2 , x3 , x4 } with the digraph G = (V, E), where V =
{ν1 , ν2 , ν3 , ν4 } and E = {(ν1 , ν2 ), (ν1 , ν3 ), (ν2 , ν3 ), (ν2 , ν4 ), (ν3 , ν2 ), (ν3 , ν4 )}, as depicted in Fig. 2(a).
The in-degree graph Laplacian for G is given by:


0
 −1
L(G) = 
−1
0


0 0
−1 0 
.
2 0 
−1 2

(19)

0
2
−1
−1


0 0
−1 0 
,
2 0 
0 1

(20)

0
2
−1
0


0 0
−1 0 
.
2 0 
−1 1

(21)

0
2
−1
−1

Let 1 := (ν3 , ν4 ) and 2 := (ν2 , ν4 ). The digraph of the system after the failure of the communication link between x2
and x4 is G1 = (V, EK{1 }), and after the failure of the communication link between x3 and x4 is G2 = (V, EK{2 }),
as depicted in Figs. 2(b) and 2(c), respectively.
The in-degree graph Laplacians of G1 and G2 are:


and

0
 −1
L(G1 ) = 
−1
0



0
 −1
L(G2 ) = 
−1
0

Consider now a permutation ψ : V → V defined as:

ψ(ν1 ) = ν1 , ψ(ν2 ) = ν3 , ψ(ν3 ) = ν2 , ψ(ν4 ) = ν4 .

(22)

The permutation matrix Ψ associated with ψ(·) in (22) is expressed as:


1
 0
Ψ=
0
0

0
0
1
0

0
1
0
0


0
0 
,
0 
1

(23)

and since ΨL(G) = L(G)Ψ, hence ψ(·) is an automorphism of G . Moreover, since Ψ(Γ(ν3 , ν4 ) − Γ(ν4 , ν4 )) =
(Γ(ν2 , ν4 ) − Γ(ν4 , ν4 ))Ψ, it follows that ΨL(G1 ) = L(G2 )Ψ. In other words, 1 and 2 are symmetric under the
automorphism given by the permutation matrix Ψ. On the other hand, Ψσ(ν1 ) = σ(ν1 ) and Ψσ(ν4 ) = σ(ν4 ).
Therefore, if Ψx(0) = x(0) (i.e. x2 (0) = x3 (0)), then both digraphs G1 and G2 induce the same responses in either
of the agents x1 and x4 ; that is, x11 (t) = x12 (t), t > 0 and x41 (t) = x42 (t), t > 0, where the superscripts i , i
= 1, 2 indicate the state values computed in the digraphs Gi , i = 1, 2. The reason is that L(G1 ) = ΨT L(G2 )Ψ,
T
and σ(ν)T e−L(G1 )t x(0) = σ(ν)T e−Ψ L(G2 )Ψt x(0) = σ(ν)T ΨT e−L(G2 )t Ψx(0). Now, since σ(ν)T ΨT = σ(ν)T for
ν ∈ {2, 4}, and Ψx(0) = x(0) because of x2 (0) = x3 (0), agents x2 and x4 will have the same responses in either of
the digraphs. It is also worth highlighting that regardless of how the states of the agents are initialized, the temporal
evolution of the state of x1 is given by x1 (t) = x1 (0), t > 0 and it is not affected by any link failure across the network.
In the following subsection the main theorem of the paper is stated and proved. This theorem provides necessary
conditions under which two distinct digraphs, corresponding to a multi-agent system S , are not distinguishable from
an agent xi ∈ S . It is therefore true that the negation of the stated conditions can be interpreted as sufficient for the
digraphs to be distinguishable from xi .
3.2. The Main Theorem
The entries of the inverse of the matrix H introduced in Lemma 1 are polynomial fractions in the Laplace
variables s. Equating the leading coefficients in the i−th rows of H −1 of two digraphs leads to a necessary
consequence for them having identical dynamics in their i−th nodes. This is set forth in the following theorem,
which constitutes the main result of this section.
Theorem 3 Given a multi-agent system S and two distinct digraphs G1 = (V, E1 ) and G2 = (V, E2 ) associated with
it, consider a vertex νi ∈ V corresponding to agent xi ∈ S . If G1 and G2 are not distinguishable from xi , then
d1 (ν, νi ) = d2 (ν, νi ) for all ν ∈ VK{νi }, and c1k (ν, νi ) = c2k (ν, νi ) for k = d1 (ν, νi ) = d2 (ν, νi ), where clk (ν, νi ) and
dl (ν, νi ) denote ck (ν, νi ) and d(ν, νi ), respectively, for digraph Gl , l = 1, 2.
Proof: If G1 and G2 are not distinguishable from xi , then xG1 (t) − xG2 (t) ≡ 0 for any x(0) ∈ R|V| , and from
(13), it follows that:
σ(νi )T e−L(G1 )t = σ(νi )T e−L(G2 )t , t > 0.
(24)
Let Hl = sI + L(Gl ), l = 1, 2, where s ∈ C is the Laplace variable. Taking the Laplace transform of (24):
σ(νi )T H1 −1 = σ(νi )T H2 −1 ,

or equivalently:



H1 −1



ip



= H2 −1 ip , p ∈ N|V| .

The adjoint of Hl , l = 1, 2 can now be used to compute the inverse matrices as follows:

l
 −1 
(−1)m+n det Cmn
, m, n ∈ N|V| , l = 1, 2,
Hl
=
nm
det (Hl )

(25)
(26)

(27)

l
where Cmn
, l = 1, 2, is the matrix obtained by removing the m−th row and n−th column of Hl , l = 1, 2. It follows
from (26) and (27) that:


1
2
det Cji
det Cji
=
, j ∈ N|V| ,
(28)
det (H1 )
det (H2 )

or:



1
2
det Cji
det (H2 ) = det Cji
det (H1 ), j ∈ N|V| .

(29)

9

Rahimian et al.: Distinguishable Agreement Dynamics

Next, det (Hl ) , l = 1, 2 in (29) can be written as a summation over the product of all possible permutations on |V|
matrix elements [11], as given below:
det (H2 ) =

X

(−1)

ι(ψ)

det (H1 ) =

[H2 ]jψ(j) ,

(30a)

[H1 ]jψ(j) ,

(30b)

j=1

ψ∈Ξ|V|

X

|V|
Y

(−1)

ι(ψ)

|V|
Y

j=1

ψ∈Ξ|V|

where Ξ|V| is the finite group formed by the (|V|)! permutations on the set N|V| . Moreover, for a permutation ψ(.) on
the set N|V| , ι(ψ) denotes its length. For l = 1, 2, note that the only term in det (Hl ) which includes s|V| (or s|V|−1 )
in the right-hand sides of (30) is the one corresponding to the diagonal elements of Hl , and is given by:
|V|
Y

k=1

[Hl ]kk =

Y

ν∈V

(s + dlin (ν)) = s|V| +

X

ν∈V

!

dlin (ν) s|V|−1 + . . . +

Y

dlin (ν),

(31)

ν∈V

where for ν ∈ V and l = 1, 2, dlin (ν) denotes din (ν) in Gl . The power of s in any other term in the right-hand sides
of (30) is less than |V| − 1. The proof now follows immediately from Lemma 1 and upon equating the leading
coefficients and the polynomial degrees in the left-hand side and right-hand side of (29) for j ∈ N|V| K{i}.

According to Theorem 3, in order to determine that two digraphs are distinguishable from an agent corresponding
to vertex νi it suffices to find some vertex whose distance to νi differs in each digraph, or else if all vertices are at
the same distance from νi in either digraphs, then it is also sufficient to find a vertex who has a different number of
shortest paths to vertex νi in each digraph. The authors in [1] provide relevant claims that connect the relative degree
and gain factor of the transfer function of a consensus network with an observer node (output) and a controller node
(input) to the length and number of shortest paths between those two nodes. However, the proof they provide is not
correct because in Lemma 3.1 they make use of a matrix product commutative property that does not hold true.
The next corollary follows by applying the sufficient conditions of Theorem 3 to the tail vertices of ∂G− {ν} for
an observing agent {νi }, and provides useful information about indistinguishable digraphs. In essence, it states that
such digraphs should be identical in the immediate (incoming) vicinity of the observation point.
Corollary 1 Consider a multi-agent system S , an agent x ∈ S , and two distinct digraphs G1 = (V, E1 ) and G2 =
(V, E2 ) that are both associated with S . Let νi ∈ V be the vertex that corresponds to x, for some i ∈ N|V| . If G1
and G2 are not distinguishable from x, then σ(νi )L(G1 ) = σ(νi )L(G2 ), so that ∂G−1 {νi } = ∂G−2 {νi }, and in particular
−
d−
G1 {νi } = dG2 {νi }.

IV. JOINTLY DETECTABLE LINK FAILURES
In this section, the notion of distinguishable digraphs from Definition 1 is used to define and characterize the
concept of joint detectability for a multi-agent system subject to simultaneous link failures.
Definition 2 Given a multi-agent system S and its associated digraph G = (V, E), a subset of edges E1 ⊂ E is said
to be jointly detectable from the agent x ∈ S if G and G1 = (V, EKE1 ) are distinguishable from x.
The next Proposition follows from Theorem 3 using a contradiction argument. The proposition provides
sufficient graphical conditions for joint detectability of a link-set from an observing agent.
Proposition 1 Given a multi-agent system S and its associated digraph G1 = (V, E), consider a vertex νi ∈ V
corresponding to agent xi ∈ S , and a subset of edges E1 ⊂ E . If there exists an edge  := (νj , νk ) ∈ E1 such that
d(νj , νi ) > d(νk , νi ), then E1 is jointly detectable from xi .

Proof: The proof follows by contradiction. Suppose that E1 is not jointly detectable from xi and denote
G2 = (V, EKE1 ), such that G1 and G2 are not distinguishable from xi .
It follows from Theorem 3 that for some {dˆ1 , dˆ2 } ⊂ N|V|−2 :
dˆ1 = d1 (νk , νi ) = d2 (νk , νi ),
dˆ2 = d1 (νj , νi ) = d2 (νj , νi ),

(32b)

c1dˆ (νk , νi ) = c2dˆ (νk , νi ),

(33a)

c1dˆ (νj , νi )
2

(33b)

(32a)

and
1

1

=

c2dˆ (νj , νi ),
2

where for {τ, ν} ⊂ V and l = 1, 2, clk (τ, ν) and dl (τ, ν) denote ck (τ, ν) and d(τ, ν), respectively, for digraph Gl .
Let P be a νk νi path with length dˆ1 = d2 (νk , νi ) in G2 . Since P is a νj νi path with length 1 + dˆ1 in G1 , one has
that:
d1 (νj , νi ) 6 1 + d2 (νk , νi ).
(34)
On the other hand, the assumption d1 (νk , νi ) < d1 (νj , νi ), together with (32a), leads to:
d2 (νk , νi ) < d1 (νj , νi ).

(35)

d1 (νj , νi ) = 1 + d2 (νk , νi ).

(36)

The inequalities (34) and (35) imply that:

Next, from (32) and (36) it follows that dˆ2 = 1 + dˆ1 and note that since (EKE1 ) ⊂ E , every νj νi path with length
ˆ
d2 in G2 is a νj νi path with length dˆ2 in G1 , while P is a νj νi path with length dˆ1 + 1 = dˆ2 = d1 (νj , νi ) in G1 that

does not exist in G2 . Hence, c1dˆ (νj , νi ) > 1 + c2dˆ (νj , νi ), which is in contradiction with (33b).
2

2

In particular, d(νk , νi ) in Proposition 1 can be equal to zero, in which case  ∈ ∂G−1 {νi } and any subset containing
such an edge will be jointly detectable from xi . Intuitively, under the conditions specified in Proposition 1 the vertex
νj is located at a greater distance from the observing vertex νi as compared to the vertex νk . Hence, the “information”
concerning the state of νj will “reach” the observing agent “faster” when passed through the failed edge (νj , νk ).
The next proposition extends the result provided in [17] for a single link to any combination of links with a common
head vertex.
Proposition 2 Consider a multi-agent system S , its associated digraph G1 = (V, E), an agent xi ∈ S with its
corresponding vertex νi ∈ V , a vertex νk ∈ V , and a subset of edges E2 ⊂ ∂G−1 {νk }. If there exists an out-branching
root νo ∈ VK{νk } as well as a νk νo path in G2 = (V, EKE2 ), then E2 is jointly detectable from xi .
Proof: The result for k = i is a direct consequence of (10). For k 6= i suppose that Proposition 2 does not
hold true, i.e., νo is an out-branching root of G2 and there exists a νk νo path in G2 , but xG1 (t) − xG2 (t) ≡ 0 for all
x(0) ∈ R|V| , where xG1 (t) and xG2 (t) denote the state of the agent x calculated in the digraphs G1 and G2 , respectively,
with the same set of initial conditions x(0). Let Hl = sI + L(Gl ), l = 1, 2, where s ∈ C is the Laplace variable.
Moreover, denote the (|V| − 1) × (|V| − 1) sub-matrix that results from removing the m−th row and n−th column
l
of Hl by Cmn
, l = 1, 2. Since xG1 (t) − xG2 (t) ≡ 0 for all x(0) ∈ R|V| , (24) to (27) still hold and it follows from the
equality:
X
L(G2 ) = L(G1 ) − |E2 |Γ((νk , νk )) +
Γ(),
(37)
∈E2

that the matrices Hl , l = 1, 2, will only differ at [Hl ]kk and [Hl ]kj for all j ∈ {n ∈ N|V| ; (νn , νk ) ∈ E2 }. Therefore,
1
2
1
2
after removing the k−th row from Hl , l = 1, 2, one has that Cki
= Cki
, s ∈ C, or det(Cki
) ≡ det(Cki
) 6≡ 0, where
2
the inequality follows from Theorem 1, since det(Cki ) at s = 0 is equal
to
the
number
of
ν
-rooted
spanning
outk



branchings of G2 . On the other hand, it follows from (26) that H1 −1 ik ≡ H2 −1 ik . Now, substituting from (27)

11

Rahimian et al.: Distinguishable Agreement Dynamics

(a) G

(b) G1

(c) G2

Fig. 3. The digraphs for Example 3.

2
1
) ≡det(Cki
) 6≡ 0, one arrives at the relation det (sI + L(G1 )) ≡ det (sI + L(G2 )). Similarly, the
and using det(Cki
−1
−1
1
2
equality H1
≡
H
along with the preceding result yields det Coi
= det Coi
, s ∈ C. According to
2
io
io
Theorem 1, for s = 0 this means that G1 and G2 have the same number of νo -rooted spanning out-branchings. This,
however, is a contradiction since νo being an out-branching root of G2 , together with νk 6= νo , implies that the number
of νo -rooted spanning out-branchings in G1 is strictly greater than G2 .

It is notable that if all of the links in the set ∂G−1 {νk } in Proposition 2 are simultaneously removed to form the
digraph G2 , then the vertex νo 6= νk is not an out-branching root of G2 . Therefore, the set ∂G−1 {νk } does not satisfy the
sufficient conditions given by Proposition 2 for joint detectability from agent xi . It is worth highlighting that under
the conditions of Proposition 2, νk is also an out-branching root of G , so that there exists a νk νi path from the head
vertex of the failed links to the vertex corresponding to the observing agent xi . Consequently, the “information”
concerning the link failures can “reach” the observing agent. Even though the sufficient conditions in Proposition 2
may be too conservative, they do pave the way for the following useful Corollary for the special case of strongly
connected digraphs, of which connected undirected graphs can be regarded as a special class.

Corollary 2 Consider a multi-agent system S and its associated digraph G1 = (V, E). If G2 = (V, EK{}) is strongly
connected for all  ∈ E , then any edge {} is jointly detectable from any agent x, ∀ ∈ E and ∀x ∈ S .
Example 3 Consider a multi-agent system S = {x1 , x2 , x3 , x4 } with the digraph G = (V, E), where V =
{ν1 , ν2 , ν3 , ν4 } and E = {(ν1 , ν2 ), (ν1 , ν3 ), (ν2 , ν3 ), (ν2 , ν4 ), (ν3 , ν1 ), (ν3 , ν2 ), (ν3 , ν4 )}, as depicted in Fig. 3(a).
The digraphs resulting from the failure of each of the links 1 := (ν1 , ν2 ) and 4 := (ν2 , ν4 ) are G1 = (V, EK{1 })
and G4 = (V, EK{4 }), which are depicted in Figs. 3(b) and 3(c). The responses of x1 calculated in digraphs G , G1
and G2 are denoted by x1 (t), x11 (t), and x14 (t), respectively, and they are depicted in Figs. 4(a) and 4(b), with the
same random initial states. It is straightforward to verify that 4 is not detectable from x1 because although ν1 is an
out-branching root, ν4 is not and there does not exist a path from ν4 to ν1 in G2 .
Remark 1 For the cases where the agents are also prone to failures, it is notable that the effect of the removal of a
node from the digraph G is equivalent to removal of all edges that are incident to that node. It is therefore true that the
failure of the agent corresponding to node ν is detectable from agent x if the set of edges ∂G+ {ν} ∪ ∂G− {ν} is jointly
detectable from agent x.
To close this section, it is worth noting that the proof for the sufficient conditions in Proposition 1 relies on
the highest power of s and the leading coefficients in the minors of the transformed graph Laplacian. According
to Lemma 1, these parameters depend on the length and number of shortest paths between the graph vertices. On
the other hand, the proof of Proposition 2 revolves around the minors of the transformed graph Laplacian at s = 0,
which according to Theorem 1 are related to the number of rooted spanning out-branchings in the digraph. The two

0.6

0.59

0.59

x1 (t)

0.58

xǫ11 (t)

0.585
0.58
0.575

0.57
0.57
0.56
0.565
0.55
0.56
0.54
0.53
0.52

x1 (t)

0.555

xǫ14 (t)

0.55

0

1

2

3

t

4

5

(a) x11 (t) − x1 (t) 6≡ 0

6

7

0.545

0

1

2

3

t

4

5

6

7

(b) x14 (t) − x1 (t) ≡ 0
Fig. 4. The responses of x1 in digraphs of Example 3.

sets of results can therefore be interpreted as the two extremes corresponding to s → ∞ (leading coefficients) and
s = 0 (constant terms) in the minors of the transformed graph Laplacian (which are polynomials in s). The next
subsection offers a complete graphical representation for the class of jointly detectable links that satisfy the condition
of Proposition 1.
4.1. Shortest Paths Subgraph
The next definition and the corollary which follow provide a complete characterization of the class of detectable
links that satisfy the sufficient condition given in Proposition 1.
Definition 3 Given a digraph G = (V, E) and a vertex ν ∈ V , suppose that ∀µ ∈ VK{ν}, there exists a µν path in
G . The shortest subgraph of G w.r.t. ν is identified by KGν = (V, EK,ν ), where EK,ν ⊂ EK∂G+ {ν} and ∀ := (τ, ϑ) ∈
EK∂G+ {ν},  ∈ EK,ν ←→ d(τ, ν) = d(ϑ, ν) + 1.
Any link (τ, ϑ) ∈ EK∂G+ {ν} that satisfies the condition d(τ, ν) = d(ϑ, ν) + 1 in Definition 3 is guaranteed to
contribute to a shortest path from τ to ν . In particular, such a link satisfies the sufficient condition for detectability
from ν as expressed in Proposition 1. The following corollary is a restatement of Proposition 1 in terms of Definition 3.
Corollary 3 Given a multi-agent system S and its associated digraph G = (V, E), consider a vertex ν ∈ V
corresponding to agent x ∈ S , and a subset of edges Ef ⊂ E . Assume also that for any µ ∈ VK{ν}, there exists a
µν path in G , and let KGν = (V, EK,ν ) denote the shortest paths subgraph of G w.r.t. ν . If Ef ∩ EK,ν 6= ∅, then Ef is
jointly detectable from x.
4.2. Multiple Observation Points
If the states of more than one agent are available to the designer, then two graphs will be distinguishable from a
subset of nodes if and only if they are distinguishable in the sense of Definition 1, from at least one of the accessible
agents. Similarly, a given subset of links is detectable from a subset of agents if and only if the link-set is detectable
from at least one of the available agents. The concept of shortest path subgraph from the previous subsection can be
used to derive the following greedy heuristic, which is a computationally efficient procedure for determining a set O
of nodes from which the failure of any subset of links in the digraph will be detectable.

Rahimian et al.: Distinguishable Agreement Dynamics

13

Procedure 1 Determine Set O of Observation Points
Input: G = (V, E)
1: O ⇐ ∅
2: while E 6= ∅ do
3:
ν ⇐ arg max{|EK,ν̂ |; ν̂ ∈ V}
4:
O ⇐O∪ν
5:
E ⇐ EKEK,ν
6: end while
Output: O

V. CONCLUSIONS
The concept of distinguishable digraphs provides an effective mathematical characterization for the simultaneous
failure of links in multi-agent systems. The results indicate that the ability to distinguish two digraphs from a
given agent is a generic property that can be studied independently of the choice of initial states. The analytical
developments in this paper include a powerful extension to the all-minors matrix tree theorem that relates the
polynomial degree and leading coefficient of the minors of the transformed Laplacian of a digraph to the length
and number of shortest paths connecting its vertices. Moreover, the analytical results reveal an intricate relationship
between the ability to distinguish between the dynamic response of two multi-agent systems and the inter-nodal
distances and number of shortest paths in their digraphs. Detectability of link failures is studied as a special case, and
sufficient conditions indicate that, in order for a group of links to be jointly detectable from a given agent, it suffices
to design the information flow digraph in such a way that for one of the links in the group, the head vertex is at a
shorter topological distance from the observing agent, as compared to the tail vertex. Alternatively, a group of links
with a common head are jointly detectable from any agent in the network, provided the common head vertex is an
out-branching root and there exists another out-branching root in the network information flow digraph. The concept
of shortest paths subgraph can be used to efficiently select a subset of nodes from which the failure of any set of links
is detectable. Developing efficient detection and isolation procedures is the next step for future research.
REFERENCES
1. B. Briegel, D. Zelazo, M. Burger, and F. Allgower. On the zeros of consensus networks. In Proceedings of the
50th IEEE Conference on Decision and Control and European Control Conference, pages 1890 –1895, 2011.
2. F. Bullo, J. Cortés, and S. Martı́nez. Distributed Control of Robotic Networks. Princeton University Press, 2009.
3. S. Chaiken. A combinatorial proof of the all minors matrix tree theorem. SIAM Journal on Algebraic and
Discrete Methods, 3(3):319–329, 1982.
4. A. Chapman, M. Nabi-Abdolyousefi, and M. Mesbahi. Identification and infiltration in consensus-type
networks. In IFAC Workshop on Estimation and Control of Networked Systems, 2009.
5. G. Ferrari-Trecate, M. Egerstedt, A. Buffa, and M. Ji. Laplacian sheep: A hybrid, stop-go policy for leaderbased containment control. In Hybrid Systems: Computation and Control, volume 3927 of Lecture Notes in
Computer Science, pages 212–226. Springer Berlin/Heidelberg, 2006.
6. A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents using nearest
neighbor rules. IEEE Transactions on Automatic Control, 48(6):988–1001, 2003.
7. S. Jafari, A. Ajorlou, and A. G. Aghdam. Leader localization in multi-agent systems subject to failure: A
graph-theoretic approach. Automatica, 47(8):1744–1750, 2011.
8. J. Kleinberg, M. Sandler, and A. Slivkins. Network failure detection and graph connectivity. SIAM Journal on
Computing, 38(4):1330–1346, 2008.
9. B. Liu, T. Chu, L. Wang, and G. Xie. Controllability of a leader-follower dynamic network with switching
topology. IEEE Transactions on Automatic Control, 53(4):1009 –1013, 2008.
10. M. Mesbahi and M. Egerstedt. Graph Theoretic Methods in Multiagent Networks. Princeton University Press,
2010.
11. C. D. Meyer. Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics,
2000.

12. N. Moshtagh, N. Michael, A. Jadbabaie, and K. Daniilidis. Vision-based distributed control laws for motion
coordination of nonholonomic robots. IEEE Transactions on Robotics, 25:851–860, 2009.
13. R. Olfati-Saber. Flocking for multi-agent dynamic systems: algorithms and theory. IEEE Transactions on
Automatic Control, 51(3):401–420, 2006.
14. R. Olfati-Saber and R.M. Murray. Consensus problems in networks of agents with switching topology and
time-delays. IEEE Transactions on Automatic Control, 49(9):1520–1533, 2004.
15. A. Olshevsky and J. N. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM Journal
on Control and Optimization, 48(1):33–35, 2009.
16. M. A. Rahimian and A. G. Aghdam. Structural controllability of multi-agent networks: Robustness against
simultaneous failures. Automatica, 49(11): 3149–3157, 2013.
17. M. A. Rahimian, A. Ajorlou, and A. G. Aghdam. Characterization of link failures in multi-agent systems under
the agreement protocol. In Proceedings of the American Control Conference, pages 5258–5263, 2012.
18. M. A. Rahimian, A. Ajorlou, R. Tutunov, and A. G. Aghdam. Identifiability of links and nodes in multi-agent
systems under the agreement protocol. In Proceedings of the American Control Conference, pages 6853–6858,
2013.
19. A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt. Controllability of multi-agent systems from a graph-theoretic
perspective. SIAM Journal on Control and Optimization, 48(1):162–186, 2009.
20. W. Ren and R. Beard. Consensus seeking in multiagent systems under dynamically changing interaction
topologies. IEEE Transactions on Automatic Control, 50(5):655–661, 2005.
21. W. Ren and R. Beard. Distributed Consensus in Multi-vehicle Cooperative Control. Springer, 2008.
22. A. Tahbaz-Salehi and A. Jadbabaie. A necessary and sufficient condition for consensus over random networks.
IEEE Transactions on Automatic Control, 53(3):791–795, 2008.
23. W. T. Tutte. Graph Theory. Cambridge University Press, 2001.
24. T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet. Novel type of phase transition in a system of
self-driven particles. Physical Review Letters, 75(6):1226–1229, 1995.
25. L. Xiao, S. Boyd, and S.-J. Kim. Distributed average consensus with least-mean-square deviation. Journal of
Parallel and Distributed Computing, 67:33–46, 2007.
26. M.-G. Yoon and K. Tsumura. Transfer function representation of cyclic consensus systems. Automatica,
47(9):1974–1982, September 2011.
27. S. Zhang, M. K. Camlibel, and M. Cao. Controllability of diffusively-coupled multi-agent systems with general
and distance regular coupling topologies. In Proceedings of the 50th IEEE Conference on Decision and Control
and European Control Conference, pages 759 –764, 2011.

