* Simitsis et al (2008) Simitsis A, Koutrika G, Ioannidis Y (2008) Précis: From unstructured keywords as queries to structured databases as answers. VLDB J 17(1):117–149
  * Song et al (2015) Song D, Schilder F, Smiley C, Brew C, Zielund T, Bretz H, Martin R, Dale C, Duprey J, Miller T, Harrison J (2015) TR Discover: A Natural Language Interface for Querying and Analyzing Interlinked Datasets. Semant Web-ISWC 2015 pp 21–37
  * Soru et al (2017) Soru T, Marx E, Moussallem D, Publio G, Valdestilhas A, Esteves D, Neto CB (2017) Sparql as a foreign language. 13th International Conference on Semantic Systems
  * Sutskever et al (2014) Sutskever I, Vinyals O, Le Q (2014) Sequence to sequence learning with neural networks. Advances in Neural Information Processing systems
  * Szalay et al (2002) Szalay AS, Gray J, Thakar AR, Kunszt PZ, Malik T, Raddick J, Stoughton C, vandenBerg J (2002) The sdss skyserver: public access to the sloan digital sky server data. SIGMOD 202
  * Tang and Mooney (2001) Tang L, Mooney R (2001) Using multiple clause constructors in inductive logic programming for semantic parsing. Mach Learn ECML 2001 (September):466–477
  * Thompson and Thompson (1983) Thompson B, Thompson F (1983) Introducing ASK, a simple knowledgeable system. Proc first Conf Appl Nat Lang Process pp 17–24
  * Walter et al (2012) Walter S, Unger C, Cimiano P, Bär D (2012) Evaluation of a layered approach to question answering over linked data. Semant Web–ISWC 2012 pp 362–374
  * Waltinger et al (2013) Waltinger U, Tecuci D, Olteanu M (2013) USI Answers: Natural Language Question Answering Over (Semi-) Structured Industry Data. Assoc Adv Artif Intell pp 1471–1478
  * Wang et al (2015) Wang Y, Berant J, Liang P (2015) Building a semantic parser overnight. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), vol 1, pp 1332–1342
  * Warren and Pereira (1982) Warren DH, Pereira FC (1982) An Efficient for Interpreting Easily Adaptable System Natural Language Queries. Am J Comput Linguist Vol 8, Number 3-4, July-December 1982
  * Weischedel (1989) Weischedel R (1989) A hybrid approach to representation in the JANUS natural language processor. In: Proc. 27th Annu. Meet. Assoc. Comput. Linguist., pp 193–202
  * Williams et al (2015) Williams JD, Kamal E, Ashour M, Amr H, Miller J, Zweig G (2015) Fast and easy language understanding for dialog systems with microsoft language understanding intelligent service (luis). In: Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue, pp 159–161
  * Woods (1973) Woods WA (1973) Progress in natural language understanding: an application to lunar geology. In: Proc. Natl. Comput. Conf. Expo. AFIPS ’73, pp 441–450
  * Xu et al (2014) Xu K, Feng Y, Zhao D (2014) Answering Natural Language Questions via Phrasal Semantic Parsing. Nat Lang Process Chinese Comput pp 333—-344
  * Xu et al (2017) Xu X, Liu C, Song D (2017) Sqlnet: Generating structured queries from natural language without reinforcement learning. arXiv preprint arXiv:171104436
  * Yavuz et al (2018) Yavuz S, Gur I, Su Y, Yan X (2018) What it takes to achieve 100% condition accuracy on wikisql. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp 1702–1711
  * Zenz et al (2009) Zenz G, Zhou X, Minack E, Siberski W, Nejdl W (2009) From keywords to semantic queries-Incremental query construction on the semantic web. J Web Semant 7(3):166–176
  * Zheng et al (2017) Zheng W, Cheng H, Zou L, Yu JX, Zhao K (2017) Natural Language Question/Answering: Let Users Talk With The Knowledge Graph. In: Proc. 2017 ACM Conf. Inf. Knowl. Manag., ACM, pp 217–226
  * Zhong et al (2017) Zhong V, Xiong C, Socher R (2017) Seq2sql: Generating structured queries from natural language using reinforcement learning. arXiv preprint arXiv:170900103

##  Appendix A SQL Representation

Q1:

⬇

SELECT DISTINCT p.*

FROM movie m, person p, directing d

WHERE m.id = d.movieId

AND person.id = d.directorId

AND m.title = ’Inglourious␣Basterds’

Q2:

⬇

SELECT * FROM movie m WHERE m.rating > 9

Q3:

⬇

SELECT DISTINCT m.*

FROM movie m, starring s, person p

WHERE m.id = s.movieId

AND s.actorId = p.id

AND p.name = ’Brad␣Pitt’

AND m.releaseDate >= ’2000-01-01’

AND m.releaseDate <= ’2010-12-31’

Q4:

⬇

SELECT DISTINCT m.*

FROM movie m, gross g

WHERE m.id = g.movieId

AND g.gross = (

SELECT MAX(gross) FROM gross

)

Q5:

⬇

SELECT DISTINCT m.*

FROM movie m, genre g

WHERE m.id = g.movieId

AND (

g.genre = ’drama’

OR g.genre = ’comedy’

)

Q6:

⬇

SELECT * FROM movie m WHERE m.rating >= 8

Q7:

⬇

SELECT DISTINCT m.*

FROM movie m, genre g, (

SELECT g.genre, max(m.rating) as maxRating

FROM movie m, genre g

WHERE m.id = g.moveId

GROUP BY g.genre

) as maxMovie

WHERE m.id = g.movieId

AND m.rating = maxMovie.maxRating

AND g.genre = maxMovie.genre

Q8:

⬇

SELECT DISTINCT m.*

FROM movie m, genre g

WHERE m.id = g.movieId

AND originalLang != ’jp’

AND g.genre = ’horror’

Q9:

⬇

SELECT *

FROM movie m1

WHERE m1.rating > (

SELECT m2.rating

FROM movie m2

WHERE m2.title = ’Sin␣City’

)

Q10:

⬇

SELECT DISTINCT m1.*

FROM genre g1, movie m1

WHERE m1.id = g1.movieId

AND NOT EXISTS (

SELECT ’’

FROM movie m2

WHERE m2.title = ’Sin␣City’

AND NOT EXISTS (

SELECT ’’

FROM genre g2

WHERE g2.movieId = m1.id

AND g2.id = g1.id

)

)


# Geometric Approaches to Matrix Normalization and Graph Balancing

Tom Needham  Clayton Shonkwiler

###### Abstract

Normal matrices, or matrices which commute with their adjoints, are of
fundamental importance in pure and applied mathematics. In this paper, we
study a natural functional on the space of square complex matrices whose
global minimizers are normal matrices. We show that this functional, which we
refer to as the non-normal energy, has incredibly well-behaved gradient
descent dynamics: despite it being non-convex, we show that the only critical
points of the non-normal energy are the normal matrices, and that its gradient
descent trajectories fix matrix spectra and preserve the subset of real
matrices. We also show that, even when restricted to the subset of unit
Frobenius norm matrices, the gradient flow of the non-normal energy retains
many of these useful properties. This is applied to prove that low-dimensional
homotopy groups of spaces of unit norm normal matrices vanish; for example, we
show that the space of $d\times d$ complex unit norm normal matrices is simply
connected for all $d\geq 2$. Finally, we consider the related problem of
balancing a weighted directed graph—that is, readjusting its edge weights so
that the weighted in-degree and out-degree is the same at each node. We adapt
the non-normal energy to define another natural functional whose global minima
are balanced graphs and show that gradient descent of this functional always
converges to a balanced graph, while preserving graph spectra and realness of
the weights. Our results were inspired by concepts from symplectic geometry
and Geometric Invariant Theory, but we mostly avoid invoking this machinery
and our proofs are generally self-contained.

##  1 Introduction

A matrix $A$ is called _normal_ if it commutes with its conjugate transpose:
$AA^{\ast}=A^{\ast}A$. The set of $d\times d$ complex normal matrices, which
we denote as $\mathcal{N}_{d}\subset\mathbb{C}^{d\times d}$, is a fundamental
object in linear algebra; for example, the Spectral Theorem characterizes
$\mathcal{N}_{d}$ as the set of unitarily diagonalizable matrices:

$\mathcal{N}_{d}=\\{UDU^{\ast}\mid
D\in\mathcal{D}_{d},\,U\in\operatorname{U}(d)\\},$

where $\mathcal{D}_{d}\subset\mathbb{C}^{d\times d}$ is the set of diagonal
matrices and $\operatorname{U}(d)$ is the group of unitary matrices. Moreover,
normal matrices are especially well-behaved from a numerical analysis
perspective. Indeed, the Bauer–Fike Theorem [5] implies that the eigenvalues
of a normal matrix are Lipschitz stable under perturbations, which motivates
the approximation of transfer matrices by normal matrices in classical control
theory [13, 14]. In the literature on dynamics on complex networks, it has
also been observed that directed networks whose weighted adjacency matrices
are not normal exhibit distinctive dynamical features which can confound
classical spectral methods [2, 41, 3]. Based on these considerations, the
_closest normal matrix problem_ —that is, the problem of finding a closest
point in $\mathcal{N}_{d}$ to an arbitrary matrix in $\mathbb{C}^{d\times
d}$—has been thoroughly studied [48, 19, 46, 22].

This paper studies $\mathcal{N}_{d}$ from a geometric perspective, with a view
toward optimization tasks such as the closest normal matrix problem. Our
results are largely derived from the simple observation that $\mathcal{N}_{d}$
is the set of global minima of the function

$\operatorname{E}:\mathbb{C}^{d\times d}\to\mathbb{R},\quad\mbox{defined
by}\quad\operatorname{E}(A)=\|AA^{\ast}-A^{\ast}A\|^{2},$ (1)

where $\|\cdot\|$ is the Frobenius norm. Despite the fact that the function
$\operatorname{E}$, which we refer to as the _non-normal energy_ , is not
quasiconvex (see Remark 2.5), it is surprisingly well-behaved from an
optimization perspective: we prove in Theorem 2.3 that the only critical
points of $\operatorname{E}$ are normal matrices, hence gradient descent along
$\operatorname{E}$ gives an approximate solution to the closest normal matrix
problem. We derive several related results, which are described in more detail
below in Section 1.1; in short, we show that gradient descent preserves
interesting features of the initializing matrix, such as its spectrum or the
realness of its entries. We also consider the restriction of non-normal energy
to the space of matrices with unit Frobenius norm and show that its gradient
flow is also quite well-behaved. This has immediate topological implications,
as we explain in more detail in Section 1.1.

The properties of the non-normal energy which we exploit in this paper are
predictable from a high-level perspective: $\operatorname{E}$ is the squared
norm of a momentum map associated to a Hamiltonian action of $\mathrm{SU}(d)$
on $\mathbb{C}^{d\times d}$ (see 2.2). This terminology comes from the field
of symplectic geometry, where the behavior of functions of this form is well-
understood [34, 37]. Our work in this paper is heavily inspired by Mumford’s
_Geometric Invariant Theory (GIT)_ [40] (see [50] for a nice introduction or
[39] for applications to similar matrix optimization problems) and Kirwan’s
work relating GIT and symplectic geometry [34]; there are also strong
connections to Ness’s paper [45]. One of our goals in writing this paper was
to make our arguments—especially the fundamentally elementary ones—as
accessible as possible, so we have mostly avoided explicitly invoking GIT in
what follows, but it was very much on our minds as we were working on this
paper. Connections to GIT and symplectic ideas are explained throughout.

As our results on $\mathcal{N}_{d}$ are rooted in powerful general theory, it
should not be surprising that our techniques are more broadly applicable.
Indeed, we also apply our geometric approach to the _graph balancing problem_
: given a weighted, directed graph $\mathcal{G}$, one wishes to determine a
new set of edge weights which balances the graph in the sense that the
weighted in-degree is the same as the weighted out-degree at each node. If the
latter condition is met, we say that the graph is _balanced_. An example of
our gradient flow-based approached to graph balancing, as is described below,
is shown in Figure 1. This problem is natural from an applications
perspective; for example, in the case that the underlying graph represents a
road network and that the weights are roadway capacities, that the graph is
balanced corresponds to the feasibility of traffic flow through all
intersections. As such, the graph balancing problem is well-studied in the
operations research literature [47, 30, 23].

Representing a graph $\mathcal{G}$ on $d$ nodes by a matrix
$A\in\mathbb{C}^{d\times d}$ containing the square roots of the entries of the
weighted adjacency matrix of $\mathcal{G}$, the balanced graphs are exactly
the global minima of the _unbalanced energy_ function,

$\operatorname{B}:\mathbb{C}^{d\times d}\to\mathbb{R},\quad\mbox{defined
by}\quad A\mapsto\|\operatorname{diag}(AA^{\ast}-A^{\ast}A)\|^{2},$ (2)

where $\operatorname{diag}$ is the linear map which zeros out all off-diagonal
entries. The unbalanced energy is similar in structure to the non-normal
energy—in fact, it is also the squared norm of a momentum map—and we derive
similar results regarding its gradient flow. We show in Theorem 4.1 that the
critical points of $\operatorname{B}$ are exactly the balanced matrices and
refine this result to show that gradient flow preserves geometric features of
the underlying graph. We describe these results more precisely in the
following subsection.

###  1.1 Main Contributions and Outline

We now summarize our main results in more detail.

  * •

Gradient flow of non-normal energy: Section 2 considers properties of the non-
normal energy (1), with a focus on properties of its gradient descent dynamics
in relation to normal matrices. Although the non-normal energy is not convex
(Remark 2.5), we show in Theorem 2.3 that the only critical points of
$\operatorname{E}$ are normal matrices; i.e., its global minima. It follows
easily that its gradient descent has a well-defined limiting normal matrix for
every choice of initial conditions; we additionally show in Theorem 2.6 that
the gradient descent trajectories of the non-normal entries preserve spectra
and realness of matrix entries. We derive estimates of the distance traveled
under gradient flow, which give new interpretations of concepts in the
literature on the closest normal matrix problem (Corollary 2.8 and 2.10).

  * •

Restriction to unit norm matrices and topological consequenes: In Section 3,
we consider the restriction of the non-normal energy to the space of matrices
with unit Frobenius norm. We prove in Theorem 3.1 that if gradient descent is
initialized at a non-nilpotent unit norm matrix, then it converges to a normal
matrix, and that if the initialization has real entries then so does its
limit. As an application, we show that the low-dimension homotopy groups of
the spaces of complex and real unit norm normal matrices vanish in Theorem 3.9
and Theorem 3.13, respectively. In particular, the space of $d\times d$ unit
norm complex normal matrices is connected for all $d$ and simply connected for
$d\geq 2$, whereas the space of unit norm real normal matrices is connected
for $d\geq 2$ and simply connected for $d\geq 3$.

  * •

Graph balancing via unbalanced energy: The unbalanced energy (2) and its
applications to graph balancing are studied in Section 4. Theorem 4.1 shows
that the only critical points of the unbalanced energy are its global minima;
that is, matrices representing balanced digraphs. Gradient descent converges
to a balanced digraph representation, and we show in Theorem 4.3 that it
preserves spectra and realness of entries. Moreover, this theorem shows that
if the entries of a real matrix are positive then this property is also
preserved, and that if an entry in the initial matrix is zero then it stays
zero along the gradient descent path—in terms of graphs, gradient descent does
not create any edges that were not present at initialization. We also consider
the restriction of the unbalanced energy to unit norm matrices (which
represent digraphs with a fixed total edge capacity) and derive similar useful
properties of its gradient flow in Theorem 4.5. Finally, we observe in Theorem
4.10 that the spaces of complex and real balanced unit norm matrices are
homotopy equivalent to spaces of real and complex normal matrices,
respectively.

Figure 1: Balancing a graph, starting at left with a random weighted, directed
multigraph with 6 vertices and 15 edges and ending with a balanced graph with
the same edges and vertices on the right. The thickness of each edge is
proportional to its weight.

##  2 Normal Matrices and Optimization

Recall from the introduction that the _non-normal energy_
$\operatorname{E}:\mathbb{C}^{d\times d}\to\mathbb{R}$ is the function

$\operatorname{E}(A)=\|AA^{\ast}-A^{\ast}A\|^{2}=\|[A,A^{\ast}]\|^{2}.$

Throughout this paper we use $[\cdot,\cdot]$ to denote the matrix commutator:
$[A,B]=AB-BA$.

The goal of this section is to derive properties of the gradient descent
dynamics of $\operatorname{E}$. In particular, we will show that we can
normalize any square matrix by sending it to its limit under the negative
gradient flow of $\operatorname{E}$.

###  2.1 Background

The map $\operatorname{E}$ has a long history in the problem of finding the
closest normal matrix to a given matrix, going back at least to Henrici [27],
who proved the following:

######  Proposition 2.1 (Henrici [27]).

For any $A\in\mathbb{C}^{d\times d}$,

$\inf_{M\in\mathcal{N}_{d}}\|A-M\|\leq\left(\frac{d^{3}-d}{12}\operatorname{E}(A)\right)^{1/4}.$

In other words, the distance from $A$ to $\mathcal{N}_{d}$ is bounded above by
a quantity proportional to $\operatorname{E}(A)^{1/4}$. One virtue of this
estimate is that $\operatorname{E}(A)$ is relatively easy to compute.

We now give an interpretation of $\operatorname{E}$ in terms of symplectic
geometry, where we consider $\mathbb{C}^{d\times d}\approx\mathbb{C}^{d^{2}}$
as a symplectic manifold with its standard symplectic structure. This
interpretation is not necessary for most of the paper, and is mainly included
for context. As such, we give a somewhat informal treatment and avoid explicit
definitions of any of the standard terminology from symplectic geometry. In
our previous papers, we give short and elementary overviews of the necessary
concepts from symplectic geometry, with a view toward understanding similar
spaces of structured matrices (e.g., spaces consisting of unit norm tight
frames); we refer the reader to [42, Section 2] and [43, Section 2.1] for more
in-depth exposition.

Consider the action of the unitary group $\operatorname{SU}(d)$ on
$\mathbb{C}^{d\times d}$ by conjugation. Let $\mathfrak{su}(d)$ denote the Lie
algebra of $\operatorname{SU}(d)$—that is, the traceless, skew-Hermitian
$d\times d$ matrices—and let $\mathfrak{su}(d)^{\ast}$ denote its dual. It
will be convenient to identify $\mathfrak{su}(d)^{\ast}$ with the space
$\mathscr{H}_{0}(d)$ of $d\times d$ traceless Hermitian matrices via the
isomorphism

$\displaystyle\mathscr{H}_{0}(d)$ $\displaystyle\to\mathfrak{su}(d)^{\ast}$
$\displaystyle Y$
$\displaystyle\mapsto\big{(}X\mapsto\frac{i}{2}\mathrm{Tr}(XY)\big{)}.$

Then we have the following interpretation of $\operatorname{E}$. Throughout
the paper, we use brackets to denote the matrix commutator,

$[A,B]\coloneq AB-BA.$

######  Proposition 2.2.

The conjugation action of $\operatorname{SU}(d)$ on $\mathbb{C}^{d\times d}$
is Hamiltonian, with momentum map

$\displaystyle\mu:\mathbb{C}^{d\times d}$
$\displaystyle\to\mathscr{H}_{0}(d)\approx\mathfrak{su}(d)^{\ast}$ (3)
$\displaystyle A$ $\displaystyle\mapsto[A,A^{\ast}].$ (4)

The non-normal energy $\operatorname{E}$ is therefore the squared norm of a
momentum map.

We omit the proof of 2.2, which is a straightforward calculation. In light of
this result, one should expect the non-normal energy to have nice
properties—see, e.g., work of Kirwan [34] and Lerman [37]. However, the
specific properties of $\operatorname{E}$ (and related functions) that we
derive below do not follow directly from the general theory.

###  2.2 Critical Points of Non-Normal Energy

Obviously, the global minima of the non-normal energy $\operatorname{E}$ are
exactly the normal matrices. In fact, we now show that these are the only
critical points. Throughout the paper, we use $\langle\cdot,\cdot\rangle$ to
denote the real part of the Frobenius inner product on $\mathbb{C}^{d\times
d}$,

$\langle A,B\rangle\coloneq\mathrm{Re}\operatorname{tr}(B^{\ast}A),$

and we use $D\mathrm{F}(A)$ to denote the derivative of a map
$\mathrm{F}:\mathbb{C}^{d\times d}\to\mathbb{R}$ at $A\in\mathbb{C}^{d\times
d}$.

######  Theorem 2.3.

The only critical points of $\operatorname{E}$ are the global minima; that is,
the normal matrices.

###### Proof.

We claim that

$\nabla\operatorname{E}(A)=-4[A,[A,A^{\ast}]].$ (5)

Indeed, since $\operatorname{E}$ is the square of a momentum map (2.2), this
follows by general principles of symplectic geometry—see, e.g., [34, Lemma
6.6] or [45, Lemma 6.1]. Let us additionally give an elementary derivation of
this fact. Writing $\operatorname{E}=N\circ\mu$, where $\mu$ is the momentum
map (3) and $N:\mathbb{C}^{d\times d}\to\mathbb{R}$ is the norm-squared map
$N(A)=\|A\|^{2}$, we have, for any $A,B\in\mathbb{C}^{d\times d}$,

$\langle\nabla\operatorname{E}(A),B\rangle=D\operatorname{E}(A)(B)=DN(\mu(A))\circ
D\mu(A)(B)=\langle\nabla N(\mu(A)),D\mu(A)(B)\rangle=\langle
D\mu(A)^{\vee}\nabla N(\mu(A)),B\rangle,$

where we use $D\mu(A)^{\vee}$ to denote the adjoint of $D\mu(A)$ with respect
to the inner product $\langle\cdot,\cdot\rangle$. It follows that

$\nabla\operatorname{E}(A)=D\mu(A)^{\vee}\nabla N(\mu(A)).$

A straightforward calculation then shows that the adjoint is given by the
formula

$D\mu(A)^{\vee}(C)=[C+C^{\ast},A].$ (6)

It is also easy to show that $\nabla N(C)=2C$, so we conclude that

$\nabla\operatorname{E}(A)=[2\mu(A)+2\mu(A)^{\ast},A]=-4[A,[A,A^{\ast}]].$

Therefore, we have a critical point of $\operatorname{E}$ exactly when

$0=[A,[A,A^{\ast}]];$

that is, when $A$ and $[A,A^{\ast}]$ commute. By Jacobson’s Lemma (stated
below as 2.4), this implies that $[A,A^{\ast}]$ is nilpotent. But
$[A,A^{\ast}]$ is Hermitian, so it is nilpotent if and only if it is the zero
matrix, which happens precisely when $A$ is normal.111The equivalence of $A$
being normal and $A$ commuting with $[A,A^{\ast}]$ appears as #73 in Elsner
and Ikramov’s list [16]; they attribute it to [38, 4.28.5]. ∎

######  Lemma 2.4 (Jacobson [31]; see also [33]).

If $A$ and $B$ are $d\times d$ matrices over a field of characteristic 0 and
$A$ commutes with $[A,B]$, then $[A,B]$ is nilpotent.

######  Remark 2.5.

Theorem 2.3 might lead one to suspect that $\operatorname{E}$ is convex, but
it is not. To see this, consider the normal matrices

$A_{0}=\begin{bmatrix}0&1\\\ -1&0\end{bmatrix}\qquad\mbox{and}\qquad
A_{1}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}.$

Since they are normal, $\operatorname{E}(A_{0})=0=\operatorname{E}(A_{1})$.
However,

$\operatorname{E}((1-t)A_{0}+tA_{1})=32t^{2}(1-t)^{2}>0$

for all $0<t<1$, so the interior of line segment connecting $A_{0}$ and
$A_{1}$ consists entirely of non-normal matrices, and hence $\operatorname{E}$
is not even quasiconvex, let alone convex. See Figure 2. Of course, we can pad
$A_{0}$ and $A_{1}$ by zeros to get an analogous example for any $d>2$.

Figure 2: The graph of $\operatorname{E}$ restricted to the collection of real
matrices of the form $\begin{bmatrix}0&x\\\ y&0\end{bmatrix}$.

On the other hand, Theorem 2.3 together with a theorem of Craven and Glover
[12] (see also [6]) shows that $\operatorname{E}$ is an invex function; this
class of functions was first defined by Hanson [24] and named by Craven [11].

###  2.3 Gradient Flow of Non-Normal Energy

Consider the negative gradient flow $\mathcal{F}:\mathbb{C}^{d\times
d}\times[0,\infty)\to\mathbb{C}^{d\times d}$ defined by

$\mathcal{F}(A_{0},0)=A_{0},\qquad\frac{d}{dt}\mathcal{F}(A_{0},t)=-\nabla\operatorname{E}(\mathcal{F}(A_{0},t)).$
(7)

Since $\operatorname{E}$ is a real polynomial function on the real vector
space $\mathbb{C}^{d\times d}$, the gradient flow cannot have limit cycles or
other bad behavior [53], so Theorem 2.3 implies that, for any
$A_{0}\in\mathbb{C}^{d\times d}$, the limit
$A_{\infty}\coloneq\lim_{t\to\infty}\mathcal{F}(A_{0},t)$ of the gradient flow
is well-defined and normal.

From (5), we see that

$\nabla\operatorname{E}(A)=-4[A,[A,A^{\ast}]]=-4(A[A,A^{\ast}]-[A,A^{\ast}]A)=4\left(\left.\frac{d}{d\epsilon}\right|_{\epsilon=0}e^{\epsilon[A,A^{\ast}]}Ae^{-\epsilon[A,A^{\ast}]}\right)=4\left(\left.\frac{d}{d\epsilon}\right|_{\epsilon=0}e^{\epsilon[A,A^{\ast}]}\cdot
A\right).$ (8)

Since $[A,A^{\ast}]$ is traceless,
$e^{\epsilon[A,A^{\ast}]}\in\operatorname{SL}_{d}(\mathbb{C})$ for any
$\epsilon$, so the negative gradient flow lines $\mathcal{F}(A_{0},t)$
produced by any $A_{0}$ stay within the conjugation orbit of $A_{0}$. In
particular, $A_{\infty}$ must have the same eigenvalues as $A_{0}$. Since real
matrices are invariant under gradient flow, we have thus proved:

######  Theorem 2.6.

For any $A_{0}\in\mathbb{C}^{d\times d}$, the matrix
$A_{\infty}=\displaystyle\lim_{t\to\infty}\mathcal{F}(A_{0},t)$ exists, is
normal, and has the same eigenvalues as $A_{0}$. Moreover, if $A_{0}$ is real,
then so is $A_{\infty}$.

If $A_{0}$ and $A_{\infty}$ are as in the theorem and
$\lambda_{1},\dots,\lambda_{d}$ are their common eigenvalues, then the
normality of $A_{\infty}$ implies that

$\|A_{\infty}\|^{2}=\sum_{i=1}^{d}|\lambda_{i}|^{2}.$

This immediately implies the following corollary.

######  Corollary 2.7.

If $A_{0}$ is non-nilpotent, then its gradient flow (7) is bounded away from
zero. On the other hand, if $A_{0}$ is nilpotent, then the limit of gradient
flow $A_{\infty}$ is the zero matrix.

A widely-used statistic for describing the extent to which a matrix is non-
normal is the _Henrici departure from normality_ [27]. For a matrix
$A\in\mathbb{C}^{d\times d}$ with eigenvalues $\lambda_{i}$, this is the
quantity222Note that some authors, including Henrici, define the departure
from normality to be the square root of this quantity.

$\mathrm{Hen}(A)=\|A\|^{2}-\sum_{i=1}^{d}|\lambda_{i}|^{2}.$

######  Corollary 2.8.

Let $A_{0}\in\mathbb{C}^{d\times d}$ and let $A_{\infty}$ be its limit under
the gradient flow (7). The change in scale along gradient flow is equal to
Henrici departure from normality,

$\|A_{0}\|^{2}-\|A_{\infty}\|^{2}=\mathrm{Hen}(A_{0}).$

###  2.4 Bound on the Distance to the Limit of Gradient Flow

We now show that $A_{\infty}$ is not too much further from $A_{0}$ than the
closest normal matrix, despite the fact that $A_{\infty}$ preserves features
(spectrum, realness) that the closest normal matrix may not. We do so by a
standard argument starting from a Łojasiewicz inequality.

Since $\operatorname{E}$ is the squared norm of a momentum map (2.2), a result
of Fisher [17] gives us the desired inequality:333Similar results appear in
Neeman [44, Theorem A.1], Woodward [52, Lemma B.0.6], and Lerman [37]; both
Woodward and Lerman credit Duistermaat with proving a version of this result
in unpublished work, as do Mumford, Fogarty, and Kirwan [40, p. 166, footnote
58].

######  Proposition 2.9 (Fisher [17, Theorem 4.7]).

There exist constants $\epsilon,c>0$ so that for all $A\in\mathbb{C}^{d\times
d}$ with $\operatorname{E}(A)<\epsilon$,

$\|\nabla\operatorname{E}(A)\|\geq c\operatorname{E}(A)^{3/4}.$

Now we follow a standard argument (see, e.g., Lerman [37]) to get bounds on
the distance from $A_{0}$ to $A_{\infty}$. Certainly this distance is no
larger than the length of the gradient flow path:

$\|A_{0}-A_{\infty}\|\leq\int_{0}^{\infty}\left\|\frac{d}{dt}\mathcal{F}(A_{0},t)\right\|dt=\int_{0}^{\infty}\|\nabla\operatorname{E}(\mathcal{F}(A_{0},t))\|dt.$
(9)

So long as $\operatorname{E}(\mathcal{F}(A_{0},t))<\epsilon$,

$-\frac{d}{dt}(\operatorname{E}(\mathcal{F}(A_{0},t)))^{1/4}=-\frac{1}{4}\operatorname{E}(\mathcal{F}(A_{0},t))^{-3/4}D\operatorname{E}(\mathcal{F}(A_{0},t)))(-\nabla\operatorname{E}(\mathcal{F}(A_{0},t)))\\\
=\frac{1}{4}\operatorname{E}(\mathcal{F}(A_{0},t))^{-3/4}\|\nabla\operatorname{E}(\mathcal{F}(A_{0},t))\|^{2}\geq\frac{c}{4}\|\nabla\operatorname{E}(\mathcal{F}(A_{0},t))\|,$

where the last inequality follows since 2.9 implies
$\operatorname{E}(\mathcal{F}(A_{0},t))^{-3/4}\|\nabla\operatorname{E}(\mathcal{F}(A_{0},t))\|\geq
c$.

Combining this with (9) yields:

$\|A_{0}-A_{\infty}\|\leq\int_{0}^{\infty}\|\nabla\operatorname{E}(\mathcal{F}(A_{0},t))\|dt\leq-\frac{4}{c}\int_{0}^{\infty}\frac{d}{dt}(\operatorname{E}(\mathcal{F}(A_{0},t)))^{1/4}dt=\frac{4}{c}\operatorname{E}(A_{0})^{1/4}.$

Therefore, we have proved:

######  Proposition 2.10.

There exist constants $\epsilon,c>0$ so that, if
$\operatorname{E}(A_{0})<\epsilon$, then

$\|A_{0}-A_{\infty}\|\leq\frac{4}{c}\operatorname{E}(A_{0})^{1/4}.$

Comparing to the Henrici estimate (2.1), we see that, at least when
$\operatorname{E}(A_{0})$ is small, the normal matrix $A_{\infty}$ we get by
doing gradient descent is not much further from $A_{0}$ than the closest
normal matrix is, even though $A_{\infty}$ has the same spectrum as $A_{0}$
and is real if $A_{0}$ is.

######  Remark 2.11.

The closest normal matrix to a given $A_{0}\in\mathbb{C}^{d\times d}$ can
computed explicitly by Ruhe’s algorithm [48], but the actual closest normal
matrix does not have the same spectrum as $A_{0}$ and may be complex even if
$A_{0}$ is real (see discussion in Chu [10] and Guglielmi and Scalone [22]).
This suggests that the gradient descent approach to finding a nearby normal
matrix may be useful in situations where one is interested in preserving
structural properties of the initialization. These observations are born out
by numerical experiments, and indeed $A_{\infty}$ gets relatively closer to
the closest normal matrix when $A_{0}$ is almost normal to begin with: see
Footnote 4.

Figure 3: Left: We generated 10,000 initial matrices
$A_{0}\in\mathbb{C}^{20\times 20}$ by letting the real and imaginary parts of
each entry be drawn from a standard Gaussian and then normalizing so that
$A_{0}$ has Frobenius norm 1. We computed the closest normal matrix
$\widehat{A}$ using Ruhe’s algorithm [48]444Note that, as Higham points out
[28], there is a missing minus sign before the determinant in the definition
of $\theta$ in step 2 of the published version of Ruhe’s Algorithm J.and
$A_{\infty}=\displaystyle\lim_{t\to\infty}\mathcal{F}(A_{0},t)$ using a very
simple gradient descent with fixed step sizes, and then plotted the point
$(\|\widehat{A}-A_{0}\|^{2},\|A_{\infty}-A_{0}\|^{2})$. The ratios
$\frac{\|A_{\infty}-A_{0}\|^{2}}{\|\widehat{A}-A_{0}\|^{2}}$ were all in the
interval $[1.028,1.161]$. Center: The same computations and visualization,
except the initial matrices $A_{0}$ were all $20\times 20$ real matrices. In
this case the $\frac{\|A_{\infty}-A_{0}\|^{2}}{\|\widehat{A}-A_{0}\|^{2}}$
were all in the interval $[1.023,1.196]$. Right: The same computations and
visualization, but with nearly normal initial matrices
$A_{0}\in\mathbb{C}^{20\times 20}$. More precisely, we generated
$B\in\mathbb{C}^{20\times 20}$ by normalizing a matrix of standard complex
Gaussians, found the closest normal matrix $\widehat{B}$, then added an
$\mathcal{N}(0,0.0075)$ random variate to the real and complex parts of each
entry of $\widehat{B}$, and let $A_{0}$ be the normalization of this matrix,
so that $A_{0}$ has Frobenius norm 1 and is already close to being normal. In
this case the $\frac{\|A_{\infty}-A_{0}\|^{2}}{\|\widehat{A}-A_{0}\|^{2}}$
were all in the interval $[1.009,1.036]$. In all three plots, the solid line
has slope 1 and the dashed line has slope $1.3$. Code for these experiments is
available on GitHub [49].

##  3 Unit Norm Normal Matrices

We have seen in Corollary 2.8 that the gradient flow of $\operatorname{E}$
does not preserve the Frobenius norm. If we want a flow that preserves the
norm, we should consider the restriction of $\operatorname{E}$ to the space
$\mathcal{U}_{d}$ of $d\times d$ matrices with Frobenius norm 1.
Geometrically, $\mathcal{U}_{d}$ is just the $(2d^{2}-1)$-dimensional unit
sphere in $\mathbb{C}^{d\times d}$.

Let $\overline{\operatorname{E}}:\mathcal{U}_{d}\to\mathbb{R}$ be the
restriction of $\operatorname{E}$ to $\mathcal{U}_{d}$ and let
$\overline{\mathcal{F}}:\mathcal{U}_{d}\times[0,\infty)\to\mathcal{U}_{d}$ be
the associated gradient flow; i.e.,

$\overline{\mathcal{F}}(A_{0},0)=A_{0}\qquad\frac{d}{dt}\overline{\mathcal{F}}(A_{0},t)=-\operatorname{grad}\overline{\operatorname{E}}(\overline{\mathcal{F}}(A_{0},t)),$

where $\operatorname{grad}$ is the Riemannian gradient on $\mathcal{U}_{d}$.

###  3.1 Gradient Flow of Restricted Non-Normal Energy

The normal matrices in $\mathcal{U}_{d}$ are exactly the global minima of
$\overline{\operatorname{E}}$; the goal is to show that almost every matrix in
$\mathcal{U}_{d}$ flows to a normal matrix under the gradient flow:

######  Theorem 3.1.

For any non-nilpotent $A_{0}\in\mathcal{U}_{d}$, the matrix
$A_{\infty}\coloneq\displaystyle\lim_{t\to\infty}\overline{\mathcal{F}}(A_{0},t)$
exists, is normal, and has Frobenius norm 1. Moreover, if $A_{0}$ is real,
then so is $A_{\infty}$.

######  Remark 3.2.

In GIT terms, we are looking at (a linearization of) the projective adjoint
action of $\operatorname{SL}(d)$ on $\mathbb{P}(\mathfrak{sl}(d)^{\ast})$, and
the fact that we have to assume $A_{0}$ is non-nilpotent in Theorem 3.1 is
equivalent to the fact that the non-nilpotent matrices are exactly the semi-
stable points with respect to this action [35] (see [40, Proposition 4.4]).

Since $\overline{\operatorname{E}}$ is a polynomial function defined on a
real-analytic submanifold of Euclidean space, it will have a Łojasiewicz
exponent (cf. [7, Corollary 4.2]), and hence the gradient flow will have a
single limit point [53], proving the existence of $A_{\infty}$.

Since the non-nilpotent matrices form an open, dense subset of
$\mathcal{U}_{d}$, Theorem 3.1 implies that almost every member of any
neighborhood of a non-minimizing critical point will flow to a normal matrix;
that is, a global minimum of $\overline{\operatorname{E}}$. Hence, the non-
minimizing critical points of $\overline{\operatorname{E}}$ cannot be basins
of attraction. Since $\overline{\operatorname{E}}$ has a Łojasiewicz exponent,
an argument analogous to [1, Theorem 3] shows that all local minima must be
basins of attraction. Hence we have the following corollary.

######  Corollary 3.3.

Every local minimum of $\overline{\operatorname{E}}$ must be a global minimum;
that is, a normal matrix.

We have already shown that the gradient flow of $\overline{\operatorname{E}}$
converges to a single limit point $A_{\infty}$. The remainder of this
subsection will be devoted to proving the remaining statements of Theorem 3.1
through several supporting results. The strategy for proving the rest of the
first sentence of Theorem 3.1 is to show that the gradient flow preserves non-
nilpotency, and that all non-minimizing critical points must be nilpotent. As
with Theorem 2.6, the last sentence will follow because the real submanifold
of $\mathcal{U}_{d}$ is invariant under the gradient flow.

######  Proposition 3.4.

The intrinsic gradient of $\overline{\operatorname{E}}$ on $\mathcal{U}_{d}$
is

$\operatorname{grad}\overline{\operatorname{E}}(A)=-4([A,[A,A^{\ast}]]+\overline{\operatorname{E}}(A)A).$

###### Proof.

Geometrically, $\operatorname{grad}\overline{\operatorname{E}}(A)$ is the
projection of $\nabla\operatorname{E}(A)$ onto the tangent space
$T_{A}\mathcal{U}_{d}=\mathrm{span}(\\{A\\})^{\bot}$:

$\operatorname{grad}\overline{\operatorname{E}}(A)=\nabla\operatorname{E}(A)-\langle\nabla\operatorname{E}(A),A\rangle
A.$

We know from (5) that $\nabla\operatorname{E}(A)=-4[A,[A,A^{\ast}]]$, so the
fact that $[A,A^{\ast}]$ is Hermitian implies

$\langle\nabla\operatorname{E}(A),A\rangle=-4\mathrm{Re}\operatorname{tr}([A,[A,A^{\ast}]]^{\ast}A)=-4\mathrm{Re}\operatorname{tr}([A,A^{\ast}]A^{\ast}A-A^{\ast}[A,A^{\ast}]A)\\\
=4\mathrm{Re}\operatorname{tr}([A,A^{\ast}][A,A^{\ast}])=4\|[A,A^{\ast}]\|^{2}=4\overline{\operatorname{E}}(A)$
(10)

by the linearity and cyclic invariance of trace, and the result follows. ∎

Since $[A,A^{\ast}]$ is traceless, notice that

$\operatorname{grad}\overline{\operatorname{E}}(A)=4\left.\frac{d}{dt}\right|_{t=0}e^{-t\overline{\operatorname{E}}(A)}e^{t[A,A^{\ast}]}Ae^{-t[A,A^{\ast}]}=4\left.\frac{d}{dt}\right|_{t=0}(e^{t[A,A^{\ast}]},e^{-t\overline{\operatorname{E}}(A)})\cdot
A$

is tangent to the
$\operatorname{SL}_{d}(\mathbb{C})\times\mathbb{C}^{\times}$-orbit of $A$,
where the action of
$\operatorname{SL}_{d}(\mathbb{C})\times\mathbb{C}^{\times}$ on
$\mathbb{C}^{d\times d}$ is defined by $(g,z)\cdot A\coloneq zgAg^{-1}$.

We could use this to show that the negative gradient flow preserves non-
nilpotency, but extending to the limit poses challenges, so we adopt a
different approach. For $A\in\mathbb{C}^{d\times d}$, define

$s(A)\coloneq\sum_{i=1}^{d}|\lambda_{i}|^{2},$

where $\lambda_{1},\dots,\lambda_{d}$ are the eigenvalues of $A$. The
nilpotent matrices are precisely the vanishing locus of $s$.

######  Lemma 3.5.

For any $A\in\mathcal{U}_{d}$,

$\langle-\operatorname{grad}\overline{\operatorname{E}}(A),\operatorname{grad}s(A)\rangle=8s(A)\overline{\operatorname{E}}(A),$

where $\operatorname{grad}s(A)$ is the intrinsic gradient of $s$ in
$\mathcal{U}_{d}$.

###### Proof.

Note, first of all, that $\langle A,\operatorname{grad}s(A)\rangle=0$, since
$\operatorname{grad}s(A)\in
T_{A}\mathcal{U}_{d}=\mathrm{span}(\\{A\\})^{\bot}$. Therefore,

$\displaystyle\langle-\operatorname{grad}\overline{\operatorname{E}}(A),\operatorname{grad}s(A)\rangle$
$\displaystyle=\langle-\nabla\operatorname{E}(A)+4\overline{\operatorname{E}}(A)A,\operatorname{grad}s(A)\rangle$
$\displaystyle=\langle-\nabla\operatorname{E}(A),\operatorname{grad}s(A)\rangle$
$\displaystyle=\langle-\nabla\operatorname{E}(A),\nabla s(A)-\langle\nabla
s(A),A\rangle A\rangle$
$\displaystyle=-\langle\nabla\operatorname{E}(A),\nabla
s(A)\rangle+\langle\nabla
s(A),A\rangle\langle\nabla\operatorname{E}(A),A\rangle$
$\displaystyle=-\langle\nabla\operatorname{E}(A),\nabla
s(A)\rangle+4\langle\nabla s(A),A\rangle\overline{\operatorname{E}}(A),$

using (10) in the first and last equalities.

We know from (8) and the following sentence that $\nabla\operatorname{E}(A)$
lies in the conjugation orbit of $A$. But this means that
$\nabla\operatorname{E}(A)$ must be tangent to the level set of $s$ passing
through $A$, since conjugation preserves eigenvalues, and hence fixes $s$.
Therefore, $\langle\nabla\operatorname{E}(A),\nabla s(A)\rangle=0$ and we have
shown that

$\langle-\operatorname{grad}\overline{\operatorname{E}}(A),\operatorname{grad}s(A)\rangle=4\langle\nabla
s(A),A\rangle\overline{\operatorname{E}}(A).$

By definition of the gradient, the inner product is a directional derivative,

$\langle\nabla s(A),A\rangle=Ds(A)(A)=\lim_{t\to
0}\frac{s(A+tA)-s(A)}{t}=\lim_{t\to 0}\frac{(1+t)^{2}s(A)-s(A)}{t}=2s(A),$

completing the proof. ∎

######  Proposition 3.6.

If $A_{0}\in\mathcal{U}_{d}$ is non-nilpotent, then so is
$A_{t}\coloneq\overline{\mathcal{F}}(A_{0},t)$ for all $t\in[0,\infty)$ and so
is
$A_{\infty}\coloneq\displaystyle\lim_{t\to\infty}\overline{\mathcal{F}}(A_{0},t)$.

###### Proof.

For any $A\in\mathcal{U}_{d}$, 3.5 implies that

$\langle-\operatorname{grad}\overline{\operatorname{E}}(A),\operatorname{grad}s(A)\rangle=8s(A)\overline{\operatorname{E}}(A)\geq
0.$

Therefore, $s(A)$ must be non-decreasing along the negative gradient flow
lines of $\overline{\operatorname{E}}$, so $s(A_{t})\geq s(A_{0})>0$ for all
$t\in[0,\infty)$, and in the limit we also have $s(A_{\infty})\geq
s(A_{0})>0$. Hence, $A_{t}$ and $A_{\infty}$ must be non-nilpotent. ∎

In other words, gradient flow preserves non-nilpotency, including in the
limit, so we have completed the first step in our strategy for proving Theorem
3.1. We now proceed with the second step.

######  Proposition 3.7.

All non-minimizing critical points of $\overline{\operatorname{E}}$ are
nilpotent.

###### Proof.

By 3.4, $A$ is a critical point of $\overline{\operatorname{E}}$ if and only
if

$0=[A,[A,A^{\ast}]]+\overline{\operatorname{E}}(A)A.$

If $A$ is a non-minimizing critical point, then $A$ is not normal, so
$\overline{\operatorname{E}}(A)\neq 0$ and

$A=-\frac{1}{\overline{\operatorname{E}}(A)}[A,[A,A^{\ast}]].$

In other words, $A=[A,B]$ with
$B=-\frac{1}{\overline{\operatorname{E}}(A)}[A,A^{\ast}]$. But then $A$
certainly commutes with $[A,B]$, so Jacobson’s Lemma (2.4) implies that
$[A,B]$ is nilpotent. Since $A=[A,B]$, we conclude that $A$ is nilpotent. ∎

###### Proof of Theorem 3.1.

If $A_{0}\in\mathcal{U}_{d}$ is not nilpotent, then the limit
$A_{\infty}=\displaystyle\lim_{t\to\infty}\overline{\mathcal{F}}(A_{0},t)$
exists and, by 3.6, is not nilpotent. $A_{\infty}$ must be a critical point of
$\overline{\operatorname{E}}$ and, by 3.7, must be a global minimum, and hence
normal. ∎

It is possible to prove an analogous statement to 2.10 in this setting as
well, so gradient descent of $\overline{\operatorname{E}}$, even though it
preserves norms and (when applicable) realness, produces a limiting normal
matrix $A_{\infty}$ which is not much further from $A_{0}$ than the closest
normal matrix. Again, this conclusion is supported by numerical experiments:
see Figure 4

Figure 4: This is the same experimental setup as in Footnote 4, except that
now
$A_{\infty}=\displaystyle\lim_{t\to\infty}\overline{\mathcal{F}}(A_{0},t)$.
Left: $A_{0}\in\mathbb{C}^{20\times 20}$; all
$\frac{\|A_{\infty}-A_{0}\|^{2}}{\|\widehat{A}-A_{0}\|^{2}}\in[1.060,1.198]$.
Center: $A_{0}\in\mathbb{R}^{20\times 20}$; all
$\frac{\|A_{\infty}-A_{0}\|^{2}}{\|\widehat{A}-A_{0}\|^{2}}\in[1.046,1.253]$.
Right: $A_{0}\in\mathbb{C}^{20\times 20}$ is a small perturbation of a normal
matrix; all
$\frac{\|A_{\infty}-A_{0}\|^{2}}{\|\widehat{A}-A_{0}\|^{2}}\in[1.010,1.031]$.
In all three plots, the solid line has slope 1 and the dashed line has slope
$1.3$. Code for these experiments is available on GitHub [49].

###  3.2 Topology of Unit Norm Normal Matrices

The space of normal matrices $\mathcal{N}_{d}$ is a cone in
$\mathbb{C}^{d\times d}$ and hence topologically trivial. However, the space
$\mathcal{U}\mathcal{N}_{d}$ can potentially have interesting topology.
Friedland [18] argues that $\mathcal{U}\mathcal{N}_{d}$ is irreducible and the
quasi-variety of its smooth points is connected. However, this is not quite
enough to imply that $\mathcal{U}\mathcal{N}_{d}$ is connected, since
irreducible real varieties can have connected components consisting entirely
of non-smooth points (see, e.g., [9, Figure 2]). In this subsection, we show
that $\mathcal{U}\mathcal{N}_{d}$ is connected and, in fact, that many of its
low-dimensional homotopy groups vanish.

The key fact that we use when studying the topology of
$\mathcal{U}\mathcal{N}_{d}$ is that it is closely related to the topology of
the space of all non-nilpotent matrices in $\mathbb{C}^{d\times d}$. For the
rest of this subsection, we use $\mathcal{P}_{d}$ to denote the space of
nilpotent matrices in $\mathbb{C}^{d\times d}$ and we let
$\mathcal{M}_{d}=\mathbb{C}^{d\times d}\setminus\mathcal{P}_{d}$. The
relationship between the topologies of $\mathcal{U}\mathcal{N}_{d}$ and
$\mathcal{M}_{d}$ is made precise by the following result.

######  Corollary 3.8.

The space $\mathcal{U}\mathcal{N}_{d}$ is a strong deformation retract of
$\mathcal{M}_{d}$.

###### Proof.

As the function $\mu:A\mapsto\|[A,A^{\ast}]\|^{2}$ is the norm squared of a
momentum map (2.2), with set of critical points exactly equal to
$\mathcal{N}_{d}$ (Theorem 2.3), it follows by a more general result of
Duistermaat (see the expository work of Lerman [37]) that gradient descent
gives a strong deformation retract of $\mathbb{C}^{d\times d}$ onto
$\mathcal{N}_{d}$. One can also deduce this from the work above: by Theorem
2.6, we have a well-defined function $\mathcal{F}:\mathbb{C}^{d\times
d}\times[0,\infty]\to\mathcal{N}_{d}$ induced by gradient descent, which
obviously fixes $\mathcal{N}_{d}$, and the arguments in [37] show that the map
is continous. Moreover, this restricts to a strong deformation retract
$\mathcal{M}_{d}\times[0,\infty]\to\mathcal{N}_{d}\setminus\\{0\\}$, by
Corollary 2.7. As $\mathcal{N}_{d}\setminus\\{0\\}$ is a cone over
$\mathcal{U}\mathcal{N}_{d}$, the former also strong deformation retracts onto
the latter. Concatenating these two strong deformation retracts gives a strong
deformation retract $\mathcal{M}_{d}\to\mathcal{U}\mathcal{N}_{d}$. ∎

In particular, $\mathcal{U}\mathcal{N}_{d}$ is homotopy equivalent to
$\mathcal{M}_{d}$, so our goal of characterizing the topology of the former
space reduces to understanding that of the latter space. From such an
understanding, we will deduce the main theorem of this subsection, stated
below. In the following, we use $\pi_{k}(\mathcal{X},x_{0})$ to denote the
$k$th homotopy group of a space $\mathcal{X}$ with respect to a basepoint
$x_{0}\in\mathcal{X}$, and write $\pi_{k}(\mathcal{X})$ in the case that
$\mathcal{X}$ is path connected (in which case the result is independent of
basepoint, up to isomorphism)—we refer the reader to [25, Chapter 4] for basic
terminology and properties. We say that $\mathcal{X}$ is $k$-connected if
$\pi_{k}(\mathcal{X},x_{0})$ is the trivial group.

######  Theorem 3.9.

The space $\mathcal{U}\mathcal{N}_{d}$ is $k$-connected for all $k\leq 2d-2$.

######  Remark 3.10.

In particular, $\mathcal{U}\mathcal{N}_{d}$ is connected for all $d$.
Moreover, $\mathcal{U}\mathcal{N}_{d}$ is simply connected (i.e.
$\pi_{1}(\mathcal{U}\mathcal{N}_{d})$ is also trivial) for all $d\geq 2$.

The proof will use two auxiliary topological results. The first follows from
more general results on _nilpotent cones_ , which are classical. We use [32]
as a general reference and explain how to deduce this particular result from
the general results therein.

######  Lemma 3.11.

The space $\mathcal{P}_{d}$ of nilpotent matrices in $\mathbb{C}^{d\times d}$
is an irreducible variety of complex dimension $d(d-1)$.

###### Proof.

We apply the general nilpotent cone theory to the Lie group of invertible
matrices $\mathrm{GL}_{d}(\mathbb{C})$, in which case the nilpotent cone is
exactly $\mathcal{P}_{d}$. Then the fact that $\mathcal{P}_{d}$ is an
irreducible variety is [32, Lemma 6.2]. By [32, Theorem 6.4], the dimension of
$\mathcal{P}_{d}$ is twice the dimension of the maximal unipotent subalgebra
of the Lie algebra $\mathbb{C}^{d\times d}$, namely the subalgebra of strictly
upper triangular matrices (i.e., with zeros on the diagonal). This subalgebra
has complex dimension $1+2+\cdots+(d-1)=\frac{1}{2}d(d-1)$. ∎

The following is a standard application of transversality (see [36, Chapter 6]
and [29, Chapter 3]). Special cases of the result appear in, e.g., [20,
Theorem 2.3] and [15, Theorem 1.1.4]. We give a proof sketch here for the sake
of convenience.

######  Lemma 3.12.

Let $\mathcal{X}$ be a connected smooth manifold and let
$\mathcal{Y}\subset\mathcal{X}$ be a union of smooth submanifolds,
$\mathcal{Y}=\mathcal{Y}_{1}\cup\cdots\cup\mathcal{Y}_{\ell}$, such that each
$\mathcal{Y}_{j}$ has codimension greater than or equal to $m$ in
$\mathcal{X}$. Then $\pi_{k}(\mathcal{X}\setminus\mathcal{Y})$ is isomorphic
to $\pi_{k}(\mathcal{X})$ for all $k\leq m-2$.

###### Proof.

We will show that the inclusion map
$\iota:\mathcal{X}\setminus\mathcal{Y}\hookrightarrow\mathcal{X}$ induces a
bijection between homotopy groups.

To establish surjectivity, we will show that any map $f:S^{k}\to\mathcal{X}$
is homotopic to a map $S^{k}\to\mathcal{X}\setminus\mathcal{Y}$. To do so, we
apply the Whitney Approximation Theorem [36, Theorem 6.26] to homotope $f$ to
a smooth map. By the version of the corollary of the Transversality Theorem
given in [29, Theorem 2.5], together with the argument in the proof of the
Transversality Homotopy Theorem [36, Theorem 6.36], the resulting map is then
homotopic to a map $S^{k}\to\mathcal{X}$ which is transverse to each
submanifold $\mathcal{Y}_{j}$. By the codimensionality constraint, this is
only possible if the image of $S^{k}$ is disjoint from each $\mathcal{Y}_{j}$.
This shows that $f$ is homotopic to a map whose image is disjoint from
$\mathcal{Y}$.

Next, we show that the map induced by $\iota$ is injective. That is, if maps
$f_{0},f_{1}:S^{k}\to\mathcal{X}$ are homotopic, and, without loss of
generality (by the above),
$f_{0}(S^{k})\cap\mathcal{Y}=f_{1}(S^{k})\cap\mathcal{Y}=\emptyset$, then they
are homotopic in $\mathcal{X}\setminus\mathcal{Y}$. This is done by applying
similar arguments to the above to the homotopy
$f:S^{k}\times[0,1]\to\mathcal{X}$; in particular, this map may be homotoped
without destroying transversality at the boundary $S^{k}\times\\{0,1\\}$ [29,
Ch. 3, Theorem 2.1]. ∎

###### Proof of Theorem 3.9.

By Corollary 3.8, it suffices to show that $\mathcal{M}_{d}$ is $k$-connected
for all $2d-2$. By a theorem of Whitney, the algebraic variety
$\mathcal{P}_{d}$ can be expressed as a disjoint union of smooth manifolds
[51, Theorem 2], and, by 3.11, each of these has real codimension at least

$\mathrm{dim}(\mathbb{C}^{d\times
d})-\mathrm{dim}(\mathcal{P}_{d})=2d^{2}-2d(d-1)=2d.$

The theorem then follows from 3.12, since $\mathbb{C}^{d\times d}$ is
$k$-connected for all $k$. ∎

###  3.3 Topology of Real Unit Norm Normal Matrices

Let $\mathcal{U}\mathcal{N}_{d}^{\mathbb{R}}$ denote the space of real, normal
$d\times d$ matrices with Frobenius norm equal to one (so
$\mathcal{UN}_{d}^{\mathbb{R}}\subset\mathcal{U}\mathcal{N}_{d}$). Adapting
the arguments from the previous subsection, we will show the following.

######  Theorem 3.13.

The space $\mathcal{UN}_{d}^{\mathbb{R}}$ is $k$-connected for all $k\leq
d-2$.

Figure 5: Consider the space $\mathcal{U}_{2}^{\mathbb{R}}$ of $2\times 2$
real matrices with Frobenius norm 1. Since $\mathcal{U}_{2}^{\mathbb{R}}$ is a
copy of the 3-sphere, we can stereographically project to $\mathbb{R}^{3}$.
The image under this projection of the unit-norm nilpotent matrices is shown
in blue, and the image of $\mathcal{UN}_{2}^{\mathbb{R}}$ is shown in pink.
Specifically, the pink plane (which is the $y=z$ plane) is the image of the
symmetric matrices and the pink loop is the image of the normal matrices of
the form $\begin{bmatrix}a&b\\\ -b&a\end{bmatrix}$.

######  Remark 3.14.

It follows from the theorem that $\mathcal{UN}_{d}^{\mathbb{R}}$ is path
connected for $d\geq 2$ and simply connected for $d\geq 3$. These results are
tight:

  * •

$\mathcal{UN}_{1}^{\mathbb{R}}\approx\\{\pm 1\\}$ is not path connected.

  * •

$\mathcal{UN}_{2}^{\mathbb{R}}$ is not simply connected. This is illustrated
in Figure 5.

The proof of the theorem follows the same general steps as that of Theorem
3.9. Let $\mathcal{P}_{d}^{\mathbb{R}}$ denote the $d\times d$ real nilpotent
matrices, and let $\mathcal{M}_{d}^{\mathbb{R}}=\mathbb{R}^{d\times
d}\setminus\mathcal{P}_{d}^{\mathbb{R}}$ denote the set of non-nilpotent
matrices. By the same arguments used in the previous subsection,
$\mathcal{M}_{d}^{\mathbb{R}}$ deformation retracts onto
$\mathcal{UN}_{d}^{\mathbb{R}}$, so it suffices to prove that
$\mathcal{M}_{d}^{\mathbb{R}}$ is $k$-connected for all $k\leq d-2$.

The main difference in the real case is that an analogue of 3.11 does not
follow from general facts of nilpotent cones described in [32], as the results
therein are valid over algebraically closed fields. We obtain a decomposition
of $\mathcal{P}_{d}^{\mathbb{R}}$ in analogy with the Whitney decomposition
used in the proof of Theorem 3.9 from results of [26] and [8].

######  Lemma 3.15.

The set of nilpotent matrices $\mathcal{P}_{d}^{\mathbb{R}}$ is a union of
smooth submanifolds of $\mathbb{R}^{d\times d}$, each of which has codimension
at least $d$.

###### Proof.

It follows from a general theory of real reductive Lie group actions developed
in [26] that $\mathbb{R}^{d\times d}\setminus\\{0\\}$ decomposes as a union of
$\mathrm{GL}_{d}(\mathbb{R})$-invariant (with respect to the conjugation
action) smooth submanifolds $S_{0}\cup S_{1}\cup\cdots\cup S_{k}$, where
$S_{0}$ is exactly the open submanifold $\mathcal{M}_{d}^{\mathbb{R}}$—see
also [8, Section 1] for a short exposition of these ideas. It is shown in [8,
Section 1.2] that (for the specific example of the conjugation action on
$\mathbb{R}^{d\times d}$) the remaining submanifolds $S_{i}$, $i>0$, are
parameterized by Jordan canonical forms of nilpotent matrices. That is, fixing
such a Jordan matrix $J$, we consider the corresponding set of nilpotent
matrices as the homogeneous space
$\mathrm{GL}_{d}(\mathbb{R})/\mathrm{stab}(J)$, where $\mathrm{stab}(J)$ is
the stabilizer of $J$ under the conjugation action. To complete the proof, it
suffices to show that the dimension of such a homogeneous space is at most
$d^{2}-d$, i.e., to show that the stabilizer of any such Jordan matrix is at
least dimension-$d$.

Let us now establish the claim made above. A nilpotent Jordan matrix $J$
necessarily has all zeros on its diagonal, and is therefore characterized by
the pattern of ones in the super diagonal (i.e., by the size of its Jordan
blocks). An invertible real matrix $A=(a_{ij})_{i,j=1}^{d}$ lies in the
stabilizer of $J$ if and only if $AJ=JA$. This matrix equation gives several
constraints in the entries of $A$, and the number of independent constraints
determines the dimension of the stabilizer.

In particular, since we aim to determine a lower bound on codimension, it
suffices to consider the Jordan matrix which produces the largest number of
constraints: that is, when $J$ is the matrix whose superdiagonal consists of
all ones (i.e., it has a single Jordan block). It is a standard fact (see,
e.g., [21, Theorem 9.1.1]) that, for this $J$, solutions of the equation
$AJ=JA$ must be upper triangular Toeplitz matrices. In other words, elements
of $\mathrm{stab}(J)$ are of the form

$\begin{bmatrix}a_{1}&a_{2}&a_{3}&\cdots&a_{d-1}&a_{d}\\\
0&a_{1}&a_{2}&\cdots&a_{d-2}&a_{d-1}\\\ 0&0&a_{1}&\cdots&a_{d-3}&a_{d-2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&\cdots&a_{1}&a_{2}\\\
0&0&0&\cdots&0&a_{1}\end{bmatrix}.$

Clearly, then, $\dim(\mathrm{stab}(J))=d$. This implies that the codimension
of the associated submanifold is $d$. Since this is the submanifold of
smallest codimension, this completes the proof. ∎

###### Proof of Theorem 3.13.

By the discussion above, it suffices to prove that
$\mathcal{M}_{d}^{\mathbb{R}}$ is $k$-connected for all $k\leq d-2$. In light
of 3.15, the same transversality argument as was used in the proof of Theorem
3.9 can be used here. ∎

##  4 Balanced Matrices and Weighted Digraphs

As was described in the introduction, the techniques and results that we have
developed for normal matrices can be adapted to the setting of weighted
digraphs. The naturality of such an application follows from the following
observation. Notice that the diagonal entries of $\mu(A)=[A,A^{\ast}]$ are of
the form $\|A_{i}\|^{2}-\|A^{i}\|^{2}$, where $A_{i}$ is the $i$th row of $A$
and $A^{i}$ is the $i$th column. Hence, if $A\in\mathbb{C}^{d\times d}$ is
normal, then $\|A_{i}\|^{2}=\|A^{i}\|^{2}$ for all $i=1,\dots,d$. This
suggests a certain _balancing condition_ , as we expand on below.

Suppose that $\mathcal{G}$ is a weighted, directed graph and $\widehat{A}$ is
its associated adjacency matrix; that is, the $(i,j)$ entry of $\widehat{A}$
is the (non-negative) weight of the directed edge from vertex $i$ to vertex
$j$ if such an edge exists, and zero if there is no such edge. In particular,
the entries of $\widehat{A}$ are non-negative real numbers. If $A$ is the
matrix whose entries are the square roots of the entries of $\widehat{A}$,
then $\|A_{i}\|^{2}=\|A^{i}\|^{2}$ says that the $i$th vertex $v_{i}$ of
$\mathcal{G}$ is _balanced_ : the sum of the weights of the edges coming into
$v_{i}$ equals the sum of the weights of the edges leaving $v_{i}$. In other
words, every real normal matrix $A$ corresponds to a balanced, weighted,
directed (multi-)graph555If $A$ has nonzero entries on its diagonal, the
resulting graph will have loop edges at the corresponding vertices.
$\mathcal{G}$ by interpreting the component-wise square of $A$ as the
adjacency matrix of $\mathcal{G}$. Moreover, the gradient descent procedures
described in the previous sections give ways of balancing a given weighted,
directed graph.

However, balancing a graph by gradient descent of $\operatorname{E}$ or
$\overline{\operatorname{E}}$ has some undesirable features. First, the
condition that $A$ is normal is stronger than the condition that $\mathcal{G}$
is balanced;666For example, in the case when all weights are 1, normality of
$A$ implies that every pair of vertices (not necessarily distinct) has the
same number of common out-neighbors as common in-neighbors. second, the
gradient flow is not guaranteed to ensure that a zero entry in the adjacency
matrix will stay zero, so the limiting balanced graph may have sprouted new
edges (and even loop edges) not present in the initial graph.

For applications to balancing graphs, then, the natural energy to consider is
not the non-normal energy $\operatorname{E}$, but rather the _unbalanced
energy_ $\operatorname{B}:\mathbb{C}^{d\times d}\to\mathbb{R}$ defined by

$\operatorname{B}(A)=\|\operatorname{diag}(AA^{\ast}-A^{\ast}A)\|^{2}=\sum_{i=1}^{d}\left(\|A_{i}\|^{2}-\|A^{i}\|^{2}\right)^{2},$

where we use $A_{i}$ for the $i$th row of $A$ and $A^{i}$ for the $i$th
column. We will say that $A$ is _balanced_ if $\operatorname{B}(A)=0$.

We now describe this function from the perspective of symplectic geometry and
GIT. Following a general theme of the paper, these observations are not really
essential in what follows, but they provided inspiration, especially in light
of Kirwan’s fundamental work [34]. Let $\operatorname{DSU}(d)$ be the subgroup
of $\operatorname{SU}(d)$ consisting of diagonal matrices. Then
$\operatorname{DSU}(d)\approx\operatorname{U}(1)^{d-1}$ is the standard
maximal torus of $\operatorname{SU}(d)$. The restriction of the conjugation
action of $\operatorname{SU}(d)$ on $\mathbb{C}^{d\times d}$ gives a
Hamiltonian action of $\operatorname{DSU}(d)$ on $\mathbb{C}^{d\times d}$ with
momentum map $\mu_{\Delta}:\mathbb{C}^{d\times d}\to\mathbb{R}^{d}$ given by
composing the momentum map $\mu$ of the $\operatorname{SU}(d)$ action with
orthogonal projection to
$\mathfrak{dsu}(d)^{\ast}\subset\mathfrak{su}(d)^{\ast}$ (see, e.g., [4,
Proposition III.1.10]). Under the identification of $\mathfrak{su}(d)^{\ast}$
with the traceless Hermitian matrices, $\mathfrak{dsu}(d)^{\ast}$ corresponds
to the traceless, diagonal, real matrices, so we have

$\mu_{\Delta}(A)=\operatorname{diag}(\mu(A))=\operatorname{diag}([A,A^{\ast}])$

and $\operatorname{B}(A)=\|\mu_{\Delta}(A)\|^{2}$. The GIT version of the
foregoing is that the diagonal subgroup
$\operatorname{DSL}_{d}(\mathbb{C})\subset\operatorname{SL}_{d}(\mathbb{C})$
has an algebraic action by conjugation on $\mathbb{C}^{d\times d}$ (or, in
Section 4.2, on $\mathbb{P}(\mathbb{C}^{d\times d})$).

###  4.1 Balancing Matrices by Gradient Descent

As in the case of $\operatorname{E}$, all critical points of
$\operatorname{B}$ are global minima:

######  Theorem 4.1.

The only critical points of $\operatorname{B}$ are the global minima; that is,
the balanced matrices.

###### Proof.

We first show that the gradient of the balanced energy is given by

$\nabla\operatorname{B}(A)=-4[A,\operatorname{diag}([A,A^{\ast}])].$ (11)

We write $\operatorname{B}=N\circ\mathrm{diag}\circ\mu$, where $\mu$ is the
momentum map (3), we consider the diagonalization operator as a linear map
$\mathrm{diag}:\mathbb{C}^{d\times d}\to\mathbb{C}^{d\times d}$, and $N$ is
the norm-squared map, as in the proof of Theorem 2.3. Following the logic of
that proof, we then have that

$\nabla\operatorname{B}(A)=D\mu(A)^{\vee}\mathrm{diag}^{\vee}\nabla
N(\mathrm{diag}\circ\mu(A)),$

where the superscripts once again denote adjoints with respect to
$\langle\cdot,\cdot\rangle$. It is not hard to show that the map
$\mathrm{diag}$ is self-adjoint and idempotent. Then

$\nabla\operatorname{B}(A)=D\mu(A)^{\vee}\mathrm{diag}(2\cdot\mathrm{diag}\circ\mu(A))=2D\mu(A)^{\vee}\mathrm{diag}(\mu(A))\\\
=2[\mathrm{diag}(\mu(A))+\mathrm{diag}(\mu(A))^{\ast},A]=-4[A,\mathrm{diag}([A,A^{\ast}])].$

The above shows that we have a critical point of $\operatorname{B}$ exactly
when

$0=[A,\operatorname{diag}([A,A^{\ast}])].$

Since the entries of $[A,\operatorname{diag}([A,A^{\ast}])]$ are of the form

$a_{ij}\left((\|A_{i}\|^{2}-\|A^{i}\|^{2})-(\|A_{j}\|^{2}-\|A^{j}\|^{2})\right),$
(12)

this means that $\|A_{i}\|^{2}-\|A^{i}\|^{2}=\|A_{j}\|^{2}-\|A^{j}\|^{2}$ for
all $i$ and $j$ such that $a_{ij}\neq 0$.

In other words, $A$ is a critical point of $\operatorname{B}$ if and only if
$\|A_{i}\|^{2}-\|A^{i}\|^{2}$ is independent of $i$. However, since

$\sum_{i=1}^{d}\left(\|A_{i}\|^{2}-\|A^{i}\|^{2}\right)=\sum_{i=1}^{d}\|A_{i}\|^{2}-\sum_{i=1}^{d}\|A^{i}\|^{2}=\|A\|^{2}-\|A\|^{2}=0,$

this can only happen if all $\|A_{i}\|^{2}-\|A^{i}\|^{2}=0$; that is, if $A$
is balanced. ∎

######  Remark 4.2.

Theorem 4.1 shows that $\operatorname{B}$ is an invex function, but
considering the values of $\operatorname{B}$ along the straight-line path
between the matrices $A_{0}$ and $A_{1}$ from Remark 2.5 shows that
$\operatorname{B}$ is not quasiconvex.

As in the case of $\operatorname{E}$, we can find global minima of
$\operatorname{B}$ by gradient descent. Specifically, let
$\mathscr{F}:\mathbb{C}^{d\times d}\times[0,\infty)\to\mathbb{C}^{d\times d}$
be the negative gradient flow of $\operatorname{B}$:

$\mathscr{F}(A_{0},0)=A_{0}\qquad\frac{d}{dt}\mathscr{F}(A_{0},t)=-\nabla\operatorname{B}(\mathscr{F}(A_{0},t)).$

Since $\operatorname{B}$ is a real polynomial function on $\mathbb{C}^{d\times
d}$, Theorem 4.1 implies that $\lim_{t\to\infty}\mathscr{F}(A_{0},t)$ is
always well-defined and normal. Since the real matrices stay real under
gradient flow, this limit will be real whenever $A_{0}$ is.

Moreover,

$\nabla\operatorname{B}(A)=-4[A,\operatorname{diag}([A,A^{\ast}])]=4\left(\left.\frac{d}{d\epsilon}\right|_{\epsilon=0}e^{\epsilon\operatorname{diag}([A,A^{\ast}])}\cdot
A\right)$ (13)

is tangent to the orbit of the diagonal subgroup
$\operatorname{DSL}_{d}(\mathbb{C})\leq\operatorname{SL}_{d}(\mathbb{C})$
acting by conjugation on $\mathbb{C}^{d\times d}$. In particular, flowing
$A_{0}$ by the gradient flow of $\operatorname{B}$ preserves not just the
eigenvalues of $A_{0}$, but also all principal minors of $A_{0}$, including
the diagonal entries of $A_{0}$.

From the expression (12) for the entries of
$-\frac{1}{4}\nabla\operatorname{B}(A)$ we see that, if there is $t_{0}\geq 0$
so that the $(i,j)$ entry in $\mathscr{F}(A_{0},t_{0})$ vanishes, then the
$(i,j)$ entry of $\mathscr{F}(A_{0},t)$ will vanish for all $t\geq t_{0}$. In
graph terms, the gradient flow of $\operatorname{B}$ cannot sprout new edges
in the graph. This also means that if $A_{0}$ is real, its entries cannot
change sign under gradient descent of $\operatorname{B}$. Thus, we have
proved:

######  Theorem 4.3.

For any $A_{0}\in\mathbb{C}^{d\times d}$, the matrix
$A_{\infty}\coloneq\displaystyle\lim_{t\to\infty}\mathscr{F}(A_{0},t)$ exists,
is balanced, has the same eigenvalues and principal minors as $A_{0}$, and has
zero entries wherever $A_{0}$ does. If $A_{0}$ is real, then so is
$A_{\infty}$, and if $A_{0}$ has all non-negative entries, then so does
$A_{\infty}$.

When we take $A_{0}$ to be the entrywise square root of the adjacency matrix
of some weighted, directed graph
$\mathcal{G}_{0}=(\mathcal{V}_{0},\mathcal{E}_{0},w_{0})$, then we can
sensibly interpret
$A_{\infty}=\displaystyle\lim_{t\to\infty}\mathscr{F}(A_{0},t)$ as the
entrywise square root of the adjacency matrix of some balanced, weighted,
directed graph
$\mathcal{G}_{\infty}=(\mathcal{V}_{\infty},\mathcal{E}_{\infty},w_{\infty})$
with $\mathcal{V}_{\infty}=\mathcal{V}_{0}$ and
$\mathcal{E}_{\infty}\subseteq\mathcal{E}_{0}$. In other words, gradient
descent of $\operatorname{B}$ balances $\mathcal{G}_{0}$ without introducing
any new edges.

######  Remark 4.4.

An important consideration in the applied literature on graph balancing is
that algorithms are _local_ , in the sense that iterative updates are only
performed based on node-level information [47, 30, 23]. This is due both to
practical constraints on data acquisition, as well as the need for
parallelizability in computation. Observe from the structure of the gradient
of the unbalanced energy that the gradient descent approach to graph balancing
is not local in the sense described above, but is _semi-local_ in the sense
that updates only depend on edge-level information. While this paper is
concerned with theory and makes no claims to efficiency or practicality of the
algorithm, the useful properties of the gradient flow of $\mathrm{B}$ suggest
that it may be interesting to explore its viability in real world
applications.

In the case of gradient descent of $\operatorname{E}$, we saw that all
nilpotent matrices flowed to the zero matrix. We see the same phenomenon here:
if $\mathcal{G}_{0}$ is a weighted, directed, acyclic graph (DAG), then its
adjacency matrix is nilpotent, as is the entrywise square root $A_{0}$. The
gradient flow $\mathscr{F}(A_{0},t)$ will limit to the zero matrix, which
makes sense: the only way to balance a weighted DAG is by driving all the
weights to zero.

###  4.2 Preserving Weights

Weighted DAGs provide an extreme example of the general phenomenon that
gradient descent of $\operatorname{B}$ decreases the Frobenius norm. In graph
terms, if $A_{0}$ is the entrywise square root of the adjacency matrix of a
weighted, directed graph $\mathcal{G}_{0}$, then the squared Frobenius norm

$\|A_{0}\|^{2}=\sum_{i,j}|a_{ij}|^{2}=\sum_{i,j}a_{ij}^{2}$

is precisely the sum of the weights in $\mathcal{G}_{0}$. If the weights
correspond to, e.g., mass traversing between nodes in a network, then it may
not make sense to balance the flows in the network by reducing the total mass
in the system.

In order to preserve the sum of weights on $\mathcal{G}_{0}$, we consider
$\overline{\operatorname{B}}:\mathcal{U}_{d}\to\mathbb{R}$, the restriction of
$\operatorname{B}$ to $\mathcal{U}_{d}$, and its gradient descent
$\overline{\mathscr{F}}:\mathcal{U}_{d}\times[0,\infty)\to\mathcal{U}_{d}$
given by

$\overline{\mathscr{F}}(A_{0},0)=A_{0}\qquad\frac{d}{dt}\overline{\mathscr{F}}(A_{0},t)=-\operatorname{grad}\overline{\operatorname{B}}(\overline{\mathscr{F}}(A_{0},t)).$

######  Theorem 4.5.

For any non-nilpotent $A_{0}\in\mathcal{U}_{d}$, the matrix
$A_{\infty}\coloneq\displaystyle\lim_{t\to\infty}\overline{\mathscr{F}}(A_{0},t)$
exists, is balanced, has Frobenius norm 1, and has zero entries wherever
$A_{0}$ does. If $A_{0}$ is real, so is $A_{\infty}$, and if $A_{0}$ has all
non-negative entries, then so does $A_{\infty}$.

In graph terms, if $A_{0}$ is the entrywise square root of an adjacency matrix
for $\mathcal{G}_{0}$ with total weight 1, then $A_{\infty}$ is the entrywise
square root of the adjacency matrix for a balanced graph
$\mathcal{G}_{\infty}$ with total weight 1 whose vertices are the same as the
vertices of $\mathcal{G}_{0}$ and whose edges are a subset of the edges of
$\mathcal{G}_{0}$. That is, gradient descent of $\overline{\operatorname{B}}$
balances $\mathcal{G}_{0}$ without introducing any new edges and without
losing any overall weight.

The strategy for proving Theorem 4.5 is the same as for Theorem 3.1. The
existence of a unique limit point $A_{\infty}$ follows from the fact that
$\overline{\operatorname{B}}$ is a polynomial function on $\mathcal{U}_{d}$,
and hence has a Łojasiewicz exponent. The bulk of the argument is in showing
that the gradient flow preserves non-nilpotency and that the non-minizing
critical points are nilpotent. The rest of the theorem will follow from the
structure of $\operatorname{grad}\overline{\operatorname{B}}$ and the fact
that the real submanifold of $\mathcal{U}_{d}$ is invariant under gradient
flow.

First, we compute the intrinsic gradient of $\overline{\operatorname{B}}$,
which follows the same pattern as
$\operatorname{grad}\overline{\operatorname{E}}$:

######  Proposition 4.6.

The intrinsic gradient of $\overline{\operatorname{B}}$ on $\mathcal{U}_{d}$
is

$\operatorname{grad}\overline{\operatorname{B}}(A)=-4([A,\operatorname{diag}([A,A^{\ast}])]+\overline{\operatorname{B}}(A)A).$

###### Proof.

We know that

$\operatorname{grad}\overline{\operatorname{B}}(A)=\nabla\operatorname{B}(A)-\langle\nabla\operatorname{B}(A),A\rangle
A,$

so the key is to use (11) and the fact that the diagonal of $[A,A^{\ast}]$ is
real to compute

$\langle\nabla\operatorname{B}(A),A\rangle=-4\mathrm{Re}\operatorname{tr}([A,\operatorname{diag}([A,A^{\ast}])]^{\ast}A)=-4\mathrm{Re}\operatorname{tr}(\operatorname{diag}([A,A^{\ast}])A^{\ast}A-A^{\ast}\operatorname{diag}([A,A^{\ast}])A)\\\
=4\mathrm{Re}\operatorname{tr}(\operatorname{diag}([A,A^{\ast}])[A,A^{\ast}])=4\mathrm{Re}\operatorname{tr}(\operatorname{diag}([A,A^{\ast}])\operatorname{diag}([A,A^{\ast}]))=4\|\operatorname{diag}([A,A^{\ast}])\|^{2}=4\overline{\operatorname{B}}(A)$

using the linearity and cyclic invariance of trace. ∎

Each entry of $\operatorname{grad}\overline{\operatorname{B}}(A)$ is a scalar
multiple of the corresponding entry of $A$, so the fact that the negative
gradient flow $\overline{\mathscr{F}}$ preserves zero entries and cannot
change the sign of real entries follows immediately.

Next, we prove an analog of 3.5. Recall that $s(A)=\sum|\lambda_{i}|^{2}$ is
the sum of the squares of the absolute values of the eigenvalues of $A$.

######  Lemma 4.7.

For any $A\in\mathcal{U}_{d}$,

$\langle-\operatorname{grad}\overline{\operatorname{B}}(A),\operatorname{grad}s(A)\rangle=8s(A)\overline{\operatorname{B}}(A).$

###### Proof.

The proof exactly parallels the proof of 3.5 by substituting
$\operatorname{B}$, $\overline{\operatorname{B}}$, and (13) for
$\operatorname{E}$, $\overline{\operatorname{E}}$, and (8), respectively. ∎

Since
$\langle-\operatorname{grad}\overline{\operatorname{B}}(A),\operatorname{grad}s(A)\rangle=8s(A)\overline{\operatorname{B}}(A)\geq
0$, $s(A)$ must be non-decreasing along the negative gradient flow lines of
$\overline{\operatorname{B}}$, so we have proved:

######  Proposition 4.8.

If $A_{0}\in\mathcal{U}_{d}$ is non-nilpotent, then so is
$A_{t}\coloneq\overline{\mathscr{F}}(A_{0},t)$ and so is
$A_{\infty}\coloneq\displaystyle\lim_{t\to\infty}\overline{\mathscr{F}}(A_{0},t)$.

We know the balanced matrices are exactly the global minima of
$\overline{\operatorname{B}}$. 4.6 implies that $A$ is a critical point of
$\overline{\operatorname{B}}$ if and only if

$0=[A,\operatorname{diag}([A,A^{\ast}])]+\overline{\operatorname{B}}(A)A.$

When $A$ is a non-minimizing critical point,
$\overline{\operatorname{B}}(A)\neq 0$ and the same Jacobson’s Lemma argument
as in 3.7 shows that $A$ is nilpotent, proving:

######  Proposition 4.9.

All non-minimizing critical points of $\overline{\operatorname{B}}$ are
nilpotent.

This completes the proof of Theorem 4.5.

Figure 1 shows an application of this approach to balancing graphs, and Figure
6 shows a much larger example. In both cases, up to an overall normalization
to ensure $\|A_{0}\|=1$, the non-zero entries in the starting matrix $A_{0}$
were populated by the absolute values of standard Gaussians.

Figure 6: Balancing a larger graph by the flow $\overline{\mathscr{F}}$, with
$A_{0}$ on the left and
$A_{\infty}=\displaystyle\lim_{t\to\infty}\overline{\mathscr{F}}(A_{0},t)$ on
the right. The thickness of each edge is proportional to its weight. The
underlying graph is a random planar graph with 100 vertices and 284 edges,
constructed as the 1-skeleton of the Delaunay triangulation of 100 random
points in the square; to make the visualization more comprehensible, the graph
that is shown is a spring embedding, so the vertices are not at the locations
of the original random points in the square.

###  4.3 Topology of Unit Norm Balanced Graphs

Let $\mathcal{UB}_{d}$ denote the space of balanced $d\times d$ matrices of
unit Frobenius norm, and let $\mathcal{UB}_{d}^{\mathbb{R}}$ denote the
subspace of balanced matrices with real entries. The topology of these spaces
is tied to the topology of the relevant spaces of normal matrices, as we
record in the following theorem.

######  Theorem 4.10.

The spaces $\mathcal{U}\mathcal{N}_{d}$ and $\mathcal{UB}_{d}$ are homotopy
equivalent. Similarly, the spaces $\mathcal{UN}_{d}^{\mathbb{R}}$ and
$\mathcal{UB}_{d}^{\mathbb{R}}$ are homotopy equivalent.

###### Proof.

By Theorem 3.1 and Theorem 4.5, respectively, $\mathcal{U}\mathcal{N}_{d}$ and
$\mathcal{UB}_{d}$ are both deformation retracts of the space of non-nilpotent
unit norm matrices. The same theorems give the result in the real case. ∎

### Acknowledgments

We are grateful to Malbor Asllani for catalyzing this line of inquiry and to
Chris Peterson for enlightening conversations. We would like to thank the
Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and
hospitality during the program New equivariant methods in algebraic and
differential geometry, where some of the work on this paper was undertaken.
This work was supported by EPSRC grant EP/R014604/1 and by grants from the
National Science Foundation (DMS–2107808 and DMS–2324962, Tom Needham;
DMS–2107700, Clayton Shonkwiler).

## References

  * [1] Pierre-Antoine Absil and Krzysztof Kurdyka.  On the stable equilibrium points of gradient systems.  Systems & Control Letters, 55(7):573–577, 2006.
  * [2] Malbor Asllani and Timoteo Carletti.  Topological resilience in non-normal networked systems.  Physical Review E, 97(4):042302, 2018.
  * [3] Malbor Asllani, Renaud Lambiotte, and Timoteo Carletti.  Structure and dynamical behavior of non-normal networks.  Science Advances, 4(12):eaau9403, 2018.
  * [4] Michèle Audin.  Torus Actions on Symplectic Manifolds, volume 93 of Progress in Mathematics.  Birkhäuser Verlag, Basel, second revised edition, 2004.
  * [5] Friedrich L. Bauer and Charles T. Fike.  Norms and exclusion theorems.  Numerische Mathematik, 2(1):137–141, 1960.
  * [6] Adi Ben-Israel and Bertram Mond.  What is invexity?  The Journal of the Australian Mathematical Society. Series B. Applied Mathematics, 28(1):1–9, 1986.
  * [7] Bernhard G. Bodmann and John Haas.  Frame potentials and the geometry of frames.  Journal of Fourier Analysis and Applications, 21(6):1344–1383, 2015\.
  * [8] Christoph Böhm and Ramiro A. Lafuente.  Real geometric invariant theory.  In Owen Dearricott, Wilderich Tuschmann, Yuri Nikolayevsky, Thomas Leistner, and Diarmuid Crowley, editors, Differential Geometry in the Large, number 463 in London Mathematical Society Lecture Note Series, pages 11–49. Cambridge University Press, Cambridge, UK, 2021.
  * [9] Jameson Cahill, Dustin G. Mixon, and Nate Strawn.  Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames.  SIAM Journal on Applied Algebra and Geometry, 1(1):38–72, 2017\.
  * [10] Moody T. Chu.  Least squares approximation by real normal matrices with specified spectrum.  SIAM Journal on Matrix Analysis and Applications, 12(1):115–127, 1991.
  * [11] Bruce D. Craven.  Duality for generalized convex fractional programs.  In Siegfried Schaible and William T. Ziemba, editors, Generalized Concavity in Optimization and Economics: Proceedings of the NATO Advanced Study Institute held at the University of British Columbia, Vancouver, Canada, Aug. 4-15, 1980, pages 473–489. Academic Press, New York, NY, USA, 1981.
  * [12] Bruce D. Craven and Bevil M. Glover.  Invex functions and duality.  Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 39(1):1–20, 1985.
  * [13] Ronald W. Daniel and Basil Kouvaritakis.  The choice and use of normal approximations to transfer-function matrices of multivariable control systems.  International Journal of Control, 37(5):1121–1133, 1983.
  * [14] Ronald W. Daniel and Basil Kouvaritakis.  Analysis and design of linear multivariable feedback systems in the presence of additive perturbations.  International Journal of Control, 39(3):551–580, 1984.
  * [15] Johannes Ebert.  A lecture course on cobordism theory, 2012.  https://ivv5hpp.uni-muenster.de/u/jeber_02/skripten/bordism-skript.pdf.
  * [16] Ludwig Elsner and Khakim D. Ikramov.  Normal matrices: an update.  Linear Algebra and its Applications, 285(1–3):291–303, 1998.
  * [17] Jonathan M. Fisher.  Morse theory with the norm-square of a hyperKähler moment map.  The Quarterly Journal of Mathematics, 65(1):149–173, 2014.
  * [18] Shmuel Friedland.  Normal matrices and the completion problem.  SIAM Journal on Matrix Analysis and Applications, 23(3):896–902, 2002.
  * [19] Richard Gabriel.  The normal $\Delta$H-Matrices with connection to some Jacobi-like methods.  Linear Algebra and its Applications, 91:181–194, 1987.
  * [20] Claude Godbillon.  Eléments de topologie algébrique.  Hermann, Paris, 1971.
  * [21] Israel Gohberg, Peter Lancaster, and Leiba Rodman.  Invariant Subspaces of Matrices with Applications.  Number 51 in Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2006.
  * [22] Nicola Guglielmi and Carmela Scalone.  Computing the closest real normal matrix and normal completion.  Advances in Computational Mathematics, 45:2867–2891, 2019.
  * [23] Christoforos N. Hadjicostis and Apostolos Rikos.  Distributed strategies for balancing a weighted digraph.  In 2012 20th Mediterranean Conference on Control & Automation (MED), pages 1141–1146. IEEE, 2012.
  * [24] Morgan A. Hanson.  On sufficiency of the Kuhn–Tucker conditions.  Journal of Mathematical Analysis and Applications, 80(2):545–550, 1981.
  * [25] Allen Hatcher.  Algebraic Topology.  Cambridge University Press, 2002.
  * [26] Peter Heinzner, Gerald W. Schwarz, and Henrik Stötzel.  Stratifications with respect to actions of real reductive groups.  Compositio Mathematica, 144(1):163–185, 2008.
  * [27] Peter Henrici.  Bounds for iterates, inverses, spectral variation and fields of values of non-normal matrices.  Numerische Mathematik, 4(1):24–40, 1962.
  * [28] Nicholas J. Higham.  Matrix nearness problems and applications.  In Michael J. C. Gover and Stephen Barnett, editors, Applications of Matrix Theory: Based on the Proceedings of a Conference Organized by the Institute of Mathematics and its Applications on Applications of Matrix Theory, held in the University of Bradford in July, 1988, number 22 in The Institute of Mathematics and its Applications Conference Series. New Series, pages 1–27. The Clarendon Press, Oxford University Press, New York, NY, USA, 1989\.
  * [29] Morris W. Hirsch.  Differential Topology.  Number 33 in Graduate Texts in Mathematics. Springer, New York, NY, USA, 2012.
  * [30] Loh Hooi-Tong.  On a class of directed graphs—with an application to traffic-flow problems.  Operations Research, 18(1):87–94, 1970.
  * [31] Nathan Jacobson.  Rational methods in the theory of Lie algebras.  Annals of Mathematics, Second Series, 36(4):875–881, 1935.
  * [32] Jens Carsten Jantzen.  Nilpotent orbits in representation theory.  In Jean-Philippe Anker and Bent Orsted, editors, Lie Theory: Lie Algebras and Representations, pages 1–211. Birkhäuser, Boston, MA, USA, 2004\.
  * [33] Irving Kaplansky.  Jacobson’s Lemma revisited.  Journal of Algebra, 62(2):473–476, 1980.
  * [34] Frances Kirwan.  Cohomology of Quotients in Symplectic and Algebraic Geometry, volume 31 of Mathematical Notes.  Princeton University Press, Princeton, NJ, USA, 1984.
  * [35] Bertram Kostant.  Lie group representations on polynomial rings.  American Journal of Mathematics, 85(3):327, 1963.
  * [36] John M. Lee.  Introduction to Smooth Manifolds.  Number 218 in Graduate Texts in Mathematics. Springer, New York, NY, USA, second edition, 2013.
  * [37] Eugene Lerman.  Gradient flow of the norm squared of a moment map.  L’Enseignement Mathématique, 51:117–127, 2005.
  * [38] Marvin Marcus and Henryk Minc.  A Survey of Matrix Theory and Matrix Inequalities.  Series in Advanced Mathematics. Allyn and Bacon, Boston, MA, USA, 1964\.
  * [39] Dustin G. Mixon, Tom Needham, Clayton Shonkwiler, and Soledad Villar.  Three proofs of the Benedetto–Fickus theorem.  In Sampling, Approximation, and Signal Analysis: Harmonic Analysis in the Spirit of J. Rowland Higgins, pages 371–391. Springer, 2024\.
  * [40] David Mumford, John Fogarty, and Frances Kirwan.  Geometric Invariant Theory, volume 34 of Ergebnisse der Mathematik und ihrer Grenzgebiete.  Springer–Verlag, Berlin, 1994.
  * [41] Riccardo Muolo, Malbor Asllani, Duccio Fanelli, Philip K Maini, and Timoteo Carletti.  Patterns of non-normality in networked systems.  Journal of theoretical biology, 480:81–91, 2019.
  * [42] Tom Needham and Clayton Shonkwiler.  Symplectic geometry and connectivity of spaces of frames.  Advances in Computational Mathematics, 47(1):5, 2021.
  * [43] Tom Needham and Clayton Shonkwiler.  Toric symplectic geometry and full spark frames.  Applied and Computational Harmonic Analysis, 61:254–287, 2022.
  * [44] Amnon Neeman.  The topology of quotient varieties.  The Annals of Mathematics, Second Series, 122(2):419–459, 1985\.
  * [45] Linda Ness.  A stratification of the null cone via the moment map.  American Journal of Mathematics, 106(6):1281–1329, 1984.
  * [46] Silvia Noschese and Lothar Reichel.  The structured distance to normality of banded Toeplitz matrices.  BIT Numerical Mathematics, 49:629–640, 2009.
  * [47] Apostolos I. Rikos, Themistoklis Charalambous, and Christoforos N. Hadjicostis.  Distributed weight balancing over digraphs.  IEEE Transactions on Control of Network Systems, 1(2):190–201, 2014\.
  * [48] Axel Ruhe.  Closest normal matrix finally found!  BIT Numerical Mathematics, 27:585–598, 1987.
  * [49] Clayton Shonkwiler.  Geometry of Normal Matrices.  https://github.com/shonkwiler/normal-matrices-computations.
  * [50] Richard P. Thomas.  Notes on GIT and symplectic reduction for bundles and varieties.  Surveys in Differential Geometry, 10(1):221–273, 2005.
  * [51] Hassler Whitney.  Elementary structure of real algebraic varieties.  Annals of Mathematics, 66(3):545–556, 1957.
  * [52] Christopher T. Woodward.  The Yang–Mills heat flow on the moduli space of framed bundles on a surface.  Preprint, arXiv:math/0211231, 2002. This is a preprint version of Christopher T. Woodward. The Yang–Mills heat flow on the moduli space of framed bundles on a surface. _American Journal of Mathematics_ , 128(2):311–369, 2006.
  * [53] Stanisław Łojasiewicz.  Sur les trajectoires du gradient d’une fonction analytique.  In Seminari di Geometria 1982–1983, pages 115–117. Dipartimento di Matematica, Instituto di Geometria, Università di Bologna, 1984\.