Modulus consensus in discrete-time signed networks and properties of
special recurrent inequalities

arXiv:1703.06853v1 [cs.SY] 20 Mar 2017

Anton V. Proskurnikov and Ming Cao
Abstract— Recently the dynamics of signed networks, where
the ties among the agents can be both positive (attractive) or
negative (repulsive) have attracted substantial attention of the
research community. Examples of such networks are models of
opinion dynamics over signed graphs, recently introduced by
Altafini (2012,2013) and extended to discrete-time case by Meng
et al. (2014). It has been shown that under mild connectivity
assumptions these protocols provide the convergence of opinions
in absolute value, whereas their signs may differ. This “modulus
consensus” may correspond to the polarization of the opinions
(or bipartite consensus, including the usual consensus as a
special case), or their convergence to zero.
In this paper, we demonstrate that the phenomenon of
modulus consensus in the discrete-time Altafini model is a
manifestation of a more general and profound fact, regarding
the solutions of a special recurrent inequality. Although such
a recurrent inequality does not provide the uniqueness of a
solution, it can be shown that, under some natural assumptions,
each of its bounded solutions has a limit and, moreover,
converges to consensus. A similar property has previously been
established for special continuous-time differential inequalities
(Proskurnikov, Cao, 2016). Besides analysis of signed networks,
we link the consensus properties of recurrent inequalities to the
convergence analysis of distributed optimization algorithms and
the problems of Schur stability of substochastic matrices.

I. I NTRODUCTION
In the recent years protocols for consensus and synchronization in multi-agent networks have been thoroughly
studied [1]–[4]. Much less studied are “irregular” behaviors, exhibited by many real-world networks, such as e.g.
desynchronization [5] and chaos [6]. An important step
in understanding these complex behaviors is to elaborate
mathematical models for “partial” or cluster synchronization,
or simply clustering [5], [7]–[9]. In social influence theory,
this problem is known as the community cleavage problem
or Abelson’s diversity puzzle [10], [11]: to disclose mechanisms that hinder reaching consensus among social actors
and lead to splitting of their opinions into several clusters.
One reason for clustering in multi-agent networks is the
presence of “negative” (repulsive, antagonistic) interactions
among the agents [8]. Models of signed (or “coopetition”)
A.V. Proskurnikov is with the Delft Center for Systems and Control (DCSC) at Delft University of Technology. He is also with
ITMO University and Institute for Problems of Mechanical Engineering
of Russian Academy of Sciences (IPME RAS), St. Petersburg, Russia; anton.p.1982@ieee.org
M. Cao is with the Engineering and Technology Institute (ENTEG) at
the University of Groningen, The Netherlands; m.cao@rug.nl
Financial support was provided by the ERC (ERC-StG-307207), NWO
(vidi-438730), Russian Federation President’s Grant MD-6325.2016.8, and
RFBR, grants 17-08-01728, 17-08-00715 and 17-08-01266. Theorem 1
is obtained at IPME RAS under the sole support of Russian Science
Foundation (RSF) grant 14-29-00142.

networks with positive and negative couplings among the
nodes describe a broad class of real-world systems, from
molecular ensembles [12] to continental supply chains [13].
Positive and negative relations among social actors can
express, respectively, trust (friendship) or distrust (hostility).
Negative ties among the individuals may also result from
the reactance or boomerang effects, first described in [14]:
an individual may not only resist the persuasion process, but
even adopt an attitude that is contrary to the persuader’s one.
A simple yet instructive model of continuous-time opinion dynamics over signed networks has been proposed by
Altafini [15], [16] and extended to the discrete-time case
in [17]. In the recent years, Altafini-type coordination protocols over static and time-varying signed graphs have been
extensively studied, see e.g. [18]–[25]. It has been shown
that under mild connectivity assumptions these models exhibit consensus in absolute value, or modulus consensus: the
agents’ opinions agree in modulus yet may differ in signs.
The modulus consensus may correspond to the asymptotic
stability of the network (the opinions of all individuals converge to zero), usual consensus (convergence of the opinions
to the same value, depending on the initial condition) and
polarization, or “bipartite consensus”: the agents split into
two groups, converging to the opposite opinions.
In the recent works [26], [27] it has been shown that the
effect of modulus consensus in the continuous-time Altafini
model is in fact a manifestation of a more profound result,
concerned with the special class of differential inequalities
ẋ(t) ≤ −L(t)x(t),

(1)

where L(t) stands for the Laplacian matrix of a time-varying
weighted graph. Although the inequality (1) is a seemingly
“loose” constraint, any of its bounded solutions (under natural connectivity assumptions) converges to a consensus equilibrium (this property is called consensus dichotomy). This
implies, in particular, the modulus consensus in the Altafini
model [26], [27] since the vector of the opinions’ absolute
values obeys the inequality (1). In this paper, we extend the
theory of differential inequalities to the discrete-time case,
where (1) is replaced by the recurrent inequality x(k + 1) ≤
W (k)x(k) with {W (k)}k≥0 being a sequence of stochastic
matrices. We establish the consensus dichotomy criteria for
these inequalities, which imply the recent results on modulus
consensus in the discrete-time Altafini model [17], [23]. We
also apply the recurrent inequalities to some problems of
matrix theory and the analysis of distributed algorithms for
optimization and linear equations solving.

II. P ROBLEM S ETUP

Proposition 1: Any solution of (2) obeys the inequality

We start with preliminaries and introducing some notation.
A. Preliminaries
First we introduce some notation. A vector x ∈ Rn is
non-negative (x ≥ 0) if xi ≥ 0 ∀i. Given two vectors x, y ∈
Rn , we write x ≥ y (respectively, x ≤ y) if x − y ≥ 0
(respectively, y − x ≥ 0). The vector of ones is denoted by
1n = (1, . . . , 1)> ∈ Rn . Given a matrix A = (aij ), we use
|A| = (|aij |) to denote the matrix of element-wise absolute
values (the same rule applies to vectors). A matrix A = (aij )
is stochastic
P if its entries are non-negative and all rows sum
to 1, i.e. j aij = 1 ∀i. We use ρ(A) to denote the spectral
radius of a square matrix A. The standard
Euclidean norm
√
of a vector x is denoted by kxk = x> x.
A non-negative matrix A = (aij )i,j∈V can be associated
to a (directed) weighted graph1 G[A] = (V, E[A], A), whose
set of arcs is E[A] = {(i, j) : aij 6= 0}.
B. Recurrent inequalities and consensus dichotomy.
In this paper, we are interested in the solutions of the
following discrete-time, or recurrent, inequality
x(k + 1) ≤ W (k)x(k),

k = 0, 1, . . .

(2)

n

where x(k) ∈ R is a sequence of vectors and W (k) ∈
Rn×n stands for a sequence of stochastic matrices.
Replacing the inequality in (2) by the equality, one obtains
the well-known averaging, or consensus protocol [30]–[32]
x(k + 1) = W (k)x(k),

(3)

dating back to the early works on social influence [33],
[34], rational decision making [35] and distributed optimization [36]. The algorithm (3) may be interpreted as the
dynamics of opinions2 formation in a network of n agents.
At each step of the opinion iteration k agent i calculates the
weighted average of its own opinion xi (k) and the others’
opinions; this averagePis used as the new opinion of the ith
agent xi (k + 1) =
j wij (k)xj (k). The graph G[W (k)]
naturally represents the interaction topology of the network
at step k. Agent i is influenced by agent j if wij (k) > 0,
otherwise the jth agent’s opinion xj (k) plays no role in the
formation of the new agent i’s opinion xi (k + 1).
A similar interpretation can be given to the inequality (2).
Unlike the algorithm (3), the opinion of agent i at each
step of opinion formation is not uniquely determined by
the opinions from the previous
step, but is only constrained
P
by them xi (k + 1) ≤ j wij (k)xj (k). The weight wij (k)
stands for the contribution of agent j’s opinion xj (k) to this
constraint, and in this sense it can also be treated as the
“influence” weight. The inequality (2) does not provide the
solution’s uniqueness for a given x(0), but only guarantees
the existence of an upper bound for the solutions.
1 We assume that the reader is familiar with the standard concepts of
graph theory, regarding directed graphs and their connectivity properties,
e.g. walks (or paths), cycles and strongly connected components [28], [29].
2 In the broad sense, “opinion” is just a scalar quantity of interest; it can
stand for e.g. a physical parameters or an attitude to some event or issue.

x(k) ≤ M 1n , M = max xi (0).
i
Proof: Proposition 1 is proved via straightforward
induction on k. By definition, x(0) ≤ M 1n ; if x(k) ≤ M 1n
then x(k + 1) ≤ W (k)x(k) ≤ M W (k)1n = M 1n .
Although many solutions of (2) are unbounded from
below, under certain assumptions any its bounded solution
converges to a consensus equilibrium c1n , where c ∈ R.
A similar property, called consensus dichotomy3 has been
established in [26], [27] for the differential inequalities (1).
Definition 1: The inequality (2) is said to be dichotomic
if any of its bounded (from below) solutions has a limit
x∗ = lim x(k). It is called consensus dichotomic if these
k→∞
limits are consensus equilibria x∗ = c∗ 1n , where c∗ ∈ R.
The main goal of this paper is to disclose criteria of
consensus dichotomy in the recurrent inequalities (2). In Section IV we discuss applications of these criteria to models of
opinion dynamics and algorithms of distributed optimization.
∆

III. M AIN R ESULTS
The first step is to examine time-invariant inequalities (2).
A. A dichotomy criterion for the time-invariant case
In this subsection, we assume that W (k) ≡ W is a
∆
constant matrix, whose graph G = G[W ] has s ≥ 1 strongly
connected (or strong) components G1 , . . . , Gs ; in general,
arcs between different components may exist (Fig. 1a). A
strong component is isolated if no arc enters or leaves it.
All strong components are isolated (Fig. 1b) if and only if
every arc of the graph belongs to a cycle [28, Theorem 3.2].

(a)

(b)

Fig. 1: Non-isolated (a) vs. isolated (b) strong components
Theorem 1: The inequality (2) with the static matrix
W (k) ≡ W is dichotomic if and only if all the strong
components G1 , . . . , Gs of its graph G are isolated and
aperiodic4 . The inequality is consensus dichotomic if and
only if G is strongly connected (s = 1) and aperiodic, or,
equivalently, the matrix W is primitive [29], [38].
The proof of Theorem 1, as well as the remaining results
of this section, is given in Appendix.
3 The term dichotomy originates from ODE theory. A system is dichotomic
if any of its solutions either grows unbounded or has a finite limit [37].
4 Recall that a graph is aperiodic if the greatest common divisor of its
cycles’ lengths (that is also referred to as the graph’s period) is equal to 1.

Remark 1: Let Vj stand for the set of nodes of Gj . Theorem 1 shows that the time-invariant dichotomic inequality (2)
reduces to s independent inequalities of lower dimensions
x(m) (k + 1) ≤ W (m) x(m) (k),

m = 1, . . . , s,

(4)

where x(m) (k) = (xi (k))i∈Vm , W (m) = (wij )i,j∈Vm and
each inequality (4) is consensus dichotomic.
Remark 2: The matrix is primitive if and only if [11],
[29], [38] its powers W k are strictly positive for large k.
B. Consensus dichotomy in the time-varying case
In this subsection, we extend the result of Theorem 1 to
the case of general time-varying inequality (2). Given ε >
0, let Sε denote the class of all stochastic matrices W =
(wij )i,j∈V , satisfying the two conditions:
1) wii ≥ ε for any i ∈ V ;
2) the graph Gε [W ] = (V, Eε [W ]) is strongly connected,
∆
where Eε [W ] = {(i, j) ∈ V × V : wij ≥ ε}.
In other words, removing from the graph G[W ] all “light”
arcs weighted by less than ε, the remaining subgraph Gε [W ]
is strongly connected and has self-loops at each node.
For any integers k ≥ 0 and m > k let Φ(m, k) =
∆
(ϕij (m, k))ni,j=1 = W (m − 1) . . . W (k) stand for the evolutionary matrix of the equation (3); for convenience, we
denote Φ(k, k) = In . It is obvious that any solution of (2)
satisfies also the family of inequalities
x(m) ≤ Φ(m, k)x(k) ∀m ≥ k ≥ 0.
The following theorem provides a consensus dichotomy
criterion for the case of the time-varying matrix W (k).
Theorem 2: The inequality (2) is consensus dichotomic if
ε > 0 exists that satisfies the following condition: for any
k ≥ 0 there exists m > k such that Φ(m, k) ∈ Sε .
Notice that for the static matrix W (k) ≡ W one has
Φ(m, k) = W m−k , so the condition from Theorem 2 means
that W s ∈ Sε for some s. It can be easily shown that
in this case W s(n−1) is a strictly positive matrix. On the
other hand, if W d is strictly positive for some d, then
W d ∈ Sε for sufficiently small ε > 0. In view of Remark 2
and Theorem 1, in the static case W (k) ≡ W the sufficient
condition of consensus dichotomy from Theorem 2 is in fact
also necessary, boiling down to the primitivity of W .
The condition from Theorem 2 is implied by the two
standard assumptions on the sequence {W (k)}k≥0 .
Assumption 1: There exists δ > 0 such that for any k ≥ 0
1) wii (k) ≥ δ for any i = 1, . . . , n;
2) for any i, j such that i 6= j one has wij (k) ∈ {0}∪[δ; 1].
Assumption 2: (Repeated joint strong connectivity) There
exists an integer B ≥ 1 such that the graph G[W (k) + . . . +
W (k + B − 1)] is strongly connected for any k.
Corollary 1: Let Assumptions 1 and 2 hold. Then the
inequality (2) is consensus dichotomic.
Proof: We are going to show that the condition from
Theorem 2 holds for ε = δ B and m = k + B, i.e.
Φ(k + B, k) ∈ SδB for any k. Indeed, ϕii (m, k) ≥ wii (m −

1) . . . wii (k) ≥ δ m−k ∀i whenever m ≥ k due to Assumption 1. Supposing that (i, j) ∈ G[W (l)], where k ≤ l < m,
one has Φ(m, k) = Φ(m, l + 1)W (l)Φ(l, k), and therefore
ϕij (m, k) ≥ ϕii (m, l + 1)wij (l)ϕjj (l, k) ≥ δ m−l−1 δδ l−k =
δ m−k . Applying this to m = k + B, one easily notices that
i is connected to j in the graph GδB [Φ(k + B, k)] whenever
wij (l) > 0 for some l = k, . . . , k + B − 1. Assumption 2
implies now that Φ(k + B, k) ∈ SδB for any k.
It should be noticed however that the condition of Theorem 2 may hold in many situations where Assumptions 1
and 2 fail. Even in the static case W (k) ≡ W , the
matrix W can be primitive yet have zero diagonal entries.
The following corollary illustrates another situation where
both Assumptions 1 and 2 may fail, whereas Theorem 2
guarantees consensus dichotomy.
Corollary 2: Suppose that for any k one has W (k) ∈
{W0 }∪W, where W0 stands for the primitive matrix and W
is a set of stochastic matrices, commuting with W0 : W0 W =
W W0 ∀W ∈ W. Let the set K0 = {k : W (k) = W0 } be
infinite. Then the inequality (2) is consensus dichotomic.
Proof: Let d be so large that W0d is a positive matrix,
whose minimal entry equals ε > 0. For any k, we can find
such m > k that the sequence k, k + 1, . . . , m − 1 contains d
elements from the set K0 . Since any W (j) commutes with
W0 , Φ(m, k) = Tk W0d , where Tk is some stochastic matrix,
and thus all entries of Φ(m, k) are not less than ε.
Many sequences {W (k)}, satisfying the conditions of
Corollary 2, fail to satisfy Assumptions 1 and 2. For instance,
if W 3 In then the sequence {W (k)} can contain an
arbitrary long subsequence of consecutive identity matrices,
which violates Assumption 2. Both the matrix W0 and
matrices from W may have zero diagonal entries, which also
violates Assumption 1. The set W can also be non-compact,
containing matrices with arbitrary small yet non-zero entries.
C. The case of bidirectional interaction
It is known that in the case of bidirectional graphs wij >
0 ⇔ wji > 0 the conditions for consensus in the network (3)
is reached under very modest connectivity assumptions.
Under Assumption 1, consensus is reached if and only if
the following relaxed version of Assumption 2 holds [31].
Assumption 3: (Infinite joint strong connectivity) The
graph G∞ = (V, E∞ ) is strongly connected, where
(
)
∞
X
E∞ = (i, j) :
wij (k) = ∞ .
k=1

The following result extends this consensus criterion to
the condition of consensus dichotomy in the inequality (2).
Theorem 3: Suppose that Assumption 1 and 3 hold and
for any k one has wij (k) > 0 ⇔ wji (k) > 0. Then the
inequality (2) is consensus dichotomic.
The relaxation of Assumption 1 in Theorem 3 remains a
non-trivial open problem. To the best of the authors’ knowledge, the same applies to usual consensus algorithms (3):
most of the existing results for consensus in discrete-time
switching networks [2], [30]–[32] rely on Assumption 1 or
at least require uniformly positive diagonal entries wii (k).

IV. E XAMPLES AND A PPLICATIONS
In this section we apply the criteria from Section III to
the analysis of several multi-agent coordination protocols.
A. Modulus consensus in the discrete-time Altafini model
We first consider the discrete-time Altafini model [17],
[19] of opinion formation in a signed network. This model
is similar to the consensus protocol (3) and is given by
ξ(k + 1) = A(k)ξ(k) ∈ Rn , or, equivalently
n
X
ξi (k + 1) =
aij (k)xj (k).

(5)

In general, the assumptions of Theorems 2 and 3 do not
guarantee the exponential convergence rate to the equilibrium, which is provided by Assumptions 1 and 2 [19], [25].
In the case of exponential convergence, an additional criterion has been established in [19], [25] (see also Theorem 2.3
in [23]), allowing to distinguish between “degenerate” modulus consensus (asymptotic stability of the linear system (5))
and polarization. In the latter case, the agents split into
two “hostile camps” V1 ∪ V2 = V = {1, . . . , n}, and the
opinions of agents from Vi converge to (−1)i M , where
M = M (ξ(0)) 6= 0 for almost all ξ(0). If V1 = ∅ or V2 = ∅,
then polarization reduces to usual consensus of opinions.

j=1

Here the matrix (aij (k)) satisfies the following assumption.
Assumption 4: For any k = 0, 1, . . ., the matrix A(k) =
(aij (k)) has non-negative diagonal entries aii (k) ≥ 0, and
the modulus matrix |A(k)| = (|aij (k)|) is stochastic.
The non-diagonal entries aij (k) in (5) may be both
positive and negative. Considering the elements ξi (k) as
“opinions” of n agents, the positive value aij (k) > 0 can
be treated as trust or attraction among agents i and j. In
this case, agent i shifts its opinion towards the opinion of
agent j. Similarly, the negative value aij (k) < 0 stands
for distrust or repulsion among the agents: the ith agent’s
opinion is shifted away from the opinion of agent j. The
central question concerned with the model (5) is reaching
consensus in absolute value, or modulus consensus [17].
Definition 2: We say that modulus consensus is established by the protocol (5) if the coincident limits exist
lim |ξ1 (k)| = . . . = lim |ξn (k)| for any ξ(0) ∈ Rn .

k→∞

The absolute values

k→∞
xi (k) =

xi (k + 1) ≤

n
X

|ξi (k)| obey the inequalities

|aij (k)|xj (k) ∀i,

(6)

j=1

and hence the vector x(k) = (x1 (k), . . . , xn (k))> obeys (2)
with W (k) = |A(k)|. If this recurrent inequality is consensus
dichotomic, then modulus consensus in (5) is established.
Theorems 2 and 3 yield in in the following criterion.
Theorem 4: Modulus consensus in (5) is established, if the
sequence of matrices W (k) = |A(k)| satisfies the conditions
of Theorem 2 or Theorem 3.
In particular, if Assumption 1 holds, then modulus consensus is ensured by the repeated strong connectivity (Assumption 2), which can be relaxed to the infinite strong
connectivity (Assumption 3) if the network is bidirectional
wij (k) > 0 ⇔ wji (k) > 0. Theorem 4 includes thus the
results of Theorems 2.1 and 2.2 in [23]. As discussed in
Section III, the condition from Theorem 2 holds in many
situations where Assumption 1 fails, e.g. W (k) ≡ W may
be a constant primitive matrix with zero diagonal entries.
Unlike consensus algorithms (3), where the gains wij (k) are
design parameters, the social influence (or “social power”)
of an individual over another one depends on many uncertain
factors [39], and the uniform positivity of the non-zero gains
|aij (k)| may become a restrictive assumption.

B. Substochastic matrices and the Friedkin-Johnsen model
non-negative matrix A = (aij ) is called substochastic if
PA
n
of A is a deficiency
j=1 aij = 1 ∀i. We say that the ith rowP
row of A if the latter inequality is strict j aij < 1. Unlike
a stochastic matrix, always having an eigenvalue at 1, a
substochastic square matrix is usually Schur stable ρ(A) < 1.
Theorem 1 allows to give an elegant proof of the Schur
stability criterion for substochastic matrices [40], [41].
Lemma 1: Let G = G[A] be P
the graph of a substochastic
square matrix A and Id = {i : j aij < 1} is the subset of
its nodes, corresponding to the deficiency rows of A. If any
node j either belongs to the set Id , or Id is reachable from
it in G via some walk, then ρ(A) < 1.
Proof: Consider the matrix W = (wij ), defined by
!
X
1
∆
1−
ail ≥ aij .
wij = aij +
n
l

Obviously, W = (wij ) is stochastic and wij > aij ≥ 0 ∀j
when i ∈ Id . Hence in the graph G[W ] each node i ∈ Id is
connected to any other node and to itself, and hence G[W ] is
aperiodic. The condition of Lemma 1 implies that G[W ] is
also strongly connected. Choosing an arbitrary non-negative
vector x0 ≥ 0, the vectors x(k) = Ak x0 are non-negative for
any k ≥ 0 and satisfy the inequality (2) with W (k) ≡ W .
Thanks to Theorem 1, x(k) → c1, where c ≥ 0. It remains
to notice that 1 is not an eigenvector of A since Id (A) 6= ∅,
and hence c = 0. Thus Ak x0 → 0 as k → ∞ for any x0 ≥ 0,
which implies the Schur stability of A since any vector x0
is a difference of two non-negative vectors.
Notice that Lemma 1 implies the following well-known
property of substochastic irreducible matrices [38]: if G is
strongly connected then A is either stochastic or Schur stable.
The condition from Lemma 1 is not only sufficient but also
necessary for the Schur stability [41]. Lemma 1 implies the
condition of opinion convergence in the Friedkin-Johnsen
model of opinion formation [10], [41], [42]
x(k) = ΛW x(k) + (I − Λ)u,

u = x(0).

(7)

Here W is a stochastic matrix of influence weights, and Λ is
a diagonal matrix of the agents’ susceptibilities to the social
influence [42], 0 ≤ λii ≤ 1. Without loss of generality, one
may suppose that λii = 0 ⇔ wii = 1; in this case agent
i is stubborn xi (k) ≡ xi (0) (often it is assumed [42] that

consider the following three algorithms
hXn
i
ξi (k + 1) = PΞi
wij (k)ξj (k) ,
j=1
hXn
i
ξi (k + 1) = PΞi
wij (k)PΞj (ξj (k)) ,
j=1
X
ξi (k + 1) = wii (k)PΞi (ξi (k)) +
wij (k)ξj (k).
Fig. 2: The projection onto a closed convex set

k→∞

(8)

By noticing that the graphs G[ΛW ] and G[W ] differ only by
the structure of self-loops (recall that λii > 0 unless wii = 1
and wij = 0 ∀j 6= i), Lemma 1 implies the following.
Corollary 3: [41] The opinions (8) converge if from each
agent i with λii = 1 there exists a walk in G[W ] to some
agent j with λjj < 1, that is, each agent is either prejudiced
or influenced (directly or indirectly) by a prejudiced agent.
Using Theorems 2 and 3, some stability criteria for the
time-varying extension [43] of the Friedkin-Johnsen model
can be obtained that are beyond the scope of this paper.

lim x1 (k) = . . . = lim xn (k) ∈ Ξ.
(13)
k→∞
Proof: Due to the page limit, we give only an outline
of the proof. By assumption, there exists some ξ0 ∈ Ξ.
∆
∆
∆
Denote
Pi (·) = PΞi (·), di (·) = dΞi (·) and let ηi (k) =
P
j wij (k)ξj (k). Under Assumptions 1 and 2, to prove the
constrained consensus (13) it suffices to show [46] that
k→∞

∆

ei (k) = ξi (k + 1) − ηi (k) −−−−→ 0,

di (ξi (k)) −−−−→ 0.
k→∞
(14)
Applying (9) to Ω = Ξi , x = ξ, y = ξ0 ∈ Ξi , one gets
k→∞

kξ − ξ0 k2 ≥ kPi (ξ) − ξ0 k2 + di (ξ)2

In this subsection, we consider another application of
the recurrent inequalities case, related to the problem of
constrained or “optimal” consensus that is closely related
to distributed convex optimization [44]–[46] and distributed
algorithms, solving linear equations [47]–[49].
For any closed convex set Ω ⊂ Rd and x ∈ Rd the
projection operator PΩ : x ∈ Rd 7→ PΩ (x) ∈ Ω can
be defined, mapping a point to the closest element of Ω,
i.e. kx − PΩ (x)k = miny∈Ω kx − yk. This implies that
](y − PΩ (x), x − PΩ (x)) ≥ π/2 (Fig. 2) and
2

kx − yk ≥ kx − PΩ (x)k + ky − PΩ (x)k
∆

∀y ∈ Ω. (9)

The distance dΩ (x) = kx − PΩ (x)k is a convex function.
Consider a group of n discrete-time agents with the state
vectors ξi (k) ∈ Rd . Each agent is associated with a closed
convex set Ξi ⊆ Rd (e.g., the set of minima of some convex
function). The agents’ cooperative goal is to find some point
∆
ξ∗ ∈ Ξ = Ξ1 ∩ . . . ∩ Ξn . To solve this problem, various
modifications of the protocol (3) have been proposed. We

∀ξ ∈ Rd ,

(15)

and therefore kξ − ξ0 k ≥ kPi (ξ) − ξ0 k. Each protocol (10)∆
(12) thus implies the recurrent inequality (2), where xi (k) =
kξi (k) − ξ0 k ∀i. For instance, the equation (10) entails that
0 ≤ xi (k+1) ≤

2

(12)

Here W (k) = (wij (k)) stands for the sequence of stochastic
matrices. The protocol (10) has been proposed in the influential paper [44] (see also [46]), dealing with distributed
optimization problems. The special cases of protocols (11)
and (12) naturally arise in distributed algorithms, solving
linear equations, see respectively [47], [48] and [49]; a
randomized version of (12) has been also examined in [45].
Theorem 5: Let the set Ξi be closed and convex, and
assume that Ξ = Ξ1 ∩ . . . ∩ Ξn 6= ∅. Suppose that the
matrices W (k) satisfy Assumptions 1 and 2. Then each of
the protocols (10)-(12) establishes constrained consensus:

C. Constrained consensus

2

(11)

j6=i

λii = 1 − wii ). Another extremal case is λii = 1, which
means that agent i “forgets” its initial opinion ui = xi (0) and
iterates
the usual procedure of opinion averaging xi (k+1) =
P
w
x
j ij j (k). If 0 < λii < 1, then agent i is “partially
stubborn” or prejudiced [11], [43]: such an agent adopts the
others’ opinions, however it is “attached” to its initial opinion
xi (0) and factors it into every opinion iteration.
If the substochastic matrix ΛW is Schur stable, then the
opinion vector x(k) in (7) converges to the equilibrium
x(k) −−−−→ (I − ΛW )−1 (I − Λ)u.

(10)

n
X

wij (k)ξj (k) − ξ0 ≤

j=1

n
X

wij (k)xj (k).

j=1

Corollary 1 implies the existence of the common limit x∗ =
limk→∞ xi (k) ≥ 0. We are now going to prove (14) for the
protocol (10). The second statement in (14) is obvious since
di (ξi (k + 1)) ≡ 0. Substituting ξ = ηi (k) into (15),
(15)

(10)

kei (k)k2 = di (ηi (k))2 ≤ kηi (k) − ξ0 k2 − xi (k + 1)2 ≤
X
≤
wij (k)xj (k) − xi (k + 1) −−−−→ 0.
j

k→∞

(16)
To prove (14) for the protocol (12), notice that
X
(10)
xi (k + 1) ≤ wii (k)kPi (ξi (k)) − ξ0 k +
wij xj (k)
j6=i

(17)
X
p
2
2
wij xj (k).
≤ wii (k) xi (k) − di (ξi (k)) +

(15)

j6=i

Recalling that wii (k) ≥ δ and xi (k) → x∗ ∀i, it can be shown
that di (ξi (k)) → 0 and hence kei (k)k = wii (k)di (ξi (k)) →
0. The property (14) for the protocol (11) is proved similarly,
combining the arguments from (16) and (17).

V. C ONCLUSIONS
In this paper, we have examined a class of recurrent
inequalities (2), inspired by the analysis of “modulus consensus” in signed networks. Under natural connectivity assumptions the inequality is shown to be consensus dichotomic,
that is, any of its solution is either unbounded or converges
to consensus. Besides signed networks, we illustrate the
applications of this profound property to some problems of
matrix theory and distributed optimization algorithms.
R EFERENCES
[1] R. Olfati-Saber, J. Fax, and R. Murray, “Consensus and cooperation
in networked multi-agent systems,” Proceedings of the IEEE, vol. 95,
no. 1, pp. 215–233, 2007.
[2] W. Ren and R. Beard, Distributed Consensus in Multi-Vehicle Cooperative Control: Theory and Applications. London: Springer-Verlag,
2008.
[3] W. Ren and Y. Cao, Distributed Coordination of Multi-agent Networks.
Springer, 2011.
[4] F. Lewis, H. Zhang, K. Hengster-Movris, and A. Das, Cooperative
Control of Multi-Agent Systems. Optimal and Adaptive Design Approaches. London: Springer-Verlag, 2014.
[5] L. Pecora, F. Sorrentino, A. Hagerstrom, T. Murphy, and R. Roy,
“Cluster synchronization and isolated desynchronization in complex
networks with symmetries,” Nature Commun., vol. 5, p. 4079, 2014.
[6] O. Popovych, Y. Maistrenko, and P. Tass, “Phase chaos in coupled
oscillators,” Phys. Rev. E, vol. 71, p. 065201, 2005.
[7] A. Pogromsky, “A partial synchronization theorem,” Chaos, vol. 18,
p. 037107, 2008.
[8] W. Xia and M. Cao, “Clustering in diffusively coupled networks,”
Automatica, vol. 47, no. 11, pp. 2395–2405, 2011.
[9] A. Proskurnikov and M. Cao, “A novel homogenous protocol for multiagent clustering over directed graphs,” in Proc. American Control
Conference (ACC), Boston, MA, 2016, pp. 1906–1911.
[10] N. Friedkin, “The problem of social control and coordination of
complex systems in sociology: A look at the community cleavage
problem,” IEEE Control Syst. Mag., vol. 35, no. 3, pp. 40–51, 2015.
[11] A. Proskurnikov and R. Tempo, “A tutorial on modeling and analysis
of dynamic social networks. Part I,” Annual Reviews in Control, 2017,
published online.
[12] C.-C. Lin, C.-H. Lee, C.-S. Fuh, H.-F. Juan, and H.-C. Huang, “Link
clustering reveals structural characteristics and biological contexts in
signed molecular networks,” PLoS One, vol. 8, no. 6, p. e67089, 2013.
[13] G. Pache, “Coopetitive supply chains: Toward a social ties perspective,” Management, vol. 18, no. 2, pp. 125–140, 2013.
[14] C. Hovland, I. Janis, and H. Kelley, Communication and persuasion.
New Haven: Yale Univ. Press, 1953.
[15] C. Altafini, “Dynamics of opinion forming in structurally balanced
social networks,” PLoS ONE, vol. 7, no. 6, p. e38135, 2012.
[16] ——, “Consensus problems on networks with antagonistic interactions,” IEEE Trans. Autom. Control, vol. 58, no. 4, pp. 935–946, 2013.
[17] Z. Meng, G. Shi, K. Johansson, M. Cao, and Y. Hong, “Modulus
consensus over networks with antagonistic interactions and switching
topologies,” Publ. online on arxiv.org/abs/1402.2766.
[18] J. Hendrickx, “A lifting approach to models of opinion dynamics with
antagonisms,” in Proc. of IEEE Conference on Decision and Control
(CDC), 2014, pp. 2118–2123.
[19] J. Liu, X. Chen, T. Başar, and M.-A. Belabbas, “Stability of discretetime Altafini’s model: a graphical approach,” in Proc. of IEEE Conf.
Decision and Control (CDC), 2015, pp. 2835–2840.
[20] W. Xia, M. Cao, and K. Johansson, “Structural balance and opinion
separation in trust–mistrust social networks,” IEEE Trans. Control
Netw. Syst., vol. 3, no. 1, pp. 46–56, 2016.
[21] A. Proskurnikov, A. Matveev, and M. Cao, “Opinion dynamics in
social networks with hostile camps: Consensus vs. polarization,” IEEE
Trans. Autom. Control, vol. 61, no. 6, pp. 1524–1536, 2016.
[22] D. Meng, J. Du, and Y. Jia, “Interval bipartite consensus of networked
agents associated with signed digraphs,” IEEE Trans. Autom. Control,
vol. 61, no. 12, pp. 3755–3770, 2016.
[23] Z. Meng, G. Shi, K. Johansson, M. Cao, and Y. Hong, “Behaviors
of networks with antagonistic interactions and switching topologies,”
Automatica, vol. 73, pp. 110–116, 2016.

[24] J. Liu, X. Chen, and T. Başar, “Stability of the continuous-time Altafini
model,” in Proc. of Amer. Control Conf. (ACC), 2016, pp. 1931–1935.
[25] J. Liu, M. El Chamie, T. Başar, and B. Açikmeşe, “The discrete-time
Altafini model of opinion dynamics with communication delays and
quantization,” in Proc. of IEEE Conf. Decision and Control, 2016, pp.
3572–3577.
[26] A. Proskurnikov and M. Cao, “Dichotomic differential inequalities
and multi-agent coordination,” in Proc. European Control Conference
(ECC), Aalborg, Denmark, 2016, pp. 230–235.
[27] ——, “Differential inequalities in multi-agent coordination and opinion dynamics modeling,” Automatica, conditionally accepted, available
at https://arxiv.org/abs/1610.03373.
[28] F. Harary, R. Norman, and D. Cartwright, Structural Models. An
Introduction to the Theory of Directed Graphs. Wiley & Sons, 1965.
[29] F. Bullo, Lectures on Network Systems.
published online at
http://motion.me.ucsb.edu/book-lns, 2016, with contributions by J.
Cortes, F. Dorfler, and S. Martinez.
[30] A. Jadbabaie, J. Lin, and A. Morse, “Coordination of groups of mobile
autonomous agents using nearest neighbor rules,” IEEE Trans. Autom.
Control, vol. 48, no. 6, pp. 988–1001, 2003.
[31] V. Blondel, J. Hendrickx, A. Olshevsky, and J. Tsitsiklis, “Convergence in multiagent coordination, consensus, and flocking,” in Proc.
IEEE Conf. Decision and Control, 2005, pp. 2996 – 3000.
[32] M. Cao, A. Morse, and B. Anderson, “Reaching a consensus in a
dynamically changing environment: a graphical approach,” SIAM J.
Control Optim., vol. 47, no. 2, pp. 575–600, 2008.
[33] J. French Jr., “A formal theory of social power,” The Physchological
Review, vol. 63, pp. 181–194, 1956.
[34] F. Harary, “A criterion for unanimity in French’s theory of social
power,” in Studies in Social Power, D. Cartwright, Ed. Ann Arbor,
MI: Inst. for Social Research, 1959, pp. 168–182.
[35] M. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, pp. 118–121, 1974.
[36] J. Tsitsiklis, D. Bertsekas, and M. Athans, “Distributed asynchronous
deterministic and stochastic gradient optimization algorithms,” IEEE
Trans. Autom. Control, vol. 31, no. 9, pp. 803–812, 1986.
[37] V. A. Yakubovich, “Dichotomy and absolute stability of nonlinear
systems with periodically nonstationary linear part,” Systems Control
Lett., vol. 11, no. 3, pp. 221–228, 1988.
[38] C. Meyer, Matrix Analysis and Applied Linear Algebra. SIAM, 2000.
[39] J. French and B. Raven, “The bases of social power,” in Studies in
Social Power, D. Cartwright, Ed. Ann Arbor, MI: Inst. for Social
Research, 1959, pp. 150–167.
[40] P. Frasca, C. Ravazzi, R. Tempo, and H. Ishii, “Gossips and prejudices:
Ergodic randomized dynamics in social networks,” in Proc. of IFAC
NecSys 2013 Workshop, Koblenz, Germany, 2013, pp. 212–219.
[41] S. Parsegov, A. Proskurnikov, R. Tempo, and N. Friedkin, “Novel
multidimensional models of opinion dynamics in social networks,”
IEEE Trans. Autom. Control, vol. 62, no. 5, 2017, (publ. online).
[42] N. Friedkin and E. Johnsen, “Social influence networks and opinion change,” in Advances in Group Processes, S. Thye, E. Lawler,
M. Macy, and H. Walker, Eds., 1999, vol. 16, pp. 1–29.
[43] A. Proskurnikov, R. Tempo, M. Cao, and N. Friedkin, “Opinion evolution under time-varying social influence with individual prejudices:
from consensus to disagreement,” in Proc. of IFAC World Congress,
Toulouse, France, 2017.
[44] A. Nedic, A. Ozdaglar, and P. Parrilo, “Constrained consensus and
optimization in multi-agent networks,” IEEE Trans. Autom. Control,
vol. 55, no. 4, pp. 922–938, 2010.
[45] G. Shi and K. Johansson, “Randomized optimal consensus of multiagent systems,” Automatica, vol. 48, pp. 3018–3030, 2012.
[46] P. Lin and W. Ren, “Constrained consensus in unbalanced networks
with communication delays,” IEEE Trans. Autom. Control, vol. 59,
no. 3, pp. 775–781, 2014.
[47] J. Liu, A. Morse, A. Nedić, and T. Başar, “Stability of a distributed
algorithm for solving linear algebraic equations,” in Proc. of IEEE
Conference on Decision and Control (CDC), 2014, pp. 3707–3712.
[48] S. Mou, J. Liu, and A. Morse, “A distributed algorithm for solving
a linear algebraic equation,” IEEE Trans. Autom. Control, vol. 60,
no. 11, pp. 2863–2878, 2015.
[49] K. You, S. Song, and R. Tempo, “A networked parallel algorithm for
solving linear algebraic equations,” in Proc. of IEEE Conf. Decision
and Control, 2016, pp. 1727–1732.

A PPENDIX
P ROOFS OF T HEOREMS 1-3
Although the results of Theorems 1-3 resemble usual
criteria of convergence for consensus protocols (3), their
proofs are based on different techniques, which are inspired
by the analysis of differential inequalities from [26], [27].
Given a solution x(k) ∈ Rn of (2), let j1 (k), . . . , jn (k)
be the permutation of the indices {1, . . . , n}, sorting the
elements of x(k) in the ascending order. In other words,
∆
the numbers yi (k) = xj1 (k) (k) satisfy the inequalities
min xi (k) = y1 (k) ≤ y2 (k) ≤ . . . ≤ yn (k) = max xi (k).
i

i

∆

We also introduce the sets Ji (k) = {j1 (k), . . . , ji (k)} and
∆
Jic (k) = {1, . . . , n} \ Ji (k) (where 1 ≤ i ≤ n). Recall that
Φ(m, k) = (ϕij (ms , ks )) = W (m − 1) . . . W (k) stands for
the evolutionary matrix of the linear equation (3).
We start with the following simple proposition.
Proposition 2: For any p ≥ 0, q > p and j, l = 1, . . . , n
the inequality holds as follows
xl (q) ≤ yn (p) − ϕlj (q, p) (yn (p) − xj (p)) .
In particular, for the case where q = p + 1 one has
xl (p + 1) ≤ yn (p) − wlj (p) (yn (p) − xj (p)) .
(18)
Proof: The proof is immediate from the inequalities
xl (q) ≤

n
X

0) for some j ∈ J and l ∈ J c . Let m − 1 stand for the
minimum of such s (that is, m ≥ k + 1). Since wjl (s) =
wlj (s) = 0 for any s = k, . . . , m−2, one has ϕjl (m−1, k) =
ϕlj (m − 1, k) = 0 for any pair j ∈ J, l ∈ J c . Hence
X
xj (m − 1) =
ϕjr (m − 1, k)xr (k) ≤ yi (k).
r∈J

Applying (18) to p = m−1 and j = l ∈ J, one has xj (m) ≤
(1−δ)yn (m−1)+δxj (m−1) ≤ (1−δ)yn (k)+δyi (k). At the
same time, there exist j ∈ J, l ∈ J c such that wlj (m−1) ≥ δ.
In view of (18), xl (m) ≤ (1 − δ)yn (m − 1) + δxj (m −
1) ≤ (1 − δ)yn (k) + δyi (k). This entails (20) since the set
Ji (k) ∪ {l} contains i + 1 elements.
A. Proofs of Theorems 2 and 3
Consider a bounded solution x(k) of (2) and its ordering
y(k). The inequality (2) implies, obviously, that yn (k +
1) ≤ yn (k), and therefore there exists the limit y∗ =
limk→∞ yn (k). Our goal is to show that yj (k) −−−−→ y∗ for
k→∞
any j, provided that the assumptions of either Theorem 2
or Theorem 3 are valid. The proof is via induction on
j = n, n − 1, . . . , 1. For j = n the statement holds. Suppose
that yj (k) → y∗ for j = i + 1, . . . , n; we are now going
to prove that yi (k) → y∗ as k → ∞. Since yi (k) ≤ yn (k),
it suffices to show that lim yi (k) ≥ y∗ . Suppose, on the
k→∞

contrary, that lim yi (k) < y∗ , that is, there exist a sequence
k→∞

ϕls (q, p)xs (p) = ϕlj (q, p)xj (p)+

ks −−−→ ∞ and q > 0, such that yi (ks ) −−−→ y∗ − q.
s→∞
s→∞
As implied by Lemma 2 (respectively, Lemma 3), under
the assumptions of Theorem 2 (respectively, Theorem 3), a
sequence ms > ks and a constant ε > 0 exist such that

s=1

+

X

ϕls (q, p)xs (p)

s6=j

by noticing that xs (p) ≤ yn (p) for any s 6= j.
Lemma 2: Suppose that for some k ≥ 0 and m > k one
has Φ(m, k) ∈ Sε . Then for any i < n one has
yi+1 (m) ≤ (1 − ε)yn (k) + εyi (k).
(19)
Proof: The definition of the set Ji (k) and (2) imply
that xj (m) ≤ (1 − ε)yn (k) + εyi (k) for any j ∈ Ji (k)
since ϕjj (m, k) ≥ ε and xj (k) ≤ yi (k). Since the graph
Gε [Φ(m, k)] is strongly connected, there exist some j ∈
Ji (k) and l ∈ Jic (k) such that ϕlj (m, k) ≥ ε, and thus
xl (m) ≤ (1 − ε)yn (k) + εyi (k) due to (2). This entails (19)
since the set Ji (k) ∪ {l} contains i + 1 elements.
The statement of Lemma 2 retains its validity, replacing
the condition from Theorem 2 by the assumptions of Theorem 3. However, in this situation m = m(k, i) should be
chosen in a different way and depends on both i and k.
Lemma 3: Let Assumptions 1 and 3 hold and the communication be bidirectional wij (k) > 0 ⇐⇒ wji (k) > 0. Then
for all k ≥ 0, i < n there exists m = m(i, k) > k such that
yi+1 (m) ≤ (1 − δ)yn (k) + δyi (k),

(20)

where δ > 0 is the constant from Assumption 1.
Proof: For a fixed k ≥ 0 and i < n, we denote for
brevity J = Ji (k) and J c = Jic (k). Assumption 3 implies
the existence of s ≥ k such that wjl (s) > 0 (and thus wlj >

yi+1 (ms ) ≤ εyi (ks ) + (1 − ε)yn (ks ).
Passing to the limit as s → ∞, one arrives at
y∗ = lim yi+1 (ms ) ≤ (1 − ε)y∗ + ε(y∗ − q) = y∗ − εq,
s→∞

which is a contradiction. Thus yi (k) → y∗ as k → ∞, which
proves the induction step. Therefore, the solution converges
to a consensus equilibrium x(k) −−−−→ y∗ 1n .

k→∞

B. Proof of Theorem 1
The sufficiency part is immediate from Remark 2 and
Theorem 2. Indeed, if the graph G[W ] is strongly connected
and aperiodic, then W d is a strictly positive matrix for some
d, so the condition of Theorem 2 holds: Φ(k + d, k) =
W d ∈ Sε for some ε > 0. Hence the inequality (2) is
consensus dichotomic. If the graph G[W ] is constituted by
s > 1 isolated and aperiodic strongly connected components,
then (2) is dichotomic, reducing to s independent consensus
dichotomic inequalities of lower dimensions.
To prove necessity, consider a dichotomic inequality (2)
with W (k) ≡ W and let wij > 0, that is, i is connected to
j in the graph G[W ]. Let the set J include node j and all
nodes that are reachable from j by walks. We are going to

show that i ∈ J, that is,
component. Suppose, on

k

(−1) ,
xr (k) = M,


−1,

i and j belong to the same strong
the contrary, that i 6∈ J and let
r = i,
r ∈ J,
r 6∈ J ∪ {i},

r = 1, . . . , n.

Here M is chosen sufficiently large so that (M + 1)wij > 2.
It can be easily shown that the vector x(k) is a solution to (2).
Indeed, for any r ∈ J and q 6∈ J one obviously has wrq = 0
(otherwise, q would
from j via l). Therefore,
Pn be reachable P
M = xr (k) = q=1 wrq xq (k) = q∈J wrq
Pxnq (k). For any
r 6∈ J ∪{i} we have xr (k) = minq xq (k) ≤ q=1 wrq xq (k).
Finally, xi (k) ≤ 1 ≤ P
M wij − (1 − wijP
) = M wij −
P
n
q6=j wiq ≤ wij xj (k)+
q6=j wiq xq (k) =
q=1 wiq xq (k).
Since x(k) is bounded yet does not converge, one arrives at
the contradiction with the assumption of dichotomy.
Hence for the dichotomy it is necessary that any arc
connects nodes from the same strong components, whereas
two different components have no arcs between them. Notice
that the dichotomy (respectively, consensus dichotomy) of
the inequality (2) implies that any solution of the equation (3) converges to an equilibrium (respectively, to a
consensus equilibrium). Applying the standard convergence
and consensus criteria for the static consensus protocol (3)
(see e.g. [11]), one shows that dichotomy is possible only
when all strong components of G[W ] are aperiodic, whereas
consensus dichotomy implies that the graph is strongly
connected and aperiodic, which ends the proof.

