# A Unified Framework for Consensus and Synchronization on Lie Groups
admitting a Bi-Invariant Metric

Rama Seshan, Ravi N Banavar, Arun D Mahindrakar

(September 2022)

###### Abstract

For a finite number of agents evolving on a Euclidean space and linked to each
other by a connected graph, the Laplacian flow that is based on the inter-
agent errors, ensures consensus or synchronization for both first and second-
order dynamics. When such agents evolve on a circle (the Kuramoto oscillator),
the flow that depends on the sinusoid of the inter-agent error angles
generalizes the same. In this work, it is shown that the Laplacian flow and
the Kuramoto oscillator are special cases of a more general theory of
consensus on Lie groups that admit bi-invariant metrics. Such a theory not
only enables generalization of these consensus and synchronization algorithms
to Lie groups but also provide insight on to the abstract group theoretic and
differential geometric properties that ensures convergence in Euclidean space
and the circle.

##  1 Introduction

There is a huge scope for the design and analysis of algorithms that
coordinate a system of identical autonomous agents - examples include
formation of vehicles [11], oscillator synchronization [23], spacecraft
formations [6], study of flocking mechanisms in living beings such as birds or
fish [1], mobile sensor networks, social dynamics [5] and mechanical system
networks in robotics [8].

For agents that evolve on Euclidean spaces of any finite dimension, design and
analysis of consensus algorithms, both in continuous and discrete time exists
in the literature and is well established [2]. The adjacency matrix that
describes the communication topology of the connectivity of the network of
agents is used in generating a linear flow map on the configuration space of
the multi-agent system (which is a direct product of the configuration space
of each agent), called the Laplacian flow in continuous-time. The Laplacian
flow is designed such that the state of the system, starting from any initial
condition, converges asymptotically ( exponentially for linear systems) to the
consensus subspace where all agents share the same state. In continuous time,
first-order and second-order Laplacian flow on Euclidean spaces serve as
standard algorithms for consensus for identical agents evolving on Euclidean
spaces, as extensively analyzed in [2]. They are recalled in a future section.
The central theme is that each agent has a velocity or acceleration that is
directly proportional to a weighted sum of its displacement from each of its
neighbors. So, a spring like force is created where each agent is pulled
towards the position of all of its neighbors. This forces them to eventually
attain consensus.

We refer to agents evolving on the circle as oscillators. Oscillator phase
consensus and velocity synchronization has also been extensively observed,
analyzed and studied ever since the observation by Huygens [10] that two
pendulum clocks hung in the same frame eventually go exactly $180^{\circ}$ out
of step. Excellent surveys about oscillator synchronization can be found in
[23] , [2] and [7] . Once again, the theme is the same. Each agent has two
components. A constant natural angular velocity with which it wants to
maintain and, an angular velocity that is directly proportional to a weighted
sum of the sines of its angular separation from each of its neighbors. So, a
spring like force is created where each agent is pulled towards the angle of
all of its neighbors. This forces them to eventually attain consensus. In case
of second-order agents with no intrinsic preference for any angular velocity,
the consensus term alone appears as an acceleration along with a dissipative
damping.

One notes that both the Euclidean space and the unit circle are Lie groups
where one can sensibly define an inter-agent error in terms of the difference
in linear or angular displacement between two agents. So, one is tempted to
ask if these results can be unified and extended to a general theory of
consensus on Lie groups, where one can define a left (or right) invariant
error between two agents, whose deviation from identity, captures the degree
of separation between them. There have been many attempts to generalize this
theory of consensus and formations to such non-Euclidean, non-circular spaces
[21]. For vehicular and rigid body systems, the consensus happens on
$SO(n),SE(n)$, where $n=2,3$. There is a huge body of work that deals with
consensus on each of these individual spaces separately. However, a common and
elegant geometric framework to capture all these theories under a single
umbrella is wanting, not only for mathematical completeness and elegance but
also to give more insights into the nature of the problem.

There are also generalizations of consensus to Riemannian manifolds [25] but
these turn out to lack any elegant structure and involve intense computation
of the parallel transport map which is not just involved but is also not
globally defined. Lie groups provide a nice framework that are neither too
general like Riemannian manifolds nor too special like Euclidean spaces or
tori. They are generic enough to cover a wide range of systems, especially
aerospace and mechanical systems, but also have enough structure to generalize
the geometric insights of the Laplacian flow and oscillator synchronization
directly. In [20], consensus on compact Lie groups is studied using a
generalization of the mean to Lie groups. A unified theory for consensus and
coordinated motion in Lie groups is presented in [19], but this does not
handle first-order consensus, second-order consensus and velocity
synchronization together in a unified framework, and insights into tangible
mechanical interpretations, such as being driven by a spring-like potential
energy between agents, are absent.

These developments prompted the authors of this article to develop a theory
that directly builds on the Laplacian flow and coupled oscillator theory on
Lie groups. A Lie group with a bi-invariant metric is considered and a
preliminary generalization of Laplacian flow to such Lie groups was done in
[22]. Here, the authors used gradients of a special class of potential
functions on Lie groups, and the left-invariant inter-agent errors to directly
generalize the second-order Laplacian flow and oscillator consensus to Lie
groups with a bi-invariant metric. But the equilibrium analysis and stability
convergence was only presented for a special communication structure - the
line graph - where an agent $i$ is connected to just agents $i-1$ and $i+1$.
The present work is built upon that previous preliminary work and contains the
following significant additions:

  1. 1.

A unified geometric theory for first-order and second-order consensus, and
velocity synchronization on Lie groups admitting a bi-invariant metric is
presented and the stability analysis of all of them are carried in a united
manner, using special classes of potential functions on Lie groups (named
$G$-Polar Morse functions) that mimic the potential energy of a spring and
also which are compatible with the group structure.

  2. 2.

The consensus equilibrium for first and second-order consensus is proven to be
locally exponentially stable for any undirected, weighted, connected graph.

  3. 3.

For connected trees, the consensus equilibrium is shown to be asymptotically
stable with an almost global domain of attraction.

  4. 4.

A necessary condition for existence of synchronous solution is presented for
velocity synchronization dynamics, when each agent has a non-uniform natural
velocity.

  5. 5.

Sufficient conditions for the existence of velocity synchronous solutions are
presented for various special graphs like stars, line graphs and trees.

  6. 6.

Velocity synchronous solutions are guaranteed to exist when the difference in
the natural velocities of the agents are sufficiently small in magnitude.

  7. 7.

Any synchronization equilibrium with inter-agent errors at steady-state that
are in some neighborhood $U$ (explicitly characterized in the following
sections) of identity , is shown to be locally exponentially stable for any
connected graph.

##  2 Mathematical Preliminaries

Let $\mathbb{R}$ denote the set of real numbers, $\mathbb{R}_{+}$, the set of
non-negative real numbers. The cardinality of a finite set $A$ is denoted by
$|A|$. Let ($V,\langle.\rangle$) be an inner product space. Denote by $||v||$,
the norm of a vector $v$ induced by the inner product. Let $T:V\rightarrow V$
be a linear operator. The operator $T$ is said to be symmetric if it satisfies
for all $v,w\in V$, $\langle w,Tv\rangle=\langle v,Tw\rangle$ and is said to
be skew-symmetric if it satisfies for all $v,w\in V$, $\langle
w,Tv\rangle=-\langle v,Tw\rangle$. Then, we have the following result. It then
follows that the spectrum (set of eigen values of an operator) of a symmetric
operator consists of real numbers and the spectrum of a skew-symmetric linear
operator consists of purely imaginary numbers. An important result from linear
algebra is reviewed.

###### Theorem 1

[9] Let $S$ be a linear transformation in an inner product space such that
$S=S_{sym}+S_{sks}$ where $S_{sym}$ is a symmetric operator and $S_{sks}$ is a
skew-symmetric operator. Then, $S$ has its spectrum in the closed (or
respectively open) right-half of the complex plane if and only if $S_{sym}$ is
positive semi-definite (or respectively positive-definite) - that is, all of
the real eigen values of $S_{sym}$ are non-negative (or respectively
positive).

That is, the stability of a dynamical system can be inferred by just
investigating the stability of its symmetric part. The addition of a skew-
symmetric matrix to a stable symmetric matrix does not affect its stability.
The spectrum still remains in the left-half of the complex plane if it
originally were so, to begin with.

As a Corollary, noting that a matrix with all of its eigen-values in open
right-half of the complex plane has full rank, we note that adding a skew-
symmetric matrix to a symmetric positive-definite matrix, maintains its full
rank.

###  2.1 Graph Theoretic Preliminaries

A weighted undirected graph $\mathcal{G}$, is defined as a finite set of
vertices , denoted by $\mathcal{V}=\\{1,2,\cdots,n\\}$, and a weight function
$\mathcal{W}:\mathcal{V}\times\mathcal{V}\rightarrow\mathbb{R}_{+}$ such that

  * •

$\mathcal{W}$ is symmetric, that is, $\mathcal{W}(i,j)=\mathcal{W}(j,i)\hskip
8.53581pt\forall\hskip 2.84526pti,j$.

  * •

$\mathcal{W}_{ii}=0$.

The symmetric matrix $A$ whose entries are defined as
$A=[a_{ij}]:=[\mathcal{W}(i,j)]$ is called the adjacency matrix. The degree of
a node $i$ is defined as $deg(i)=\sum_{j\neq i}a_{ij}$. From now on, we will
assume we have a weighted undirected symmetric graph whose adjacency matrix is
symmetric .

The following basic definitions from graph theory are recalled:

  * •

A distinct pair of vertices $(i,j)$ is called an edge if $a_{ij}>0$.

  * •

A neighbor of a vertex $i$ is another vertex $j$ such that $(i,j)$ is an edge.

  * •

The degree of a node $i$ is the number of edges that connect the node $i$.
i.e. Degree of $i=\big{|}\\{j\hskip 5.69054pt|\hskip 2.84526pti<j,\hskip
2.84526pt(i,j)\hskip 2.84526pt\text{is an edge}\\}\big{|}$

  * •

A path between two vertices $(i,j)$ is a sequence of pairs of vertices
$(i=k_{0},k_{1}),(k_{1},k_{2}),\ldots,(k_{n-1},k_{n}=j)$ such that each
$(k_{i},k_{i+1})$ is an edge.

  * •

A path is called a cycle if the initial and final vertices coincide.

  * •

A graph $\mathcal{G}$ is said to be connected if there exists a path between
any two distinct vertices.

  * •

A graph $\mathcal{G}$ is called a tree if it does not have cycles. A node in a
tree is called a leaf if it has degree 1.

The following facts about trees are recalled as they are used in a forthcoming
section.

###### Theorem 2

Every tree has at least one leaf. The graph formed by removing the leaves of a
connected tree (along with their corresponding edges) is again a connected
tree or empty.

Another related matrix of equal importance for a graph is the Laplacian matrix
$L$ that is defined for a symmetric adjacency matrix $A$ as $L:=O-A$ where $O$
is diagonal matrix whose diagonal entries are defined as $[O]_{ii}:=deg(i)$.
The following theorem establishes the relation between the spectral properties
of the Laplacian matrix and the connectivity of the graph. Note that the
Laplacian matrix being symmetric, always has real eigen values and all of them
can be shown to be non-negative (refer [2]).

###### Theorem 3

Let $A$ be a symmetric matrix with non-negative weights and $L=O-A$. The
following hold:

  * •

The graph described by $A$ is connected if and only if the second smallest
eigen value of $L$, denoted by $\lambda_{2}(L)$, is strictly positive.

  * •

If the graph is connected and if
$\textbf{1}:=\begin{bmatrix}1&1&\cdots&1\end{bmatrix}_{1\times n}^{T}$, then
$Lx=0\Leftrightarrow x\in span\\{\textbf{1}\\}$.

Another important matrix of interest is the incidence matrix $B$. For this to
be defined, two things need to be done. First, the edges of the graph have to
be labelled arbitrarily, say $e=1,2,\cdots,|E|$ (the notation for the number
of edges $|E|$ has vertical lines surrounding the letter E so that it may not
be confused with the quantity energy $E$ that will be defined in a future
section). Second, an arbitrary direction has to be assigned to each edge such
that every edge $e=(i,j)$ should be thought of as directed from $i$ to $j$ or
from $j$ to $i$. The direction labelled to a given edge can be arbitrary but
once assigned, has to be consistent. Note that if a graph is connected with
$n$ nodes, it will at least have $n-1$ edges. i.e. $|E|\geq n-1$.

Then, the incidence matrix $B$ is a $n\times|E|$ matrix which is defined as

$\displaystyle B_{ie}$ $\displaystyle=+1,\hskip 8.53581pt\text{if node $i$ is
source of the edge $e$}$ $\displaystyle B_{ie}$ $\displaystyle=-1,\hskip
8.53581pt\text{if node $i$ is the sink of the edge}$ $\displaystyle B_{ie}$
$\displaystyle=\hskip 2.84526pt0,\hskip 8.53581pt\text{otherwise}.$

Let $D$ be a $|E|\times|E|$ diagonal matrix whose $(e,e)^{th}$ entry is
defined as

$\displaystyle D_{ee}$ $\displaystyle=a_{ij},\hskip 8.53581pt\text{$(i,j)$ are
the nodes for the edge $e$}.$

Then, the incidence matrix is related to the Laplacian matrix as stated in the
following theorem.

###### Theorem 4

$\displaystyle L=BDB^{T}.$ (1)

Also, another Theorem related to the rank of $L$ and the rank of $B$ is stated
below. The proofs of both the Theorems are standard and can be found in [2].

###### Theorem 5

The following statements are equivalent

  * •

the graph $\mathcal{G}$ is connected.

  * •

$rank(L)=n-1$.

  * •

$rank(B)=n-1$.

Note that the factorization of the Laplacian matrix as $L=BDB^{T}$ where $D$
is a diagonal matrix of positive diagonal entries renders the positive semi-
definiteness of $L$ (and hence the non-negativity of its eigen values), very
immediate and transparent.

###  2.2 Geometric and Group Theoretic Preliminaries

Denote by $M$, a smooth manifold and by $T_{p}M$ and $T_{p}^{*}M$, the tangent
and co-tangent spaces at a point $p\in M$. If $M$ is equipped with a smoothly
varying metric , denoted by $\mathbb{I}$, then $(M,\mathbb{I})$ is called a
Riemannian Manifold. Denote by $\nabla$, the unique symmetric Levi-Civita
connection induced on $M$ by the metric $\mathbb{I}$. For a smooth real-valued
function $V$, its differential at a point $p$ is denoted by $dV_{p}$ and its
gradient, by $grad_{p}(V)$. Given a smooth map between two manifolds
$F:M\rightarrow N$, its derivative map at a point $m\in M$ is denoted by
$DF_{m}:T_{m}M\rightarrow T_{F(m)}N$.

Let a manifold be equipped with a Lie group structure with the group operation
$*$ , group inversion $()^{-1}$ and group identity $e$. A Lie group is called
Abelian if the group operation is commutative. We also now assume henceforth
unconditionally that all Lie groups in this work are assumed to be connected.
It is customary to denote the Lie group by $G$ and an arbitrary point in it by
$g$. The tangent space of a Lie group at its identity is defined to be the Lie
algebra and is denoted by $\mathfrak{g}$. Let the dual of the Lie algebra be
denoted by $\mathfrak{g}^{*}$.

Denote by $ad_{g}$, the adjoint $ad_{g}:G\rightarrow G$ defined as
$ad_{g}(h)=g*h*g^{-1}$.

Let $L_{g}$ denote the left translation map, denoted by $L_{g}:G\rightarrow G$
and defined as $L_{g}(h)=g*h$. Since $L_{g}$ is a diffeomorphism on $G$, this
enables us to transport all tangent and cotangent vectors to $\mathfrak{g}$
and $\mathfrak{g}^{*}$. Similarly, the right translation map
$R_{g}:G\rightarrow G$, defined as $R_{g}(h)=h*g$, also is a diffeomorphism of
$G$ and likewise enables one to transport all tangent and co-tangent vectors
to $\mathfrak{g}$ and $\mathfrak{g}^{*}$.

If $X\in T_{g}G$, then it can be left translated to $\mathfrak{g}$ , denoted
by $g^{-1}*X$ which is defined as $g^{-1}*X:=(DL_{g^{-1}})_{g}X$. Similarly,
it can also be right translated to $\mathfrak{g}$ , denoted by $X*g^{-1}$
which is defined as $X*g^{-1}:=(DR_{g^{-1}})_{g}X$. Hence, now we can uniquely
identify every tangent vector in $\mathfrak{g}$, every cotangent vector in
$\mathfrak{g}^{*}$ and any tensor in Cartesian products of $\mathfrak{g}$ and
$\mathfrak{g}^{*}$ (through the left or right translation map). When there is
an inner product on $\mathfrak{g}$, it is possible to uniquely induce a metric
on $G$ by left translations. Such a metric is called left-invariant and it
satisfies $\mathbb{I}_{g}(X,Y)=\mathbb{I}_{h*g}(h*X,h*Y)$ for all $g,h\in G$
and for all $X,Y\in T_{g}G$. It is also likewise possible to induce a metric
on $G$ by right translations. Such a metric is called right-invariant and it
satisfies $\mathbb{I}_{g}(X,Y)=\mathbb{I}_{g*h}(X*h,Y*h)$ for all $g,h\in G$
and for all $X,Y\in T_{g}G$. A metric that is both left and right invariant is
called a bi-invariant metric. Hereafter, it is assumed that the metric
$\mathbb{I}$ on a Lie group is bi-invariant. For details regarding any result
quoted so far, refer [3] or [14].

The following results give the necessary and sufficient condition for the
existence of a bi-invariant metric on a Lie group $G$.

###### Theorem 6

[13] A Lie group $G$ admits a bi-invariant metric if and only if it is a
Cartesian product of a compact Lie group and an Euclidean space . i.e.
$G=G_{C}\times\mathbb{R}^{p}$ where $G_{C}$ is a compact Lie group and
$\mathbb{R}^{p}$ is the Euclidean space, considered as a group under vector
addition.

In a Lie group with a bi-invariant metric, the metric is ad-invariant as well,
that is, invariant under adjoint operator. This property is called ad-
invariance, which is

$\displaystyle\mathbb{I}_{g}(X_{g},Y_{g})$
$\displaystyle=\mathbb{I}_{h*g*h^{-1}}(h*X_{g}*h^{-1},h*Y_{g}*h^{-1})$
$\displaystyle=\mathbb{I}_{h*g*h^{-1}}(ad_{h}X_{g},ad_{h}Y_{g}).$ (2)

A nice compatibility between the geometry of the group and its algebra ensues
if there exists a bi-invariant metric. Some of them are presented here.

###### Theorem 7

[13]. If a Lie group $G$ admits a bi-invariant metric, then the integral
curves of left/right invariant vector fields are precisely the geodesics under
the bi-invariant metric. In other words, the one-parameter subgroups and the
geodesics through $e$ coincide. In other words, the Riemannian geodesic
exponential coincides with the group exponential (loosely, the one parameter
subgroups exp(tX) are the straight lines passing through $e$ with direction
$X$).

Relations between the Lie bracket operation and the covariant derivative also
ensue. A couple of them are stated below.

###### Theorem 8

[13] In a Lie group $G$ with a bi-invariant metric with its correspnding
induced Levi-Civita connection $\nabla$, if $X,Y$ are two left invariant
vector fields, then

$\displaystyle\nabla_{X}Y=\frac{1}{2}[X,Y].$ (3)

###### Theorem 9

[13]

$\displaystyle\langle Z,[X,Y]\rangle=\langle X,[Y,Z]\rangle=-\langle
X,[Z,Y]\rangle.$ (4)

As a Corollary of both the theorems in Eqns (3)-(4), we have

###### Corollary 1

Given a vector $Y\in\mathfrak{g}$, The linear map
$L_{Y}:\mathfrak{g}\rightarrow\mathfrak{g}$ defined as

$\displaystyle L_{Y}(X):=\nabla_{X}Y=\frac{1}{2}[X,Y].$ (5)

is skew-symmetric. In other words, it satisfies for any $Z\in\mathfrak{g}$,

$\displaystyle\langle Z,L_{Y}(X)\rangle=-\langle X,L_{Y}(Z)\rangle.$ (6)

(or equivalently, the matrix representation of $L_{Y}$ in an orthonormal basis
of $\mathfrak{g}$ is skew-symmetric).

Proof:

$\displaystyle\langle Z,L_{Y}(X)\rangle$ $\displaystyle=\frac{1}{2}\langle
Z,[X,Y]\rangle=-\frac{1}{2}\langle X,[Z,Y]\rangle$ from (4)
$\displaystyle=-\frac{1}{2}\langle X,\nabla_{Z}Y\rangle=-\frac{1}{2}\langle
X,L_{Y}(Z)\rangle.$

###  2.3 Morse Theoretic Preliminaries

Let $F:M\rightarrow\mathbb{R}$ be a smooth scalar function on a manifold $M$.
A point $c\in M$ is called a critical point of $F$ if the differential at $c$
vanishes, that is $dF_{c}=0$. A critical point $c$ is called non-degenerate,
if the Hessian matrix of $F$ in any local coordinate system is full rank (or
equivalently, does not have zero as any of its eigen values) [13]. Note that
as the Hessian matrix is symmetric for any scalar function, its eigen values
are all real. So, if non-zero, they must be either positive or negative.

###### Definition 1

A function $F$ is called a Morse function if all of its critical points are
non-degenerate

The following are some important results about Morse functions.

###### Theorem 10

[13] Let $F$ be a Morse function and $c\in M$ be a critical point in a
manifold $M$ of dimension $m$ and assume $F(q)=0$ by adding an appropriate
constant to $F$. Let $p$ eigen values of the Hessian matrix of $F$ at $c$ be
positive and the remaining $m-p$, negative. Then, there exists a local
coordinate system $(x_{1},x_{2},\ldots,x_{m})$ around $c$ such that $c$ is in
the origin and $F$ in that coordinate system is
$F(x_{1},x_{2},\ldots,x_{m})=x_{1}^{2}+x_{2}^{2}+\cdots
x_{p}^{2}-x_{p+1}^{2}-x_{p+2}^{2}-\cdots-x_{m}^{2}$

As a corollary of Theorem 10, we have that if $c$ is a local minimum, then
$p=m$ and one can render $F$ as $F(x)=x_{1}^{2}+x_{2}^{2}+\cdots+x_{m}^{2}$ in
some local coordinates around $p$ (since a quadratic function has origin as
its minimum if and only if all its coefficients are positive). As an easy
corollary of the above Theorem 10, we state another result that follows.

###### Corollary 2

[13] The critical points of a Morse function $F$ are isolated. In other words,
if $c$ is a critical point, there exists a neighborhood of $c$ such that $c$
is the only critical point in that neighborhood (there can be no continuum of
critical points for a Morse function). If $M$ is compact, this implies that
the number of critical points are finite.

For control problems involving regulation to a point $p\in M$, one is
interested in a special class of Morse functions, called Polar Morse
functions.

###### Definition 2

A function $F$ is called Polar Morse function based at point $e$, if it
satisfies the following properties:

  * •

$F$ is Morse.

  * •

$F$ attains its global minimum at $e$ (whose value can be assumed as zero by
translation).

  * •

All the other critical points (except $e$) are not local minima (their
Hessians have atleast one negative eigen value).

The polar Morse function based at $e$ is ideal for the control problem of
regulation to $e$. Since $e$ is the global minimum of $F$, going to $e$ is
equivalent to minimizing $F$. Since $F$ has no other local minima, one can use
the negative gradient of $F$ and do gradient descent to steer a point to the
global minimum $e$. It has been proven by Morse in [18] that such polar Morse
functions always exist on any smooth manifold. They are also proven to exist
on any smooth compact manifolds with boundary in [15].

Now we state another theorem related to the asymptotic behavior of gradient
dynamical systems which will be very helpful in the forthcoming sections.

###### Theorem 11

[2] Let $F$ be a smooth scalar function on a smooth Riemannian manifold $M$
and let $k_{P},k_{D}>0$. Consider a first-order or second-order negative
gradient flow given by

$\displaystyle\dot{\gamma}$ $\displaystyle=-k_{P}grad(F),$ (7)
$\displaystyle\nabla_{\dot{\gamma}}\dot{\gamma}$
$\displaystyle=-k_{P}grad(F)-k_{D}\dot{\gamma},$ (8)

respectively. If all the sublevel sets of $F$ are compact (this is true
trivially if $M$ itself is compact), then

  * •

any trajectory $\gamma(t)$ of (7) satisfies

$\displaystyle\lim_{t\rightarrow\infty}\gamma(t)=c^{*}.$

  * •

any trajectory $(\gamma(t),\dot{\gamma}(t))$ of (8) satisifies

$\displaystyle\lim_{t\rightarrow\infty}(\gamma(t),\dot{\gamma}(t))=(c^{*},0).$

where $c^{*}$ is a critical point of the function $F$, that is,
$grad_{c^{*}}(F)=0$.

###  2.4 Review of the Centre Manifold Emergence Theorem

In this section, we recollect the centre manifold emergence theorem that is
crucial in the stability analyses that ensue in future sections. Let us first
recapitulate the notion of the Jacobian of a vector field in a Riemannian
manifold.

If $W$ is a smooth vector field on a Riemannian manifold $G$, then the
Jacobian of $W$ at a point $p\in G$ is defined as a linear map
$J_{p}W:T_{p}G\rightarrow T_{p}G$ as follows:

$\displaystyle J_{p}W(v)$ $\displaystyle:=(\nabla_{v}W)(p),$ (9)

where $v\in T_{p}G$.

This induces a bilinear form $J:T_{p}G\times T_{p}G\rightarrow\mathbb{R}$ as
follows:

$\displaystyle J_{p}W(v_{1},v_{2}):=\langle
v_{2},(\nabla_{v_{1}}W)_{p}\rangle.$ (10)

With this, we state the center manifold emergence theorem.

###### Theorem 12

[12] (Center-manifold emergence theorem) Let $W$ be a smooth vector field in a
Riemannian manifold $G$ and let $g^{*}$ be any of its equilibrium point
($W(g^{*})=0$). Let the Jacobian of $W$ at $g^{*}$ be such that their eigen
values are either zero or with negative real parts. Let $p$ of the eigen
values of $J_{g^{*}}W$ be zero and the remaining eigen values have strictly
negative real part. Let $\nu$ be the maximum real part of the non-zero eigen
values. Then, there exists a locally-unique $p$-dimensional invariant
submanifold passing through $g^{*}$ and tangential to $ker(J_{p}W)$ called the
centre manifold $M_{cen}$ such that in a neighborhood $N_{cen}$ around
$g^{*}$, any integral curve of the vector field $W$ starting in $N_{cen}$
exponentially converges to an invariant solution in $M_{cen}\cap N_{cen}$ with
rate $\nu$.

##  3  The notion of G-polar Morse Functions

When the manifold is a Lie group and the objective is to achieve consensus, we
want polar Morse functions to satisfy additional group theoretic properties.
The importance of these properties will be evident in the coming sections. We
name such class of functions on a Lie group $G$ as $G-$Polar Morse.

###### Definition 3

A function $V$ on a Lie group is called $G-$Polar Morse if it satisfies the
following properties:

  * •

$V$ is a polar Morse function based at identity $e$ of $G$

  * •

$\forall g\in G$, $V(g)=V(g^{-1})$ (inversion symmetry)

  * •

The set of all critical points, denoted by $C:=\\{g\in G\hskip
8.53581pt|\hskip 2.84526ptdV_{g}=0\\}$ is a discrete subgroup of $G$

  * •

The left transported and right transported gradient vectors in the Lie algebra
$\mathfrak{g}$ coincide. That is,

$\displaystyle g^{-1}*grad_{g}V=grad_{g}V*g^{-1}$ (11)

(Note that this property is trivially satisfied for Abelian Lie groups like
$\mathbb{R}^{n}$ and $\mathbb{S}^{1}$ as the left translation and right
translation maps coincide).

In the next section, we will see why such a notion is important for consensus
theory on Lie group. In Table 1, examples of such $G$-Polar Morse functions on
commonly encountered Lie groups are listed. One can easily verify that the
given functions in $\mathbb{R}^{n}$ and $\mathbb{S}^{1}$ satisfy all the
required properties in Definition 3. As an illustrative example, we comment on
the properties just for the $SO(3)$ case.

  * •

$V(R)=trace(I-R)$ is a polar Morse function.

  * •

$V(R)=trace(I-R)=trace(I-R^{T})=V(R^{T})=V(R^{-1})$ as for orthogonal
matrices, $R^{T}=R^{-1}$.

  * •

The four critical points can be verified easily to form a subgroup of $SO(3)$.

  * •

One can verify that the gradient of $V$ at $R$, when left and right
translated, coincide and equals
$\frac{1}{2det(\mathbb{I})}\mathbb{I}(R-R^{T})\mathbb{I}$.

It turns out that even for the higher dimensional $SO(n)$, $V(R)=trace(I-R)$
is a $G-$polar Morse function. And in the unitary group $U(n)$, the function
$V(R)=trace(I-Re[R])$ (where $Re$ stands for the real part) is a $G$-polar
Morse function as well. The issue of the guarantee of existence of such
$G$-polar Morse functions on any arbitrary compact Lie group is discussed in
the conclusion section.

Lie Group | Morse Function | Critical Points
---|---|---
($\mathbb{R}^{N},+$) | $\frac{1}{2}||x||^{2}$ | $\\{\textbf{0}\\}$
($\mathbb{S}^{1},+_{2\pi}$) | $1-\cos\theta$ | $\\{\textbf{0},\pm\pi\\}$
($SO(3),.$) | $\mathrm{trace}(I-R)$ | $\\{\textbf{I},\mathrm{diag}(-1,-1,1),$
|  | $\mathrm{diag}(1,-1,-1),$
|  | $\mathrm{diag}(-1,1,-1)\\}$
Table 1: Examples of $G$-Polar Morse functions

Let the gradient vector $grad$ of a smooth scalar function $V$ on $G$, when
left translated to the Lie algebra, be denoted by $\mathfrak{grad}V$, be
referred to as the left Lie gradient, which is
$\mathfrak{grad}_{g}V(X):=grad_{g}V(g*X)$. Then, some important properties of
$G$-Polar Morse functions ensue.

###### Lemma 1

If $V$ is a G-polar Morse function, then its left gradient at a point $g$ in
the Lie algebra, is adjoint invariant under $ad_{g}$. Mathematically,
$\mathfrak{grad}_{g}V=g*\mathfrak{grad}_{g}V*g^{-1}$.

Proof:

The left translated gradient and the right translated gradient of a $G$-polar
Morse function, coincide at any point $g$. So,

$\displaystyle\mathfrak{grad}_{g}V$ $\displaystyle=g^{-1}*grad_{g}(V)$ (12)
and $\displaystyle\mathfrak{grad}_{g}V$ $\displaystyle=grad_{g}(V)*g^{-1}.$
(13)

From (12), we get $grad_{g}V=g*\mathfrak{grad}_{g}V$ and substituting it in
(13), we have

$\displaystyle\mathfrak{grad}_{g}V=g*\mathfrak{grad}_{g}V*g^{-1},$

and hence the result ensues.

Let us recollect some basic results in Lie groups that will be frequently used
in the forthcoming sections.

###### Lemma 2

Let $g(t)$ be a smooth curve on $G$ with its velocity $\dot{g}(t)$. Then,
$\frac{d}{dt}g^{-1}(t):=\dot{g}^{-1}(t)=-g^{-1}*\dot{g}(t)*g^{-1}$.

###### Lemma 3

$\displaystyle\frac{d}{dt}(g_{i}*g_{j})=g_{i}*\dot{g}_{j}+\dot{g}_{i}*g_{j}$
(14)

###### Theorem 13

For a $G-$Polar Morse function, we have

$\displaystyle g^{-1}*grad(V)_{g}=-g*grad(V)_{g^{-1}}$ (15)

or equivalently

$\displaystyle\mathfrak{grad}_{g}V=-\mathfrak{grad}_{g^{-1}}V.$ (16)

The physical significance of (16) is that the gradients at $g$ and $g^{-1}$
are negatives of each other, when viewed in the Lie algebra.

Proof:

Consider an arbitrary tangent vector at $g$ that is the velocity of a curve,
that is denoted by $\dot{g}$. From the property of inversion symmetry, we have

$\displaystyle V(g)$ $\displaystyle=V(g^{-1}).$ (17)

Taking the time derivative of $V$ along the curve $g(t)$ and using chain rule,
we have

$\displaystyle\langle grad(V)_{g},\dot{g}\rangle$ $\displaystyle=\langle
grad(V)_{g^{-1}},\dot{g^{-1}}\rangle,$ (18)
$\displaystyle\Longrightarrow\langle grad(V)_{g},\dot{g}\rangle$
$\displaystyle=\langle grad(V)_{g^{-1}},-g^{-1}*\dot{g}*g^{-1}\rangle.$ (19)

By left invariance of the metric, translating all vectors to the Lie algebra
through left translation by $g$ on LHS of (19) and by $g^{-1}$ on RHS of (19),
we get

$\displaystyle\langle g^{-1}*grad(V)_{g},g^{-1}*\dot{g}\rangle=-\langle
g*grad(V)_{g^{-1}},\dot{g}*g^{-1}\rangle$ (20)

But

$\displaystyle\dot{g}*g^{-1}=(g*g^{-1})*\dot{g}*g^{-1}=$ $\displaystyle
g*(g^{-1}*\dot{g})*g^{-1}=ad_{g}(g^{-1}\dot{g}).$

Denoting $g^{-1}*\dot{g}\in\mathfrak{g}$ by $X$, we have

$\displaystyle\langle g^{-1}*grad(V)_{g},X\rangle=-\langle
g*grad(V)_{g^{-1}},ad_{g}X\rangle.$ (21)

Hence,

$\displaystyle\langle\mathfrak{grad}_{g}V,X\rangle=-\langle\mathfrak{grad}_{g^{-1}}V,ad_{g}X\rangle.$
(22)

Taking $ad_{g^{-1}}$ for both vectors in the RHS of (22), and using the ad-
invariance (Lemma 1), we have,

$\displaystyle\langle\mathfrak{grad}_{g}V,X\rangle$ $\displaystyle=-\langle
ad_{g^{-1}}\mathfrak{grad}_{g^{-1}}V,\overbrace{ad_{g^{-1}}ad_{g}}^{\text{=identity}}X\rangle$
$\displaystyle=-\langle ad_{g^{-1}}\mathfrak{grad}_{g^{-1}}V,X\rangle$
$\displaystyle=-\langle\mathfrak{grad}_{g^{-1}}V,X\rangle,$ (23)

which yields the requires result.

The result is visualized in Figure 1.

Figure 1: Illustration of $\mathfrak{grad}_{g}V=-\mathfrak{grad}_{g^{-1}}V$

##  4 Group Theoretic Insights:
Review of Laplacian Flow and Coupled Oscillators

In this section, the Laplacian flow and coupled oscillators are reviewed and
are cast in the $G-$polar Morse theoretic framework, proposed in Section 3.
This enables one to generalize the theory of consensus and synchronization to
general Lie groups admitting a bi-invariant metric and a $G$-polar Morse
function.

###  4.1 Laplacian Flow

The Laplacian flow is a standard algorithm for consensus in Euclidean space.
Denoting by $x_{i}$, the configuration of the $i^{th}$ agent in a Euclidean
space $\mathbb{R}^{N}$, we have the following Laplacian flows for consensus

First-Order Laplacian Flow:
$\displaystyle\dot{x}_{i}=-k_{P}\sum_{j=1}^{n}a_{ij}(x_{i}-x_{j})$ (24)
Second-Order Laplacian Flow:
$\displaystyle\ddot{x}_{i}=-k_{P}\sum_{j=1}^{n}a_{ij}(x_{i}-x_{j})-k_{D}\dot{x}_{i}$
(25)

where $k_{P},k_{D}>0$.

The crucial component of these algorithms is the inter-agent consensus term
$(x_{i}-x_{j})$. It steers the agent $i$ towards agent $j$.

The important observation one notes here is that by considering the $G$-polar
Morse function on Euclidean space as $V=\frac{1}{2}||x||^{2}$ , the consensus
term can be written as

$\displaystyle(x_{i}-x_{j})$ $\displaystyle=grad_{i}V(x_{i}-x_{j}).$ (26)

This is natural because the negative gradient of a polar Morse function like
$V$ drives the flow towards the minimum of $V$, which happens when
$x_{i}-x_{j}=0$ or $x_{i}=x_{j}$.

Both the first and second-order Laplacian flow lead to consensus from all
initial conditions if the graph is connected and the gains $k_{P},k_{D}$ are
strictly positive [2].

The general intuition as to why this is true can be explained by a mechanical
interpretation. Each edge with an interconnection $a_{ij}>0$ can be viewed as
a spring connecting agents $i$ and $j$ with a spring constant $a_{ij}$ and
with the standard quadratic potential energy
$a_{ij}V(x_{i}-x_{j})=a_{ij}\frac{1}{2}||x_{i}-x_{j}||^{2}$. The total
potential energy of the system is given by
$V_{TOT}=\frac{1}{2}\sum_{i,j}a_{ij}V(x_{i}-x_{j})$ (since each spring is
counted twice, there is a half in the front). Since the network is connected,
the system arrives at a consensus due to the effect of the spring, and the
damping term $\gamma_{D}\dot{x}_{i}$ for second-order agents.

The entire dynamics in (24)-(25) can be rewritten as a gradient dynamical flow
as

$\displaystyle\dot{x}_{i}$ $\displaystyle=-k_{P}grad_{i}(V_{TOT}),$ (27)
$\displaystyle\ddot{x}_{i}$
$\displaystyle=-k_{P}grad_{i}(V_{TOT})-k_{D}\dot{x}_{i}.$ (28)

Formally, it has been shown that

###### Theorem 14

[2] Subject to the following assumptions

  * •

$k_{P},k_{D}>0$,

  * •

the graph describing the agents are undirected and connected,

  * •

the adjacency matrix is symmetric,

the first/second-order Laplacian flow starting from any initial condition,
satisfies for all $i,j$,

$\displaystyle\lim_{t\rightarrow\infty}\dot{x}_{i}(t)$ $\displaystyle=0,\hskip
5.69054pt$ $\displaystyle\lim_{t\rightarrow\infty}x_{i}(t)$
$\displaystyle\hskip 5.69054pt\text{exists},$
$\displaystyle\lim_{t\rightarrow\infty}x_{i}(t)$
$\displaystyle=\lim_{t\rightarrow\infty}x_{j}(t)\hskip 8.53581pt\hskip
5.69054pt.$

###  4.2 Coupled Oscillators: Consensus on the circle

We now consider the standard model of coupled identical oscillators with zero
natural frequency. Let $\theta\in\mathbb{R}$ be the standard angular
coordinate of the unit circle.

First-Order Coupled Oscillators:
$\displaystyle\dot{\theta}_{i}=-k_{P}\sum_{j=1}^{n}a_{ij}\sin(\theta_{i}-\theta_{j})$
(29) Second-Order Coupled Oscillators:
$\displaystyle\ddot{\theta}_{i}=-k_{P}\sum_{j=1}^{n}a_{ij}\sin(\theta_{i}-\theta_{j})-k_{D}\dot{\theta}_{i}$
(30)

where $k_{P},k_{D}>0$.

For the first-order case and when $a_{ij}=\frac{1}{n}$ for all $i,j$, we have
the Kuramoto oscillator

Kuramoto Oscillator
$\displaystyle\dot{\theta}_{i}=-k_{P}\sum_{j=1}^{n}\frac{1}{n}\sin(\theta_{i}-\theta_{j}).$
(31)

Once again the crucial term for consensus is the inter-agent sinusoidal term
$\sin(\theta_{i}-\theta_{j})$. As mentioned before, this is also the gradient
of a $G$-polar Morse function on the circle. Considering $V=1-\cos\theta$, we
get

$\displaystyle\sin(\theta_{i}-\theta_{j})$
$\displaystyle=grad_{i}V(\theta_{i}-\theta_{j})$ (32) $\displaystyle V$
$\displaystyle=1-\cos\theta.$

The same mechanical intuition can be given with
$a_{ij}(1-\cos(\theta_{i}-\theta_{j}))$ being interpreted as the potential
energy of a spring connecting agents $i$ and $j$ and once again the entire
system can be cast in gradient form by defining
$V_{TOT}=\frac{1}{2}\sum_{i,j}V(\theta_{i}-\theta_{j})$. The systems now
become

$\displaystyle\dot{\theta}_{i}$ $\displaystyle=-k_{P}grad_{i}(V_{TOT}),$ (33)
$\displaystyle\ddot{\theta}_{i}$
$\displaystyle=-k_{P}grad_{i}(V_{TOT})-k_{D}\dot{\theta}_{i}.$ (34)

So we see that both the oscillator dynamics for consensus on $\mathbb{S}^{1}$
and Laplacian flow for consensus on Euclidean space have the same geometric
and group theoretic structure. Here too, the Morse function mimics the
potential energy of a spring (it is minimum at identity, and does not have a
local minimum anywhere else).

Note that the crucial difference from the Euclidean case is that while the
Morse function there had no other critical points apart from the global
minimum at identity, the Morse function on the circle $1-\cos\theta$ has
another critical point which is $\pi$. The set of critical points
$\\{0,\pi\\}$ are a two-element subgroup. This cannot be avoided as
$\theta=\pi$ is the maximum of $V$ and any continuous function on a compact
set like the circle $\mathbb{S}^{1}$ has to have a maximum (this shows that
for compact manifolds, one cannot escape having critical points other than the
global minimum).

####  4.2.1 Comment on the subgroup property of the critical points

We know that in a gradient descent flow, it is possible to converge to a
critical point other than the global minimum. So, in general, at equilibrium,
in addition to the consensus solution $\theta_{i}=\theta_{j}$ for all $i,j$,
we can also have

$\displaystyle\theta_{i}-\theta_{j}\in C=\\{0,\pi\\}.$ (35)

So, in limit, it is possible for the oscillators to be either in consensus
$\theta_{i}=\theta_{j}$ or anti-consensus $\theta_{i}-\theta_{j}=\pi$ with one
another. But it is important that $C$ be a subgroup for (35) to be consistent.
Because,

$\displaystyle\overbrace{\theta_{i}-\theta_{j}}^{\text{$\in
C$}}=\overbrace{(\theta_{i}-\theta_{k})}^{\text{$\in
C$}}+\overbrace{(\theta_{k}-\theta_{j})}^{\text{$\in C$}}.$ (36)

Only if $C$ is a subgroup, the above equation (36) is consistent as the right
hand side is the sum of two elements in $C$ and it has to be remain in $C$ as
the LHS is in $C$. So, $C$ has to be closed under $+$ which is the group
operation in circle. This is required for a transitive closure of the
consensus/anti-consensus relation which is: if agent $i$ is in consensus/anti-
consensus with agent $j$ and if agent $j$ is in consensus/anti-consensus with
agent $k$, then agents $i$ and $k$ are also in consensus/anti-consensus with
each other.

####  4.2.2 Comments on the graph structure

We expect the global minimum (where all the oscillators are in consensus with
each other) to be locally exponentially stable, the anti-consensus solutions
(where some of the oscillators are anti-consensus with the others) to be
unstable, and we would require that there are no other equilibria of the
system (critical points of $V_{TOT}$). This would render the globally minimal
synchronous solution almost globally asymptotically stable. But while the
first two expectations are fulfilled for arbitrary graphs, the third
expectation that there are no other equilibria other than the consensus/anti-
consensus equilibria is not the case for arbitrary graphs. So, the next
following question would be that are the other equilibria that are neither
conesus nor anti-consensus, locally unstable? This is also not true for all
graphs and the cyclic graph with 5 nodes is proven to exhibit an equilibrium
that is locally attracting. For what kinds of graphs, is the consensus
equilibrium, also the only attracting equilibrium (that renders it almost
globally asymptotically stable)? We shall now review the convergence
properties of (29)-(30) under different graph structures.

First let us define some notions related to the geometry of the circle.

###### Definition 4

Let $0\leq\gamma<\pi$

  * •

The arc subset $\bar{\Gamma}_{arc}(\gamma)$ is defined as the set of agent
angles $\theta_{i}$ such that there exists an arc of length $\gamma$ in
$\mathbb{S}^{1}$ containing all the angles $\theta_{i}$. The set
$\Gamma_{arc}(\gamma)$ is defined to be the interior of the set
$\bar{\Gamma}_{arc}(\gamma)$.

  * •

Given a graph $\mathcal{G}$, a cohesive subset $\Delta^{\mathcal{G}}(\gamma)$
is defined as the set of agent angles $\theta_{i}$ such that
$\theta_{i},\theta_{j}$ are contained in an arc of length $\gamma$ if $(i,j)$
is an edge of the graph

We now capture the various notions of synchronization through formal
definitions below.

###### Definition 5

Angles $\theta_{i}(t)$ evolving on $\mathbb{S}^{1}$ are said to be

  * •

phase synchronized if $\theta_{i}(t)=\theta_{j}(t)$ $\forall\hskip 2.84526ptt$
, $\forall\hskip 2.84526pti,j$

  * •

frequency synchronized if $\dot{\theta}_{i}(t)=\dot{\theta}_{j}(t)$ $\forall
t$, $\forall\hskip 2.84526pti,j$

  * •

phase cohesive if $\forall\hskip 2.84526ptt$, either
$\theta_{i}(t)\in\Gamma_{arc}(\gamma)$ or with respect to a graph
$\mathcal{G}$, $\theta_{i}(t)\in\Delta^{\mathcal{G}}(\gamma)$

###### Theorem 15

[7] Consider the dynamic equations (29) or (30) with a connected graph with
symmetric adjacency matrices and $k_{P},k_{D}>0$. Then,

  * •

For all initial conditions $\theta_{i}(0)$, the angles converge to the set of
critical points of $V_{TOT}$.

  * •

If the initial angles are phase cohesive w.r.t some $0\leq\gamma<\pi$, then
the solution remains phase cohesive.

  * •

The consensus solution is locally exponentially stable with an exponent
$-\lambda_{2}(L)\cos(\frac{\gamma}{2})$ for the domain-of-attraction being
chosen as $\Gamma_{arc}(\gamma)$ for any $0\leq\gamma<\pi$.

  * •

The consensus solution is almost globally asymptotically stable (it is the
only attracting equilibrium) for the following graphs

    1. 1.

a tree [4]

    2. 2.

a sufficiently dense graph [24],[17], [16] (in particular, this includes the
complete graph [2], [7]) - the current state of the art is that for a graph of
$n$ nodes, if the degree of each node $d_{i}$ satisfies $d_{i}>0.7889n$ for
all $i$, then the consensus equilibrium is the only attracting equilibrium

It is also known that there are graphs for which almost global asymptotic
stability of the consensus does not hold [26] where there are other attracting
equilibria (or non-consensus local minima of $V_{TOT}$).

###  4.3 Synchronization of Coupled Oscillators

For synchronization of oscillators, we consider the case wherein each
oscillator also has its own natural frequency $\omega_{i}$ apart from having
to arrive at a consensus with other oscillators. In this case, the consensus
dynamics in (29) gets modified by the addition of an extra natural frequency
which becomes

$\displaystyle\dot{\theta}_{i}=\omega_{i}-k_{P}\sum_{j=1}^{n}a_{ij}\sin(\theta_{i}-\theta_{j}),$
(37)

which again can be recast as

$\displaystyle\dot{\theta}_{i}=\omega_{i}-k_{P}\sum_{j=1}^{n}a_{ij}grad_{i}V(\theta_{i}-\theta_{j}).$
(38)

Here each oscillator has two driving velocities: $\omega_{i}$ that makes it
oscillate with its own preset constant angular frequency and another consensus
term that drives it towards matching the state of its neighboring oscillators.
The equilibria of such systems as well have been studied in detail [2]. Let
$\omega_{m}=\frac{1}{n}\sum_{i}\omega_{i}$ (mean natural frequency). Then,
subtracting $\omega_{m}$ both sides and defining
$\Delta\omega_{i}=\omega_{i}-\omega_{m}$, we get

$\displaystyle\dot{\theta}_{i}-\omega_{m}=\Delta\omega_{i}-\sum_{j=1}^{n}a_{ij}\sin(\theta_{i}-\theta_{j}).$
(39)

Let us situate ourselves in a frame that is rotating with the mean angular
velocity $\omega_{m}$. Then in this frame, the oscillators evolve by the RHS
of (39).

It is intuitvely expected that if the coupling strength is much larger than
$\Delta\omega_{i}$, the oscillators should get in sync eventually and if the
coupling strength is much smaller than $\Delta\omega_{i}$, the oscillators
should not get in sync. Formally one can show the following result:

###### Theorem 16

[7] Define

$\displaystyle||\Delta\omega||_{2}:=\sqrt{\frac{1}{2}\sum_{i,j=1}^{n}(\Delta\omega_{i}-\Delta\omega_{j})^{2}},$
(40)

and $\lambda_{2}(L)$ as the second smallest eigen value of the symmetric
matrix $L=O_{n\times n}-A$. If $k_{P}\lambda_{2}(L)>||\Delta\omega||_{2}$,
then frequency synchronization is achieved for all oscillators asymptotically
to the mean frequency $\omega_{m}$ if their initial spread is restricted to an
arc (around the synchronous equilibrium), whose length is sufficiently small.
Phase synchronization is achieved only when all the natural frequencies are
equal.

##  5 Consensus on Lie groups

###  5.1 The protocol

We now consider a consensus protocol on a Lie group that generalizes the
Laplacian flow in Euclidean space and the sinusoidally coupled oscillators on
the unit circle. We assume the Lie group to be compact hereafter. This is not
a problem as already it was seen that any Lie group with a bi-invariant metric
can be written as a Cartesian product of a compact Lie group and an Euclidean
space. We can take care to design consensus and synchronization on Euclidean
space separately and concentrate only on the compact Lie group. In a Lie
group, all velocities can be left translated to the Lie algebra $\mathfrak{g}$
as visualized below. Henceforth, it is assumed that all tangent vectors are
shown after left transport to the Lie algebra, including the velocity of each
agent.

Figure 2: Visualizing velocity of a curve in the Lie Algebra

As already defined, the left invariant error of agent $i$ w.r.t agent $j$ as
$E_{ij}=g_{j}^{-1}*g_{i}$. Note that this inter-agent error is identity when
the agents are coincident and deviate from identity otherwise. This is
visualized below.

Figure 3: Visualizing $E_{ij}$

Next, we need to capture the deviation of this error from identity. That is
what is exactly done by a $G$-polar Morse function. So, $V(E_{ij})$ will be
zero if and only if $g_{i}=g_{j}$ and strictly positive otherwise. So, we use
$V(E_{ij})$ to construct the consensus dynamics.

We first prove various elementary properties of $V_{ij}:G\times
G\rightarrow\mathbb{R}$ defined by $V_{ij}:=V(E_{ij})=V(g_{j}^{-1}*g_{i})$.
Recall the notation that the gradient translated to the Lie algebra be denoted
by $\mathfrak{grad}$ \- that is, $\mathfrak{grad}_{g}V(v)=grad_{g}V(g*v)$. Let
$\mathfrak{grad}^{i}V_{ij}$ and $\mathfrak{grad}^{j}V_{ij}$ denote the
gradients of $V_{ij}$ with respect to the variables $g_{i}$ and $g_{j}$
respectively. Then, we have

###### Theorem 17

$\displaystyle\mathfrak{grad}^{i}V_{ij}=-\mathfrak{grad}^{j}V_{ji}.$ (41)

Proof:

Let $\dot{g}_{i}(t),\hskip 2.84526pt\dot{g}_{j}(t)$ be the velocities of
curves. Then, by chain rule, we have

$\displaystyle\frac{d}{dt}V_{ij}$ $\displaystyle=\langle
grad_{g_{j}^{-1}*g_{i}}V,\frac{d}{dt}(g_{j}^{-1}*g_{i})\rangle$
$\displaystyle=\langle
grad_{g_{j}^{-1}*g_{i}}V,\dot{g}_{j}^{-1}*g_{i}+g_{j}^{-1}*\dot{g}_{i}\rangle$
$\displaystyle=\langle
grad_{g_{j}^{-1}*g_{i}}V,-g_{j}^{-1}*\dot{g}_{j}*g_{j}^{-1}*g_{i}+g_{j}^{-1}*\dot{g}_{i}\rangle.$

When we left multiply both the gradient and the velocities by
$(g_{j}^{-1}*g_{i})^{-1}=g_{i}^{-1}*g_{j}$, they both will be in the Lie
algebra. Doing this and simplifying, we have

$\displaystyle=\langle\overbrace{\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-g_{i}^{-1}*\dot{g}_{j}*g_{j}^{-1}*g_{i}+g_{i}^{-1}*\dot{g}_{i}}^{\text{left
transported to $\mathfrak{g}$}}\rangle.$ (42)

Using adjoint operator, the velocities simplify further as

$\displaystyle=\langle\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-ad_{g_{i}^{-1}*g_{j}}\underbrace{g_{j}^{-1}*\dot{g}_{j}}_{\text{$\in\mathfrak{g}$}}+\underbrace{g_{i}^{-1}*\dot{g}_{i}}_{\text{$\in\mathfrak{g}$}}\rangle.$
(43)

Now, since gradient is linear, we can split the sum into two parts as

$\displaystyle=$
$\displaystyle\langle\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-ad_{g_{i}^{-1}*g_{j}}{g_{j}^{-1}*\dot{g}_{j}}\rangle+$
$\displaystyle\langle\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,g_{i}^{-1}*\dot{g}_{i}\rangle.$
(44)

Since the metric is ad-invariant, adjointing the first-term by
$ad_{g_{j}^{-1}*g_{i}}$, we get

$\displaystyle=\langle
ad_{g_{j}^{-1}*g_{i}}\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-\overbrace{ad_{g_{j}^{-1}*g_{i}}ad_{g_{i}^{-1}*g_{j}}}^{\text{yields
identity}}g_{j}^{-1}*\dot{g}_{j}\rangle$ $\displaystyle=\langle
ad_{g_{j}^{-1}*g_{i}}\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-g_{j}^{-1}*\dot{g}_{j}\rangle.$
(45)

But by adjoint invariance of the gradient of a $G-$polar Morse function in
Lemma 1, we have
$ad_{E_{ij}}\mathfrak{grad}_{E_{ij}}V=\mathfrak{grad}_{E_{ij}}V$. Substituting
this in the above equation (45), we get

$\displaystyle\langle
ad_{g_{j}^{-1}*g_{i}}\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-g_{j}^{-1}*\dot{g}_{j}\rangle=\langle\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-g_{j}^{-1}*\dot{g}_{j}\rangle.$
(46)

Hence, ignoring the adjoint term in (43) due to (46), we get

$\displaystyle\frac{d}{dt}V_{ij}$
$\displaystyle=\langle\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V,-g_{j}^{-1}*\dot{g}_{j}+g_{i}^{-1}*\dot{g}_{i}\rangle.$
(47)

Let $v_{i}=g_{i}^{-1}*\dot{g}_{i}$ , $v_{j}=g_{j}^{-1}*\dot{g}_{j}$ be the
velocity of the $i^{th}$ and $j^{th}$ agents left translated to Lie algebra.
Then we have

$\displaystyle\frac{d}{dt}V_{ij}=\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V(v_{i}-v_{j}).$
(48)

Since we want the gradient of $V_{ij}$ with respect to just the $i^{th}$
agent, we set $v_{j}=0$ in (48) and hence we have

$\displaystyle\frac{d}{dt}V_{ij}\bigg{|}_{v_{j}=0}$
$\displaystyle=\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V(v_{i})$ (49)
$\displaystyle\Rightarrow\mathfrak{grad}^{i}V_{ij}$
$\displaystyle=\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V.$ (50)

Interchanging the indices $i,j$, we have

$\displaystyle\mathfrak{grad}^{j}V_{ji}=\mathfrak{grad}_{g_{i}^{-1}*g_{j}}V.$
(51)

Due to inversion symmetry (15), in the Lie algebra, the gradients at inversely
related points are negatives of each other. But $g_{i}^{-1}*g_{j}$ and
$g_{j}^{-1}*g_{i}$ are inverses of each other. So,

$\displaystyle\mathfrak{grad}^{j}V_{ji}=\mathfrak{grad}_{g_{i}^{-1}*g_{j}}V=-\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V=-\mathfrak{grad}^{i}V_{ij},$
(52)

which yields the required result.

We are now ready to propose the consensus algorithm on a Lie group, for both
first- and second-order agents. With $v_{i}$ being the velocity of the
$i^{th}$ agent in the Lie algebra and $\nabla$ being the bi-invariant
connection induced by the bi-invariant metric $\mathbb{I}$, we have

First-Order Laplacian Flow: $\displaystyle
v_{i}=-k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij},$ (53) Second-Order Laplacian
Flow: $\displaystyle\nabla_{v_{i}}v_{i}=-k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}-k_{D}v_{i}.$ (54)

Recall that $\nabla_{v_{i}}v_{i}$ is the acceleration of the $i^{th}$ agent in
Riemannian geometry and hence the above equations are direct generalizations
of the Laplacian flow and sinusoidal consensus protocols to an arbitrary Lie
group.

###  5.2 Equilibrium Analysis

For the first-order system in (54), the equilibriua are the configurations
that satisfy

$\displaystyle\forall\hskip 2.84526pti:\hskip
5.69054pt\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}=0.$ (55)

Included within these equilibria are:

  * •

Consensus Solution: Where $g_{i}=g_{j}$ for all $i,j$ which implies
$\mathfrak{grad}^{i}_{E_{ij}}V_{ij}=0$ individually for every $i,j$.

  * •

Anti-Consensus Solutions: Where $g_{i}^{-1}*g_{j}\in C$ for all $i,j$ which
also implies $\mathfrak{grad}^{i}_{E_{ij}}V_{ij}=0$ individually for every
$i,j$.

  * •

Other Solutions: Where the gradients $\mathfrak{grad}^{i}_{E_{ij}}V_{ij}=0$ do
not individually vanish but collectively satisfy the equilibrium condition
(55).

For the sake of ease of reference, let us call the equilibria where the
gradients individually vanish (consensus and anti-consensus points) as trivial
equilibria and the other equilibria as non-trivial equilibria.

For the second-order system in (54), the dynamics in state-space form is

$\displaystyle\dot{g}_{i}$ $\displaystyle=g_{i}*v_{i},$
$\displaystyle\nabla_{v_{i}}v_{i}$
$\displaystyle=-k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}-k_{D}v_{i}.$ (56)

At equilibrium, we hence have $v_{i}=0$ and the same condition (55) for the
first-order case. So, the equilibria of the second-order flow are those where
the velocities of the agents vanish and the positions same as that of the
first-order flow.

Ideally, we would only want the consensus solution to exist and be globally
asymptotic stable. But as we have seen, for compact manifolds, $C$ has points
other than identity and hence we have anti-consensus solutions as well,
similar to oscillators.

It can be shown (it will be shown in a future section) that the consensus
points are locally exponentially stable and that these anti-consensus points
possess an unstable direction and hence cannot be locally stable (these are
done in the next section). So, then, if we do not have any other non-trivial
equilibria, then the locally exponentially stable consensus equilibrium can be
almost globally exponentially stable. But as is known from the theory of
oscillators, this is not the case for all graphs. There can be other non-
trivial solutions to (55) where the individual gradients in the summation do
not vanish.

As it was mentioned, in the theory of oscillators, it is known that for the
Kuramoto oscillator where the graph is a complete graph with equal weights
($a_{ij}=\frac{1}{n}$ for all $i,j$), there are no other non-trivial
equilibrium solutions and that the consensus equilibrium is almost globally
asymptotically stable . This has also been established for trees. Now, we will
establish that this is the case here for general Lie groups as well, when the
graph is a tree. We will start the analysis with simpler graphs like two-agent
system and a line graph as precursors to visualize the situation
geometrically.

####  5.2.1 Two Agent case

Consider the case when there are only two agents. Then, the consensus
protocols generalize as follows:

  * •

First-Order:

$\displaystyle v_{1}=-\frac{k_{P}}{2}\mathfrak{grad}^{1}V_{12}.$ (57)
$\displaystyle v_{2}=-\frac{k_{P}}{2}\mathfrak{grad}^{2}V_{21}.$ (58)

  * •

Second-Order:

$\displaystyle\nabla_{v_{1}}v_{1}=-\frac{k_{P}}{2}\mathfrak{grad}^{1}V_{12}-k_{D}v_{1},$
(59)
$\displaystyle\nabla_{v_{2}}v_{2}=-\frac{k_{P}}{2}\mathfrak{grad}^{2}V_{21}-k_{D}v_{2}.$
(60)

Observing that in either case $V_{12}=V_{21}=V$ and that the gradients are
negatives of each other, that is,
$\mathfrak{grad}^{2}V_{21}=-\mathfrak{grad}^{1}V_{12}:=\mathfrak{grad}V$, we
see that the equilibrium conditions for both the dynamical systems is given by

$\displaystyle\mathfrak{grad}^{1}V_{12}=0.$ (61)

This implies that at equilibrium,

$\displaystyle g_{1}^{-1}*g_{2}\in C.$ (62)

So, we see that for the two agent case, there are only trivial equilibrium
solutions - the consensus case (when $g_{1}^{-1}*g_{2}=e$) and the anti-
consensus cases $g_{1}^{-1}*g_{2}=c\in C-\\{e\\}$. There are no non-trivial
equilibria.

####  5.2.2 Line Graph

For multiple agents, first let us start with a simple graph where the an agent
$i$ is connected to just $i+1$ and $i-1$. (agent 1 is connected only to 2 and
agent $n$, only to $n-1$).

The equilibrium condition for such $a_{ij}$ looks as follows:

$\displaystyle a_{12}\mathfrak{grad}^{1}_{E_{12}}V_{12}=0,$ $\displaystyle
a_{21}\mathfrak{grad}^{2}_{E_{21}}V_{21}+a_{23}\mathfrak{grad}^{2}_{E_{23}}V_{23}=0,$
$\displaystyle
a_{32}\mathfrak{grad}^{3}_{E_{32}}V_{32}+a_{34}\mathfrak{grad}^{3}_{E_{34}}V_{34}=0,$
$\displaystyle\vdots$ $\displaystyle
a_{n,n-1}\mathfrak{grad}^{n}_{E_{n,n-1}}V_{n,n-1}=0.$ (63)

First, we have $\mathfrak{grad}^{1}_{E_{12}}V_{12}=0$ and since
$\mathfrak{grad}^{2}_{E_{21}}V_{21}=-\mathfrak{grad}^{1}_{E_{12}}V_{12}$, that
term in the second equation also vanishes. So, the only remaining term in the
second equation is $a_{23}\mathfrak{grad}^{2}_{E_{23}}V_{23}$ which also has
to vanish. Proceeding further, we have

$\displaystyle\forall\hskip 2.84526pti=2,3,\ldots,n:\hskip 8.53581pt$
$\displaystyle\mathfrak{grad}^{i}_{E_{i,i-1}}V_{i,i-1}=0,$ (64)
$\displaystyle\Longleftrightarrow\hskip 5.69054pt$ $\displaystyle
g_{i-1}^{-1}*g_{i}\in C.$

But since $C$ is a subgroup (now we see why that property is crucial), we have

$\displaystyle g_{i}^{-1}*g_{j}$
$\displaystyle=\overbrace{g_{i}^{-1}*g_{i+1}}^{\text{$\in$
C}}*\overbrace{g_{i+1}^{-1}*g_{i+2}}^{\text{$\in$ C}}*\cdots$
$\displaystyle\cdots*\overbrace{g_{j-1}^{-1}*g_{j}}^{\text{$\in$ C}}.$ (65)

So, $g_{i}^{-1}*g_{j}\in C$ for any $i,j$ since it is a group product of
elements in $C$ and $C$, being a subgroup is closed under group operation. So,
we have that all pair of agents are C related and the individual gradients
$grad^{i}V(g_{j}^{-1}*g_{i})=0$ vanish. So, the equilibrium consists of only
the trivial consensus and anti-consensus points.

####  5.2.3 Trees

We now consider the case when the graph is connected and is a tree. We
establish once again that in a tree, the equilibria only consists of the
trivial consensus and anti-consensus points.

###### Theorem 18

When a graph $\mathcal{G}$ is a connected tree, the only solutions that
satisfy the equilibrium condition in (55) are trivial - only the consensus and
anti-consensus points.

Figure 4: A visualization of a tree with its leaves and its neighbors

Proof:
Consider a connected tree graph, an example of which is shown in Figure 4.
From Theorem 2, leaves exist. Let $l$ be a leaf of the tree graph
$\mathcal{G}$. Then, it has degree 1 by definition and hence in the dynamics
of the agent $l$, there can be only one gradient term. Let the lone neighbor
of $l$ be $N(l)$. Then we have the equilibrium condition of agent $l$ as

$\displaystyle a_{l,N(l)}\hskip
2.84526pt\mathfrak{grad}^{l}_{E_{l,N(l)}}V_{l,N(l)}=0.$ (66)

So we now have that

$\displaystyle g_{l}^{-1}*g_{N(l)}\in C.$ (67)

Now since these gradients associated with the leaves $l$ vanish, we can
substitute zero in their place and now consider the reduced connected tree
that is obtained after removing the leaves and their associated edges.

Now, one can do the same process for the reduced tree. Consider their leaves.
One can then equate their associate gradients to zero as well and move on by
removing them.

One can continue this until the reduced tree becomes empty. The reduction will
lead to an empty graph in finite steps since in each step, atleast one node is
removed (every tree has atleast one leaf and we are removing leaf nodes at
each step). So, since the graph ultimately reduces to the empty graph,
eventually, every node will be removed as a leaf at some stage. But since the
gradients for edges associated with leaf nodes are proven to vanish at each
step, we have that the gradient terms for every edge associated with every
node vanishes. So, we have

$\displaystyle g_{k}^{-1}*g_{l}\in C\hskip 5.69054pt\text{if $(k,l)$ is an
edge}.$ (68)

Since the graph $\mathcal{G}$ is connected, there is a path made of edges,
between any two nodes. Let $i,j$ be two arbitrary nodes, with a path
$(i,i^{\prime}),(i,i^{\prime\prime}),\cdots(i^{{}^{\prime\prime}\cdots^{\prime}},j)$.
Then, again since $C$ is a subgroup, we have

$\displaystyle g_{i}^{-1}*g_{j}$
$\displaystyle=\overbrace{g_{i}^{-1}*g_{i^{\prime}}}^{\text{$\in$
C}}*\overbrace{g_{i^{\prime}}^{-1}*g_{i^{\prime\prime}}}^{\text{$\in$
C}}*\cdots$
$\displaystyle\cdots*\underbrace{g_{i^{\prime\prime}\cdots^{\prime}}^{-1}*g_{j}}_{\text{$\in$
C}}.$ (69)

So, for any pair of agents $(i,j)$, at equilibrium, $g_{i}^{-1}*g_{j}\in C$,
since $C$ is a subgroup.

###  5.3 Energy and formulation as a Gradient Dynamical System

We saw that $V$ is a spring-like potential energy function that acts to
provide a restoring force that tries to bring together, the pair of agents it
connects. With this intuition, let us analyze the behavior of the energy
function for the first and second-order Laplacian flow.

Inspired from the Euclidean and circle case, consider the total potential
energy function (the $\frac{1}{2}$ in the potential energy term $V_{T}$ is
because each spring is counted twice).

$\displaystyle
V_{T}(g_{1},\ldots,g_{n})=\frac{1}{2}\sum_{j,k=1}^{n}a_{jk}V_{jk}=\sum_{j<k}V_{jk}.$
(70)

Let us evaluate the gradient of $V_{T}$.

$\displaystyle grad^{i}V_{T}$
$\displaystyle=\frac{1}{2}\sum_{j,k=1}^{n}a_{jk}grad^{i}V_{jk}$ (71)
$\displaystyle=\frac{1}{2}\sum_{i,k=1}^{n}a_{ik}grad^{i}V_{ik}+\frac{1}{2}\sum_{j,i=1}^{n}a_{ji}grad^{i}V_{ji}$
(72) $\displaystyle=\sum_{i,k=1}^{n}a_{ik}grad^{i}V_{ik}.$ (73)

We see that the gradient of $V_{T}$ is the consensus term appearing in the
first and second-order dynamics in (53)-(54). So, they can be rewritten as

First-Order Laplacian Flow: $\displaystyle v_{i}$
$\displaystyle=-k_{P}\mathfrak{grad}^{i}\hskip 2.84526ptV_{T},$ (74) Second-
Order Laplacian Flow: $\displaystyle\nabla_{v_{i}}v_{i}$
$\displaystyle=-k_{P}\mathfrak{grad}^{i}\hskip 2.84526ptV_{T}-k_{D}v_{i}.$
(75)

So, the equilibria of the systems, as required in (55), are nothing but the
critical points of $V_{T}$. We now state a standard result from gradient
dynamical systems as follows:

###### Theorem 19

[2] Consider a first or second-order gradient descent dynamical system in the
form

$\displaystyle\dot{x}$ $\displaystyle=-k_{P}grad(F),$ (76)
$\displaystyle\nabla_{\dot{x}}\dot{x}$
$\displaystyle=-k_{P}grad(F)-k_{D}\dot{x}.$ (77)

Assume that $k_{P},k_{D}>0$ and the sub-level set corresponding to the initial
position is compact. Then, the trajectory starting from that initial condition
with any initial velocity satisfies the following:

  * •

Its velocity goes to zero asymptotically.

  * •

Its position that is attained asymptotically is one of the critical points of
$F$.

  * •

If a critical point has a direction that maximizes $F$, then that point is
never locally stable and has an unstable manifold of non-zero dimension.

So, we see that if the group $G$ is compact, all trajectories of the first and
second-order Laplacian flow converge to critical points of $V_{T}$ which is
the equilibrium of the dynamics as well. So, the equilibrium set of the system
is globally asymptotically stable. But it includes, as we saw, consensus
points, anti-consensus points and other non-trivial solutions for generic
graphs. We can rule out the non-trivial solutions for special graphs as was
seen in the previous section - for two agents, or when the graph is a tree.

###  5.4 Local Asymptotic Stability of the Consensus Solution

We now show that the consensus solution is locally asymptotically stable for
both the first and second-order systems and that the anti-consensus solutions
are unstable. For the first-order dynamical system in (53), the Jacobian of
the dynamical system is nothing but the negative Hessian of $V_{T}$ as the
vector field is itself the negative gradient of $V_{T}$. Recall that for a
smooth vector field $W$ in a Riemannian manifold $G$ with an induced covariant
derivative $\nabla$, the Riemannian Jacobian at a point $p$, denoted by
$J_{p}(W):T_{p}G\rightarrow T_{p}G$ is a linear map, defined in geometric
coordinate invariant terms as

$\displaystyle J_{p}W(v)=(\nabla_{v}W)_{p}.$

When the vector field $W$ is the gradient of a scalar function $F$, putting
$W=grad(F)$, the Jacobian of $grad(F)$ at a point $p$ is called the Riemannian
Hessian of $F$ defined as

$\displaystyle Hess_{p}F(v)=(\nabla_{v}grad(F))_{p}.$

When the manifold is a Lie group, the vector field, the input vector, the
gradient vector, all can be left transported to $\mathfrak{g}$ and the
connection also can be transported to the Lie algebra and hence the
Hessian/Jacobian can be defined as a map from $\mathfrak{g}$ to
$\mathfrak{g}$. Denoting the Lie-algebraic Jacobian and Hessian by
$\mathfrak{J}$ and $\mathfrak{hess}$, and the Lie algebraic vector field by
$\mathfrak{W}$, we have

$\displaystyle\mathfrak{J}W(v)$ $\displaystyle=\nabla_{v}\mathfrak{W},$ (78)
$\displaystyle\mathfrak{hess}F(v)$ $\displaystyle=\nabla_{v}\mathfrak{grad}F.$
(79)

Let us evaluate the Jacobian matrix of the first-order consensus flow (74),
which is also the negative of the Hessian matrix of $V_{TOT}$. Since the
configuration space of the system is a product space of $G$, $n$ times, the
Jacobian also splits into blocks as
$\mathfrak{J}=[J]_{ij}:=-\nabla^{j}\mathfrak{grad}^{i}V_{TOT}$ where
$\nabla^{j}$ is the covariant derivative with respect to only the velocity of
the $j^{th}$ agent , that is, $v=(0,0,\ldots,v_{j},0,\ldots,0)$. The linearity
of the Jacobian enables one to split up the Jacobian as block matrices and
hence we have

$\displaystyle[\mathfrak{J}(v_{1},\ldots,v_{k},\ldots,v_{n})]^{i}=\sum_{k}J_{ik}v_{k}.$
(80)

We now evaluate the Jacobian, block-by-block.

###### Lemma 4

The block Jacobians are

$\displaystyle J_{ii}$ $\displaystyle=-\sum_{j\neq
i}a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij},$ (81) $\displaystyle J_{ij}$
$\displaystyle=a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij}.$ (82)

Proof:

If $i\neq j$, we have

$\displaystyle
J_{ij}=-\nabla^{j}\sum_{k}a_{ik}\mathfrak{grad}^{i}V_{ik}=-a_{ij}\nabla^{j}\mathfrak{grad}^{i}V_{ij}.$
(83)

When $i=j$, the diagonal block evaluates to

$\displaystyle J_{ii}$ $\displaystyle=-\nabla^{i}\sum_{k\neq
i}a_{ik}\mathfrak{grad}^{i}V_{ik}=-\nabla^{i}\sum_{j\neq
i}a_{ij}\mathfrak{grad}^{i}V_{ij}$ $\displaystyle=-\sum_{j\neq
i}a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij}.$ (84)

We now simplify equation (83).

$\displaystyle
J_{ij}=-a_{ij}\nabla^{j}\mathfrak{grad}^{i}V_{ij}=a_{ij}\nabla^{j}\underbrace{(-\mathfrak{grad}^{i}V_{ij})}_{grad^{j}V_{ji}\hskip
2.84526pt\text{from theorem \ref{oppt}}}.$ (85)

Recalling the result in Theorem 17 that
$\mathfrak{grad}^{i}V_{ij}=-\mathfrak{grad}^{j}V_{ji}$, we now have

$\displaystyle J_{ij}=a_{ij}\nabla^{j}\mathfrak{grad}^{j}V_{ji}.$ (86)

We now note that an important feature of the Riemannian Hessian that it is a
self-adjoint operator. Hence, it is symmetric as a block matrix. Hence we have
$J_{ij}=J_{ji}$. Hence, we have

$\displaystyle J_{ij}$
$\displaystyle=a_{ij}\nabla^{j}\mathfrak{grad}^{j}V_{ji}=$ $\displaystyle
J_{ji}$ $\displaystyle=a_{ji}\nabla^{i}\mathfrak{grad}^{i}V_{ij}$
$\displaystyle=a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij}.$ (87)

Once again, putting the entries of $J_{ij}$ and $J_{ii}$ side by side, we see
that we have the required result (81)-(82).

Let us compare (81)-(82) to the definition of the negative of the Laplacian
matrix as follows:

$\displaystyle-L_{ii}$ $\displaystyle=-(O-A)_{ii}=-O_{ii}=-\sum_{j\neq
i}a_{ij},$ (88) $\displaystyle-L_{ij}$
$\displaystyle=-(O-A)_{ij}=(A-O)_{ij}=a_{ij}.$ (89)

So, we have finally,

$\displaystyle-L_{ii}$ $\displaystyle=-\sum_{j\neq i}a_{ij},$ (90)
$\displaystyle-L_{ij}$ $\displaystyle=a_{ij}.$ (91)

Now, replacing $a_{ij}$ in (90)-(91) by
$a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij}$, we get the Jacobian matrix
(81)-(82). So, the block Jacobian matrix looks exactly like the negative of
the Laplacian matrix except that the weights $a_{ij}$ now are multiplied by a
block Hessian $\nabla^{i}\mathfrak{grad}^{i}V_{ij}$.

In the graph theoretic preliminaries, it was mentioned that the Laplacian
matrix can be factorised as $L=BDB^{T}$ where $B$ is the incidence matrix and
$D$ is the diagonal matrix consisting of edge weights. With a modified notion
of block incidence matrix defined as

$\displaystyle\bar{B}_{ie}:$ $\displaystyle=+I_{m\times m},\hskip
5.69054pt\text{if node $i$ is the source of the edge $e$},$
$\displaystyle\bar{B}_{ie}:$ $\displaystyle=-I_{m\times m},\hskip
5.69054pt\text{if node $i$ is the sink of the edge $e$},$
$\displaystyle\bar{B}_{ie}:$ $\displaystyle=\hskip 2.84526pt0_{m\times
m},\hskip 5.69054pt\text{otherwise},$

and a modifed block diagonal matrix defined as

$\displaystyle\bar{D}_{ee}=a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij},$

we can analogously factorize the Jacobian $\mathfrak{J}$ as

$\displaystyle\mathfrak{J}=-\bar{B}\bar{D}\bar{B}^{T}.$ (92)

Since $\mathfrak{J}=-\bar{B}\bar{D}\bar{B}^{T}$, we are assured the negative
semi-definiteness of $\mathfrak{J}$ if we are sure that each block diagonal
matrix $a_{ij}\nabla^{i}\mathfrak{grad}^{i}V_{ij}$ is positive definite. Since
$a_{ij}>0$, we must have that the map $\nabla^{i}\mathfrak{grad}^{i}V_{ij}$ be
positive definite. We will now show that this is indeed the case as long as
$E_{ij}=g_{j}^{-1}*g_{i}$ belongs to a small enough neighborhood of $e$.

###### Lemma 5

The map $\nabla^{i}\mathfrak{grad}^{i}V_{ij}$ is positive definite if
$E_{ij}=g_{j}^{-1}*g_{i}$ is restricted to a neighboorhood $U$ around $e$.

Proof:

$\displaystyle\nabla^{i}\mathfrak{grad}^{i}V_{ij}$
$\displaystyle=\nabla^{i}\mathfrak{grad}^{i}V(g_{j}^{-1}*g_{i})$
$\displaystyle=\nabla^{i}\mathfrak{grad}_{g_{j}^{-1}*g_{i}}V$
$\displaystyle=\mathfrak{hess}(V)_{g_{j}^{-1}*g_{i}}.$

But since $V$ is a polar Morse function, the Hessian at identity
$\mathfrak{hess}_{e}$ is positive definite as $e$ is the global minimum. Now,
since $\mathfrak{hess}$ is continuous (as $V$ is smooth), and the set of
positive definite matrices is open, we have that $\mathfrak{hess}$ is positive
definite in a neighborhood $U$ of $e$ as well. Hence, the result ensues.

###### Theorem 20

The consensus equilibrium is locally exponentially stable for any connected
symmetric graph for both the first and second order dynamics.

Proof:

So, the matrix $\bar{D}$ is positive definite if $E_{ij}\in U\hskip
5.69054pt\forall i,j$. But, we are concerned about the consensus equilibrium
where $E_{ij}=e\hskip 5.69054pt\forall i,j$ and hence the matrix $\bar{D}$ is
trivially positive definite. Hence, $\mathfrak{J}$ is negative semi-definite.
Since the the graph $\mathcal{G}$ is connected, the null space of
$\mathfrak{J}$ will consist only of consensus velocities of the form
$(v,v,\ldots,v)$ where $v\in\mathfrak{g}$, that is
$ker(\mathfrak{J})=\\{(v,v,\ldots,v)\hskip 5.69054ptv\in\mathfrak{g}\\}$. But
these consensus velocities span the tangent space to the consensus manifold
$M_{C}:=\\{(g,g,\ldots,g):g\in G\\}$. Also, the consensus manifold is
invariant (since agents stay in consensus once they start at consensus). So,
$M_{C}$ is an invariant submanifold spanning $ker(\mathfrak{J})$. So, the
uniqueness of the center manifold (by center manifold emergence theorem), it
is the centre manifold and hence in a neighborhood, any solution exponentially
converges to a solution in $M_{C}$ and hence consensus is locally
exponentially stable.

The local asymptotic stability of the consensus solution in second-order flow
follows from the standard result that the asymptotic behavior of first and
second-order gradient systems are equivalent with $k_{P},k_{D}>0$. It follows
easily from the fact that the spectrum of a matrix $A$ lies in the left/right
half plane if and only if the spectrum of the matrix $\begin{bmatrix}0&I\\\
-A&-k_{D}I\end{bmatrix}$ lies in the left/right half plane for any $k_{D}>0$.
Applying this result to the Jacobian of the second-order system yields local
exponential stability of the consensus manifold there as well.

###### Theorem 21

The other trivial anti-consensus equilibria where all the inter-agent errors
are not necessarily $e$ but in $C$ are unstable.

Proof:
To prove this, let us choose an agent pair $(i,j)$ where $E_{ij}=c\neq e$
where $c\in C$. Then, in $V=\frac{1}{2}\sum_{i,j=1}^{n}a_{ij}V_{ij}$, if we
vary only $g_{i},g_{j}$, $V_{ij}$ is a saddle with at least one negative eigen
value at $E_{ij}=c\in C$ and hence there is a direction in which it is
maximum. So, there is an unstable direction and hence the trivial equilibrium
is not attracting if it is not a consensus equilibrium.

As a Corollary, since a gradient system on a compact manifold can only
converge to an equilibrium asymptotically, we have that the consensus
equilibrium has an almost global domain-of-attraction if all other equilibria
are unstable (since it is the only attracting equilibrium).

##  6 Synchronization on Compact Lie Groups

We can also generalize the synchronization protocol from oscillators to Lie
groups. Compare the consensus and synchronization protocols for oscillators as
follows:

Consensus: $\displaystyle\dot{\theta}_{i}$
$\displaystyle=-k_{P}\sum_{j=1}^{n}a_{ij}\sin(\theta_{i}-\theta_{j}),$ (93)
Synchronization: $\displaystyle\dot{\theta}_{i}$
$\displaystyle=\omega_{i}-k_{P}\sum_{j=1}^{n}a_{ij}\sin(\theta_{i}-\theta_{j}).$
(94)

The only extra term in the synchronization protocol (compared to the consensus
dynamics), is an extra angular velocity $\omega_{i}$. So, with this intuition,
we propose a synchronization protocol in Lie groups as

$\displaystyle v_{i}=\mathfrak{w}_{i}-k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}.$ (95)

Here, $\mathfrak{w}_{i}$ is now a constant velocity in the Lie algebra, and is
a generalization of the intrinsic natural frequency of the oscillator
$\omega_{i}$ in $\mathbb{S}^{1}$. In the oscillator case, without the
coupling, each oscillator would exhibit a periodic motion with angular
velocity $\omega_{i}$. In this case, when the coupling gain $k_{P}$ is zero,
each $i^{th}$ agent travels with a constant left velocity $\mathfrak{w}_{i}$
(or the trajectory of the agent is an integral curve of the left invariant
vector field generated by $\mathfrak{w}_{i}$). In the case of an oscillator
that evolves on a circle, such a curve with constant velocity $\omega_{i}$ is
periodic. In case of tori that are Cartesian products of circles, the curves
will be quasi-periodic - periodic in each angular component. We now establish
the same result for general compact Lie groups. That is, when a Lie group $G$
is compact, their integral curves of left invariant vector fields are also
quasi-periodic.

###### Theorem 22

The integral curves of left invariant vector fields on a compact Lie group are
quasi-periodic.

Proof:
: As is standard from representation theory, every compact Lie group has a
faithful matrix representation by unitary matrices of finite-dimension. In
other words, every connected and compact Lie group is isomorphic to a matrix
Lie subgroup of $U(n)$. So, since the Lie algebra of $U(n)$ is
$\mathfrak{u}(n)$ (space of $n\times n$ skew Hermitian matrices), the left
invariant vector field on a matrix Lie group of orthogonal matrices can be
written as

$\displaystyle\dot{X}$ $\displaystyle=X\mathfrak{w},\hskip
5.69054pt\text{where}\hskip 2.84526pt\mathfrak{w}\in\mathfrak{u}(n)$
$\displaystyle\text{Integral curve:}\hskip 5.69054ptX(t)$
$\displaystyle=e^{\mathfrak{w}t}X(0).$

Now since $\mathfrak{w}$ is a skew Hermitian matix, it has purely imaginary
eigen values $\pm i\omega_{k}$. When $\mathfrak{w}$ is diagonalized, and the
ODE is rendered in diagonalized coordinates, we hence have
$\frac{d}{dt}x_{i}=\pm i\omega_{i}x_{i}$ which integrates to give
$x_{i}(t)=e^{\pm i\omega_{i}t}x_{i}(0)$ which is periodic in each $x_{i}$. So,
we see that the integral curve is resolvable into periodic motions and hence
is quasi-periodic.

When all the $\mathfrak{w}_{i}=0$, then the equation reduces to the standard
Laplacian flow with just the consensus term, as usual.

###  6.1 Synchronization notions

So, now we have that the agents have a natural tendency to move at some
constant left velocity in addition to trying to achieve consensus. Recalling
the synchronization protocol again

$\displaystyle v_{i}=\mathfrak{w}_{i}-k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij},$

we are curious as to what ensues, as a result of these two opposing tendencies
for each of the agent.

We now extend the definitions from the oscillator case to the generic case.
Let $U$ be a given open neighborhood of identity that is symmetric under
inversion ($U=U^{-1}$) (such neighborhoods can easily be constructed as if $U$
is any other neighborhood of $e$, $U\cap U^{-1}$ satisfies this requirement).

###### Definition 6

Trajectories $g_{i}(t)$ evolving on a compact Lie group $G$ are said to be

  * •

position synchronized if $g_{i}(t)=g_{j}(t)$, $\forall\hskip 2.84526ptt$,
$\forall\hskip 2.84526pti,j$.

  * •

left velocity synchronized if their left velocities coincide , that is
$g_{i}^{-1}(t)*\dot{g}_{i}(t)=g_{j}^{-1}*\dot{g}_{j}(t)$ $\forall\hskip
2.84526ptt$ $\forall\hskip 2.84526pti,j$.

  * •

$U$-cohesive if $g_{j}^{-1}(t)*g_{i}(t)\in U$ $\forall\hskip 2.84526ptt$
,$\forall\hskip 2.84526pti,j$.

With this , we prove a couple of simple results.

###### Theorem 23

Consider the dynamical system in (95).

  1. 1.

Phase synchronization is possible if and only if all the $\mathfrak{w}_{i}$
coincide (agents share a common natural left velocity)

  2. 2.

If velocity synchronization occurs in the dynamics (95), then the synchronous
velocity attained (denoted by $\mathfrak{w}_{S}$) can only be equal to the
average of the individual natural left velocities.

$\displaystyle\mathfrak{w}_{S}=\frac{1}{n}\sum_{i=1}^{n}\mathfrak{w}_{i}.$
(96)

Proof:

  1. 1.

If $g_{i}(t)=g_{j}(t)$ (which implies $E_{ij}=e$), then differentiating,
$\dot{g}_{i}(t)=\dot{g}_{j}(t)$ which gives $v_{i}=v_{j}$. Substituting the
dynamics for $v_{i}$ in (95) and noting that all gradients vanish (all errors
being $e$ and gradient of $V$ vanishes at $e$), we have that
$v_{i}=\mathfrak{w}_{i}+0=\mathfrak{w}_{i}$. Since $v_{i}=v_{j}$,
$\mathfrak{w}_{i}=\mathfrak{w}_{j}$.

  2. 2.

Summing over $i$ in (95) , we have

$\displaystyle\mathfrak{w}_{S}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathfrak{w}_{S}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}v_{i}=\frac{1}{n}\sum_{i=1}^{n}\mathfrak{w}_{i}-\frac{1}{n}k_{P}\overbrace{\sum_{i=1}^{n}\sum_{j=1}^{n}\mathfrak{grad}^{i}_{E_{ij}}V_{ij}}^{\text{add
to 0}}.$ (97)

But by Theorem (41) in 17, we have
$\mathfrak{grad}^{i}V_{ij}=-\mathfrak{grad}^{j}V_{ji}$ and hence the gradient
terms in (97) add to zero pairwise. Hence, (96) ensues.

Note: When the agents are all moving with a constant left-synchronous velocity
$\mathfrak{w}_{S}$, then their flow is given by
$g_{i}(t)=\mathrm{e}^{\mathfrak{w}_{S}t}g_{i}(0)$ and hence their left-
invariant errors $E_{ij}=g_{j}^{-1}(t)g_{i}(t)=g_{j}(0)^{-1}g_{i}(0)$ remain
constant. So, the arguments of $V_{ij}$ remain constant. So, $E_{ij}$ are
constants for all $i,j$.

###  6.2 A necessary condition for the existence of synchronization solution

Next, we need to look deeply, what are some necessary and sufficient
conditions for which the synchronous solution exists. The following are some
investigations. We first prove some elementary results.

###### Theorem 24

Topological result : Consider the gradient function
$\mathfrak{grad}:G\rightarrow\mathfrak{g}$. Then, the image of $G$ under the
function $\mathfrak{grad}$ is a compact (hence bounded) subset of
$\mathfrak{g}$, containing a neighborhood $U^{\prime}$ of origin. It is also
possible to choose this neighborhood $U^{\prime}$ such that the function
$\mathfrak{grad}_{g}V$ is locally injective and surjective (hence a local
diffeomorphism) in that neighborhood.

Proof:

Since $G$ is a compact and connected Lie group by assumption and
$\mathfrak{grad}V$ is smooth (and hence continuous), the image set
$\mathfrak{grad}V(G)$ will also be compact and connected as continuous
functions preserve compactness and connectedness. As a Corollary,
$\mathfrak{grad}V$ is bounded in $M$ and hence its norm has a supremum that is
actually attained in $M$.

Since $e$ is the global minimum of $V$, it is also a local minimum and choose
a local coordinate system around $e$ so that
$F(x_{1},\ldots,x_{m})=x_{1}^{2}+x_{2}^{2}+\cdots+x_{m}^{2}$. (By Theorem 10).
Then the differential of $F$ in this coordinate system is $\frac{\partial
F}{\partial x_{i}}=2x_{i}$ and hence $grad(F(x))=2x$. Hence, locally the
gradient map is scaled identity in this local coordinate system for $G$, and
hence is injective, surjective and smooth. This makes $\mathfrak{grad}V$, a
local diffeomorphism around $e$ (by inverse function theorem). But local
injectivity and surjectivity are coordinate independent facts and hence
generalize to any coordinate system for $G$ and $\mathfrak{g}$. Since
$\mathfrak{grad}V(e)=0$, the identity $e$ gets mapped to origin in
$\mathfrak{g}$ and hence a coordinate neighborhood around $e$ gets mapped to a
neighborhood of origin in $\mathfrak{g}$ since the map is a local
diffeomorphism. Restricting $\mathfrak{grad}V$ to this coordinate neighborhood
of $e$ on $G$ and considering its image in $\mathfrak{g}$, we get the required
result. The result is visualized in Figure 5.

Figure 5: Visualization of the topology of
$\mathfrak{grad}:G\rightarrow\mathfrak{g}$

NOTE: For the case of the circle (that is of interest to oscillator
synchronization) where $V=1-\cos\theta$, and $grad(V)=-\sin\theta$, the
neighborhood around identity is nothing but $(-\frac{\pi}{2},\frac{\pi}{2})$
as the sine function
$\sin:(-\frac{\pi}{2},\frac{\pi}{2})\rightarrow\mathbb{R}$ is injective and
hence $\sin:(-\frac{\pi}{2},\frac{\pi}{2})\rightarrow(-1,1)$ is a local
diffeomorphism. And
$\mathrm{sup}_{\theta}||\mathfrak{grad}(V)||=\mathrm{sup}_{\theta}|\sin\theta|=1$
for the circle.

###### Theorem 25

If $\lambda:=\mathrm{sup}_{G}\hskip 2.84526pt||\mathfrak{grad}\hskip
2.84526ptV||$ (it exists by Theorem 24) , and
$||\mathfrak{w}_{i}-\mathfrak{w}_{S}||>deg(i)k_{P}\lambda$ for some $i$, then
there can be no velocity synchronous solution for the system. (the agents
cannot attain velocity synchrony if the deviation from synchronous velocity is
large enough compared to the coupling strength)

Proof:
Substracting $\mathfrak{w}_{S}$ from the synchronization dynamics (95), we get

$\displaystyle
v_{i}-\mathfrak{w}_{S}=(\mathfrak{w}_{i}-\mathfrak{w}_{S})-k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}.$ (98)

The LHS of (98) has to vanish if the agents are in synchrony. Hence we must
have

$\displaystyle(\mathfrak{w}_{i}-\mathfrak{w}_{S})=k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}.$ (99)

But since $0\leq a_{ij}\leq 1$, we have by triangle inequality,

$\displaystyle||\mathfrak{w}_{i}-\mathfrak{w}_{S}||=\bigg{|}\bigg{|}k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt\mathfrak{grad}^{i}_{E_{ij}}V_{ij}\bigg{|}\bigg{|}$
$\displaystyle\leq k_{P}\sum_{j=1}^{n}a_{ij}\hskip
2.84526pt||\mathfrak{grad}^{i}_{E_{ij}}V_{ij}||$ $\displaystyle\leq
k_{P}\lambda\underbrace{\sum_{j=1}^{n}a_{ij}}_{\text{=deg(i)}}.$ (100)

So, when the agents are synchronous, we have that
$||\mathfrak{w}_{i}-\mathfrak{w}_{S}||\leq deg(i)k_{P}\lambda$. So, synchrony
cannot happen if $||\mathfrak{w}_{i}-\mathfrak{w}_{S}||>deg(i)k_{P}\lambda$.

In particular, if
$||\mathfrak{w}_{i}-\mathfrak{w}_{S}||>k_{P}\lambda\mathrm{max}_{i}deg(i)$,
then velocity synchronization cannot occur. So, if the maximum deviation from
synchronous speed of an agent exceeds a large enough value, then the agents
cannot achieve velocity synchronization.

###  6.3 A sufficient condition for the existence of synchronization solution

Now, a sufficient condition for the existence of velocity synchronous solution
is investigated.

####  6.3.1 Two Agent Case

Let us consider first, the case of a two agents to get a geometric intuition.
In case of two agents, with adjacency matrix elements chosen as
$a_{12}=a_{21}=\frac{1}{2}$, we have the dynamics as

$\displaystyle
v_{1}-\mathfrak{w}_{S}=\mathfrak{w}_{1}-\mathfrak{w}_{S}-k_{P}\frac{1}{2}\mathfrak{grad}^{1}V_{12},$
(101) $\displaystyle
v_{2}-\mathfrak{w}_{S}=\mathfrak{w}_{2}-\mathfrak{w}_{S}-k_{P}\frac{1}{2}\mathfrak{grad}^{2}V_{21}.$
(102)

Taking $\mathfrak{grad}^{1}V_{12}=-\mathfrak{grad}^{2}V_{21}=\xi$, we get

$\displaystyle v_{1}-\mathfrak{w}_{S}=\mathfrak{w}_{1}-\frac{1}{2}k_{P}\xi,$
(103) $\displaystyle
v_{2}-\mathfrak{w}_{S}=\mathfrak{w}_{2}+\frac{1}{2}k_{P}\xi.$ (104)

Adding and subtracting the two equations, we get

$\displaystyle\frac{1}{2}(v_{1}+v_{2})=\frac{1}{2}(\mathfrak{w}_{1}+\mathfrak{w}_{2}),$
(105) $\displaystyle
v_{1}-v_{2}=(\mathfrak{w}_{1}-\mathfrak{w}_{2})-k_{p}\xi.$ (106)

So, we have that the velocity synchronization happens only if the following
equation has a solution.

$\displaystyle(\mathfrak{w}_{1}-\mathfrak{w}_{2})=k_{P}\xi.$ (107)

Let us now define another scalar quantity $\mu\leq\lambda$ as follows. Let
$\mu$ be the radius of the largest ball that is contained in $S$, which is a
neighborhood of the origin in $\mathfrak{g}$ where $\mathfrak{grad}V$ is
injective and surjective. Then, this means that given a vector $\xi$ with
$||\xi||<\mu$, there exists a unique $g\in U$ such that
$\mathfrak{grad}_{g}V=\xi$. Let us search for synchronous solutions where the
inter-agent error is in this gradient-bijective neighborhood $U$, that is
$g_{1}^{-1}*g_{2}\in U$ . Due to this restriction, we have that that, given a
vector $\xi\in\mathfrak{g}$ with $||\xi||<\mu$, there exists a unique
$E_{12}=g_{1}^{-1}*g_{2}\in U$ such that $\mathfrak{grad}_{E_{12}}V=\xi$.

Returning to the two-agent dynamical system, if
$||\mathfrak{w}_{1}-\mathfrak{w}_{2}||<k_{P}\mu$, then (107) implies that
$||\xi||<\mu$ which is sufficient for the existence of a solution as $||\xi||$
can be attained as a gradient at some point in the group. So, at least for the
two agent case, we have that if the spread in the natural velocities is
sufficiently smaller in magnitude than the coupling strength, then there
exists a synchronous solution.

####  6.3.2 Star Graph

A star is a tree where the first node is connected to all $n-1$ nodes and has
degree $n-1$ with all the other nodes connected to only the first node. The
first node acts as a leader which is connected to all other agents and the
other agents following only the leader. In other words, the adjacency matrix
is such that $a_{12}=a_{13}=\cdots=a_{1n}=a_{21}=a_{31}=\cdots=a_{n1}=1$ and
all other weights zero.

The equilibrium conditions for the system are:

$\displaystyle\mathfrak{w}_{1}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}\sum_{j\neq 1}\mathfrak{grad}^{1}V_{1j},$ (108)
$\displaystyle\mathfrak{w}_{i}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}\mathfrak{grad}^{i}V_{i1}.$ (109)

If $||\mathfrak{w}_{i}-\mathfrak{w}_{S}||\leq k_{P}\mu$ for $i\geq 2$, then
$||\mathfrak{grad}^{i}V_{i1}||<\mu$ and hence we have a solution for
$\mathfrak{w}_{i}-\mathfrak{w}_{S}=\frac{1}{k_{P}}grad_{i}V_{i1}$. Note that
once again, we are looking for a synchronous solution where the inter-agent
errors $E_{ij}$ are in the bijective neighborhood. i.e.
$||\mathfrak{grad}_{E_{ij}}V||=||\mathfrak{grad}^{i}V_{ij}||<\mu.$ Putting
$grad^{1}V_{1j}=-grad^{j}V_{j1}=-\frac{1}{k_{P}}(\mathfrak{w}_{j}-\mathfrak{w}_{S})$
in (108), we get

$\displaystyle\mathfrak{w}_{1}-\mathfrak{w}_{S}$ $\displaystyle=\sum_{j\neq
1}(\mathfrak{w}_{S}-\mathfrak{w}_{j})$ (110) $\displaystyle\Longrightarrow
n\mathfrak{w}_{S}$ $\displaystyle=\mathfrak{w}_{1}+\sum_{j\neq
1}\mathfrak{w}_{j}=n\mathfrak{w}_{S},$ (111)

which is trivially satisfied as
$\mathfrak{w}_{S}:=\frac{\sum_{j=1}^{n}\mathfrak{w}_{j}}{n}$.

So, for the star graph as well, we see that if
$\mathfrak{w}_{i}-\mathfrak{w}_{S}$ is sufficiently small enough, existence of
synchronous solution is guaranteed.

####  6.3.3 Line Graph

Now, let us consider a line graph with weights chosen that
$a_{i,i+1}=a_{i+1,i}=1$.

The synchronization condition in (99) then gives

$\displaystyle\mathfrak{w}_{1}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}\mathfrak{grad}^{1}V_{12},$
$\displaystyle\mathfrak{w}_{2}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}(\mathfrak{grad}^{2}V_{21}+\mathfrak{grad}^{2}V_{23}),$
$\displaystyle\mathfrak{w}_{3}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}(\mathfrak{grad}^{3}V_{32}+\mathfrak{grad}^{3}V_{34}),$
$\displaystyle\vdots$ $\displaystyle\mathfrak{w}_{n}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}\mathfrak{grad}^{n}V_{n,n-1}.$

If $||\mathfrak{w}_{1}-\mathfrak{w}_{S}||<\frac{1}{2}k_{P}\mu$, then
$||\mathfrak{grad}_{1}V_{12}||<\frac{\mu}{2}\leq\mu$, and hence there is a
relative configuration $E_{12}$ such that $\mathfrak{grad}_{1}V_{12}$ equals
$\frac{\mathfrak{w}_{1}-\mathfrak{w}_{S}}{k_{P}}$.

Having decided the relative configuration of agent 2 with respect to agent 1,
let us move to the next equation. Next, substituting this, we get to the
second equation in the system which is

$\displaystyle\mathfrak{w}_{2}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}(\mathfrak{grad}^{2}V_{21}+\mathfrak{grad}^{2}V_{23})$
$\displaystyle=k_{P}(-\overbrace{\mathfrak{grad}^{1}V_{12}}^{\text{already
determined}}+\mathfrak{grad}^{2}V_{23})$

. Hence we have

$\displaystyle
k_{P}\mathfrak{grad}^{2}V_{23}=(\mathfrak{w}_{2}-\mathfrak{w}_{S})+k_{P}\mathfrak{grad}^{1}V_{12}.$
(112)

For the existence of a solution, we must have
$||\mathfrak{w}_{2}-\mathfrak{w}_{S}||\leq\frac{k_{P}\mu}{2}$ as well. If it
holds, then $||\mathfrak{grad}^{2}V_{23}||\leq\mu$ (by triangle inequality)
and hence there exists a relative configuration $E_{23}$. Proceeding further,
we see that if $||\mathfrak{w}_{i}-\mathfrak{w}_{S}||\leq\frac{k_{P}\mu}{2}$
for $i=3,\cdots,n-1$, we determine
$k_{P}grad^{i}V_{i,i+1}=(\mathfrak{w}_{i}-\mathfrak{w}_{S})+k_{P}\mathfrak{grad}_{i-1}V_{i-1,i}$.
Hence, by induction, we have

$\displaystyle
k_{P}\mathfrak{grad}^{i}V_{i,i+1}=\sum_{j=1}^{i}(\mathfrak{w}_{j}-\mathfrak{w}_{S}).$
(113)

With this, we come to the last equation

$\displaystyle\mathfrak{w}_{n}-\mathfrak{w}_{S}$
$\displaystyle=k_{P}grad^{n}V_{n,n-1}$ (114)
$\displaystyle=-k_{P}grad^{n-1}V_{n-1,n}=-\sum_{j=1}^{n-1}(\mathfrak{w}_{j}-\mathfrak{w}_{S}),$
(115)

which is trivially satisfied as
$\mathfrak{w}_{S}:=\frac{1}{n}\sum_{j=1}^{n}\mathfrak{w}_{j}$

So, we get the existence of velocity synchronous solution when the magnitude
of deviations are small enough, for the line graph as well.

####  6.3.4 Trees

With the same logic as in consensus, one can generalize these to trees as
well. Assuming
$||\mathfrak{w}_{i}-\mathfrak{w}_{S}||\leq\frac{1}{\mathrm{max}_{i}deg(i)}k_{P}\mu$
and solving first for the leaf nodes and going further down, we can verify
that synchronous solution is achieved. This is proved by induction on the
number of nodes of the tree. When $n=2$, we have already shown. Let us assume
that for a tree of $n-1$ nodes or lower, if
$||\mathfrak{w}_{i}-\mathfrak{w}_{S}||\leq\frac{1}{max_{i}deg(i)}k_{P}\mu$,
then a synchronous solution exists. With this, consider a tree with $n$ nodes.
It has aleast one leaf node with degree 1. Without loss of generality, label
it the last node $n$ and its lone neighbor as $n-1$. Then, we have at
equilibrium,

$\displaystyle\mathfrak{w}_{n}-\mathfrak{w}_{S}=k_{P}\mathfrak{grad}^{n}V_{n,n-1}.$
(116)

Since
$||\mathfrak{w}_{n}-\mathfrak{w}_{S}||<\frac{1}{max_{i}deg(i)}k_{P}\mu\leq
k_{P}\mu$, a solution exists for $\mathfrak{grad}_{n}V_{n,n-1}$. Now, remove
the corresponding leaf and the edge to get another connected tree of $n-1$
edges. Wherever one sees $\mathfrak{grad}^{n-1}V_{n-1,n}$, we know that it is
equal to $-\mathfrak{grad}^{n}V_{n,n-1}$ and we know that its magnitude is
less than or equal to $\frac{1}{max_{i}deg(i)}$. Combine it with the term
$\mathfrak{w}_{n}-\mathfrak{w}_{S}$ and proceeding further using induction, we
get the result.

###  6.4 Counting argument for the existence of a unique cohesive synchronous
solution for arbitrary graphs

In this section, we give a simple counting argument to support the existence
of a synchronous solution when $||\mathfrak{w}_{i}-\mathfrak{w}_{S}||$ is
small enough in magnitude.

The system of equations that we have to get a synchronous solution is

$\displaystyle\mathfrak{w}_{i}-\mathfrak{w}_{S}=\sum_{j=1}^{n}a_{ij}\mathfrak{grad}^{i}V_{ij}.$
(117)

The important thing is that not all the gradients in the right hand side of
(117) are independent. As an example, let us say that the gradients
$\mathfrak{grad}^{2}V_{12}=\mathfrak{grad}_{E_{12}}V=\zeta_{12}$ and
$\mathfrak{grad}^{3}V_{23}=\mathfrak{grad}_{E_{23}}=\zeta_{23}$ are known, due
to the local bijectivity of the gradient ensures that the errors
$E_{12},E_{23}$ are uniquely fixed in this neighborhood of $e$. But once
$E_{12}.E_{23}$ are known, it fixes $E_{13}$ as
$E_{13}=g_{1}^{-1}*g_{3}=(g_{1}^{-1}*g_{2})*(g_{2}^{-1}*g_{3})=E_{12}*E_{23}$.
So, in a similar manner, once the inter-agent positions $E_{i,i+1}$ are chosen
such that gradients $\mathfrak{grad}^{i}\mathfrak{grad}V_{i,i+1}$ are fixed,
all other inter-agent positions and their relative gradients are fixed. Since
$i$ runs from $1$ to $n-1$, only $n-1$ gradient terms are independent. So,
number of independent unknowns is $n-1$.

How many independent equations do we have? Equations in (117) might look like
$n$ equations but we will soon verify that only $n-1$ of them are independent.
This follows from summing the $n$ equations in (117).

Doing this, we get

$\displaystyle\mathfrak{w}_{i}-\mathfrak{w}_{S}$
$\displaystyle=\sum_{j=1}^{n}a_{ij}\mathfrak{grad}^{i}V_{ij}$ (118)
$\displaystyle\underbrace{\Longrightarrow\sum_{i=1}^{n}(\mathfrak{w}_{i}-\mathfrak{w}_{S})}_{\text{
add to 0 as $n\mathfrak{w}_{S}=\sum_{i=1}^{n}\mathfrak{w}_{i}$ }}$
$\displaystyle=\underbrace{\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}\mathfrak{grad}^{i}V_{ij}}_{\text{add
to 0}}.$ (119)

So, the $n$ equations are linearly dependent as they all add to zero. This
tells that any one equation can be written in terms of the other $n-1$
equations. So, there are only $n-1$ independent equations which matches the
number of independent unknowns (the $n-1$ gradients that was shown before).
So, this counting argument dictates that there exist a unique solution for the
gradients if their magnitudes are low enough to lie in the locally bijective
neighborhood. In particular, since a synchronous solution exists when
$\mathfrak{w}_{i}=\mathfrak{w}_{S}$ for all $i$ (identical agents - consensus
is equivalent to synchronization), for small enough magnitude of
$||\mathfrak{w}_{i}-\mathfrak{w}_{S}||$, there must still exist a solution to
this system of equations.

###  6.5 Local Asymptotic Stability of Synchronization

Finally, we investigate the important question. If a synchronous solution
exists in the gradient-injective neighborhood, is it indeed locally
exponentially stable? Let us begin by proving some elementary results that
would help in establishing a positive answer to the question.

The dynamics of the entire system of agents can be cast in the form as

$\displaystyle v=\mathfrak{w}-k_{P}\mathfrak{grad}V_{T},$ (120)

where $v=(v_{1},\cdots,v_{n})$ and
$\mathfrak{w}=(\mathfrak{w}_{1},\ldots,\mathfrak{w}_{n})$. So, we see that the
vector field is addition of two vector fields - a constant left-invariant
vector field $\mathfrak{w}$ and a gradient field. In the consensus case, we
had only the gradient term. Now, we have an additional drift velocity that is
constant (when viewed in the Lie algebra by left translation).

Hence the Jacobian of the vector field is the sum of two Jacobians - the
Jacobian of the left invariant vector field $\mathfrak{w}$ and the Jacoobian
of the negative gradient of $V_{T}$ which is the negative Hessian of $V_{T}$.

We saw from the corollary in (6) that the map $L_{Y}(X):=\nabla_{X}Y$ is skew
symmetric if $Y$ is a left invariant vector field! Replacing $Y$ by
$\mathfrak{w}$ (which is also a left-invariant vector field as they are
constant left-velocities), we get that the Jacobian of $W$ that is also
defined as $\mathfrak{J}\mathfrak{w}(v)=\nabla_{v}\mathfrak{w}$ is also skew-
symmetric. We already saw in the linear algebraic result in the preliminaries
that the addition of a skew-symmetric operator to an already stable symmetric
operator does not affect the stability property. So, we can investigate the
stability of the synchronization system by just investigating the stability of
the symmetric part of the Jacobian which is the negative Hessian of $V_{T}$,
thereby ignoring the influence of the drift $\mathfrak{w}$ completely. But the
investigation of stability of the negative Hessian of $V_{T}$ already has been
carried out in the consensus case with $\mathfrak{w}=0$. So, those results are
transferable now.

We look for synchronization solution where all the inter-agent errors are in
the gradient-bijective neighborhood $U$, which is $g_{i}^{-1}*g_{j}\in U\hskip
5.69054pt\forall i,j$. A small result that gives insight into the analysis
follows:

###### Theorem 26

If $g\in U$, then $\mathfrak{J}\mathfrak{grad}_{g}V=\mathfrak{hess}_{g}V$ is
always positive definite for all $g\in U$.

Proof:
Note that when $g\in U$, $\mathfrak{grad}_{g}V$ is bijective. Therefore, its
Jacobian also has to be invertible and always has to be full rank for all $p$.
But the Jacobian of a gradient is the Hessian. So, the Hessian has to be full
rank for all points in $U$. So, the eigen values of the Hessian have to be
non-zero and real (the eigen values of a symmetric matrix like Hessian is
always real). The Hessian at identity $e$ is positive definite as $e$ is the
global minimum of the polar Morse function $V$. So, all the eigen values of
the Hessian at $e$ are positive. Since the eigen values are continuous
functions of the matrices and the Hessian is continuous and smooth as well,
they continuously vary in $U$. But they all have to be positive. Even if one
of the eigen values at some $p\in U$ were negative, we can have a path joining
$e$ to $p$ ($U$ is path connected). Since the eigen values are continous
function in the curve and change from being positive at $e$ to negative at
$p$, it would have to attain the value zero at some point in the middle, say
$p^{\prime}\in U$. So, the Jacobian of the gradient of $V$ at $p^{\prime}$
(which is the Hessian of $V$ at $p^{\prime}$) would have a zero eigen value.
This would make the Jacobian non-invertible at $p^{\prime}\in U$ and hence
contradict the fact that it is full rank and invertible at all points in $U$.

###### Theorem 27

The synchronous solution where all the agents are phase-cohesive with respect
to the gradient-bijective neighborhood $U$ around $e$ \- i.e. $\forall
i,j\hskip 5.69054ptg_{i}^{-1}*g_{j}\in U$, is always locally exponentially
stable.

Proof:
The Jacobian of the synchronization system, that is to be analyzed for
stability, is the same as that of the consensus (as the skew symmetric
component can be ignored for stability analysis). But the Jacobian, in case of
consensus, was guaranteed to be negative-semidefinite as long as all
$\nabla^{i}\mathfrak{grad}^{i}V_{ij}=\mathfrak{hess}(V)_{g_{j}^{-1}*g_{i}}$,
were guaranteed to be positive definite. But since we have assumed that
$g_{j}^{-1}*g_{i}\in U$ (synchronous solutions in $U$) and hence
$\mathfrak{hess}(V)_{g_{j}^{-1}*g_{i}}$ is positive definite for all $i,j$ by
Theorem 27. Hence, the Jacobian is negative semi-definite, which by similar
techniques, guarantees local exponential stability to the manifold of velocity
synchronous solutions, if they exist.

##  7 Conclusion and Future Work

Thus, we have built a unified and a geometrically elegant theory for first and
second-order consensus and synchronization, for Lie groups admitting a bi-
invariant metric by making use of a special class of functions called
$G-$polar Morse functions. We have seen that such functions indeed exist in
the commonly encountered groups like $SO(n)$ and $U(n)$. The next interesting
question to ask would be, given a compact Lie group, can one always guarantee
the existence of such $G-$polar Morse functions? Is a constructive proof
possible? This is an interesting mathematical problem. Representation theory
ensures that every compact Lie group can be embedded in $U(n)$ and we have a
$G$-polar Morse function in $U(n)$ as $V(R)=tr(I-Re[R])$. Can we show that
this function, when restricted to any Lie subgroup of $U(n)$, is still a
$G$-polar Morse function on the subgroup as well? If the answer is positive,
this would give a constructive proof on the existence of such $G$-polar Morse
functions on any compact Lie group whose faithful matrix representation by
unitary matrices can be constructed.

Since every compact Lie group has a unitary representation (and hence
isomorphic to a subgroup of $U(n)$) and since $V(R)=tr(I-Re[R])$ is a
$G$-polar Morse function in $U(n)$, a natural question will be, is the
restriction of $V$ on any Lie subgroup $G^{\prime}$ of $U(n)$, render $V$ as a
$G$-polar Morse function on $G^{\prime}$ as well? The authors would like to
explore a definitive answer to this conjecture based on applying Morse
theoretic and group theoretic techniques in the future.

The issue of characterizing graphs that have almost globally stable consensus
solutions is again a very important open problem. In this work, it was shown
to include trees. For oscillators, it is also shown to include complete graphs
and sufficiently dense graphs. Extending them to arbitrary compact Lie groups
would be a significant contribution.

Other extensions would be to include time-varying adjacency matrices and to
extend Theorems 15,16 in full generality to the present setting in Lie groups
and give the explicit rates for the exponentials of stability and bounds on
gains. The authors also intend to extend these techniques to formation control
and tracking on Lie groups with a bi-invariant metric.

## References

  * [1] V.D. Blondel, J.M. Hendrickx, A. Olshevsky, and J.N. Tsitsiklis.  Convergence in multiagent coordination, consensus, and flocking.  In Proceedings of the 44th IEEE Conference on Decision and Control, pages 2996–3000, 2005.
  * [2] F. Bullo.  Lectures on Network Systems.  Kindle Direct Publishing, 1.6 edition, 2022.
  * [3] Francesco Bullo and Andrew Lewis.  Geometric Control of Mechanical Systems.  Springer, New York-Heidelberg-Berlin, 2004.
  * [4] Eduardo Canale and Pablo Monzón.  Almost Global Synchronization of Symmetric Kuramoto coupled oscillators.  08 2008.
  * [5] Morris H. DeGroot.  Reaching a consensus.  Journal of the American Statistical Association, 69(345):118–121, 1974.
  * [6] Dimos V. Dimarogonas, Panagiotis Tsiotras, and Kostas J. Kyriakopoulos.  Laplacian cooperative attitude control of multiple rigid bodies.  In 2006 IEEE Conference on Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control, pages 3064–3069, 2006.
  * [7] Florian Dörfler and Francesco Bullo.  Synchronization in complex networks of phase oscillators: A survey.  Automatica, 50(6):1539–1564, 2014.
  * [8] Heinz Hanßmann, Naomi Ehrich Leonard, and Troy R. Smith.  Symmetry and reduction for coordinated rigid bodies.  European Journal of Control, 12(2):176–194, 2006.
  * [9] Kenneth Hoffman and Ray A. Kunze.  Linear Algebra.  PHI Learning, 2004.
  * [10] C Huygens.  Oeuvres complètes de Christiaan Huygens.  1893\.
  * [11] A. Jadbabaie, Jie Lin, and A.S. Morse.  Coordination of groups of mobile autonomous agents using nearest neighbor rules.  IEEE Transactions on Automatic Control, 48(6):988–1001, 2003.
  * [12] Philip Holmes John Guckenheimer.  Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields.  Springer New York, NY, 1 edition, 1983.
  * [13] Milnor J.W.  Morse Theory.  Princeton University Press, 1969.
  * [14] Hassan K. Khalil.  Nonlinear Systems.  Prentice Hall, 2002.
  * [15] Daniel E Koditschek and Elon Rimon.  Robot navigation functions on manifolds with boundary.  Advances in Applied Mathematics, 11(4):412–442, 1990.
  * [16] Shuyang Ling, Ruitu Xu, and Afonso S. Bandeira.  On the landscape of synchronization networks: A perspective from nonconvex optimization.  SIAM Journal on Optimization, 29(3):1879–1907, 2019.
  * [17] Jianfeng Lu and Stefan Steinerberger.  Synchronization of kuramoto oscillators in dense networks.  Nonlinearity, 33(11):5905–5918, 2020.
  * [18] Marston Morse.  The existence of polar non-degenerate functions on differentiable manifolds.  Annals of Mathematics, 71(2):352–383, 1960.
  * [19] Alain Sarlette, Silvère Bonnabel, and Rodolphe Sepulchre.  Coordinated motion design on Lie groups.  IEEE Transactions on Automatic Control, 55(5):1047–1058, 2010.
  * [20] Alain Sarlette and Rodolphe Sepulchre.  Consensus optimization on manifolds.  SIAM Journal on Control and Optimization, 48(1):56–76, 2009.
  * [21] R. Sepulchre.  Consensus on nonlinear spaces.  Annual Reviews in Control, 35(1):56–64, 2011.
  * [22] Rama Seshan, Ravi N Banavar, and Arun D Mahindrakar.  Geometric second-order laplacian flow for consensus on lie groups.  In 2022 European Control Conference (ECC), pages 2191–2195, 2022\.
  * [23] Steven H. Strogatz.  From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled oscillators.  Physica D: Nonlinear Phenomena, 143(1):1–20, 2000.
  * [24] Richard Taylor.  There is no non-zero stable fixed point for dense networks in the homogeneous Kuramoto model.  J. Phys. A: Math. Theor., 45(5):055–102, 2012.
  * [25] Roberto Tron, Bijan Afsari, and René Vidal.  Riemannian consensus for manifolds with bounded curvature.  IEEE Transactions on Automatic Control, 58(4):921–934, 2013.
  * [26] Girvan M. Wiley DA, Strogatz SH.  The size of the sync basin.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 16(1):10.1063–1.2165594, 2005.