On the Nonexistence of Quadratic Lyapunov Function

Abstract—We provide an example proving that there exists no quadratic
Lyapunov function for a certain class of linear agreement /consensus algorithms,
a fact that had been numerically verified in [6].We also briefly discuss
sufficient conditions for the existence of such a Lyapunov function.

Index Terms —Consensus algorithms, Lyapunov theory, multi-agent systems.

I. INTRODUCTION

We examine a class of algorithms that can be used by a group of
agents (e.g., UAVs, nodes of a communication network, etc.) in order
to reach consensus on a common opinion (represented by a scalar or
vector), starting from different initial opinions, and possibly in the presence
of severe restrictions on inter-agent communications.

We focus on a particular algorithm, whereby, at each time step , every
agent averages its own opinion with received messages containing the
current opinions of some other agents. While this algorithm is known to
converge under mild conditions, convergence proofs usually rely on the
“span norm” of the vector of opinions. In this note, we address the question
of whether convergence can also be established using a quadratic
Lyapunov function. Among other reasons, this question is of interest
because of its potential implications on convergence time analysis. A
negative answer to this question was provided in [6], where the nonexistence
of a quadratic Lyapunov function was verified numerically. In
this paper, we provide an explicit example and proof of this fact.

In Section II we give some definitions and formally state the
problem. Section III contains the main result and its proof. Section IV
provides some additional perspective, together with some conditions
under which a quadratic Lyapunov function is guaranteed to exist [1].

II. AGREEMENT ALGORITHM

We consider a set of agents embedded, at each
nonnegative integer time t, in a directed graph .We
assume that , for all i and t. We define
, and let be the cardinality of .

Each agent i starts with a scalar value . At each time t, agent i
receives from every agent a message with the value of ,
and uses the received values to perform the update

where the are nonnegative coefficients that satisfy if
so that is a weighted
average of the values held by the agents at time t. We define the
vector , and note that the algorithm can be
written in the form .

We next state some conditions under which the agreement algorithm
is guaranteed to converge.

Assumption 1: There exists some such that if ,
then .

Assumption 2: (Bounded Intercommunication Intervals): There
is some B such that for every nonnegative integer k, the graph
is strongly connected.

Theorem 3: Under Assumptions 1–2, and for every , the components
converge to a common limit.

Theorem 3 is presented in [11] and is proved in [10] (under a slightly
different version of Assumption 2), as well as in [6], for a special case
to be considered below; see also [5], [9] for generalizations and extensions}.
On the other hand, if the graphs are symmetric, namely,
if and only if , Assumption 2 can be replaced
by the weaker requirement that the graph is strongly
connected for every ; see [4], [5], [7], [9].

We will focus on a special case, motivated from the model of Vicsek
et al. [12], and studied in [6], to be referred to as the symmetric, equalneighbor,
model. In this model, the graphs are symmetric, and
, for every . Thus, each node forms an
unweighted average of the values that it has access to (including
its own).

Theorem 3 is usually proved by showing that the “span norm”
is guaranteed to decrease after a certain
number of iterations . Unfortunately, this proof method usually gives
an overly conservative bound on the convergence time of the algorithm.
Tighter bounds on the convergence time would have to rely on
alternative Lyapunov functions, such as quadratic ones, of the form
, if they exist.

Although quadratic Lyapunov functions can always be found for
linear systems , they may fail to exist when the system is allowed to
switch between a fixed number of linear modes. On the other hand,
there are classes of such switched linear systems that do admit quadratic
Lyapunov functions. See [8] for a broad overview of the literature on
this subject. For the symmetric, equal-neighbor model this issue was
investigated in [6]. The authors write:

no such common Lyapunov matrix M exists. While we
have not been able to construct a simple analytical example which
demonstrates this, we have been able to determine, for example,
that no common quadratic Lyapunov function exists for the class
of all [ graphs which have] 10 vertices and are connected. One
can verify that this is so by using semidefinite programming

The main contribution of this note is to provide an analytical example
that proves this fact.

III. THE EXAMPLE

Let us fix a positive integer n. We start by defining a class Q of
functions with some minimal desired properties of quadratic Lyapunov
functions. Let be the vector in with all components equal to 1. A
square matrix is said to be stochastic if it is nonnegative and the sum of
the entries in each row is equal to one. Let be the set of stochastic
matrices A such that: (i) , for all i; (ii) all positive entries
on any given row of A are equal; (iii) if and only if ;
(iv) the graph associated with the set of edges is connected.
These are precisely the matrices that correspond to a single iteration
of the equal-neighbor algorithm on symmetric, connected graphs.

Definition 4: A function Q: belongs to the class Q if it
is of the form , where:

a) The matrix is nonzero, symmetric, and nonnegative
definite.
b) For every , and , we have .
c) We have .
Note that condition (b) may be rewritten in matrix form as

The rationale behind condition (c) is as follows. Let be the subspace
spanned by the vector . Since we are interested in convergence to the
set , and every element of is a fixed point of the algorithm, it is
natural to require that , or, equivalently,

Of course, for a Lyapunov function to be useful, additional properties
would be desirable. For example we should require some additional
condition that guarantees that eventually decreases. However,
according to Theorem 5, even the minimal requirements in Definition
4 are sufficient to preclude the existence of a quadratic Lyapunov
function.

Theorem 5: Suppose that . Then, the class Q (cf. Definition 4) is empty.

The idea of the proof is as follows. Using the fact the dynamics of the
system are essentially the same when we rename the components, we
show that if has the desired properties, so does for a matrix
Z that has certain permutation-invariance properties. This leads us
to the conclusion that there is essentially a single candidate Lyapunov
function, for which a counterexample is easy to develop.

Recall that a permutation of n elements is a bijective mapping
Let be the set of all permutations of
n elements. For any , we define a corresponding permutation
matrix by letting the ith component of be equal to . Note
that , for all be the set of all permutation
matrices corresponding to permutations in .

Lemma 6: Let . Define Z as

Then, .

Proof: For every matrix , and any , it is easily seen
that . This is because the transformation
amounts to permuting the rows and columns of A, which is the same
as permuting (renaming) the nodes of the graph.

We claim that if Indeed,
if M is nonzero, symmetric, and nonnegative definite, so is .
Furthermore, since To
establish condition (b) in Definition 4, let us introduce the notation
. Fix a vector define
. We have

where the inequality follows by applying (1), which is satisfied by M,
to the vector and the matrix B. We conclude that
Since the sum of matrices in Q remains in Q, it follows that Z=
belongs to Q.

We define the “sample variance” of the values , by

where . This is a nonnegative quadratic function of
x, and therefore, , for a suitable nonnegative definite,
nonzero symmetric matrix .

Lemma 7: There exists somesuch that

Proof: We observe that the matrix Z satisfies

To see this, fix R and notice that the mapping is a bijection
of onto itself, and therefore,

We will now show that condition (2) determines Z, up to a multiplicative
factor . Let th entry of Z. Let be the
ith unit vector, so that . Let be a permutation
matrix that satisfies . Then,
Therefore, all diagonal entries
of Z have a common value, to be denoted by z.

Let us now fix three distinct indices , and let ,
. Let be a permutation matrix such that
, so that . We have

By repeating this argument for different choices of , it follows
that all off-diagonal entries of Z have a common value to be denoted
by r. Using also the property that , we obtain that
This shows that the matrix Z is uniquely determined, up to a
multiplicative factor .

We now observe that permuting the components of a vector x does
not change the value of . Therefore, for every
, which implies that and
. Thus, C satisfies (2). Since all matrices that satisfy (3) are
scalar multiples of each other, the desired result follows.

Proof of Theorem 5: In view of Lemmas 6 and 7, if Q is
nonempty, then . Thus, it suffices to show that . Suppose
that , and consider the vector x with components ,
and
Consider the outcome
of one iteration of the symmetric, equal-neighbor algorithm, if the
graph has the form shown in Fig. 1. After the iteration, we obtain the
vector y with components
We have

where we used that is minimized when
. A simple calculation shows that the expression (3)
evaluates to , which implies that .
Thus, if and the set Q is empty.

IV. CONDITIONS FOR THE EXISTENCE OF A QUADRATIC LYAPUNOV FUNCTION

Are there some additional conditions (e.g., restricting the matrices
A to a set smaller than ), under which a quadratic Lyapunov function
is guaranteed to exist? We start by showing that the answer is positive
for the case of a fixed matrix (that is, if the graph is the same for
all t).

Let A be a stochastic matrix, and suppose that there exists a positive
vector such that . Without loss of generality, we can
assume that . It is known that in this case,

where D is a diagonal matrix, whose th diagonal entry is equal to
(cf. Lemma 6.4 in [2]). However, cannot be used as a Lyapunov
function because (cf. condition (c) in Definition 4). To remedy
this, we argue as in [3] and define the matrix , and
consider the choice . Note that M has rank .
We have , as desired.
Furthermore,

Using this property, we obtain, for every ,

where the inequality was obtained from (4), applied to . This shows
that has the desired properties (a)–(c) of Definition 4, provided
that is replaced with .

We have just shown that every stochastic matrix (with a positive left
eigenvector associated to the eigenvalue 1) is guaranteed to admit a
quadratic Lyapunov function, in the sense of Definition 4. Moreover,
our discussion implies that there are some classes of stochastic matrices
for which the same Lyapunov function can be used for all matrices
in the class.

a) Let be a set of stochastic matrices. Suppose that there exists a
positive vector such that
Then, there exists a nonzero, symmetric, nonnegative definite
matrix M, of rank , such that , and
, for all x and

b) The condition in (a) above is automatically true if all the matrices
in are doubly stochastic (recall that a matrix A is doubly stochastic
if both A and are stochastic); in that case, we can take

c) The condition in (a) above holds if and only if there exists a
positive vector , such that , for all and
all x. In words, there must be a positive linear functional of the
agents’ opinions which is conserved at each iteration. For the
case of doubly stochastic matrices, this linear functional is any
positive multiple of the sum of the agents’ values (e.g.,
the average of these values).

ACKNOWLEDGMENT

The authors are grateful to Ali Jadbabaie for useful discussions about
this problem.