# A deterministic algorithm for Harder-Narasimhan filtrations for
representations of acyclic quivers

chi-yu Cheng

###### Abstract.

Let $M$ be a representation of an acyclic quiver $Q$ over an infinite field
$k$. We establish a deterministic algorithm for computing the Harder-
Narasimhan filtration of $M$. The algorithm is polynomial in the dimensions of
$M$, the weights that induce the Harder-Narasimhan filtration of $M$, and the
number of paths in $Q$. As a direct application, we also show that when $k$ is
algebraically closed and when $M$ is unstable, the same algorithm produces
Kempf’s maximally destabilizing one parameter subgroups for $M$.

###### Key words and phrases:

Geometric invariant theory, Harder-Narasimhan filtration, representation of a
quiver, weight stability, slope stability, discrepancy.

###### 2010 Mathematics Subject Classification:

14Q20

###### Contents

  1. 1 Introduction
    1. 1.1 The main results
    2. 1.2 Outline of the paper
    3. 1.3 Acknowledgements
  2. 2 Stability conditions for representations of quivers
    1. 2.1 Set up
    2. 2.2 Slope stability
    3. 2.3 Weight stability
  3. 3 The main results
  4. 4 Completing B
    1. 4.1 Instability in affine geometric invariant theory
    2. 4.2 The quiver setting
    3. 4.3 From the Harder-Narasimhan filtration to maximally destabilizing one parameter subgroups
    4. 4.4 Maximizing Kempf function
  5. 5 A short example
    1. 5.0.1 Set up
    2. 5.0.2 Witnesses to the discrepancy
    3. 5.0.3 The Harder-Narasimhan filtration
    4. 5.0.4 Maximal destabilizing one parameter subgroups
  6. A Algebraic complexity towards the stability of representations of quivers
    1. A.1 Preliminaries
    2. A.2 Relating the two discrepancies

##  1\. Introduction

Our goal in this paper is to provide a constructive approach to Harder-
Narasimhan filtrations of representations of acyclic quivers. Specifically, we
first establish in A a link between the Harder-Narasimhan filtration and the
_discrepancy_ of a representation. The later notion, introduced in [CK21],
allows us to apply algebraic complexity tools to the study of Harder-
Narasimhan filtrations of representations of acyclic quivers. The main result,
Theorem 2 of [CK21] is a deterministic, polynomial time algorithm for finding
witnesses to the discrepancies of representations of bipartite quivers. Huszar
then extended the result to acyclic quivers in [Hus21] in Proposition 3.5
(Theorem 3.5 in our paper). Our first main result A affirms that for any
representation, its Harder-Narasimhan filtration has a term that witnesses its
discrepancy. So the next natural question to ask is that is there also a
systematic way to compute Harder-Narasimhan filtrations? Combining Theorem 3.5
and A, we are able to establish a deterministic algorithm, Algorithm 1 in B
that computes the Harder-Narasimhan filtration of a representation of an
acyclic quiver. We would like to point out that Algorithm 1 is not polynomial
in the number of edges of the quiver, but in the number of paths (see Theorem
3.7). When the quiver is bipartite where arrows only go from one partite to
the other, the number of arrows equals that of the paths. In this case
Algorithm 1 indeed has polynomial time complexity.

This paper was originally motivated by the relations between ”maximally
destabilizing subobjects” under different stability conditions in the case of
representations of quivers. Stability plays an important role in algebraic
geometry for constructing moduli spaces of algebro-geometric objects. In the
case of representations of quivers, two commonly used stability conditions are
weight stability and slope stability. We now briefly introduce the two
stability conditions, and we shall see that failing either one of them would
require some subobject that contradicts the condition. We let $Q$ be an
acyclic quiver.222The assumption that the quiver is acyclic is not required to
define either stability condition. Nevertheless, we will stick to acyclic
quivers throughout the paper for consistency, as the algorithm deals with
acyclic quivers only. That is, $Q$ does not have an oriented cycle, and we let
$Q_{0}$ denote the set of vertices of $Q$.

Weight stability was formulated in [Kin94] to construct moduli of
representations of finite dimensional algebras. King considered
representations of $Q$ of a fixed dimension $\mathbf{d}\in\mathbf{N}^{Q_{0}}$,
and a $\mathbf{Z}$-linear weight function
$\theta:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$ such that
$\theta(\mathbf{d})=0$. For a representation $M$ of $Q$, we let
$\boldsymbol{\dim}M\in\mathbf{N}^{Q_{0}}$ be its dimension vector. By
$\theta(M)$ we mean $\theta(\boldsymbol{\dim}M).$ King defined that for a
representation $M$ of dimension $\mathbf{d}$, $M$ is $\theta$-_semistable_ if
and only if $\theta(M^{\prime})\leq\theta(M)=0$ for every subrepresentation
$M^{\prime}$ of $M$. Otherwise, $M$ is $\theta$-_unstable_. Namely, there is a
subrepresntation $M^{\prime}$ of $M$ such that $\theta(M^{\prime})>0.$ In
[CK21], the _discrepancy_ of any representation $M$ _with respect to_ $\theta$
is defined to be the number

$\operatorname{disc}(M,\theta)=\max_{M^{\prime}\subseteq
M}\theta(M^{\prime}),$

where $M^{\prime}\subseteq M$ means $M^{\prime}$ is a subrepresentation of
$M$. We see that if $M$ is $\theta$-unstable, then the subrepresentation that
witnesses $\operatorname{disc}(M,\theta)$ contradicts $\theta$-semistability
of $M$ the most.

On the other hand, weight stability is in fact a reinterpretation of the
Hilbert-Mumford criterion (Theorem 4.3). When $M$ is $\theta$-unstable, the
original Hilbert-Mumford criterion states that there is a one parameter
subgroup (of the group to be defined in Section 4.2) that contradicts
$\theta$-semistability for $M$. Kempf showed in [Kem78] that among all
destabilizing one parameter subgroups, there is a unique indivisible one, up
to conjugation by a parabolic subgroup, that maximally contradicts
$\theta$-semistability in the numerical sense that will be made precise in
Section 4. The maximally destabilizing one parameter subgroups of an unstable
representation induce a unique filtration, which was referred to as Kempf
filtration in [Zam14]. The other type of filtration, known as the Harder-
Narasimhan filtration, comes from slope instability.

Slope stability depends on two weights
$\Theta,\kappa:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$, where
$\kappa((\mathbf{Z}^{+})^{Q_{0}})>0$. The slope $\mu$ of a nonzero
representation $M$ is defined as

$\mu(M)=\frac{\Theta(M)}{\kappa(M)}.$

Unlike weight stability, slope stability is defined for any nonzero
representation, whether its slope is zero or not. In [HdlPn02], a nonzero
representation $M$ is said to be $\mu$-semistable if
$\mu(M^{\prime})\leq\mu(M)\text{ for all }0\neq M^{\prime}\subseteq M.$ In
Section 2, we recall in Lemma 2.7 a way to go between weight and slope
stability. In any case, we shall stick to the following convention throughout
the paper, whose convenience will become apparent later: If a statement only
involves weight stability, we shall use the lower case $\theta$ as the weight.
When slope stability is involved, we use the upper case $\Theta$ as the
numerator of the slope.

The Harder-Narasimhan filtration of a representation $M$ with respect to $\mu$
is constructed inductively in [HdlPn02]. As the first step, set $M_{1}$ as the
unique subrepresentation that is maximal among all subrepresentations having
the highest slope. Such a subrepresentation is called the _strongly
contradicting semistability_(abbreviated as scss) _subrepresentation of_ $M$.
One then goes on to set $M_{i+1}/M_{i}$ as the scss subrepresentation of
$M/M_{i}$ until $M/M_{i}$ is $\mu$-semistable. The resulting filtration
$0\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r}=M$ is called the _Harder-
Narasimhan filtration_ of $M$.

We now have the following maximally destabilizing subobjects associated to an
unstable representation $M$:

  1. (1)

The discrepancy of $M$, and its witnessing subrepresentations (not necessarily
unique).

  2. (2)

The scss subrepresentation of $M$, and the Harder-Narasimhan filtration of
$M$.

  3. (3)

The one parameter subgroups that maximally contradict the semistability of
$M$, and the Kempf filtration induced by those one parameter subgroups.

The relation between (2) and (3) is already unraveled by the paper [Zam14].
The main result is that for an unstable representation, its Harder-Narasimhan
filtration coincides with its Kempf filtration. The first of our two main
results A establishes a link between (1) and (2). The second main result B
establishes a deterministic algorithm (Algorithm 1) for computing the Harder-
Narasimhan filtration and therefore the maximally destabilizing one parameter
subgroups of any unstable representation.

###  1.1. The main results

We let $Q$ be an acyclic quiver.

######  Theorem A (Lemma 3.1, Theorem 3.3, Corollary 3.4).

Let $\Theta$ be a weight and let $M$ be a representation of $Q$ with
$\Theta(M)=0$. For any weight $\kappa$ with
$\kappa((\mathbf{Z}^{+})^{Q_{0}})>0$, if $\mu=\Theta/\kappa$ is the slope
function, then any subrepresentation $M^{\prime}$ with
$\Theta(M^{\prime})=\operatorname{disc}(M,\Theta)$ contains the scss
subrepresentation of $M$ (with respect to $\mu$). Moreover, if

$0\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r-1}\subsetneq M_{r}=M$

is the Harder-Narasimhan filtration of $M$ (with respect to $\mu$), then there
is an $M_{l}$ in the filtration such that
$\Theta(M_{l})=\operatorname{disc}(M,\Theta)$.

It is noteworthy that the discrepancy depends only on $\Theta$, but the
Harder-Narasimhan filtration depends on $\mu$, which has an extra piece
$\kappa$. While the Harder-Narasimhan filtration of $M$ may change due to
different choices of $\kappa$, the results of A are independent of $\kappa$
for a fixed $\Theta$.

######  Theorem B (Theorem 3.7, Theorem 4.6).

Let $M$ be a representation of $Q$ over an infinite field. There exists a
deterministic algorithm to compute the Harder-Narasimhan filtration of $M$.
When the ground field is algebraically closed and when $M$ is unstable, a
maximally destabilizing one parameter subgroup for $M$ can be constructed
based on its Harder-Narasimhan filtration. Hence the algorithm also produces a
maximally destabilizing one parameter subgroup for $M$. Moreover, in the case
that $Q$ is bipartite where all arrows go from one partite to the other, the
algorithm has polynomial time complexity.

B is inviting for several purposes. First, finding Kempf’s maximally
destabilizing one parameter subgroups in general is very hard. Roughly
speaking, suppose $V$ is a representation of a reductive group $G$. If $G$ is
a torus, then finding Kempf’s one parameter subgroup for an unstable point
$v\in V$ is done by linear programming, whose constraints come from the states
of $v$. For a general reductive group, one can first restrict the action to a
maximal torus, then conduct linear programming on the entire orbit $G\cdot v$.
The set of states of all points in the orbit can be as large as the power set
of $\\{1,2,\ldots,\dim V\\}$, minus the empty subset. Hence the time
complexity to compute Kempf’s one parameter subgroups using brute force is
exponential. B provides an alternative to brute force for finding Kempf’s one
parameter subgroups in the context of representations of acyclic quivers. In
addition, if the quiver is bipartite as stated in B, the algorithm has
polynomial time complexity.

Second, [Hos14] shows that the stratification of the space of representations
of a quiver of a fixed dimension by Harder-Narasimhan types coincides with the
stratification by Kempf’s one parameter subgroups. Hence B sheds new light on
computing the stratification by either type.

###  1.2. Outline of the paper

We briefly recall slope stability (Definition 2.1), weight stability
(Definition 2.5), and a way to go between the two (Lemma 2.7) in Section 2. In
Section 3, we establish A (Lemma 3.1, Theorem 3.3, Corollary 3.4) and the
first part of B (Theorem 3.7). Specifically the first part of B constructs
Algorithm 1, and calculates its complexity. The second part of B constructs
maximally destabilizing one parameter subgroups for unstable representations
from their Harder-Narasimhan filtrations. Due to the technicality involved in
invariant theory, we postpone the second part of B to Section 4.

In Section 4.1, we recall the Hilbert-Mumford criterion (Theorem 4.3), and
define maximally destabilizing one parameter subgroups (Definition 4.4). We
also present Kempf’s main result, Theorem 4.5 from the paper [Kem78]. Theorem
4.5 describes the existence and the uniqueness of maximally destabilizing one
parameter subgroups. We then apply the machinery to the case of representation
of quivers at Section 4.2. Finally, we are able to finish the second part of B
at Theorem 4.6.

In Section 5, we construct an unstable representation to showcase that not all
subrepresentations that witness the discrepancy occur in the Harder-Narasimhan
filtration. We also provide two approaches to compute its maximally
destabilizing one parameter subgroups. The first one uses B and the second one
is the brute force procedure that can be applied to any representation of any
reductive group. Although the second approach works in more generality, the
cost will be apparent in the example. The point is to give the readers an idea
of the hardness of finding maximally destabilizing one parameter subgroups and
the value of B.

We note that our Algorithm 1 relies on Theorem 3.5, which is an algorithm that
computes discrepancies and was established in [Hus21]. Theorem 3.5 in turn is
a consequence of Theorem A.2 from [IQS18]. We supply an almost self-contained
account of how Theorem 3.5 is established based on Theorem A.2 at Appendix A.
Although this was the work of [Hus21], we intend to fill in some details not
supplied in the original paper. Here is a visualization of the logical
dependency of the results in our paper:

$\leavevmode\hbox to408.92pt{\vbox
to95.73pt{\pgfpicture\makeatletter\hbox{\hskip
253.8664pt\lower-47.86668pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}
{{}\pgfsys@rect{-252.9664pt}{-47.66669pt}{164.4997pt}{15.66602pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-249.63339pt}{-42.33368pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
<EMAIL_ADDRESS>}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}
{{}\pgfsys@rect{-192.53871pt}{-47.66669pt}{214.36087pt}{15.66602pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-189.2057pt}{-42.33368pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\lx@cref{creftypecap~refnum}{discrepancy_rep_algorithm}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}
{{}\pgfsys@rect{-23.9751pt}{-7.83301pt}{178.83304pt}{15.66602pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-20.64209pt}{-2.5pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\lx@cref{creftypecap~refnum}{Effective_alg_intro}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}
{{}\pgfsys@rect{-216.34428pt}{32.00067pt}{261.97202pt}{15.66602pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-213.01128pt}{37.33368pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\lx@cref{creftypecap~refnum}{HN_contains_Witness_to_disc_intro}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{}}{}
{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-10.6633pt}{0.0pt}\pgfsys@curveto{-10.6633pt}{5.31528pt}{-24.99706pt}{9.62404pt}{-42.67914pt}{9.62404pt}\pgfsys@curveto{-60.36122pt}{9.62404pt}{-74.69498pt}{5.31528pt}{-74.69498pt}{0.0pt}\pgfsys@curveto{-74.69498pt}{-5.31528pt}{-60.36122pt}{-9.62404pt}{-42.67914pt}{-9.62404pt}\pgfsys@curveto{-24.99706pt}{-9.62404pt}{-10.6633pt}{-5.31528pt}{-10.6633pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-42.67914pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-61.98473pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{Combine}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} { {}{}{}}{}{ {}{}{}}
{{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.4pt}\pgfsys@invoke{ }{}{{ {\pgfsys@beginscope
\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys<EMAIL_ADDRESS>{}{}{} {}{}{}
\pgfsys@moveto{-4.27998pt}{4.70642pt}\pgfsys@curveto{-3.49805pt}{1.88254pt}{-1.75558pt}{0.54909pt}{0.0pt}{0.0pt}\pgfsys@curveto{-1.75558pt}{-0.54909pt}{-3.49805pt}{-1.88254pt}{-4.27998pt}{-4.70642pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{-253.1664pt}{-39.83368pt}\pgfsys@lineto{-193.1387pt}{-39.83368pt}\pgfsys@stroke\pgfsys@invoke{
}\pgfsys@beginscope\pgfsys@invoke{
}{\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@moveto{-253.1664pt}{-39.83368pt}\pgfsys@lineto{-193.1387pt}{-39.83368pt}\pgfsys@stroke\pgfsys@invoke{
}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-192.9387pt}{-39.83368pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {
{}{}{}}{}{ {}{}{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{}{{}}}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.4pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-82.90767pt}{-31.80067pt}\pgfsys@curveto{-83.03326pt}{-20.17763pt}{-78.34875pt}{-11.85782pt}{-68.68993pt}{-6.14122pt}\pgfsys@stroke\pgfsys@invoke{
}\pgfsys@beginscope\pgfsys@invoke{
}{\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@moveto{-82.90767pt}{-31.80067pt}\pgfsys@curveto{-83.03326pt}{-20.17763pt}{-78.34875pt}{-11.85782pt}{-68.68993pt}{-6.14122pt}\pgfsys@stroke\pgfsys@invoke{
}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.86057}{0.50932}{-0.50932}{0.86057}{-68.51784pt}{-6.03935pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {
{}{}{}}{}{ {}{}{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{}{{}}}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.4pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-82.90767pt}{31.80067pt}\pgfsys@curveto{-83.03326pt}{20.17763pt}{-78.34875pt}{11.85782pt}{-68.68993pt}{6.14122pt}\pgfsys@stroke\pgfsys@invoke{
}\pgfsys@beginscope\pgfsys@invoke{
}{\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@moveto{-82.90767pt}{31.80067pt}\pgfsys@curveto{-83.03326pt}{20.17763pt}{-78.34875pt}{11.85782pt}{-68.68993pt}{6.14122pt}\pgfsys@stroke\pgfsys@invoke{
}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.86057}{-0.50932}{0.50932}{0.86057}{-68.51784pt}{6.03935pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
{{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.4pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-10.4633pt}{0.0pt}\pgfsys@lineto{-23.7751pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}\pgfsys@beginscope\pgfsys@invoke{
}{\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@invoke{
}\pgfsys@moveto{-10.4633pt}{0.0pt}\pgfsys@lineto{-23.7751pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{-23.9751pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
Finally, we will work with an arbitrary ground field throughout Section 2 and
Section 3 until Theorem 3.5. Originally, the machinery of Theorem 3.5 only
requires the ground field to have _enough_ elements. For simplicity we will
work with an infinite field, starting from Theorem 3.5. In Section 4, we will
assume further that the ground field is algebraically closed for the
formulation of Kempf’s maximally destabilizing one parameter subgroups.

###  1.3. Acknowledgements

The author would like to thank Calin Chindris for his support along the
preparation of this paper. The discussion with him and questions raised by him
offered many insights that fostered the results in the paper. The author also
gives thanks to Alfonso Zamora, Alana Huszar, and Gábor Ivanyos, Youming Qiao
for kindly answering the author’s questions on certain results in the paper
[Zam14], [Hus21], and [IQS18] respectively. Finally, the author thanks a
referee for clarifying the complexity of the algorithms presented.

##  2\. Stability conditions for representations of quivers

In this section we recall slope stability (Definition 2.1) and weight
stability (Definition 2.5) for representations of quivers.

Weight stability defined in this section is originally the Hilbert-Mumford
criterion (Theorem 4.3) formulated in [Kin94] in the context of
representations of quivers. For the purpose of the exposition of this paper,
we postpone a more detailed account of weight stability to Section 4. At the
end of this section we recall in Lemma 2.7 a way to translate between slope
stability and weight stability.

###  2.1. Set up

Let $k$ be a field, not necessarily algebraically closed. A quiver
$Q=(Q_{0},Q_{1},t,h)$ consists of $Q_{0}$ (vertices) and $Q_{1}$ (arrows)
together with two maps $t,h:Q_{1}\rightarrow Q_{0}$. The image of an arrow
under $t$ (resp. $h$) is the tail (resp. head) of the arrow. We represent $Q$
as a directed graph with vertices $Q_{0}$ and directed arrows $a:ta\rightarrow
ha$ for $a\in Q_{1}$. A _path_ in $Q$ is a composition of arrows in $Q$. We
give each vertex $v$ the trivial arrow $e_{v}:v\rightarrow v$. For any path
$p:x\rightarrow v$ (resp. $q:v\rightarrow y$), we set $e_{v}p=p$ (resp.
$qe_{v}=q$). We let $Q$ be a finite acyclic quiver throughout the paper. That
is, both $Q_{0}$ and $Q_{1}$ are finite, and $Q$ does not have any oriented
cycle other than the self-loops $\\{e_{v}\\}_{v\in Q_{0}}$. In this way, the
number of paths in $Q$ is finite.

A representation $M$ of $Q$ consists of a collection of finite dimensional
$k$-vector spaces $M_{v}$, for each $v\in Q_{0}$ together with a collection of
$k$-linear maps $M(a):M_{ta}\rightarrow M_{ha}$, for each $a\in Q_{1}$. For
each $v\in Q_{0}$, we set $M(e_{v}):M_{v}\rightarrow M_{v}$ to be the identity
map.

If $M,N$ are two representations of $Q$, then a morphism from $M$ to $N$ is a
collection of $k$-linear maps $\varphi_{v}:M_{v}\rightarrow N_{v}$ for each
$v\in Q_{0}$, such that $N(a)\varphi_{ta}=\varphi_{ha}M(a)$ for each $a\in
Q_{1}$. In particular, $M^{\prime}$ is a subrepresentation of $M$ whenever
each $M^{\prime}_{v}$ is a subspace of $M_{v}$ and each $M^{\prime}(a)$ is the
restriction of $M(a)$ to $M^{\prime}_{ta}$. We will write $M^{\prime}\subseteq
M$ if $M^{\prime}$ is a subrepresentation of $M$. We also note that the
collection of representations of $Q$ forms an abelian category.

The dimension vector of a representation $M$ of $Q$ is the tuple
$\boldsymbol{\dim}M\in\mathbf{Z}^{Q_{0}}$ where $(\boldsymbol{\dim}M)_{v}=\dim
M_{v}$ as a $k$-vector space for each $v\in Q_{0}$. A _weight_ is a
$\mathbf{Z}$-linear function $\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$. If
$\theta$ is a weight, we write $\theta(\boldsymbol{\dim}M)$ as $\theta(M)$.

For clarity, below is a summary of some important notations that we stick to
throughout the paper:

  * Notation

Let $M$ be a representation of $Q$. For each vertex $v\in Q_{0}$, we write
$M_{v}$ as the vector space of $M$ at $v$. For each $a\in Q_{1}$, $M(a)$
denotes the map $M_{ta}\rightarrow M_{ha}$ that is part of the data of $M$.
For any weight $\theta:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$, $\theta(v)$
instead of $\theta_{v}$ is the weight of $\theta$ at $v$. We also decree that
$\theta(M)$ means $\sum_{v\in Q_{0}}\theta(v)\dim M_{v}$. For a dimension
vector $\mathbf{d}\in\mathbf{Z}^{Q_{0}}$, we write $\mathbf{d}_{v}$ instead of
$\mathbf{d}(v)$ for its component at $v$.

###  2.2. Slope stability

In this section we recall semistability of representations of quivers with
respect to a slope, along with some important properties stated in Lemma 2.2
and Lemma 2.3. We then recall the construction from [HdlPn02] of the Harder-
Narasimhan filtration of a representation at Theorem 2.4. These results will
be widely used at Section 3.

Fix two weights $\Theta,\kappa:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$ where
we require $\kappa((\mathbf{Z}^{+})^{Q_{0}})>0$. We set
$\mu(M)=\Theta(M)/\kappa(M)$ for any nonzero representation $M$. We implicitly
assume that a representation is nonzero whenever the slope function is applied
to it.

######  Definition 2.1.

We say a representation $M$ of $Q$ is $\mu$-_semistable_ if $\mu(N)\leq\mu(M)$
for every subrepresentation $N$ of $M$.

######  Lemma 2.2 (Lemma 2.1 [HdlPn02] ).

Let $0\rightarrow L\rightarrow M\rightarrow N\rightarrow 0$ be a short exact
sequence of representations of $Q$. Then the following conditions are
equivalent:

  1. (1)

$\mu(L)\leq\mu(M)$,

  2. (2)

$\mu(L)\leq\mu(N)$,

  3. (3)

$\mu(M)\leq\mu(N)$.

A fundamental result is the following:

######  Lemma 2.3 (Lemma 2.2 [HdlPn02]).

Let $M$ be a representation of $Q$. There is a unique subrepresentation $N$
such that

  1. (1)

$\mu(N)$ is maximal among subrepresentations of $M$, and

  2. (2)

if $\mu(N^{\prime})=\mu(N)$, then $N^{\prime}\subseteq N$.

We call such a representation $N$ the _strongly contradicting
semistability_(abbreviated as scss) _subrepresentation of_ $M$.

######  Theorem 2.4 (Theorem 2.5 [HdlPn02]).

Let $M$ be a representation of $Q$. There is a unique filtration
$0=M_{0}\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r-1}\subsetneq M_{r}=M$
such that

  1. (1)

$\mu(M_{i}/M_{i-1})>\mu(M_{i+1}/M_{i})$ for $i=1,\ldots,r-1$,

  2. (2)

the representation $M_{i}/M_{i-1}$ is $\mu$-semistable for $i=1,\ldots,r$.

The above filtration is called the _Harder-Narasimhan filtration of_ $M$. It
is constructed by setting $M_{1}$ to be the scss subrepresentation of $M$,
then by inductively setting $M_{i+1}/M_{i}$ as the scss subrepresentation of
$M/M_{i}$ until $M/M_{i}$ is $\mu$-semistable.

###  2.3. Weight stability

Another stability condition on representations of quivers comes from GIT and
was introduced in [Kin94]. Like the slope stability we introduced earlier, GIT
stability also depends on a choice of parameters. In the case of
representations of quivers the parameter is a single weight. We therefore
refer to this stability condition as weight stability. We will relate weight
and slope stability in Lemma 2.7 at the end of this section.

######  Definition 2.5.

Let $\mathbf{d}\in\mathbf{Z}^{Q_{0}}$ be a dimension vector and let $\theta$
be a weight with $\theta(\mathbf{d})=0$. A representation $M$ with dimension
vector $\mathbf{d}$ is $\theta$-_semistable_ if $\theta(N)\leq 0$ for all
subrepresentations $N\subseteq M$.

The notion of _discrepancy_ was introduced in [CK21] to describe the
subrepresentations that contradict the weight stability the most. This very
notion allows us to compute the Harder-Narasimhan filtrations of
representations of an acyclic quiver using tools from algebraic complexity, as
we shall see in Section 3.

######  Definition 2.6.

Let $M$ be a representation and let $\theta$ be a weight. We do not require
$\theta(M)=0$. The _discrepancy of_ $M$ _with respect to_ $\theta$ is defined
as

$\operatorname{disc}(M,\theta)=\max_{N\subseteq M}\theta(N).$

We say a subrepresentation $N$ is $\theta$-_optimal in_ $M$, or $N$
_witnesses_ $\operatorname{disc}(M,\theta)$ if
$\theta(N)=\operatorname{disc}(M,\theta)$.

We recall the following way to go between weight stability and slope
stability:

######  Lemma 2.7.

Let $\Theta$ and $\kappa$ be two weights with $\kappa(N)>0$ for every nonzero
representation $N$. Let $\mu$ be the corresponding slope $\Theta/\kappa$. For
every dimension vector $\mathbf{d}\in\mathbf{Z}^{Q_{0}}$, define the new
weight

$\theta_{\mathbf{d}}(N):=\kappa(\mathbf{d})\Theta(N)-\Theta(\mathbf{d})\kappa(N)\text{
for each }N.$

Then a representation $M$ of dimension $\mathbf{d}$ is $\mu$-semistable if and
only if $M$ is $\theta_{\mathbf{d}}$-semistable. Moreover, the new slope
$\mu_{\mathbf{d}}=\theta_{\mathbf{d}}/\kappa$ defines the same slope stability
condition so that the Harder-Narasimhan filtrations of a representation with
respect to $\mu$ and $\mu_{\mathbf{d}}$ coincide.

###### Proof.

Let $M$ be a representation of dimension $\mathbf{d}$ and let $N\subset M$ be
any subrepresentation. We then have

$\begin{split}\mu(N)=\frac{\Theta(N)}{\kappa(N)}\leq\mu(M)=\frac{\Theta(\mathbf{d})}{\kappa(\mathbf{d})}\Leftrightarrow\kappa(\mathbf{d})\Theta(N)-\Theta(\mathbf{d})\kappa(N)=\theta_{\mathbf{d}}(N)\leq
0\end{split}$

The first statement follows.

For the second statement, simply note that

$\mu_{\mathbf{d}}(N)=\kappa(\mathbf{d})\cdot\mu(N)-\Theta(\mathbf{d}).$

Hence $\mu_{\mathbf{d}}$ is a positive scalar multiple of $\mu$, followed by a
translation. ∎

##  3\. The main results

Fix an acyclic quiver $Q$. In this section we prove two major results: Theorem
3.3 and Theorem 3.7. Theorem 3.3 provides a sufficient condition for the
Harder-Narasimhan filtration of a representation of $Q$ to contain a term that
witnesses the discrepancy. We then propose Algorithm 1 to compute the Harder-
Narasimhan filtrations of representations of $Q$. The correctness of Algorithm
1 is ensured by Proposition 3.6. We also recall the algebraic complexity
machinery Theorem 3.5 derived from [IQS18]. With the aid of Theorem 3.5, we
establish in Theorem 3.7 the time complexity of Algorithm 1. The derivation of
Theorem 3.5 is supplied in Appendix A for interested readers.

We fix two weights $\Theta,\kappa$ on $\mathbf{Z}^{Q_{0}}$ where $\kappa(N)>0$
for each non-zero representation $N.$ We let $\mu=\Theta/\kappa$ be the slope.
We do not assume anything about the ground field until Theorem 3.5, where we
will begin to assume the ground field is infinite.

We now present Lemma 3.1, which is the cornerstone of this paper.

######  Lemma 3.1.

Let $M$ be a $\mu$-unstable representation, and let $M_{1}$ be the scss
subrepresentation of $M$. Suppose $\Theta(M_{1})>0$ and $M^{\prime}$ is
$\Theta$-optimal in $M$. Then $M^{\prime}$ contains $M_{1}$. Moreover,
$M^{\prime}$ is $\mu$-semistable if and only if $M^{\prime}=M_{1}$.

###### Proof.

Note that $\Theta(M_{1})>0$ implies
$\operatorname{disc}(M,\Theta)=\Theta(M^{\prime})>0$. Suppose on the contrary
that $M_{1}\not\subset M^{\prime}$. We then have a proper inclusion
$M^{\prime}\subsetneq M_{1}+M^{\prime}$. In particular,
$\kappa(M^{\prime})<\kappa(M_{1}+M^{\prime})$. On the other hand,
$\Theta(M^{\prime})\geq\Theta(M_{1}+M^{\prime})$ as $M^{\prime}$ attains the
discrepancy. If $\Theta(M_{1}+M^{\prime})\leq 0$, we automatically have
$\mu(M^{\prime})>\mu(M_{1}+M^{\prime}).$ If $\Theta(M_{1}+M^{\prime})>0$, we
have

$\frac{\Theta(M^{\prime})}{\kappa(M^{\prime})}\geq\frac{\Theta(M_{1}+M^{\prime})}{\kappa(M^{\prime})}>\frac{\Theta(M_{1}+M^{\prime})}{\kappa(M_{1}+M^{\prime})}.$

In any case we deduce that $\mu(M^{\prime})>\mu(M_{1}+M^{\prime})$. By Lemma
2.2, the following short exact sequence

$0\rightarrow M^{\prime}\rightarrow
M_{1}+M^{\prime}\rightarrow(M_{1}+M^{\prime})/M^{\prime}\simeq
M_{1}/(M_{1}\cap M^{\prime})\rightarrow 0$

implies $\mu(M^{\prime})>\mu(M_{1}+M^{\prime})>\mu\big{(}M_{1}/(M_{1}\cap
M^{\prime})\big{)}$.

On the other hand, since $M_{1}$ is the scss subrepresentation of $M$, we have
$\mu(M_{1}\cap M^{\prime})\leq\mu(M_{1})$. Now Lemma 2.2 applied to the
following short exact sequence

$0\rightarrow M_{1}\cap M^{\prime}\rightarrow M_{1}\rightarrow
M_{1}/(M_{1}\cap M^{\prime})\rightarrow 0$

implies $\mu\big{(}M_{1}/(M_{1}\cap M^{\prime})\big{)}\geq\mu(M_{1})$. In sum,
we obtained

$\mu(M^{\prime})>\mu(M_{1}+M^{\prime})>\mu\big{(}M_{1}/(M_{1}\cap
M^{\prime})\big{)}\geq\mu(M_{1}).$

However, $M_{1}$ is the scss subrepresentation of $M$. We arrive at a
contradiction.

For the second implication of the lemma, if $M^{\prime}$ is the scss
subrepresentation of $M$, it is obviously $\mu$-semistable. Conversely, if
$M^{\prime}$ is $\mu$-semistable, since it contains $M_{1}$, we must have
$\mu(M_{1})\leq\mu(M^{\prime})$. This implies $\mu(M_{1})=\mu(M^{\prime})$ so
that $M^{\prime}=M_{1}$. ∎

Now we can make sense of the following proposition.

######  Proposition 3.2.

Let $M$ be a $\mu$-unstable representation, and let $M_{1}$ be the scss
subrepresentation of $M$ with $\Theta(M_{1})>0$. If $M^{\prime}$ is
$\Theta$-optimal in $M$, we then have

$\Theta(M^{\prime}/M_{1})=\operatorname{disc}(M/M_{1},\Theta).$

Namely, $M^{\prime}/M_{1}$ is $\Theta$-optimal in $M/M_{1}$.

###### Proof.

Suppose $N/M_{1}$ is $\Theta$-optimal in $M/M_{1}$. We then obviously have

$\Theta(M^{\prime}/M_{1})\leq\operatorname{disc}(M/M_{1},\Theta)=\Theta(N/M_{1}).$

This is equivalent to $\Theta(M^{\prime})\leq\Theta(N)$. However, $M^{\prime}$
is $\Theta$-optimal in $M$ by assumption. So we must have
$\Theta(M^{\prime})=\Theta(N)$, resulting in
$\Theta(M^{\prime}/M_{1})=\Theta(N/M_{1})=\operatorname{disc}(M/M_{1},\Theta)$.
The proposition is proved. ∎

######  Theorem 3.3.

Let $M$ be a $\mu$-unstable representation and let

$0\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r-1}\subsetneq M_{r}=M$

be its Harder-Narasimhan filtration. Suppose there is an integer $l$ such that
$\mu(M_{l}/M_{l-1})>0$ but $\mu(M_{l+1}/M_{l})\leq 0$. Then the term $M_{l}$
in the filtration is $\Theta$-optimal in $M.$ In addition, $M_{l}$ has the
highest slope among all $\Theta$-optimal subrepresentations.

###### Proof.

We will prove the theorem by induction on $l$. Let $l=1$. We need to show that
$\Theta(M_{1})\geq\Theta(M^{\prime})$ for every $M^{\prime}\subset M$. We
break this down into several steps.

  1. (1)

For any $M^{\prime}_{1}\subset M_{1}$, we show that
$\Theta(M_{1}^{\prime})\leq\Theta(M_{1})$.

  2. (2)

Next, assuming on the contrary that there is an $M^{\prime}\subset M$ with
$\Theta(M^{\prime})>\Theta(M_{1})$, we prove that such an $M^{\prime}$ induces
the proper inclusion $M_{1}\subsetneq M_{1}+M^{\prime}$.

  3. (3)

Finally, we deduce from step (1) and (2) that
$\mu\big{(}(M_{1}+M^{\prime})/M_{1})>\mu(M_{2}/M_{1}\big{)}$, contradicting
the fact that $M_{2}/M_{1}$ is the scss subrepresentation of $M/M_{1}$.

For step (1), suppose on the contrary that there is an
$M_{1}^{\prime}\subsetneq M_{1}$ such that
$\Theta(M_{1}^{\prime})>\Theta(M_{1})$. We would then have

$\mu(M_{1}^{\prime})=\frac{\Theta(M_{1}^{\prime})}{\kappa(M_{1}^{\prime})}>\frac{\Theta(M_{1})}{\kappa(M_{1}^{\prime})}>\frac{\Theta(M_{1})}{\kappa(M_{1})}=\mu(M_{1}).$

Note that again we are using the assumption that $\Theta(M_{1})$ is positive.
Since $M_{1}$ is the scss subrepresentation of $M$, we arrive at a
contradiction. Step (1) is completed.

For step (2), since $M_{1}$ is scss in $M$, we get
$\mu(M^{\prime})\leq\mu(M_{1})$. This together with the assumption that
$\Theta(M^{\prime})>\Theta(M_{1})$ imply $\kappa(M^{\prime})>\kappa(M_{1})$.
This clearly implies that $M^{\prime}$ is not contained in $M_{1}$ so that
$M_{1}\subsetneq M_{1}+M^{\prime}$, finishing step (2).

For step (3), simply note that
$\Theta(M^{\prime})>\Theta(M_{1})\geq\Theta(M_{1}\cap M^{\prime})$ by step
(1). We then have

$\begin{split}\mu\big{(}(M_{1}+M^{\prime})/M_{1}\big{)}&=\mu\big{(}M^{\prime}/(M_{1}\cap
M^{\prime})\big{)}=\frac{\Theta(M^{\prime})-\Theta(M_{1}\cap
M^{\prime})}{\kappa(M^{\prime})-\kappa(M_{1}\cap M^{\prime})}\\\
&>0\geq\mu(M_{2}/M_{1}).\end{split}$

These complete all three steps and therefore the base case of the induction.

If $\mu(M_{l+1}/M_{l})>0$ but $\mu(M_{l+2}/M_{l+1})\leq 0$, consider the
Harder-Narasimhan filtration for $M/M_{1}$:

$0\subsetneq M_{2}/M_{1}\subsetneq\cdots\subsetneq M/M_{1}.$

By the induction hypothesis,
$\Theta(M_{l+1}/M_{1})=\operatorname{disc}(M/M_{1},\theta)$. Moreover,
Proposition 3.2 implies
$\operatorname{disc}(M/M_{1},\Theta)=\operatorname{disc}(M,\Theta)-\Theta(M_{1})$.
Combining these two, we get $\Theta(M_{l+1})=\operatorname{disc}(M,\Theta)$,
as desired.

Finally, the maximality of slope of $M_{l}$ can also be proved by induction on
$l$, together with Lemma 3.1. ∎

######  Corollary 3.4.

Suppose $M$ is a $\mu$-unstable representation of $Q$, and $\Theta(M)=0$. Then
there exists a term $M_{i}$ in the Harder-Narasimhan filtration of $M$ such
that $\Theta(M_{i})=\operatorname{disc}(M,\Theta)$, and such that $M_{i}$ has
the highest slope among all subrepresentations of $M$ that witness
$\operatorname{disc}(M,\Theta)$.

###### Proof.

Let $0\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r}=M$ be the Harder-
Narasimhan filtration of $M$. The integer $l$ described in Theorem 3.3 must
exist. For if this is not the case, we then have

$0=\Theta(M)>\Theta(M_{r-1})>\cdots>\Theta(M_{1})>0,$

which is absurd. ∎

We now turn our attention to the computation of Harder-Narasimhan filtrations
for representations of $Q$. This comes down to computing the scss
subrepresentation. The main ideas come from Lemma 3.1, and the following
machinery that works for arbitrary infinite fields:

######  Theorem 3.5.

Let $Q$ be an acylcic quiver and let $M$ be a representation of $Q$ over an
infinite field. Fix a weight $\theta:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$
with $\theta(M)=0$. There is a deterministic algorithm that finds the
discrepancy $\operatorname{disc}(M,\theta)$, together with a subrepresentation
$M^{\prime}$ so that $\theta(M^{\prime})=\operatorname{disc}(M,\theta)$. If we
set $\Omega=\sum_{v\in Q_{0}}|\theta(v)|$, $K=\sum_{v\in Q_{0}}\dim M_{v}$,
and $P$ as the number of paths in $Q$, then the algorithm has run time
complexity that is polynomial in $\Omega,K,P$.

We refer interested readers to Appendix A for a proof of the theorem. It is
presented at Corollary A.8. We now explain how Lemma 3.1, together with the
algorithm of Theorem 3.5 can be applied for deriving the scss
subrepresentation. For convenience, we adopt the following notations:

  * Notation

For any representation $M$ of $Q$ of dimension $\mathbf{d}$, $F(M)$ denotes
the output subrepresentation of the algorithm in Theorem 3.5 applied to $M$
and to the weight $\theta_{\mathbf{d}}$. We let
$G(M)=\operatorname{disc}(M,\theta_{\mathbf{d}})=\theta_{\mathbf{d}}(F(M)).$

As a first instance of the convenience of notations just introduced, we can
say a representation $M$ is $\mu$-semistable (resp. $\mu$-unstable) if and
only if $G(M)=0$ (resp. $G(M)>0$) (see Lemma 2.7).

Now let $M=M^{0}$ be a representation of $Q$. If $G(M^{0})=0$, then $M^{0}$
itself is the scss subrepresentation. Otherwise, let $M^{1}=F(M^{0})$. Lemma
3.1 then dictates that $G(M^{1})=0$ if and only if $M^{1}$ is the scss
subrepresentation of $M$. If $G(M^{1})>0$, then $M^{2}=F(M^{1})$ is a proper
subrepresentation of $M^{1}$. We continue to produce $M^{i}=F(M^{i-1})$ if
$G(M^{i-1})>0$. The procedure must end in a finite number of steps as $M$ is
finite dimensional at each vertex, and each $M^{i}$ is a proper
subrepresentation of $M^{i-1}$. At the end, we have a filtration

$0\subsetneq M^{r}\subsetneq M^{r-1}\subsetneq\cdots\subsetneq M^{1}\subsetneq
M^{0},$

where

  1. (1)

$\theta_{\mathbf{d}_{i-1}}(M^{i})>0$,

  2. (2)

$M^{i}$ is $\theta_{\mathbf{d}_{i-1}}$-optimal in $M^{i-1}$, and

  3. (3)

$M^{r}$ is $\mu$-semistable.

The following proposition ensures that in this case $M^{r}$ is the scss
subrepresentation of $M$.

######  Proposition 3.6.

Let $0\subsetneq M^{r}\subsetneq\ldots\subsetneq M^{0}$ be a filtration of
representations of $Q$ and let
$\boldsymbol{\dim}M^{i}=\mathbf{d}_{i}\in\mathbf{Z}^{Q_{0}}$. Suppose for each
$i$,

$\theta_{\mathbf{d}_{i-1}}(M^{i})=\operatorname{disc}(M^{i-1},\theta_{\mathbf{d}_{i-1}})>0.$

Then $M^{r}$ is $\mu$-semistable if and only if $M^{r}$ is the scss
subrepresentation of $M^{i}$ for $i=0,\ldots,r-1$.

###### Proof.

The if part is trivial. The proof for the only if part can be carried out by
induction. We let $M_{1}^{i}$ be the scss subrepresentation of $M^{i}$.
Suppose $M^{r}$ is $\mu$-semistable. Then Lemma 3.1 (applied to
$\theta_{\mathbf{d}_{r-1}}$) implies $M^{r}=M^{r-1}_{1}$. Now suppose
$M^{r}=M^{i}_{1}$, we will show that $M^{r}=M^{i-1}_{1}$. For this, since
$M^{i}$ is $\theta_{\mathbf{d}_{i-1}}$-optimal in $M^{i-1}$, Lemma 3.1 implies
$M^{i}$ contains $M^{i-1}_{1}$. This immediately implies
$M^{i-1}_{1}=M^{i}_{1}$. By the induction hypothesis, $M^{r}=M^{i}_{1}$ so
that $M^{r}=M^{i-1}_{1}$, finishing the induction. ∎

We therefore propose the following algorithm to compute the Harder-Narasimhan
filtration of a representation of an acyclic quiver. The outer while loop
tests at each $i$-th step if $M/M_{i}$ is $\mu$-semistable. If not, the inner
while loop then computes the scss subrepresentation $M_{i+1}/M_{i}$ of
$M/M_{i}$. The correctness of the inner loop is established by Proposition
3.6. In the end of the algorithm we have $M_{1}$,
$M_{2}/M_{1},\ldots,M/M_{r-1}$ for some $r\geq 1$, where each $M_{i+1}/M_{i}$
is the scss subrepresentation of $M/M_{i+1}$, and $M/M_{r-1}$ is
$\mu$-semistable. From these the Harder-Narasimhan filtration for $M$ is
immediate.

Input:$\text{ A Representation }M\text{ of }Q$ Output:$\text{ The Harder-
Narasimhan filtration of }M$

if $G(M)=0$ then

$\text{return }M$ $\triangleright$ In this case $M$ is semistable, so the
filration is $M$ itself.

end if

while $G(M)>0$ do

$N\leftarrow F(M)$

while $G(N)>0$ do

$N\leftarrow F(N)$

end while

$\text{Record }N$ $\triangleright$ $N$ is the scss subrepresentation of $M$

$\text{Compute }M/N$

$M\leftarrow M/N$

end while

Algorithm 1 An algorithm for Harder-Narasimhan filtrations

We now show that the above algorithm satisfy the complexity bound given in the

######  Theorem 3.7.

Let $Q$ be an acyclic quiver and let $M$ be a representation of $Q$ over an
infinite field. Let $\Theta,\kappa:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$ be
two weights that define the slope $\mu=\Theta/\kappa$, $P$ be the number of
paths in $Q$, $\Omega=\sum_{v}|\Theta(v)|$, and let $K=\kappa(M)$. Algorithm 1
constructs the Harder-Narasimhan filtration of $M$ within time complexity that
is polynomial in $\Omega,K,$ and $P$.

Note that this is only the first part of B. We postpone the precise statement
and the proof of the second part to Theorem 4.6 at the end of the next
section.

###### proof of Theorem 3.7.

For starters, in the $i$-th outer while loop of Algorithm 1 ($i$ starts from
0), the first line uses the algorithm of Theorem 3.5 to test $\mu$-stability
of $M/M_{i}$. Let $\mathbf{d}^{i}$ be the dimension vector for the quotient
$M/M_{i}$. Theorem 3.5 states that the time complexity to determine stability
of $M/M_{i}$ is polynomial in $\sum_{v}|\theta_{\mathbf{d}^{i}}(v)|$,
$\sum_{v}\dim(M/M_{i})_{v}$, and $P$. Obviously the second term is bounded by
$K$. To bound the first term by a polynomial in $\Omega$ and $K$, we first
note that

$|\Theta(M/M_{i})|\leq\sum_{v}|\Theta(v)|\dim(M/M_{i})_{v}\leq\Omega K.$

Therefore

$\begin{split}\sum_{v}|\theta_{\mathbf{d}^{i}}(v)|&=\sum_{v}|\kappa(M/M_{i})\Theta(v)-\Theta(M/M_{i})\kappa(v)|\\\
&\leq\sum_{v}\kappa(M/M_{i})|\Theta(v)|+|\Theta(M/M_{i})|\kappa(v)\\\
&\leq\Omega K+\Omega K^{2}.\end{split}$

Hence, the first line of Algorithm 1 in the outer while loop has time
complexity polynomial in $\Omega,K,P$.

Next, in the $j$-th inner while loop, we are testing $\mu$-stability of some
subrepresentation $M^{j}_{i}/M_{i}$ of $M/M_{i}$ using Theorem 3.5. As before,
the time complexity is bounded by a polynomial in $\Omega,K,P.$ Since there
are at most $\sum_{v}\dim M_{v}\leq K$ many inner while loops, completing the
inner while loop has again time complexity polynomial in $\Omega,K,P$.

After the inner loop, we arrive at the scss subrpresentation $M_{i+1}/M_{i}$
of $M/M_{i}$. To compute a basis for the quotient $(M/M_{i+1})_{v}$ at each
vertex $v$, we may compute a basis for a complement of $(M_{i+1}/M_{i})_{v}$
in $(M/M_{i})_{v}$. This can be done by computing the null space of the basis
matrix for $(M_{i+1}/M_{i})_{v}$, which has complexity
$O\big{(}\dim(M_{i+1}/M_{i})_{v}^{2}\dim(M/M_{i})_{v}\big{)}.$ The complexity
to compute bases at all vertices can therefore be bounded by $O(K^{3})$. Next,
for each arrow $a\in Q_{1}$, the map $(M/M_{i+1})(a)$ can be obtained via the
following change of bases to the original map

$(M/M_{i})(a):(M_{i+1}/M_{i})_{ta}\oplus(M/M_{i+1})_{ta}\rightarrow(M_{i+1}/M_{i})_{ha}\oplus(M/M_{i+1})_{ha},$

which has time complexity bounded by $O(K^{3})$. Therefore, the time
complexity to compute the quotient $M/M_{i+1}$ is bounded by a polynomial in
$K$ and $P.$

In sum, we showed that each outer while loop has time complexity polynomial in
$\Omega,K,P$. Since there can be at most $\sum_{v}\dim M_{v}\leq K$ outer
loops, the total time complexity is still polynomial in $\Omega,K,P$. ∎

##  4\. Completing B

The major goal of this section is to complete B. That is, we are going to
construct a maximally destabilizing one parameter subgroup from the Harder-
Narasimhan filtration of an unstable representation. This is where GIT comes
into play.

GIT stability and its numerical criterion, known as the Hilbert-Mumford
criterion (Theorem 4.3), were established by Mumford in [MFK94]. The Hilbert-
Mumford criterion reduces testing stability for reductive group actions to one
dimensional torus actions. This is done by restricting the action to one
parameter subgroups of the reductive group. Mumford first conjectured the
existence of the one parameter subgroups that fail the numerical criterion
maximally. The conjecture was then resolved by Kempf in his famous paper
[Kem78]. Beyond existence Kempf actually established the uniqueness of
maximally destabilizing one parameter subgroups up to conjugacy by some
parabolic subgroup (Theorem 4.5).

In Section 4.1, we will first recall Mumford’s definition of stability
(Definition 4.1) and the Hilbert-Mumford criterion (Theorem 4.3) in the affine
setting. We then make precise the meaning of maximally destabilizing one
parameter subgroups (Definition 4.4), and present Kempf’s theorem (Theorem
4.5).

We then apply these machinery in the context of representations of quivers in
Section 4.2. Finally in Section 4.3, we recall in Theorem 4.6 a way due to
[Zam14] to construct a maximally destabilizing one parameter subgroup from the
Harder-Narasimhan filtration of an unstable representation. This would
complete B.

###  4.1. Instability in affine geometric invariant theory

Here we recall necessary notions and theorems from affine GIT. We work with a
fixed algebraically closed field $k$. Let $G$ be a reductive group acting on
an affine variety $X$. We let $\boldsymbol{\Gamma}(G)$ denote the set of one
parameter subroups of $G$. We fix a norm $||-||$ on $\boldsymbol{\Gamma}(G)$.
The norm would satisfy the following two properties:

  1. (1)

$||-||$ is invariant under conjugation. Namely, for any $g\in G$ and any
$\lambda\in\boldsymbol{\Gamma}(G)$, we have

$||\lambda||=||g\lambda g^{-1}||.$

  2. (2)

For any maximal torus $T\subset G$, the restriction of $||-||$ to the lattice
$\boldsymbol{\Gamma}(T)$ is induced by an inner product on the vector space
$\boldsymbol{\Gamma}(T)\otimes\mathbf{R}$ that is integral on
$\boldsymbol{\Gamma}(T)\times\boldsymbol{\Gamma}(T)$.

For the precise notion of a norm on the set of one parameter subgroups, we
refer the readers to page 58 of [MFK94].

Stability in GIT depends on the choice of a linearized line bundle. In the
affine setting, a character $\chi:G\rightarrow k^{\times}$ of $G$ induces a
linearization of the trivial line bundle $\mathscr{O}_{X}$. Fix a character
$\chi$.

For any one parameter subgroup $\lambda:k^{\times}\rightarrow G$ of $G$, we
let $\langle\chi,\lambda\rangle$ be the integer that satisfies
$(\chi\circ\lambda)(t)=t^{\langle\chi,\lambda\rangle}$ for all $t\in
k^{\times}$.

######  Definition 4.1.

An element $f\in k[X]$ is $\chi$-_invariant of weight d_ if $f(g\cdot
x)=\chi^{d}(g^{-1})f(x)$ for all $g\in G$ and for all $x\in X$. We say a point
$x\in X$ is $\chi$-_semistable_ if there is a $\chi$-invariant $f$ of positive
weight such that $f(x)\neq 0$. We say a point $x\in X$ is $\chi$-_unstable_ if
$x$ is not $\chi$-semistable. We write $X^{\text{ss}}(\chi)$ as the set of
$\chi$-semistable points in $X$ and $X^{\text{us}}(\chi)$ as the complement
$X-X^{\text{ss}}(\chi).$

It follows from the definition that $X^{\text{ss}}(\chi)$ is a $G$-invariant
open subvariety and that $X^{\text{us}}(\chi)$ is a $G$-invariant closed
subvariety. Moreover, $X^{\text{ss}}(\chi)=X^{\text{ss}}(\chi^{d})$ for any
$d>0$.

######  Remark 4.2 ([MFK94]).

Let $k[X]_{\chi,d}$ be the space of $\chi$-invariant elements of weight $d$.
The space $\oplus_{d\geq 0}k[X]_{\chi,d}$ has a natural graded ring structure.
Let

$X/\\!\\!/_{\chi}G:=\operatorname{Proj}(\oplus_{d\geq 0}k[X]_{\chi,d}).$

Then there is a map $X^{\text{ss}}(\chi)\rightarrow X/\\!\\!/_{\chi}G$ that is
constant on $G$-orbits, submersive and induces a bijection between points in
$X/\\!\\!/_{\chi}G$ and closed orbits in $X^{\text{ss}}(\chi)$. Moreover,
$X/\\!\\!/_{\chi}G$ is a quasi-projective variety that is known as _the GIT
quotient of X by G with respect to_ $\chi$.

We now introduce the Hilbert-Mumford criterion, which tests stability by
restricting the group action to certain one parameter subgroups. Let
$\lambda:k^{\times}\rightarrow G$ be a one parameter subgroup and let $x\in X$
be a point. We say $\lim\limits_{t\rightarrow 0}\lambda(t)\cdot x$ exists if
the domain of the map $\lambda_{x}:k^{\times}\rightarrow X$ defined by
$t\mapsto\lambda(t)\cdot x$ can be extended to the entire affine line.

######  Theorem 4.3.

(Hilbert-Mumford criterion [MFK94], [Kin94]) A point $x\in X$ is
$\chi$-semistable if and only if for each one parameter subgroup
$\lambda:k^{\times}\rightarrow G$ such that $\lim\limits_{t\rightarrow
0}\lambda(t)\cdot x$ exists, we have $\langle\chi,\lambda\rangle\leq 0$.

Next, we define a numerical measure for instabilities contributed by
destabilizing one parameter subgroups. For a point $x\in X$, set

$C_{x}=\\{\lambda\in\boldsymbol{\Gamma}(G)|\lim_{t\rightarrow
0}\lambda(t)\cdot x\text{ exits}\\}.$

According to Theorem 4.3, $x\in X^{\text{us}}(\chi)$ if and only if there is a
one parameter subgroup $\lambda$ such that

  1. (1)

$\lambda\in C_{x}$, and

  2. (2)

$\langle\chi,\lambda\rangle>0$.

Therefore, for an $x\in X^{\text{us}}(\chi)$, it is natural to ask if there is
a one parameter subgroup that contributes to the highest instability measured
by the quantities $\langle\chi,\lambda\rangle$ among all $\lambda\in C_{x}$.
An immediate problem is that
$\langle\chi,\lambda^{N}\rangle=N\cdot\langle\chi,\lambda\rangle$ for any
$N\in\mathbf{N}$. To get rid of the dependency on multiples of one parameter
subgroups, we divide the function
$\langle\chi,-\rangle:\boldsymbol{\Gamma}(G)\rightarrow\mathbf{Z}$ by the norm
$||-||$ on $\boldsymbol{\Gamma}(G)$.

For $x\in X^{\text{us}}(\chi)$, we set

$\mathcal{M}^{\chi}(x):=\sup_{\lambda\in
C_{x}\backslash\\{0\\}}\frac{\langle\chi,\lambda\rangle}{||\lambda||}.$

######  Definition 4.4.

We say a one parameter subgroup $\lambda$ is _indivisible_ if $\lambda$ is a
primitive lattice in a (and hence in any) maximal torus containing $\lambda$.
We say a one parameter subgroup $\lambda$ is $\chi$-_adapted to_ $x$ if
$\frac{\langle\chi,\lambda\rangle}{||\lambda||}=\mathcal{M}^{\chi}(x)$. We let
$\Lambda^{\chi}(x)$ denote the set of indivisible one parameter subgroups that
are $\chi$-adapted to $x$.

We also recall that for any one parameter subgroup $\lambda$, there is the
associated parabolic subgroup

$P(\lambda)=\\{g\in G\mid\lim_{t\rightarrow 0}\lambda(t)g\lambda(t)^{-1}\text{
exists in }G\\}$

of $G$. An important property about $P(\lambda)$ we want to mention is that it
preserves filtration in the following sense: Let $V$ be a representation of
$G$ and let $\oplus_{n\in\mathbf{Z}}V^{(n)}$ be the weight decomposition of
some one parameter subgroup $\lambda$ of $G$. Namely, $\lambda$ acts on
$V^{(n)}$ with weight $n$. Suppose $p\in P(\lambda)$, we then have

$p\cdot V^{(\geq n)}=V^{(\geq n)}$

where $V^{(\geq n)}=\oplus_{m\geq n}V^{(m)}$.

We are now ready for Kempf’s theorem from [Kem78]:

######  Theorem 4.5.

(Kempf) Let $G$ be a reductive group, acting on an affine variety $X$. Let
$\chi$ be a character of $G$, and let $x\in X$ be a $\chi$-unstable point.
Then

  1. (1)

$\Lambda^{\chi}(x)$ is not empty;

  2. (2)

For any $g\in G$, $\Lambda^{\chi}(g\cdot x)=g\Lambda^{\chi}(x)g^{-1}$, and
$\mathcal{M}^{\chi}(g\cdot x)=\mathcal{M}^{\chi}(x)$;

  3. (3)

There is a parabolic subgroup $P(\chi,x)$ of $G$ such that for all
$\lambda\in\Lambda^{\chi}(x)$, $P(\lambda)=P(\chi,x)$, and such that any two
elements of $\Lambda^{\chi}(x)$ are conjugate to each other by an element in
$P(\chi,x)$.

###  4.2. The quiver setting

We now unpack what these machineries mean in the case of representation of
quivers. For starters, let us fix an acyclic quiver $Q$, and a dimension
vector $\mathbf{d}\in\mathbf{Z}^{Q_{0}}$. By $\operatorname{GL}(n)$ we mean
the linear algebraic group of invertible $n\times n$ matrices with entries in
$k$. Let the linear algebraic group

$\operatorname{GL}(\mathbf{d}):=\prod_{v\in
Q_{0}}\operatorname{GL}(\mathbf{d}_{v})$

act on the $k$-vector space

$R(Q,\mathbf{d}):=\prod_{a\in
Q_{1}}\operatorname{Hom}_{k}(k^{\mathbf{d}_{ta}},k^{\mathbf{d}_{ha}})$

via the following law:

$(g\cdot\phi)_{a}=g_{ha}\circ\phi_{a}\circ(g_{ta})^{-1}\text{ for any }g\in
G,\phi\in R(Q,\mathbf{d}).$

In this way, the $\operatorname{GL}(\mathbf{d})$-orbits in $R(Q,\mathbf{d})$
correspond to the isomorphism classes of representations of $Q$ of dimension
$\mathbf{d}$. A weight $\theta:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$
defines a character $\chi_{\theta}:\operatorname{GL}(\mathbf{d})\rightarrow
k^{\times}$ by

$\chi_{\theta}(g)=\prod_{v\in Q_{0}}\det(g_{v})^{\theta(v)}\text{ for any
}g\in\operatorname{GL}(\mathbf{d}).$

We fix a weight $\theta$ with $\theta(\mathbf{d})=0$.

Let $M$ be a representation of $Q$ of dimension $\mathbf{d}$. Since
$\chi_{\theta}$-stability is constant on
$\operatorname{GL}(\mathbf{d})$-orbits, different choices of bases for each
$M_{v}$ does not affect the $\chi_{\theta}$-stability of the corresponding
elements of $M$ in $R(Q,\mathbf{d})$. From now on we fix an identification
$M_{v}\simeq\mathbf{R}^{\mathbf{d}_{v}}$ for each $v$, and still write the
identification of $M$ in $R(Q,\mathbf{d})$ as $M.$

We now recall the following relation between weighted filtrations of $M$, and
the one parameter subgroups having limits at $M$, namely, the one parameter
subgrous in $C_{M}$. Any one parameter subgroup $\lambda\in C_{M}$ induces a
weighted filtration

$0=M_{0}\subsetneq M_{1}\subsetneq M_{2}\subsetneq\cdots\subsetneq M_{s}=M,$

where $\lambda$ acts on each quotient $M_{i}/M_{i-1}$ with weight
$\Gamma_{i}$. Moreover, the weights enjoy the following property:
$\Gamma_{1}>\Gamma_{2}>\cdots>\Gamma_{s}$ (see [Kin94]).

Conversely, given a weighted filtration $0=M_{0}\subsetneq
M_{1}\subsetneq\cdots\subsetneq M_{s}=M$ with weights
$\Gamma_{1}>\cdots>\Gamma_{s}$, we may choose new bases for $M$ at all
vertices that are compatible with the filtration. Namely, choose a basis for
$M_{1}$, then extends the basis to $M_{2},M_{3}$, and so on. We then let
$g_{v}\in\operatorname{GL}(\mathbf{d}_{v})$ be the one parameter subgroup that
acts on $(M_{i}/M_{i-1})_{v}$ by weight $\Gamma_{i}$. In this way, the one
parameter subgroup $\lambda=\prod_{v\in Q_{0}}g_{v}$ of
$\operatorname{GL}(\mathbf{d})$ induces the original filtration. Moreover,
since $\theta(M)=0$, we have

(4.1)
$\langle\chi_{\theta},\lambda\rangle=\sum_{i=1}^{s}\Gamma_{i}\theta(M_{i}/M_{i-1})=\sum_{i=1}^{s-1}(\Gamma_{i}-\Gamma_{i+1})\theta(M_{i}).$

In particular, for any proper subrepresentation $M^{\prime}$ of $M$, one may
form the filtration $0\subsetneq M^{\prime}\subsetneq M$, and assign weights
$\Gamma_{1},\Gamma_{2}$ to $M^{\prime}$ and $M$ respectively, where
$\Gamma_{1}$ is any integer and $\Gamma_{2}=\Gamma_{1}-1$. It then follows
from the above discussion and eq. 4.1 that there is a one parameter subgroup
$\lambda$ with $\langle\chi_{\theta},\lambda\rangle=\theta(M^{\prime})$. In
view of Theorem 4.3, we see that $M$ is $\chi_{\theta}$-semistable if and only
if $\theta(M^{\prime})\leq 0$ for any subrepresentation $M^{\prime}$ of $M$.
This was the definition, Definition 2.5 we used for weight stability.

###  4.3. From the Harder-Narasimhan filtration to maximally destabilizing one
parameter subgroups

In this section, we address how to derive a maximally destabilizing one
parameter subgroup of an unstable representation $M$ of $Q$ from its Harder-
Narasimhan filtration. We need to set up appropriate weights and slope.

Let $\Theta,\kappa:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$ be two weights,
and let $\mu=\Theta/\kappa$ be the associated slope function. Suppose
$\boldsymbol{\dim}M=\mathbf{d}.$ Recall that we defined the weight
$\theta_{\mathbf{d}}$ where

$\theta_{\mathbf{d}}(N):=\kappa(\mathbf{d})\Theta(N)-\Theta(\mathbf{d})\kappa(N)\text{
for any representation }N.$

With these we have that $\theta_{\mathbf{d}}(M)=0$, and that $M$ is
$\mu$-semistable if and only if it is $\chi_{\theta_{\mathbf{d}}}$-semistable
(Lemma 2.7).

We now define a norm $||-||$ on
$\boldsymbol{\Gamma}(\operatorname{GL}(\mathbf{d}))$. This norm will depend on
the weight $\kappa$. We first build the norm on the diagonal maximal torus
$T\subset\operatorname{GL}(\mathbf{d})$. There is a natural identification

$\boldsymbol{\Gamma}(T)_{\mathbf{R}}\simeq\bigoplus_{v\in
Q_{0}}\mathbf{R}^{\mathbf{d}_{v}}.$

We weight the standard norm on $\mathbf{R}^{\mathbf{d}_{v}}$ by $\kappa(v)$
for each $v$. More explicitly, if $\lambda\in\boldsymbol{\Gamma}(T)$ with
$\lambda_{v}=(\lambda_{1,v},\ldots,\lambda_{\mathbf{d}_{v},v})$, we set

(4.2) $||\lambda||=\big{(}\sum_{v\in
Q_{0}}\sum_{i=1}^{\mathbf{d}_{v}}\kappa(v)(\lambda_{i,v})^{2}\big{)}^{1/2}.$

This norm $||-||$ extends to the entire set
$\Gamma(\operatorname{GL}(\mathbf{d}))$ and is invariant under conjugation. We
refer the readers to page 58 in [MFK94] for a detailed discussion on the
construction of norms on the set of one parameter subgroup of a reductive
group.

Therefore, whenever $\lambda\in C_{M}$ (that is, $\lim_{t\rightarrow
0}\lambda(t)\cdot M$ exists), its norm can be expressed in terms of its
weights and the filtration it induces: If $0=M_{0}\subsetneq
M_{1}\subsetneq\cdots\subsetneq M_{s}=M$ is the filtration induced by
$\lambda$ with weights $\Gamma_{1}>\cdots>\Gamma_{s}$, then

(4.3) $||\lambda||=\big{(}\sum_{i=1}^{s}\sum_{v\in
Q_{0}}\kappa(v)\Gamma_{i}^{2}\dim(M_{i}/M_{i-1})_{v}\big{)}^{1/2}=\big{(}\sum_{i=1}^{s}\Gamma_{i}^{2}\kappa(M_{i}/M_{i-1})\big{)}^{1/2}.$

We adopt the above norm to define (using Definition 4.4) one parameter
subgroups that are $\chi_{\theta_{\mathbf{d}}}$-adapted to $M$.

Since all one parameter subgroups that are
$\chi_{\theta_{\mathbf{d}}}$-adapted to $M$ are in a full conjugacy class of
their parabolic subgroup (Theorem 4.5), the filtrations induced by those one
parameter subgroups are the same. In [Zam14], such a filtration is named as
the Kempf filtration of $M$. By Theorem 5.3 from [Zam14], it is also the
Harder-Narasimhan filtration for $M$ with respect to the slope $\mu$. In
addition, there is the following recipe for reverse engineering a maximally
destabilizing one parameter subgroup from the Harder-Narasimhan filtration.

######  Theorem 4.6 (Theorem 4.1, Lemma 5.2 [Zam14]).

Let $\Theta,\kappa:\mathbf{Z}^{Q_{0}}\rightarrow\mathbf{Z}$ be two weights and
let $\mu=\Theta/\kappa$ be the slope. Let $M$ be a $\mu$-unstable
representation of dimension $\mathbf{d}$, and let

$0=M_{0}\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r}=M$

be the Harder-Narasimhan filtration. Set

$u_{i}=\kappa(M)\mu(M_{i}/M_{i-1})-\Theta(M)\text{ for }i=1,\ldots,r.$

Choose a basis for $M_{v}$ for each vertex $v$ compatible with the filtration,
and let $T\subset\operatorname{GL}(\mathbf{d})$ be the maximal torus diagonal
with respect to these bases. Define
$\tilde{\lambda}\in\boldsymbol{\Gamma}(T)_{\mathbf{Q}}\simeq\oplus_{v\in
Q_{0}}\mathbf{Q}^{\mathbf{d}_{v}}$ where for each $i$ and $v$, the entries of
$\tilde{\lambda}_{v}$ that correspond to $(M_{i}/M_{i-1})_{v}$ are $u_{i}$.
Then the lattice points on the ray $\mathbf{Q}_{>0}\cdot\tilde{\lambda}$ are
the one parameter subgroups in $T$ that are
$\chi_{\theta_{\mathbf{d}}}$-adapted to $M$. Moreover,

$\mathcal{M}^{\chi_{\theta_{\mathbf{d}}}}(M)=\big{(}\sum_{i=1}^{r}(\kappa(M)\mu(M_{i}/M_{i-1})-\Theta(M))^{2}\kappa(M_{i}/M_{i-1})\big{)}^{1/2}.$

######  Remark 4.7.

In the case that $\Theta(M)=0$ in the first place, one can take

$u_{i}=\mu(M_{i}/M_{i-1}),$

and

$\begin{split}\mathcal{M}^{\chi_{\Theta}}(M)&=\big{(}\sum_{i}\mu(M_{i}/M_{i-1})^{2}\kappa(M_{i}/M_{i-1})\big{)}^{1/2}\\\
&=\big{(}\sum_{i}\Theta(M_{i}/M_{i-1})\mu(M_{i}/M_{i-1})\big{)}^{1/2}.\end{split}$

Therefore, knowing the Harder-Narasimhan filtration of an unstable
representation is equivalent to knowing its maximally destabilizing one
parameter subgroups. A full treatment of B is now complete. An account of the
correctness of the construction in Theorem 4.6 is given in the next section
for interested readers.

###  4.4. Maximizing Kempf function

Let $M$ be a $\mu$-unstable representation of $Q$ of dimension $\mathbf{d}$
with the Harder-Narasimhan filtration

$0=M_{0}\subsetneq M_{1}\subsetneq\cdots\subsetneq M_{r}=M.$

By Theorem 5.3 from [Zam14], the filtration is the same as the Kempf
filtration. Recall that $C_{M}$ denotes the set of one parameter subgroups
having limits at $M$. Let

$f:C_{M}\backslash\\{\mathbf{0}\\}\rightarrow\mathbf{R}$

be the function defined by

$f(\lambda)=\frac{\langle\chi_{\theta_{\mathbf{d}},\lambda}\rangle}{||\lambda||}.$

To maximize this function, we can restrict the search range to the set of one
parameter subgroups that induce the Kempf filtration, which is also the
Harder-Narasimhan filtration.

Consider the inner product
$(-,-):\mathbf{R}^{r}\times\mathbf{R}^{r}\rightarrow\mathbf{R}$ defined by the
matrix

$\begin{pmatrix}\kappa(M_{1})&&&0\\\ &\kappa(M_{2}/M_{1})&&\\\ &&\ddots&\\\
0&&&\kappa(M/M_{r-1})\end{pmatrix}.$

If $\lambda$ is a one parameter subgroup that induces the Harder-Narasimhan
filtration of $M$ with the weight vector
$\Gamma=(\Gamma_{1},\ldots,\Gamma_{s})$, then upon using $\theta_{\mathbf{d}}$
as $\theta$ in equation (4.1), we derive that

(4.4)
$\begin{split}\langle\chi_{\theta_{\mathbf{d}}},\lambda\rangle&=\sum_{i}\Gamma_{i}\big{(}\kappa(M)\Theta(M_{i}/M_{i-1})-\Theta(M)\kappa(M_{i}/M_{i-1})\big{)}\\\
&=\sum_{i}\Gamma_{i}\kappa(M_{i}/M_{i-1})\big{(}\kappa(M)\mu(M_{i}/M_{i-1})-\Theta(M)\big{)}\\\
&=(\Gamma,u),\end{split}$

where $u_{i}=\kappa(M)\mu(M_{i}/M_{i-1})-\Theta(M)$. Moreover, eq. 4.3 implies
$||\lambda||=(\Gamma,\Gamma)^{1/2}$.

Letting $u=(u_{1},\ldots,u_{r})\in\mathbf{R}^{r}$, we define the function

$g_{u}:\mathbf{R}^{r}\backslash\\{\mathbf{0\\}}\rightarrow\mathbf{R}$

where

$g_{u}(x)=\frac{(x,u)}{\sqrt{(x,x)}}.$

This function is called the Kempf function in [Zam14]. We see that maximizing
$f$ among all one parameter subgroups inducing the Kempf filtration is
equivalent to maximizing the Kempf function $g_{u}$ on the open cone
$C=\\{x\in\mathbf{R}^{r}\mid x_{1}>x_{2}>\cdots>x_{r}\\}.$ By the Cauchy-
Schwarz inequality, $g_{u}$ attains global maximum at $u$. Since
$\mu(M_{1})>\mu(M_{2}/M_{1})>\cdots>\mu(M/M_{r})$, $u$ is already in the cone
$C$. Therefore, the one parameter subgroup constructed in Theorem 4.6
maximizes $f$.

##  5\. A short example

In this example we construct an unstable representation of a bipartite quiver
and compute the following:

  1. (1)

Several witnesses to the discrepancy;

  2. (2)

The Harder-Narasimhan filtration;

  3. (3)

A maximally destabilizing one parameter subgroup.

We compare the results of (1), (2) with Theorem 3.3, and demonstrate that not
all optimal subrepresentations occur in the Harder-Narasimhan filtration. For
(3), we present two approaches. The first approach applies Theorem 4.6 to the
Harder-Narasimhan filtration obtained in (2), and the second is a sketch of
the brute force procedure that can be applied to any representation of any
reductive group. By doing so we hope to give readers a sense of the hardeness
of finding Kempf’s one parameter subgroups in general. The set up of this
example is motivated by [CK21].

####  5.0.1. Set up

Let us consider the following representation $M$ of the following bipartite
quiver over the field $\mathbf{C}$ of complex numbers:

$\mathbf{C}$$\mathbf{C}$$\mathbf{C}$$\mathbf{C}$$\mathbf{C}^{4}$.$a_{1}$$a_{2}$$a_{3}$$a_{4}$

Label the four vertices on the left by $x_{1},x_{2},x_{3},x_{4}$ from top to
bottom. Label the single vertex on the right as $y$ so that
$M_{x_{i}}=\mathbf{C}$ for each $i=1,\ldots,4$, and $M_{y}=\mathbf{C}^{4}$.

We set $M(a_{1})(1)=e_{2},M(a_{2})(1)=e_{1},M(a_{3})(1)=2e_{1}$, and
$M(a_{4})(1)=e_{3}$ in $\mathbf{C}^{4}$, where $e_{1},\ldots,e_{4}$ form the
standard basis of $\mathbf{C}^{4}$. We let $\Theta$ and $\kappa$ be two
weights where $\Theta(x_{i})=4$, $\Theta(y)=-4$, and
$\kappa(x_{i})=\kappa(y)=1$ for each $i$. It then follows that $\Theta(M)=0$.
We also let $\mu(-)=\Theta(-)/\kappa(-)$ be the corresponding slope.

We let $\operatorname{Sp}(e_{1})$ be the largest subrepresentation
$M^{\prime}$ of $M$ such that $M^{\prime}_{y}=\operatorname{Span}(e_{1})$.
Specifically,

$\operatorname{Sp}(e_{1})_{x_{i}}=\begin{cases}\mathbf{C}\text{ if }i=2,3,\\\
0\text{ if i=1,4},\end{cases}$

and

$\operatorname{Sp}(e_{1})_{y}=\operatorname{Span}(e_{1}).$

We define $\operatorname{Sp}(e_{1},e_{2}),\operatorname{Sp}(e_{1},e_{3}),$ and
$\operatorname{Sp}(e_{1},e_{2},e_{3})$ similarly.

####  5.0.2. Witnesses to the discrepancy

We verify that the four subrepresentations $\operatorname{Sp}(e_{1})$,
$\operatorname{Sp}(e_{1},e_{2})$, $\operatorname{Sp}(e_{1},e_{3})$,
$\operatorname{Sp}(e_{1},e_{2},e_{3})$ are $\Theta$-optimal in $M$ with
$\Theta$ value 4. For this, note that for any subrepresentation $M^{\prime}$
of $M$,

$\Theta(M^{\prime})\leq 4\cdot\big{(}\\#\\{i\mid
M^{\prime}_{x_{i}}=\mathbf{C}\\}-\dim(\operatorname{Span}(\\{M(a_{i})(1)\mid
M^{\prime}_{x_{i}}=\mathbf{C}\\}))\big{)}.$

Therefore, for $\Theta(M^{\prime})$ to be positive, $M^{\prime}_{x_{2}}$ and
$M^{\prime}_{x_{3}}$ must be equal to $\mathbf{C}$. The only proper
subrepresentations of $M$ that are nonzero at $x_{2},x_{3}$ with positive
$\Theta$ values are exactly the four subrepresentations listed above. Since
they all have the same $\Theta$ value 4, they are also $\Theta$-optimal and
$\operatorname{disc}(M,\Theta)=4$.

####  5.0.3. The Harder-Narasimhan filtration

We verify that

$0\subsetneq\operatorname{Sp}(e_{1})\subsetneq\operatorname{Sp}(e_{1},e_{2},e_{3})\subsetneq
M$

is the Harder-Narasimhan filtration of $M$. For this, it is clear that
$\operatorname{Sp}(e_{1})$ is the only subrepresentation with the highest
slope $4/3$. We may infer that $\operatorname{Sp}(e_{1})$ is the scss
subrepresentation of $M$. Moving on to $M/\operatorname{Sp}(e_{1})$, since
$\operatorname{Sp}(e_{1})$ is $\Theta$-optimal, we can infer
$\mu(M^{\prime}/\operatorname{Sp}(e_{1}))\leq 0$ for any subrepresentation
$M^{\prime}$ containing $\operatorname{Sp}(e_{1})$. Since

$\mu(\operatorname{Sp}(e_{1},e_{2})/\operatorname{Sp}(e_{1}))=\mu(\operatorname{Sp}(e_{1},e_{3})/\operatorname{Sp}(e_{1}))=\mu(\operatorname{Sp}(e_{1},e_{2},e_{3})/\operatorname{Sp}(e_{1}))=0,$

we infer that the quotient
$\operatorname{Sp}(e_{1},e_{2},e_{3})/\operatorname{Sp}(e_{1})$ is the scss
subrepresentation of $M/\operatorname{Sp}(e_{1})$. The quotient
$M/\operatorname{Sp}(e_{1},e_{2},e_{3})$ is one dimensional on $y$ and zero
elsewhere. We conclude that $M/\operatorname{Sp}(e_{1},e_{2},e_{3})$ is
$\mu$-semistable and that the filtration written above is the Harder-
Narasimhan filtration of $M$.

Here we note that the two $\Theta$-optimal subrepresentations
$\operatorname{Sp}(e_{1},e_{2})$ and $\operatorname{Sp}(e_{1},e_{3})$ are not
included in the filtration. We see in this example that not all optimal
subrepresentations occur in the Harder-Narasimhan filtration. Also note that
$\operatorname{Sp}(e_{1})$ has the highest slope among all $\Theta$-optimal
subrepresentations. This agrees with the implications of Theorem 3.3 because
$\mu(\operatorname{Sp}(e_{1}))=4/3>0=\mu(\operatorname{Sp}(e_{1},e_{2},e_{3})/\operatorname{Sp}(e_{1}))$.
Namely, $\operatorname{Sp}(e_{1})$ serves as $M_{l}$ in the description of
Theorem 3.3.

####  5.0.4. Maximal destabilizing one parameter subgroups

We now demonstrate a maximally destabilizing one parameter subgroup for $M$
with respect to the weight $\Theta$ and the norm weighted by $\kappa$. The
first thing to do is to reproduce the GIT set up introduced in Section 4.2. To
begin with, we have the vector space $\prod_{a\in
Q_{1}}\operatorname{Hom}_{\mathbf{C}}(\mathbf{C},\mathbf{C}^{4})\simeq\mathbf{C}^{4\times
4}$. Each column of a matrix in $\mathbf{C}^{4\times 4}$ defines a map from a
left vertex to the right vertex. We let the first column define a map from
$x_{1}$ to $y$, and so on. In this way, the group
$G=(\mathbf{C}^{\times})^{4}\times\operatorname{GL}(4)$ acts on
$\mathbf{C}^{4\times 4}$ via the rule

$(t_{1},t_{2},t_{3},t_{4},A)\cdot U=A\cdot
U\cdot\begin{pmatrix}t_{1}^{-1}&&&\\\ &t_{2}^{-1}&&\\\ &&t_{3}^{-1}&\\\
&&&t_{4}^{-1}\end{pmatrix}$

for all $(t_{1},t_{2},t_{3},t_{4},A)\in G$ and for all
$U\in\mathbf{C}^{4\times 4}$. There is the diagonal torus
$D\simeq(\mathbf{C}^{\times})^{4}$ in $\operatorname{GL}(4)$. Let
$T=(\mathbf{C}^{\times})^{4}\times D\subset G$ be the maximal torus in $G$. We
then have $\boldsymbol{\Gamma}(T)_{\mathbf{Q}}\simeq\mathbf{Q}^{8}$. With the
notations introduced in Theorem 4.6, we have

$u_{1}=\frac{4}{3},u_{2}=0,u_{3}=-4$

by Remark 4.7. The maximally destabilizing one parameter subgroups in $T$ is
then on the positive ray of the point

$(\underbrace{0,\frac{4}{3},\frac{4}{3},0}_{x_{1},x_{2},x_{3},x_{4}},\underbrace{\frac{4}{3},0,0,-4}_{y}).$

We now sketch a procedure using linear programming. Here we do not assume we
know the Harder-Narasimhan filtration in the first place. Recall that $\Theta$
defines the character $\chi_{\Theta}$ of $G$ where

$\chi_{\Theta}(t_{1},t_{2},t_{3},t_{4},A)=(t_{1}t_{2}t_{3}t_{4})^{4}\cdot\det(A)^{-4}$

for all $(t_{1},t_{2},t_{3},t_{4},A)\in G$. The representation $M$ corresponds
to the matrix $\begin{pmatrix}0&1&2&0\\\ 1&0&0&0\\\ 0&0&0&1\\\
0&0&0&0\end{pmatrix}.$ Let us continue to use $M$ to represent the matrix.

If $\lambda(t)=(t^{a_{1}},\ldots,t^{a_{8}})$ is a one parameter subgroup in
$T$, then

$\lambda(t)\cdot M=\begin{pmatrix}0&t^{-a_{2}+a_{5}}&2\cdot
t^{-a_{3}+a_{5}}&0\\\ t^{-a_{1}+a_{6}}&0&0&0\\\ 0&0&0&t^{-a_{4}+a_{7}}\\\
0&0&0&0\end{pmatrix}.$

We see that $\lim_{t\rightarrow\infty}\lambda(t)\cdot M$ exists if and only if

(5.1) $\begin{cases}-a_{1}+a_{6}\geq 0\\\ -a_{2}+a_{5}\geq 0\\\
-a_{3}+a_{5}\geq 0\\\ -a_{4}+a_{7}\geq 0\end{cases}.$

One also easily calculates that

$\langle\chi_{\Theta},\lambda\rangle=4(a_{1}+a_{2}+a_{3}+a_{4})-4(a_{5}+a_{6}+a_{7}+a_{8}).$

The norm on the set of one parameter subgroups of $T$ is weighted by $\kappa$.
In this case it is simply the standard norm. Therefore, to find one parameter
subgroups in $T$ that maximally destabilize $M$, we are maximizing the
function

$f=\frac{4(a_{1}+a_{2}+a_{3}+a_{4})-4(a_{5}+a_{6}+a_{7}+a_{8})}{(a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+a_{4}^{2}+a_{5}^{2}+a_{6}^{2}+a_{7}^{2}+a_{8}^{2})^{1/2}},$

with the side constraints given by eq. 5.1. With the help of SageMath, we
calculated that $f$ attains maximum on the positive ray of the point
$(0,\frac{4}{3},\frac{4}{3},0,\frac{4}{3},0,0,-4)$.

Notice that the constraints depends only on the nonzero entries of $M$. That
is, replacing the nonzero entries of $M$ by any other nonzero scalars does not
change the linear programming problem. The set of the positions of the nonzero
entries of $M$ is called the support of $M$.

We must be aware that up to this point, we are only calculating one parameter
subgroups in $T$. In general, maximally destabilizing one parameter subgroups
of an unstable point do not have to be in a particular maximal torus. To work
with a particular maximal torus, one needs to enumerate all supports coming
from the orbit of the unstable point, conduct linear programming for each
support, and choose the maximum result. Often times the challenge is to
determine the supports of points in the orbit. Beyond that the number of
supports of points in the orbit can be quite large, leading to vast amount of
linear programming required. As we can see, enumerating supports of $g\cdot M$
for all $g\in G$ in this relatively small example already gets tedious. We
shall not continue this brute force procedure here, as the main point to
illustrate the hardness of finding Kempf’s one parameter subgroups in general,
and to demonstrate the value of Theorem 4.6 is made.

## References

  * [CK21] Calin Chindris and Daniel Kline.  Simultaneous robust subspace recovery and semi-stability of quiver representations.  J. Algebra, 577:210–236, 2021.
  * [HdlPn02] Lutz Hille and José Antonio de la Peña.  Stable representations of quivers.  J. Pure Appl. Algebra, 172(2-3):205–224, 2002.
  * [Hos14] Victoria Hoskins.  Stratifications associated to reductive group actions on affine spaces.  Q. J. Math., 65(3):1011–1047, 2014.
  * [Hus21] Alana Huszar.  Non-commutative rank and semi-stability of quiver representations, 2021\.
  * [IKQS15] Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha.  Generalized Wong sequences and their applications to Edmonds’ problems.  J. Comput. System Sci., 81(7):1373–1386, 2015.
  * [IQS18] Gábor Ivanyos, Youming Qiao, and K. V. Subrahmanyam.  Constructive non-commutative rank computation is in deterministic polynomial time.  Comput. Complexity, 27(4):561–593, 2018.
  * [Kem78] George R. Kempf.  Instability in invariant theory.  Ann. of Math. (2), 108(2):299–316, 1978.
  * [Kin94] A. D. King.  Moduli of representations of finite-dimensional algebras.  Quart. J. Math. Oxford Ser. (2), 45(180):515–530, 1994.
  * [MFK94] D. Mumford, J. Fogarty, and F. Kirwan.  Geometric invariant theory, volume 34 of Ergebnisse der Mathematik und ihrer Grenzgebiete (2) [Results in Mathematics and Related Areas (2)].  Springer-Verlag, Berlin, third edition, 1994.
  * [Zam14] Alfonso Zamora.  On the Harder-Narasimhan filtration for finite dimensional representations of quivers.  Geom. Dedicata, 170:185–194, 2014.

##  Appendix A Algebraic complexity towards the stability of representations
of quivers

In this section, we will demonstrate how algebraic complexity tools can be
applied to computing the discrepancy, together with a witnesses, for a
representation of an acyclic quiver.

###  A.1. Preliminaries

For starters, we let $\mathbf{F}$ be an infinite field of arbitrary
characteristic. The space of $n\times n$ matrices over $\mathbf{F}$ is denoted
$M(n,\mathbf{F})$. Let $\mathcal{B}$ be a subspace of $M(n,\mathbf{F})$. If
$U$ is a subspace of $\mathbf{F}^{n}$, we set

$\mathcal{B}(U)=\sum_{B\in\mathcal{B}}BU,$

where $\sum$ denote the sum of subspaces. We say $U$ is a $c$-_shrunk subspace
of_ $\mathcal{B}$ if

$\dim U-\dim\mathcal{B}(U)\geq c.$

We say $U$ is a _shrunk subspace of_ $\mathcal{B}$ if $U$ is a $c$-shrunk
subspace of $\mathcal{B}$ for some $c\in\mathbf{Z}^{+}$. We define the
_discrepancy of_ $\mathcal{B}$ as the integer

$\operatorname{disc}(\mathcal{B})=\max_{c\in\mathbf{N}}\\{\exists\text{ a
}c\text{-shrunk subspace of }\mathcal{B}\\}.$

######  Remark A.1.

For any subspace $\mathcal{B}\subset M(n,\mathbf{F})$, if
$c=\operatorname{disc}(\mathcal{B})$, it is shown in [Hus21], Lemma 2.1 that
the intersection of $c$-shrunk subspaces is again a $c$-shrunk subspace.
Therefore, there is an unique minimal $c$-shrunk subspace of $\mathcal{B}$.

The following is a summary of various results from [IQS18] and [IKQS15] .

######  Theorem A.2 (Theorem 1.5 [IQS18], Proposition 7, Lemma 9 [IKQS15]).

Let $\mathcal{B}$ be a matrix space in $M(n,\mathbf{F})$ with
$\operatorname{disc}(\mathcal{B})=c$ (a priori unknown). There exists a
deterministic algorithm using $n^{O(1)}$ arithmetic operations over
$\mathbf{F}$ that returns a $c$-shrunk subspace of $\mathcal{B}$. Moreover,
the $c$-shrunk subspace produced by this algorithm is the minimal $c$-shrunk
subspaces of $\mathcal{B}$.

######  Remark A.3.

The original Theorem 1.5 from [IQS18] deals with how field elements are
represented in a computer, which is not the main concern of this paper.
Personal communications with the authors of [IQS18] confirmed that in terms of
the number of operations needed, there is nothing special about the field of
rational numbers stated in the theorem in [IQS18]. Any field with large enough
set of elements to work with will suffice.

We now follow the recipe of [Hus21] to build a matrix space from a given
representation of an acyclic quiver, and establish the connection between the
discrepancy of the matrix space and that of the representation. Recall we
wrote a quiver as $Q=(Q_{0},Q_{1},t,h)$. Multiple arrows between any two
vertices are allowed. We fix a weight $\theta:Q_{0}\rightarrow\mathbf{Z}$ and
a representation $W$ of $Q$ of dimension $\mathbf{d}$ with
$\theta(\mathbf{d})=0$. If $p=a_{j}a_{j-1}\cdots a_{1}$ is a path in $Q$, we
let $W(p)$ denote the composition $W(a_{j})W(a_{j-1})\cdots W(a_{1})$.

Let $x_{1},\ldots,x_{n}$ (resp. $y_{1},\ldots,y_{m}$) be the vertices of $Q$
where $\theta$ takes positive values (resp. negative values). We then define

$\theta_{+}(x_{i})=\theta(x_{i})\text{ }(\text{resp.
}\theta_{-}(y_{j})=-\theta(y_{j})),$
$N:=\sum_{i}\theta_{+}(x_{i})\mathbf{d}(x_{i})=\sum_{j}\theta_{-}(y_{j})\mathbf{d}(y_{j}),$

and

$M=\sum_{j}\theta_{-}(y_{j})\text{ }(\text{resp.
}M^{\prime}=\sum_{i}\theta_{+}(x_{i})).$

For each $i\in[n]$ and each $j\in[m]$, we let

$I^{+}_{i}=\\{r\in\mathbf{N}\mid\sum_{k=1}^{i-1}\theta_{+}(x_{i})<r\leq\sum_{k=1}^{i}\theta_{+}(x_{i})\\},$

and

$I_{j}^{-}=\\{q\in\mathbf{N}\mid\sum_{k=1}^{j-1}\theta_{-}(y_{j})<q\leq\sum_{k=1}^{j}\theta_{-}(y_{j})\\}.$

For each $q\in I_{j}^{-}$, $r\in I_{i}^{+}$, and each path $p$ between $x_{i}$
and $x_{j}$, we define the $M\times M^{\prime}$ block matrix $A^{i,j,p}_{q,r}$
whose $(q,r)$-block is the $\mathbf{d}(y_{j})\times\mathbf{d}(x_{i})$ matrix
representing $W(p):\mathbf{R}^{d(x_{i})}\rightarrow\mathbf{R}^{d(y_{j})}$, and
whose other blocks are zero block matrices of appropriate sizes. In this way,
the same matrix representing $W(p)$ is placed in the various
$(q^{\prime},r^{\prime})$-blocks of $M\times M^{\prime}$ block matrices for
$q^{\prime}\in I_{j}^{-}$, and $r^{\prime}\in I_{i}^{+}$. We set

$\mathcal{A}_{W,\theta}=\operatorname{Span}(\\{A^{i,j,p}_{q,r}\mid
i\in[n],j\in[m],q\in I_{j}^{-},r\in I_{i}^{+},p\in\mathcal{P}_{i,j}\\})\subset
M(N,\mathbf{F}).$

where $\mathcal{P}_{i,j}$ is the collection of paths from $x_{i}$ to $y_{j}$.

We have an immediate relation described by the

######  Lemma A.4.

For any representation $W$, we have
$\operatorname{disc}(W,\theta)\leq\operatorname{disc}(\mathcal{A}_{W,\theta})$.

###### Proof.

Let $W^{\prime}\subset W$ be a subrepresentation. Define
$U=\bigoplus_{i}(W^{\prime}_{x_{i}})^{\theta_{+}(x_{i})}$. It then follows
that

$\begin{split}\theta(W^{\prime})&=\sum_{i}\theta_{+}(x_{i})W^{\prime}_{x_{i}}-\sum_{j}\theta_{-}(y_{j})W^{\prime}_{y_{j}}=\dim
U-\dim\big{(}\bigoplus_{j}W_{y_{j}}^{\theta_{-}(y_{j})}\big{)}\\\ &\leq\dim
U-\dim\big{(}\bigoplus_{j,q}\sum_{i}\sum_{p\in\mathcal{P}_{ij}}W(p)(W^{\prime}_{x_{i}})\big{)}=\dim
U-\dim\mathcal{A}_{W,\theta}(U).\end{split}$

This finishes the proof of the lemma. ∎

###  A.2. Relating the two discrepancies

In this section we relate better the two discrepancies
$\operatorname{disc}(W,\theta)$, and
$\operatorname{disc}(\mathcal{A}_{W,\theta})$. We will show that they are
equal, and demonstrate how to translate a witness to one discrepancy into a
witness to the other. For this we need to introduce a right action on
$\bigoplus_{i}W^{\theta_{+}(x_{i})}_{x_{i}}$ and on
$\bigoplus_{j}W_{y_{j}}^{\theta_{-}(y_{j})}$ by the paths of $Q$. For the
following, homomorphisms and endomorphisms are taken in the category of
representations of $Q$. In addition, we let
$c=\operatorname{disc}(\mathcal{A}_{W,\theta})$ so that by a $c$-shrunk
subspace of $\mathcal{A}_{W,\theta}$ we mean a subspace that witnesses
$\operatorname{disc}(\mathcal{A}_{W\,\theta})$.

For any vertex $x\in Q_{0}$, we let $P_{x}$ be the representation of $Q$ where
for each $y\in Q_{0}$, $(P_{x})_{y}$ is the vector space with basis the paths
from $x$ to $y$. Here $(P_{x})_{x}$ is one dimensional with basis the trivial
path $e_{x}$. For any $a\in Q_{1}$, we define

$P_{x}(a):(P_{x})_{ta}\rightarrow(P_{x})_{ha}$

by post composition.

For any representation $V$ of $Q$, there is a natural identification
$\operatorname{Hom}(P_{x},V)\simeq V_{x}$. Letting

$P_{1}=\bigoplus_{i}P_{x_{i}}^{\theta_{+}(x_{i})}\text{ }\big{(}\text{resp.
}P_{0}=\bigoplus_{j}P_{y_{j}}^{\theta_{-}(y_{j})}\big{)},$

we have

$\operatorname{Hom}(P_{1},W)\simeq\bigoplus_{i}W_{x_{i}}^{\theta_{+}(x_{i})}\text{
}\big{(}\text{resp.
}\operatorname{Hom}(P_{0},W)\simeq\bigoplus_{j}W_{y_{j}}^{\theta_{-}(y_{j})}\big{)}.$

Under the above identifications, a morphism
$\varphi\in\operatorname{Hom}(P_{0},P_{1})$ induces a morphism
$A(\varphi):\bigoplus_{i}W_{x_{i}}^{\theta_{+}(x_{i})}\rightarrow\bigoplus_{j}W_{y_{j}}^{\theta_{-}(y_{j})}$
by pre-composition. Moreover, if $p$ is a path from $x_{i}$ to $y_{j}$ placed
in the $(q,r)$-th component of
$\operatorname{Hom}(P_{0},P_{1})\simeq\bigoplus_{i,j}P_{x_{i}}(y_{j})^{\theta_{-}(y_{j})\theta_{+}(x_{i})},$
then the map it induces is precisely $A^{i,j,p}_{q,r}$. Therefore, for any
subspace $U\subset\bigoplus_{i}W_{x_{i}}^{\theta_{+}(x_{i})}$,
$\mathcal{A}_{W,\theta}(U)$ is the same as the sum
$\sum_{\varphi}A(\varphi)(U)$, taken over all
$\varphi\in\operatorname{Hom}(P_{0},P_{1})$.

Similarly, $\operatorname{End}(P_{1})$ (resp. $\operatorname{End}(P_{0})$)
induces a right action on $\bigoplus_{i}W_{x_{i}}^{\theta_{+}(x_{i})}$ (resp.
$\bigoplus_{j}W_{y_{j}}^{\theta_{-}(y_{j})}$) by pre-composition. We recall
Remark A.1 that there is a unique minimal subspace that witnesses
$\operatorname{disc}(\mathcal{A}_{W,\theta}).$ Now we quote the

######  Lemma A.5 (Lemma 3.2 [Hus21]).

Let $U\subset\bigoplus_{i}W_{x_{i}}^{\theta_{+}(x_{i})}$ be the minimal
$c$-shrunk subspace of $\mathcal{A}_{W\,\theta}$. Then $U$ (resp.
$\sum_{\varphi}A(\varphi)(U)$) is a right $\operatorname{End}(P_{1})$ (resp.
$\operatorname{End}(P_{0})$)-module. Namely, $U$ (resp.
$\sum_{\varphi}A(\varphi)(U)$) is closed under the right action of
$\operatorname{End}(P_{1})$ (resp. $\operatorname{End}(P_{0})$) defined by
pre-composition.

We now apply the lemma to establish the

######  Proposition A.6.

Let $U$ be the minimal $c$-shrunk subspace of $\mathcal{A}_{W,\theta}$, and
let $V=\sum_{\varphi}A(\varphi)(U)$. For each $i,r$ (resp. $j,q$), let
$\pi_{i,r}:\bigoplus_{i}W_{x_{i}}^{\theta_{+}(x_{i})}\rightarrow W_{x_{i}}$
(resp. $\pi_{j,q}:\bigoplus_{j}W_{y_{j}}^{\theta_{-}(y_{j})}\rightarrow
W_{y_{j}}$) be the projection onto the $(i,r)$-th (resp. $(j,q)$-th)
component. The following properties then hold:

  1. (1)

$U=\bigoplus_{i}(W^{\prime}_{x_{i}})^{\theta_{+}(x_{i})}$, where
$W^{\prime}_{x_{i}}=\pi_{i,r}(U)\subseteq W_{x_{i}}$ for any $r\in I^{+}_{i}$.

  2. (2)

$V=\bigoplus_{j}(W^{\prime}_{y_{j}})^{\theta_{-}(y_{j})}$, where
$W^{\prime}_{y_{j}}=\pi_{j,q}(V)=\sum_{i,p\in\mathcal{P}_{i,j}}W(p)(W^{\prime}_{x_{i}})\subseteq
W_{y_{j}}$ for any $q\in I_{j}^{-}$.

###### Proof.

Let $u\in U$ and let $p$ be a path from $x_{i^{\prime}}$ to $x_{i}$ in the
$(r^{\prime},r)$-th component of
$\operatorname{End}(P_{1})\simeq\bigoplus_{i,i^{\prime}}(P_{x_{i^{\prime}}})_{x_{i}}^{\theta_{+}(x_{i^{\prime}})\theta_{+}(x_{i})}.$
The pre-composition $u\circ p$ is then $W(p)(\pi_{i^{\prime},r^{\prime}}(u))$
placed in the $r$-th component of $W(x_{i})^{\theta_{+}(x_{i})}$. Since $U$ is
a right $\text{End}(P_{1})$-module, and the same path $p$ can be placed in any
$(r^{\prime},r)$-th component of $\operatorname{End}(P_{1})$, the image
$W(p)(\pi_{i^{\prime}r^{\prime}}(u))$ when placed in the $r$-th component of
$W(x_{i})^{\sigma_{+}(x_{i})}$, is still in $U$ for any $r^{\prime}\in
I^{+}_{i^{\prime}}$ and any $r\in I^{+}_{i}$. In particular, taking
$i^{\prime}=i$, we see that for any $r_{1},r_{2}\in I_{i}^{+}$,
$\pi_{i,r_{1}}(u)$ when placed at the $r_{2}$-th component of
$W_{x_{i}}^{\theta_{+}(x_{i})}$, is still in $U$. Basically, we obtain

$\pi_{i,r_{1}}(U)=\pi_{i,r_{2}}(U)\text{ for any }r_{1},r_{2}\in
I_{i}^{+}\text{, and }$
$U=\bigoplus_{i}\big{(}\pi_{i,r}(U)\big{)}^{\theta_{+}(x_{i})}\text{ for any
r}\in I_{i}^{+}.$

This establishes property (1).

Using the fact that $V$ is a right $\operatorname{End}(P_{0})$-module, we also
get

$V=\bigoplus_{j}\big{(}\pi_{j,q}(V)\big{)}^{\theta_{-}(y_{j})}\text{ for any
q}\in I^{-}_{j}.$

On the other hand, it is clear that

$\begin{split}\sum_{\varphi}A(\varphi)(U)&=\bigoplus_{j,q}\big{(}\sum_{i,p}\sum_{r}A^{i,j,p}_{q,r}\cdot\pi_{i,r}(U)\big{)}=\bigoplus_{j,q}\big{(}\sum_{i,p}\sum_{r}W(p)(\pi_{i,r}(U)\big{)}\\\
&=\bigoplus_{j}\big{(}\sum_{i,p\in\mathcal{P}_{i,j}}W(p)(W^{\prime}_{x_{i}})\big{)}^{\theta_{-}(y_{j})}\end{split}$

This establishes property (2), finishing the proof of the proposition. ∎

######  Theorem A.7.

Let $U\subset M(N,\mathbf{F})$ be the minimal $c$-shrunk subspace of
$\mathcal{A}_{W,\theta}$. Let
$\pi_{i,r}:\bigoplus_{i}W_{x_{i}}^{\sigma_{+}(x_{i})}\rightarrow W_{x_{i}}$ be
the projection onto the $(i,r)$-th component. For each $i\in[n]$, set

$W^{\prime}_{x_{i}}=\pi_{i,r}(U).$

For each $j\in[m]$, set

$W^{\prime}_{y_{j}}=\sum_{i,p\in\mathcal{P}_{i,j}}W(p)\big{(}W_{x_{i}}\big{)}.$

For each $y\in Q_{0}$ with $\theta(y)=0$, set

$W^{\prime}_{y}=\sum_{\theta(x)\neq 0}\bigg{(}\sum_{p:x\rightarrow
y}W(p)\big{(}W_{x}\big{)}\bigg{)}.$

Then $\\{W^{\prime}_{x}\\}_{x\in Q_{0}}$ defined this way yields a
subrepresentation $W^{\prime}$ with $\theta(W^{\prime})=c$. In this case, we
actually have

$\operatorname{disc}(W,\theta)=c.$

###### Proof.

We first verify that $\\{W^{\prime}_{x}\\}_{x\in Q_{0}}$ forms a
subrepresentation $W^{\prime}$ of $W$. We need to show that
$W(a)(W^{\prime}_{ta})\subset W^{\prime}_{ha}$ for all $a\in Q_{1}$. Due to
the construction of $W^{\prime}$, it is more convenient to work with paths. We
split the paths in $Q$ into three major categories.

Case 1: The path starts at some $x_{i^{\prime}}$. We consider three
possibilities:

  * •

Case (1a): The path ends at some $x_{i}$.

  * •

Case (1b): The path ends at some $y_{j}$.

  * •

Case (1c): The path ends at some $y$.

For case (1a), let $p:x_{i^{\prime}}\rightarrow x_{i}$ be a path. We have seen
in the proof of Proposition A.6 that $W(p)(W_{x_{i^{\prime}}})$, when placed
in any $r$-th component of $W_{x_{i}}^{\theta_{+}(x_{i})}$, is still in $U$.
By property (1) of Proposition A.6, $W(p)(W^{\prime}_{x_{i^{\prime}}})\subset
W^{\prime}_{x_{i}}$. This finishes case (1a). Case (1b) follows from the
description of $W^{\prime}_{y_{j}}$ in Proposition A.6. Case (1c) follows from
the construction of $W^{\prime}_{y}$.

Case 2: The path starts at some $y_{j^{\prime}}$. Again we consider three
possibilities:

  * •

Case (2a): The path ends at some $x_{i}$.

  * •

Case (2b): The path ends at some $y_{j}$.

  * •

Case (2c): The path ends at some $y$.

For case (2a), if there are no paths from any $x_{i^{\prime}}$ into $y_{j}$,
then $W^{\prime}_{y_{j}}$ is the zero subspace, which is a trivial scenario.
If there are paths from some $x_{i^{\prime}}$ into $y_{j}$, the case is
covered by case (1a). Case (2b) can be established using the fact that $V$ is
an $\operatorname{End}(P_{0})$-module like what we did for case (1a). Finally,
case (2c) follows from the construction of $W^{\prime}_{y}$ as well.

Case 3: The path starts at some $y^{\prime}$. We consider:

  * •

Case (3a): The path ends at some $x_{i}$

  * •

Case (3b): The path ends at some some $y_{j}$.

  * •

Case (3c): The path ends at some $y$.

If there are no paths from either $x_{i^{\prime}}$ or $y_{j^{\prime}}$ into
$y$, then $W^{\prime}_{y}$ must be the zero subspace, which is a trivial
scenario. If there is a path from some $x_{i^{\prime}}$ or some
$y_{j^{\prime}}$ into $y$, case (3a) is covered by case (1a) and case (2a).
Similarly case (3b) is covered by case (1b) and case (2b). Finally, case (3c)
is covered by the construction of $W^{\prime}_{y}$.

We have shown that $\\{W^{\prime}_{x}\\}_{x\in Q_{0}}$ forms a
subrepresentation $W^{\prime}$ of $W$. Next, note that

$\theta(W^{\prime})=\sum_{i}(\dim
W^{\prime}_{x_{i}})\cdot\theta_{+}(x_{i})-\sum_{j}(\dim
W^{\prime}_{y_{j}})\cdot\theta_{-}(y_{j})=\dim
U-\dim\mathcal{A}_{W,\theta}(U)$

by Proposition A.6. By Lemma A.4, it must be the case that
$\theta(W^{\prime})=\operatorname{disc}(W,\theta)=\operatorname{disc}(\mathcal{A}_{W,\theta}).$
∎

We are now able to establish the algorithm of Theorem 3.5, which returns the
discrepancy, together with a witness for any representation of an acyclic
quiver over an infinite field.

######  Corollary A.8.

Let $Q$ be an acylcic quiver and let $W$ be a representation as above. There
is a deterministic algorithm that finds the discrepancy
$\operatorname{disc}(W,\theta)$, together with a subrepresentation
$W^{\prime}$ so that $\theta(W^{\prime})=\operatorname{disc}(W,\theta)$. If we
set $\Omega=\sum_{x\in Q_{0}}|\theta(x)|$, $K=\sum_{x\in Q_{0}}\dim W_{x}$,
and $P$ as the number of paths in $Q$, then the algorithm has time complexity
that is polynomial in $\Omega,K,P$.

###### Proof.

We propose the following three steps to find the discrepancy of $W$, together
with a witnessing subrepresentation. As step 1, we compute a basis for the
matrix space

$\mathcal{A}_{W,\theta}=\bigoplus_{i,j}\bigoplus_{q,r}\operatorname{Span}(A^{i,j,p}_{q,r}\mid
p\in\mathcal{P}_{ij}),$

where each $A^{i,j,p}_{q,r}$ is $W(p)$ placed in the $(q,r)$-block. If $p$ has
length $l$, then $W(p)$ involves $l-1$ multiplications of matrices of sizes
taken from a subset of $\\{\dim W_{x}\\}_{x\in Q_{0}}$. Iterating through
paths in increasing lengths, computing $W(p)$ for all $p\in\mathcal{P}_{i,j}$
has time complexity polynomial in $K$, and linear in $P$. We then sort out
linearly independent size $\dim W(y_{j})\times\dim W(x_{i})$ matrices among
$\\{W(p)\mid p\in\mathcal{P}_{i,j}\\}$, which has time complexity polynomial
in $K,P$. Finally ,we put these linearly independent matrices into appropriate
$(q,r)$-blocks for all $q\in I^{+}_{j}$, $r\in I^{+}_{i}$, and for all $i,j$.
There are $M\times M^{\prime}$ blocks so the time complexity to compute a
basis for $\mathcal{A}_{W,\theta}$ is polynomial in $\Omega,K,P$.

As step 2, apply the algorithm of Theorem A.2 to obtain a basis of the minimal
$c$-shrunk subspace $U$ of $\mathcal{A}_{W,\theta}$. The time complexity is
polynomial in $N$, which in turn is bounded by a polynomial in $\Omega\cdot
K$.

As step 3, we apply Theorem A.7 to derive a basis for $W^{\prime}_{x}$ for
each $x\in Q_{0}$. A spanning set for each $W^{\prime}_{x_{i}}$ is obtained by
truncating suitable parts of the basis of $U$ we obtained earlier. We can then
trim this spanning set down to a basis within time complexity polynomial in
$\dim W_{x_{i}}$ and $N$, which is bounded by a polynomial in $\Omega,K$.
Since there are at most $\Omega$ many $x_{i}^{\prime}$s, the time complexity
to obtain bases for all $W^{\prime}_{x_{i}}$ is bounded by a polynomial in
$\Omega,K$. For $W^{\prime}_{y_{j}}$, we can first compute $\sum_{i}\sum_{p\in
P_{i,j}}W(p)(W^{\prime}_{x_{i}})$. In this case, since each $W(p)$ is computed
earlier, a spanning set of $W(p)(W^{\prime}_{x_{i}})$ is obtained by
multiplying $W(p)$ with the basis matrix of $W^{\prime}_{x_{i}}$. Hence a
spanning set for $W^{\prime}(y_{j})$ can be obtained within time complexity
polynomial in $K,P$. Since there are at most $P\cdot\sum_{i}\dim
W^{\prime}_{x_{i}}$ vectors in the spanning set for each $W^{\prime}(y_{j})$,
deriving a basis for $W^{\prime}_{y_{j}}$ has time complexity polynomial in
$K,P$. Since the number of $y_{j}$’s is bounded by $\Omega$, we may infer that
computing bases for all $W^{\prime}_{y_{j}}$ has time complexity polynomial in
$\Omega,K,P$. Similarly, computing bases for all $W^{\prime}_{y}$ with
$\theta(y)=0$ has time complexity polynomial in $\Omega,K,P$.

Since the three major steps are all within time complexity polynomial in
$\Omega,K,P$. The corollary is proved. ∎