# Bilinear Systems Induced by Proper Lie Group Actions

Gong Cheng, Wei Zhang, and Jr-Shin Li The authors are with the Department of
Electrical and Systems Engineering, Washington University, Saint Louis, MO
63130, USA (e-mail: {gong.cheng, wei.zhang, jsli}@wustl.edu).

###### Abstract

In the study of induced bilinear systems, the classical Lie algebra rank
condition (LARC) is known to be impractical since it requires computing the
rank everywhere. On the other hand, the transitive Lie algebra condition,
while more commonly used, relies on the classification of transitive Lie
algebras, which is elusive except for few simple geometric objects such as
spheres. We prove in this note that for bilinear systems induced by proper Lie
group actions, the underlying Lie algebra is closely related to the orbits of
the group action. Knowing the pattern of the Lie algebra rank over the
manifold, we show that the LARC can be relaxed so that it suffices to check
the rank at an arbitrary single point. Moreover, it removes the necessity for
classifying transitive Lie algebras. Finally, this relaxed rank condition also
leads to a characterization of controllable submanifolds by orbits.

###### Index Terms:

Bilinear system, Lie group, proper group action

##  I Introduction

Bilinear systems induced by Lie group actions have attracted great attention
in control theory and engineering. Prominent examples range from excitation of
spin systems in quantum physics [1, 2, 3] to control of rigid bodies in
mechanics to manipulation of neuron oscillators in neuroscience [4, 5]. In
these examples, examining controllability of the considered systems is one of
the most fundamental steps. However, the classical controllability condition,
the Lie algebra rank condition (LARC), requires the examination on the rank of
the underlying Lie algebra of the system at each point over the entire state
space, thus impractical in most cases. On the other hand, it has been revealed
that induced bilinear systems on homogeneous spaces are closely related to
their counterparts on Lie groups, so that controllability of induced systems
corresponds to transitivity of Lie group actions (or Lie subalgebras) [6, 7].
Following this correspondence, many works have been done to study the
controllability of induced systems using transitivity [8, 9]. One major
obstacle in this approach is that it requires prior knowledge about the
classification of transitive Lie subalgebras, which is only known for very few
manifolds: Montgomery and Samelson [10] classified all transitive Lie group
actions on spheres in 1943, and Boothby [9, 11] classified all transitive Lie
algebras for punctured Euclidean spaces in 1975.

In this note, we investigate the Lie algebra rank and characterize its pattern
from a group action viewpoint. By establishing a connection between the
underlying Lie algebra of the induced system and the orbits of its
corresponding group action, we show that the rank is constant on each orbit,
given that the group action is proper. Consequently, we can relax the
classical LARC such that it suffices to check the Lie algebra rank at an
arbitrary single point, instead of over the entire state space. This relaxed
condition applies to bilinear systems induced by any compact Lie group, as
well as many non-compact Lie groups such as the special Euclidean group
$\mathrm{SE}(n)$. Our result simplifies the analysis of controllability of
many induced bilinear systems, since classifications of transitive Lie
algebras are no longer necessary. Furthermore, we also prove that for bilinear
systems induced by proper Lie group actions that are not controllable, their
controllable submanifolds can be fully characterized by the orbits of group
actions.

The note is organized as follows: in Section II we provide an overview of the
concepts of group actions, orbits, and induced bilinear systems. In Section
III, we formulate the relaxed rank condition for bilinear systems on
$\mathbb{S}^{n-1}$ induced by $\mathrm{SO}(n)$. In Section IV, we generalize
our result to all bilinear systems induced by proper Lie group actions.

##  II Bilinear Systems Induced by Lie Group Actions

The Lie algebra rank condition (LARC) marks an important milestone in
geometric control theory aiming at increasing the accessibility to nonlinear
systems by exploiting tools in modern mathematics, in particular, differential
geometry and Lie theory. Technically, LARC reveals the connection between
controllability of a nonlinear system and the rank of the Lie algebra
generated by the vector fields which govern the system dynamics (See Appendix
-B). So far, LRAC remains one of the most widely-used criteria for examining
controllability of nonlinear systems, but it also has its limitations. For
example, as is shown in the motivating example below, systems with vector
fields which generate a non-constant rank distribution are outside its scope.

Let us consider the bilinear system defined on $\mathbb{R}^{n}$ as

$\dot{x}(t)=\Bigl{(}B_{0}+\sum_{i=1}^{m}u_{i}(t)B_{i}\Bigr{)}x(t),\quad
x(0)=x_{0}\in\mathbb{R}^{n}\backslash\\{0\\},$ (1)

where $B_{i}\in\mathfrak{so}(n)$, the special orthogonal Lie algebra
consisting of $n\times n$ anti-symmetric matrices, for all $i=0,\dots,m$. Note
that every $B_{i}$ gives rise to an element $B_{i}x$ in
$\mathfrak{X}(\mathbb{R}^{n})$, the space of smooth vector fields on
$\mathbb{R}^{n}$, and at any $x\in\mathbb{R}^{n}$ the tangent vector
$B_{i}x\in\mathsf{T}_{x}\mathbb{R}^{n}$ satisfies the following identity

$x\cdot{}(B_{i}x)=x^{\intercal}B_{i}x=(x^{\intercal}B_{i}x)^{\intercal}=x^{\intercal}(-B_{i})x=0,$

where $\mathsf{T}_{x}\mathbb{R}^{n}$ denotes the tangent space of
$\mathbb{R}^{n}$ at $x$, and “$\cdot$” is the Euclidean inner product.
Geometrically, the above identity implies that the tangent vector $B_{i}x$ is
always perpendicular to the vector $x$. Adopting this observation to the
system in (1) yields

$\frac{\mathrm{d}}{\mathrm{d}t}\|x(t)\|^{2}=2x(t)\cdot\dot{x}(t)=x(t)\cdot
B_{i}x(t)=0.$

Namely, the Euclidean norm of the state variable is invariant under the system
dynamics, so the system is restricted to evolving on the sphere centered at
the origin with radius $\|x_{0}\|$. Without loss of generality, we may assume
for the initial condition $\|x_{0}\|=1$ and reduce the state space of the
system to the $(n-1)$-dimensional unit sphere $\mathbb{S}^{n-1}$.

By the LARC, controllability of the system in (1) is determined by the rank of
the Lie algebra $\mathfrak{L}=\mathrm{Lie}\,\\{B_{i}x:x\in\mathbb{S}^{n-1},\
i=0,\dots,m\\}$. However, in general, $\mathfrak{L}$ is not of constant rank.
For example, in the case of $n=4$, $m=3$, and $B_{0}=0$,

$B_{1}=\pNiceMatrix[columns-width=2mm]0&\\\ 01\\\ -10\\\ 0\\\ ,\
B_{2}=\pNiceMatrix[columns-width=2mm]0&\\\ 0\\\ 01\\\ -10\\\ ,$

since $[B_{1}x,B_{2}x]=-[B_{1},B_{2}]x$, we have that

$\mathfrak{L}=\mathrm{Lie}\,\\{B_{1}x,B_{2}x\\}=\mathrm{span}\,\\{B_{1}x,B_{2}x,[B_{1},B_{2}]x\\},$

where

$[B_{1},B_{2}]=\pNiceMatrix[columns-width=2mm]0&\\\ 01\\\ 0\\\ -10\\\ .$

We can check that at $x_{1}=(1,0,0,0)^{\intercal}$,
$B_{1}x_{1}=B_{2}x_{1}=[B_{1}x_{1},B_{2}x_{1}]=0$, so
$\operatorname{\mathrm{rank}}\mathfrak{L}{}=0$ at $x_{1}$. In comparison, at
$x_{2}=(0,1,0,0)^{\intercal}$, $\mathfrak{L}$ is the span of
$(0,0,-1,0)^{\intercal}$ and $(0,0,0,-1)^{\intercal}$, so
$\operatorname{\mathrm{rank}}\mathfrak{L}=2$ at $x_{2}$. As a result, the Lie
algebra $\mathfrak{L}\subset\mathfrak{X}(\mathbb{S}^{3})$ gives a non-constant
rank distribution on $\mathbb{S}^{3}$. This poses a problem for determining
the controllable submanifold of the system by using LARC.

To elaborate this non-constant rank phenomenon from an algebraic viewpoint, we
note that $\mathbb{S}^{n-1}$ is an ${\rm SO}(n)$-homogeneous space, so that
the vector fields $\\{B_{i}x:x\in\mathbb{S}^{n-1},\ i=0,\dots,m\\}$ which
govern the dynamics of the system in (1) are generated by the
$\mathfrak{so}(n)$-action on $\mathbb{R}^{n}$. Equivalently, the system in (1)
is induced by the Lie group action of SO$(n)$ on $\mathbb{R}^{n}$. However,
the SO$(n)$-action on $\mathbb{S}^{n-1}$ is not free, and correspondingly, the
$\mathfrak{so}(n)$-action as a Lie algebra homomorphism from
$\mathfrak{so}(n)$ to $\mathfrak{X}(\mathbb{S}^{n-1})$ is not injective. So
different elements in $\mathfrak{so}(n)$ may give the same vector fields on
$\mathbb{S}^{n-1}$, which result in the drop of the rank of the Lie algebra
generated by $B_{i}x$.

In what follows, to tackle the issue of non-constant rank, we integrate the
theory on Lie group actions with geometric control theory to establish
sufficient and necessary controllability conditions for bilinear systems
induced by Lie group actions on smooth manifolds. The basics of Lie groups
actions, homogeneous spaces and quotient manifolds that are necessary to our
development are reviewed in Appendix -A.

### Controllability of Induced Systems

Next, we introduce the theory that connects induced bilinear systems to
bilinear systems on Lie groups. First, we give the formal definition of
induced systems.

######  Definition 1 (Induced Systems).

Let $G$ be a connected Lie group, $\mathfrak{g}$ its Lie algebra, and $M$ a
smooth manifold which admits a left $G$-action. Given a right-invariant
bilinear system on $G$,

$\dot{X}=\Bigl{(}B_{0}+\sum_{i=1}^{m}u_{i}(t)B_{i}\Bigr{)}X(t),\quad
B_{i}\in\mathfrak{g},\quad X(0)=I,$ (2)

it induces a bilinear system on $M$ in the form of

$\dot{x}(t)=(\theta_{\ast}B_{0})(x)+\sum_{k=1}^{m}u_{i}(t)(\theta_{\ast}B_{i})(x),\quad
x(0)\in{}M.$ (3)

where $\theta_{\ast}B_{i}$ is the fundamental vector field of $B_{i}$ (see
Definition 15). The bilinear system in (3) is called the _induced system_ of
(2).

The system in (3) is named as “induced” because its drifting and control
vector fields are generated from those of the system in (2), which reflect the
action of $G$ on $M$ from the infinitesimal viewpoint. It is then natural
that, other than the controllability of the system in (2) on $G$, the
properties of the action of $G$ on $M$ also impacts on controllability of the
induced system in (3).

######  Lemma 2 (Controllability of Induced Systems).

Let $M$ be a homogeneous $G$-space, i.e., $G$ acts transitively on $M$.
Suppose that the bilinear system in (2) is controllable on $G$, or its
reachable set $\mathcal{A}$, which is a semigroup, acts transitively on $M$,
then the induced system in (3) is controllable on $M$.

###### Proof.

See [6, Theorem 5.1]. ∎

On the other hand, since all Lie groups and their homogeneous spaces are
analytic, the following lemma provides a necessary condition for
controllability of induced systems. In general, for a system

$\dot{x}(t)=a_{0}(x)+\sum_{i=1}^{m}u_{i}(t)a_{i}(x)$ (4)

on an analytic manifold $M$ with $a_{i}(x)\in\mathfrak{X}(M)$ being analytic
on $M$, we have the following result.

######  Lemma 3 (See [12, Theorem 1]).

Suppose $M$ is an analytic manifolds of dimension $k$, and that its
fundamental group $\pi_{1}(M)$ has no elements of infinite order. If a system
in (4) is controllable on $M$, then the Lie subalgebra $\mathfrak{A}$,
generated by $\\{Y_{0},a_{1},\dots,a_{m}\\}$ where $Y_{0}$ has the local form
as

$Y_{0}=\frac{\partial}{\partial{}t}+\sum_{j}a^{j}_{0}\frac{\partial}{\partial{}x_{j}},$

has rank $k+1$ on the space $M\times\mathbb{R}$.

Since the vector fields $a_{i}(x)$ are time-invariant and commute with the
differential operator $\partial/\partial t$, if
$\operatorname{\mathrm{rank}}\mathfrak{A}=k-1$, then the Lie algebra generated
by $\\{a_{0},\ldots,a_{m}\\}$ must have rank $k$. So if we let
$\iota:M\hookrightarrow M\times\mathbb{R}$ to denote the the inclusion map and
taking $a_{i}=\iota_{\ast}\theta_{\ast}B_{i}$, we conclude the lemma below.

######  Lemma 4.

If the induced system in (3) is controllable on $M$, then the Lie algebra
generated by the fundamental vector fields $\\{\theta_{\ast}B_{i},\
{}i=0,\dots,m\\}$ is of constant rank $k$ on $M$.

##  III Bilinear Systems Induced by $\mathrm{SO}(n)$-Actions and the Rank
Condition

In this section, we examine the bilinear system in (1) using the results of
group actions that we introduced in Section II, and prove a sufficient and
necessary controllability condition. First, we should emphasize that the
system in (1) is an induced system. Indeed, for a natural group action of any
matrix group $G$ on $\mathbb{R}^{n}$ (i.e., matrix multiplication), its
fundamental vector fields on $\mathbb{R}^{n}$ are in the form of products: for
any $B\in\mathfrak{g}$, let $(\theta_{\ast}B)$ denote the fundamental vector
field on $\mathbb{R}^{n}$ corresponding to $B$, then by Definition 15 we have

$\displaystyle(\theta_{\ast}B)(x)$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}\Big{|}_{t=0}\exp(tB)x$ (5)
$\displaystyle=\Bigl{(}\frac{\mathrm{d}}{\mathrm{d}t}\Big{|}_{t=0}\exp(tB)\Bigr{)}x=Bx.$

So according to Definition 1, the system in (1) is induced by the following
bilinear system on $\mathrm{SO}(n)$:

$\dot{X}=\Bigl{(}B_{0}+\sum_{i=1}^{m}u_{i}(t)B_{i}\Bigr{)}X(t),\quad X(0)=I.$
(6)

Recall from Lemma 2 that controllability of an induced systems is related to
controllability of its counterpart on a Lie group. Therefore, the system in
(1) on $\mathbb{S}^{n-1}$ is controllable if the bilinear system in (6) is
controllable on $\mathrm{SO}(n)$, or if its controllable submanifold $H$,
which is a closed Lie subgroup of $\mathrm{SO}(n)$ with its Lie subalgebra
being $\mathfrak{h}:=\mathrm{Lie}\,\\{B_{i}\\}\leqslant{}\mathfrak{so}(n)$,
acts transitively on $\mathbb{S}^{n-1}$. So the controllability of (1) depends
on the transitivity of the action by $H$, and for that, we introduce a rank
condition that connects the transitivity of $H$-action to the rank of
$\mathfrak{L}:=\mathrm{Lie}\,\\{B_{i}x\\}$, the underlying Lie algebra of (1).
We will see that, in this case, it suffices to check the rank of
$\mathfrak{L}$ at _any single_ point $x$ on the sphere $\mathbb{S}^{n-1}$.

######  Definition 5.

Let $G$ be a matrix group acting naturally on $\mathbb{R}^{n}$, and
$\mathfrak{g}$ its Lie algebra. The _rank_ of $\mathfrak{g}$ at a point
$x\in\mathbb{R}^{n}$ is defined as the dimension of the subspace
$\\{Ax:A\in\mathfrak{g}\\}\subseteq\mathsf{T}_{x}\mathbb{R}^{n}$, i.e.,

$\operatorname{\mathrm{rank}}_{x}\mathfrak{g}:=\dim\\{Ax:A\in\mathfrak{g}\\}.$

Note that by Definition 5, the rank of the Lie algebra $\mathfrak{L}$
generated by vector fields $\mathrm{Lie}\,\\{B_{i}x\\}$ coincides with
$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}$ at all $x$, where
$\mathfrak{h}=\mathrm{Lie}\,\\{B_{i}\\}$. The next lemma shows a group action
of a subgroup of $\mathrm{SO}(n)$ is transitive if its Lie algebra has the
_maximal_ rank.

######  Lemma 6.

Let $\mathfrak{h}$ be a Lie subalgebra of $\mathfrak{so}(n)$ which corresponds
to a closed Lie subgroup $H\leqslant{}\mathrm{SO}(n)$. The (natural) group
action of $H$ on $\mathbb{S}^{n-1}$ is _transitive_ if and only if
$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=n-1$ for some
$x\in\mathbb{S}^{n-1}$.

###### Proof.

As we will show in Lemma 9, the rank of $\mathfrak{h}$ at $x$ coincides with
the dimension of the orbit $H(x)\subset\mathbb{S}^{n-1}$. Suppose $H$ acts
transitively on $\mathbb{S}^{n-1}$, i.e., $H(x)=\mathbb{S}^{n-1}$ for any
$x\in\mathbb{S}^{n-1}$, so
$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=\dim{}H(x)=n-1$. On the other
hand, if for some $x\in\mathbb{S}^{n-1}$ we have
$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=n-1$, then the orbit
$H(x)\subseteq\mathbb{S}^{n-1}$, as a submanifold of dimension $n-1$, is open
in $\mathbb{S}^{n-1}$. To show that the $H$-action is transitive
(equivalently, $H(x)=\mathbb{S}^{n-1}$), it remains to show that $H(x)$ is
also closed. This is because the $H$-action is proper for any closed
$H\leqslant\mathrm{SO}(n)$, so its orbit $H(x)$ is closed in
$\mathbb{S}^{n-1}$, by Lemma 17. Therefore, since $\mathbb{S}^{n-1}$ is
connected, we conclude that $H(x)=\mathbb{S}^{n-1}$ if
$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=n-1$. ∎

Following Lemma 2 and Lemma 6, the system in (1) is controllable if
$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=n-1$ for some
$x\in\mathbb{S}^{n-1}$, where $\mathfrak{h}=\mathrm{Lie}\,\\{B_{i}\\}$.
Conversely, we learn from Lemma 4 that the rank condition is also sufficient.
Combined with Lemma 2 and 6, we conclude that, since
$\pi_{1}(\mathbb{S}^{n-1})=\\{0\\}$ for $n\geqslant{}3$, the system in (1) is
controllable if and only if $\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=n-1$
for some $x\in\mathbb{S}^{n-1}$, where
$\mathfrak{h}=\mathrm{Lie}\,\\{B_{i}\\}$. When $n=2$, since the unit circle
$\mathbb{S}^{1}$ is one-dimensional, controllability naturally guarantees the
rank condition. In summary, we have the following theorem for controllability
of the system in (1).

######  Theorem 7.

Let $\mathfrak{h}:=\mathrm{Lie}\,\\{B_{0},\ldots,B_{m}\\}$ be a Lie subalgebra
of $\mathfrak{so}(n)$ and $H\leqslant{}\mathrm{SO}(n)$ be a closed Lie
subgroup whose Lie algebra equals to $\mathfrak{h}$. The following statements
are equivalent:

  1. (1)

the system in (1) is controllable on $\mathbb{S}^{n-1}$;

  2. (2)

$\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=n-1$ for some
$x\in\mathbb{S}^{n-1}$;

  3. (3)

$H$ acts transitively on $\mathbb{S}^{n-1}$.

######  Example 1.

Let us consider the Bloch system, which is a bilinear system of the form,

$\dot{x}(t)=\bigl{(}\omega_{0}\Omega_{z}+u(t)\Omega_{y}+v(t)\Omega_{z}\bigr{)}x(t),\quad
x(0)=x_{0},$ (7)

where $x(t)$ denotes the bulk magnetic moment of the spin ensemble on the
2-dimensional sphere $\mathbb{S}^{2}$, $\omega_{0}$ is the Larmor frequency,
$u(t)$ and $v(t)$ are the external radio-frequency fields (controls) applied
on the $y$ and $z$ directions, respectively, and

$\Omega_{x}=\pNiceMatrix 0&00\\\ 00-1\\\ 010,\ \Omega_{y}=\pNiceMatrix 0&01\\\
000\\\ -100,\ \Omega_{z}=\pNiceMatrix 0&-10\\\ 100\\\ 000$

in $\mathfrak{so}(3)$ are the generators of rotation around the $x$-, $y$-,
and $z$-axis, respectively. From our earlier discussion, (7) is induced by the
Bloch system defined on $\mathrm{SO}(3)$,

$\dot{X}(t)=\bigl{(}\omega_{0}\Omega_{z}+u(t)\Omega_{y}+v(t)\Omega_{z}\bigr{)}X(t),\quad
X(0)=I.$

More generally, we can consider the following bilinear system

$\dot{x}(t)=\Bigl{(}\Omega_{i_{0}j_{0}}+\sum_{k=1}^{m}u_{k}(t)\Omega_{i_{k}j_{k}}\Bigr{)}x(t),\quad{}x(0)\in\mathbb{S}^{n-1},$
(8)

where $\Omega_{ij}=E_{ij}-E_{ji}$ is an anti-symmetric matrix belonging to the
standard basis of $\mathrm{SO}(n)$. It is induced by

$\dot{X}(t)=\Bigl{(}\Omega_{i_{0}j_{0}}+\sum_{k=1}^{m}u_{k}(t)\Omega_{i_{k}j_{k}}\Bigr{)}X(t),\quad{}X(0)\in\mathrm{SO}(n),$
(9)

on $\mathrm{SO}(n)$. It is proved in [13, 14] that the bilinear systems in (9)
is controllable on $\mathrm{SO}(n)$ if and only if the associated graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ is connected, where
$\mathcal{V}=\\{v_{1},\ldots,v_{n}\\}$ and
$\mathcal{E}=\\{v_{i_{0}}v_{j_{0}},\ldots,v_{i_{m}}v_{j_{m}}\\}$. Next, we
will show that the controllability of (8) and (9) coincide, so graph
connectivity criterion also applies to (8).

######  Proposition 8.

An induced system in (8) is controllable on $\mathbb{S}^{n-1}$ if and only if
$\mathcal{G}$ is a connected graph.

###### Proof.

The part of sufficiency is clear, since the connectivity of $\mathcal{G}$
ensures controllability of the bilinear system on $\mathrm{SO}(n)$, so by
Lemma 2, the induced system in (8) is also controllable. On the other hand,
without loss of generality, we may assume that the vertex $v_{n}$ is _not_
contained in $\mathcal{G}$, which means $\Omega_{jn}\not\in\mathfrak{g}$ for
any $j=1,\ldots,n-1$, where $\mathfrak{g}\leqslant{}\mathfrak{so}(n)$ is the
Lie subalgebra generated by
$\\{\Omega_{i_{0}j_{0}},\Omega_{i_{1}j_{1}},\ldots,\Omega_{i_{m}j_{m}}\\}$.
Therefore, each group element in $G=\langle\exp\mathfrak{g}\rangle$ has the
form $\pNiceMatrix[small]A&\\\ 1$ with $A$ being a matrix in
$\mathrm{SO}(n-1)$, which implies that the $G$-action fixes the point
$x_{n}=(0,\ldots,1)^{\intercal}\in\mathbb{S}^{n-1}$, and thus is _not_
transitive. So by the necessity condition in Theorem 7, system in (8) is not
controllable if the graph $\mathcal{G}$ is not connected. ∎

So far we have proved a rank condition which is both necessary and sufficient
for the controllability of systems induced by $\mathrm{SO}(n)$-actions, so
that the Lie algebra $\mathfrak{L}$ of drifting and control vector fields of a
_controllable_ system in (1) is of _constant full rank_. Next, we turn our
focus to induced systems that are not controllable, and describe their
controllable submanifolds.

######  Example 2.

Let us revisit the bilinear system we introduced at the beginning of Section
II evolving on $\mathbb{S}^{3}$ which is induced by the
$\mathrm{SO}(4)$-action with $m=2$, $\lVert x_{0}\rVert=1$, where

$B_{0}=0,\ B_{1}=\pNiceMatrix 0&\\\ 01\\\ -10\\\ 0\\\ ,\ B_{2}=\pNiceMatrix
0&\\\ 0\\\ 01\\\ -10\\\ .$

Using Proposition 8, we find that the system is _not_ controllable, because
the associated graph $\mathcal{G}$ is not connected.

We have demonstrated that the Lie algebra
$\mathfrak{L}\subset\mathfrak{X}(\mathbb{S}^{3})$ generated by vector fields
$\\{B_{1}x,B_{2}x\\}$ is not of constant rank:
$\operatorname{\mathrm{rank}}_{x_{1}}\mathfrak{g}=0$ for
$x_{1}=(1,0,0,0)^{\intercal}$, and
$\operatorname{\mathrm{rank}}_{x_{2}}\mathfrak{g}=\operatorname{\mathrm{rank}}_{x_{3}}=2$
for $x_{2}=(0,1,0,0)^{\intercal}$ and $x_{3}=(0,0,1,0)^{\intercal}$. To see
how the rank of the algebra $\mathfrak{L}$ changes, from the perspective of
group action, we notice that $x_{1}=(1,0,0,0)^{\intercal}$ and
$x_{2}=(0,1,0,0)^{\intercal}$ belong to different orbits. To be more specific,
the controllable submanifold of the corresponding bilinear system

$\dot{X}(t)=\bigl{(}u_{1}(t)B_{1}+u_{2}(t)B_{2}\bigr{)}X,\quad X(0)=I$

on $\mathrm{SO}(4)$ is the closed Lie subgroup $H<\mathrm{SO}(4)$, which is
generated by the Lie subalgebra
$\mathfrak{h}:=\mathrm{Lie}\,\\{B_{0},B_{1},B_{2}\\}$. $H$ consists of all
matrices of the form $\begin{pmatrix}1&\\\ &A\end{pmatrix}$, where
$A\in\mathrm{SO}(3)$ is a $3$-by-$3$ matrix. Therefore,
$x_{2}=(0,1,0,0)^{\intercal}$ and $x_{3}=(0,0,1,0)^{\intercal}$ belong to the
same orbit of $H$, so that the rank of $\mathfrak{L}$ on both points coincide
(see Lemma 9 below); while $x_{1}=(1,0,0,0)^{\intercal}$ is in a different
orbit.

The above observation motivates us to examine how rank of a Lie subalgebra
varies on a manifold, which lays the foundation for the study of controllable
submanifolds. In fact, the following lemma asserts that the rank of
$\mathfrak{L}$ is _constant_ over an orbit of $H$.

######  Lemma 9.

For a subalgbra
$\mathfrak{h}:=\mathrm{Lie}\,\\{B_{i}\\}\leqslant\mathfrak{so}(n)$ and let
$H\leqslant{}\mathrm{SO}(n)$ be a closed Lie subgroup corresponding to
$\mathfrak{h}$. Given $x\in\mathbb{S}^{n-1}$, the rank of $\mathfrak{h}$ is
constant over the orbit $H(x)$, i.e.,
$\operatorname{\mathrm{rank}}_{y}\mathfrak{h}=\dim{}H(x)$ for all
$y\in{}H(x)$. Consequently, the rank of
$\mathfrak{L}=\mathrm{Lie}\,\\{B_{i}x\\}$ is _constant_ on $H(x)$.

###### Proof.

We know from Lemma 17 that the orbit $H(x)$ is a closed, embedded submanifold
of $\mathbb{S}^{n-1}$, and that for any $y\in{}H(x)$,

$\mathsf{T}_{y}H(x)=\\{Ay:A\in\mathfrak{h}\\}.$ (10)

Hence we have $\operatorname{\mathrm{rank}}_{y}\mathfrak{h}=\dim{}H(x)$ for
all $y\in{}H(x)$. As a consequence, since the rank of $\mathfrak{L}$ at
$y\in{}H(x)$ equals to $\operatorname{\mathrm{rank}}_{y}\mathfrak{h}$,
$\mathfrak{L}$ is of constant rank over any given orbit $H(x)$. ∎

From Lemma 9, we can draw a clear link between controllable submanifolds and
group orbits. More specifically, in the next theorem we prove that the
controllable submanifold of system (1) with a given initial condition
$x(0)=x_{0}$ is a group orbit of $x_{0}$.

######  Theorem 10.

Let $\mathfrak{h}$ and $H$ be the same as in Lemma 9. For an induced bilinear
system in (1) with initial condition $x(0)=x_{0}\in\mathbb{S}^{n-1}$, its
controllable submanifold is the orbit $H(x_{0})$.

###### Proof.

By (5) and Lemma 17, the system in (1) evolves on the orbit $H(x_{0})$, so its
attainable set is a subset of $H(x_{0})$. On the other hand, since $H$ acts
transitively on the orbit $H(x_{0})$ by definition, Lemma 2 guarantees that
the system in (1) is controllable on $H(x_{0})$. Therefore, we conclude that
the controllable submanifold of the system in (5) is the orbit $H(x_{0})$. ∎

######  Remark 1.

As a consequence of Theorem 10, we remark that the controllable submanifolds
of induced systems in the form of (1) can be classified by closed subgroups of
$\mathfrak{so}(n)$ and their orbits. To be more specific, suppose
$G\leqslant\mathrm{SO}(n)$ is a closed subgroup,
$\mathfrak{g}=\mathsf{T}_{e}G$ is the Lie subalgebra of $\mathfrak{so}(n)$
corresponding to $G$ and let $\\{A_{1},\ldots,A_{m}\\}$ be a (finite) set of
generators of $\mathfrak{g}$, then the orbit $G(y_{0})$ is the controllable
submanifold of the following system

$\dot{x}(t)=\Bigl{(}\sum_{i=1}^{m}u_{i}(t)A_{i}\Bigr{)}x(t),\quad{}x(0)=y_{0}.$

In summary, in this section, we examine the bilinear systems induced by
$\mathrm{SO}(n)$ group actions, and show that the rank of its underlying Lie
algebra $\mathfrak{L}$ is constant over its controllable submanifold.
Therefore, such a bilinear system is controllable if the rank of
$\mathfrak{L}$ is maximal at any point; and if it is not controllable, the
controllable submanifold is an orbit of the group action.

##  IV Systems Induced by Proper Lie Group Actions

Following the discussions in previous sections on systems induced by the
natural $\mathrm{SO}(n)$-action, in this section, we generalize Theorem 7 and
Theorem 10, and prove that the previous results still hold for systems induced
by _proper_ Lie group actions.

Let $G$ be a (connected) matrix group acting _properly_ on $\mathbb{R}^{n}$,
$\mathfrak{g}$ the Lie algebra of $G$, and
$\mathcal{H}\subseteq\mathbb{R}^{n}$ a homogeneous $G$-space. For an induced
bilinear system in the form of

$\dot{x}(t)=\Bigl{(}\sum_{i=1}^{m}u_{i}(t)B_{i}\Bigr{)}x(t),\quad{}x(0)=x_{0}\in\mathcal{H},$
(11)

where $B_{1},\ldots,B_{m}\in\mathfrak{g}$, we have the following theorem
concerning the controllability of system (11) and its controllable
submanifolds.

######  Theorem 11.

Let $\mathfrak{h}=\mathrm{Lie}\,\\{B_{1},\ldots,B_{m}\\}$ be a Lie subalgebra
of $\mathfrak{g}$ generated by matrices $B_{i}$ in (11), and let
$H\leqslant{}G$ be a closed Lie subgroup of $G$ corresponding to
$\mathfrak{h}$. Suppose either (i) $H$ acts transitively on $\mathcal{H}$, or
(ii) $\operatorname{\mathrm{rank}}_{x}\mathfrak{h}=\dim\mathcal{H}$ for some
$x\in\mathcal{H}$, then (iii) the system (11) is controllable. Additionally,
if the fundamental group $\pi_{1}(\mathcal{H})$ has no elements of infinite
order, then conditions (i), (ii) and (iii) are equivalent. Furthermore, in
case that system (11) is not controllable, its controllable submanifold is the
orbit $H(x_{0})$.

###### Proof.

$\mathrm{(i)}\Rightarrow\mathrm{(iii)}$ comes directly from Lemma 2. Note that
$\mathcal{H}$ is connected since $H$ is connected, one can show
$\mathrm{(i)}\Leftrightarrow\mathrm{(ii)}$ by an almost identical argument in
the proof of Lemma 6. In the case that $\pi_{1}(\mathcal{H})$ has no element
of infinite order, one can apply Lemma 3 to show that
$\mathrm{(iii)}\Rightarrow\mathrm{(ii)}$, since the homogeneous space
$\mathcal{H}$ is naturally analytic.

Moreover, in case that system (11) is non-controllable, Lemma 17 shows that
the rank of $\mathfrak{h}$ is constant over the orbit $H(x_{0})$, and that
vector fields $\\{B_{i}x\\}$ are tangent to $H(x_{0})$. Therefore,
transitivity gives that $H(x_{0})$ is the embedded controllable submanifold in
$\mathcal{H}$ of system (11). ∎

######  Remark 2.

It is clear that Theorem 11 applies to bilinear systems with drifting terms in
the form of

$\dot{x}(t)=\Bigl{(}B_{0}+\sum_{i=1}^{m}u_{i}(t)B_{i}\Bigr{)}x(t),\quad{}x(0)=x_{0}\in\mathcal{H}$

if $G$ is compact, or if $\dot{X}(t)=B_{0}X(t)$, $X(0)=I$ has a periodic
solution on $G$.

Since all actions by compact groups are proper, Theorem 11 applies to all
systems induced by actions of compact Lie groups. Next, as an application of
Theorem 11 for non-compact groups, we show a rank condition for systems
induced by $\mathrm{SE}(n)$-actions: consider a bilinear system in the form of

$\dot{x}(t)=\Bigl{(}\sum_{t=1}^{m}u_{i}(t)B_{i}\Bigr{)}x(t),\quad{}x(0)=x_{0}\in\mathbb{R}^{n},$
(12)

where $B_{i}=(A_{i},\mu_{i})\in\mathfrak{se}(n)$ for
$A_{i}\in\mathfrak{so}(n)$, $\mu_{i}\in\mathbb{R}^{n}$, and
$B_{i}x:=A_{i}x+\mu_{i}$. Note that $\mathbb{R}^{n}$ is a homogeneous
$\mathrm{SE}(n)$-space, and that the $\mathrm{SE}(n)$-action on
$\mathbb{R}^{n}$ is proper.

######  Lemma 12.

The group action of $\mathrm{SE}(n)$ on $\mathbb{R}^{n}$ is proper.

###### Proof.

Consider the map
$\alpha:\mathrm{SE}(n)\times{}\mathbb{R}^{n}\to\mathbb{R}^{n}\times{}\mathbb{R}^{n}$
s.t. $\alpha((R,\tau),x)=(x,Rx+\tau)$, where $R\in\mathrm{SO}(n)$,
$\tau\in\mathbb{R}^{n}$, and $(R,\tau)\in\mathrm{SE}(n)$. To show that
$\alpha$ is proper, without loss of generality, we need to show that the pre-
image

$\\{((R,\tau),x)\in\mathrm{SE}(n)\times\mathbb{R}^{n}:\lVert
x\rVert\leqslant{}c,\lVert Rx+\tau\rVert\leqslant{}c\\}$ (13)

is compact, for any constant $c$. Note that $\lVert Rx\rVert=\lVert x\rVert$
as $R\in\mathrm{SO}(n)$, $\lVert Rx+\tau\rVert\leqslant{}c$ implies that
$\lVert\tau\rVert\leqslant{}2c$. Since

$\\{(R,\tau)\in\mathrm{SE}(n):R\in\mathrm{SO}(n),\lVert\tau\rVert\leqslant{}2c\\}$

is a compact subset, the pre-image in (13) is also compact, which finishes our
proof. ∎

Consequently, by Theorem 11, we have the following corollary for the system in
(12):

######  Corollary 13.

Let $\mathfrak{g}=\mathrm{Lie}\,\\{B_{1},\ldots,B_{m}\\}$ be the Lie
subalgebra of $\mathfrak{se}(n)$ generated by $B_{i}$ in (12), and let
$G\leqslant{}\mathrm{SE}(n)$ denote a closed Lie subgroup corresponding to
$\mathfrak{g}$. The following statements are equivalent:

  1. (1)

the system of the form (12) is controllable on $\mathbb{R}^{n}$;

  2. (2)

$\operatorname{\mathrm{rank}}_{x}\mathfrak{g}=n$ for some
$x\in\mathbb{R}^{n}$;

  3. (3)

$G$ acts transitively on $\mathbb{R}^{n}$.

##  V Conclusion

In this note, we study the controllability of bilinear systems induced by
proper Lie group actions. By utilizing Lie group theory, we establish a
connection between the underlying Lie algebra of the induced system and the
orbits of its group action, and prove that the rank of the Lie algebra is
constant on each orbit. Such pattern of the Lie algebra rank enables us to
characterize the controllable submanifolds of induced bilinear systems, and
also provides a relaxed rank condition that is both sufficient and necessary.
This condition also avoids the difficult task of classifying transitive Lie
algebras for a given homogeneous space, which is required in most of the
existing works.

###  -A Group Actions, Homogeneous Spaces and Orbits

######  Definition 14 (Group Actions and Homogeneous Spaces).

A Lie group action of $G$ on $M$ is a smooth map

$\theta:G\times{}M\to{}M,\quad(g,m)\mapsto{}g.m$ (14)

such that $h.(g.m)=(hg).m$ for any $h,g\in{}G$ and $m\in{}M$. Given an
$x\in{}M$, the _orbit_ of $x$ is the image of $G\times\\{x\\}$ under the group
action map $\theta$ in (14):

$G(x):=\theta(G\times{}\\{x\\}).$ (15)

Moreover, a $G$-action is called _transitive_ if for any pair of
$x_{1},x_{2}\in{}M$, there is some $g\in{}G$ such that $g.x_{1}=x_{2}$. If $M$
is endowed with a transitive $G$-action, it is called a _homogeneous
$G$-space_.

######  Definition 15.

For a fixed $X\in\mathfrak{g}$ and any given $m\in{}M$, the curve $\exp(tX)$
on $G$ induces a curve $\Phi(t)=\exp(tX).m$ on $M$ by the $G$-action such that
$\Phi(0)=m$. Hence the vector field $X\in\mathfrak{g}$ defines a vector field
$\theta_{\ast}X$ on $M$ by taking the derivative of $\Phi(t)$ at $t=0$: for
each $m\in M$,

$(\theta_{\ast}X)(m):=\frac{\mathrm{d}}{\mathrm{d}t}\Big{|}_{t=0}\exp(tX).m.$
(16)

We call $\theta_{\ast}X$ the _fundamental vector field_ of $X$.

For the establishment of our rank condition for bilinear systems in the form
of (1), there is one type of group actions that is of particular interest to
us:

######  Definition 16 (Proper Actions).

A $G$-action on $M$ is _proper_ if the following group action map

$\begin{array}[]{cccc}\phi:&G\times{}M&\to&M\times{}M\\\
&(g,m)&\mapsto&(m,g.{}m)\end{array}$ (17)

is proper, i.e., pre-images of compact subsets in $M\times{}M$ are compact in
$G\times{}M$. Particularly, if $G$ is compact, all $G$-actions are proper.

One important feature of proper actions is that their orbits are _embedded_
submanifolds, as stated in the next lemma.

######  Lemma 17 (See [15]).

An orbit $\mathcal{O}$ for a proper $G$-action is a closed, embedded
submanifold of $M$, whose tangent space has the form

$\mathsf{T}_{m}\mathcal{O}=\\{\theta_{\ast}X(m):X\in\mathfrak{g}\\},\quad{}\text{for
any }m\in{}\mathcal{O}.$ (18)

###### Proof.

The orbit $\mathcal{O}$ being a closed, embedded submanifold is proved in [15,
Corollary 2.3.33], and its tangent space $\mathsf{T}_{m}\mathcal{O}$ can be
computed using the constant rank theorem. More specifically, consider an
evaluation map $\mathrm{ev}_{m}:G\to{}\mathcal{O}$ such that

$\mathrm{ev}_{m}(g):=g.{}m.$

Note that $\mathrm{ev}_{m}$ is $G$-equivariant, i.e.,
$\mathrm{ev}_{m}(hg)=h.{}\mathrm{ev}_{m}(g)$ for all $h\in{}G$, so it is of
constant rank, say $r$, by the equivariant rank theorem [16]. Therefore, since
$\mathrm{ev}_{m}$ is surjective, at the identity there is a basis
$\\{X_{1},\ldots,X_{l}\\}$ of $\mathfrak{g}=\mathsf{T}_{e}G$ such that
$\\{\mathrm{d}(\mathrm{ev}_{m})(X_{i})\\}_{i=1}^{r}$ forms a basis of
$\mathsf{T}_{m}\mathcal{O}$ and that $\mathrm{d}(\mathrm{ev}_{m})(X_{j})=0$
for $j=r+1,\ldots,l$. Since

$\displaystyle\mathrm{d}(\mathrm{ev}_{m})(X)$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}\Big{|}_{t=0}\mathrm{ev}_{m}(\exp{}tX)$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}\Big{|}_{t=0}(\exp{}tX).{}m=\theta_{\ast}(X)(m)$

for any $X\in\mathfrak{g}$, we conclude that

$\displaystyle\mathsf{T}_{m}\mathcal{O}$
$\displaystyle=\mathrm{span}\,\\{\mathrm{d}(\mathrm{ev}_{m})(X_{i})\\}_{i=1}^{r}$
$\displaystyle=\mathrm{span}\,\\{\mathrm{d}(\mathrm{ev}_{m})(X_{i})\\}_{i=1}^{l}$
$\displaystyle=\mathrm{span}\,\\{\theta_{\ast}(X_{i})(m)\\}$
$\displaystyle=\\{\theta_{\ast}(X)(m):X\in\mathfrak{g}\\}.\qed$

###  -B Lie Algebra Rank Condition

Consider a right-invariant bilinear system defined on a compact, connected Lie
group $G$ in the form of

$\dot{X}(t)=B_{0}X(t)+\Bigl{(}\sum_{i=1}^{m}u_{i}(t)B_{i}\Bigr{)}X(t),\quad{}X(0)=I,$
(19)

where $X(t)\in G$ is the state, $I$ is the identity element of $G$, $B_{0}$,
…, $B_{m}$ are elements in the Lie algebra $\mathfrak{g}$ of $G$, and
$u_{i}(t)\in\mathbb{R}$ are piecewise constant control inputs. Let
$\Gamma=\\{B_{0},\dots,B_{m}\\}$ be the set of the drift and control vector
fields of the system in (19) evaluated at the identity element $I$, then we
use $\mathrm{Lie}\,(\Gamma)$ to denote the Lie subalgebra of $\mathfrak{g}$
generated by $\Gamma$, which is the smallest vector subspace of $\mathfrak{g}$
that contains $\Gamma$ and is closed under the Lie bracket operation, i.e.,
$[C,D]=CD-DC$ for $C,D\in\mathfrak{g}$. The LARC then estabilishes a
connection between the controllability of the systems in the form of (19) and
the Lie algebras generated by the vector fields governing the system dynamics.

######  Theorem 18 (LARC, see [17]).

The system in (19) is _controllable_ on $G$ if and only if
$\mathrm{Lie}\,(\Gamma)=\mathfrak{g}$.

## References

  * [1] S. J. Glaser, T. Schulte-Herbrüggen, M. Sieveking, O. Schedletzky, N. C. Nielsen, O. W. Sørensen, and C. Griesinger, “Unitary control in quantum ensembles: Maximizing signal intensity in coherent spectroscopy,” _Science_ , vol. 280, no. 5362, pp. 421–424, 1998.
  * [2] J.-S. Li and N. Khaneja, “Control of inhomogeneous quantum ensembles,” _Phys. Rev. A_ , vol. 73, p. 030302, Mar 2006.
  * [3] J.-S. Li, J. Ruths, T.-Y. Yu, H. Arthanari, and G. Wagner, “Optimal pulse design in quantum control: A unified computational method,” _Proceedings of the National Academy of Sciences_ , vol. 108, no. 5, pp. 1879–1884, 2011.
  * [4] W. Gerstner, _Spiking Neuron Models: Single Neurons, Populations, Plasticity_. Cambridge University Press, 2002.
  * [5] P. Dayan and L. F. Abbott, _Theoretical Neuroscience: Computational and Mathematical Modeling of Neural Systems_ , revised ed., ser. Computational Neuroscience Series. The MIT Press, September 2005.
  * [6] Y. L. Sachkov, “Control theory on Lie groups,” _Journal of Mathematical Sciences_ , vol. 156, no. 3, pp. 381–439, 2009.
  * [7] R. Brockett, “Lie Theory and Control Systems Defined on Spheres,” _SIAM Journal on Applied Mathematics_ , vol. 25, no. 2, pp. 213–225, 1973\.
  * [8] W. Boothby and E. Wilson, “Determination of the transitivity of bilinear systems,” _SIAM Journal on Control and Optimization_ , vol. 17, no. 2, pp. 212–221, 1979.
  * [9] W. M. Boothby, “A transitivity problem from control theory,” _Journal of Differential Equations_ , vol. 17, no. 2, pp. 296 – 307, 1975.
  * [10] D. Montgomery and H. Samelson, “Transformation groups of spheres,” _Annals of Mathematics_ , vol. 44, no. 3, pp. 454–470, 1943.
  * [11] D. L. Elliott, _Bilinear Control Systems: Matrices in Action_ , ser. Applied Mathematical Sciences. Springer Netherlands, 2009, vol. 169.
  * [12] ——, “A consequence of controllability,” _Journal of Differential Equations_ , vol. 10, no. 2, pp. 364 – 370, 1971.
  * [13] G. Cheng, W. Zhang, and J.-S. Li, “Combinatorics-Based Approaches to Controllability Characterization for Bilinear Systems,” _SIAM Journal on Control and Optimization_ , vol. 59, no. 5, pp. 3574–3599, 2021.
  * [14] W. Zhang and J. Li, “Analyzing controllability of bilinear systems on symmetric groups: Mapping Lie brackets to permutations,” _IEEE Transactions on Automatic Control_ , 2019.
  * [15] J.-P. Ortega and T. S. Ratiu, _Momentum maps and Hamiltonian reduction_ , ser. Progress in Mathematics. Birkhäuser Boston, Inc., Boston, MA, 2004, vol. 222.
  * [16] J. M. Lee, _Introduction to smooth manifolds_ , 2nd ed., ser. Graduate Texts in Mathematics. Springer, New York, 2013, vol. 218.
  * [17] R. Brockett, “System theory on group manifolds and coset spaces,” _SIAM Journal on Control_ , vol. 10, no. 2, pp. 265–284, 1972.


Critical properties of a 2D frustrated magnet with non-magnetic impurities  D.
N. Yasinskaya∗1, V. A. Ulitko1, Yu. D. Panov1 1Ural Federal University 620002,
19 Mira Street, Ekaterinburg, Russia<EMAIL_ADDRESS>
We report on classical Monte Carlo study of phase transitions and critical
behavior of a 2D spin-pseudospin model describing a dilute magnet with
competing charge and spin interactions. The static critical exponents of the
specific heat and correlation length are calculated using the finite-size
scaling theory in a wide range of model parameters. The order of phase
transitions is analyzed within the energy histogram method. It is found that
approaching the frustration point and increasing the density of non-magnetic
impurities leads to non-universal critical behavior and first-order phase
transitions. Features of non-universal critical behavior are shown to depend
on the relationship between the parameters of the spin and pseudospin
interactions.

Keywords: critical properties, frustration, magnetic, nonmagnetic impurities,
phase transitions, pseudospin

##  1 Introduction

The study of phase transitions (PT) and critical phenomena in spin systems is
of great importance for modern condensed matter physics. In particular,
frustrated and diluted magnetic systems are a subject of increased attention.
Frustration causes a variety of unstable phase states, significant and highly
unpredictable changes in the critical, thermodynamic and magnetic properties
[1, 2, 3]. In addition, magnetic systems with frustrations cover a wide range
of objects with special magnetic states, such as spin liquid, spin glass [4]
and spin ice [5]. The study of dilute magnets is significant not only from a
theoretical, but also from a practical point of view, since it expands the
understanding of behavior and properties of real materials, which, as a rule,
have defects and impurities. Moreover, disorder caused by doping impurities
and defects significantly affects the critical behavior and phase states of
magnetic systems [6, 7, 8].

The focus of theoretical research aims to study more realistic complex models.
The study of phase transitions and critical phenomena in such systems by
methods of theoretical physics is a rather difficult problem. Therefore,
complex systems are intensively investigated by numerical-simulation methods
such as Monte Carlo methods. For example, Monte Carlo methods have been used
to study magnetic multilayers [9, 10, 11], Kekulene structures [12, 13],
decorated lattices [14, 15] and many other various systems.

One of the most effective methods for studying complex magnetic systems with
different degrees of freedom is the pseudospin formalism. Pseudospin models
are widely used for describing the properties of binary alloys, classical and
quantum liquids, dilute magnets, superconductors, and many other physical
systems [16, 17]. Here in the paper, we consider the spin-pseudospin model to
explore the site-dilute 2D magnet with frustration. The frustration is caused
by competitive charge (pseudospin-1) and magnetic (spin-1/2) orders. On the
one hand, this model generalizes the frustrated mixed-spin Ising model with
nonmagnetic impurities. On the other hand, this model was initially proposed
[18] to consider this competition of different orders in underdoped
high-$T_{c}$ cuprates like La2-xSrxCuO4 in the normal state. The properties of
the spin-pseudospin model in the ground state were studied within the mean-
field approximation [18], the temperature phase diagrams were obtained within
the Bethe approximation [19]. It was shown that the ground state phase
diagrams and thermodynamic properties of the system are different for the
cases of weak and strong spin exchange interactions. Complex effect of non-
magnetic impurities and frustration on features of the phase states formation
in the weak exchange limit was studied in the work [20]. The critical behavior
of the model was considered only in the strong spin exchange limit [21]. In
this work, we present the Monte Carlo study of critical properties of an
anisotropic dilute magnet with competition between charge and magnetic orders
in a wide range of model parameters.

##  2 Model and methods

In the framework of the spin-pseudospin model [22] we consider the CuO2 planes
as a charge triplets system consisting of three many-electron mixed-valence
centers [CuO4]7-,6-,5- (nominally corresponding to the copper ion states
Cu1+,2+,3+). Two non-magnetic states Cu1+,3+ are associated with two
pseudospin projections $S_{z}=\pm 1$. The Cu2+ state is associated with the
$S_{z}=0$ projection of pseudospin and has a conventional spin $s=1/2$. The
Hamiltonian includes on-site density-density correlations in the form of
single-ion pseudospin anisotropy ($\Delta$), inter-site density-density
correlations in the form of pseudospin exchange interaction of Ising type
($V$), and Ising spin $s=1/2$ exchange coupling ($J$):

$\mathcal{H}=\Delta\sum_{i}^{\phantom{N}}S_{iz}^{2}+V\sum_{\left\langle
ij\right\rangle}S_{iz}S_{jz}+\tilde{J}\sum_{\left\langle
ij\right\rangle}\sigma_{iz}\sigma_{jz}-\mu\sum_{i}S_{iz},$ (1)

where both $V,J>0$. Here the sum runs over $N=L\times L$ sites of the square
lattice, $\langle ij\rangle$ denotes the nearest neighbors,
$\tilde{J}=Js^{2}$, $\sigma_{iz}=P_{0i}s_{iz}/s$ is a normalized $z$-component
of the spin $s=1/2$, multiplied by the projection operator
$P_{0i}=1-S^{2}_{iz}$, which distinguishes the magnetic Cu2+-state with
$S_{z}=0$. $\mu$ is the chemical potential that is necessary to assume the
constant charge constraint

$n=\frac{1}{N}\sum\limits_{i}S_{iz}=const,$ (2)

where $n$ corresponds to the density of doped charge in the system. Thus, the
system is diluted with nonmagnetic annealed interacting impurities acting as
defects for the spin subsystem.

We used a parallel modification of the classical Monte Carlo (MC) method [23],
which takes into account the condition (2). The temperature dependence of the
specific heat is obtained using the following expression:

$C=\frac{1}{N}\frac{\langle E^{2}\rangle-\langle E\rangle^{2}}{T^{2}},$ (3)

where $E$ is the energy of the system with the Hamiltonian (1). The order
parameter $\mathcal{O}$ for checkerboard antiferromagnetic ($m$) and charge
ordered ($M$) phases is determined as follows:

$\mathcal{O}=\left\\{\begin{array}[]{l}m=m_{1}-m_{2},\\\ M=M_{1}-M_{2}.\\\
\end{array}\right.\\\ $ (4)

Here $m_{\lambda}=\sum\limits_{i\in\lambda}s_{iz}$ – magnetization of the
$\lambda$ sublattice, $M_{\lambda}=\sum\limits_{i\in\lambda}S_{iz}$ – total
charge of the $\lambda$ sublattice (pseudo-magnetization), $\lambda=1,2$
denotes the checkerboard sublattice.

The Binder cumulant method [24] is used for accurate determination of PT
temperatures. The temperature dependencies of cumulants

$U_{L}=1-\frac{\langle\mathcal{O}^{4}\rangle_{L}}{3\langle\mathcal{O}^{2}\rangle^{2}_{L}}$
(5)

for systems with different sizes $L$ intersect in the critical point $T_{c}$.

The critical exponents of the specific heat $\alpha$ and correlation length
$\nu$ are calculated in the framework of the finite-size scaling theory. For
sufficiently large $L$ one can write [25]

$C(T=T_{c},L)\sim L^{\alpha/\nu},$ (6) $V_{n}(T=T_{c},L)\sim L^{1/\nu},$ (7)

where $V_{n}$ is the logarithmic derivative of the order parameter
$\mathcal{O}^{n}$:

$V_{n}=\frac{\langle\mathcal{O}^{n}E\rangle}{\langle\mathcal{O}^{n}\rangle}-\langle
E\rangle.$ (8)

For the 2D Ising model regime of the critical behavior, the scaling relation
for the specific heat will be the logarithmic one:

$C(T=T_{c},L)\sim\ln L.$ (9)

In this case, we assume $\alpha=0$ [6]. Calculation of critical exponents was
performed for the system with periodic boundary conditions, $L=32$-$64$, and
the total number of MC steps was $22\cdot 10^{6}$. All calculations were
performed simultaneously for $10^{2}$ copies of the system in order to improve
the accuracy of the results.

To determine the order of PT, we performed a precise analysis of energy
histograms [25]. Energy histograms were plotted for $L=128$. Data binning was
performed by dividing $2\cdot 10^{6}$ MC steps into a thousand of intervals.

##  3 Monte Carlo results

Fig. 1 shows the dependencies of specific heat $C$ on lattice linear sizes $L$
for $V/\tilde{J}=0.4$, $n=0$ and two different values of $\Delta/J$. For
$\Delta/J=0$, the specific heat behaves according to the logarithmic law (9),
which yields $\alpha=0\pm 0.004$. For $\Delta/J=-0.295$, the specific heat is
scaled according to the power law (6), which corresponds to
$\alpha/\nu=1.174\pm 0.018$.

Figure 1: Dependencies of specific heat $C$ at the critical point $T_{c}$ on
lattice sizes $L$ for $V/\tilde{J}=0.4$, $n=0$. Logarithmic scaling relation
for $\Delta/J=0$ yields $\alpha=0\pm 0.004$, power relation for
$\Delta/J=-0.295$ yields $\alpha/\nu=1.174\pm 0.018$ Figure 2: Histograms for
$V/\tilde{J}=0.2$, $n=0$, $L=128$. For $\Delta/J=-0.37$ (left), the two-peak
histogram provides a first-order phase transition. One-peak Gaussian histogram
for $\Delta/J=-0.35$ (right) indicates a second-order phase transition

It is known that the order of PT can change in many frustrated systems [1, 3].
Fig. 2 exhibits histograms of the energy distribution for $V/\tilde{J}=0.2$,
$n=0$ and two different values of $\Delta/J$. The histograms are plotted near
the critical temperature. For $\Delta/J=-0.37$ at $T=0.1505$, the histogram
has a double-peak feature, which indicates a first-order PT. For
$\Delta/J=-0.35$ at $T=0.1748$, the histogram has only one maximum. This was
interpreted as evidence for a second-order PT.

To explore the effects of frustration and non-magnetic impurities on the
critical properties of our system, we obtained the dependencies of critical
temperatures $T_{c}$, critical exponents of the specific heat $\alpha$ and
correlation length $\nu$ on ‘‘single-ion anisotropy’’ $\Delta/J$ and charge
density $n$ for different relationships between parameters of pseudospin and
spin interactions $V/\tilde{J}$. We present these dependencies on $\Delta/J$
for $V/\tilde{J}=0.2$, $n=0$ in Fig 3a. The frustration point is denoted by
$\Delta^{*}$. Ground-state configurations are given by antiferromagnetic (AFM)
order for $\Delta/J>\Delta^{*}$ and charge order (CO) for
$\Delta/J<\Delta^{*}$. It can be seen that exponents take the values of 2D
Ising universality class ($\nu_{Ising}=1$, $\alpha_{Ising}=0$, marked with
black stars) for $|\Delta/J|\gg\Delta^{*}$. The area where the phase
transition belongs to the 2D Ising universality class is marked by dark gray.
The exponents vary monotonically as $\Delta/J$ decreases to $\Delta^{*}$, i.e.
the critical behavior near the frustration point $\Delta^{*}$ becomes non-
universal. This area is marked by light gray. A first-order phase transition
occurs in the area marked by white, and the critical exponents are not
calculated.

(a)

(b)

Figure 3: Dependencies of critical temperature $T_{c}/J$, critical exponents
$\alpha$ and $\nu$ on ‘‘single-ion anisotropy’’ parameter $\Delta/J$ for (a)
$V/\tilde{J}=0.2$, $n=0$; (b) $V/\tilde{J}=1.2$, $n=0$

(a)

(b)

Figure 4: Dependencies of critical temperature $T_{c}/J$, critical exponents
$\alpha$ and $\nu$ on (a) ‘‘single-ion anisotropy’’ parameter $\Delta/J$ for
$V/\tilde{J}=4.0$, $n=0$; (b) charge density $n$ for $V/\tilde{J}=0.4$,
$\Delta/J=0$ ($T_{c}/J$ is not shown)

Figures 3b–3b are designed in a similar way. They show the dependencies of the
critical temperature $T_{c}$ and critical exponents $\alpha$ and $\nu$ on
$\Delta/J$ for $n=0$, $V/\tilde{J}=1.2$ (Fig. 3b) and $V/\tilde{J}=4$ (Fig.
3a). The presented data allow us to conclude again that the model belongs to
the 2D Ising universality class far from the frustration point, and
nonuniversal critical behavior and first-order PT are observed near the
frustration point. The difference appears when approaching the boundary
between strong and weak spin exchange $V/\tilde{J}=1$. Firstly, the region
with first-order PT decreases, and secondly, the exponent of the specific heat
$\alpha$ begins to decrease rather than increase. For $V/\tilde{J}<1$ non-
universal critical behavior and first-order PT appeared for the transition to
the AFM state. For $V/\tilde{J}>1$ this occurs for the transition to the CO
state. Since the area of non-universality is adjacent to the area with first-
order PT, there is a possibility that evidence of the first or second-order PT
occurs only in a certain scale of the system. For example, the instability of
a first-order signature in energy histograms was found in [3], which examines
the Ising model with competing interactions and also shows non-universal
critical behavior and area with first-order phase transitions. Therefore,
frustrated systems require extremely careful and accurate analysis of critical
behavior.

In addition, we studied the influence of charged impurities on the critical
behavior for various $V/\tilde{J}$. Fig. 3b shows the dependence of $\alpha$
and $\nu$ ($T_{c}/J$ is not shown) on density of charged impurities $n$ for
$V/\tilde{J}=0.4$, $\Delta/J=0$. For small $n$, the exponents take the Ising
values. However, as the density increases, the critical exponents begin to
depend on $n$, which also indicates the non-universal critical behavior. This
result coincides with those for other ratios $V/\tilde{J}$ and for the
transition to the CO state. A possible explanation is that the presence of
interacting impurities leads to the dissipation of critical fluctuations
responsible for phase transitions. This phenomenon is consistent, for example,
with Dotsenko’s results for the 2D Ising model with random bonds [7]. It is
important to note that non-magnetic impurities do not change the order of PT.

##  4 Conclusion

We explored the critical properties of the spin-pseudospin model, which
describes a 2D Ising magnet with non-magnetic impurities and competing charge
and spin interactions. We performed extensive Monte-Carlo simulations to
calculate the critical exponents of the specific heat $\alpha$ and correlation
length $\nu$ in the framework of the finite-size scaling theory. The
calculations were performed for a wide range of model parameters, such as
‘‘single-ion anisotropy’’ $\Delta/J$ (local density-density correlation
parameter), density of nonmagnetic impurities $n$, and the relationship
between between pseudospin and spin exchange interactions $V/\tilde{J}$.
Energy histogram method enabled us to determine the order of phase
transitions.

The 2D Ising universality class is revealed to remain far from the frustration
point and at low densities of non-magnetic impurities. We found that
frustration and non-magnetic impurities lead to non-universal critical
behavior. Moreover, first-order phase transitions are observed near the
frustration point. The features of the non-universal critical behavior, as
well as the width of the area with first-order phase transitions, depend on
the relationship between the spin and pseudospin interactions.

## Acknowledgment

This work was supported in part by Competitiveness Enhancement Program of the
Ural Federal University (Act 211 of the Government of the Russian Federation,
Agreement N. 02.A03.21.0006 and CEP 3.1.1.1-20), and also the Ministry of
Education and Science of the Russian Federation (project FEUZ-2020-0054). We
also would like to thank Alexander Moskvin for fruitful discussions.

## References

  * [1] H. T. Diep, Magnetic Systems with Competing Interactions, World Scientific, Singapore, (1994); Frustrated Spin Systems, World Scientific, Singapore (2004)
  * [2] A. V. Zarubin, F.A. Kassan-Ogly, A.I. Proshkin J. Magn. Magn Mater., 514, 167144 (2020)
  * [3] A. Kalz, A. Honecker, Phys. Rev. B 86, 134410 (2012)
  * [4] L. Balents. Nature 464, 199 (2010)
  * [5] S. T. Bramwell, M. J. P. Gingras. Science 294, 1495 (2001)
  * [6] M. A. Novotny and D. P. Landau, Phys. Rev. B 24, 1468 (1981)
  * [7] Vl. S. Dotsenko and V. S. Dotsenko, Adv. Phys. 32, 129 (1983)
  * [8] A. K. Murtazaev, A. B. Babaev, J. Magn. Magn. Mat 321, 2630 (2009)
  * [9] R. Masrour, A. Jabar, A. Benyoussef, M. Hamedoun, J. Magn. Magn. Mat 401, 695 (2016)
  * [10] R. Masrour, A. Jabar, Appl. Surf. Sci. 432, 78 (2018)
  * [11] S. Belhamra, R. Masrour, A. Jabar, Thin Solid Films 711, 138304 (2020)
  * [12] A. Jabar, R. Masrour, Chem. Phys. Lett. 700, 130 (2018)
  * [13] A. Jabar, R. Masrour, Physica B: Condens. Matter 539, 21 (2018)
  * [14] R. Masrour, A. Jabar, Physica A 539, 122878
  * [15] R. Masrour, A. Jabar, Physica A 538, 122959
  * [16] J. Sivardiere, J. Lajzerowicz, Phys. Rev. A. 11, 2090 (1975); 11, 2101 (1975)
  * [17] S. A. Cannas, D. A. Stariolo, Phys. Rev. E. 99, 042137 (2019)
  * [18] Y. D. Panov, A. S. Moskvin, A. A. Chikov, I. L. Avvakumov, J. Low Temp. Phys. 185, 409 (2016)
  * [19] Y. D. Panov, V. A. Ulitko, K. S. Budrin, A. A. Chikov, A. S. Moskvin, J. Magn. Magn. Mater. 477, 162 (2019)
  * [20] D. N. Yasinskaya, V. A. Ulitko, Y. D. Panov, Phys. Solid State 62, 1713 (2020)
  * [21] D. N. Yasinskaya V. A. Ulitko, A. A. Chikov, Y. D. Panov, Acta Phys. Pol. A. 137(5), 979 (2020)
  * [22] A. S. Moskvin. Phys. Rev. B. 94(7), 075116 (2011)
  * [23] K. S. Budrin, V. A. Ulitko, A. A. Chikov, Y. D. Panov, A. S. Moskvin. Parallel computational technologies (PCT’2018), 22 (2018)
  * [24] K. Binder, D. W. Heermann. Monte Carlo Simulation in Statistical Physics. Berlin, Springer (1992)
  * [25] A. M. Ferrenberg, D. P. Landau. Phys. Rev. B 44(10), 5081 (1991)


# HyHTM: Hyperbolic Geometry based
Hierarchical Topic Models

Simra Shahid Tanay Anand11footnotemark: 1 Nikitha Srikanth11footnotemark: 1
Sumit Bhatia Balaji Krishnamurthy Nikaash Puri
Media and Data Science Research Lab, Adobe, India
{sshahid, tana, srikanth, sumit.bhatia, kbalaji<EMAIL_ADDRESS>Authors
contributed equally to the work.

###### Abstract

Hierarchical Topic Models (HTMs) are useful for discovering topic hierarchies
in a collection of documents. However, traditional HTMs often produce
hierarchies where lower-level topics are unrelated and not specific enough to
their higher-level topics. Additionally, these methods can be computationally
expensive. We present HyHTM \- a Hyperbolic geometry based Hierarchical Topic
Models - that addresses these limitations by incorporating hierarchical
information from hyperbolic geometry to explicitly model hierarchies in topic
models. Experimental results with four baselines show that HyHTM can better
attend to parent-child relationships among topics. HyHTM produces coherent
topic hierarchies that specialise in granularity from generic higher-level
topics to specific lower-level topics. Further, our model is significantly
faster and leaves a much smaller memory footprint than our best-performing
baseline.We have made the source code for our algorithm publicly accessible.
111Our code is released at: https://github.com/simra-shahid/hyhtm

##  1 Introduction

The topic model family of techniques is designed to solve the problem of
discovering human-understandable topics from unstructured corpora
paul2014discovering where a topic can be interpreted as a probability
distribution over words blei2003latent. Hierarchical Topic Models (HTMs), in
addition, organize the discovered topics in a hierarchy, allowing them to be
compared with each other. The topics at higher levels are generic and broad
while the topics lower down in the hierarchy are more specific teh2004sharing.

Figure 1: In figure (a) we see a concept tree in Euclidean spaces. Words such
as space shuttle and satellite, which belong to moderately different super-
concepts such as vehicles and space, respectively, are brought closer together
due to their semantic similarity. This leads to a convergence of their
surrounding words, such as helicopter and solar system, creating a false
distance relationship and a crowding effect in Euclidean spaces. In figure
(b), we see a concept tree in Hyperbolic spaces (Poincaré ball), which
inherently has more space (represented by grey circles) than Euclidean spaces.
The distances here grow exponentially towards the edge of the ball, and the
concepts at deeper levels such as helicopter and solar systems move apart in
these growing spaces and are far from each other. The dashed blue line shows
how the distances in both spaces are calculated.

While significant efforts have been made to develop HTMs blei2003hierarchical;
chirkova2016additive; isonuma2020tree; viegas2020cluhtm, there are still
certain areas of improvement. First, the ordering of topics generated by these
approaches provides little to no information about the granularity of concepts
within the corpus. By granularity, we mean that topics near the root should be
more generic, while topics near the leaves should be more specific. Second,
the lower-level topics must be related to the corresponding higher-level
topics. Finally, some of these approaches such as CluHTM viegas2020cluhtm are
very computationally intensive. We argue that these HTMs have such
shortcomings primarily because they do not explicitly account for the
hierarchy of words between topics.

Most of the existing approaches use document representations that employ word
embeddings from euclidean spaces. These spaces tend to suffer from the
crowding problem which is the tendency to accommodate moderately distant words
close to each other van2008visualizing. There are several notable efforts that
have shown that Euclidean spaces are suboptimal for embedding concepts in
hierarchies such as trees, words, or graph entities chami2019hyperbolic;
chami2020low; guo2022co. In figure 1(a), we show the crowding of concepts in
euclidean spaces. Words such as space shuttle and satellite, which belong to
moderately different concepts such as vehicles and space, respectively, are
brought closer together due to their semantic similarity. This also leads to a
convergence of their surrounding words, such as helicopter and solar system
creating a false distance relationship. As a result of this crowding, topic
models such as CluHTM that use Euclidean word similarities in their
formulation tend to mix words that belong to different topics.

Contrary to this, hyperbolic spaces are naturally equipped to embed
hierarchies with arbitrarily low distortion nickel2017poincare;
tifrea2018poincar; chami2020low. The way distances are computed in these
spaces are similar to tree distances, i.e., children and their parents are
close to each other, but leaf nodes in completely different branches of the
tree are very far apart chami2019hyperbolic. In figure 1(b), we visualise this
intuition on a Poincaré ball representation of hyperbolic geometry (discussed
in detail in Section 3). As a result of this tree-like distance computation,
hyperbolic spaces do not suffer from the crowding effect and words like
helicopter and satellite are far apart in the embedding space.

Inspired by the above intuition and to tackle the shortcomings of traditional
HTMs, we present HyHTM, a Hyperbolic geometry based Hierarchical Topic Model
which uses hyperbolic geometry to create topic hierarchies that better capture
hierarchical relationships in real-world concepts. To achieve this, we propose
a novel method of incorporating semantic hierarchy among words from hyperbolic
spaces and encoding it explicitly into topic models. This encourages the topic
model to attend to parent-child relationships between topics.

Experimental results and qualitative examples show that incorporating
hierarchical information guides the lower-level topics and produces coherent,
specialised, and diverse topic hierarchies (Section LABEL:sect:experiments).
Further, we conduct ablation studies with different variants of our model to
highlight the importance of using hyperbolic embeddings for representing
documents and guiding topic hierarchies (Section LABEL:sect:roleofHyperbolic).
We also compare the scalability of our model with different sizes of datasets
and find that our model is significantly faster and leaves much smaller memory
footprint than our best-performing baseline (Section LABEL:sect:speed). We
also present qualitative results in Section LABEL:sect:quality), where we
observe that HyHTM topic hierarchies are much more related, diverse and
specialised. Finally, we discuss and perform in-depth ablations to show the
role of hyperbolic spaces and importance of every choice we made in our
algorithm (See Section LABEL:sect:roleofHyperbolic).

Figure 2: Comparing our Hyperbolic-based HyHTM model to the Euclidean-based
CluHTM, for selected 20News document labels (comp.graphics, comp.os.ms-
windows.misc), we find that HyHTM is better at discriminating between similar
document labels. CluHTM’s root-level topics are not related to computer
concepts, and it cannot separate these labels at lower levels. HyHTM groups
them in the same root level and separates them into different lower-level
topics, showing the advantage of using hyperbolic embeddings over euclidean
ones to avoid the crowding problem. We show the top words with the highest
probability for the topics.

##  2 Related Work

To the best of our knowledge, HTMs can be classified into three categories,
(I) Bayesian generative model like hLDA blei2003hierarchical, and its variants
paisley2013nested; kim2012modeling; tekumalla2015nested utilize bayesian
methods like Gibbs sampler for inferring latent topic hierarchy. These are not
scalable due to the high computational requirements of posterior inference.
(II) Neural topic models like TSNTM isonuma2020tree and others wang2021layer;
pham2021neural use neural variational inference for faster parameter inference
and some heuristics to learn topic hierarchies but lack the ability to learn
appropriate semantic embeddings for topics. Along with these methods, there
are (III) Non-negative matrix factorization (NMF) based topic models, which
decompose a term-document matrix (like bag-of-words) into low-rank factor
matrices to find latent topics. The hierarchy is learned using some heuristics
HSOC; liu2018topic or regularisation methods chirkova2016additive based on
topics in the previous level.

However, the sparsity of the BoW representation for all these categories leads
to incoherent topics, especially for short texts. To overcome this, some
approaches have resorted to incorporating external knowledge from knowledge
bases (KBs) duan2021topicnet; wang2022knowledge or leveraging word embeddings
meng2020hierarchical. Pre-trained word embeddings are trained on a large
corpus of text data and capture the relationships between words such as
semantic similarities, and concept hierarchies. These are used to guide the
topic hierarchy learning process by providing a semantic structure to the
topics. viegas2020cluhtm utilizes euclidean embeddings for learning the topic
hierarchy. However, tifrea2018poincar; nickel2017poincare; chami2020low;
dai2020apo have shown how the crowding problem in Euclidean spaces makes such
spaces suboptimal for representing word hierarchies. These works show how
Hyperbolic spaces can model more complex relationships better while preserving
structural properties like concept hierarchy between words. Recently,
shihyperminer made an attempt to learn topics in hyperbolic embedding spaces.
Contrary to the HTMs above, this approach adopts a bottom-up training where it
learns topics at each layer individually starting from the bottom, and then
during training leverages a topic-linking approach from duan2021sawtooth, to
link topics across levels. They also have a supervised variant that
incorporates concept hierarchy from KBs.

Our approach uses latent word hierarchies from pretrained hyperbolic
embeddings to learn the hierarchy of topics that are related, diverse,
specialized, and coherent.

##  3 Preliminaries

We will first review the basics of Hyperbolic Geometry and define the terms
used in the remainder of this section. We will then describe the basic
building blocks for our proposed solution, followed by a detailed description
of the underlying algorithm.

###  3.1 Hyperbolic Geometry

Hyperbolic geometry is a non-Euclidean geometry with a constant negative
Gaussian curvature. Hyperbolic geometry does not satisfy the parallel
postulate of Euclidean geometry. Consequently, given a line and a point not on
it, there are at least two lines parallel to it. There are many models of
hyperbolic geometry, and we direct the interested reader to an excellent
exposition of the topic by book-hyperbolic. We base our approach on the
Poincaré ball model, where all the points in the geometry are embedded inside
an $n$-dimensional unit ball equipped with a metric tensor
(nickel2017poincare). Unlike Euclidean geometry, where the distance between
two points is defined as the length of the line segment connecting the two
points, given two points $u\in\mathbb{D}^{n}$ and $v\in\mathbb{D}^{n}$, the
distance between them in the Poincaré model is defined as follows:

$\begin{multlined}d_{P}(u,v)=\operatorname{arcosh}\left(1+2\frac{{\|u-v\|}^{2}}{(1-\|u\|^{2})(1-\|v\|^{2})}\right)\end{multlined}d_{P}(u,v)=\operatorname{arcosh}\left(1+2\frac{{\|u-v\|}^{2}}{(1-\|u\|^{2})(1-\|v\|^{2})}\right)$
(1)

Here, $\operatorname{arcosh}$ is the inverse hyperbolic cosine function, and
$\|.\|$ is the Euclidean norm. Figure 1 has shown an exemplary visualization
of how words get embedded in hyperbolic spaces using the Poincaré ball model.
As illustrated in Figure 1(b), distances in hyperbolic space follow a tree-
like path, and hence they are informally also referred to as tree distances.
As can be observed from the figure, the distances grow exponentially larger as
we move toward the boundary of the Poincaré ball. This alleviates the crowding
problem typical to Euclidean spaces, making hyperbolic spaces a natural choice
for the hierarchical representation of data.

###  3.2 Matrix Factorization for Topic Models

A topic can be defined as a ranked list of strongly associated terms
representative of the documents belonging to that topic. Let us consider a
document corpus $\mathcal{D}$ consisting of $n$ documents
$d_{1},d_{2},\dots,d_{n}$, and let $\mathcal{V}$ be the corpus vocabulary
consisting of $m$ distinct words $w_{1},w_{2},\dots,w_{m}$. The corpus can
also be represented by a document-term matrix
$\textbf{A}\in\mathbb{R}^{n\times m}$ such that $\textbf{A}_{ij}$ represents
the relative importance of word $w_{j}$ in document $d_{i}$ (typically
represented by the TF-IDF weights of $w_{i}$ in $d_{j}$).

A popular way of inferring topics from a given corpus is to factorize the
document-term matrix. Typically, non-negative Matrix Factorization (NMF) is
employed to decompose the document-term matrix, A, into two non-negative
approximate factors: $\textbf{W}\in\mathbb{R}^{n\times\textbf{N}}$ and
$\textbf{H}\in\mathbb{R}^{\textbf{N}\times m}$. Here, N can be interpreted as
the number of underlying topics. The factor matrix W can then be interpreted
as the document-topic matrix, providing the topic memberships for documents,
and H, the topic-term matrix, describes the probability of a term belonging to
a given topic. This basic algorithm can also be applied recursively to obtain
a hierarchy of topics by performing NMF on the set of documents belonging to
each topic produced at a given level to get more fine-grained topics
(chirkova2016additive; viegas2020cluhtm).

##  4 Hierarchical Topic Models Using Hyperbolic Geometry

We now describe HyHTM – our proposed Hyperbolic geometry-based Hierarchical
Topic Model. We first describe how we capture semantic similarity and
hierarchical relationships between terms in hyperbolic space. We then describe
the step-by-step algorithm for utilizing this information to generate a topic
hierarchy.

###  4.1 Learning Document Representations in Hyperbolic Space and Root Level
Topics

As discussed in Section 3.2, the first step in inferring topics from a corpus
using NMF is to compute the document-term matrix A. A typical way to compute
the document-term matrix A is by using the TF-IDF weights of terms in a
document that provides reprsentations of the documents in the term space.
However, usage of TF-IDF (and its variants) results in sparse representations
and ignores the semantic relations between different terms by considering only
the terms explicitly present in a given document. viegas2019cluwords proposed
an alternative formulation for document representations that utilizes pre-
trained word embeddings to enrich the document representations by
incorporating weights for words that are semantically similar to the words
already present in the document. The resulting document representations are
computed as follows.

$\textbf{A}=(\textbf{TF}\times\textbf{M}_{\text{S}})\odot(\mathbf{1}\times\textbf{IDF}^{T})$
(2)

Here, $\odot$ indicates the Hadamard product. A is the $n\times m$ document-
term matrix. TF is the term-frequency matrix such that
$\textbf{TF}_{i,j}=tf(d_{i},w_{j})$ and $\textbf{M}_{\text{S}}$ is the
$m\times m$ term-term similarity matrix that captures the pairwise semantic
relatedness between the terms and is defined as
$\textbf{M}_{\text{s}_{i,j}}=sim(w_{i},w_{j})$, where $sim(w_{i},w_{j})$
represents the similarity between terms $w_{i}$ and $w_{j}$ and can be
computed using typical word representations such as word2vec (w2v) and GloVe
(pennington2014glove). Finally, IDF is the $m\times 1$ inverse-document-
frequency vector representing the corpus-level importance of each term in the
vocabulary. Note that viegas2019cluwords used the following modified variant
of IDF in their formulation, which we also chose in this work.

$\textbf{IDF}(i)=\log\left(\frac{|D|}{\sum_{d\in
D}\mu\left(w_{i},d\right)}\right)$ (3)

Here, $\mu\left(w_{i},d\right)$ is the average of the similarities between
term $w_{i}$ and all the terms $w$ in document $d$ such that
$\textbf{M}_{\text{S}}(w_{i},w)\neq 0$. Thus, unlike traditional IDF
formulation where the denominator is document-frequency of a term, the
denominator in the above formulation captures the semantic contribution of
$w_{i}$ to all the documents.

In our work, we adapt the above formulation to obtain document representations
in Hyperbolic spaces by using Poincaré GloVe embeddings (tifrea2018poincar),
an extension of the traditional Euclidean space GloVe (pennington2014glove) to
hyperbolic spaces. Due to the nature of the Poincaré Ball model, the resulting
embeddings in the hyperbolic space arrange the correspondings words in a
hierarchy such that the sub-concept words are closer to their parent words
than the sub-concept words of other parents.

There is one final missing piece of the puzzle before we can obtain suitable
document representations in hyperbolic space. Recall that due to the nature of
the Poincaré Ball model, despite all the points being embedded in a unit ball,
the hyperbolic distances between points, i.e., tree distances (Section 3.1)
grow exponentially as we move towards boundary of the ball (see Figure 1).
Consequently, the distances are bounded between $0$ and $1$. As NMF requires
all terms in the input matrix to be positive, we cannot directly use these
distances to compute the term-term similarity matrix $\textbf{M}_{\text{S}}$
in Equation (2) as $1-d_{P}\left(w,w^{\prime}\right)$ can be negative. To
overcome this limitation, we introduce the notion of Poincaré Neighborhood
Similarity, ($s_{p_{n}}$), which uses a neighborhood normalization technique.
The $k$-neighborhood of a term $w$ is defined as the set of top k-nearest
terms ${w_{1},...,w_{k}}$ in the hyperbolic space and is denoted as
$n_{k}(w)$. For every term in the vocabulary $\mathcal{V}$, we first calculate
the pair-wise poincaré distances with other terms using Equation (1). Then,
for every term $w\in\mathcal{V}$, we compute similarity scores with all the
other terms in its $k$-neighborhood $n_{k}(w)$ by dividing each pair-wise
poincaré distance between the term and its neighbor by the maximum pair-wise
distance in the neighborhood. This can be represented by the following
equation where $w^{\prime}\in n_{k}(w)$:

$s_{p_{n}}\left(w,w^{\prime}\right)=1-\frac{d_{P}\left(w,w^{\prime}\right)}{\max\limits_{w_{a},w_{b}\in
n_{k}(w)}(d_{P}\left(w_{a},w_{b}\right))}$ (4)

With this, we can now compute the term-term similarity matrix $\bm{M_{S}}$ as
follows.

$\textbf{M}_{\text{S}}{(w,w^{\prime})}=\begin{cases}s_{p_{n}}\left(w,w^{\prime}\right)&\text{
if }s_{p_{n}}\left(w,w^{\prime}\right)\geq\alpha,\\\ 0&\text{ otherwise
}\end{cases}$ (5)

Note that there are two hyperparameters to control the neighborhood – (i) the
neighborhood size using $k_{s}$; and (ii) the quality of words using $\alpha$,
which keeps weights only for the pair of terms where the similarity crosses
the pre-defined threshold $\alpha$ thereby reducing noise in the matrix.
Without $\alpha$, words with very low similarity may get included in the
neighborhood eventually leading to noisy topics.

We now have all the ingredients to compute the document-representation matrix
A in the hyperbolic space and NMF can be performed to obtain the first set of
topics from the corpus as described in Section 3.2. This gives us the root
level topics of our hierarchy. Next, we describe how we can discover topics at
subsequent levels.

###  4.2 Building the Topic Hierarchy

In order to build the topic hierarchy, we can iteratively apply NMF for topics
discovered at each level as is typically done in most of the NMF based
approaches. However, do note that working in the Hyperbolic space allows us to
utilize hierarchical information encoded in the space to better guide the
discovery of topic hierarchies. Observe that the notion of similarity in the
hyperbolic space as defined in Equation(4) relies on the size of the
neighborhood. In large neighborhood, a particular term will include not only
its immediate children and ancestors but also other semantically similar words
that may not be hierarchically related. On the other hand, a small
neighborhood will include only the immediate parent-child relationships
between the words, since subconcept words are close to their concept words.
HyHTM uses this arrangement of words in hyperbolic space to explicitly guide
the lower-level topics to be more related and specific to higher-level topics.
In order to achieve this, we construct a Term-Term Hierarchy matrix,
$\textbf{M}_{\text{H}}\in R^{|V|\times|V|}$ as follows.

$\textbf{M}_{\text{H}}{(w,w^{\prime})}=\begin{cases}1&\text{if }w^{\prime}\in
n_{k_{h}}(w),\\\ 0&\text{ otherwise }\end{cases}$ (6)

Here, $k_{H}$ is a hyperparameter that controls the neighborhood size.
$\textbf{M}_{\text{H}}$ is a crucial component of our algorithm as it encodes
the hierarchy information and helps guide the lower-level topics to be related
and specific to the higher-level topics.

Without loss of generality, let us assume we are at $i^{th}$ topic node
$t_{i}$ at level $l$ in the hierarchy. We begin by computing
$\textbf{A}_{0}=\textbf{A}$, as outlined in Equation (2), at the root node
(representing all topics) and subsequently obtaining the first set of topics
(at level $l=1$). Also, let the number of topics at each node in the hierarchy
be $N$ (a user-specified parameter). Every document is then assigned to one
topic with which it has the highest association in the document-topic matrix
$\textbf{W}_{l-1}$. Once all the documents are collected into disjoint parent
topics, we use a subset of $\textbf{A}_{0}$ with only the set of documents
($\mathcal{D}_{t_{j}}$) belonging to the $j^{th}$ topic, and denote this by
$\textbf{A}_{l-1}$. We then branch out to $N$ lower-level topics at the
$i^{th}$ node, using the following steps:

Parent-Child Re-weighting for Topics in the Next Level: We use the term-term
hierarchical matrix $\textbf{M}_{\text{H}}$ to assign more attention to words
hierarchically related to all the terms in the topic node $t_{i}$, and guide
the topic hierarchy so that the lower-level topics are consistent with their
parent topics. We take the product of the topic-term matrix of the $t_{i}$,
denoted by, $\textbf{H}_{i}$ with the hierarchy matrix
$\textbf{M}_{\text{H}}$. This assigns weights with respect to associations in
the topic-term matrix

$\textbf{M}_{ti}=\mathbbm{1}_{i}^{T}\textbf{H}_{l-1}\times\textbf{M}_{\text{H}}$
(7)

Here, $\mathbbm{1}_{i}$ is the one-hot vector for topic $i$, and
$\textbf{H}_{l-1}$ is the topic-term factor obtained by factorizing the
document-representations $\textbf{A}_{l-1}$ of the parent level.

Document representation for computing next level topics: We now compute the
updated document representations for documents in topic node $t_{i}$ that
infuse semantic similarity between terms with hierarchical information as
follows.

$\textbf{A}_{l}=\textbf{A}_{l-1}\odot\textbf{M}_{ti}$ (8)

By using the updated document representations $\textbf{A}_{l}$ we perform NMF
as usual and obtain topics for level $l+1$. The algorithm then continues to
discover topics at subsequent levels and stops exploring topic hierarchy under
two conditions – (i) if it reaches a topic node such that the number of
documents in the node is less than a threshold ($D_{min}$); (ii) when the
maximum hierarchy depth ($\mathcal{L}_{max}$) is reached. We summarize the
whole process in the form of a pseudcode in Algorithm 1.

1

Input : Max depth level ($\mathcal{L}_{\text{max}}$)

Min # of documents ($D_{\text{min}}$)

Default # of topics ($N$)

Output : Hierarchy of Topics

2 Compute A using Eq (2) & (5)

3 GetHier(_A , $1$_)

4 def GetHier(_A , $L$_):

5if $L$ $>$ $L_{max}$ or len(A) $<$ $D_{min}$: return

6
$\textbf{W}_{l-1},\textbf{H}_{l-1}\leftarrow\textnormal{{{NMF}}}(\textbf{A},N)$

7 for  _$i=0$ to $H_{l-1}.\text{size}$_ do

8

9 Get parent topic using $\textbf{H}_{l-1}$

10 Add topic to hierarchy

11

12 Get Docs of topic $t_{j}$ using $\textbf{W}_{l-1}$

13 Get $\textbf{A}_{l-1}$ for $D_{t_{j}}$ from $\textbf{A}_{0}$

14

15 Compute Parent-Child Reweighting $\textbf{M}_{ti}$ using Eq (7)

16

17 Compute $\textbf{A}_{l}$ next level from $\textbf{M}_{ti}$ &
$\textbf{A}_{l-1}$ using Eq (8)

18

19 GetHier(_$\textbf{A}_{l}$ , $L+1$_)

Algorithm 1 The HyHTM Algorithm

##  5 Experimental Setup

Datasets: To evaluate our topic model, we consider 8 well-established public
benchmark datasets. In Table LABEL:tab:dataset we report the number of words
and documents, as well as the average number of words per document. We have
used datasets with varying numbers of documents and average document lengths.
We provide preprocessing details in the Appendix (See
LABEL:sect:preprocessing).