# On the Nonexistence of Quadratic Lyapunov Function

# 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.

Prev | Next |