Data Rate for Distributed Consensus of Multi-agent
Systems with High Order Oscillator Dynamics
Zhirong Qiu1 , Lihua Xie†,1 , and Yiguang Hong2

arXiv:1609.09206v1 [cs.SY] 29 Sep 2016

Abstract
Distributed consensus with data rate constraint is an important research topic of multi-agent systems. Some results have been
obtained for consensus of multi-agent systems with integrator dynamics, but it remains challenging for general high-order systems,
especially in the presence of unmeasurable states. In this paper, we study the quantized consensus problem for a special kind of
high-order systems and investigate the corresponding data rate required for achieving consensus. The state matrix of each agent is
a 2m-th order real Jordan block admitting m identical pairs of conjugate poles on the unit circle; each agent has a single input,
and only the first state variable can be measured. The case of harmonic oscillators corresponding to m = 1 is first investigated
under a directed communication topology which contains a spanning tree, while the general case of m ≥ 2 is considered for a
connected and undirected network. In both cases it is concluded that the sufficient number of communication bits to guarantee
the consensus at an exponential convergence rate is an integer between m and 2m, depending on the location of the poles.

I. I NTRODUCTION
Distributed consensus is a basic problem in distributed control of multi-agent systems, which aims to reach an interested
common value of the states for a team of agents or subsystems by exchanging information with their neighbors. A variety
of consensus protocols have been proposed for different kinds of applications; see the survey papers [2], [3], [4] and the
reference therein. Nonetheless, to apply the consensus protocol in a digital network with limited bandwidth, it is necessary to
introduce quantization and devise the corresponding encoding-decoding scheme. With static uniform quantization, quantized
consensus was first studied in [5] to achieve the approximate average consensus for integer-valued agents by applying gossip
algorithms. For a large class of averaging algorithms of real-valued agents, [6] established the bounds of the steady-state error
and the convergence times, as well as their dependence on the number of quantization levels. Logarithmic quantizers with
infinite quantization levels were adopted in [7] to guarantee the asymptotic average consensus. To achieve the asymptotic
average consensus with finite quantization levels, a static finite-level uniform quantizer with a dynamic encoding scheme was
proposed in [8], and used to shown that an exponentially fast consensus can be ensured by finite-level quantizers for multi-agent
systems with general linear dynamics, whether the state is fully measurable [9], or the state is only partially measurable and
yet detectable [10]. However, the lower bound of sufficient data rate for the consensus obtained in these works are overly
conservative, and it is more appealing to achieve the consensus with fewer bits of information exchange from the perspective
of reducing communication load.
Some works have been devoted to exploring the sufficient data rate to guarantee the consensus of multi-agent systems with
integrator dynamics, and single-integrator systems receive the most attention. With a presumed bound of the initial state of
each agent, Li et. al. [8] showed that the average consensus can be achieved by 1 bit of information exchange for a fixed and
undirected network, which was further extended to the case when the network is balanced and contains a spanning tree [11]. In
an undirected network where the duration of link failure is bounded, 5-level quantizers suffices for the consensus [8], which also
holds when the network is periodically strongly connected [12]. With a novel update protocol carefully screening the quantized
message, the presumed bound of initial values was shown to be unnecessary in [13] and it was concluded that ternary messages
are sufficient for the average consensus under a periodically connected network. Then, for double-integrator systems with only
position being measurable, [14] concluded that 2 bits of communications suffice for the consensus. By employing a totally
different technique based on matrix perturbation, n bits were found to be sufficient to achieve the consensus of multi-agent
systems with n-th integrator agent dynamics in [15]. Still, it is unclear about the sufficient data rate to guarantee the consensus
for general high-order systems, especially when the state variables are only partially measured.
In this paper, we explore the data rate problem in achieving quantized consensus of another kind of discrete-time high-order
critical systems as a complement of integrator systems. The dynamics of each agent is described by a 2m-th order real Jordan
block admitting m identical pairs of conjugate poles on the unit circle with single input, and only the first state variable
can be measured. We design the encoding-decoding scheme on the basis of the constructability of the state variables of each
*This work is partially supported by National Research Foundation of Singapore under grant NRF-CRP8-2011-03 and NNSF of China under Grant 61174071.
The work in this paper has been partially presented in [1].
† Author for correspondence.
1 Z. Qiu and L. Xie are with School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798. Email:

qiuzhr@gmail.com; elhxie@ntu.edu.sg
2 Y.

Hong is with the Key Laboratory of Systems and Control, Institute of Systems Science, Chinese Academy of Sciences, Beijing 100190, China. Email:

yghong@iss.ac.cn

individual system: at each time instant the quantizer will produce a signal to make an estimate for the current measurable
state, which is combined with the previous 2m − 1 estimates of the measurable state to obtain the estimate of the current full
state. The same quantized signal will also be sent to neighbor agents to generate the identical estimate of state. The control
input is constructed in terms of the estimate of its own state, as well as those of its neighbor agents. For harmonic oscillators
(m = 1), it is shown that 2 bits of communications suffice to guarantee the exponentially fast consensus for a directed network
containing a spanning tree. For higher-order case of m ≥ 2, the exponentially fast consensus can be achieved with at most
2m bits under an undirected network, provided that the undirected communication topology is connected. The exact number
of bits for achieving consensus in both the cases is an integer between m and 2m, depending on the frequency of oscillators
or the location of poles on the unit circle.
Although the analysis of consensus and data rate in this paper employs similar perturbation techniques as in [15], the problem
posed here is much different, and it is much more challenging to obtain an explicit data rate required for consensus in the
oscillator case (corresponding to complex eigenvalues). In contrast to [15] where the special structure of integrator dynamics
enables a direct connection between the encoder’s past outputs and those at the present moment which leads to a convenient
iteration in the encoding scheme, a similar iteration is no longer available for the estimation of state variables in the case of
oscillator dynamics. As such, a new observer-based encoding scheme is devised. However, such an encoding scheme leads
to the involvement of control inputs into the estimation error, which makes the consensus analysis challenging. Furthermore,
the expression of data rate for the oscillator case requires calculating a linear combination of some rows of a matrix which
is a multiplication of the (2m − 1)-th power of the system matrix and the inverse of the observability matrix, and is hard to
obtain by a direct computation. To overcome this difficulty, we transform the linear combination into a set of linear equations
and employ techniques of combinatorics. It is shown that a data rate between m and 2m, depending on the frequencies of the
oscillations, suffices to achieve the consensus. It is worthy noting that the result not only provides a sufficient data rate for
consensus of the systems under consideration but also reveals an interesting connection between the data rate and the system
dynamics. We believe it will shed some further light on the data rate problem for multi-agent systems of general dynamics.
The rest of the paper is organized as follows. Some preliminaries about graph theory and the problem formulation are
presented in Section II. Then the data rate problem for distributed consensus of the coupled harmonic oscillators is conducted
in Section III, which is followed by the general case of m ≥ 2 in Section IV. For illustration, a numeric example is given in
Section V. Some concluding remarks are drawn in Section VI. The proofs of the main lemmas can be found in the Appendix.
Some notations listed below will be used throughout this paper. For a matrix U , U (i, j) and U (i, ·) respectively denote its
(i, j)-th entry and i-th row; U T is its transpose, and ||U || is its infinity-norm. N+ is the set of positive integers, and ⌈a⌉, ⌊a⌋
respectively denote the smallest integer not less than a, and the largest integer not greater than a. C(n, k) is the number of
k-combinations from a given set of n√ elements. 1N is the N dimensional vector with every component being 1, and Im is
the identity matrix of order m.  = −1 is the unit imaginary number. Jλ,n denotes the n dimensional Jordan block with
eigenvalue λ. A ⊗ B denotes the Kronecker product between matrices A and B. h·, ·i denotes the standard inner product in
Euclidean spaces.
II. P ROBLEM F ORMULATION
Consider a multi-agent system in the following form:
 i
x (t + 1) = Axi (t) + bui (t),
yi (t) = xi1 (t),
T

where xi (t) = [ xi1 (t), xi2 (t), . . . , xi,2m
 (t)] ∈
Q I2


Q
agent i, respectively. Moreover, A = 



(1)

R2m , yi (t),
 ui (t) ∈ R, i = 1, . . . , N represent the state, output and input of

..



 ∈ R2m×2m is a real Jordan form consisting of m pairs of conjugate

..
. I2 
Q

cos θ
sin θ
T
eigenvalues cos θ +  sin θ with sin θ 6= 0 and Q =
; b = [ 0, . . . , 0, 1] ∈ R2m .
− sin θ cos θ
Suppose that the total number of agents is N . Assumed to be error-free, the digital communication channels between agents
are modeled as edges of a directed or undirected graph. A graph G consists of a node set V = {1, . . . , N } and an edge
set E = {(i, v) : i, v ∈ V} where self-loop (i, i) is excluded. An edge (i, v) of a directed graph implies that node v can
receive information from node i, but not necessarily vice versa. In contrast, for an undirected graph, (i, v) ∈ E means mutual
communications between i and v. For node i, Ni+ = {v : (v, i) ∈ E} and Ni− = {v : (i, v) ∈ E} respectively denote its inneighbors and out-neighbors, which coincide if G is undirected, and will be denoted as Ni . A directed path (i1 , i2 ), (i2 , i3 ), . . .
is formed by a sequence of edges. For a directed graph G, if there exists a directed path connecting all the nodes, then G is
said to contain a spanning tree, which is equivalent to the case of being connected when G is undirected.
Usually, a nonnegetive matrix G = [giv ] ∈ RN ×N is assigned to the weighted graph G, where giv > 0 if and only if
(v, i) ∈ E, and giv = gvi is further required for an undirected graph. The connectivity of G can be examined from an algebraic
.

PN
G
G
point of view, by introducing the Laplacian matrix L = DG − G, where DG = diag(dG
1 , . . . , dN ) and di =
v=1 giv . By
L1N = 0, L has at least one zero eigenvalue, with the other non-zero eigenvalues on the right half plane. L has only one zero
eigenvalue √
if and only if G contains a spanning tree [16]. We can always find a nonsingular matrix UL = [φ1 φ2 . . . φN ] with
φ1 = 1N / N and ||φi || = 1, such that UL−1 LUL = diag{J0,N1 , Jλ2 ,N2 , . . . , Jλl ,Nl } , LJ , where 0 ≤ Reλ2 ≤ · · · ≤ Reλl
with λi being an eigenvalue of L. In particular, we denote ψi = UL−1 (i, ·)T . Moreover, LJ = diag{0, λ2 , . . . , λN } with
0 ≤ λ2 ≤ · · · ≤ λN and ψi = φTi if G is undirected.
We adopt the following finite-level uniform quantizer qt (·) in the encoding scheme, where M (t) ∈ N+ :

0,
− 21 < y < 21 ;


 j,
2j−1
≤ y < 2j+1
2
2 , j = 1, . . . , M (t) − 1;
(2)
qt (y) =
2M(t)−1

;
M (t),
y≥

2

−qt (−y), y ≤ − 12 .

Remark 2.1: Clearly, the total number of quantization levels of qt (·) is 2M (t) + 1. Demanding that agent i does not send
out any signal when the output is zero, it is enough to use ⌈log2 (2M (t))⌉ bits to represent all the signals.
The problem of distributed quantized consensus is solved if we can design a distributed control protocol based on the outputs
of the encoding-decoding scheme, making the states of different agents reach the agreement asymptotically:
lim [xi (t) − xj (t)] = 0,

t→∞

i, j = 1, 2, . . . , N.

(3)

III. H ARMONIC O SCILLATOR C ASE
In this section, we will start with the harmonic oscillator case as an example to investigate how many bits of information
exchange are enough to achieve consensus exponentially fast with quantized neighbor-based control. We separate it from
higher-order cases due to its speciality and simplicity: the solution of this basic case not only provides a result under a directed
communication topology, but also serves to facilitate the understanding of higher-order cases. Some relevant remarks will be
included in the next section, as a comparison
between second-order
and higher-order cases, or a summary of general cases.


cos θ sin θ
Note that now the system matrix A =
.
− sin θ cos θ
A. Encoding-decoding scheme and distributed control law
An encoding-decoding scheme has a paramount importance in the quantized consensus, which should not only provide
estimates for all the states from the partially measurable states, but also help reduce the data rate. Accordingly, the encoder
should serve as an observer based on iterations. To be specific, inspired by the constructability in the sense that the present
state of the system can be recovered from the present and past outputs and inputs, namely

 

 

xi1 (t)
0
1
xi1 (t − 1)
0
=
+
,
(4)
xi2 (t)
− csc θ cot θ
xi1 (t)
ui (t − 1)
we propose the following encoder ϕi for agent i:

i (1)
), x̂i1 (1) = p(0)si (1);
si (1) = qt ( yp(0)




y
(2)
i


si (2) = qt ( p(1)
), x̂i1 (2) = p(1)si (2),



x̂i2 (2) = cot θx̂i1 (2) − csc θx̂i1 (1);
yi (t)−[cos θ x̂i1 (t−1)+sin θ x̂i2 (t−1)]


),
 si (t) = qt (
p(t−1)



x̂
(t)
=
cos
θx̂
(t
−
1)
+
sin
θx̂
(t
−
1)
+
p(t − 1)si (t),

i1
i2

 i1
x̂i2 (t) = cot θx̂i1 (t) − csc θx̂i1 (t − 1), t ≥ 2,

where p(t) = p0 γ t , 0 < γ < 1 is a decaying scaling function.
After si (t) is received by one of the i-th agent’s out-neighbors, say v ∈ Ni− , a decoder ϕiv will be activated:

x̂iv1 (1) = p(0)si (1);


 x̂ (2) = p(1)s (2), x̂ (2) = cot θx̂ (2) − csc θx̂ (1);
iv1
i
iv2
iv1
iv1
x̂
(t)
=
cos
θx̂
(t
−
1)
+
sin
θx̂
(t
−
1)
+
p(t
−
1)si (t),

iv1
iv1
iv2


x̂iv2 (t) = cot θx̂iv1 (t) − csc θx̂iv1 (t − 1), t ≥ 2.

(5)

(6)

Remark 3.1: As in [15], a scaled “prediction error” is quantized to generate the signal si (t), in an effort to reduce the number
of quantization levels. si (t) is then used to construct the estimate x̂i1 (t) of the first component xi1 (t), which is combined with
x̂i1 (t − 1) to obtain the estimate x̂i2 (t) for xi2 (t). Denote ∆i (t) = si (t) − di (t) as the quantization error, where
( y (t)
i
p(t−1) , t = 1, 2;
(7)
di (t) =
yi (t)−[cos θ x̂i1 (t−1)+sin θ x̂i2 (t−1)]
, t > 2,
p(t−1)

and eij (t) = x̂ij (t) − xij (t) as the estimation for xij (t), j = 1, 2. Then comparing (4), (5) and (6) we have

ei1 (t) = x̂i1 (t) − xi1 (t) = p(t − 1)∆i (t), t ≥ 1;
ei2 (t) = x̂i2 (t) − xi2 (t) = cot θei1 (t) − csc θei1 (t − 1) − ui (t − 1), t ≥ 2.

(8)

Evidently the estimation error is related with control inputs in addition to quantization errors, which may impair the consensus.
But as shown in the consensus analysis below, the influence of the control inputs can be ignored by making the control gains
arbitrarily small.
Based on the outputs of the encoding-decoding scheme, the distributed control law of agent i is given by
(
0, t = 0, 1;
P
P2
ui (t) =
(9)
j=1 kj
v∈N + giv [x̂vij (t) − x̂ij (t)], t ≥ 2.
i

B. Consensus Analysis and Data Rate

Some notations are defined as follows:
u(t) = [u1 (t), . . . , uN (t)]T ,
∆(t) = [∆1 (t), . . . , ∆N (t)]T ,
d(t) = [d1 (t), . . . , dN (t)]T ,
xj (t) = [x1j (t), . . . , xN j (t)]T ,
δj (t) = (IN − φ1 ψ1T )xj (t) = [δ1j (t), . . . , δN j (t)],
ej (t) = [e1j (t), . . . , eN j (t)]T .

(10)

We adopt the following two assumptions in the subsequent analysis.
Assumption 3.1: The communication graph G contains a spanning tree.
Assumption 3.2: There exist known positive constants C ∗ and Cδ∗ such that maxj=1,2 ||xj (0)|| ≤ C ∗ and maxj=1,2 ||δj (0)|| ≤
Cδ∗ .
Remark 3.2: Assumption 3.1 is a standard assumption, under which we have 0 < Reλ2 ≤ · · · ≤ Reλl , with 0 as the simple
eigenvalue. Assumption 3.2 enables us to make the quantizer qt (·) unsaturated at initial steps.
The following lemma is critical
in theconsensus analysis.

0 0
and Ai = A − λi K with Reλi > 0. Let kj = cj ε, j = 1, 2 and ε > 0. Then the
Lemma 3.1: Denote K =
k1 k2
following results hold with sufficiently small ε:
1). The spectral radius ρi of Ai is less than 1 if c2 cos θ − c1 sin θ > 0 and c1 cos θ + c2 sin θ = 0. Moreover, ρi =
1 − 21 (Reλi )(c2 cos θ − c1 sin θ)ε + o(ε).
2). Take c1 , c2 as in 1). For any vector ξ ∈ R2 , the entries of Asi ξ, which are denoted as ξs1 and ξs2 , satisfy that |ξsj | ≤ 5/2ρsi
for j = 1, 2.

 θ




1 −
e
1 1
1
−1
−1
P
with
P
=
, we have
Proof: 1). Noticing that A = P
and
P
=
2
1 
 −
e−θ


µ − eθ
µI − A = P
P −1
µ − e−θ


(11)
(µ − eθ ) + (µ − e−θ ) −(µ − eθ ) + (µ − e−θ )
= 12
.
(µ − eθ ) − (µ − e−θ )
(µ − eθ ) + (µ − e−θ )

Consequently the characteristic polynomial of Ai can be obtained as

λi
ε[(c2 + c1 )(µ − eθ ) + (c2 − c1 )(µ − e−θ )].
2
By perturbation theory [17] it is readily seen that the two perturbed roots of (12) are given by
χi (µ) = (µ − eθ )(µ − e−θ ) +

µi1 = eθ + µi11 ε + o(ε), µi2 = e−θ + µi21 ε + o(ε).

(12)

(13)

Substituting µ = µi1 into χi (µ) = 0 and comparing the coefficient of ε yield
1
µi11 (2 sin θ) + λi (c2 − c1 )(2 sin θ) = 0
2
and µi11 = − 12 λi (c2 − c1 ) follows immediately. Direct computation shows that |µi1 |2 = 1 + 2Re(µi11 e−θ )ε + o(ε), where
1
Re(µi11 e−θ ) = − [ai (c2 cos θ − c1 sin θ) + bi (c1 cos θ + c2 sin θ)]
2

if we let λi = ai + bi . Clearly |µi1 | = 1 − 12 (Reλi )(c2 cos θ − c1 sin θ)ε + o(ε) when c1 cos θ + c2 sin θ = 0. Similarly we
can show µi21 = − 21 λi (c2 + c1 ) and |µi2 | = 1 − 12 Reλi (c2 cos θ − c1 sin θ)ε + o(ε), which implies the conclusion.

2). Here we need to compute the Jordan decomposition of Ai . The eigenvector corresponding to the eigenvalue µi1 is
given by wi1 = wi10 + wi11 ε + o(ε). Substituting it into the equation Ai wi1 = µi1 wi1 and comparing the coefficients of
constant term, we have Awi10 = eθ wi10 . With the normalization condition v T wi1 = 1 where v T = 21 (1 − ), wi10 = (1 )T .
Similarly, the eigenvector corresponding
to the eigenvalue µi2 is given by wi2 = wi20 + wi21 ε + o(ε) with wi20 = (1 −

1 + O(ε) 1 + O(ε)
− + O(ε) −1 + O(ε)
T
) . Letting Ri = (wi1 wi2 ) =
, it is clear that Ri−1 = det1Ri
=

+
O(ε)
−
+
O(ε)
−
 + O(ε) 1 + O(ε)



µi1
1 + O(ε) − + O(ε)
1
Ri−1 .
. The result follows directly by noticing that Ai = Ri
2
µi2
1 + O(ε)  + O(ε)
Remark 3.3: Denote ρ = max ρi and let h be a constant in (0, Reλ2 ]. Taking c1 = − sin θ/h and c2 = cos θ/h, we have
i=2,...,l

ρ ≤ 1 − ε + o(ε) < 1 − ε/2 with sufficiently small ε.
We also need to define some constants as follows:

1
C0 = 12 |c1 | + 23 |c2 csc θ| = 2h
(| sin θ| + 3| cot θ|),
Λ = maxi=2,...,l |λi |,
C(1) = ||UL−1 || + 2C0 Λ||UL ||,
C(k) = ||UL−1 || + 2C0 (Λ + 1)||UL || + 10(|c1 | + |c2 |)C(k − 1), k ≥ 2,
C̄ = 5(|c1 | + |c2 |)C(Nmax ) + C0 ||UL ||,

(14)

where Nmax = maxi=2,...,l Nl .
Lemma 3.2: Let γ = 1 − ε/4. Then we can choose sufficiently small ε to satisfy the following inequalities:
(Λ + 1)C̄ε ≤ 12 γ| csc θ|||UL ||;
+ γ1 ) ≤ 2| cos θ| + 1 + 21 ;
(N − 1)C̄(Λ + 1)ε ≤ 14 | csc θ|γ 3 .

1
γ (2| cos θ|

(15a)
(15b)
(15c)

Theorem 3.1: Take cj ’s as in Remark 3.3 and let γ = 1 − ε/4. Select sufficiently small ε to satisfy Lemmas 3.1 and 3.2
with ρ < 1 − ε/2. Then under Assumptions 3.1 and 3.2, consensus can be achieved at a convergence rate of O(γ t ) provided
4
C ∗ , Cδ∗ } and M (t) satisfies
that g0 ≥ max{ 3γ

M (t) ≥ 1, t = 1, 2;
(16)
M (t) ≥ | cos θ| + 1/2, t = 2m + 1, . . . .
Therefore, the number of bits used to achieve the consensus is ⌈log2 2⌈| cos θ| + 1/2⌉⌉.
Proof: 1) Preparation. The closed-loop system of disagreement vectors can be established as

 


 
δ1 (t)
0
δ1 (t + 1)
cos θIN
sin θIN
+
=
δ2 (t)
− sin θIN cos θIN
u(t)
δ2 (t + 1)
with
u(t) =



0, t = 0, 1;
P2
− j=1 kj L(δj (t) + ej (t)), t ≥ 2,

(17)

by noticing (9) and L = L(IN − φ1 ψ1T ). Letting δ̃j (t) = UL−1 δj (t) = [δ̃1j (t), . . . , δ̃N,j (t)]T , we obtain
 

 


0
cos θIN
sin θIN
δ̃1 (t)
δ̃1 (t + 1)
+
,
=
η(t)
− sin θIN − k1 LJ cos θIN − k2 LJ
δ̃2 (t)
δ̃2 (t + 1)
where η(t) = −LJ UL−1 (k1 e1 (t) + k2 e2 (t)). Denote δ̃ i (t) = [δ̃i1 (t), δ̃i2 (t)]T for i = 1, . . . , N . Clearly δ̃ 1 (t) ≡ 0 due to that
δ̃1j (t) = ψ1T (IN − φ1 ψ1T )xj (t) = 0 for j = 1, 2. Without loss of generality we assume that N2 = 2 (the Jordan block with
respect to λ2 is two-dimensional) and consequently δ̃ 2 (t) and δ̃ 3 (t) are coupled in the following way:
δ̃ i (t + 1) = Aδ̃ i (t), t = 0, 1, i = 2, 3;
δ̃ 2 (t + 1) = A2 δ̃ 2 (t) − K δ̃ 3 (t) − η2 (t),
δ̃ 3 (t + 1) = A2 δ̃ 3 (t) − η3 (t), t ≥ 2,

(18)

where A2 and K have been defined in Lemma 3.1 and η2 (t) = [0, (λ2 ψ2T +ψ3T )(k1 e1 (t)+k2 e2 (t))]T , η3 (t) = [0, λ2 ψ3T (k1 e1 (t)+
k2 e2 (t))]T .
2) Estimation error and exponential convergence. Remember that e2 (t) = cot θe1 (t) − csc θe1 (t − 1) − u(t − 1) is dependent
on the control input by (8), we have to first make an estimate for u(t) before establishing the consensus result. Below we shall
show |ψiT u(t)| ≤ ε(Λ + 1)C̄p0 γ t−2 , t ≥ 2 for i ≥ 2 by induction.

With the choice of p0 and γ it is easy to see |si (t)| ≤ 3/2 when t ≤ 2 by noticing |yi (t)| ≤ 2C ∗ , hence we obtain
max ||∆(t)|| ≤ 1/2 if M (1), M (2) ≥ 1. For i = 2, we have ψ2T L = λ2 ψ2T + ψ3T and as a result

t=1,2

P2
|ψ2T u(2)| = |ψ2T L j=1 kj (δj (2) + ej (2))|

≤ ε(Λ + 1)||UL || |c1 |(2||δ(0)|| + p(1)||∆(2)||)

+ |c2 |(2||δ(0)|| + | cot θ|p(1)||∆(2)|| + | csc θ|p(0)||∆(1)||)
≤ ε(Λ + 1)||UL ||(|c1 | + |c2 |)(2||δ(0)|| + | csc θ|p0 )
≤ ε(Λ + 1)||UL ||(|c1 | + |c2 |)(2 + | csc θ|)p0
≤ ε(Λ + 1)C̄p0 ,
which also holds for |ψiT u(2)| for i > 2.
Now assume that
|ψiT u(t)| ≤ε(Λ + 1)C̄p0 γ t−2 , t ≥ 2;
||∆(τ )|| ≤ 1/2(⇒ |ei1 (τ )| ≤ 21 p0 γ τ −1 ), 1 ≤ τ ≤ t.

(19)

Then by combining (19) and (15a) it follows that
||η3 (τ )|| = |λ2 ||ψ3T (k1 e1 (τ ) + k2 e2 (τ ))|
≤ ε|λ2 |p0 γ τ −2 ||UL ||( 12 |c1 | + |c2 || csc θ|) + ε|λ2 |c2 ||ψ3T u(τ − 1)|
≤ ε|λ2 |||UL ||C0 p0 γ τ −2 .

Recalling (18) we get that for t ≥ 2

3
δ̃ 3 (t + 1) = At−1
2 δ̃ (2) −

which produces the following estimate by Lemma 3.1 and (20)

Pt−1

τ =1

(20)

At−1−τ
η3 (τ + 1),
2

3
t−1
||δ̃ 3 (t + 1)|| ≤ 25 (ρt−1
)
2 ||δ̃ (2)|| + 4|λ2 |C0 ||UL ||p0 γ
−1
t−1
≤ 5γ (||UL ||||δ(0)|| + 2|λ2 |C0 ||UL ||p0 )
≤ 5C(1)p0 γ t−1 .

(21)

Similarly, an estimate for ||δ̃2 (t + 1)|| can be found as ||δ̃ 2 (t + 1)|| ≤ 5C(2)p0 γ t−1 , if we notice that ||K δ̃ 3 (τ )|| ≤ 5ε(|c1 | +
|c2 |)C(1)p0 γ τ −2 and ||η2 (τ )|| ≤ ε(|λ2 | + 1)||UL ||C0 p0 γ τ −2 for 2 ≤ τ ≤ t. For any i ≥ 2, by proceeding along the same line
as in the above it is concluded that
||δ̃ i (t + 1)|| ≤ 5C(Nmax )p0 γ t−1 .
(22)
P
2
3) Data rate. Now we are able to discuss the estimation for |ψiT u(t+1)|, which is bounded by the sum of | j=1 kj ψiT Lδj (t+
P2
1)| and | j=1 kj ψiT Lej (t + 1)|. For the first term, by (22) it is readily seen that
P2
P2
| j=1 kj ψiT Lδj (t + 1)| ≤ | j=1 kj ψiT UL LJ δ̃j (t + 1)|
(23)
≤ 5ε(|c1 | + |c2 |)C(Nmax )p0 γ t−1 ;
while the second term is essentially related with ej (t + 1), or more exactly ∆(t + 1). By (7) and (8) we have
d(t + 1) =
=

1
p(t) (− cos θe1 (t) − sin θe2 (t))
1
−2 cos θ
∆(t) + γ12 ∆(t − 1) + p(t)
γ

sin θu(t − 1),

(24)

which is obviously dependent on the previous quantization errors ∆(t) and ∆(t − 1), as well as the previous control input
u(t − 1). Hence with the induction assumption (19) the quantizer can be made unsaturated with sufficiently many bits at time
t + 1, and ||∆(t + 1)|| ≤ 1/2 follows directly. Consequently
P2
| j=1 kj ψiT Lej (t + 1)| ≤ ε|λ2 |||UL ||C0 p0 γ t−1
(25)

as in (20). The induction is then established by combining (23). Moreover, by (22) the consensus can be achieved at a
convergence rate of O(γ t ).
Below we are to calculate the number of required quantization levels at each time step. The situation when t ≤ 2 has been
discussed. When t > 2, from (24) we can see that
||d(t)|| ≤

≤
≤

by noticing (15b), (15c) and u(t) =

PN

i=2

| sin θ|
1
1
2γ (2| cos θ| + γ ) + p(t−1) ||u(t − 2)||
| sin θ|
1
1
2 (2| cos θ| + 1) + 4 + γ 3 (N − 1)(Λ
1
1
2 (2| cos θ| + 1) + 2

+ 1)C̄

φi ψiT u(t) (ψ1T u(t) = 0). In summary, the proof is completed.

Remark 3.4: For the coupling system shown in (18), we divide it into two subsystems with disturbance. Each subsystem
can be stabilized as long as the disturbance decays exponentially at a speed slower than ρ2 , i.e. ||η3 (t)|| ∼ O(γ t ) and
||K δ̃ 3 (t) + η2 (t)|| ∼ O(γ t ), with ρ2 < γ < 1. The interference of u(t) in the estimation error e(t) can be ignored, as long
as ||u(t)|| ∼ O(εα )p0 γ t with α > 0, yielding that ||η3 (t)|| ∼ O(ε)p0 γ t , and then ||δ̃ 3 (t)|| ∼ O(γ t ) follows. As a result,
||K δ̃ 3 (t)|| ∼ O(ε)γ t and ||δ̃ 3 (t)|| ∼ O(γ t ) follows by combining ||η3 (t)|| ∼ O(ε)p0 γ t . Such a reasoning still applies when
(18) involves more than two subsystems. Finally we show that ||u(t)|| ∼ O(ε)p0 γ t , and by (24) we conclude that the control
input does not consume extra bits in exchanging the information when the control gains are sufficiently small.
IV. H IGHER - ORDER

CASES

In this section, we will conduct the same task as in the last section for general higher-order cases. The analysis actually
proceeds along a similar line, but the assignment of control gains to achieve consensus is much more challenging, and we
have to resort to combinatorial identities for an explicit data rate. As before, we first provide an encoding-decoding scheme
for all the agents and devise a control protocol in terms of the outputs of the scheme. Then we present some lemmas, which
will play a crucial role in the convergence analysis and the derivation of the data rate in the final part.
A. Encoding-decoding scheme and distributed control law
As pointed out in the last section, the construction of the encoding scheme should follow two principles: firstly, the encoder
is able to estimate other state variables given that only the first component is measurable; secondly, the estimation should be
based on iterations in an effort to reduce quantization levels. Such an idea can be stated more clearly as follows. At each time
step, the scaled difference between the output yi (t) and its estimate is quantized to obtain a signal si (t). Based on si (t) we
construct an estimate x̂i1 (t) of the first component xi1 (t), and combine previous estimates x̂i1 (t − 1) through x̂i1 (t − 2m + 1)
to obtain estimates of the other components xi2 (t) through
 xi,2m (t). 
I2m (1, ·)


A(1, ·)


To be detailed, denote the observability matrix O = 
,
..


.
2m−1
A
(1, ·)
x̄i (t) = [xi1 (t − 2m + 1), xi1 (t − 2m + 2), . . . , xi1 (t)]T ,
bn (θ) = [0, . . . , 0, A(1, 2m), . . . , An−1 (1, 2m)]T ∈ R2m .

We have
x̄i (t) = Oxi (t − 2m + 1) +
if we notice by (1) that
xi (t − 2m + k) = Ak−1 xi (t − 2m + 1) +
k = 1, . . . , 2m.

2m−1
X
n=1

k−2
P

n=0

As a result,
xi (t − 2m + 1) = O−1 [x̄i (t) −
and

bn (θ)ui (t − n)

Ak−2−n bui (t − 2m + 1 + n),

2m−1
X
n=1

bn (θ)ui (t − n)]

P2m−2
xi (t) = A2m−1 xi (t − 2m + 1) + j=0 A2m−2−j bui (t − 2m + 1 + j)
P2m−1
= S x̄i (t) + j=1
b̃j (θ)ui (t − j),

(26)

(27)

(28)

(29)

where S = A2m−1 O−1 (the existence of O−1 can be easily verified by PBH test [18] if sin θ 6= 0) and b̃n (θ) = −Sbn (θ) +
An−1 (·, 2m). Inspired by (29), the encoding scheme for agent i is implemented below:
for t ≤ 2m,

yi (t)
), x̂i1 (t) = p(t − 1)si (t);
si (t) = qt ( p(t−1)





  x̂ (2m) 
x̂i1 (1)
i2
(30)




..
..

 = Sm 
;
 
.
.


x̂i,2m (2m)
x̂i1 (2m)

for t > 2m,


θ x̂i2 (t−1)+x̂i3 (t−1)]
),
si (t) = qt ( yi (t)−[cos θx̂i1 (t−1)+sin

p(t−1)




x̂
(t)
=
cos
θx̂
(t
−
1)
+
sin
θx̂
(t
−
1)
+
x̂
(t
−
1) + p(t − 1)si (t),
i1
i1
i2
i3
 



x̂i1 (t − 2m + 1)
x̂i2 (t)




..
..

 
,
 = Sm 


.
.


x̂i1 (t)
x̂i,2m (t)

(31)

where Sm = S(2 : 2m, ·) is a submatrix of S obtained by deleting the first row, and p(t) = p0 γ t , 0 < γ < 1 is a decaying
scaling function.
After si (t) is generated, transmitted and received by one of agent i’s out-neighbors, say v ∈ Ni− , a decoder will be activated:
for t ≤ 2m,

x̂



iv1 (t) = p(t − 1)si (t); 


x̂iv1 (1)
x̂iv2 (2m)
(32)




..
..

;

 = Sm 
.
.



x̂iv1 (2m)
x̂iv,2m (2m)
for t > 2m,


x̂iv1 (t) = cosθx̂iv1 (t −


 + x̂iv3 (t − 1) + p(t − 1)si (t);
 1) + sin θx̂iv2 (t − 1)



x̂iv1 (t − 2m + 1)
x̂iv2 (t)




..
..

.
 = Sm 

.
.



x̂iv1 (t)
x̂iv,2m (t)

(33)

Remark 4.1: Comparing (30) with (32), (31) with (33), it is clear that x̂ivj (t) ≡ x̂ij (t), j = 1, . . . , 2m, for v ∈ Ni− , i =
1, . . . , N . Denote eij (t) = x̂ij (t) − xij (t) as the estimation error, ∆i (t) = si (t) − di (t) as the quantization error, where
( y (t)
i
p(t−1) , t = 1, 2, . . . , 2m;
di (t) =
(34)
yi (t)−[cos θ x̂i1 (t−1)+sin θ x̂i2 (t−1)+x̂i3 (t−1)]
, t > 2m.
p(t−1)
Comparing (29) with (31), the estimation errors are given by the following:

− 1)∆i (t), t ≥ 1;
 ei1 (t) = p(t
P2m−1
P2m
eij (t) = n=1 S(j, n)ei1 (t − 2m + n) − n=1 b̃nj (θ)ui (t − n),

t ≥ 2m, j = 2, . . . , 2m,

(35)

where b̃nj is the j-th entry of b̃n .
Remark 4.2: The encoding schemes (5) and (31) proposed in our work is different from those in [10] or [15]. Actually, to
address the general dynamics with unmeasurable states, [10] designed the encoding scheme respectively for the output and
control input, and used Luenberger observer to estimate the unmeasurable states. If we compare with [15], we can also see a
big difference: the special structure of n-th order integrator dynamics enables it to easily “recover” the control input at n steps
earlier, based on which an estimate of the unmeasurable components can be made with time delay, and the encoding scheme
can be designed accordingly. However, in our case it is unlikely to achieve the same task and we resort to the constructability
of the system, namely we estimate the unmeasurable states directly from x̂i1 (t) through x̂i1 (t − 2m + 1). Although such a
method introduces the control input into the estimation errors, it is able to make an estimation without time delay, and hence
avoids the stabilization of a time-delayed closed-loop system in the consensus analysis.
For agent i, the outputs of encoder are x̂i1 (t), . . . , x̂i,2m (t), while the outputs of decoders are x̂vi1 (t), . . . , x̂vi,2m (t) for
v ∈ Ni+ . Based on these outputs, the distributed control law of agent i is proposed as
(
0, t = 0, 1, . . . , 2m − 1;
P
P2m
ui (t) =
(36)
j=1 kj
v∈N + giv [x̂vij (t) − x̂ij (t)], t ≥ 2m.
i

B. Lemmas
The following two lemmas are respectively needed in analyzing consensus and data rate. The first one is to stabilize the
closed-loop system of disagreements, and the second one is used for estimating the magnitude of ui (t) and di (t).
Lemma 4.1: Denote Ai = A − λi K with λi > 0, where K ∈ R2m×2m and its nonzero entries are only at the last row
[k1 , k2 , . . . , k2m−1 , k2m ]. Take

c2j−1 εm−j , j = 1, . . . , m − 1;
k2j−1 =
ε, j = m,
 c2j−1m−j
(37)
c2j ε
, j = 1, . . . , m − 1;
k2j =
c2j ε, j = m.

Then we can find constants c2j−1 and c2j (j = 1, . . . , m) such that, when ε is sufficiently small, the spectral radius ρi of Ai
is less than 1 with distinct eigenvalues. Moreover, denote
Rm =

c2m−5  − c2m−4 −θ
1 1
e ].
+ (c2m−1 sin θ − c2m cos θ), H = Re[
2 2
c2m−3  − c2m−2

(38)

The requirements about c2j−1 ’s and c2j ’s corresponding to different m’s are listed below.
1). m = 2: let c1 = − sin 2θ and c2 = cos 2θ. If R2 < 0, then ρi = 1 + 12 λi R2 ε + o(ε);
2). m ≥ 3: let c2m−3 = − sin 2θ and c2m−2 = cos 2θ. If λi Rm + H < 0 and Re(ϑn1 e−θ ) < 0 with ϑn1 , n = 3, . . . , m
denoting the m − 2 distinct roots of the equation
ϑm−2
(c2m−2 − c2m−3 ) + · · · + ϑ1 (c4 − c3 ) + (c2 − c1 ) = 0,
1

1
2

(39)

−θ

then ρi = 1 + maxn=3,...,n {λi Rm + H, 2Re(ϑn1 e )}ε + o(ε).
Lemma 4.2: Assume that Lemma 4.1 holds. When ε is sufficiently small, for any vector ξ ∈ R2m , the entries of Asi ξ, which
are denoted as ξs,2j−1 and ξs,2j , j = 1, . . . , m, satisfy that

||ξ||Mij ρsi εj−(m−1) , j = 1, 2, . . . , m − 2;
|ξs,2j−1 |, |ξs,2j | ≤
(40)
||ξ||Mij ρsi ε(j−m)/2 , j = m − 1, m,
where

Mij =

















Pm

5
2λi (

Pm

5
2λi (

j−1

Q|ϑn1 |
|ϑk1 −ϑn1 | ),

n=3

3≤k≤m,k6=n

n=3

m−3
Q|ϑn1 |
|ϑk1 −ϑn1 |

3≤k≤m,k6=n

j = 1, . . . , m − 3;

+ 1), j = m − 2;

√3 ,
2λi

j = m − 1;
5/2, j = m.

Remark 4.3: The proofs of the above lemmas can be found in the Appendix. As in [15], the basic idea is to combine
the bifurcation analysis of the roots of characteristic polynomials and the Jordan basis of a perturbed matrix [19]. However,
the situation here is much different. On one hand, the complex conjugate eigenvalues of the original matrix A complicates
the analysis of the perturbed eigenvalues, as seen from the proof of Lemma 4.1. On the other hand, unlike [15] where the
unperturbed matrix admits multiple eigenvalues of 0 and 1, the unperturbed matrix here admits eigenvalues of m identical pairs
of complex conjugate numbers, which allows a less cumbersome calculation of the perturbed Jordan basis, as in the proof of
Lemma 4.2.
Remark 4.4: Assume 0 < λ2 ≤ · · · ≤ λN and let ρ = max ρi , h ∈ (0, λ2 ]. Given c2m−3 = − sin 2θ and c2m−2 = cos 2θ,
i=2,...,N

the other constants c2j−1 and c2j can be selected as follows such that ρ ≤ 1 − ε + o(ε) < 1 − ε/2 holds with sufficiently small
ε:
1). m = 2: select c3 = −(4/h + 1) sin θ, c4 = (4/h + 1) cos θ such that R2 = −2/h < 0;
2). m ≥ 3: first select c2m−4 , c2m−5 , · · · , c1 such that the solutions of (39) are given by ϑn1 = −(n − 2)eθ , n = 3, . . . , m
and H is determined by (38). In fact, direct computation shows that c2m−4 − c2m−5  = 21 (m − 1)(m − 2)e3θ and consequently
H = (m − 1)(m − 2)/2 > 0. Now let c2m−1 = −[(2H + 4)/h + 1] sin θ, c2m = [(2H + 4)/h + 1] cos θ such that
λi Rm + H = H(1 − λi /h) − 2λi /h < −2λi /h ≤ −2.
P
j−1
Qn
With such a selection, Mij = 2λ5 i ( m−2
n=1
|k−n| ), j = 1, . . . , m−3 and Mi,m−2 =
1≤k≤m−2,k6=n

1).
To explicitly express the data rate, another lemma is required.
Lemma 4.3: Denote

Pm−2

5
2λi (

m−3
Qn

n=1

1≤k≤m−2,k6=n

|k−n| +

l(θ) = [l0 (θ), l1 (θ), . . . , l2m−2 (θ), l2m−1 (θ)] = cos θS(1, ·) + sin θS(2, ·) + S(3, ·).
Then
lk (θ) = (−1)k−1

⌊k/2⌋
P
h=0

C(m, k − 2h)C(m − (k − 2h), h)(2 cos θ)k−2h , k = 0, 1, . . . , 2m − 1.

P2m−1
Moreover, k=0 |lk (θ)| = [2(1 + | cos θ|)]m − 1.
The proof of Lemma 4.3 can be found in the Appendix. The idea is simple and direct: by viewing l(θ) as the solution to
an equation, we are left to the verification when l(θ) takes the form in the lemma. Still, the computation is quite complicated
and requires special techniques from combinatorics [20], [21].

C. Convergence analysis and data rate
The notations in (10) will still be used, except that ψ1 is replaced by φ1 . The following assumptions are adopted in the
subsequent analysis.
Assumption 4.1: The communication graph G is undirected and connected.
Assumption 4.2: There exist known positive constants C ∗ and Cδ∗ such that max ||xj (0)|| ≤ C ∗ and max ||δj (0)|| ≤
j=1,...,2m

j=1,...,2m

Cδ∗ .
Remark 4.5: Assumption 4.1 is a standard assumption, under which the eigenvalues of L can be rearranged as 0 = λ1 <
λ2 ≤ · · · ≤ λN . The reason that we only consider the undirected graph will be clarified in Remark 4.7. Assumption 4.2 serves
the same purpose as Assumption 3.2.
We also need the following constants:
b∗ = max{|b̃lj |}, c∗ = max {|cj |},
l,j
1/2

3/2

Λi = max{λi , λi }, C̄ =

1≤j≤2m
√9 [||U −1 ||
L
2

+ 5c∗ mN (||S|| + 2)].

Lemma 4.4: Let γ = 1 − ε/4. Then we can choose sufficiently small ε to satisfy the following inequalities:
P
2c∗ j6=m−1 Mij ε1/2 ≤ Mi,m−1 , i = 2, . . . , N ;
P2m−1
2m
≤ [2(1 + | cos θ|)]m − 1/2;
k=0 |lk (θ)|/γ
∗
(2m − 1)b (N − 1)ΛC̄ε1/2 ≤ 81 γ 4m−1 ,

(41)

(42a)
(42b)
(42c)

where Λ = maxi Λi .
Theorem 4.1: Take kj ’s as in (37), cj ’s as in Remark 4.4 and γ = 1 − ε/4. Select sufficiently small ε to satisfy Lemma 4.4
and ρi < 1 − ε/2 for i = 2, . . . , N . Then under Assumptions 4.1 and 4.2, consensus can be achieved at a convergence rate of
O(γ t ) provided that M (t) satisfies

M (t) ≥ 1, t = 1, . . . , 2m;
(43)
M (t) ≥ 2m−1 (1 + | cos θ|)m − 12 , t = 2m + 1, . . . ,
√
and p0 ≥ ( 2 + 1)2m max{C ∗ , Cδ∗ }.
Therefore, we can use ⌈log2 2⌈2m−1 (1 + | cos θ|)m − 12 ⌉⌉ bits of information exchange to achieve the consensus.
Proof: 1) Preparation. By (36) we have

 0, t = 0, 1, . . . , 2m − 1;
2m
P
(44)
u(t) =
kj L(δj (t) + ej (t)), t ≥ 2m.
 −
j=1

Direct computation shows





 

δ1 (t + 1)
δ1 (t)
0



  .. 
..
..

 = (A ⊗ IN ) 
+ . 
.
.
δ2m (t + 1)
δ2m (t)
u(t)

Let δ̃j (t) = UL−1 δj (t) = [δ̃1j (t), . . . , δ̃N,j (t)]T and δ̃ i (t) = [δ̃i1 (t), . . . , δ̃i,2m (t)]T . Then we obtain δ̃ 1 (t) ≡ 0, and for
i = 2, . . . , N

Aδ̃ i (t),
t = 0, 1 . . . , 2m − 1;
i
(45)
δ̃ (t + 1) =
Ai δ̃ i (t) − ǫi (t), t ≥ 2m,
P2m
where ǫi (t) = [0, . . . , 0, j=1 kj λi φTi ej (t)]T ∈ R2m .
2) Estimation error and exponential convergence. To analyze the influence of u(t) on the error term ej (t), we will show
|φTi u(t)| ≤ Λi C̄p0 γ t−2m ε1/2 , t ≥ 2m by induction.
√
2m ∗
C , hence we
With the choice of p0 and γ it’s easy to see |si (t)| ≤ 3/2 when t ≤ 2m by noticing |y√
i (t)| ≤ ( 2 + 1)
2m ∗
obtain max ||∆(t)|| ≤ 1/2 provided M (t) ≥ 1, t = 1, . . . , 2m. Moreover, ||δj (2m)|| ≤ ( 2 + 1) Cδ . Recalling (36) and
1≤t≤2m

ej (2m) ≤ p0 ||S|| max ||∆(t)|| we have
1≤t≤2m

P2m
(2m) + ej (2m))|
|φTi u(2m)| = |φTi
j=1 kj L(δ
√ j
≤ 2λi mN c∗ ε(( 2 + 1)2m Cδ∗ + p0 ||S||/2)
≤ 2λi mN c∗ ε(1 + ||S||/2)p0
≤ Λi C̄p0 ε1/2

√
by noticing p0 ≥ ( 2 + 1)2m Cδ∗ and ε < 1.

Assume that

we have
and

|φTi u(τ )| ≤ Λi C̄p0 γ τ −2m ε1/2 , 2m ≤ τ ≤ t;
||∆(τ )|| ≤ 12 (⇒ |ei1 (τ )| ≤ 21 p0 γ τ −1 ), 1 ≤ τ ≤ t.



S(j, 1)
e11 (τ − 2m + 1) . . . e11 (τ )

 P2m−1

..
..
.
..
ej (τ ) = 
 − n=1 b̃nj (θ)u(τ − n),

. ..
.
.
S(j, 2m)
eN 1 (τ − 2m + 1) . . . eN 1 (τ )
|φTi ej (τ )| ≤ N p0
||ǫi (τ )||

max

τ −2m+1≤s≤τ

≤ λi c∗ ε2mN [p0
≤

(46)

||∆(s)||γ τ −2m ||S|| + N (2m − 1)b∗ λi ε1/2 C̄p0 γ τ −4m+1

max

||∆(s)||γ τ −2m ||S|| + (2m − 1)b∗ λi ε1/2 C̄p0 γ τ −4m+1 ]

τ −2m+1≤s≤τ
2λi c∗ mN (||S||/2 + 1)p0 γ τ −2mε

(47)

by (42c), if ||∆(s)|| ≤ 1/2 for τ − 2m + 1 ≤ s ≤ τ . Recalling (45) we obtain
i

δ̃ (t + 1) =

At+1−2m
δ̃ i (2m)
i

−

t−2m
X

At−2m−τ
ǫi (2m + τ ).
i

τ =0

By applying Lemma 4.2 and taking into account (47), it yields that

|
δ̃i,2j−1 (t + 1)|, |δ̃i,2j (t + 1)|

Mij εj−(m−1) γ t+1−2m ||δ̃ i (2m)|| + 4λi c∗ mN (||S|| + 2)p0 ,



j = 1, . . . , m − 2;


≤

M ε(j−m)/2 γ t+1−2m ||δ̃ i (2m)|| + 4λi c∗ mN (||S|| + 2)p0 ,

 ij
j = m − 1, m,

(48)

due to ε/(γ − ρi ) < 4.
P
P2m
T
T
With (48) it is ready to estimate φTi u(t + 1), which is a sum of 2m
j=1 kj φi Lδj (t + 1) and
j=1 kj φi ej (t + 1). For the
−1
i
first part, by (48) and ||δ̃ (2m)|| ≤ ||UL ||||δi (2m)|| we have
P2m
| j=1 kj φTi Lδj (t + 1)|
P
= λi | 2m
j=1 kj δ̃ij (t + 1)|
P
(49)
≤ λi p0 γ t−2m+1 (2Mi,m−1 ε1/2 + 2c∗ ε j6=m−1 Mij )·
i
∗
[||δ̃ (2m)|| + 4λi c mN (||S|| + 2)p0 ]
≤ 3λi Mi,m−1 [||UL−1 || + 4λi c∗ mN (||S|| + 2)]p0 γ t−2m+1 ε1/2
if we note that |c2m−2 |, |c2m−3 | ≤ 1. For the second part, as in the second order case, it is closely related with ||∆(t + 1)|| and
similarly it can be inferred from (34) that d(t + 1) is only dependent on the past quantization errors ∆(τ ), t − 2m + 1 ≤ τ ≤ t
and the past control inputs u(τ ), t − 2m + 1 ≤ τ ≤ t − 1. Hence with the induction assumption (46) the quantizer can be made
unsaturated at time t + 1 with finite bits, namely ||∆(t + 1)|| ≤ 1/2. In consequence we get an estimation similar to (47) that
P2m
(50)
| j=1 kj φTi Lej (t + 1)| ≤ 2λi c∗ mN (||S||/2 + 1)p0 γ t−2m+1 ε.

Combining (49) and (50), it is clear that |φTi u(t + 1)| ≤ Λi C̄p0 γ t−2m+1 ε1/2 , which establishes the induction. Furthermore,
by (48) clearly the consensus can be achieved at a convergence rate of O(γ t ).
3) Data rate. Below we are to discuss the number of quantization levels at each time step. The situation when t ≤ 2m has
been discussed. When t > 2m, we have
||d(t)||

θ
≤ || cos
γ ∆(t − 1) +

j=1

sin θS(2,j)+S(3,j)
∆(t
γ 2m−j+1

− 1 − 2m + j)|| + 2b∗

1
γ 2m−j+1 [cos θS(1, j) + sin θS(2, j) + S(3, j)]∆(t − 1
j=1
P2m−1 ||u(t−1−j)||
+2b∗ j=1
p(t−1)
P
2m−1
1
|l
(θ)|
+ 2b∗ (2m − 1)(N − 1)ΛC̄γ 1−4m ε1/2
k
k=0
2γ 2m

= ||
≤

2m
P

2m
P

P2m−1
j=1

||u(t−1−j)||
p(t−1)

− 2m + j)||

PN
by noticing S(1, ·) = [0, . . . , 0, 1] and u(t) = i=1 φi φTi u(t), Λ1 = 0. By taking into account (42b) and (42c) it can be seen
that ||d(t)|| is bounded by 2m−1 (1 + | cos θ|)m and the proof is completed by remembering (43).

Fig. 1.

Communication topology

Q
Remark 4.6: Noticing that 1≤k≤m−2,k6=n |k−n| = (n−1)!(m−2−n)! attains the minimum at n = ⌊ m−2
2 ⌋ and multiplying
by a positive λi on both sides does not change the direction of an inequality, (42a) can be substituted by the following stronger
one, which is easier to check:
q
Pm−2 Pm−2
λ2
nj−1
1/2
(51)
+
1
+
λ
)ε
≤
3
5c∗ ( j=1
m
m
N
n=1 (⌊ ⌋−2)!(m−1−⌊ ⌋)!
2 .
2

2

Remark 4.7: From the proof it is readily seen that we can still use the same number of bits to achieve the quantized consensus
once the Laplacian of the directed topology satisfies that 0 < λ2 ≤ · · · ≤ λN . However, unlike the case of the 2nd-order
oscillator, it does not hold for the general topology, when the Laplacian contains complex eigenvalues, or real Jordan blocks of
multiple dimensions. For one reason, note that Lemma 4.1 does not hold for a complex λi . For another one, note the disparity
in the order of ε between the disturbance term and the weighted sum of disagreement entries, i.e. ||ǫi (t)|| ∼ O(ε)p0 γ t and
||K δ̃ i (t)|| ∼ O(ε1/2 )p0 γ t . Therefore, if we assume m = 2 and the Jordan block corresponding to λ2 > 0 is two-dimensional
as in (18), then it follows from ||K δ̃ 3 (t)|| ∼ O(ε1/2 )p0 γ t that ||δ̃ 2 (t)|| ∼ O(ε−1 )p0 γ t and ||u(t)|| ∼ O(1)p0 γ t , suggesting
that the input term can no longer be neglected in the estimation errors, nor in the quantization input d(t). Such a situation is
also encountered in [15].
Remark 4.8: At the first glance it may seem doubtful that the data rate is dependent on | cos θ|; but a little further inspection
is enough to clarify. Similar to the situation of the n-th order integrator system investigated in [15], the control input does
not consume any bit in exchanging the estimates of the states when ε is sufficiently small. In other words, we only need to
focus on how many bits it needs to estimate the output of an individual open loop system. Take the second-order case as an
example. Noticing that yi (t) = cos θxi1 (t − 1) + sin θxi2 (t − 1) = 2 cos θxi1 (t − 1) − xi1 (t − 2), we can estimate yi (t) based
on x̂i1 (t − 1) and x̂i1 (t − 2) with an error bound no larger than 12 (2| cos θ| + 1) + 21 . Generally speaking, when | cos θ| ≈ 0
or equivalently | sin θ| ≈ 1, xi,2j−1 (t) and xi,2j (t) are tightly coupled, and it needs only m bits of information exchange
to achieve the consensus; in the case of | cos θ| ≈ 1, after rearranging of states A can be approximated by I2 ⊗ J1,m , and
2m bits are sufficient. Anyway, for a 2m-th order system studied in this paper, 2m bits are enough to realize the consensus
asymptotically, which is consistent with the conclusion for n-th order integrator systems [15].
V. N UMERICAL E XAMPLE
For simplicity we only show an example of m = 2. Consider a 5-node network with 4-th order dynamics, where the edges
are generated randomly according to probability P (i, j) ∈ E = 0.5 with 0-1 weights. The initial states are randomly chosen
as xij (0) ∈ (0, j), i = 1, . . . , 5, j = 1, .. . , 4. Given
3 bitsof information exchange to realize the
√ it is enough
√ to use √
√ θ = π/3,
−4/(3 3) 2/ 3 −4/(3 3) 5/(3 3)
 to construct the encoder and decoder
−1/3
1√
−1√
2/3
consensus, and we can compute S2 = 
√
−1/ 3
1/ 3
−1/ 3
0
respectively as (30)-(33). The communication topology is generated as in Figure 1 with λ2 = 0.8299, and cj ’s are determined
as in Remark 4.4 by choosing h = λ2 . Moreover, let ε = 0.01, p0 = 10, γ = 0.9975 to satisfy the conditions in Theorem 4.1.
From Figure 2 which depicts the trajectory of δjmax (t) = {δnj (t) : n = arg maxi |δij (t)|}, we can see that the consensus is
achieved asymptotically.
VI. C ONCLUDING R EMARKS
In this paper, we explored the data rate problem for quantized consensus of a special kind of multi-agent systems. The
dynamics of each agent is described by a 2m-th order real Jordan form consisting of m pairs of conjugate poles on the unit
circle with single input, and only the first state can be measured. The encoding-decoding scheme was based on the observability
matrix. Perturbation techniques were employed in the consensus analysis and the data rate analysis, and combinatorial techniques

15

15

10

10

5

5

δ

1max

δ

2max

0

−5

−5

−10

−10

−15

0

200

400

600

800

1000

−15

1200

2

2

1.5

1.5

1

1

0.5
δ3max

0

200

400

600

800

1000

1200

0

200

400

600

800

1000

1200

0.5
δ4max

0

0

−0.5

−0.5

−1

−1

−1.5

−1.5

−2

Fig. 2.

0

0

200

400

600

800

1000

1200

−2

Trajectories of disagreements δjmax (t)

were used to explicitly obtain the data rate. The second-order case of m = 1 and higher-order cases of m ≥ 2 were investigated
separately. For the second-order case, we showed that at most 2 bits of information exchange suffice to achieve the consensus
at an exponential rate, if the communication topology has a spanning tree. For the higher-order cases, consensus was achieved
with at most 2m bits, provided that the undirected communication topology is connected. The exact number of bits for achieving
consensus in both cases is an integer which increases from m to 2m when | cos θ| increases from 0 to 1. The case of switching
directed topology is still under investigation, and noisy communication channels will be considered in the future work. As for
general unstable systems with poles outside the unit circle, perturbation techniques no longer apply and new methods need to
be developed to serve the same purpose of stabilizing the dynamics of disagreements.
A PPENDIX
Proof of Lemma 4.1 Here we mainly deal with the case of m ≥ 3, since the proof can be slightly adapted if m = 2 and the
modification will be pointed out accordingly. The characteristic equation of Ai can be computed as
χi (µ) = det[(µI − Q)m + λi Km (µI − Q)m−1 + · · · + λi K2 (µI − Q) + λi K1 ],

P

0

m−1

2
Pm−1

1
P2m
0

Fig. 3.

P

2m−1

1

P

m−2

P

P

m

2m−2

2

m−1

m

m+1

m+2

2m

Newton diagram



cos θ
where Q =
− sin θ
we rewrite χi (µ) as

sin θ
cos θ



and Kj =



0
k2j−1

0
k2j



for j = 1, . . . , m. By employing (11) in the proof of Lemma 3.1,

χi (µ) = (µ − eθ )m (µ − e−θ )m + 21 [(µ − eθ )m + (µ − e−θ )m ] λ2i ·
m
m
P
P
(k2j−1  + k2j )(µ − e−θ )j−1 ]
[ (−k2j−1  + k2j )(µ − eθ )j−1 + 2k2 +
j=2

j=2

+ 2 [(µ − eθ )m − (µ − e−θ )m ] λ2i ·
m
m
P
P
(k2j−1 − k2j )(µ − e−θ )j−1 ]
[ (k2j−1 + k2j )(µ − eθ )j−1 + 2k1 +

(52)

j=2

j=2

θ m

= (µ − e ) [(µ − e

−θ m

) +

λi
2 (k2

+ k1 )] +

λi
2 (µ

− e−θ )m

m
P

j=1

(µ − eθ )j−1 (−k2j−1  + k2j ).

With Ai being real, we only need to focus on the perturbed roots around eθ , which are denoted by µ = eθ + ∆µ. Noticing
that µ − e−θ = µ − eθ + 2 sin θ, we substitute µ = eθ + ∆µ into (52) and obtain
χi (eθ + ∆µ) =

m
X

ain (ε)(∆µ)m−n +

n=1

m
X

(C(m, m − n)(2 sin θ)m−n + O(ε))(∆µ)m+n

(53)

n=0

with the selection of k2j−1 and kj in (37), where

(2 sin θ)m−1 [2 sin θ(c2m − c2m−1 ) + m(c2m−2 − c2m−3 )]ε + o(ε), n = 1;
ain (ε) =
(2 sin θ)m (c2(m−n+1) − c2(m−n)+1 )εn−1 + o(εn−1 ), n = 2, . . . , m.
Now the Newton diagram [17] can be depicted as in Fig. 3, by first plotting points P2m−j (j, α2m−j ), j = 0, . . . , 2m and then
connecting the segments on the lower boundary of the convex hull of the above points, where α2m−j is the leading exponent
of ε in the coefficient of (∆µ)2m−j . The slopes of the two non-horizontal segments are 1/2, 1 respectively, implying that ∆µ
has the following two forms of expansions:
1

∆µ = µ1 ε 2 + µ2 εβ + o(εβ ), µ1 6= 0;
∆µ = υ1 ε + o(ε), ϑ1 =
6 0.

(54a)
(54b)

m−2 λi
m
m
Substituting (54a) into (53) and finding the coefficients of the term εm/2 , it yields that µm
1 (2 sin θ) +µ1
2 (2 sin θ) (c2m−2 −
c2m−3 ) = 0, and thus
r q
α
λi
µ1 = ±
c22m−3 + c22m−2 e 2 ,
(55)
2
where α = arg(c2m−3  − c2m−2 ). Moreover, to determine µ2 and β, we substitute (54a) into (53) again and find the lowest
order term as
mµm−1
µ2 (2 sin θ)m ε(m−1)/2 εβ
1
λi m−1
+ 2 µ1 (2 sin θ)m (c2m − c2m−1 )ε(m+1)/2
(56)
+ λ2i (m − 2)µm−3
µ2 (2 sin θ)m (c2m−2 − c2m−3 )ε(m−1)/2 εβ
1
(2 sin θ)m (c2m−4 − c2m−5 )ε(m+1)/2 = 0,
+ λ2i µm−3
1

which implies β = 1 and µ2 =

(c2m−5 −c2m−4 )
λi
4 (c2m−1  − c2m ) + 2(c2m−3 −c2m−2 ) .
1

In the form of (54a), the module of µ is determined as

|µ|2 = µµ̄ = 1 + 2Re(µ1 e−θ )ε 2 + (|µ1 |2 + 2Re(µ2 e−θ ))ε + o(ε),

(57)

with Re(µ1 e

−θ

) = ±

r

λi
2

q
c22m−3 + c22m−2 cos( α2 − θ). In order that |µ| < 1 with sufficiently small ε, we must have

− θ = π2 , and hence it suffices to let |µ1 |2 + 2Re(µ2 e−θ ) < 0. Combining these arguments gives rise to a sufficient
condition as
α
2

−c2m−3 /c2m−2 = tan(2θ + π), c22m−3 + c22m−2 6= 0;
q
−c2m−4 −θ
λi
e ] < 0.
c22m−3 + c22m−2 + λ2i (c2m−1 sin θ − c2m cos θ) + Re[ cc2m−5
2
2m−3 −c2m−2

(58b)

|µ|2 = 1 + 2Re(ϑ1 e−θ )ε + o(ε)

(59)

(58a)

With c2m−3 = − sin 2θ and c2m−2 = cos 2θ satisfying (58a), (58b) is equivalent to λi Rm + H < 0. When m = 2, µ only
takes the form of (54a) and µ2 = λ4i (c2m−1  − c2m ), leading to the sufficient condition R2 < 0 for |µ| < 1.
On the other hand, substituting (54b) into (52) and finding the coefficients of the term εm−1 , we obtain the equation (39).
Similarly, the module of µ with the form (54b) is determined by

and it suffices to let Re(ϑ1 e−θ ) to be negative such that |µ| < 1 with sufficiently small ε. For prescribed c2m−3 and c2m−2 ,
the roots of (39) can be assigned arbitrarily such that Re(ϑ1 e−θ ) < 0 with m − 2 distinct ϑ1 ; after determining c2m−4 and
c2m−5 , (58b) can always be satisfied by properly chosen c2m and c2m−1 since λ2i (c2m−1 sin θ − c2m cos θ) can be assigned
to any number. In summary, the proof is completed.
Proof of Lemma 4.2 As in the last proof, we only focus on the case of m ≥ 3 which essentially includes the case of m = 2.
For Ai , we are to find the following Jordan decomposition:
Ai = A +

m−1
X

Aij εj = Ri Ãi Ri−1 ,

(60)

j=1

where Ãi is a diagonal matrix consisting of 2m different eigenvalues determined in Lemma 4.1. To find an appropriate Ri
and the corresponding Ri−1 , we first determine the Jordan basis of the unperturbed matrix A. The Jordan chain corresponding
to the eigenvalue µ0 = eθ is given by
A−µ0 I

A−µ0 I

A−µ0 I

A−µ0 I

um−1 −−−−→ um−2 −−−−→ . . . −−−−→ u1 −−−−→ u0 ,
where uj = e2j+1 + e2j+2 , j = 0, . . . , m − 1 and en ∈ R2m denotes the vector with a 1 in the n-th coordinate and 0’s
elsewhere. Similarly, the Jordan chain corresponding to the eigenvalue µ̄0 = e−θ is given by
A−µ̄0 I

A−µ̄0 I

A−µ̄0 I

A−µ̄0 I

ūm−1 −−−−→ ūm−2 −−−−→ . . . −−−−→ ū1 −−−−→ ū0 .




1 1
Hence the two Jordan chains of A can be rearranged as R0 = (u0 ū0 . . . um−1 ūm−1 ) = Im ⊗ P with P =
.
 −
With Ai being real, once we obtain the eigenvectors corresponding to the m different perturbed eigenvalues around µ0 , the
other eigenvectors can be obtained by taking conjugates. Hence we only need to find the eigenvectors corresponding to the m
different perturbed eigenvalues around µ0 .
The eigenvectors corresponding to the m perturbed eigenvalues around µ0 have the following form of Puiseux series [19]:
P∞
P∞
k/2
µin = µ0 + Pk=1 µink εk/2 , uin = uin0 +
P∞k=1 uinkkε , n = 1, 2;
∞
k
µin = µ0 + k=1 ϑink ε , uin = uin0 + k=1 uink ε , n = 3, . . . , m,
r q
α
λi
c22m−3 + c22m−2 e 2 , µi21 = −µi11 and ϑin1 = ϑn1 , n = 3, . . . , m have been defined in Lemma 4.1.
where µi11 =
2

Substituting µin , uin into the equation Ai uin = µin uin respectively, and collecting coefficients of equal powers of ε; moreover,
noticing the fact that Aij uk = 0, j = 1, . . . , m − 2; k = 0, . . . , m − 2 − j, where Aij has
 been defined in (60) and imposing
T
T
the normalization condition as vm−1
uin = 1, where vm−1
= 21 1 − 0 . . . 0 is the left associated eigenvector of
T
T
T
A with respect to the eigenvalue µ0 such that vm−1
u0 = 1, vm−1
u1 = · · · = vm−1
um−1 = 0, the m eigenvectors can be
obtained as:
m−1
P k/2 k
′
ε (µi1n uk + uikn ) + o(εm/2 ), n = 1, 2;
uin = u0 +
uin = u0 +

k=1
m−1
P
k=1

′

′

′

εk (ϑk1n uk + uikn ) + o(εm ), n = 3, . . . , m,

where ui1n = 0 and uikn ∈ span{u1 , . . . , uk−1}, k = 2, . . . , m − 1 for n = 1, . . . , m.
Letting Ri = ui1 ūi1 . . . uim ūim , we are to investigate the magnitude of each entry in Ri−1 by adjoint method.
Therefore we need to find the order of det Ri and the corresponding cofactor, both of which can be expressed as Puiseux
series. The following facts should be mentioned before the calculation:
1). Determinant is a multi-linear function of column vectors, and it vanishes when two or more columns coincide.

2). There exist two types of series in the columns of Ri , and we categorize ui1 , ui2 and their conjugates for type I, the others
for type II.
With these facts, we can see that the lowest degree can be obtained by taking out terms with ε(m−2)/2 um−2 and ε(m−1)/2 um−1
respectively from ui1 and ui1 , terms with u0 , εu1 , . . . , εm−3 um−3 respectively from ui3 , . . . , uim , as well as the corresponding
m−1
2
conjugates from ūi1 , . . . , ūim , and calculated by 2(0 + 1 + · · · + m − 3 + m−2
2 + 2 ) = m − 3m + 3. Moreover,
2

m−2
m−2 m−1 2
2
m −3m+3
| det Ri | = |µm−1
(1 + o(1))
i11 µi21 − µi11 µi21 | | det V0 | | det R0 |ε
(61)
m−2 m−2
2
2 m m2 −3m+3
= |µi11 µi21 (µi11 − µi21 )| | det V0 | 2 ε
(1 + o(1)),


1 ϑ31 . . . ϑm−3
31
 1 ϑ41 . . . ϑm−3 
41


where V0 = V (ϑ31 , . . . , ϑm1 ) =  .
 is a Vandermonde matrix of order m − 2.
..
..
..

 ..
.
.
.
m−3
1 ϑm1 . . . ϑm1
(i)
On the other hand, we need to determinate the order of the cofactor Cs,t of the (s, t) entry, and we illustrate it by calculating
(i)
C1,1 with m = 3. After deleting the first column ui1 , we delete the first row and use the same notations u1 , u2 and e2 , . . . , e6 .
(i)
Now Ri has been reduced to a square matrix R1,1 consisting of the following 5 columns:

a1 = −je2 + ε1/2 µ̄i11 ū1 + εµ̄2i11 ū2 + O(ε)ū1 + O(ε2 ),
a2 = je2 + ε1/2 µi21 u1 + εµ2i21 u2 + O(ε)u1 + O(ε2 ), a3 = ā2 ,
a4 = je2 + εϑ31 u1 + ε2 ϑ231 u2 + O(ε2 )u1 + O(ε2 ), a5 = ā4 .
(i)

Consequently the order of C1,1 is found in such a way: take out terms with ε1/2 ū1 , εū2 respectively from a1 , a3 , terms with
e2 from a5 , terms with εu2 from a2 , terms with εu1 from a4 . Now that a1 , a3 , a5 jointly contribute the same degree of
1
2
2 (m − 3m + 3) as ūi1 , ūi2 , ūi3 , we are left to choose terms with u1 and u2 respectively from a2 and a4 . The above can
(i)
be conducted similarly for calculating the order of C1,1 when m > 3, and actually for every cofactor. Moreover, by the
(i)
(i)
(i)
(i)
(i)
symmetry of conjugates, C2k−1,2n−1 , C2k−1,2n , C2k,2n−1 , C2k,2n have an identical order. So we only focus on C2k−1,2n−1
(i)
below. Reminded by the case of C1,1 when m = 3, we suffice to choose linearly independent terms with a lowest sum
of degrees from the modified columns uij for j 6= n, where uk−1 has been subtracted from each column. Recall that in
finding the order of | det Ri |, terms with εu0 , . . . , εm−3 um−3 from type II columns are first selected, and then terms with
ε(m−2)/2 um−2 , ε(m−1)/2 um−1 from type I columns. Such a method still applies in finding the order of cofactors, and we
(i)
conclude that C2k−1,2n−1 has the lowest order for fixed n if and only if k = m. In other words, for any row in adjRi , the
entries at the 2m − 1-th and 2m-th column exclusively have the lowest order when compared with other entries at the same
row. To be detailed,
(i)

(i)

(i)

(i)

|C2m−1,2n−1 |, |C2m−1,2n |, |C2m,2n−1 |, |C2m,2n |
 m−1
m−2
m−2
2
| det V0 |2 |µm−2

i11 µi21 (µi11 − µi21 )||µin1 |
 m2 −3m+3−(m−1)/2

·ε
(1 + o(1)), n = 1, 2;
=
m−2
m−1
2
|
det
V
||
det
V
||µm−2

0
n
i11 µi21 (µi11 − µi21 )|


m−3 m−3
m2 −3m+3−(m−2)
·|µi11 µi21 (µi11 − µi21 )|ε
(1 + o(1)), n = 3, . . . , m,

(62)

where Vn = V (ϑ31 , . . . , ϑn−1,1 , ϑn1 , . . . , ϑm1 ) is a Vandermonde matrix of order m − 3. Together with (61) it yields that by
µi11 = −µi21
−1
−1
−1
−1
|R
( i (2n1 − 1, 2m − 1)|, |Ri (2n, 2m − 1)|, |Ri (2n − 1, 2m)|, |Ri (2n, 2m)|
−(m−1)/2
(1 + o(1)), n = 1, 2;
4|µi11 |m−1 ε
=
| det Vn | −(m−1)
1
ε
(1 + o(1)), n = 3, . . . , m;
2|µi11 |2 | det V0 |
(63)
−1
−1
|R
− 1, k)|, |Ri (2n, k)|
 i (2n
o(ε−(m−1)/2 ), n = 1, 2;
=
for 1 ≤ k ≤ 2m.
o(ε−(m−1) ), n = 3, . . . , m;
In the meanwhile, the following holds for 1 ≤ j ≤ m:

|Ri (2j − 1, 2n − 1)|, |Ri (2j − 1, 2n)|, |Ri (2j, 2n − 1)|, |Ri (2j, 2n)|
 j−1 (j−1)/2
|µin1 |ε
+ O(εj/2 ), n = 1, 2;
=
j−1 j−1
|ϑn1 |ε
+ O(εj ), n = 3, . . . , m;

(64)

Combining (60), (63) and (64) we can obtain
|ξs,2j−1 |
 Pm
−1
−1
≤ ρsi ||ξ||
n=1 |Ri (2j − 1, 2n − 1)|(|Ri (2n − 1, 2m − 1)| + |Ri (2n − 1, 2m)|)
Pm
−1
−1
+ n=1 |Ri (2j − 1, 2n)|(|Ri (2n, 2m − 1)| + |Ri (2n, 2m)|) (1 + o(1))
 P2
Pm |ϑj−1 |
|µj−1
Vn | j−(m−1) 
(j−m)/2
in1 |
+ n=3 2|µn12 | || det
(1 + o(1)).
≤ ρsi ||ξ||2
n=1 4|µm−1 | ε
det V0 | ε
i11

i11

< j−m
p 2

and the conclusion follows by noticing that j − (m − 1)
for j = m − 1, m, as well as |µi11 | =
j − (m − 1) > j−m
2

for j < m − 2, j − (m − 1) = j−m
for j = m − 2 and
2
Q
Vn |
|ϑ
−
ϑ
|.
=
λi /2, || det
k1
n1
det V0 |
3≤k≤m,k6=n

Proof of Lemma 4.3 The proofPof Lemma 4.3 relies on the following combinatorial identity.
∞
Lemma A.1: [21] Let f (t) = k=0 fk tk be a formal power series [20]. Then the following rule holds if b = 0 and f (t) is
a polynomial:
X
C(n + ak, m + bk)z m+bk fk = [tm ](1 + zt)n f (t−b (1 + zt)a ),
k

m

where [t ]g(t) denotes the extraction of the coefficient of tm from the formal power series g(t).
Now let we return to the proof. Denoting
v(θ) = cos θA2m−1 (1, ·) + sin θA2m−1 (2, ·) + A2m−1 (3, ·)
= [v1 (θ) v2 (θ) . . . v2m−1 (θ) v2m (θ)]

and recalling S = A2m−1 O−1 , the original equation is equivalent to l(θ)O = v(θ). Direct computation shows that the entries
of v(θ) are given by
v2j−1 (θ) = C(2m, j − 1) cos(2m − j + 1)θ,
v2j (θ) = C(2m, j − 1) sin(2m − j + 1)θ, j = 1, . . . , m;
and the entries of O are given by
O(k, 2j − 1) = C(k − 1, j − 1) cos(k − j)θ,
O(k, 2j) = C(k − 1, j − 1) sin(k − j)θ, k = 1, . . . , 2m, j = 1, . . . , m.
As a result, the equation l(θ)O = v(θ) is equivalent to the following m equations:
2m−1
X
k=0

or equally

lk (θ)C(k, h)e(k−h)θ = C(2m, h)e(2m−h)θ , h = 0, 1, . . . , m − 1,
2m
X

k=0

lk (θ)C(k, h)e(k−h)θ = 0, h = 0, 1, . . . , m − 1,

(65)

(65′ )

if we let l2m (θ) = −1. Noticing that 2 cos θ = eθ + e−θ , we substitute
the expression of lk (θ)P
into the left-hand side of the
P
m
(k−h)θ
(2w−h)θ
above h-th equation, and expand it into a power series of eθ as 2m
l
(θ)C(k,
h)e
=
, with
k
k=0
w=0 αw,h e
αw,h =

w m−k
X
X

k=0 j=w−k

C(m, j)C(m − j, k)C(j, w − k)C(j + 2k, h)(−1)j+2k−1 .

Therefore, if we can show that αw,h for w = 0, 1, . . . , m and h = 0, 1, . . . , m − 1, then the prescribed l(θ) is a solution of
(65), and by the nonsigularity of O it is also unique.
We first transform αw,h as follows. By remembering that
C(m, j)C(m − j, k)C(j, w − k) = C(m, k)C(m − k, j)C(j, w − k)
= C(m, k)C(m − k, w − k)C(m − w, j − (w − k))
and letting s = j − (w − k), it is clear that
αw,h =

w
X

k=0

C(m, k)C(m − k, w − k)(−1)k+w−1

m−w
X
s=0

C(m − w, s)C(s + w + k, h)(−1)s .

NowPwe claim that
s
m−w
, w = 0, 1, . . . , m,
1). Pm−w
s=0 C(m − w, s)C(s + w + k, h)(−1) = C(w + k, h − (m − w))(−1)
w
m+k−1
= 0, h = 0, 1, . . . , m − 1,
2). k=0 C(m, k)C(m − k, w − k)C(w + k, h − (m − w))(−1)

and the proof of the first part is completed by combining
these two claims.
P
1). Let fs = (−1)s C(m − w, s) and f (t) = fs ts = (1 − t)m−w . Applying Lemma A.1, we have
s

Pm−w
C(m − w, s)C(s + w + k, h)(−1)s
Ps=0
m−w
= s=0 C(w + k + 1 · s, h + 0 · s) · 1 · fs
= [th ](1 + t)w+k f (1 + t)
= [th ](1 + t)w+k (−t)m−w
= (−1)m−w [th−(m−w) ](1 + t)w+k
= (−1)m−w C(w + k, h − (m − w)),

which establishes the first claim.
2). For the second claim,
Pw
=
=
=
=

=

k)C(m − k, w − k)C(w + k, h − (m − w))(−1)m+k−1
k=0 C(m,
Pm
m−1
k
(−1)
k=0 C(m, k)(−1) C(m − k, w − k)C(w + k, h − (m − w))
P
m
(−1)m−1 k=0 [tk ](1 − t)m [v m−w ](1 + v)m−k [uh−(m−w) ](1 + u)w+k
Pm
k
m
(−1)m−1 [v m−w ](1 + v)m [uh−(m−w) ](1 + u)w k=0 [tk ]( 1+u
1+v ) (1 − t)
m
(−1)m−1 [v m−w ](1 + v)m [uh−(m−w) ](1 + u)w (1 − 1+u
1+v )
m
m−1 m−w
m h−(m−w)
w (v−u)
(−1)
[v
](1 + v) [u
](1 + u) (1+v)m
m−1 m−w
h−(m−w)
w
m

= (−1)

[v

r=h−(m−w)

][u

](1 + u) (v − u)

========== (−1)m−1 [v m−w ][ur ](1 + u)w (v − u)m
Pr
= (−1)m−1 [v m−w ] k=0 C(w, r − k)C(m, k)v m−k (−1)k
P
= (−1)m−1 [v k−w ] rk=0 C(w, r − k)C(m, k)(−1)k ,

where t, v, u are indeterminates. Noticing that r ≥ w ⇔ h − (m − w) ≥ w ⇔ h ≥ m is contradictory to h = 0, 1, . . . , m − 1,
we have r < w and k ≤ r < w, which suggests the vanishing of the last equation in the above, and the proof for the first part
is complete.
As for the second part, by noting that the exponents of cos θ in lk (θ) are even when k is an even number, while the exponents
are odd when k is an odd number, it can be noted that the sign of each term in lk (θ) is the same. Therefore we obtain
P2m−1
P2m−1 P⌊k/2⌋
k−2h
k=0 |lk (θ)| = Pk=0
h=0 C(m, k − 2h)C(m − (k − 2h), h)|2 cos θ|
m
j
= j=0 βj | cos θ| ,
P
m
with β0 = 2m − 1 and βj = 2j C(m, j) m−j
h=0 C(m − j, h) = 2 C(m, j) for j = 1, . . . , m, and the conclusion follows
directly.
Acknowledgement The authors would like to thank Dr. Shuai Liu for his valuable suggestions.
R EFERENCES
[1] Z. Qiu, L. Xie, and Y. Hong, “Data rate for quantized consensus of high-order multi-agent systems with poles on the unit circle,” in 53rd IEEE Conference
on Decision and Control, Dec. 2014, pp. 3771–3776.
[2] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and Cooperation in Networked Multi-Agent Systems,” Proceedings of the IEEE, vol. 95,
no. 1, pp. 215–233, Jan. 2007.
[3] Y. Cao, W. Yu, W. Ren, and G. Chen, “An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination,” IEEE Transactions on
Industrial Informatics, vol. 9, no. 1, pp. 427–438, Feb. 2013.
[4] S. Knorn, Z. Chen, and R. Middleton, “Overview: Collective Control of Multi-agent Systems,” IEEE Transactions on Control of Network Systems,
vol. PP, no. 99, pp. 1–1, 2015.
[5] A. Kashyap, T. Başar, and R. Srikant, “Quantized consensus,” Automatica, vol. 43, no. 7, pp. 1192–1203, July 2007.
[6] A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “On distributed averaging algorithms and quantization effects,” IEEE Transactions on
Automatic Control, vol. 54, no. 11, pp. 2506–2517, 2009.
[7] R. Carli, F. Bullo, and S. Zampieri, “Quantized average consensus via dynamic coding/decoding schemes,” International Journal of Robust and
Nonlinear Control, vol. 20, no. 2, pp. 156–175, Jan. 2010.
[8] T. Li, M. Fu, L. Xie, and J.-F. Zhang, “Distributed Consensus With Limited Communication Data Rate,” IEEE Transactions on Automatic Control,
vol. 56, no. 2, pp. 279–292, Feb. 2011.
[9] Keyou You and Lihua Xie, “Network Topology and Communication Data Rate for Consensusability of Discrete-Time Multi-Agent Systems,” IEEE
Transactions on Automatic Control, vol. 56, no. 10, pp. 2262–2275, Oct. 2011.
[10] Y. Meng, T. Li, and J.-F. Zhang, “Coordination Over Multi-Agent Networks With Unmeasurable States and Finite-Level Quantization,” arXiv:1505.03259
[cs, math], May 2015.
[11] Q. Zhang and J.-F. Zhang, “Quantized Data–Based Distributed Consensus under Directed Time-Varying Communication Topology,” SIAM Journal on
Control and Optimization, vol. 51, no. 1, pp. 332–352, Jan. 2013.
[12] D. Li, Q. Liu, X. Wang, and Z. Yin, “Quantized consensus over directed networks with switching topologies,” Systems & Control Letters, vol. 65, pp.
13–22, Mar. 2014.
[13] A. Olshevsky, “Consensus with Ternary Messages,” SIAM Journal on Control and Optimization, vol. 52, no. 2, pp. 987–1009, Jan. 2014.

[14] Tao Li and Lihua Xie, “Distributed Coordination of Multi-Agent Systems With Quantized-Observer Based Encoding-Decoding,” IEEE Transactions on
Automatic Control, vol. 57, no. 12, pp. 3023–3037, Dec. 2012.
[15] Z. Qiu, L. Xie, and Y. Hong, “Quantized Leaderless and Leader-Following Consensus of High-Order Multi-Agent Systems With Limited Data Rate,”
IEEE Transactions on Automatic Control, vol. 61, no. 9, pp. 2432–2447, Sept. 2016.
[16] Wei Ren and R. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies,” IEEE Transactions on Automatic
Control, vol. 50, no. 5, pp. 655–661, May 2005.
[17] A. P. Seyranian and A. A. Mailybaev, Multiparameter stability theory with mechanical applications. World Scientific, 2003, vol. 13.
[18] C.-T. Chen, Linear system theory and design. Oxford University Press, Inc., 1995.
[19] H. Baumgärtel, Analytic perturbation theory for matrices and operators. Springer, 1985, vol. 15.
[20] R. Sprugnoli, “An introduction to mathematical methods in combinatorics,” Dipartimento di Sistemi e Informatica Viale Morgagni, 2006.
[21] ——, “Riordan array proofs of identities in Gould’s book,” Published electronically at http://www. dsi. unifi. it/resp/GouldBK. pdf, 2007.

