# Positive Moments Forever:
Undecidable and Decidable Cases

Gemma De les Coves  Institute for Theoretical Physics, University of
Innsbruck, Austria  Joshua Graf  Institute for Theoretical Physics, University
of Innsbruck, Austria  Andreas Klingler Corresponding author. E-mail:
<EMAIL_ADDRESS>Institute for Theoretical Physics, University of
Innsbruck, Austria  Tim Netzer  Department of Mathematics, University of
Innsbruck, Austria

###### Abstract

Is there an algorithm to determine attributes such as positivity or non-
zeroness of linear recurrence sequences? This long-standing question is known
as Skolem’s problem. In this paper, we study the complexity of an equivalent
problem, namely the (generalized) moment membership problem for matrices. We
show that this problem is decidable for orthogonal, unitary and real
eigenvalue matrices, and undecidable for matrices over certain commutative and
non-commutative polynomial rings. Our results imply that the positivity
problem for simple unitary linear recurrence sequences is decidable, and is
undecidable for linear recurrence sequences over the ring of commutative
polynomials. As a byproduct, we prove a free version of Pólya’s theorem.

###### Contents

  1. 1 Introduction
  2. 2 Problem statement
    1. 2.1 Relation to the membership problem for linear recurrence sequences
  3. 3 Decidable cases
    1. 3.1 Known results: small order
    2. 3.2 Orthogonal and unitary matrices
    3. 3.3 Matrices with a unique dominant eigenvalue or real eigenvalues
    4. 3.4 Further generalizations
  4. 4 Undecidable cases
    1. 4.1 Commutative polynomial rings
    2. 4.2 Non-commutative polynomial rings
  5. 5 Conclusion
  6. A A version of the matrix mortality problem

##  1 Introduction

Some problems may look innocent yet be formally very difficult — perhaps
uncomputable — or even worse, their computability may be unknown. _Skolem’s
problem_ exemplifies this uncertainty, focusing on the behavior of _linear
recurrence sequences_ (LRS), where each term in the sequence is generated
linearly from its predecessors. Examples of LRS include well-known sequences
like the Fibonacci sequence or those derived from discretizing differential
equations. Despite their simplicity, LRS are fundamental in various
mathematical and computer science domains, notably in generating pseudo-random
numbers [18], describing the dynamics of cellular automata [11], and many
other applications [6].

Specifically, an LRS of order $s$ is given by

$u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+\cdots+a_{s}u_{n-s}$

where $a_{1},\ldots,a_{s}\in\mathcal{R}$ are fixed elements in a ring
$\mathcal{R}$, usually commutative. Together with initial values
$u_{1},\ldots,u_{s}\in\mathcal{R}$, this gives rise to a sequence
$(u_{n})_{n\in\mathbb{N}}$ in $\mathcal{R}$. While several important examples
of LRS are over the ring $\mathcal{R}=\mathbb{Z}$, many interesting examples
are defined over other rings. For example, the Chebyshev polynomials are
defined via the LRS

$T_{n}(x)=2xT_{n-1}(x)-T_{n-2}(x)\quad\text{ with }T_{1}(x)\coloneqq x\text{
and }T_{0}(x)\coloneqq 1$

over the commutative ring $\mathbb{Z}[x]$ of univariate polynomials.

Skolem’s problem is a long-standing open question concerning LRS over
$\mathbb{Z}$ [13]. It asks whether an algorithm exists that decides if an LRS
attains the value $0$ for some $n\in\mathbb{N}$. While partial solutions to
Skolem’s problem are known, implying decidability for order $s\leqslant 4$
[19, 20], they do not apply to recurrences of order five or more. A
modification of Skolem’s problem is the _positivity problem_ for LRS. Instead
of asking whether the LRS is non-zero, it asks whether it stays non-negative.
In this case it is also unclear whether an algorithm exists that decides the
positivity problem, as decidability is proven only for $s\leqslant 5$ [14,
15].

Examples for LRS are _moment sequences_ , in which we have

$u_{n}=\mathrm{tr}(A^{n}),$

or _generalized moment sequences_ , in which

$u_{n}=\varphi(A^{n})$

for a given matrix $A\in\mathrm{Mat}_{s}(\mathcal{R})$ and a linear functional
$\varphi$ on $\mathrm{Mat}_{s}(\mathcal{R})$. Over a commutative ring
$\mathcal{R}$, such generalized moment sequences are as expressive as LRS,
i.e. every LRS can be expressed as a moment sequence and vice versa. For this
reason, decidability results for generalized moment sequences translate to
decidability results for Skolem’s problem and the positivity problem.

In this paper, we study the decidability of the moment membership problem.
That is, we consider the problem: For an $s\times s$ matrix $A$, decide
whether

$\mathrm{tr}(A^{n})\in\mathcal{P}\quad\forall n\in\mathbb{N}$

where $\mathcal{P}$ is a fixed set. This set usually contains elements that
are positive in some sense, so we call the problem also the _moment positivity
problem_. Most of our results also hold for generalized moments of the form
$\varphi(A^{n})$ as above.

One decisive factor in the complexity of the problem is the instance set
$\mathcal{D}$ of the matrices, which allows us to distinguish between our two
main results:

  * $\triangleright$

We restrict the instance set
$\mathcal{D}\subseteq\mathrm{Mat}_{s}(\mathbb{Z})$ and prove decidability of
the problem for a large subclass of integer matrices.

  * $\triangleright$

We enlarge the instance set $\mathrm{Mat}_{s}(\mathbb{Z})\subseteq\mathcal{D}$
and prove that the problem is undecidable for matrices whose entries are
elements of certain unital rings $\mathcal{R},$ for certain
$\mathcal{P}\subseteq\mathcal{R}$.

#### Contributions.

Specifically, we determine the complexity of the moment membership problem in
the following cases (see Table 1):

  * $\triangleright$

Decidability. The moment positivity problem is decidable for orthogonal
matrices (Theorem 8), unitary matrices (Corollary 11), and matrices with a
unique dominant eigenvalue or only real eigenvalues (Theorem 13). It follows
that the positivity problem is decidable for simple unitary LRS, i.e. LRS
whose characteristic polynomial only has simple roots of modulus $1$, as well
as for LRS whose characteristic polynomial has a unique dominant root, or only
real roots.

  * $\triangleright$

Undecidability. The generalized problem is undecidable for the ring of
multivariate commutative polynomials (Theorem 18) as well as for non-
commutative polynomials, where $\mathcal{P}$ is the set of polynomials with
nonnegative coefficients (Theorem 22). This implies that the corresponding
positivity problem for LRS over commutative polynomials is undecidable.

  * $\triangleright$

Free Pólya’s Theorem. As a side result, we prove a free version of Pólya’s
theorem (Theorem 20). We show that a non-commutative polynomial has
nonnegative coefficients if and only if it is entrywise nonnegative on the set
of entrywise nonnegative matrices.

Decidable cases | Undecidable cases
---|---
Unitary and Orthogonal matrices | Comm. polynomials $\mathbb{Z}[x_{1},\ldots,x_{d}]$
(Section 3.2) | (Section 4.1)
Dominant or real eigenvalue matrices | Non-comm. polynomials $\mathbb{Z}\langle z_{1},\ldots,z_{d}\rangle$
(Section 3.3) | (Section 4.2)
Table 1: For which instance sets is the (generalized) moment membership
problem decidable or undecidable? This table summarizes the results of this
paper.

This paper is structured as follows. In Section 2 we present the problem
statement and show the relation of moment problems to LRS. In Section 3 we
present cases in which the moment problem is decidable. This includes a review
of known results (Section 3.1), the decidability for orthogonal and unitary
matrices (Section 3.2), and the decidability for matrices with unique largest
eigenvalue or only real roots (Section 3.3). In Section 4, we prove that the
moment problem is undecidable over certain commutative and non-commutative
rings, as well as a non-commutative version of Pólya’s Theorem. In Section 5
we conclude, and in Appendix A we prove a version of the matrix mortality
problem for the undecidability result of commutative polynomials.

##  2 Problem statement

Let $\mathcal{R}$ be a unital ring (not necessarily commutative), and let
$A\in\mathrm{Mat}_{s}(\mathcal{R})$ be an $s\times s$ square matrix with
entries from $\mathcal{R}.$ For $n\geqslant 0$ the _$n$ -th moment of $A$_ is
defined as

$\mu_{n}(A)\coloneqq\mathrm{tr}\mathopen{}\mathclose{{}\left(A^{n}}\right)$

where $\mathrm{tr}$ denotes the usual trace of a matrix, i.e. the sum of its
diagonal entries. The moments of $A$ are clearly elements from $\mathcal{R}$,
as for $A=\mathopen{}\mathclose{{}\left(a_{ij}}\right)_{i,j=1,\ldots,s}$ we
have

$\mu_{0}(A)=\underbrace{1_{\mathcal{R}}+\cdots+1_{\mathcal{R}}}_{s}\quad\mbox{
and }\quad\mu_{1}(A)=\sum_{i=1}^{s}a_{ii},$

and for $n\geqslant 2$

$\mu_{n}(A)=\sum_{i_{1},\ldots,i_{n}=1}^{s}a_{i_{1}i_{2}}\cdot
a_{i_{2}i_{3}}\cdots\cdot a_{i_{n-1}i_{n}}\cdot a_{i_{n}i_{1}}.$

Depending on the ring $\mathcal{R}$, the moments are studied in different
contexts, as the following example shows.

######  Example 1.

Let $V$ be a $\mathbb{C}$-vector space. Consider the tensor algebra

$\mathcal{R}\coloneqq T(V)\coloneqq\bigoplus_{m\geqslant 0}V^{\otimes
m}=\mathbb{C}\oplus V\oplus\mathopen{}\mathclose{{}\left(V\otimes
V}\right)\oplus\cdots$

$\mathcal{R}$ forms a unital ring with tensor product as multiplication.
Actually, $\mathcal{R}$ is an $\mathbb{N}$-graded unital $\mathbb{C}$-algebra.

For
$A=\mathopen{}\mathclose{{}\left(a_{ij}}\right)_{i,j}\in\mathrm{Mat}_{s}(V)$
(which embeds into $\mathrm{Mat}_{s}(\mathcal{R})$), we obtain

$\mu_{n}(A)=\sum_{i_{1},\ldots,i_{n}=1}^{s}a_{i_{1}i_{2}}\otimes
a_{i_{2}i_{3}}\otimes\cdots\otimes a_{i_{n-1}i_{n}}\otimes a_{i_{n}i_{1}},$
(1)

where the $n$-th moment is homogeneous of degree $n$ in $\mathcal{R}$. The
expression in (1) is called a _translational invariant matrix product state_
in tensor network theory. The number $s$ is usually called the _bond
dimension_ of the tensor $\mu_{n}(A)$.  $\triangle$

Now assume that $\mathcal{R}$ is also equipped with a subset
$\mathcal{P}\subseteq\mathcal{R}$. In our results and applications, this will
always be a set of elements that are positive in some sense. Further
$\mathcal{D}\subseteq\mathrm{Mat}_{s}(\mathcal{R})$ will be the set containing
all instances of our decision problem. The general decision problem addressed
in this paper is the following:

######  Problem 2 (Moment positivity problem).

Let $s$, $\mathcal{P}$, $\mathcal{D}$ be fixed as above. For $A\in\mathcal{D}$
decide whether _all_ moments $\mu_{n}(A)$ belong to $\mathcal{P}$.

Note that $\mathcal{D},\mathcal{P},s$ are fixed in our formulation of the
problem. We are thus looking for an algorithm (tailored to
$\mathcal{R},\mathcal{P},s$ and $\mathcal{D}$) that upon an input of any
instance $A\in\mathcal{D}$ stops after a finite time, and returns yes if all
moments of $A$ belong to $\mathcal{P}$, and no if at least one moment of $A$
does not belong to $\mathcal{P}$. If such an algorithm exist, we call the
moment membership problem _decidable_ , otherwise we call it _undecidable_.

Note that if the ring operations are computable and membership of single
elements in $\mathcal{P}$ is decidable, the moments membership problem is
clearly semi-decidable in the following sense. Given
$A\in\mathrm{Mat}_{s}(\mathcal{R})$, we compute higher and higher moments of
$A,$ and check membership in $\mathcal{P}$. If some moment does not belong to
$\mathcal{P}$, we will know after a finite time. However, this algorithm runs
forever in case that all moments do belong to $\mathcal{P}$. So the hard part
of the problem is certifying membership of all moments in $\mathcal{P}$. We
will make use of the semi-decidability in Theorem 8.

###  2.1 Relation to the membership problem for linear recurrence sequences

In the following, we review the relation of the moment problem to the
positivity problem for linear recurrence sequences. A _linear recurrence
sequence_ (LRS) $(u_{n})_{n\in\mathbb{N}}\in\mathcal{R}^{\mathbb{N}}$ is a
sequence whose elements are related to each other linearly, i.e.

$u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+\cdots+a_{s}u_{n-s}$ (2)

for all $n>s$. We call $s$ the _order_ of the recurrence relation. The
positivity problem for LRS is the following:

######  Problem 3.

Given an LRS as in (2) with parameters $a_{1},\ldots,a_{s}\in\mathcal{R}$ and
initial values $u_{1},\ldots,u_{s}\in\mathcal{R}$, decide whether
$u_{n}\in\mathcal{P}$ for all $n\in\mathbb{N}$.

We start with the (well-known) observation that every generalized moment
sequence is an LRS, if $\mathcal{R}$ is commutative.

######  Lemma 4.

Let $\mathcal{R}$ be a commutative unital ring, and let
$A\in\mathrm{Mat}_{s}(\mathcal{R})$. Then
$\mathopen{}\mathclose{{}\left(\varphi(A^{n})}\right)_{n\in\mathbb{N}}$ is an
LRS of order $s$, for every $\mathcal{R}$-linear map
$\varphi\colon\mathrm{Mat}_{s}(\mathcal{R})\to\mathcal{R}$.

###### Proof.

Let $p(x)=x^{s}-a_{1}x^{s-1}-\cdots-a_{s}$ be the characteristic polynomial of
the matrix $A$. By the Cayley–Hamilton theorem for commutative rings (see for
example [10, Chapter XIV.3]), we have that

$A^{s}=a_{1}A^{s-1}+a_{2}A^{s-2}+\cdots+a_{s}I$ (3)

and therefore

$A^{n}=a_{1}A^{n-1}+a_{2}A^{n-2}+\cdots+a_{s}A^{n-s}$

for all $n\geqslant s.$ Applying $\varphi$ proves the statement. ∎

It is unclear whether a similar statement to Lemma 4 is true for non-
commutative rings. While there exist versions of the Cayley–Hamilton theorem
for non-commutative rings (see for example [7, 17]), they cannot be applied to
obtain an equation similar to (3).

The next observation states that LRS are equivalent to generalized moment
sequences. It can be found in [14]:

######  Lemma 5.

Let $(u_{n})_{n\in\mathbb{N}}$ be a sequence in a commutative unital ring
$\mathcal{R}$. The following are equivalent:

  1. $(i)$

$(u_{n})_{n\in\mathbb{N}}$ is a LRS of order $s$.

  2. $(ii)$

There is a matrix $A\in\mathrm{Mat}_{s}(\mathcal{R})$ and two vectors
$v,w\in\mathcal{R}^{s}$ such that $u_{n}=v^{t}A^{n-s}w$ for all $n>s$.

###### Proof.

For $(i)\Rightarrow(ii)$ assume that the recurrence is given by

$u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+\cdots+a_{s}u_{n-s}.$

Using the companion matrix

$A=\begin{pmatrix}a_{1}&1&&&\\\ a_{2}&&1&&\\\ \vdots&&&\ddots&\\\
a_{s-1}&&&&1\\\ a_{s}&&&&\end{pmatrix}$

we have that $u_{n}=v^{t}A^{n-s}w$ where $v=(u_{s},u_{s-1},\ldots,u_{1})^{t}$
and $w=(1,0,\ldots,0)^{t}.$

The proof of $(ii)\Rightarrow(i)$ is analogous to Lemma 4, by replacing
$\mathrm{tr}$ by the function $A\mapsto v^{t}Aw$. Note that the recurrence
starts to hold only for $n>2s$, but for our purposes this is irrelevant.∎

##  3 Decidable cases

In the following we present cases in which the moment membership problem is
decidable. This includes known results for small $s$ (Section 3.1), the moment
positivity problem for unitary and orthogonal matrices (Section 3.2), and for
matrices with a unique largest eigenvalue or only real eigenvalues(Section
3.3). Throughout this section we will consider
$\mathcal{P}=\mathbb{R}_{\geqslant 0}$.

###  3.1 Known results: small order

We first review known results on the decidability of the moment positivity
problem. The results are about LRS, but in view of Lemma 4, they immediately
transfer to moments.

######  Theorem 6.

The moment positivity problem is decidable in the following cases:

  1. $(i)$

$s\leqslant 5,\mathcal{D}=\mathrm{Mat}_{s}(\mathbb{Q}).$

  2. $(ii)$

$s\leqslant 9,\mathcal{D}\subseteq\mathrm{Mat}_{s}(\mathbb{Q})$ the set of
matrices with simple eigenvalues.

The proof of ($i$) is contained in [14], the proof of ($ii$) goes back to
[15]. Decidability for other values of $s$ is unknown.

The positivity problem of LRS is closely related to _Skolem’s Problem_ which
asks if some sequence element equals $0$. The best result in this context is
that Skolem’s Problem is $\mathsf{NP}$-hard [2]. The decidability of the
positivity problem implies decidability of Skolem’s Problem. This follows for
an integer LRS because $u_{n}\neq 0$ if and only if $u_{n}^{2}-1\geqslant 0$.
If $(u_{n})_{n\in\mathbb{N}}$ is an LRS of order $s$, then $u_{n}^{2}-1$ is an
LRS of order $s^{2}$. Moreover, since Skolem’s Problem is $\mathsf{NP}$-hard,
the positivity problem is $\mathsf{NP}$-hard as well.

###  3.2 Orthogonal and unitary matrices

We now show that the moment positivity problem for orthogonal (Theorem 8) and
unitary matrices (Corollary 11) is decidable. The proof strategy is very
similar to [3].

A set $X\subseteq\mathbb{R}^{m}$ is algebraic if there are polynomials
$p_{1},\ldots,p_{n}\colon\mathbb{R}^{m}\to\mathbb{R}$ such that

$X=\\{x\in\mathbb{R}^{m}\mid p_{1}(x)=\cdots=p_{n}(x)=0\\}.$

In this case, $X$ is the algebraic variety defined by $p_{1},\ldots,p_{n}$,
and we write $X=\mathcal{V}(p_{1},\ldots,p_{n})$. Even if the set of defining
polynomials is infinite, there always exists a finite choice of polynomials
defining the same algebraic variety, by Hilbert’s basis theorem. Since we work
over $\mathbb{R}$, we can even reduce it to a single polynomial by taking the
sum of squares of the defining polynomials.

For matrices $A_{1},\ldots,A_{d}\in\mathrm{Mat}_{s}(\mathbb{R})$, let

$\langle A_{1},A_{2},\ldots,A_{d}\rangle\coloneqq\big{\\{}A_{k_{1}}\cdots
A_{k_{\ell}}\mid\ell\in\mathbb{N},\ k_{1},\ldots,k_{\ell}=1,\ldots,d\big{\\}}$

be the semigroup generated by $A_{1},\ldots,A_{d}$. We denote by
$\overline{\langle A_{1},\ldots,A_{d}\rangle}$ the topological closure inside
$\mathrm{Mat}_{s}(\mathbb{R})$ with respect to the Euclidean topology.

######  Lemma 7.

Let $A_{1},\ldots,A_{d}\in\mathrm{O}_{s}(\mathbb{Q})$ be orthogonal $s\times
s$ matrices with rational entries. Then $\mathcal{G}\coloneqq\overline{\langle
A_{1},\ldots,A_{d}\rangle}$ is a compact algebraic group. Moreover there is a
recursively enumerable sequence of rational polynomials
$(p_{k})_{k\in\mathbb{N}}$ defining $\mathcal{G}$ inside
$\mathrm{Mat}_{s}(\mathbb{R})$.

###### Proof.

Compactness of $\mathcal{G}$ is obvious. To prove that $\mathcal{G}$ is a
group we only have to show that $A^{-1}\in\mathcal{G}$ for every
$A\in\mathcal{G}$. Consider the sequence $(A^{k})_{k\in\mathbb{N}}$. By
compactness, there exists a converging subsequence. In other words, for every
$\varepsilon>0$, there exists $n_{2}>n_{1}+1$ such that

$\|A^{n_{1}}-A^{n_{2}}\|<\varepsilon$

where $\|\cdot\|$ is the operator norm. Since $\|A\cdot B\|=\|B\|$ for every
matrix $B$, we obtain

$\|A^{-1}-A^{n_{2}-n_{1}-1}\|<\varepsilon.$

This shows that $A^{-1}\in\mathcal{G}$.

Now note that every compact group
$\mathcal{G}\subseteq\mathrm{Mat}_{s}(\mathbb{R})$ is algebraic (see for
example [12, Chapter 3, Section 4.4]). In particular, it is shown there that

$\mathcal{G}=\mathcal{V}\mathopen{}\mathclose{{}\left(\mathbb{R}[X]^{\mathcal{G}}}\right)\coloneqq\mathcal{V}\Big{(}p\in\mathbb{R}[X]\mid
p(I_{s})=0,\ p(gX)=p(X)\text{ for all }g\in\mathcal{G}\Big{)},$

where $I_{s}$ is the identity matrix of size $s$.

Now note that if $\mathcal{G}$ is generated by $A_{1},\ldots,A_{d}$, then the
invariance only needs to be checked with respect to the generators, i.e.

$\mathcal{G}=\mathcal{V}\Big{(}p\in\mathbb{R}[X]\mid p(I_{s})=0,\
p(A_{i}X)=p(X)\ \text{ for }i=1,\ldots,d\Big{)}.$

Since the conditions $p(I_{s})=0$ and $p(A_{i}X)=p(X)$ are linear in the
coefficients of $p$, there exists a basis $(p_{k})_{k\in\mathbb{N}}$ of the
space of solutions of these conditions. Moreover, the coefficients of the
basis vectors $p_{k}$ can be chosen from $\mathbb{Q}$, since all conditions
are rational. We now have

$\mathcal{G}=\mathcal{V}(p_{k}\mid k\in\mathbb{N}).$

The polynomials $p_{k}$ can be computed recursively by solving the system of
linear equations over the space of polynomials with degree $d,$ and by
increasing $d$ iteratively. ∎

Note that the statement is not true if $\mathbb{R}$ is replaced by
$\mathbb{C}$. For example the group

$\mathcal{G}\coloneqq\mathopen{}\mathclose{{}\left\\{e^{i\theta}\mid\theta\in[0,2\pi)}\right\\},$

seen as a subset of $1\times 1$ matrices, is not algebraic. Yet, we shall see
that the moment problem also generalizes to unitary matrices (see Corollary
11).

Since $\mathbb{R}[X]$ is a Noetherian ring, there exists $n\in\mathbb{N}$ such
that

$\mathcal{G}=\mathcal{V}(p_{1},\ldots,p_{n}).$

This will be an important ingredient to prove the decidability of the moment
problem. Note however that $n$ can be arbitrarily large and it is unclear
whether $n$ is computable or not.

######  Theorem 8.

The moment positivity problem for $\mathcal{D}=\mathrm{O}_{s}(\mathbb{Q})$ is
decidable.

###### Proof.

We will present two procedures, each certifying either yes- or no-instances in
finite time. Letting these algorithms run in parallel will result in a
decision algorithm for the problem.

Certifying no-instances for $A\in\mathrm{O}_{s}(\mathbb{Q})$ is achieved by
iteratively checking whether $\mathrm{tr}(A^{n})\geqslant 0$ holds for every
$n$. If $A$ is a no-instance, this algorithm will halt when detecting
$\mathrm{tr}(A^{n})<0$ for the first time.

We now present an algorithm to certify yes-instances in finite time. For a
given $A\in\mathrm{O}_{s}(\mathbb{Q})$, the moment membership problem can be
rephrased as

$\forall B\in\langle A\rangle:\mathrm{tr}(B)\geqslant 0.$

By the continuity of the trace, this is equivalent to

$\forall B\in\overline{\langle A\rangle}:\mathrm{tr}(B)\geqslant 0.$ (4)

By Lemma 7 there exists a recursively enumerable sequence of polynomials
$(p_{k})_{k\in\mathbb{N}}$ and some $n\in\mathbb{N}$ such that

$\overline{\langle A\rangle}=\mathcal{V}(p_{1},\ldots,p_{n}).$

Now step $k$ of the algorithm verifies the statement

$\forall B\in\mathcal{V}(p_{1},\ldots,p_{k})\colon\mathrm{tr}(B)\geqslant 0$
(5)

which is decidable by the Tarski–Seidenberg Theorem, since it is a statement
in first order logic. As soon as Eq. 5 is true for the first time, the
algorithm halts and outputs a correct yes-answer. This will be the case after
at most $n$ steps, if $A$ is a yes-instance. ∎

######  Remark 9.

The previous statement can be generalized in two directions:

  1. ($i$)

By the same argument, the following problem is also decidable: Given
$A_{1},\ldots A_{d}\in\mathrm{O}_{s}(\mathbb{Q})$ for a fixed matrix size $s$,
decide if:

$\forall\ell\in\mathbb{N}\ \forall
k_{1},\ldots,k_{\ell}\in\\{1,\ldots,d\\}\colon\mathrm{tr}(A_{k_{1}}\cdots
A_{k_{\ell}})\geqslant 0.$

Note that this decision problem for arbitrary matrices is undecidable [4].

  2. ($ii$)

The proof remains true if $\mathrm{tr}$ is replaced by any other continuous
function. This in particular implies that the generalized problem

$\forall n\in\mathbb{N}\colon\varphi(A^{n})\geqslant 0$

is decidable.  $\triangle$

We now generalize the result to unitary matrices, by embedding them into
orthogonal matrices of larger size. We denote by $\mathbb{Q}[i]$ the field of
complex numbers with rational real and imaginary parts, and we denote the set
of $s\times s$ unitary matrices with entries in $\mathbb{Q}[i]$ by
$\mathrm{U}_{s}(\mathbb{Q}[i])$.

######  Lemma 10.

The map

$\displaystyle\Psi\colon\mathrm{U}_{s}(\mathbb{Q}[i])$
$\displaystyle\to\mathrm{O}_{2s}(\mathbb{Q})$ $\displaystyle U=A+iB$
$\displaystyle\mapsto\begin{pmatrix}A&-B\\\ B&A\end{pmatrix}$

is a group homomorphism. Moreover we have

$\mathrm{tr}(U)=\frac{1}{2}\mathrm{tr}\mathopen{}\mathclose{{}\left(\Psi(U)\cdot\begin{pmatrix}I_{s}&iI_{s}\\\
-iI_{s}&I_{s}\end{pmatrix}}\right).$

###### Proof.

The map is well defined since $\Psi(U)$ is orthogonal if and only if $U$ is
unitary. The rest is immediate. ∎

The main results of this section are summarized in the following two
corollaries.

######  Corollary 11.

For each $s\geqslant 1$, the moment positivity problem for matrices from
$\mathrm{U}_{s}(\mathbb{Q}[i])$ is decidable.

###### Proof.

It follows immediately from Lemma 10, Theorem 8 and Remark 9 ($ii$). ∎

######  Corollary 12.

The positivity problem is decidable for simple unitary LRS, i.e.

$u_{n}=a_{1}u_{n-1}+\cdots+a_{s}u_{n-s}$

with $a_{1},\ldots,a_{s}\in\mathbb{Q}[i]$, where the roots of
$p(x)=x^{s}-a_{1}x^{s-1}-a_{2}x^{s-2}-\cdots-a_{s}$ are all simple and of
modulus $1$.

###### Proof.

We choose a unitary matrix $A\in{\rm U}_{s}(\mathbb{C})$ whose eigenvalues are
the roots of $p$, and whose entries are computable numbers. For example, one
can take a diagonal matrix with the specified roots on the diagonal. We obtain
the reccurence

$A^{n}=a_{1}A^{n-1}+\cdots+a_{s}A^{n-s}$

for all $n\geqslant s$, and since the roots are all simple, $p$ is actually
the minimal polynomial of $A$. So $I_{s},A,A^{2},\ldots,A^{s-1}$ are linearly
independent, and we can thus find a linear functional $\varphi$ on
$\mathrm{Mat}_{s}(\mathbb{C})$ with $\varphi(A^{i})=u_{i}$ for
$i=0,\ldots,s-1$. Now, by Remark 9 and Lemma 10 above, it is decidable whether
$\varphi(A^{i})\geqslant 0$ holds for all $i$, and since this sequence
fulfills the same recurrence and initial conditions as $(u_{i})_{i\geqslant
1}$, the two sequences coincide.∎

###  3.3 Matrices with a unique dominant eigenvalue or real eigenvalues

In the following, we show that for matrices with a unique dominant eigenvalue,
and for matrices with only real eigenvalues, the moment problem is decidable.
Note that the idea for the case of a unique dominating eigenvalue is already
present in [14], but restricted to multiplicity $1$ and matrices of size at
most $s=5$.

######  Theorem 13.

The moment positivity problem is decidable in the following cases:

  1. $(i)$

$\mathcal{R}=\mathbb{Q},s$ arbitrary, and the set of instances restricted to
matrices with a unique dominant eigenvalue.

  2. $(ii)$

$\mathcal{R}=\mathbb{Q},s$ arbitrary, and the set of instances restricted to
matrices with only real eigenvalues.

###### Proof.

We provide algorithms that decide the moments positivity problem for the
stated instance sets. We can assume without loss of generality that
$A\in\mathrm{Mat}_{s}(\mathbb{Z}),$ by possibly multiplying the matrix with
the largest denominator of its entries.

For $(i)$ let $A\in\mathrm{Mat}_{s}(\mathbb{Z})$ have a unique dominant
eigenvalue. Since $A$ has real entries, the non-real eigenvalues of $A$ come
in conjugate pairs. Since there is exactly one eigenvalue $\lambda_{1}$ of
largest absolute value, it must be real. We let $k$ denote its multiplicity
and obtain

$|\mu_{n}(A)-k\cdot\lambda_{1}^{n}|\leqslant(s-k)|\lambda_{2}|^{n},$

where $\lambda_{2}$ denotes the second largest eigenvalue in absolute value.
Thus it suffices to check $\mu_{n}(A)\geqslant 0$ for $n$ up to

$\frac{\log(s/k-1)}{\log(|\lambda_{1}|)-\log(|\lambda_{2}|)}.$

$(ii)$: In this case only odd moments matter, since the even moments are
always nonnegative. If the dominant eigenvalues all have the same sign, then
we can apply $(i)$. Otherwise, since odd powers of eigenvalues with the same
absolute values but different signs cancel out, we can reduce the problem to a
smaller matrix, where the dominant eigenvalues do have the same sign. ∎

###  3.4 Further generalizations

In the following, we present a generalization of the statements in Section 3.2
and Section 3.3. For a matrix $A\in\mathrm{Mat}_{s}(\mathbb{R})$, we denote by
$\mathsf{spec}(A)$ the multi-set of all eigenvalues of $A$ (where multiple
eigenvalues are represented by multiple elements of $\mathsf{spec}(A)$).
Express

$\mathsf{spec}(A)=\mathsf{per}_{1}(A)\cup\mathsf{per}_{2}(A)\cup\cdots\cup\mathsf{per}_{s}(A)$

as a partition of peripheral spectra, i.e. eigenvalues of the same absolute
value, in decreasing order (i.e. $\mathsf{per}_{1}(A)$ contains the dominant
eigenvalues, $\mathsf{per}_{2}(A)$ the eigenvalues of second largest absolute
value…). Note that $\mathsf{per}_{i}(A)$ can be empty if $A$ has multiple
eigenvalues of same absolute value. Moreover, let

$\mu_{n}^{(i)}(A)\coloneqq\sum_{\lambda\in\mathsf{per}_{i}(A)}\mathopen{}\mathclose{{}\left(\frac{\lambda}{|\lambda|}}\right)^{n}.$

We define

$\eta_{i}(A)=\mathopen{}\mathclose{{}\left\\{\begin{array}[]{cl}\inf_{n\in\mathbb{N}}\mu^{(i)}_{n}(A)&\text{
: if }\mathsf{per}_{i}(A)\neq\emptyset\\\ \infty&\text{ : if
}\mathsf{per}_{i}(A)=\emptyset\end{array}}\right.$

and

$\gamma_{i}(A)=\mathopen{}\mathclose{{}\left\\{\begin{array}[]{cl}\sup_{n\in\mathbb{N}}\mu^{(i)}_{pn+q}(A)&\text{
: if }\mathsf{per}_{i}(A)\neq\emptyset\\\ -\infty&\text{ : if
}\mathsf{per}_{i}(A)=\emptyset\end{array}}\right.,$

where $p,q\geqslant 1$ are arbitrary but fixed integers. So we compute the
supremum along an arithmetic progression.

######  Lemma 14.

The following two problems are decidable:

  1. $(i)$

Given111To assume that the inputs have a finite description, we restrict to
algebraic numbers, i.e. numbers that can be represented as roots of an integer
polynomial. This is enough to apply Lemma 14 in the proof of Theorem 15.
$A\in\mathrm{Mat}_{s}(\mathbb{R})$, $c\in\mathbb{R},$ decide whether
$\eta_{i}(A)\geqslant c.$

  2. $(ii)$

Given $A\in\mathrm{Mat}_{s}(\mathbb{R})$, $c\in\mathbb{R},$ decide whether
$\gamma_{i}(A)\leqslant c.$

###### Proof.

The decision algorithms are very similar to one from the proof of Theorem 8.
To construct an algorithm for ($i$), let the following two procedures run in
parallel:

  1. ($a$)

Evaluate $\mu_{n}^{(i)}(A)$ for increasing $n\in\mathbb{N}$. Halt if
$\mu_{n}^{(i)}(A)<c$.

  2. ($b$)

Check the statement

$\forall B\in\mathcal{V}(p_{1},\ldots,p_{k})\colon\mathrm{tr}(B)\geqslant c$

for increasing $k\in\mathbb{N}$, where $(p_{\ell})_{\ell\in\mathbb{N}}$ define
the variety $\overline{\langle U\rangle},$ where $U$ is the diagonal matrix
with eigenvalues $\lambda/|\lambda|$ for $\lambda\in\mathsf{per}_{i}(A)$. Halt
if the statement is true.

If $A,c$ is a no-instance of ($i$), then ($a$) will eventually halt; if $A,c$
is a yes-instance, ($b$) will eventually halt, for the same reason as in the
proof of Theorem 8.

The algorithm for ($ii$) is very similar. Let the following two procedures run
in parallel:

  1. ($a$)

Evaluate $\mu_{pn+q}^{(i)}(A)$ for increasing $n\in\mathbb{N}$. Halt if
$\mu_{pn+q}^{(i)}(A)>c$.

  2. ($b$)

Check the statement

$\forall B\in\mathcal{V}(p_{1},\ldots,p_{k})\colon\mathrm{tr}(U^{q}B)\leqslant
c$

for increasing $k\in\mathbb{N}$, where $(p_{\ell})_{\ell\in\mathbb{N}}$ define
the group $\overline{\langle U^{p}\rangle},$ where $U$ is the diagonal matrix
with eigenvalues $\lambda/|\lambda|$ for $\lambda\in\mathsf{per}_{i}(A)$. Halt
if the statement is true.

In ($b$) we only evaluate odd moments; recall Remark 9 ($ii$). ∎

It is unclear whether $\eta_{i}(A)>c$ or $\eta_{i}(A)=c$ is decidable. This is
due to the fact that we do not know whether $\mu_{n}^{(i)}(A)$ attains the
infimum/supremum for finite $n$.

######  Theorem 15.

For a fixed parameter $\varepsilon>0$, the moment positivity problem is
decidable for all non-zero matrices $A$ satisfying one of the following
conditions:

  1. $(i)$

$\exists k\in\mathbb{N}\colon\eta_{1}(A),\ldots,\eta_{k}(A)\geqslant
0,\eta_{k+1}(A)\geqslant\varepsilon.$

  2. $(ii)$

$\exists k\in\mathbb{N}\colon\gamma_{1}(A),\ldots,\gamma_{k}(A)\leqslant
0,\gamma_{k+1}(A)\leqslant-\varepsilon.$

  3. $(iii)$

$\eta_{1}(A)<0.$

If $(ii)$ or $(iii)$ are satisfied, then $A$ is automatically a no-instance.
If $(i)$ is satisfied, then $A$ can be a yes or a no-instance. Moreover, each
of the above criteria is decidable.

###### Proof.

First, checking whether $A$ satisfies ($i$), ($ii$) or ($iii$) is decidable by
Lemma 14, since there are only finitely many of these statements to check.

To prove ($i$), assume that $\eta_{k+1}(A)\neq\infty$ (the other case is
trivial). Let $\lambda_{i}\in\mathsf{per}_{i}(A)$. We have that

$\mu_{n}(A)=\sum_{i=1}^{d}|\lambda_{i}|^{n}\mu_{n}^{(i)}(A)\geqslant|\lambda_{k+1}|^{n}\mathopen{}\mathclose{{}\left(\varepsilon-s\sum_{i=k+2}^{d}\mathopen{}\mathclose{{}\left(\frac{|\lambda_{i}|}{|\lambda_{k+1}|}}\right)^{n}}\right)$

which is positive for

$n\geqslant\frac{\log(\varepsilon)-\log(sd)}{\log(|\lambda_{k+2}|)-\log(|\lambda_{k+1}|)}.$

So we only need to check finitely many instances of the problem.

For ($ii$) we have that

$\mu_{m}(A)=\sum_{i=1}^{d}|\lambda_{i}|^{m}\mu_{m}^{(i)}(A)<|\lambda_{k+1}|^{m}\mathopen{}\mathclose{{}\left(-\varepsilon+s\sum_{i=k+2}^{d}\mathopen{}\mathclose{{}\left(\frac{|\lambda_{i}|}{|\lambda_{k+1}|}}\right)^{m}}\right).$

Now there clearly exists some $m$ of the form $pn+q$ such that the right hand
side is negative.

For ($iii$) note that $\eta_{1}(A)<0$ is decidable since $\eta_{1}(A)\geqslant
0$ is decidable by Lemma 14. Let $0<\delta<-\eta_{1}(A)$. Then there exists an
increasing sequence $(n_{\ell})_{\ell\in\mathbb{N}}$ such that
$\mu_{n_{\ell}}^{(1)}(A)<\eta_{1}(A)+\delta<0$ for all $\ell$.222This follows
from the fact that for a unitary matrix $U$ the group $\overline{\\{U^{n}\mid
n\in\mathbb{N}\\}}$ is either finite or contains no isolated points. Because
if the set contains an isolated point, then all elements are isolated. But a
compact set which contains only isolated points is finite. Hence there exists
an increasing sequence $(n_{\ell})_{\ell}$ such that
$\eta_{i}(U)\leqslant\mathrm{tr}(U^{n_{\ell}})\leqslant\eta_{i}(U)+\frac{1}{\ell}.$
Therefore we have

$\mu_{n_{\ell}}(A)=\sum_{i=1}^{d}|\lambda_{i}|^{n_{\ell}}\mu_{n_{\ell}}^{(i)}(A)<|\lambda_{1}|^{n_{\ell}}\mathopen{}\mathclose{{}\left(\eta_{1}(A)+\delta+s\sum_{i=2}^{d}\mathopen{}\mathclose{{}\left(\frac{|\lambda_{i}|}{|\lambda_{1}|}}\right)^{n_{\ell}}}\right).$

Again there exists $\ell_{0}$ such that $\mu_{n_{\ell_{0}}}(A)<0$. ∎

##  4 Undecidable cases

We now present two finitely generated rings for which the moment membership
problem is undecidable. Specifically, in Section 4.1 we prove that the moment
membership problem is undecidable for the ring of commutative polynomials
$\mathcal{R}=\mathbb{Z}[x_{1},\ldots,x_{d}]$ if $n$ is sufficiently large. In
Section 4.2, we show that the moment membership problem is also undecidable
for the space of non-commutative polynomials $\mathcal{R}=\mathbb{Z}\langle
z_{1},\ldots,z_{d}\rangle$. For a similar undecidable problem including
nonnegative and sos polynomials polynomials over infinitely many variables, we
refer to [5, Section 6].

###  4.1 Commutative polynomial rings

In the following, we show that the generalized moment membership problem for
$\mathcal{R}=\mathbb{Z}[x_{1},\ldots,x_{d}]$ and the cone

$\mathcal{P}_{\rm
coeff}\coloneqq\\{p\in\mathbb{Z}[x_{1},\ldots,x_{d}]\mid\text{all coefficients
of }p\text{ are nonnegative}\\}$

is undecidable. The proof relies on the following undecidable problem, for
which a proof can be found in Appendix A.

######  Lemma 16.

For large enough values of $s$ and $d$, and a suitable matrix
$N\in\mathrm{Mat}_{s}(\mathbb{Z}),$ the following problem is undecidable:
Given $A_{1},\ldots,A_{d}\in\mathrm{Mat}_{s}(\mathbb{Z})$, do there exist
$n_{1},\ldots,n_{d}\in\mathbb{N}$ with

$\mathrm{tr}(A_{1}^{n_{1}}\cdot A_{2}^{n_{2}}\cdots A_{d}^{n_{d}}\cdot N)<0?$

######  Problem 17.

Let $M\in\mathrm{Mat}_{s}(\mathcal{R})$ be a fixed matrix. For an input
$A\in\mathrm{Mat}_{s}(\mathcal{R})$, decide whether

$\mathrm{tr}(A^{n}\cdot M)\in\mathcal{P}$

holds for all $n\geqslant 1$.

######  Theorem 18.

If $s,d\in\mathbb{N}$ are large enough, and $M$ is chosen suitably, then 17 is
undecidable for $\mathcal{R}=\mathbb{Z}[x_{1},\ldots,x_{d}]$ and
$\mathcal{P}_{\rm coeff}$.

###### Proof.

Given $A_{1},\ldots,A_{d}\in\mathrm{Mat}_{s}(\mathbb{Z})$, set

$A=\sum_{i=1}^{d}\mathopen{}\mathclose{{}\left(\sum_{1\leqslant j\leqslant
i}e_{j}e_{i}^{t}}\right)\otimes A_{i}\cdot
x_{i}\in\mathrm{Mat}_{ds}(\mathcal{R}).$

Moreover, define

$M=mm^{t}\otimes N$

with $m=(1,\ldots,1)$ and $N$ as in Lemma 16. We have that

$\displaystyle\mathrm{tr}(A^{n}M)$ $\displaystyle=\sum_{1\leqslant
i_{1}\leqslant\cdots\leqslant i_{n}\leqslant
d}i_{1}\cdot\mathrm{tr}(A_{i_{1}}\cdots A_{i_{n}}\cdot N)\cdot x_{i_{1}}\cdots
x_{i_{n}}$
$\displaystyle=\sum_{n_{1}+\cdots+n_{d}=n}\underbrace{c_{n_{1},\ldots,n_{d}}}_{\geqslant
1}\cdot\mathrm{tr}(A_{1}^{n_{1}}\cdots A_{d}^{n_{d}}\cdot N)\cdot
x_{1}^{n_{1}}\cdots x_{d}^{n_{d}}$

where $c_{n_{1},\ldots,n_{d}}=\min\\{i\mid n_{i}\neq 0\\}.$ Thus 17 reduces to
the undecidable problem from Lemma 16. ∎

######  Remark 19.

Since the sequence $\mathrm{tr}(A^{n}M)$ is clearly a LRS (see Lemma 4), the
previous result shows that positivity of LRS over
$\mathcal{R}=\mathbb{Z}[x_{1},\ldots,x_{d}]$ is undecidable in general.
$\triangle$

###  4.2 Non-commutative polynomial rings

We now consider the ring $\mathcal{R}=\mathbb{Z}\langle
z_{1},\ldots,z_{d}\rangle$ of non-commutative polynomials, and show that its
moment membership problem is undecidable for the cone of polynomials with
positive coefficients. As a $\mathbb{Z}$-module, a basis of $\mathcal{R}$
consists of all words in the letters $z_{1},\ldots,z_{d}$ where the order of
letters does matter. Concatenation of words extends to a multiplication making
$\mathcal{R}$ a unital ring, where $1$ corresponds to the empty word. There is
a slightly different way to define this object, namely just as the tensor
algebra (cf. Example 1)

$\mathbb{Z}\langle z_{1},\ldots,z_{d}\rangle=T(\mathbb{Z}^{d}).$

The equivalence of definitions is apparent when identifying a word
$z_{k_{1}}\cdots z_{k_{m}}$ with the element $e_{k_{1}}\otimes\cdots\otimes
e_{k_{m}}\in\mathopen{}\mathclose{{}\left(\mathbb{Z}^{d}}\right)^{\otimes m},$
where $e_{r}$ denotes the $r$-th standard basis vector in $\mathbb{Z}^{d}$.

We equip $\mathcal{R}$ with two (a priori) different sets of positive
elements:

$\displaystyle\mathcal{P}_{\rm coeff}$
$\displaystyle\coloneqq\mathbb{Z}_{\geqslant 0}\langle
z_{1},\ldots,z_{d}\rangle=\mathopen{}\mathclose{{}\left\\{p\in\mathbb{Z}\langle
z_{1},\ldots,z_{d}\rangle\mid\mbox{all coefficients of }p\mbox{ are
nonnegative}}\right\\}$ $\displaystyle\mathcal{P}_{\rm eval}$
$\displaystyle\coloneqq\mathopen{}\mathclose{{}\left\\{p\in\mathbb{Z}\langle
z_{1},\ldots,z_{d}\rangle\mid\forall\ell,A_{1},\ldots,A_{d}\in\mathrm{Mat}_{\ell}(\mathbb{Z}_{\geqslant
0})\colon p(A_{1},\ldots,A_{d})\in\mathrm{Mat}_{\ell}(\mathbb{Z}_{\geqslant
0})}\right\\}.$

We now show that both cones coincide, which is a free version of Pólya’s
Theorem.

######  Theorem 20 (Free Pólya’s Theorem).

Let $p\in\mathbb{C}\langle z_{1},\ldots,z_{d}\rangle$ with
$m\coloneqq\deg(p)$. Then the following are equivalent:

  1. (i)

All coefficients of $p$ are nonnegative reals.

  2. (ii)

For all $A_{1},\ldots,A_{d}\in\mathrm{Mat}_{m+1}(\mathbb{Z}_{\geqslant 0})$ we
have

$p(A_{1},\ldots,A_{d})\in\mathrm{Mat}_{m+1}(\mathbb{R}_{\geqslant 0}).$

In particular, $\mathcal{P}_{\rm coeff}=\mathcal{P}_{\rm eval},$ and in the
definition of $\mathcal{P}_{\rm eval}$ one can restrict $\ell$ to $\deg(p)+1.$

###### Proof.

($i$) $\Rightarrow$ ($ii$) is obvious (even without the restriction on the
matrix size $m+1$). For ($ii$) $\Rightarrow$ ($i$) we construct matrices
$A_{1},\ldots,A_{d}$ that allow us to isolate a single coefficient of $p$.

Let $z_{k_{1}}\cdots z_{k_{\ell}}$ be a word in the letters
$z_{1},\ldots,z_{d}$. For $j=1,\ldots,d$ define

$A_{j}\coloneqq\sum_{i=1,\ldots,\ell;\
k_{i}=j}E_{i,i+1}\in\mathrm{Mat}_{\ell+1}(\mathbb{Z}_{\geqslant 0}),$

where $E_{i,j}$ denotes the matrix (of size $\ell+1$) with a $1$ in position
$(i,j)$ and zeros elsewhere. For $t_{1},\ldots,t_{r}\in\\{1,\ldots,d\\}$ we
have

$A_{t_{1}}\cdots A_{t_{r}}=\sum_{\tiny\begin{array}[]{c}i\\\ k_{i}=t_{1}\\\
k_{i+1}=t_{2}\\\ \vdots\\\
k_{i+r-1}=t_{r}\end{array}}E_{i,i+r}\in\mathrm{Mat}_{\ell+1}(\mathbb{Z}_{\geqslant
0}).$

In particular, the $(1,\ell+1)$-entry of a product $A_{t_{1}}\cdots A_{t_{r}}$
is $1$ if and only if $r=\ell$ and
$(k_{1},\ldots,k_{\ell})=(t_{1},\ldots,t_{\ell})$; in all other cases it is
zero. So $p(A_{1},\ldots,A_{d})$ contains in its upper right entry precisely
the coefficient of $p$ at the word $z_{k_{1}}\cdots z_{k_{\ell}}.$

Since all words appearing in $p$ are of length at most $\deg(p)=m$, we can do
this procedure with matrices $A_{j}$ of size at most $m+1$, and thus clearly
with matrices of size exactly $m+1$. ∎

######  Remark 21.

Pólya’s theorem [16, 8] states that for every homogeneous polynomial
$p\in\mathbb{R}[x_{1},\ldots,x_{d}]$ that is strictly positive on the
$d$-simplex

$\Delta_{d}\coloneqq\mathopen{}\mathclose{{}\left\\{(a_{1},\ldots,a_{d})\in\mathbb{R}^{d}\mid
a_{i}\geqslant 0,\sum_{i=1}^{d}a_{i}=1}\right\\},$

the polynomial

$(x_{1}+\cdots+x_{d})^{n}\cdot p(x_{1},\ldots,x_{d})$

has positive coefficients, for sufficiently large $n\in\mathbb{N}$. In Theorem
20, the space of nonnegative matrices takes the role of the $d$-simplex. While
in the commutative case we have to multiply $p$ with an additional polynomial,
this is not so in the free version.  $\triangle$

We now show that for these cones the moment membership problem is undecidable.

######  Theorem 22.

Let $d,s\geqslant 7$. Then the moment membership problem for
$\mathcal{R}=\mathbb{Z}\langle z_{1},\ldots,z_{d}\rangle$, $\mathcal{P}_{\rm
coeff}=\mathcal{P}_{\rm eval}$ and $s$ is undecidable. This remains true if we
restrict the instances to linear matrix polynomials, i.e.
$A\in\mathrm{Mat}_{s}(\mathbb{Z}\langle z_{1},\ldots,z_{d}\rangle)$ whose
entries are linear forms in $z_{1},\ldots,z_{d}$.

###### Proof.

For $A=\sum_{k=1}^{d}z_{k}A_{k}$ with $A_{k}\in\mathrm{Mat}_{s}(\mathbb{Z})$
we have

$\mu_{n}(A)=\sum_{k_{1},\ldots,k_{n}=1}^{d}\mathrm{tr}(A_{k_{1}}\cdots
A_{k_{n}})\cdot z_{k_{1}}\cdots z_{k_{n}}.$

So $\mu_{n}(A)\in\mathcal{P}_{\rm coeff}$ means that
$\mathrm{tr}(A_{k_{1}}\cdots A_{k_{n}})\geqslant 0$ for all
$k_{1},\ldots,k_{n}=1,\ldots,d$. Undecidability of this problem was proven in
[4, Lemma 3]. ∎

##  5 Conclusion

We have studied the moment membership problem (2) for matrices over a ring. We
have shown that there is a relation to LRS for commutative rings (Lemma 4 and
Lemma 5) and that the moments positivity problem is decidable in many cases,
including unitary and orthogonal matrices (Theorem 8 and Corollary 11) as well
as matrices with a unique dominating eigenvalue or only real eigenvalues
(Theorem 13). Finally, we have shown that the generalized moment membership
problem is undecidable over the ring of commutative and non-commutative
polynomials, where the positivity cone is given by the set of polynomials with
non-negative coefficients (Theorem 18 and Theorem 22).

The central open question remains, namely whether the moment membership
problem is decidable or undecidable for $\mathcal{R}=\mathbb{Q}$ and
$\mathcal{P}=[0,\infty)$. In the context of rings it would be interesting
whether it is undecidable for commutative polynomials for the cone of sum-of-
square polynomials or the non-negative polynomials. This might be the case, as
these cones have a richer structure than that of polynomials with nonnegative
coefficients.

## References

  * Bell et al. [2008] P. Bell, V. Halava, T. Harju, J. Karhumaki, and I. Potapov.  Matrix Equations and Hilbert’s Tenth Problem.  _Int. J. Algebra Comput._ , 18:1231–1241, 12 2008.  doi:10.1142/S0218196708004925.
  * Blondel and Portier [2002] V. D. Blondel and N. Portier.  The presence of a zero in an integer linear recurrent sequence is NP-hard to decide.  _Linear Algebra Appl._ , 351:91–98, 2002.  doi:10.1016/S0024-3795(01)00466-9.
  * Blondel et al. [2005] V. D. Blondel, E. Jeandel, P. Koiran, and N. Portier.  Decidable and undecidable problems about quantum automata.  _SIAM J. Comput._ , 34:1464–1473, 2005.  doi:10.1137/S0097539703425861.
  * De las Cuevas et al. [2016] G. De las Cuevas, T. S. Cubitt, J. I. Cirac, M. M. Wolf, and D. Pérez-García.  Fundamental limitations in the purifications of tensor networks.  _J. Math. Phys._ , 57(7):071902, 2016.  doi:10.1063/1.4954983.
  * De las Cuevas et al. [2021] G. De las Cuevas, A. Klingler, and T. Netzer.  Polynomial decompositions with invariance and positivity inspired by tensors.  _arXiv:2109.06680_ , 2021.  doi:10.48550/arXiv.2109.06680.
  * Everest et al. [2003] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward.  _Recurrence Sequences_.  American Mathematical Soc., 2003.  ISBN 1470423154.
  * Grosu [2011] R. Grosu.  The Cayley-Hamilton Theorem for Noncommutative Semirings.  In _Implementation and Application of Automata_ , pages 143–153, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.  ISBN 978-3-642-18098-9.  doi:10.1007/978-3-642-18098-9_16.
  * Hardy et al. [1952] G. H. Hardy, J. E. Littlewood, and G. Pólya.  _Inequalities_.  Cambridge University Press, 1952.
  * Klingler et al. [2023] A. Klingler, M. van der Eyden, S. Stengele, T. Reinhart, and G. De las Cuevas.  Many bounded versions of undecidable problems are NP-hard.  _SciPost Physics_ , 14(6):173, 2023.  doi:10.21468/SciPostPhys.14.6.173.
  * Lang [2012] S. Lang.  _Algebra_ , volume 211.  Springer Science & Business Media, 2012.  ISBN 9781461300410.
  * Martin et al. [1984] O. Martin, A. M. Odlyzko, and S. Wolfram.  Algebraic properties of cellular automata.  _Comm. Math. Phys._ , 93:219–258, 1984.
  * Onishchik and Vinberg [1990] A. Onishchik and E. Vinberg.  _Lie Groups and Algebraic Groups_.  Springer, 1990.
  * Ouaknine and Worrell [2012] J. Ouaknine and J. Worrell.  Decision problems for linear recurrence sequences.  In _International Workshop on Reachability Problems_ , pages 21–28. Springer, 2012.  doi:10.1007/978-3-642-33512-9_3.
  * Ouaknine and Worrell [2014a] J. Ouaknine and J. Worrell.  Positivity problems for low-order linear recurrence sequences.  In _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 366–379. ACM, New York, 2014a.
  * Ouaknine and Worrell [2014b] J. Ouaknine and J. Worrell.  On the positivity problem for simple linear recurrence sequences.  In _Automata, languages, and programming. Part II_ , volume 8573 of _Lecture Notes in Comput. Sci._ , pages 318–329. Springer, Heidelberg, 2014b.  doi:10.1007/978-3-662-43951-7_27.
  * Pólya [1928] G. Pólya.  Über positive Darstellung von Polynomen.  _Vierteljschr. Naturforsch. Ges. Zürich_ , 73(141-145):2, 1928.
  * Szigeti [2006] J. O. Szigeti.  Caley-Hamilton Theorem for Matrices over an arbitrary Ring.  _Serdica Math. J_ , 32:269–276, 2006.
  * Tausworthe [1965] R. C. Tausworthe.  Random numbers generated by linear recurrence modulo two.  _Mathematics of Computation_ , 19(90):201–209, 1965.
  * Tijdeman et al. [1984] R. Tijdeman, M. Mignotte, and T. Shorey.  The distance between terms of an algebraic recurrence sequence.  _Journal für die reine und angewandte Mathematik_ , 349:63–76, 1984.
  * Vereshchagin [1985] N. K. Vereshchagin.  The problem of appearance of a zero in a linear recurrence sequence.  _Mat. Zametki_ , 38(2):609–615, 1985.

##  Appendix A A version of the matrix mortality problem

In this appendix we prove Lemma 16 with a similar proof idea as in [4, 9],
which is based on a reduction from an undecidable version of the matrix
mortality problem.

We start with a version of the matrix mortality problem known to be
undecidable.

######  Problem 23 (Matrix Mortality version).

Let $A_{1},\ldots,A_{d}\in\mathrm{Mat}_{s}(\mathbb{Z})$. Does there exist a
choice of $n_{1},\ldots,n_{d}\in\mathbb{N}$ such that

$A_{1}^{n_{1}}\cdot A_{2}^{n_{2}}\cdots A_{d}^{n_{d}}=0?$

######  Theorem 24.

If $s$ and $d$ are large enough, then 23 is undecidable.

For a proof of Theorem 24 we refer to [1]. We are now ready to prove Lemma 16.

###### Proof of Lemma 16.

We provide a reduction from 23. First, fix the matrix

$N=\begin{pmatrix}\mathbf{0}&0\\\
0&1\end{pmatrix}+\sum_{i,j=1}^{s}\begin{pmatrix}E_{ij}\otimes E_{ij}&0\\\
0&0\end{pmatrix}\in\mathrm{Mat}_{s}(\mathbb{Z})^{\otimes
2}\oplus\mathbb{Z}\subseteq\mathrm{Mat}_{s^{2}+1}(\mathbb{Z})$

where $E_{ij}=e_{i}e_{j}^{t}$ with $e_{k}$ being the $k$th standard vector.
For every matrix in $\mathrm{Mat}_{s^{2}+1}(\mathbb{Z})$ of the form

$Y=\begin{pmatrix}X\otimes X&0\\\ 0&a\end{pmatrix}$

we have

$\mathrm{tr}(YN)=a+\sum_{i,j=1}^{s}X_{ij}^{2}.$

For an instance $A_{1},\ldots,A_{d}\in\mathrm{Mat}_{s}(\mathbb{Z})$ of 23,
define the following $d+1$ matrices:

$B_{i}=\begin{pmatrix}A_{i}\otimes A_{i}&0\\\ 0&1\end{pmatrix}\quad\text{ for
}i=1,\ldots,d$

and

$B_{d+1}=\begin{pmatrix}I_{s}\otimes I_{s}&0\\\ 0&-1\end{pmatrix}$

where $I_{s}$ is the identity matrix of size $s$.

Let $n_{1},\ldots,n_{d}\in\mathbb{N}$ be such that

$A_{1}^{n_{1}}\cdots A_{d}^{n_{d}}=0.$

Choosing $n_{d+1}=1$ we obtain

$\mathrm{tr}\mathopen{}\mathclose{{}\left(B_{1}^{n_{1}}\cdots
B_{d+1}^{n_{d+1}}\cdot
N}\right)=-1+\sum_{i,j=1}^{s}\mathopen{}\mathclose{{}\left(A_{1}^{n_{1}}\cdots
A_{d}^{n_{d}}}\right)_{ij}^{2}=-1<0.$

Conversely, let $n_{1},\ldots,n_{d+1}\in\mathbb{N}$ be such that
$\mathrm{tr}(B_{1}^{n_{1}}\cdots B_{d+1}^{n_{d+1}}\cdot N)<0$. This is only
possible for $n_{d+1}$ odd and

$\sum_{i,j=1}^{s}\mathopen{}\mathclose{{}\left(A_{1}^{n_{1}}\cdots
A_{d}^{n_{d}}}\right)_{ij}^{2}=0,$

which implies $A_{1}^{n_{1}}\cdots A_{d}^{n_{d}}=0$. ∎


# HiPart: Hierarchical Divisive Clustering Toolbox

Panagiotis Anagnostou<EMAIL_ADDRESS>Tasoulis<EMAIL_ADDRESS>Plagianakos<EMAIL_ADDRESS>
Department of Computer Science and Biomedical Informatics
University of Thessaly
Papasiopoulou 2-4, Lamia 35131, Greece Dimitris Tasoulis
<EMAIL_ADDRESS>
Signal Ocean SMPC
Leof. Vouliagmenis 110, Athina 11743, Greece

###### Abstract

This paper presents the HiPart package, an open-source native python library
that provides efficient and interpret-able implementations of divisive
hierarchical clustering algorithms. HiPart supports interactive visualizations
for the manipulation of the execution steps allowing the direct intervention
of the clustering outcome. This package is highly suited for Big Data
applications as the focus has been given to the computational efficiency of
the implemented clustering methodologies. The dependencies used are either
Python build-in packages or highly maintained stable external packages. The
software is provided under the MIT license. The package’s source code and
documentation can be found at https://github.com/panagiotisanagnostou/HiPart.

Keywords: Clustering, High dimensionality, Python

##  1 Introduction

A highly researched problem by a variety of research communities is the
problem of data clustering. However, high-dimensional data clustering still
constitutes a significant challenge, plagued by the _curse of dimensionality_
(Hutzenthaler et al., 2020). Hierarchical divisive algorithms developed in the
recent years (Tasoulis et al., 2010; Pavlidis et al., 2016; Hofmeyr, 2016;
Hofmeyr et al., 2019; Hofmeyr and Pavlidis, 2019) have shown great potential
for the particular case of high dimensional data, incorporating dimensionality
reduction iteratively within their algorithmic procedure. Additionally, they
seem unique in providing a hierarchical format of the clustering result with
low computational cost, in contrast to the commonly used but computationally
demanding agglomerative clustering methods.

Although the discovery of a hierarchical format is crucial in many fields,
such as bioinformatics (Luo et al., 2003; Modena et al., 2014), to the best of
our knowledge, this package is the first native python implementation of
divisive hierarchical clustering algorithms. We particularly focus on the
“Principal Direction Divisive Clustering (PDDP)” algorithm (Boley, 1998) for
its potential to effectively tackle the _curse of dimensionality_ and its
impeccable time performance (Tasoulis et al., 2010).

Simultaneously, we provide implementations of a complete set of hierarchical
divisive clustering algorithms with a similar basis. These are the dePDDP
(Tasoulis et al., 2010), the iPDDP (Tasoulis et al., 2010), the kM-PDDP
(Zeimpekis and Gallopoulos, 2008), and the bisecting k-Means (BKM) (Savaresi
and Boley, 2001). We also provide additional features not included in the
original developments of the aforementioned methodologies that make them
appropriate for the discovery of arbitrary shaped or non-linear separable
clusters. In detail, we incorporate kernel Principal Component Analysis (kPCA)
(Scholkopf et al., 1999) and Independent Component Analysis (ICA) (Hyvärinen
and Oja, 2000; Tharwat, 2020) for the iterative dimensionality reduction
steps.

As a result, the package provides a fully parameterized set of algorithms that
can be applied in a diverse set of applications, for example, non-linear
separable clusters, automated identification for the cluster number, and
outlier control.

##  2 Software Description

The HiPart (Hierarchical Partitioning) package is divided into three major
sections:

  * •

Method implementation

  * •

Static Visualization

  * •

Interactive Visualization

###  2.1 Method Implementation

The package employs an object-oriented approach for the implementation of the
algorithms, similarly to that of Bach et al. (2022), while incorporating
design similarities with the scikit-learn library (Pedregosa et al., 2011).
Meaning, a class executes each of the algorithms, and the class’s parameters
and attributes are the algorithm’s hyper-parameters and results.

For the execution of the algorithms, the user needs to call either the method
predict or fit_predict of each algorithm’s execution class. The algorithm
parameterization can be applied at the constructor of their respective class.

###  2.2 Static Visualization

Two static visualization methods are included. The first one is a
2-Dimensional representation of all the data splits generated by each
algorithm during the hierarchical procedure. The goal is to provide an insight
to the user regarding each node of the clustering tree and, subsequently, each
step of the algorithm’s execution.

The second visualization method is a dendrogram that represents the splits of
all the divisive algorithms. The dendrogram’s figure creation is implemented
by the _SciPy_ package, and it is fully parameterized as stated in the
library.

###  2.3 Interactive Visualization

In the interactive mode, we provide the possibility for stepwise manipulation
of the algorithms. The user can choose a particular step (node of the tree)
and manipulate the split-point on top of a two-dimensional visualization,
instantly altering the clustering result. Each manipulation resets the
algorithm’s execution from that step onwards, resulting in a restructuring of
the sub-tree of the manipulated node.

##  3 Development Notes

For the development of the package, we complied with the PEP8 style standards,
and we enforced it with the employment of _flake8_ command-line utility. To
ensure the code’s quality, we implemented the _unittest_ module to the
entirety of the source code. In addition, platform compatibility has been
assured through extensive testing, and the package development in its entirety
uses only well-established or native python packages. The package has been
released as open-source software under the “MIT License”. For more information
regarding potential contributions or for the submission of an issue, or a
request, the package is hosted as a repository on Github.

##  4 Experiments and Comparisons

In this section, we provide clustering results with respect to the execution
speed and clustering performance for the provided implementations. For direct
comparison, we employ a series of well-established clustering algorithms.
These are the k-Means (Likas et al., 2003), the Agglomerative (AGG) (Ackermann
et al., 2014) and the OPTICS (Ankerst et al., 1999) of the scikit-learn
(Pedregosa et al., 2011) python library and the fuzzy c-means (FCM) algorithm
(Bezdek et al., 1984) of the fuzzy-c-means (Dias, 2019) python package.
Clustering performance is evaluated using the Normalized Mutual Information
(NMI) score (Yang et al., 2016).

Four widely used data sets from the field of bioinformatics are employed along
with two popular data sets benchmark data set for text and image clustering,
respectively:

  * •

the Deng, (Deng et al., 2014)

  * •

the TGCA Pan-cancer111https://www.doi.org/10.7303/syn300013(Cancer),

  * •

the USPS, (Hull, 1994)

  * •

the Baron, (Baron et al., 2016)

  * •

the Chen, (Chen et al., 2017)

  * •

the BBC, (Greene and Cunningham, 2006),

All experiments took place on a server computer with Linux operating system,
kernel version 5.11.0, with an Intel Core i7-10700K CPU @ 3.80GHz and four
DDR4 RAM dims of 32GB with 2133MHz frequency. Default parameters were used for
the execution of all the algorithms, and the actual number of clusters was
provided to algorithms as a parameter when required.

In Table 1 we present the mean performance of all methods with respect to
execution time (time in secs) and NMI across 100 experiments. We observe that
HiPart implementations perform exquisitely in terms of execution time while
still being comparable with respect to clustering performance.

Algorithm | time | NMI | time | NMI |
---|---|---|---|---|---
| Deng (135, 12548) | Baron (1886, 14878) |  Gene Expression Data
iPDDP | 0.10 | 0.76 | 1.16 | 0.08
dePDDP | 0.14 | 0.70 | 2.16 | 0.53
PDDP | 0.15 | 0.54 | 2.55 | 0.53
kM-PDDP | 0.25 | 0.61 | 3.81 | 0.52
BKM | 0.50 | 0.64 | 11.51 | 0.52
k-Means | 0.14 | 0.71 | 7.52 | 0.48
AGG | 0.04 | 0.72 | 14.54 | 0.51
OPTICS | 27.78 | 0.48 | 710.99 | 0.13
FCM | 1.37 | 0.68 | 163.63 | 0.45
| Cancer (801, 20531) | Chen (14437, 23284)
iPDDP | 0.90 | 0.67 | 13.18 | 0.30
dePDDP | 1.06 | 0.93 | 20.71 | 0.36
PDDP | 1.04 | 0.74 | 37.52 | 0.48
kM-PDDP | 1.27 | 0.86 | 53.73 | 0.48
BKM | 5.94 | 0.88 | 255.85 | 0.48
k-Means | 1.54 | 0.98 | 249.72 | 0.48
AGG | 3.09 | 0.98 | 1218.68 | 0.49
OPTICS | 266.39 | 0.34 | 27089.35 | 0.00
FCM | 5.53 | 0.53 | 5710.83 | 0.26
| USPS (4575, 256) | BBC (2225, 21213) |  Benchmark Data
iPDDP | 0.02 | 0.55 | 2.02 | 0.60
dePDDP | 0.05 | 0.65 | 1.70 | 0.60
PDDP | 0.04 | 0.60 | 2.57 | 0.78
kM-PDDP | 0.17 | 0.50 | 2.93 | 0.74
BKM | 0.38 | 0.58 | 9.92 | 0.65
k-Means | 0.12 | 0.72 | 4.68 | 0.35
AGG | 1.15 | 0.77 | 23.18 | 0.64
OPTICS | 635.05 | 0.04 | 1055.75 | 0.06
FCM | 2.92 | 0.58 | 4.73 | 0.60

Table 1: Clustering results with respect to execution time and clustering
performance.

Figure 1: Dendrogram figure for the Cancer data set with the use of the dePDDP
algorithm and the dendrogram visualization module of the HiPart library. The
line below the tree represents the colour of the original cluster each sample
belongs.

##  5 Conclusions and Future Work

We present a highly time-efficient clustering package with a suite of tools
that give the capability of addressing problems in high-dimensional data
clustering. Also, the developed new visualization tools enhance understanding
and identification of the underlying clustering data structure.

We plan to continuously expand the HiPart package in the future through the
addition of more hierarchical algorithms and by providing even more options
for dimensionality reduction, such as the use of recent projection pursuit
methodologies (Pavlidis et al., 2016; Hofmeyr, 2016; Hofmeyr et al., 2019;
Hofmeyr and Pavlidis, 2019). Our final aim is to establish the golden standard
when considering hierarchical divisive clustering.

Acknowledgments

This project has received funding from the Hellenic Foundation for Research
and Innovation (HFRI), under grant agreement No 1901.

## References

  * Ackermann et al. (2014) Marcel R Ackermann, Johannes Blömer, Daniel Kuntze, and Christian Sohler.  Analysis of agglomerative clustering.  _Algorithmica_ , 69(1):184–215, 2014.
  * Ankerst et al. (1999) Mihael Ankerst, Markus M Breunig, Hans-Peter Kriegel, and Jörg Sander.  OPTICS: Ordering points to identify the clustering structure.  _ACM Sigmod record_ , 28(2):49–60, 1999.
  * Bach et al. (2022) Philipp Bach, Victor Chernozhukov, Malte S. Kurz, and Martin Spindler.  Doubleml - an object-oriented implementation of double machine learning in python.  _Journal of Machine Learning Research_ , 23(53):1–6, 2022.  URL http://jmlr.org/papers/v23/21-0862.html.
  * Baron et al. (2016) Maayan Baron, Adrian Veres, Samuel L Wolock, Aubrey L Faust, Renaud Gaujoux, Amedeo Vetere, Jennifer Hyoje Ryu, Bridget K Wagner, Shai S Shen-Orr, Allon M Klein, et al.  A single-cell transcriptomic map of the human and mouse pancreas reveals inter-and intra-cell population structure.  _Cell systems_ , 3(4):346–360, 2016.
  * Bezdek et al. (1984) James C. Bezdek, Robert Ehrlich, and William Full.  FCM: The fuzzy c-means clustering algorithm.  _Computers & Geosciences_, 10(2):191–203, 1984\.  ISSN 0098-3004.
  * Boley (1998) Daniel Boley.  Principal direction divisive partitioning.  _Data mining and knowledge discovery_ , 2(4):325–344, 1998.
  * Chen et al. (2017) Renchao Chen, Xiaoji Wu, Lan Jiang, and Yi Zhang.  Single-cell RNA-seq reveals hypothalamic cell diversity.  _Cell reports_ , 18(13):3227–3241, 2017.
  * Deng et al. (2014) Qiaolin Deng, Daniel Ramsköld, Björn Reinius, and Rickard Sandberg.  Single-cell RNA-seq reveals dynamic, random monoallelic gene expression in mammalian cells.  _Science_ , 343(6167):193–196, 2014.
  * Dias (2019) Madson Luiz Dantas Dias.  fuzzy-c-means: An implementation of fuzzy $c$-means clustering algorithm., May 2019.
  * Greene and Cunningham (2006) Derek Greene and Pádraig Cunningham.  Practical solutions to the problem of diagonal dominance in kernel document clustering.  In _Proc. 23rd International Conference on Machine learning (ICML’06)_ , pages 377–384. ACM Press, 2006.
  * Hofmeyr (2016) David P Hofmeyr.  Clustering by minimum cut hyperplanes.  _IEEE transactions on pattern analysis and machine intelligence_ , 39(8):1547–1560, 2016.
  * Hofmeyr and Pavlidis (2019) David P Hofmeyr and Nicos G Pavlidis.  PPCI: an R package for cluster identification using projection pursuit, 2019.
  * Hofmeyr et al. (2019) David P Hofmeyr, Nicos G Pavlidis, and Idris A Eckley.  Minimum spectral connectivity projection pursuit.  _Statistics and Computing_ , 29(2):391–414, 2019\.
  * Hull (1994) J.J. Hull.  A database for handwritten text recognition research.  _IEEE transactions on pattern analysis and machine intelligence_ , 16(5):550–554, 1994.  doi: 10.1109/34.291440.
  * Hutzenthaler et al. (2020) Martin Hutzenthaler, Arnulf Jentzen, Thomas Kruse, Tuan Anh Nguyen, and Philippe von Wurstemberger.  Overcoming the curse of dimensionality in the numerical approximation of semilinear parabolic partial differential equations.  _Proceedings of the Royal Society A_ , 476(2244):20190630, 2020.
  * Hyvärinen and Oja (2000) Aapo Hyvärinen and Erkki Oja.  Independent component analysis: algorithms and applications.  _Neural networks_ , 13(4-5):411–430, 2000.
  * Likas et al. (2003) Aristidis Likas, Nikos Vlassis, and Jakob J Verbeek.  The global k-means clustering algorithm.  _Pattern recognition_ , 36(2):451–461, 2003.
  * Luo et al. (2003) Feng Luo, Kun Tang, and Latifur Khan.  Hierarchical clustering of gene expression data.  In _Third IEEE Symposium on Bioinformatics and Bioengineering, 2003\. Proceedings._ , pages 328–335. IEEE, 2003.
  * Modena et al. (2014) Brian D Modena, John R Tedrow, Jadranka Milosevic, Eugene R Bleecker, Deborah A Meyers, Wei Wu, Ziv Bar-Joseph, Serpil C Erzurum, Benjamin M Gaston, William W Busse, et al.  Gene expression in relation to exhaled nitric oxide identifies novel asthma phenotypes with unique biomolecular pathways.  _American journal of respiratory and critical care medicine_ , 190(12):1363–1372, 2014.
  * Pavlidis et al. (2016) Nicos G Pavlidis, David P Hofmeyr, and Sotiris K Tasoulis.  Minimum density hyperplanes.  _Journal of Machine Learning Research_ , 2016.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Savaresi and Boley (2001) Sergio M Savaresi and Daniel L Boley.  On the performance of bisecting k-means and pddp.  In _Proceedings of the 2001 SIAM International Conference on Data Mining_ , pages 1–14. SIAM, 2001.
  * Scholkopf et al. (1999) Bernhard Scholkopf, Alexander Smola, and Klaus-Robert Müller.  Kernel principal component analysis.  In _ADVANCES IN KERNEL METHODS - SUPPORT VECTOR LEARNING_ , pages 327–352. MIT Press, 1999.
  * Tasoulis et al. (2010) S.K. Tasoulis, D.K. Tasoulis, and V.P. Plagianakos.  Enhancing principal direction divisive clustering.  _Pattern recognition_ , 43(10):3391–3411, 2010\.  ISSN 0031-3203.  doi: https://doi.org/10.1016/j.patcog.2010.05.025.
  * Tharwat (2020) Alaa Tharwat.  Independent component analysis: An introduction.  _Applied Computing and Informatics_ , 2020.
  * Yang et al. (2016) Zhao Yang, René Algesheimer, and Claudio J Tessone.  A comparative analysis of community detection algorithms on artificial networks.  _Scientific reports_ , 6(1):1–18, 2016.
  * Zeimpekis and Gallopoulos (2008) Dimitrios Zeimpekis and Efstratios Gallopoulos.  Principal direction divisive partitioning with kernels and k-means steering.  In _Survey of Text Mining II_ , pages 45–64. Springer, 2008.