Adjacency Criterion For Gradient Flow With Multiple Local Maxima

arXiv:1412.6731v3 [math.DS] 8 Sep 2017

Xudong Chen1

Abstract— In this paper, we investigate the geometry of a
general class of gradient flows with multiple local maxima.
we decompose the underlying space into disjoint regions of
attraction and establish the adjacency criterion. The criterion
states a necessary and sufficient condition for two regions of
attraction of stable equilibria to be adjacent. We then apply
this criterion on a specific type of gradient flow which has as
many as n! local maxima. In particular, we characterize the set
of equilibria, compute the index of each critical manifold and
moreover, find all pairs of adjacent neighbors. As an application
of the adjacency criterion, we introduce a stochastic version
of the double bracket flow and set up a Markov model to
approximate the sample path behavior. The study of this specific
prototype with its special structure provides insight into many
other difficult problems involving simulated annealing.

I. I NTRODUCTION
Ascent/Descent equations often provide the most direct
demonstration of the existence of a maximum/minima and
can provide an easily implemented algorithm to find the
maximum/minima (see, for example, [1]–[3]). Of course
when the function being maximized/minimized has multiple
local maxima/minima, steepest ascent/descent needs to be
modified and for the last several decades the modification of
choice has been some type of simulated annealing procedure.
However, because simulated annealing is slow and subject to
variable results because of its stochastic nature, there remains
considerable interest in finding methods for improving its
speed and, in general, learning more about its performance.
But often this requires the knowledge of the sample path
behavior.
In this paper, we start with the development of a basic
theorem about the geometry of a general class of gradient
flows. In particular, we decompose the underlying space into
disjoint regions of attraction associated with the gradient
flow, and then establish the adjacency criterion. This theorem
states a necessary and sufficient condition for two regions of
attraction of stable equilibria to be adjacent, i.e, for them to
share a boundary of co-dimension one.
The adjacency criterion has a large potential impact on
studying stochastic gradients. For example, to approximate
the sample path behavior of a stochastic gradient, R. W.
Brockett established a Markov model in [4] whose states
consist of all stable equilibria. Each transition probability
is evaluated by solving a related first-hitting time problem,
the computational complexity is in a large-scale. The adjacency criterion then sheds light on the problem. Knowing
adjacent neighbors reduces the computational amount as
the transition probability between non-adjacent equilibria is
1 X. Chen is with the ECEE department, University of Colorado at
Boulder. xudong.chen@colorado.edu

negligible when compared with the transition probability
between adjacent equilibria, especially under the case where
the noise is moderate.
The adjacency criterion also relates to a number of geometric factors. For example, the depth of the potential well
associated with a stable equilibrium, the volume of a region
of attraction, the area of the boundary shared by a pair of
adjacent neighbors and etc, all these factors are important
for explaining simulated annealing.
As an demonstration of adjacency criterion, we consider
a prototype system with the gradient flow of the type Ḣ =
[H, [H, π(H)]], the map π projects a matrix onto its diagonal.
This flow is a prototype for gradient systems with multiple
stable equilibria, it has as many as n! stable equilibria, each is
a diagonal matrix and one-to-one corresponds to an element
in the permutation group Sn . In this paper, we will characterize all pairs of adjacent neighbors, the characterization is
simple and clean. In particular, we will show that each pair
of adjacent neighbors is related to a simple transposition,
so then the n! regions of attraction are arranged in a way
that each one has (n − 1) adjacent neighbors. A stochastic
version of the gradient flow is studied at the end of this paper
as a concrete example of the application of the adjacency
criterion. In particular, we set up an optimal control problem
as an approach to evaluate the transition probability.
After this introduction, we proceed in steps: in section 2,
we will introduce the adjacency criterion after a quick review
of some basic notions about Morse-Bott gradient systems.
In section 3, we will introduce the isospectral manifold,
the normal metric and the double bracket flow under a
special class of potentials functions. In section 4, we will
focus on a specific quadratic potential function and show
that the set of equilibria under the potential function is a
mix of isolated points and continuum manifolds. In section
5, we will show that the quadratic potential is a MorseBott function by explicitly working out the Hessian of the
potential. In particular, we will compute the index and the
co-index of each critical manifold. In section 6, we will apply
the adjacency criterion to characterize all pairs of adjacent
neighbors. In the last section, we will work on a stochastic
gradient as an application of the adjacency criterion. In
particular, we will show how the adjacency criterion will
simplify the evaluation of transition probability.
II. A DJACENCY CRITERION
In this section, we will introduce the adjacency criterion.
Some mathematical backgrounds are needed here, in this
paper we will only introduce terminologies that are necessary
for establishing the criterion.

A potential Ψ on a Riemannian manifold M is a MorseBott function if the set of equilibria under the gradient flow
grad(Ψ) is a finite disjoint union of connected submanifolds
{E1 , · · · , En }, and the Hessian of Ψ is nondegenerate when
restricted at the normal space N p Ek at any point p ∈ Ek and
for any Ek . (see, for example, [5] for more details about
Morse-Bott functions)
For convenience, we say each set Ek is a critical manifold.
Assume Ψ is a Morse-Bott function, the index of each
submanifold Ek is the number of negative eigenvalues of
the Hessian restricted at N p Ek for some p ∈ Ek , this is welldefined because the index of Ek is independent of the choice
of p. Similarly, the co-index of Ek is the number of positive
eigenvalues of the Hessian restricted at N p Ek . An equation
relating the index, co-index and the dimension of M is
indEk + co-indEk + dim Ek = dim M

So two stable manifolds S j and Sk are adjacent if and only
if there is a Ki such that Ki ⊂ ∂W s (S j ) ∩ ∂W s (Sk ).

(1)

A stable critical manifold is then a critical manifold of coindex 0.
Let Ek be a critical manifold, the stable manifold of Ek
is defined by
W s (Ek ) = {p ∈ M| lim ϕt (p) ∈ Ek }
t→∞

(2)

where ϕt (p) is the solution of the differential equation
ṗ =grad(Ψ) parametrized by time t. The unstable manifold
of Ek is defined in a similar way as
W u (Ek ) = {p ∈ M| lim ϕt (p) ∈ Ek }
t→−∞
and W u (Ek )

(3)

The dimensions of W s (Ek )
are indEk + dim Ek
and co-indEk + dim Ek respectively. A decomposition of M,
with respect to stable/unstable manifolds of Ek ’s, is given by
n
[

M=

W s (Ek )

(4)

W u (Ek )

(5)

k=1

or

n
[

M=

k=1

If only stable critical manifolds {S1 , · · · , Sl } are concerned,
then
M=

l
[

(6)

We are interested in how these cells are arranged in the
underlying space. With terminologies above, we are now
ready to state the adjacency criterion.
Fact 1 (Adjacency Criterion): Suppose Ψ is a Morse-Bott
function on a smooth manifold M. Let {S1 , · · · , Sl } be the
collection of stable critical manifolds and let {K1 , · · · , Km }
be the critical manifolds of co-index 1. If
(W u (Ki ) − Ki ) ⊂

i=1

l
[

W s (S j )

(7)

j=1

then the boundary of each W s (S j ) is piece-wise smooth, each
piece is a stable manifold of some Ki , i.e,
∂W s (S j ) =

Before heading to its application on the isospectral manifold, we point out that the assumption described by equation
(7) includes a broad range of gradient systems. For example,
in a Morse-Smale gradient system, all equilibria are isolated
points and the unstable manifold of each Ki is a one dimensional curve and its boundaries consists of stable equilibrium
points as illustrated in Fig. 1. The class of Morse-Smale
gradient system is a residual class in all gradient systems(see,
for example, [6], [7] for more details about Morse-Smale
systems).
III. I SOSPECTRAL MANIFOLD AND A CLASS OF
SYMMETRIC POTENTIALS

W s (Si )

i=1

m
[

Fig. 1. In this figure, each Si is a stable equilibrium, each Ki j is an
equilibrium of co-index 1 and E is an equilibrium of co-index 2. The
pair (S1 , S2 ), for example, consists of two adjacent neighbors because their
regions of attraction share the stable manifold of K12 as a co-dimension
one boundary. On the other hand, S1 and S3 are not adjacent because their
regions of attraction intersect each other only at E.

[
Ki ∈∂W s (S j )

W s (Ki )

(8)

In this section, we will introduce the isospectral manifold
with strongly disjoint eigenvalues, the normal metric and a
special class of symmetric potential functions.
Let Sym(Λ) denote the isospectral manifold, in case here,
it refers to the collection of all n-by-n real symmetric
matrices with a fixed set of eigenvalues Λ = {λ1 , · · · , λn }.
We assume that the set Λ is strongly disjoint, i.e,
• for any two nonempty disjoint subsets {λa1 , · · · , λa p }
p
and {λb1 , · · · , λbq } of Λ, the inequality 1p ∑k=1
λak 6=
1 q
q ∑k=1 λbk holds.
The assumption on Λ is a stronger version of the condition
that all eigenvalues are distinct. Yet this condition is generic
in the sense that if we randomly pick a vector (λ1 , · · · , λn )
in Rn , then Λ is strongly disjoint for almost sure because the
p
set defined by equations 1p ∑k=1
λak = 1q ∑qk=1 λbk is a finite
n
union of hyperplanes in R . On the other side, as we will

see later this condition on Λ is necessary and sufficient for
a class of potential functions on Sym(Λ) to be Morse-Bott
functions which is a key assumption for application of the
adjacency criterion.
The so called normal metric g on Sym(Λ) is defined as
follows, the tangent space TH Sym(Λ) consists of elements of
the form [H, Ω] with Ω skew symmetric, since all eigenvalues
are distinct, the adjoint map adH : Ω 7→ [H, Ω] is then an
isomorphism. For any two tangent vectors [H, Ω1 ], [H, Ω2 ]
in TH Sym(Λ), the normal metric g at H is then defined by
g([H, Ω1 ], [H, Ω2 ]) := −tr(Ω1 Ω2 )

(9)

It is routine to check that g is positive definite. Equipped with
the normal metric, the gradient flow of a smooth function
Ψ ∈ C∞ (Sym(Λ)) is then the double bracket flow
Ḣ = [H, [H, Ψ0 (H)]]

(10)

where Ψ0 (H) denotes the derivative of Ψ with respect to H
For convenience, we assume that eigenvalues are ordered
as λ1 < · · · < λn and we denote by d1 , · · · , dn the diagonal
entries of a matrix H in Sym(Λ). There is a special class
of potentials functions Ψ on Sym(Λ), each is symmetric in
diagonal entries and can be generated by a scalar function
φ ∈ C∞ [λ1 , λn ] via the equation
n

Ψ(d1 , · · · , dn ) = ∑

Z di

φ (x)dx

(11)

i=1 λ1

As the sum of the diagonal entries is constant for any matrix
in Sym(Λ), there is actually a broad class of symmetric
potentials can be expressed in this way. In fact, we have
shown in [8] that if Ψ(d1 , · · · , dn ) can be expressed as a
power series of symmetric polynomials, then there is a scalar
function φ such that the equation (11) holds. Moreover, we
have also shown in [8] that for almost all scalar functions φ ,
the potential Ψ generated by equation (11) is a Morse-Bott
function.
In this paper, we will work on a simple case where φ (x) =
x. The corresponding potential is then in a diagonal form as
Ψ=

1 n 2
∑ di
2 i=1

(12)

In the rest of paper, we will just call this specific quadratic
potential the diagonal potential. In the next two sections,
we will characterize the critical manifolds associated with
the gradient flow and compute explicitly the Hessian at each
equilibrium point.
IV. T HE SET OF EQUILIBRIA ASSOCIATED WITH THE
DIAGONAL POTENTIAL

For convenience, we let π be a projection map sending
each matrix H to the diagonal matrix diag(d1 , · · · , dn ). Then
the gradient vector field f (H) with respect to the diagonal
potential is simply
f (H) = [H, [H, π(H)]]

(13)

A matrix H ∈ Sym(Λ) is an equilibrium if f (H) = 0
and it happens if and only if [H, π(H)] = 0 because
tr(π(H) f (H)) = −tr([H, π(H)]2 ). This leads us to
Lemma 2: If H is an equilibrium, then there exists a
permutation matrix P such that PT HP is block-diagonal, i.e,
PT HP = Diag(H1 , · · · , Hk )

(14)

Suppose di1 , · · · , dini are diagonal entries of Hi , then
di1 = · · · = dini

(15)

and this holds for each Hi .
Proof: The commutator [H, π(H)] vanishes if and only
if hi j (di − d j ) = 0 for each pair of (i, j).
Let Λi be the set of eigenvalues
of Hi , then (Λ1 , · · · , Λk ) is
S
a partition of Λ, i.e, Λ = ki=1 Λi and Λi ∩ Λ j = ∅ if i 6= j.
For convenience, we let #(Λi ) denote the cardinality of Λi ,
let s(Λi ) denote the sum of its elements and we define
µ(Λi ) := s(Λi )/#(Λi )

(16)

di1 = · · · = dini = µ(Λi )

(17)

then
A symmetric matrix H is said to be irreducible if there
isn’t a permutation matrix P such that PT HP is a nontrivial
block-diagonal matrix.
Lemma 3: Each Hi in equation (14) is irreducible, moreover µ(Λi ) 6= µ(Λ j ) if i 6= j.
Proof: Suppose Hi is not irreducible, we may assume
that Hi = Diag(Hi1 , Hi2 ), let Λi1 = Λi2 be the set of eigenvalues of Hi1 and Hi2 respectively, then µ(Λi1 ) = µ(Λi2 ) =
µ(Λi ) which contradict the fact that Λ is strongly disjoint.
By applying the same arguments, we conclude that µ(Λi )
and µ(Λ j ) are disjoint if i 6= j.
An equilibrium H gives rise to a partition of Λ. Conversely
a partition of Λ will correspond to a set of equilibria. Let A
be the collection of all choices of partitions of Λ. Given a
choice of partition α = (Λ1 , · · · , Λk ), we define a subset of
Sym(Λ) as
Eα := {Diag(H1 , · · · , Hk )|π(Hi ) = µ(Λi )}

(18)

clearly Eα consists exclusively of equilibria. Moreover it is
a smooth manifold as a consequence of the next fact
Fact 4: Let Λ0 = {λ10 , · · · , λn0 0 } be a subset of Λ and
0
let C(Λ0 ) ⊂ Rn be the convex hull of all vectors
(λσ0 (1) , · · · , λσ0 (n0 ) ) where σ varies over all permutations of
{1, · · · , n0 }, then the image of the projection
0

π : Sym(Λ0 ) −→ R#(Λ )

(19)

C(Λ0 )(see,

is the convex hull
for example, [9]). Let ~e be a
0
vector of all ones in R#(Λ ) and define
X(Λ0 ) := π −1 (µ(Λ0 )~e)
then π is a submersion at each point H ∈ X(Λ0 ).

(20)

other hand, either PT Eα P = Eα or PT Eα P ∩ Eα = ∅, and
P fixes Eα if and only if P is block-diagonal, i.e, P =
Diag(P1 , · · · , Pk ) with each Pi a ni -by-ni permutation matrix.
There are exactly Πki=1 ni ! many block-diagonal permutations
matrices, so by Burnside’s counting formula, there are as
many as n!/Πki=1 ni ! disjoint sets in the orbit of Eα , each is
a smooth submanifold in Sym(Λ).

Fig. 2.
The convex hull C(Λ) under the case Λ = {λ1 , λ2 , λ3 }. Let
~e := (1, 1, 1)T , then the line R~e intersects C(Λ) perpendicularly at the point
µ(Λ)~e.

A complete proof can be found in [8]. Assuming the fact
above, then an immediate consequence is that X(Λ0 ) is a
smooth manifold of dimension 21 (#(Λ0 ) − 1)(#(Λ0 ) − 2). An
identification is that Eα ' Πki=1 X(Λi ), so
k

dim Eα = ∑ (#(Λi ) − 1)(#(Λi ) − 2)

(21)

i=1

An upshot is that the set Eα is a set of discrete points if and
only if each #(Λi ) is either one or two, in the case all Λi ’s
are singletons, the set Eα consists only of a diagonal matrix.
At this moment, we have characterized the set equilibria
that are block-diagonal, equilibria that are off block-diagonal
can be generated by letting the group of permutation matrices
act on Eα ’s by conjugation as we will describe below.
Lemma 5: If H is an equilibrium, then so is PT HP for
any permutation matrix P.
Proof: We check that π(PT HP) = PT π(H)P and hence
conjugation by permutation matrices commutes with the
commutator, i.e,
PT [H, π(H)]P = [PT HP, π(PT HP)]
So

f (PT HP) = 0

(22)

exactly when f (H) = 0.

Lemma 5 can be regarded as a converse argument of
lemma 2.
Theorem 6: Suppose α = (Λ1 , · · · , Λk ) is a choice of partition and suppose #(Λi ) = ni . Let the group of permutation
matrices act on Eα by conjugation, then the orbit of Eα
contains as many as n!/Πki=1 ni ! disjoint smooth submanifolds
in Sym(Λ), each consists exclusively of equilibria. The set
of equilibria is then the union of orbits of Eα as α varies
over A .
Proof: For any permutation matrix P, the set PT Eα P
consists exclusively of equilibria by lemma 5. On the

In the rest of this paper, we will abuse the term critical
manifold by referring it to an Eα or any set in its orbit as Eα
may have multiple connected components. (see, for example,
a discussion on the number of components in [8]). Notice
that in the orbit of Eα , there exist multiple critical manifolds
that are block-diagonal, for example, the orbit of a diagonal
matrix is the set of all diagonal matrices. Actually given
a choice of partition α = (Λ1 , · · · , Λn ), there are as many
as k! critical manifolds that are block-diagonal leaving the
others off block-diagonal. If we want to choose a canonical
representative among the orbit, then permute Λ1 , · · · , Λk
if necessary so that µ(Λ1 ) < · · · < µ(Λk ), this is possible
because eigenvalues of Λ are strongly disjoint.
V. T HE H ESSIAN OF THE DIAGONAL POTENTIAL
In this section, we will show that the diagonal potential is
a Morse-Bott function by explicitly working out the Hessian
of the potential at each equilibrium point and compute its
eigenvalues.
Let H denote the Hessian of a potential Ψ. On a Riemannian manifold, it is defined by
H = ∇2 Ψ

(23)

where ∇ is the Levi-Civita connection and if we evaluate the
Hessian at an equilibrium point, then
H (X,Y ) = X(g(grad(Ψ),Y ))

(24)

In this specific case, we have
Fact 7: Suppose H is an equilibrium, then the Hessian H
evaluated at H is given by
H ([H, Ωi ], [H, Ω j ]) =

−tr([H, Ωi ][π(H), Ω j ])
−hπ([H, Ωi ]), π([H, Ω j ])i (25)

where h·, ·i is the normal inner-product in Rn .
We omit the proof here as this is a direct computation
following equation (24). Given a choice of partition α =
(Λ1 , · · · , Λn ), we assume #(Λi ) = ni , then the dimension of
the normal space at a point H ∈ Eα is given by
k
1
dim NH Eα = {n(n − 1) − ∑ (ni − 1)(ni − 2)}
2
i=1

(26)

For convenience, let nα := dim NH Eα . We will now construct
an orthogonal basis N of NH Eα with respect to H , i.e,
H (N, N) 6= 0, ∀N ∈ N

(27)

H (N, N 0 ) = 0, if N 6= N 0

(28)

Suggested by the partition α, we divide a n-by-n matrix
N into k-by-k blocks as


B11 · · · B1k

.. 
..
(29)
N =  ...
.
. 
Bk1 · · · Bkk
with the pq-th block of dimension n p -by-nq . The basis N
consists of two parts: the block-diagonal part Nd and the off
block-diagonal part No .
1. Constructing No : Write H = Diag(H1 , · · · , Hk ) with
each Hi ∈ Sym(Λi ) and let ~vi1 , · · · ,~vini be the unitlength eigenvectors of Hi with respect to the eigenvalues
λi1 , · · · , λini .
Given integers p and q, define a set of symmetric matrices
N pq in the way that for each matrix N pq,i j ∈ N pq , all blocks
except B pq and Bqp are zeros while
B pq (= BTqp ) = (λ pi − λq j )~v pi~vTq j

(30)

for some i = 1, · · · , n p and some j = 1, · · · , nq , so there are
exactly n p nq symmetric matrices in the set N pq .
Lemma 8: The set No := p<q N pq is contained in NH Eα .
If N pq,i j ∈ N pq and N p0 q0 ,i0 j0 ∈ N p0 q0 , then

3. Orthogonality of No and Nd : First notice that by
combining No and Nd , there are exactly nα matrices, i.e,
k

nα =

∑
1≤i< j≤k

ni n j + ∑ (ni − 1)

(33)

i=1

because of the equality ∑ki=1 ni = n. So it all remains to show
that
Lemma 11: Matrices in No are orthogonal to those in Nd
with respect to the Hessian.
Proof: Divide any n-by-n skew symmetric matrix Ω
into k-by-k blocks as we did in equation (29). Define a skew
symmetric matrix Ω pq,i j by setting all blocks but B pq and
Bqp zeros while
1
B pq (= −BTqp ) = ~v pi~vTq j
2
then it is a straitforward computation that
N pq,i j = [H, Ω pq,i j ]

(34)

(35)

On the other side, if we define a skew symmetric matrix Ωs,t
by setting all blocks zeros but leaving Bss = Ω̃s,t , then

S

Ns,t = [H, Ωs,t ]

(36)

A computation shows that

H (N pq,i j , N p0 q0 ,i0 j0 )
= − 2(λ pi − λq j )(µ(Λ p ) − µ(Λq ))∆ pp0 ,qq0 ,ii0 , j j0

(31)

with ∆ pp0 ,qq0 ,ii0 , j j0 := δ pp0 δqq0 δii0 δ j j0 and δi j is the Kronecker
delta.
This is a straitforward computation following the formula
(25), more details can be found in [8]. The set No contains
as many as ∑1≤i< j≤k ni n j off-block-diagonal matrices.
2. Constructing Nd : still assume H = Diag(H1 , · · · , Hk )
with each Hi ∈ Sym(Λi ). Fix i, we let ~e ∈ Rni be a vector with
all entries ones and let ~e⊥ be the hyperplane perpendicular
to ~e. An identification is that the tangent space of the convex
hull C(Λ0 ) at any of its point is ~e⊥ .
Lemma 9: Let {~u1 , · · · ,~uni −1 } be an orthonormal basis
of ~e⊥ , then there exists a set of skew symmetric matrices
{Ω̃i,1 , · · · , Ω̃i,ni −1 } such that π([Hi , Ω̃i, j ]) = u j .
Proof: This follows fact 4 as the projection π is a
submersion.
Define a set of symmetric matrices Ni in the way that for
each matrix Ni, j ∈ Ni , all blocks except Bii are zeros while
Bii = [Hi , Ω̃i, j ]

(32)

for some j = 1, · · · , ni − 1, so there are exactly (ni − 1)
symmetric matrices in the set Ni .
Lemma 10: The set Nd := ki=1 Ni is contained in NH Eα .
If Ni, j ∈ Ni and Ni0 , j0 ∈ Ni0 , then H (Ni, j , Ni0 , j0 ) = δii0 δ j j0 .
S

This again follows the formula (25). The set Nd contains
as many as ∑ki=1 (ni − 1) block-diagonal matrices.

[π(H), Ωs,t ] = 0

(37)

π([H, Ω pq,i j ]) = 0

(38)

These two equalities annihilate the right hand side of formula
(25), so H (N pq,i j , Ns,t ) = 0.
Theorem 12: The Hessian H is nondegenerate when restricted at the normal space NH Eα for any H ∈ Eα and
any Eα . Moreover, H is invariant under conjugation of
permutation matrices, so the diagonal potential by equation
(12) is a Morse-Bott function.
Proof: The invariance is an consequence of lemma
5 and formula (25). The rest is an outcome by combining
lemma 8, lemma 10 and lemma 11.
We end this section with a discussion on the basis N .
For each symmetric matrix N ∈ NH Eα , there is a unique
matrix N 0 ∈ NH Eα such that H (N, ·) = tr(N 0 ·) because H
is nondegenerate. This induces a linear map LH on NH Eα by
sending N to N 0 . Each linear subspace spanned by N pq or Ni
is invariant under LH , moreover each matrix N pq,i j ∈ N pq
is an eigenmatrix of LH with respect to the eigenvalue
−(µ(Λ p ) − µ(Λq ))/(λ pi − λq j ). All eigenvalues from the
linear subspace spanned by Nd are positive by lemma 10. So
at this moment for each critical manifold, we have computed
its index and co-index.
VI. A PPLICATION OF ADJACENCY CRITERION ON THE
ISOSPECTRAL MANIFOLD WITH THE DIAGONAL
POTENTIAL

In this section, we will work out all stable critical manifolds and characterize all pairs of adjacent neighbors.

Lemma 13: A critical manifold is stable if and only if it
is a singleton consisting of a diagonal matrix.
Proof: Suppose M is a stable critical manifold, without
loss of generality, we assume M = Eα because the Hessian
is invariant under conjugation of permutation matrices, if
Eα is stable, then so is any critical manifold in its orbit.
Suppose α = (Λ1 , · · · , Λk ), then by lemma 10, each Λi is
a singleton, otherwise there exist at least ∑ki=1 (#(Λi ) − 1)
positive eigenvalues of LH . So M is necessarily a singleton
consisting of a diagonal matrix. On the other hand, if H is
a diagonal matrix, then it is a stable equilibrium because all
eigenvalues of LH are equal −(λ pi − λq j )/(λ pi − λq j )=-1 as
suggested by our discussion in the end of last section.
A diagonal matrix as an stable equilibrium is worth having
its own notation sσ , the subindex σ indicates the permutation
on the set of indices {1, · · · , n}, i.e, sσ = (λσ (1) , · · · , λσ (n) ).
We now characterize critical manifolds of co-index 1. Recall
that λ1 < · · · < λn , we say that two eigenvalues λi < λ j are
close in order if j = i + 1.
Lemma 14: Suppose α = (Λ1 , · · · , Λk ) and Eα is a critical
manifold is of co-index 1, then all but one Λ p are singletons,
and Λ p consists of two eigenvalues and they are closed in
order.
Proof: By lemma 10 and lemma 13, we first conclude
that there is exactly one Λ p among {Λ1 , · · · , Λk } such that it
is not a singleton and #(Λ p ) = 2. The matrix set N p is then
a singleton contains exactly one block-diagonal matrix N p .
At this moment, there is at least one positive eigenvalue
of LH with eigenmatrix N p because of lemma 10 and the
fact that spanN p is an invariant subspace. Suppose Λ p =
{λ p1 , λ p2 }, then to prevent from having extra positive eigenvalues of LH , two eigenvalues λ p1 and λ p2 are necessarily
closed in order because if not, suppose λq is in between λ p1
and λ p2 . We consider the two eigenvalues of LH contributed
by the two dimensional linear subspace spanned by N pq ,
these two eigenvalues are −(µ(Λ p ) − λq ))/(λ p1 − λq ) and
−(µ(Λ p ) − λq )/(λ p2 − λq ). By assumption one is negative
while the other is positive.
On the other hand, suppose λ p1 < λ p2 and they are
close in order, since λ p1 < µ(Λ p ) < λ p2 , it is clear that
−(µ(Λ p ) − λq ))/(λ pi − λq ) < 0 for any i = 1, 2 and any
λq ∈ Λ − {λi1 , λi2 }.
Each critical manifold of co-index 1 is a discrete set of
two elements. A typical set looks like


..
.




λi + λi+1
· · · ±(λi − λi+1 )


1

..
.
.
.
.

 (39)
.
.
.

2


±(λi − λi+1 ) · · ·
λi + λi+1


..
.
To relate with diagonal matrices, we let Sn be the group of
permutations on indices {1, · · · , n}, in convention a permutation is said to be a simple transposition if it is a 2-cycle

(i, i + 1). We say two permutations σ1 and σ2 are related by
a simple transposition σ̂ if σ1 · σ̂ = σ2 . Suppose
sσ1 = diag(· · · , λi , · · · , λi+1 , · · · )

(40)

sσ2 = diag(· · · , λi+1 , · · · , λi , · · · )

(41)

we then denote by Kσ1 ,σ2 the two matrices in equation (39).
The collection of equilibria of co-index 1 is then the union
of Kσ1 ,σ2 where (σ1 , σ2 ) varies over all pairs of permutations
that are related by a simple transposition.
A closed set Z ⊂ Sym(Λ) is invariant if for any H ∈ Z, the
solution ϕt (H) remains in Z for any t ∈ R. An observation
is that
Lemma 15: Let α = (Λ1 , · · · , Λk ) be a choice of partition.
We define
Zα := {Diag(H1 , · · · , Hk )|Hi ∈ Sym(Λi )}

(42)

then Zα is an invariant subset in Sym(Λ).
Proof: If H ∈ Zα and we write H = Diag(H1 , · · · , Hk ),
then the dynamical system is decoupled in the sense that
Ḣi = [Hi , [Hi , π(Hi )]], ∀i = 1, · · · , k

(43)

and Ḣ = Diag(Ḣ1 , · · · , Ḣk ).
Remark: Since the gradient flow f (H) commutes conjugation by permutation matrices, so PT Zα P is also an invariant
subset of Sym(Λ) for any permutation matrix P.
Theorem 16 (Adjacent neighbors of diagonal matrices):
All stable critical manifolds are singletons, and they are
diagonal matrices. Two diagonal matrices sσ1 and sσ2 are
adjacent if and only if σ1 and σ2 are related by a simple
transposition.
Proof: Fix the pair (σ1 , σ2 ), and assume k+ and k−
are the two matrices in Kσ1 ,σ2 . Let W u (k+ ) and W u (k− ) be
the unstable manifolds of k+ and k− respectively, we will
show that the boundary of either of unstable manifolds is
{sσ1 , sσ2 }, i.e,
∂W u (k+ ) = ∂W u (k− ) = sσ1 ∪ sσ2

(44)

But this is true by lemma 15 because if let Λ0 := {λ1 , λ2 }
and consider the double bracket flow on Sym(Λ0 ), then there
are exactly four isolated equilibria, two diagonal matrices as
stable equilibria and the other two are


1
λi + λi+1
±(λi − λi+1 )
0
(45)
k± =
λi + λi+1
2 ±(λi − λi+1 )
The isospectral manifold Sym(Λ0 ) is diffeomorphic to the
circle S1 , if we parametrize it by θ ∈ R, then the induced
dynamical system of θ on the covering space R is then
1
θ̇ = − (λi − λi+1 )2 sin(2θ )
2

(46)

It is clear that Zπ are stable equilibria and (Z + 12 )π are the
unstable ones, this is consistent with the earlier arguments.
0 )
Moreover this implies that the boundary of either W u (k+
0 ) is the union of diag(λ , λ
or W u (k−
i i+1 ) and diag(λi+1 , λi ).
This then completes the proof.

where c is a normalization factor of the density. (see, for example, [10] the derivation of the formula.) This implies that
the equiprobability surface of the stochastic flow coincides
with the equipotential surface of Ψ. If ε is small enough, then
the density function is highly peaked at diagonal matrices as
they are the local maxima. So a typical trajectory will spend
most of its time around stable equilibria, this suggests that
we approximate the behavior of the sample path by setting up
a Markov model whose states are the n! diagonal matrices,
and the trajectory of a sample path is simplified by a chain
T

Tk−1

T

2
1
· · · −−→ sσk
sσ2 −→
sσ1 −→

Fig. 3. Each vertex is the projection of a diagonal matrix and each edge is
the projection of an unstable manifold W u (Kσi ,σ j ). For convenience, we use
Cσi ,σ j to denote W u (Kσi ,σ j ) with emphasis that each W u (σi , σ j ) consists of
two disjoint curves with the same image under π.

There are as many as 21 (n − 1) · n! pairs of adjacent
neighbors. To better understand the geometry behind the
theorem, we consider the convex polytope C(Λ). Each vertex
of the polytope, known as a 0-dim face, corresponds to a
vector (λσ (1) , · · · , λσ (n) ). It is the image of a diagonal matrix
under the projection map π. Each edge of the polytope,
known as a 1-dim face, is then the image of an unstable
manifold W u (Kσ ,σ 0 ). Notice that each W u (Kσ ,σ 0 ) has two
disjoint curves, and both have the same image under π. It
is clear then each edge corresponds to a pair of adjacent
neighbors.
VII. A PPLICATION OF ADJACENCY THEOREM ON
STOCHASTIC GRADIENT FLOW

There is a stochastic version of the double bracket flow
by adding an isotropic noise into the equation
dH =[H, [H, π(H)]]dt + ε ∑[Ωi j , H]dωi j
+

ε2
[Ωi j , [Ωi j , H]]dt
2 ∑

(47)

The third term in the right hand side of equation above
appears as a consequence of the Itô rule so that the solution
still evolves on the isospectral manifold. In the literatures
of NMR, the last two terms relate to the Lindblad terms
modeling the heat bath. Each Ωi j is a skew symmetric matrix
defined by Ωi j =~ei~eTj −~e j~eTi where {~e1 , · · · ,~en } is a standard
basis in Rn . The significance of the stochastic effects is
modeled by the scalar ε.
It happens that there is an explicit formula for the steady
state solution of the Fokker-Planck equation associated with
our stochastic equation. It takes the form
ρ(H) = c exp(

2Ψ(H)
)
ε2

(48)

(49)

The rest of this section is to develop a method to evaluate
the transition probabilities.
There are two main challenging problems when coming
to the computation: the scale and the model. For each state,
there are as many as (n! − 1) transition probabilities we need
to evaluate, so in general the amount of computation is about
n!(n! − 1). To evaluate each transition probability, we need
to investigate a corresponding first hitting time model: we
ask for the probability P(T |sσi → sσ j ) of the event that the
passage time is than T for a sample path to reach state sσ j
from state sσi without visiting any other state. We now show
how adjacency theorem enters to simplify the problems
Reduce the computational complexity: Let Aσi be the set
of adjacent neighbors of sσi . Suppose sσ j ∈
/ Aσi , then we infer
that under the case ε  1
P(T |sσi → sσ j ) 

∑

P(T |sσi → sσ )

(50)

σ ∈Aσi

for any T > 0. This is reasonable because from geometric
perspective, if a sample path escapes from the region of
attraction W s (sσi ), there is a high percentage a path gets
trapped by one of its neighbors. So our first step of approximation is to set P(T |sσi → sσ j ) = 0 for any σ j ∈
/ Aσi . So
then for each state, the amount of computation is reduced to
(n − 1).
Approximate the transition probability: For each state sσi ,
the sample space of transition probability is discrete in space
Aσi but continuous in time. In general there is no exact
formula for computing P(T |sσi → sσ j ). One approach to
approximate the density function is to relate the first hitting
problem to an optimal control problem.
In quantum mechanics, it is known that the probability
for a system to stay in a quantum state of energy E is
proportional to exp(−E). This idea of Boltzmann sheds light
on our problem. We consider the control problem
Ḣ = [H, [H, π(H)]] + ε[H,U]

(51)

with U skew symmetric and the goal is to minimize the
energy, i.e,
1
E(T |σi → σ j ) := − min
U(t) 2

Z T

tr(U 2 (t))dt

(52)

0

under the assumption that H(0) = σi and H(T ) = σ j are
fixed. We then approximate P(T |σi → σ j ) by a scalar proportion of exp(−E(T |σi → σ j )).

R EFERENCES

Fig. 4. Illustrating the idea behind equation (50): a typical sample path
only connects adjacent neighbors while a nontypical sample path does not.

By solving the Euler-Lagrange equation, we conclude
that each optimal trajectory, or the energy minimizing
path(EMP) has to satisfy
Ḣ = [H, Ω]

(53)

Ω̇ = [H, [π(H), [H, π(H)]]] + [H, π([H, [H, π(H)]])]

(54)

It is hard to compute the MEP in general, however in the
case H(0) and H(T ) are both diagonal matrices, each MEP
coincides with a geodesic. In particular, there are two MEPs
and they together form the unstable manifold of Kσ1 ,σ2 . This
then simplifies the situation to a scalar problem: suppose the
simple transposition relating σi and σ j is the 2-cycle (λ1 , λ2 ),
then the control model is given by
1
θ̇ = − (λ1 − λ2 )2 sin(2θ ) + 2εu
2
and the goal is to minimize

(55)

RT 2
0 u dt.

Before we ending this section, we point out that locating
a MEP that connects two adjacent neighbors and computing
the minimal consumption of energy is more than an ad-hoc
plan for evaluating the transition probability. For example,
consider the situation that the control is intermittent and
impulse-like, and our goal is to steer the system from one
stable equilibrium to the other. Then questions such as in
what direction one can escape from a region of attraction
by means of an impulse? How we can save most of energy
and/or time to reach the target? These questions relate to
the design of a path that concatenates pairs of adjacent
neighbors, the analysis done in this section is then essential.
ACKNOWLEDGEMENTS
The author thanks Dr. Roger W. Brockett at Harvard
University for his comments on an earlier draft.

[1] R. W. Brockett. Dynamical systems that sort lists, diagonalize
matrices, and solve linear programming problems. Linear algebra
and its applications, 146:79–91, 1991.
[2] A. M. Bloch. Steepest descent, linear programming and hamiltonian
flows. Contemp. Math. AMS, 114:77–88, 1990.
[3] R. W. Brockett and W. S. Wong. A gradient flow for the assignment
problem. In New Trends in Systems Theory, pages 170–177. Springer,
1991.
[4] R. W. Brockett. Modeling the transient behavior of stochastic gradient
algorithms. In Decision and Control and European Control Conference
(CDC-ECC), 2011 50th IEEE Conference on, pages 4461–4466. IEEE,
2011.
[5] A. Banyaga and D. Hurtubise. Morse-bott homology. Transactions of
the American Mathematical Society, 362(8):3997–4043, 2010.
[6] A. Banyaga and D. Hurtubise. Lectures on Morse homology, volume 29. Springer Science & Business Media, 2013.
[7] J. Palis. On morse-smale dynamical systems. Topology, 8(4):385–404,
1969.
[8] X. Chen. Symmetric potential functions on the isospectral manifolds.
in preparation.
[9] A. Horn. Doubly stochastic matrices and the diagonal of a rotation
matrix. American Journal of Mathematics, 76(3):620–630, 1954.
[10] R. W. Brockett. Notes on stochastic processes on manifolds. In
Systems and Control in the Twenty-first Century, pages 75–100.
Springer, 1997.

