# Powers of Karpelevič arcs and their Sparsest Realising matrices

Priyanka Joshi  School of Mathematics and Statistics, University College
Dublin, Belfield, Dublin 4, Ireland  Stephen Kirkland  Department of
Mathematics, University of Manitoba, Winnipeg, MB, Canada  Helena Šmigoc
School of Mathematics and Statistics, University College Dublin, Belfield,
Dublin 4, Ireland

###### Abstract

The region in the complex plane containing the eigenvalues of all $n\times n$
stochastic matrices was described by Karpelevič in 1988, and it is since then
known as the Karpelevič region. The boundary of the Karpelevič region is the
union of disjoint arcs called the Karpelevič arcs. We provide a complete
characterization of the Karpelevič arcs that are powers of some other
Karpelevič arc. Furthermore, we find the necessary and sufficient conditions
for a sparsest stochastic matrix associated with the Karpelevič arc of order
$n$ to be a power of another stochastic matrix.

##  1 Introduction

A square entrywise nonnegative matrix is called stochastic if each row sum
equals $1$. Stochastic matrices and their properties are central to the study
of Markov chains; in particular, the eigenvalues of a stochastic matrix govern
the long-term behavior of the iterates of the corresponding Markov chain.
Consequently, there is a long-standing interest in localising the eigenvalues
of stochastic matrices, and a classic problem of Kolmolgorov [8] asks for a
description of the region in the complex plane containing all the eigenvalues
of all $n\times n$ stochastic matrices.

That region, denoted by $\Theta_{n}$, was characterised by Karpelevič [4]. He
showed that the boundary of the Karpelevič region, denoted by
$\partial\Theta_{n}$, is a union of disjoint arcs called the Karpelevič arcs.
Kirkland, Laffey and Šmigoc [6] expanded on this result by identifying the
point on the boundary of the Karpelevič region with a given argument
$\theta\in[0,2\pi)$.

The problem of determining a stochastic $p$-th root of a stochastic matrix
finds its motivation in the theory of Markov Chains, where it corresponds to
the problem of finding a transition matrix over a shorter time interval from a
given transition matrix. This problem was considered for example in [1].

Johnson and Paparella [3] posed a conjecture that selected Karpelevič arcs are
powers of some other Karpelevič arcs. Kim and Kim [5] proved their conjecture.
However, results in [3] and [5] only partially answer the question of
characterising the powers of the Karpelevič arcs. After establishing notation
and recalling the necessary background results on the Karpelevič region in
Section 2, we give a complete characterization of the Karpelevič arcs that can
be written as a power of another Karpelevič arc in Section 3.

Johnson and Paparella [3] also considered the question of constructing
stochastic matrices realising the boundary of the Karpelevič region. For each
Karpelevič arc, they provided a single parametric family of stochastic
matrices that realises eigenvalues on that arc. Kirkland and Šmigoc in [7]
described all sparsest $n\times n$ stochastic matrices realising eigenvalues
on the border of the Karpelevič region. In Section 4 we recall the results
from [7], and establish notation for digraphs and the associated stochastic
matrices. This background is needed in Section 5, where we characterise the
sparsest realising matrices that can be written as a power of another
stochastic matrix.

This paper is organised in two parts that can be read independently. Section 2
provides the background to Section 3 where the complete characterisation of
the Karpelevič arcs that can be written as a power of another Karpelevič arc
is given in Theorem 3.10 and Corollary 3.12. A reader that is more interested
in the powers of matrices and results developed in Section 5, could view
Theorem 3.10 and Corollary 3.12 as part of background results, and learn about
additional background in Section 4.

##  2 Background and Notation on the Karpelevič Region

Given $n\in\mathbb{N}$, the set

$\mathcal{F}_{n}=\\{\nicefrac{{p}}{{q}}\mid 0\leq p<q\leq n,\gcd(p,q)=1\\}$

is called _the set of Farey fractions of order $n$_. The pair
$(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})$ is called _a Farey pair (of order
$n$)_, if $\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}}\in\mathcal{F}_{n}$,
$\nicefrac{{p}}{{q}}<\nicefrac{{r}}{{s}}$ and
$\nicefrac{{p}}{{q}}<x<\nicefrac{{r}}{{s}}$ implies $x\not\in\mathcal{F}_{n}$.
The Farey fractions $\nicefrac{{p}}{{q}}$ and $\nicefrac{{r}}{{s}}$ are called
_Farey neighbours_ if one of $(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})$ and
$(\nicefrac{{r}}{{s}},\nicefrac{{p}}{{q}})$ is a Farey pair. It is well known
that the Farey fractions $\nicefrac{{p}}{{q}}$ and $\nicefrac{{r}}{{s}}$ form
a Farey pair iff $q+s>n$ and $\left|qr-ps\right|=1$.

For $n$, $q$ and $s$, satisfying, $q<s\leq n$, $\gcd(q,s)=1$, and $q+s>n$,
there exits precisely two Farey pairs in $\mathcal{F}_{n}$ with denominators
$q$ and $s$:

$\mathcal{F}_{n}(q,s):=\\{(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}}),(\nicefrac{{(s-r)}}{{s}},\nicefrac{{(q-p)}}{{q}})\\}.$
(1)

Hence, there exist unique $p$ and $r$ so that
$(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})\in\mathcal{F}_{n}(q,s)$. We will
denote those as $p(q,s)$ and $r(q,s)$, and when clear from the context just as
$p$ and $r$.

Further parameters associated with $\mathcal{F}_{n}(q,s)$ that were first
defined in [6] and will also be needed in this work, are given below:

$\displaystyle d(q,s)$ $\displaystyle=\left\lfloor\frac{n}{q}\right\rfloor,$
$\displaystyle\delta(q,s)$ $\displaystyle=\gcd(d(q,s),s),$ $\displaystyle s$
$\displaystyle=s_{1}(q,s)\delta(q,s),$ $\displaystyle d(q,s)$
$\displaystyle=d_{1}(q,s)\delta(q,s).$

Note that $d(q,s)$, $\delta(q,s)$, $d_{1}(q,s)$, $s_{1}(q,s)$ depend on $n$ as
well as on $q$ and $s$. Our notation does not capture this dependence, as we
will always fix $n$. Furthermore, once $q$ and $s$ are established, we will
abbreviate notation to $d$, $\delta$, $s_{1}$ and $d_{1}$.

######  Example 2.1.

Let $q=3$ and $s=14$. Then
$\mathcal{F}_{n}(3,14)=\\{(\nicefrac{{1}}{{3}},\nicefrac{{5}}{{14}}),(\nicefrac{{9}}{{14}},\nicefrac{{2}}{{3}})\\}$
for $n\in\\{14,15,16\\}$. For $n=14$ we get
$d(3,14)=\left\lfloor\frac{14}{3}\right\rfloor=4$,
$\delta(3,14)=2,d_{1}(3,14)=2$ and $s_{1}(3,14)=7$. On the other hand, for
$n=15$ and for $n=16$ we get
$d(3,14)=\left\lfloor\frac{16}{3}\right\rfloor=5$,
$\delta(3,14)=1,d_{1}(3,14)=5$ and $s_{1}(3,14)=14.$

The Karpelevič region was first described in [4]. We recall a version of this
result from [2] below.

######  Theorem 2.2.

([4],[2]) The region $\Theta_{n}$ is symmetric with respect to the real axis,
is included in the unit disc $\\{z\in C|\hskip 2.84526pt|z|\leq 1\\}$, and
intersects the unit circle $\\{z\in C|\hskip 2.84526pt|z|=1\\}$ at the points
$\\{e^{\frac{2\pi ip}{q}}|\hskip 2.84526ptp/q\in\mathcal{F}_{n}\\}$. The
boundary of $\Theta_{n}$ consists of these points and curvilinear arcs
connecting them in circular order.

The arc with endpoints $e^{\frac{2\pi ip}{q}}$ and $e^{\frac{2\pi ir}{s}}$,
$q<s$, is given by the following parametric equation:

$t^{s}(t^{q}-1+\alpha)^{\lfloor\frac{n}{q}\rfloor}=\alpha^{\lfloor\frac{n}{q}\rfloor}t^{q\lfloor\frac{n}{q}\rfloor},\alpha\in[0,1].$
(2)

For a Farey pair associated with the endpoints of an arc, the above theorem
assumes $q$ to be the smallest denominator of the two fractions appearing in
the pair. As equation (2) depends on $q$ and $s$ only, the same equation
describes both arcs associated with the Farey pairs in $\mathcal{F}_{n}(q,s)$.
These two arcs are conjugates of each other, and we will (when convenient)
only concentrate on one of them, say the arc associated with the Farey pair,
$(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})$ with $q<s$.

For $q<s$, $\gcd(q,s)=1$ and $q+s>n$, we set $p:=p(q,s)$ and $r:=r(q,s)$, and
introduce the following notation:

  1. 1.

$\arg(q,s)\equiv(\nicefrac{{2\pi p}}{{q}},\nicefrac{{2\pi
r}}{{s}})\cup(\nicefrac{{2\pi(s-r)}}{{s}},\nicefrac{{2\pi(q-p)}}{{q}})$,

  2. 2.

${\mathcal{K}}_{n}(q,s)\equiv\partial\Theta_{n}\cap\\{z\in\mathbb{C}\mid\arg(z)\in\arg(q,s)\\}$,

  3. 3.

$\mathcal{K}_{n}$ the set of all $\mathcal{K}_{n}(q,s)$ for a fixed
$n\in\mathbb{N}$.

Theorem 2.2 tells us that $\mathcal{K}_{n}(q,s)$ contains a pair of arcs that
are complex conjugates of each other, and whose points satisfy the parametric
equation (2). For the Farey pair,
$(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})\in\mathcal{F}_{n}(q,s)$ with $q<s$,
we can substitute $d=\lfloor\frac{n}{q}\rfloor$ in equation (2). The
polynomial
$f_{\alpha}(t)=t^{s}(t^{q}-\beta)^{d}-\alpha^{d}t^{qd},\alpha\in[0,1]$, are
called the _Ito polynomials_ for the Farey pair
$(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}}),q<s$. The _reduced Ito polynomials_
are the polynomials obtained from the Ito polynomials by removing the zero
roots.

######  Example 2.3.

In Example 2.1 we have seen that
$\mathcal{F}_{n}(3,14)=\\{(\nicefrac{{1}}{{3}},\nicefrac{{5}}{{14}}),(\nicefrac{{9}}{{14}},\nicefrac{{2}}{{3}})\\}$
for $n\in\\{14,15,16\\}$. In all three cases
$\arg(3,14)=(\nicefrac{{2\pi}}{{3}},\nicefrac{{5\pi}}{{7}})\cup(\nicefrac{{9\pi}}{{7}},\nicefrac{{4\pi}}{{3}})$,
and
$\mathcal{K}_{n}(3,14)=\partial\Theta_{n}\cap\\{z\in\mathbb{C}\mid\arg(z)\in\arg(3,14)\\}$.

Theorem 2.2 describes $\partial\Theta_{n}$. However, from the theorem, it is
not immediately clear, given $\theta\in[0,2\pi]$, how to find $\rho$
satisfying $\rho e^{i\theta}\in\partial\Theta_{n}$. This issue was resolved in
Theorem 1.2 from [6] which is restated below.

######  Definition 2.4.

For $n\geq 2$, we define $\rho_{n}:[0,2\pi]\rightarrow\mathbb{R}_{+}$ to be
the positive number satisfying
$\rho_{n}(\theta)e^{i\theta}\in\partial\Theta_{n}$.

######  Theorem 2.5 (Theorem 1.2, [6]).

Let $(\frac{p}{q},\frac{r}{s})\in\mathcal{F}_{n}(q,s)$, $q<s$, and
$\theta\in[\nicefrac{{2\pi p}}{{q}},\nicefrac{{2\pi r}}{{s}}]$. Then
$\rho_{n}(\theta)=\mu^{d_{1}}$, where $\mu$ is the unique positive solution to

$\mu^{s_{1}}\sin(q\theta)-\mu^{qd_{1}}\sin\left(\frac{s_{1}}{d_{1}}\theta-\frac{2\pi
r}{d}\right)-\sin\left((q-\frac{s_{1}}{d_{1}})\theta+\frac{2\pi
r}{d}\right)=0.$ (3)

Furthermore, $\rho_{n}(\theta)e^{\mathrm{i}\theta}$ is a root of the rational
function $\phi_{\alpha}(t)=(t^{q}-\beta)^{d}-\alpha^{d}t^{qd-s}$, where
$\alpha$ is given by

$\alpha\sin\left((q-\frac{s_{1}}{d_{1}})\theta+\frac{2\pi
r}{d}\right)=\mu^{s_{1}}\sin(q\theta).$

######  Remark 2.6.

To apply Theorem 2.5 directly to
$(\frac{p}{q},\frac{r}{s})\in\mathcal{F}_{n}$, the assumption $q<s$ is
necessary. To use the theorem for
$\theta^{\prime}\in(\frac{2\pi(s-r)}{s},\frac{2\pi(q-p)}{q})\in\mathcal{F}_{n}(q,s)$
we note that $\rho_{n}e^{i\theta^{\prime}}\in\partial\Theta_{n}$ if and only
if $\rho_{n}e^{i\theta}\in\partial\Theta_{n}$ for
$\theta=2\pi-\theta^{\prime}$. So for
$\theta^{\prime}\in(\frac{2\pi(s-r)}{s},\frac{2\pi(q-p)}{q})\in\mathcal{F}_{n}$,
we have $\mu^{d_{1}}e^{i\theta^{\prime}}\in\mathcal{K}_{n}(q,s)$ if and only
if $\mu$ satisfies:

$\mu^{s_{1}}\sin(q\theta^{\prime})-\mu^{qd_{1}}\sin\left(\frac{s_{1}}{d_{1}}\theta^{\prime}+\frac{2\pi(r-s)}{d}\right)-\sin\left((q-\frac{s_{1}}{d_{1}})\theta^{\prime}-\frac{2\pi(r-s)}{d}\right)=0.$
(4)

This equation can be obtained from (3) by inserting
$\theta=2\pi-\theta^{\prime}$.

######  Example 2.7.

To determine $\rho_{14}(\nicefrac{{29\pi}}{{42}})$ we first note that
$\nicefrac{{29\pi}}{{42}}\in[\nicefrac{{2\pi}}{{3}},\nicefrac{{5\pi}}{{7}}]$
and $(\nicefrac{{1}}{{3}},\nicefrac{{5}}{{14}})\in\mathcal{F}_{14}(3,14)$.
Substituting $d=4,\delta=2,d_{1}=2,s_{1}=7$ and
$\theta=\nicefrac{{29\pi}}{{42}}$ in (3), we get:

$\mu^{7}\sin(\nicefrac{{29\pi}}{{14}})+\mu^{6}\sin(\nicefrac{{\pi}}{{12}})-\sin\left(\nicefrac{{181\pi}}{{84}}\right)=0,$

which has a unique positive solution $\mu_{0}$ (approximately equal to
$0.99542$). Thus, $\rho_{14}(\nicefrac{{29\pi}}{{42}})=\mu_{0}^{2}$.

Now, for $(\nicefrac{{9}}{{14}},\nicefrac{{2}}{{3}})\in\mathcal{F}_{14}(3,14)$
let $\theta^{\prime}=2\pi-\theta=\nicefrac{{55\pi}}{{42}}$. We see that
$\nicefrac{{55\pi}}{{42}}\in[\nicefrac{{9\pi}}{{7}},\nicefrac{{4\pi}}{{3}}]$.
Substituting $\theta^{\prime}=55\pi/42$ in equation (4), we get:

$\mu^{7}\sin(\nicefrac{{55\pi}}{{14}})-\mu^{6}\sin(\nicefrac{{\pi}}{{12}})-\sin\left(\nicefrac{{323\pi}}{{84}}\right)=0,$

which again has the unique positive solution $\mu_{0}$. Hence,
$\rho_{14}(55\pi/42)=\mu_{0}^{2}$.

##  3 Powers of Karpelevič Arcs

For $\mathcal{S}\subset\mathbb{C}$ and $c\in\mathbb{N}$, we define the $c$-th
power of $\mathcal{S}$ to be:

$\mathcal{S}^{c}:=\\{\lambda^{c}|\lambda\in\mathcal{S}\\}.$

In this section, we aim to understand, when one Karpelevič arc is a power of
another Karpelevič arc. In other words, we want to identify
$q,s,\hat{q},\hat{s},n$ and $c$ so that
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$.

We start by considering the necessary conditions on the associated Farey pairs
that assure that the endpoints of an arc are mapped to the endpoints of
another arc. Let
$\mathcal{F}_{n}(q,s)=\\{(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}}),(\nicefrac{{(s-r)}}{{s}},\nicefrac{{(q-p)}}{{q}})\\}$
be the set of two Farey pairs associated with $\mathcal{K}_{n}(q,s)$, and
${\mathcal{F}}_{n}(\hat{q},\hat{s})=\\{(\nicefrac{{\hat{p}}}{{\hat{q}}},\nicefrac{{\hat{r}}}{{\hat{s}}}),(\nicefrac{{(\hat{s}-\hat{r})}}{{\hat{s}}},\nicefrac{{(\hat{q}-\hat{p})}}{{\hat{q}}})\\}$
the set of two Farey pairs associated with $\mathcal{K}_{n}(\hat{q},\hat{s})$.
If $\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$, then the
endpoints of the arcs in $\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$ have to map to
the endpoints of the arcs in $\mathcal{K}_{n}(q,s)$. In terms of the
associated Farey pairs:

$\\{(\nicefrac{{\hat{p}c}}{{\hat{q}}}-\lfloor\nicefrac{{\hat{p}c}}{{\hat{q}}}\rfloor,\nicefrac{{\hat{r}c}}{{\hat{s}}}-\lfloor\nicefrac{{\hat{r}c}}{{\hat{s}}}\rfloor),(\nicefrac{{(\hat{s}-\hat{r})c}}{{\hat{s}}}-\lfloor\nicefrac{{(\hat{s}-\hat{r})c}}{{\hat{s}}}\rfloor,\nicefrac{{(\hat{q}-\hat{p})c}}{{\hat{q}}}-\lfloor\nicefrac{{(\hat{q}-\hat{p})c}}{{\hat{q}}}\rfloor)\\}={\mathcal{F}}_{n}(q,s).$
(5)

Since arcs in $\mathcal{K}_{n}(q,s)$ span only a fraction of the unit circle,
we also need:

$\lfloor\nicefrac{{\hat{p}c}}{{\hat{q}}}\rfloor=\lfloor\nicefrac{{\hat{r}c}}{{\hat{s}}}\rfloor\text{
and
}\lfloor\nicefrac{{(\hat{q}-\hat{p})c}}{{\hat{q}}}\rfloor=\lfloor\nicefrac{{(\hat{s}-\hat{r})c}}{{\hat{s}}}\rfloor.$
(6)

The endpoints of $\mathcal{K}_{n}(q,s)$ are the $c$-th powers of the endpoints
of $\mathcal{K}_{n}(\hat{q},\hat{s})$ precisely when (5) and (6) hold. Since
those will from now on be ongoing assumptions, we gather them in the
definition below.

######  Definition 3.1.

If $\mathcal{F}_{n}(q,s)$ and $\mathcal{F}_{n}(\hat{q},\hat{s})$ satisfy
equations (5) and (6), then we define $\mathcal{F}_{n}(\hat{q},\hat{s})\star
c:=\mathcal{F}_{n}(q,s)$, otherwise we say that
$\mathcal{F}_{n}(\hat{q},\hat{s})\star c$ is not defined.

The example below illustrates that it is possible for (5) to hold while (6)
does not.

######  Example 3.2.

Let $\hat{q}=5$ and $\hat{s}=6$ and $6\leq n\leq 10$. Then $\hat{p}=4$,
$\hat{r}=5$ and
$\mathcal{F}_{n}(\hat{q},\hat{s})=\mathcal{F}_{n}(5,6)=\\{(\nicefrac{{4}}{{5}},\nicefrac{{5}}{{6}}),(\nicefrac{{1}}{{6}},\nicefrac{{1}}{{5}})\\}$.
Taking $c=31$, we verify (5):

$\\{(\nicefrac{{(4\times 31)}}{{5}}-24,\nicefrac{{(5\times
31)}}{{6}}-25),(\nicefrac{{(1\times 31)}}{{6}}-5,\nicefrac{{(1\times
31)}}{{5}}-6)\\}=\mathcal{F}_{n}(5,6)=\mathcal{F}_{n}(q,s).$

Clearly, (6) does not hold and $\mathcal{F}_{n}(5,6)\star 31$ is not defined.

######  Lemma 3.3.

If $\mathcal{F}_{n}(\hat{q},\hat{s})\star c=\mathcal{F}_{n}(q,s)$, then either
$c$ divides $\hat{q}$ or $c$ divides $\hat{s}$.

###### Proof.

Let us define $c_{\hat{q}}:=\gcd(c,\hat{q})$, $c_{\hat{s}}:=\gcd(c,\hat{s})$
so that $c=c_{\hat{q}}c_{\hat{s}}c_{0}$. If
$\mathcal{F}_{n}(\hat{q},\hat{s})\star c=\mathcal{F}_{n}(q,s)$, we notice that
$\\{q,s\\}=\\{\nicefrac{{\hat{q}}}{{c_{\hat{q}}}},\nicefrac{{\hat{s}}}{{c_{\hat{s}}}}\\}.$
Now, if $c_{\hat{s}}=c_{\hat{q}}=1$ then $\\{q,s\\}=\\{\hat{q},\hat{s}\\}$ i.e
$\mathcal{F}_{n}(\hat{q},\hat{s})=\mathcal{F}_{n}(q,s)$ since $q$, $s$ and $n$
uniquely define $\mathcal{F}_{n}(q,s)$. As this implies $c=1$, we can assume
$c_{\hat{s}}c_{\hat{q}}>1$.

From $\hat{q}<\hat{s}\leq n$ and
$q+s=\nicefrac{{\hat{q}}}{{c_{\hat{q}}}}+\nicefrac{{\hat{s}}}{{c_{\hat{s}}}}>n,$
we conclude that $c_{\hat{q}}\geq 2$ and $c_{\hat{s}}\geq 2$ cannot occur.
Assume $c_{\hat{s}}=1$, $c_{\hat{q}}\geq 2$, and
$\hat{q}=c_{\hat{q}}\hat{q}_{0}$. (The case $c_{\hat{s}}\geq 2$ and
$c_{\hat{q}}=1$ can be argued similarly.) By assumption

$((\nicefrac{{\hat{p}c}}{{\hat{q}}})-a,(\nicefrac{{\hat{r}c}}{{\hat{s}}})-a)=(\nicefrac{{(\hat{p}c_{0}-a\hat{q}_{0})}}{{\hat{q}_{0}}},\nicefrac{{(\hat{r}c_{\hat{q}}c_{0}-a\hat{s})}}{{\hat{s}}})$

is a Farey pair for
$a=\lfloor\nicefrac{{\hat{p}c}}{{\hat{q}}}\rfloor=\lfloor\nicefrac{{\hat{r}c}}{{\hat{s}}}\rfloor$.
Hence :

$\displaystyle 1$
$\displaystyle=\hat{q}_{0}(\hat{r}c_{\hat{q}}c_{0}-a\hat{s})-\hat{s}(\hat{p}c_{0}-a\hat{q}_{0})$
$\displaystyle=(\hat{s}\hat{p}-\hat{q}\hat{r})c_{0}=c_{0}.$

We conclude that $c_{0}=1$, proving that $c$ divides $\hat{q}$. ∎

######  Example 3.4.

Let $6\leq n\leq 10$,
$\mathcal{F}_{n}(\hat{q},\hat{s})=\mathcal{F}_{n}(5,6)=\\{(\nicefrac{{4}}{{5}},\nicefrac{{5}}{{6}}),(\nicefrac{{1}}{{6}},\nicefrac{{1}}{{5}})\\}$,
and $c=3$. Although $c$ divides $\hat{s}$,
$\mathcal{F}_{n}(\hat{q},\hat{s})\star c$ is not defined for all $6\leq n\leq
10$. Indeed,

$\\{(\nicefrac{{(4\times 3)}}{{5}}-2,\nicefrac{{(5\times
3)}}{{6}}-2),(\nicefrac{{(1\times 3)}}{{6}}-0,\nicefrac{{(1\times
3)}}{{5}}-0)\\}=\\{(\nicefrac{{2}}{{5}},\nicefrac{{1}}{{2}}),(\nicefrac{{1}}{{2}},\nicefrac{{3}}{{5}})\\},$

and
$\\{(\nicefrac{{2}}{{5}},\nicefrac{{1}}{{2}}),(\nicefrac{{1}}{{2}},\nicefrac{{3}}{{5}})\\}=\mathcal{F}_{n}(2,5)$
for $n\in\\{5,6\\}$ but not for $n\in\\{7,8,9,10\\}$.

######  Corollary 3.5.

Let $\mathcal{F}_{n}(\hat{q},\hat{s})\star c=\mathcal{F}_{n}(q,s)$,
${\hat{\zeta}}=(\frac{\hat{p}}{\hat{q}},\frac{\hat{r}}{\hat{s}})\in\mathcal{F}_{n}(\hat{q},\hat{s})$
and
$a:=\lfloor\nicefrac{{\hat{p}c}}{{\hat{q}}}\rfloor=\lfloor\nicefrac{{\hat{r}c}}{{\hat{s}}}\rfloor$.

  1. 1.

If $c$ divides $\hat{q}$, then:

     * •

${\zeta}=(\frac{p}{q},\frac{r}{s})\in\mathcal{F}_{n}(q,s)$ where $\hat{s}=s$,
$\hat{q}=cq$, $\hat{p}=p+aq$ and $c\hat{r}=r+as$,

     * •

$\hat{\theta}\in(\frac{2\pi\hat{p}}{\hat{q}},\frac{2\pi\hat{r}}{\hat{s}})$ if
and only if $\hat{\theta}=\frac{1}{c}(\theta+2\pi a)$ for
$\theta\in(\frac{2\pi p}{q},\frac{2\pi r}{s})$.

  2. 2.

If $c$ divides $\hat{s}$, then:

     * •

${\zeta}=(\frac{s-r}{s},\frac{q-p}{q})\in\mathcal{F}_{n}(q,s)$ where
$\hat{q}=s$, $\hat{s}=cq$, $\hat{p}c=s-r+as$ and $\hat{r}=q-p+aq$,

     * •

$\hat{\theta}\in(\frac{2\pi\hat{p}}{\hat{q}},\frac{2\pi\hat{r}}{\hat{s}})$ if
and only if $\hat{\theta}=\frac{1}{c}(\theta^{\prime}+2\pi a)$ for
$\theta^{\prime}\in(\frac{2\pi(s-r)}{s},\frac{2\pi(q-p)}{q})$.

###### Proof.

  1. 1.

Assuming
${\hat{\zeta}}=(\frac{\hat{p}}{\hat{q}},\frac{\hat{r}}{\hat{s}})\in\mathcal{F}_{n}(\hat{q},\hat{s}),$
$c|\hat{q}$ and $\hat{q}=c\hat{q}_{0}$, we have:

$\left(\frac{\hat{p}c}{\hat{q}}-a,\frac{\hat{r}c}{\hat{s}}-a\right)=\left(\frac{\hat{p}-a\hat{q}_{0}}{\hat{q}_{0}},\frac{\hat{r}c-a\hat{s}}{\hat{s}}\right)\in\mathcal{F}_{n}(q,s)$

by (5). Since $\hat{q}_{0}<\hat{q}<\hat{s}$, this implies: $\hat{q}_{0}=q$,
$\hat{s}=s$, $\hat{p}-a\hat{q}_{0}=p$, and $c\hat{r}-a\hat{s}=r$, as desired.
Now:

$\left(\frac{2\pi\hat{p}c}{\hat{q}},\frac{2\pi\hat{r}c}{\hat{s}}\right)=\left(\frac{2\pi(p+aq)}{q},\frac{2\pi(r+as)}{s}\right)=\left(\frac{2\pi
p}{q}+2\pi a,\frac{2\pi r}{s}+2\pi a\right).$

The second part of the claim follows.

  2. 2.

Let $c|\hat{s}$, then $\hat{s}=c\hat{s}_{0}$ which gives:

$\left(\frac{\hat{p}c}{\hat{q}}-a,\frac{\hat{r}c}{\hat{s}}-a\right)=\left(\frac{\hat{p}c-a\hat{q}}{\hat{q}},\frac{\hat{r}-a\hat{s}_{0}}{\hat{s}_{0}}\right)\in\mathcal{F}_{n}(q,s).$

Since $\hat{q}<\hat{s}$, we have either $\hat{s}_{0}<\hat{q}$ or
$\hat{q}<\hat{s}_{0}<\hat{s}$. The latter implies $n<2\hat{s}_{0}$ i.e
$n<2\hat{s}/c$ which is not possible as $c\geq 2$. Thus, taking
$\hat{q}>\hat{s}_{0}$ we must have $\hat{q}=s$, $\hat{s}=cq$,
$\hat{p}c=s-r+as$ and $\hat{r}=q-p+aq.$

Further,

$\displaystyle\left(\frac{2\pi\hat{p}c}{\hat{q}},\frac{2\pi\hat{r}c}{\hat{s}}\right)=\left(\frac{2\pi(s-r)}{s}+2\pi
a,\frac{2\pi(q-p)}{q}+2\pi a\right).$

Thus, $\hat{\theta}c=\theta^{\prime}+2\pi a$, where
$\theta^{\prime}\in(\frac{2\pi(s-r)}{s},\frac{2\pi(q-p)}{q})$.

∎

######  Example 3.6.

Let
$\mathcal{F}_{n}(\hat{q},\hat{s})=\mathcal{F}_{6}(5,6)=\\{(\nicefrac{{4}}{{5}},\nicefrac{{5}}{{6}}),(\nicefrac{{1}}{{6}},\nicefrac{{1}}{{5}})\\}$,
$c=3$, and
$a:=\lfloor\frac{\hat{p}c}{\hat{q}}\rfloor=\lfloor\frac{\hat{r}c}{s}\rfloor=2$.
Then $F_{6}(5,6)\star 3=\mathcal{F}_{6}(2,5)$. In particular,

$(e^{\frac{4\cdot 2\pi i}{5}})^{3}=e^{\frac{2\cdot 2\pi i}{5}}\text{,
}(e^{\frac{5\cdot 2\pi i}{6}})^{3}=e^{\frac{2\pi i}{2}},$

and $\hat{\theta}\in(\frac{4\cdot 2\pi}{5},\frac{5\cdot 2\pi}{6})$ if and only
if $\theta^{\prime}=3\hat{\theta}-2\cdot 2\pi\in(\frac{2\cdot
2\pi}{5},\frac{2\pi}{2})$.

Now that we understand, when the endpoints of a Karpelevič arc are powers of
endpoints of another Karpelevič arc, we want to know when the whole arc is
mapped to another arc. To this end, we compute the derivative of the modulus
$\rho_{n}$ with respect to the argument $\theta$ of a Karpelevič arc at the
endpoints.

######  Lemma 3.7.

Suppose that $(\frac{p}{q},\frac{r}{s})$, $q<s$, is a Farey pair and for
$\theta\in[\nicefrac{{2\pi p}}{{q}},\nicefrac{{2\pi r}}{{s}}]$ let the point
on the boundary of $\Theta_{n}$ with the argument $\theta$ be given by
$\rho_{n}(\theta)e^{\mathrm{i}\theta}$. Then

$\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}}\sin\left(\frac{2\pi}{qd}\right)=\cos\left(\frac{2\pi}{qd}\right)-1$ (7)

and

$\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}}\sin\left(\frac{2\pi}{s}\right)=1-\cos\left(\frac{2\pi}{s}\right).$ (8)

###### Proof.

Implicit differentiation of equation (3) gives us:

$\displaystyle\mu^{s_{1}}q\cos(q\theta)+s_{1}\mu^{s_{1}-1}\frac{\partial\mu(\theta)}{\partial\theta}\Big{|}_{\theta}\sin(q\theta)-$
$\displaystyle\Big{[}\mu^{qd_{1}}\frac{s_{1}}{d_{1}}\cos\left(\frac{s_{1}}{d_{1}}\theta-\frac{2\pi
r}{d}\right)+qd_{1}\mu^{qd_{1}-1}\frac{\partial\mu(\theta)}{\partial\theta}\Big{|}_{\theta}\sin\left(\frac{s_{1}}{d_{1}}\theta-\frac{2\pi
r}{d}\right)\Big{]}-$
$\displaystyle\Big{[}(q-\frac{s_{1}}{d_{1}})\cos\left((q-\frac{s_{1}}{d_{1}})\theta+\frac{2\pi
r}{d}\right)\Big{]}=0.$

Taking $\mu=1$ we have:

$\displaystyle
q\cos(q\theta)+s_{1}\frac{\partial\mu(\theta)}{\partial\theta}\Big{|}_{\theta}\sin(q\theta)-$
$\displaystyle\Big{[}\frac{s_{1}}{d_{1}}\cos\Big{(}\frac{s_{1}}{d_{1}}\theta-\frac{2\pi
r}{d}\Big{)}+qd_{1}\frac{\partial\mu(\theta)}{\partial\theta}\sin\Big{(}\frac{s_{1}}{d_{1}}\theta-\frac{2\pi
r}{d}\Big{)}\Big{]}-$
$\displaystyle\Big{[}(q-\frac{s_{1}}{d_{1}})\cos\left((q-\frac{s_{1}}{d_{1}})\theta+\frac{2\pi
r}{d}\right)\Big{]}=0.$

Inserting $\theta=\frac{2\pi p}{q}$ and $\theta=\frac{2\pi r}{s}$ in above we
get:

$\displaystyle\frac{\partial\mu(\theta)}{\partial\theta}\Big{|}_{\theta=2\pi
p/q}\sin\left(\frac{2\pi}{qd}\right)=\frac{1}{d_{1}}\left(\cos\left(\frac{2\pi}{qd}\right)-1\right)$

and

$\displaystyle\frac{\partial\mu(\theta)}{\partial\theta}\Big{|}_{\theta=2\pi
r/s}\sin\left(\frac{2\pi}{s}\right)=\frac{1}{d_{1}}\left(1-\cos\left(\frac{2\pi}{s}\right)\right).$

Noting that, $\rho_{n}(\theta)=\mu(\theta)^{d_{1}}$ which implies
$\frac{\partial\rho_{n}(\theta)}{\partial\theta}=d_{1}\mu(\theta)^{d_{1}-1}\frac{\partial\mu}{\partial\theta}$,
equations (7) and (8) follow. ∎

######  Corollary 3.8.

Let $\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$,
$d:=\lfloor\nicefrac{{n}}{{q}}\rfloor$ and
$\hat{d}:=\lfloor\nicefrac{{n}}{{\hat{q}}}\rfloor$. Then:

  1. 1.

If $c$ divides $\hat{q}$, then $qd=\hat{q}\hat{d}$ and $s=\hat{s}$.

  2. 2.

If $c$ divides $\hat{s}$, then $qd=\hat{s}$ and $s=\hat{q}\hat{d}$.

###### Proof.

Let $F(x):=\frac{1-\cos(x)}{\sin(x)}$. Note that $F(x)$ is injective on
$[0,2\pi]$.

If $\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$, then for all
$\theta\in(\frac{2\pi p}{q},\frac{2\pi r}{s})$ we have
$\rho_{n}(\theta)=(\rho_{n}(\hat{\theta}))^{c}$ for
$\hat{\theta}\in\arg(\hat{q},\hat{s})$, where by Corollary 3.5:

$\hat{\theta}=\frac{1}{c}\left(\theta+2\pi a\right)\text{ if }c\text{ divides
}\hat{q},$ (9) $\hat{\theta}=\frac{1}{c}\left(2\pi-\theta+2\pi a\right)\text{
if }c\text{ divides }\hat{s}.$ (10)

In particular:

$\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}}=\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}},$ (11)
$\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}}=\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}},$ (12)

and

$\displaystyle\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}$
$\displaystyle=c\rho_{n}(\hat{\theta})^{c-1}\frac{\cdot\partial\rho_{n}(\hat{\theta})}{\partial\hat{\theta}}\frac{\partial\hat{\theta}}{\partial\theta}.$

  1. 1.

If $c$ divides $\hat{q}$, then :

$\frac{\partial\hat{\theta}}{\partial\theta}=\frac{1}{c},$

by equation (9). Now, by Lemma by 3.7:

$\displaystyle\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}}$
$\displaystyle=\frac{\cos\left(\frac{2\pi}{qd}\right)-1}{\sin\left(\frac{2\pi}{qd}\right)}=-F\left(\frac{2\pi}{qd}\right),$
$\displaystyle\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}}$
$\displaystyle=\frac{\partial\rho_{n}(\hat{\theta})}{\partial\hat{\theta}}\Big{|}_{\hat{\theta}=\frac{2\pi\hat{p}}{\hat{q}}}=\frac{\cos\left(\frac{2\pi}{\hat{q}\hat{d}}\right)-1}{\sin\left(\frac{2\pi}{\hat{q}\hat{d}}\right)}=-F\left(\frac{2\pi}{\hat{q}\hat{d}}\right),$

since $\rho_{n}(\hat{\theta})=1$ at the endpoints, and
$\hat{\theta}=\nicefrac{{2\pi\hat{p}}}{{\hat{q}}}$ when
$\theta=\nicefrac{{2\pi p}}{{q}}$. Hence,
$F\left(\frac{2\pi}{qd}\right)=F\left(\frac{2\pi}{\hat{q}\hat{d}}\right)$ by
equation (11) and by injectivity of $F$ we have $\hat{q}\hat{d}=qd$.

Similarly,
$\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}}=F\left(\frac{2\pi}{s}\right)$ and
$\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}}=F\left(\frac{2\pi}{\hat{s}}\right),$ which implies $\hat{s}=s$.

  2. 2.

If $c$ divides $\hat{s}$, then :

$\frac{\partial\hat{\theta}}{\partial\theta}=-\frac{1}{c},$

by equation (10). Now, by Lemma by 3.7:

$\displaystyle\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}}$
$\displaystyle=\frac{\cos\left(\frac{2\pi}{qd}\right)-1}{\sin\left(\frac{2\pi}{qd}\right)}=-F\left(\frac{2\pi}{qd}\right),$
$\displaystyle\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
p}{q}}$
$\displaystyle=-\frac{\partial\rho_{n}(\hat{\theta})}{\partial\hat{\theta}}\Big{|}_{\hat{\theta}=\frac{2\pi\hat{r}}{\hat{s}}}=\frac{\cos\left(\frac{2\pi}{\hat{s}}\right)-1}{\sin\left(\frac{2\pi}{\hat{s}}\right)}=-F\left(\frac{2\pi}{\hat{s}}\right),$

since $\rho_{n}(\hat{\theta})=1$ at the endpoints, and
$\hat{\theta}=\nicefrac{{2\pi\hat{r}}}{{\hat{s}}}$ when
$\theta=\nicefrac{{2\pi p}}{{q}}$. Hence,
$F\left(\frac{2\pi}{qd}\right)=F\left(\frac{2\pi}{\hat{s}}\right)$ by equation
(11) and by injectivity of $F$ we have $\hat{s}=qd$. Similarly, identities
$\frac{\partial\rho_{n}(\theta)}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}}=F\left(\frac{2\pi}{s}\right)$ and
$\frac{\partial(\rho_{n}(\hat{\theta}))^{c}}{\partial\theta}\Big{|}_{\theta=\frac{2\pi
r}{s}}=F\left(\frac{2\pi}{\hat{q}\hat{d}}\right)$ imply $\hat{q}\hat{d}=s$.

∎

The following example shows that $\mathcal{F}_{n}(\hat{q},\hat{s})\star
c=\mathcal{F}_{n}(q,s)$ does not imply
$\mathcal{K}_{n}(\hat{q},\hat{s})^{c}=\mathcal{K}_{n}(q,s)$.

######  Example 3.9.

Let $n=27$, $\mathcal{F}_{n}(\hat{q},\hat{s})=\mathcal{F}_{27}(4,27)$,
$\mathcal{F}_{n}(q,s)=\mathcal{F}_{27}(2,27)$ and $c=2$. Then:

$\mathcal{F}_{27}(4,27)\star 2=\mathcal{F}_{27}(2,27).$

We have $q=2$, $\hat{q}=4$, $d=13$ and $\hat{d}=6$. Clearly $c$ divides
$\hat{q}$ and $qd=26\neq\hat{q}\hat{d}=24$. Therefore
$\mathcal{K}_{n}(\hat{q},\hat{s})^{c}=\mathcal{K}_{27}(4,27)^{2}\neq\mathcal{K}_{27}(2,27)=\mathcal{K}_{n}(q,s)$
by Corollary 3.8.

######  Theorem 3.10.

Let $\mathcal{K}_{n}(q,s)\in\mathcal{K}_{n}$ and
$d:=\lfloor\nicefrac{{n}}{{q}}\rfloor$. Then
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$ if, and only if,
one of the following situations occurs:

  1. 1.

$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(cq,s)^{c}$, for any $c$ that divides
$d$, satisfies $\gcd(c,s)=1$ and $cq<s$.

  2. 2.

$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(s,qd)^{d}$ if $\delta:=\gcd(d,s)=1$.

###### Proof.

Let $\mathcal{K}_{n}(q,s)\in\mathcal{K}_{n}$ and
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$. Then
$\mathcal{F}_{n}(\hat{q},\hat{s})\star c=\mathcal{F}_{n}(q,s)$, and either $c$
divides $\hat{q}$ or $c$ divides $\hat{s}$ by Lemma 3.3. We consider each case
separately.

Assume first that $c$ divides $\hat{q}$ (and $\gcd(c,\hat{s})=1$). Hence,
$\hat{q}=qc$ and $\hat{s}=s$ by Corollary 3.5. Clearly, we also have
$\gcd(c,s)=1$. By Corollary 3.8 we now have $qd=qc\hat{d}$ which implies
$\hat{d}c=d$. Since $\hat{q}<\hat{s}$, $qc<s$ has to hold. With this, we have
shown that if $\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$ and
$c$ divides $\hat{q}$, then the conditions listed in item 1 have to hold.

Now, assuming $c$ divides $d$, $\gcd(c,s)=1$, and $cq<s$, we want to prove
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(cq,s)^{c}$. Let
$\theta\in(\nicefrac{{2\pi p}}{{q}},\nicefrac{{2\pi r}}{{s}})$, where
$(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})\in\mathcal{F}_{n}(q,s)$. Theorem
2.5 tells us that
$\rho_{n}(\theta)e^{i\theta}=\mu^{d_{1}}e^{i\theta}\in\mathcal{K}_{n}(q,s)$ if
and only if $\mu$ is the unique solution to (3).

To study $\hat{\lambda}\in\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$ with the
argument $\theta$, we first use Corollary 3.5 to identify parameters
associated with Farey pairs in $\mathcal{K}_{n}(\hat{q},\hat{s})$:

$\hat{s}=s,\,\hat{q}=cq,\,\hat{p}=p+aq,\,\text{ and }c\hat{r}=r+as,$ (13)

and note that $\hat{\theta}:=\frac{1}{c}(\theta+2\pi
a)\in(\nicefrac{{2\pi\hat{p}}}{{\hat{q}}},\nicefrac{{2\pi\hat{r}}}{{\hat{s}}})\subset\arg(\hat{q},\hat{s})$.
Now, $\gcd(c,s)=1$ implies $\gcd(c\hat{d},s)=\gcd(\hat{d},s)$ which gives us
$\hat{\delta}=\gcd(\hat{d},\hat{s})=\gcd(c\hat{d},s)=\gcd(d,s)=\delta.$ Hence:

$\hat{\delta}=\delta,\,\hat{s}_{1}=s_{1},\,\hat{d}_{1}c=d_{1},$ (14)

where $\hat{s}_{1}:=s_{1}(\hat{q},\hat{s})$ and
$\hat{d}_{1}:=d_{1}(\hat{q},\hat{s})$.

By Theorem 2.5,
$\hat{\mu}^{\hat{d}_{1}}e^{i\hat{\theta}}\in\mathcal{K}_{n}(cq,s)$ if and only
if $\hat{\mu}$ satisfies equation $\eqref{eq:implicit}$ for $\hat{\theta}$ and
the parameters associated with
$(\nicefrac{{\hat{p}}}{{\hat{q}}},\nicefrac{{\hat{r}}}{{\hat{s}}})$:

$\displaystyle\hat{\mu}^{\hat{s}_{1}}\sin(\hat{q}\hat{\theta})-\hat{\mu}^{\hat{q}\hat{d}_{1}}\sin\Big{(}\frac{\hat{s}_{1}}{\hat{d}_{1}}\hat{\theta}-\frac{2\pi\hat{r}}{\hat{d}}\Big{)}-\sin\Big{(}(\hat{q}-\frac{\hat{s}_{1}}{\hat{d}_{1}})\hat{\theta}+\frac{2\pi\hat{r}}{\hat{d}}\Big{)}=0.$
(15)

Using (13) and (14) we get:

$\displaystyle\hat{\mu}^{\hat{s}_{1}}\sin(\hat{q}\hat{\theta})$
$\displaystyle=\hat{\mu}^{s_{1}}\sin\left(q(\theta+2\pi
a)\right)=\hat{\mu}^{s_{1}}\sin(q\theta),$
$\displaystyle\mu^{\hat{q}\hat{d}_{1}}\sin\left(\frac{\hat{s}_{1}}{\hat{d}_{1}}\hat{\theta}-\frac{2\pi\hat{r}}{\hat{d}}\right)$
$\displaystyle={\hat{\mu}}^{qd_{1}}\sin\left(\frac{s_{1}}{d_{1}}(\theta+2\pi
a)-\frac{2\pi(r+as)}{d}\right)$
$\displaystyle={\hat{\mu}}^{qd_{1}}\sin\left(\frac{s_{1}}{d_{1}}\theta-\frac{2\pi
r}{d}\right),$
$\displaystyle\sin\left((\hat{q}-\frac{\hat{s}_{1}}{\hat{d}_{1}})\hat{\theta}+\frac{2\pi\hat{r}}{\hat{d}}\right)$
$\displaystyle=\sin\left((cq-\frac{cs_{1}}{d_{1}})\frac{(\theta+2\pi
a)}{c}+\frac{2\pi(r+as)}{d}\right)$
$\displaystyle=\sin\left((q-\frac{s_{1}}{d_{1}})\theta+\frac{2\pi
r}{d}\right),$

which proves that the coefficients of $\hat{\mu}$ in (15) and the coefficients
of $\mu$ in (3) agree. Since (3) defines $\mu$ uniquely, we conclude
$\hat{\mu}=\mu$. Finally,

$\hat{\lambda}^{c}=(\hat{\mu}^{\hat{d}_{1}}e^{i\hat{\theta}})^{c}=\mu^{d_{1}}e^{i\theta}=\rho_{n}(\theta)e^{i\theta}$

completes the proof that $\mathcal{K}_{n}(cq,s)^{c}=\mathcal{K}_{n}(q,s)$.

Next, assume that $c$ divides $\hat{s}$ (and $\gcd(c,\hat{q})=1$). Hence,
$\hat{s}=cq$ and $\hat{q}=s$ by Corollary 3.5. Now, by Corollary 3.8 we have
$qd=cq$ and $s=s\hat{d}$ which gives $c=d$ and $\hat{d}=1$. Therefore,
$\delta=\gcd(d,s)=\gcd(c,\hat{q})=1$, as required. This shows that if
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$ and $c$ divides
$\hat{s}$, then the condition in item 2 has to hold.

Now, assuming $\gcd(d,s)=1$, we want to prove
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(s,qd)^{d}$. Since, $c$ divides
$\hat{s}$, let
$\theta^{\prime}\in(\nicefrac{{2\pi(s-r)}}{{s}},\nicefrac{{2\pi(q-p)}}{{q}})$,
where
$\zeta=(\nicefrac{{(s-r)}}{{s}},\nicefrac{{(q-p)}}{{q}})\in\mathcal{F}_{n}(q,s)$.
By Remark 2.6,
$\rho_{n}e^{i\theta^{\prime}}=\mu^{d_{1}}e^{i\theta^{\prime}}\in\mathcal{K}_{n}(q,s)$
if and only if $\mu$ satisfies $\eqref{eq:implicit}$ for parameters associated
with $\zeta$ and $\theta=2\pi-\theta^{\prime}$. That is:

$\mu^{s_{1}}\sin(q(2\pi-\theta^{\prime}))-\mu^{qd_{1}}\sin\left(\frac{s_{1}}{d_{1}}(2\pi-\theta^{\prime})-\frac{2\pi
r}{d}\right)-\sin\left((q-\frac{s_{1}}{d_{1}})(2\pi-\theta^{\prime})+\frac{2\pi
r}{d}\right)=0,$

or equivalently:

$\displaystyle-\mu^{s_{1}}\sin(q\theta^{\prime})+\mu^{qd_{1}}\sin\left(\frac{s_{1}}{d_{1}}\theta^{\prime}+\frac{2\pi(r-s)}{d}\right)+\sin\left((q-\frac{s_{1}}{d_{1}})\theta^{\prime}+\frac{2\pi(s-r)}{d}\right)=0.$
(16)

To understand $\hat{\lambda}\in\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$ with the
argument $\theta^{\prime}$, we first use Corollary 3.5 to identify parameters
associated with Farey pairs in $\mathcal{K}_{n}(\hat{q},\hat{s})$:

$\hat{q}=s,\,\hat{s}=qc,\,\hat{p}c=s-r+as,\,\text{ and }\hat{r}=q-p+aq,$ (17)

and $\hat{\theta}=\frac{1}{c}(\theta^{\prime}+2\pi
a)\in(\nicefrac{{2\pi\hat{p}}}{{\hat{q}}},\nicefrac{{2\pi\hat{r}}}{{\hat{s}}})\subset\arg(\hat{q},\hat{s})$.
In addition: $c=d$, $\hat{d}=1$, and $\hat{d}_{1}=1.$

Theorem 2.5 tells us that
$\hat{\lambda}=\hat{\mu}^{\hat{d}_{1}}e^{i\hat{\theta}}\in\mathcal{K}_{n}(s,qd)$
if and only of $\hat{\mu}$ satisfies (15) for parameters associated with
$(\nicefrac{{\hat{p}}}{{\hat{q}}},\nicefrac{{\hat{r}}}{{\hat{s}}})$ and
$\hat{\theta}$. Using the parameters defined above, we get:

$\displaystyle\hat{\mu}^{\hat{s}_{1}}\sin(\hat{q}\hat{\theta})$
$\displaystyle=\hat{\mu}^{qd}\sin\left(\frac{s}{d}\theta^{\prime}+2\pi\frac{as}{d}\right),$
$\displaystyle\hat{\mu}^{\hat{q}\hat{d}_{1}}\sin\left(\frac{\hat{s}_{1}}{\hat{d}_{1}}\hat{\theta}-\frac{2\pi\hat{r}}{\hat{d}}\right)$
$\displaystyle={\hat{\mu}}^{s}\sin\left(q\theta^{\prime}\right),$
$\displaystyle\sin\left((\hat{q}-\frac{\hat{s}_{1}}{\hat{d}_{1}})\hat{\theta}+\frac{2\pi\hat{r}}{\hat{d}}\right)$
$\displaystyle=\sin\left((\frac{s}{d}-q)(\theta^{\prime}+2\pi a)\right)$
$\displaystyle=\sin\left((\frac{s}{d}-q)\theta^{\prime}+\frac{2\pi
as}{d}\right).$

Since $as=\hat{p}d-s+r$ implies that the coefficients of $\hat{\mu}$ in (15)
and the coefficients of $\mu$ in (16) are the same, we can conclude that
$\hat{\mu}=\mu$. Hence,
$\hat{\lambda}^{d}=(\hat{\mu}^{\hat{d}_{1}}e^{i\hat{\theta}})^{d}=\mu^{d_{1}}e^{i\theta^{\prime}}=\rho_{n}(\theta)e^{i\theta^{\prime}}$
i.e $\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(s,qd)^{d}$, as required. ∎

######  Example 3.11.

Theorem 3.10 allows us to identify all Karpelevič arcs that are powers of
another arc. In particular, for $n=8$ we list all such cases below:

  1. 1.

$\mathcal{K}_{8}(4,7)=\mathcal{K}_{8}(7,8)^{2}$

  2. 2.

$\mathcal{K}_{8}(2,7)=\mathcal{K}_{8}(7,8)^{4}=K_{8}(4,7)^{2}$

  3. 3.

$\mathcal{K}_{8}(3,7)=\mathcal{K}_{8}(7,6)^{2}$

  4. 4.

$\mathcal{K}_{8}(4,5)=\mathcal{K}_{8}(5,8)^{2}.$

As an example let us consider $\mathcal{K}_{8}(4,7)$, with $q=4$, $s=7$, $d=2$
and $\delta=1$. Hence, $\mathcal{K}_{8}(4,7)=\mathcal{K}_{8}(7,8)^{2}$, by
item 1 in the theorem. Considering $\mathcal{K}_{8}(2,7)$ with $q=2$, $s=7$,
$d=4$, $\delta=1$, we have $\mathcal{K}_{8}(2,7)=\mathcal{K}_{8}(7,8)^{4}$ by
item 2. Also, $c=2$ divides $d=4$ which implies
$\mathcal{K}_{8}(2,7)=\mathcal{K}_{8}(4,7)^{2}$ by item 1.

Theorem 3.10 answers the question, given $\mathcal{K}_{n}(q,s)$, what are all
possible arcs $\mathcal{K}_{n}(\hat{q},\hat{s})$ whose power is
$\mathcal{K}_{n}(q,s)$. Since the theorem gives the complete characterisation,
it also answers the question, given $\mathcal{K}_{n}(\hat{q},\hat{s})$, what
are all possible arcs $\mathcal{K}_{n}(q,s)$ that are powers of
$\mathcal{K}_{n}(\hat{q},\hat{s})$. This point of view is given in the result
below.

######  Corollary 3.12.

Let $\mathcal{K}_{n}(\hat{q},\hat{s})\in\mathcal{K}_{n}$ and
$\hat{d}:=\lfloor\nicefrac{{n}}{{q}}\rfloor$. Then
$\mathcal{K}_{n}(\hat{q},\hat{s})^{c}=\mathcal{K}_{n}(q,s)\in\mathcal{K}_{n}$
if and only if one of the following situations occurs:

  1. 1.

$\mathcal{K}_{n}(\hat{q},\hat{s})^{c}=\mathcal{K}_{n}(\nicefrac{{\hat{q}}}{{c}},\hat{s})$
for all $c$ that divide $\hat{q}$ and satisfy
$|\hat{s}-\hat{q}\hat{d}|<\nicefrac{{\hat{q}}}{{c}}$.

  2. 2.

$\mathcal{K}_{n}(\hat{q},\hat{s})^{c}=\mathcal{K}_{n}(\nicefrac{{\hat{s}}}{{c}},\hat{q})$,
for all $c$ that divide $\hat{s}$ and satisfy
$n-\hat{q}<\nicefrac{{\hat{s}}}{{c}}$.

##  4 Stochastic matrices and associated digraphs, notation and background

In the second part of the paper, we consider the question, of when a
stochastic matrix, that realises an eigenvalue on the border of the Karpelevič
region, can be written as a power of another stochastic matrix. This section
is dedicated to the necessary background and notation.

###  4.1 Notation

When taking powers of matrices and the associated digraphs, we will repeatedly
encounter modular arithmetic. Since we want to use the standard numbering of
the rows and columns of $n\times n$ matrices from $1$ to $n$, it is convenient
to define: $\langle k\rangle_{n}:=1+((k-1)\mod n)$. In this notation $\langle
k\rangle_{n}\in\\{1,\ldots,n\\}$.

Given $n\in\mathbb{N}$ we define the following vectors:

$\displaystyle{\bf a}(n)$
$\displaystyle:=\left(\begin{matrix}1&2&\ldots&n\end{matrix}\right),$
$\displaystyle{\bf a_{0}}(n)$
$\displaystyle:=\left(\begin{matrix}0&1&\ldots&n-1\end{matrix}\right),$
$\displaystyle{\bf e}$
$\displaystyle:=\left(\begin{matrix}1&1&\ldots&1\end{matrix}\right),$

where the size of ${\bf e}$ will be clear from the context. In addition, we
will depend on standard operations to build new vectors. For example,
$i\cdot{\bf a}(n)=\left(\begin{matrix}i&2i&\ldots&ni\end{matrix}\right)$,
$i\cdot{\bf e}+{\bf
a}(n)=\left(\begin{matrix}i+1&i+2&\ldots&i+n\end{matrix}\right)$, etc.
Furthermore, for ${\bf v}=\left(\begin{matrix}v_{1}&\ldots
v_{k}\end{matrix}\right)\in\leavevmode\nobreak\ \mathbb{N}_{0}^{k}$ we denote:

$\mathscr{T}({\bf v}):=\\{\left(\begin{matrix}v_{i}&v_{\langle
i+1\rangle_{k}}&\ldots&v_{\langle
i+k-1\rangle_{k}}\end{matrix}\right);i=1,\ldots,k\\}$

to be the set of vectors obtained from ${\bf v}$ by cyclic permutations of its
elements.

A digraph $G$ is defined by its vertex set $V(G)=\\{1,\ldots,n\\}$ and edge
set $E(G)\subseteq V(G)\times V(G)$. For ${\bf
v}=\left(\begin{matrix}v_{1}&\ldots v_{k}\end{matrix}\right)\in\mathbb{N}^{k}$
we denote by $C({\bf v})$ the $k$-cycle with $V(C({\bf
v}))=\\{{v}_{i};i=1,\ldots,k\\}$ and $E(C({\bf v}))=\\{({v}_{i},{v}_{\langle
1+i\rangle_{k}});i=1,\ldots,k\\}$. Clearly, $C({\bf v})=C({\bf u})$ if and
only if $\mathscr{T}({\bf v})=\mathscr{T}({\bf u})$. The _weight of a cycle_
is defined to be the product of the weights on the edges of that cycle.
Furthermore, $P({\bf v})$ will denote the path with $V(P({\bf
v}))=\\{{v}_{i};i=1,\ldots,k\\}$ and $E(P({\bf
v}))=\\{({v}_{i},{v}_{i+1});i=1,\ldots,k-1\\}.$ Let $\mathcal{E}\subset
V(G)\times V(G)$, then $G+\mathcal{E}$ is defined to be the digraph with
$V(G+\mathcal{E})=V(G)$ and $E(G+\mathcal{E})=E(G)+\mathcal{E}$. With
$G^{(b)}$ we denote the strong power of $G$, i.e. the digraph on vertex set
$V(G)$, where $(v_{1},v_{2})\in E(G^{(b)})$ if and only if $v_{1}$ and $v_{2}$
are at distance $b$ in $G$. Given a nonnegative $n\times n$ matrix $A$, we
define $\Gamma(A)$ to be _the digraph associated with $A$_ defined by
$V(\Gamma(A))=\\{1,2,\ldots,n\\}$ and $E(\Gamma(A))=\\{(i,j);(A)_{i,j}\neq
0\\}$.

For integers $q,s,n\in\mathbb{N}$ satisfying $q<s$, $\gcd(q,s)=1$ and $q+s>n$,
we denote by $\mathcal{M}_{n}(q,s)$ the set of all $n\times n$ stochastic
matrices with an eigenvalue from $\mathcal{K}_{n}(q,s)$. The set of sparsest
matrices in $\mathcal{M}_{n}(q,s)$ is denoted by $\mathcal{M}_{n}^{0}(q,s)$.
More precisely, $A\in\mathcal{M}_{n}^{0}(q,s)$ if and only if
$A=(a_{ij})\in\mathcal{M}_{n}(q,s)$ and there does not exist
$A^{\prime}=(a^{\prime}_{ij})\in\mathcal{M}_{n}(q,s)$ satisfying
$\\{(i,j);a^{\prime}_{ij}\neq 0\\}\subset\\{(i,j);a_{ij}\neq 0\\}$. (It turns
out that, for fixed $n$, $q$ and $s$, all matrices in
$\mathcal{M}^{0}_{n}(q,s)$ have the same number of nonzero elements, hence
$\mathcal{M}^{0}_{n}(q,s)$ can also be defined as the set of matrices in
$\mathcal{M}_{n}(q,s)$ with the least number of non-zero entries.)

Let $\mathcal{S}$ be a set of $n\times n$ matrices and $c\in\mathbb{N}$, then
$\mathcal{S}^{c}:=\\{A^{c};A\in\mathcal{S}\\}$. For $n\times m$ matrix $M$,
let $\operatorname{vec}(M)$ denote the $m\cdot n$ vector obtained by stacking
the columns of the matrix $M$.

###  4.2 Sparsest realisations of Ito polynomials

In [7] the sparsest realizing matrices for Ito polynomials of degree $n$ were
characterised. Given a reduced Ito polynomial $f_{\alpha}(t)$ of degree $n$
associated with $\mathcal{K}_{n}(q,s)$, the sparsest realisation of
$f_{\alpha}(t)$ is (up to permutation similarity) uniquely defined by the
associated digraph. Moreover, associated digraphs are precisely digraphs on
$n$ vertices that contain one $s$-cycle and $d$ disjoint $q$-cycles.

Let $q,s,\hat{q},\hat{s},n$ and $c$ be such that
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(\hat{q},\hat{s})^{c}$. Then:

$\displaystyle\mathcal{M}_{n}(\hat{q},\hat{s})^{c}$
$\displaystyle\subset\mathcal{M}_{n}(q,s),$
$\displaystyle\mathcal{M}_{n}^{0}(\hat{q},\hat{s})^{c}$
$\displaystyle\subset\mathcal{M}_{n}^{0}(q,s),$

but $\mathcal{M}_{n}(\hat{q},\hat{s})^{c}\neq\mathcal{M}_{n}(q,s)$ and
$\mathcal{M}_{n}^{0}(\hat{q},\hat{s})^{c}\neq\mathcal{M}_{n}^{0}(q,s)$. In
this section, we aim to characterise matrices in
$\mathcal{M}_{n}^{0}(\hat{q},\hat{s})^{c}$ in terms of the associated
digraphs. For this, we first recall the characterisation of
$\mathcal{M}_{n}^{0}(q,s)$ given in [7] that depends on separating the
Karpelevič arcs into four categories: Type 0, I, II, and III. This separation
was introduced by Johnson and Paparella [3].

While it is possible for the degree of the reduced Ito polynomial associated
with a Farey pair $(\nicefrac{{p}}{{q}},\nicefrac{{r}}{{s}})$ of order $n$ to
be less than $n$, we will consider only the situations when $n$ and the degree
of the reduced Ito polynomial agree. For example, the reduced Ito polynomials
associated with $\mathcal{K}_{n}(3,14)$ for $n=15$ and $n=16$ are both equal
to $f_{\alpha}(t)=(t^{3}-(1-\alpha))^{5}-\alpha^{5}t,$ $\alpha\in[0,1]$. But
since for $n=16$, this polynomial has a degree less than $n$, our
investigation will not cover this case.

Below we list the different types of reduced Ito polynomials of order $n$,
using the notation introduced in [7]:

  * •

Type 0: If $n=s,d=n,q=1$, then $f_{\alpha}(t)=(t+\alpha-1)^{n}-\alpha^{n}$ for
$\alpha\in[0,1]$.

  * •

Type I: If $n=s,d=1,q>n/2$, then
$f_{\alpha}(t)=t^{n}-(1-\alpha)t^{n-q}-\alpha$ for $\alpha\in[0,1]$.

  * •

Type II: If $n=qd,d>1$, then
$f_{\alpha}(t)=(t^{q}+\alpha-1)^{d}-\alpha^{d}t^{z}$, where $z=qd-s$ and
$z\in\\{1,\ldots,q-1\\}$ for $\alpha\in[0,1]$.

  * •

Type III: If $n=s,d>1$, then
$f_{\alpha}(t)=t^{y}(t^{q}+\alpha-1)^{d}-\alpha^{d}$, where $y=s-qd$ and
$y\in\\{1,\ldots,q-1\\}$ for $\alpha\in[0,1]$.

Next, we recall results from [7] that characterise the sparsest realising
matrices for Type I, II, and III reduced Ito polynomials, through their
associated digraphs.

######  Theorem 4.1 ([7], Type I).

Let $q,n\in\mathbb{N}$, $\gcd(q,n)=1$ and $2q>n>q$. Then for a stochastic
matrix $A$, the following statements are equivalent:

  1. 1.

$A\in\mathcal{M}_{n}^{0}(q,s).$

  2. 2.

$\Gamma(A)$ is up to isomorphism equal to $\Gamma=C({\bf a}(n))+\\{(q,1)\\}$.

  3. 3.

$\Gamma(A)$ has one $n$-cycle, one $q$-cycle and no other cycles.

In addition, if the weight on the edge $(q,1)$ in $\Gamma(A)$ is equal to
$(1-\alpha)$, then the characteristic polynomial of $A$ is
$f_{\alpha}(t)=(t+\alpha-1)^{n}-\alpha^{n}$ .

######  Theorem 4.2 ([7], Type II).

Let $n=qd$, $s=qd-z$ where $z\in\\{1,\ldots,q-1\\}$, $\gcd(q,s)=1$, $d\geq 2$.
For a stochastic matrix $A$, the following statements are equivalent:

  1. 1.

$A\in\mathcal{M}_{n}^{0}(q,s).$

  2. 2.

$\Gamma(A)$ is up to isomorphism equal to

$\Gamma=\cup_{i=1}^{d}\left(C\left(q(i-1)\cdot{\bf e}+{\bf
a}(q)\right)+\left\\{(iq-z_{i},\langle 1+iq\rangle_{n})\right\\}\right),$ (18)

where $z_{i}$ correspond to some (ordered) partition of $z$ into $d$ parts:
$z=z_{1}+\ldots+z_{d}$, $z_{i}\geq 0$. Furthermore, all the edges $(iq-
z_{i},\langle 1+iq\rangle_{n}),i=1,\ldots,d$, have equal weight $\alpha$, for
some $\alpha\in(0,1)$.

  3. 3.

$\Gamma(A)$ has $d$ $q$-cycles, one $s$-cycle, and no other cycles. All
$q$-cycles have equal weight.

For $A$ to have the characteristic polynomial
$f_{\alpha}(t)=(t^{q}+\alpha-1)^{d}-\alpha^{d}t^{z}$, the weights on all the
edges $(iq-z_{i},\langle 1+iq\rangle_{n})$, $i=1\ldots,d$, have to be equal to
$\alpha$.

In the second item of the above theorem, a detailed description of the digraph
$\Gamma(A)$ is given, where $z_{i}$ count the number of vertices on the $i$-th
$q$-cycle $C(q(i-1)\cdot{\bf e}+{\bf a}(q))$ that are not included in the
(unique) $s$-cycle in $\Gamma(A)$. Different partitions of $z$ will result in
different graphs $\Gamma(A)$. To identify the partitions that produce non-
isomorphic graphs we offer the following definition.

######  Definition 4.3.

Let $A\in\mathcal{M}_{n}^{0}(q,s)$, $n=qd$, $s=qd-z$, where $\Gamma(A)$ is
isomorphic to a directed graph of the form (18) for the partition
$z=z_{1}+\ldots+z_{d}$. Let $\bf
z=\left(\begin{matrix}z_{1}&\ldots&z_{d}\end{matrix}\right)$. We say that
$\mathscr{T}(\bf z)$ is _the partition class_ of $A$, denoted by
$\operatorname{{\mathscr{P}}_{\text{\emph{\tiny{II }}}}}2(A)$.

Note that the partition class $\mathscr{T}(\bf z)$ determines
$A\in\mathcal{M}_{n}^{0}(q,s)$ up to permutation similarity, and the
associated directed graph up to isomorphism.

######  Theorem 4.4 ([7], Type III).

Let $n=qd+y$, where $\gcd(q,n)=1$, $d\geq 2$, and $y\in\\{1,\ldots,q-1\\}$.
For a stochastic matrix $A$, the following statements are equivalent:

  1. 1.

$A\in\mathcal{M}_{n}^{0}(q,s).$

  2. 2.

$\Gamma(A)$ is up to isomorphism equal to

$\Gamma=C\left({\bf
a}\left(n\right)\right)+\left\\{\left(iq+\sum_{k=1}^{i}y_{k},1+(i-1)q+\sum_{k=1}^{i}y_{k}\right);i=1,\ldots,d\right\\},$
(19)

where $y_{i}$ correspond to an (ordered) partition of $y$ into $d$ parts:
$y=y_{1}+\ldots+y_{d}$, $y_{i}\geq 0.$ In addition, the edges
$(iq+\sum_{k=1}^{i}y_{k},1+(i-1)q+\sum_{k=1}^{i}y_{k}),i=1,\ldots,d$, all have
the same weight.

  3. 3.

$\Gamma(A)$ has $d$ $q$-cycles, one $n$-cycle, and no other cycles, where the
weights on each of the $q$-cycles are equal.

For $A$ to have the characteristic polynomial
$f_{\alpha}(t)=t^{y}(t^{q}+\alpha-1)^{d}-\alpha^{d}$, the weights on the edges
$(iq+\sum_{k=1}^{i}y_{k},1+(i-1)q+\sum_{k=1}^{i}y_{k})$, $i=1,\ldots,d$, have
to be equal to $1-\alpha$.

In the theorem above, a digraph $\Gamma$ consists of $d$ $q$-cycles and an
$s$-cycle that contains all the vertices of the $q$-cycles together with paths
that connect the $q$-cycles. The partition of $y$ determines the number of
vertices on those connecting paths. To recognize partitions that produce non-
isomorphic graphs described in item 2 of the theorem above, we introduce the
following definition.

######  Definition 4.5.

Let $A\in\mathcal{M}_{n}^{0}(q,s)$, $n=qd+y$, $\gcd(q,n)=1$, $d\geq 2$, where
$\Gamma(A)$ is isomorphic to a directed graph of the form (19) for the
partition $y=y_{1}+\ldots+y_{d}$. Let $\bf
y=\left(\begin{matrix}y_{1}&\ldots&y_{d}\end{matrix}\right)$. We say that
$\mathscr{T}(\bf y)$ is _the partition class_ of $A$, denoted by
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.

To summarise, in all cases (Type I, II, and III) the sparsest realising
matrices for the arc $\mathcal{K}_{n}(q,s)$ are completely described by their
digraphs and the weights on $q$-cycles in the digraphs. Moreover, the digraph
for Type I is unique, for Type II and III the digraphs are associated with the
partitions of $z$ and $y$, respectively.

###  4.3 Power of a single cycle

The following well-known lemma on the powers of a cycle will be needed to
study the powers of digraphs associated with stochastic matrices. A short
proof is given for completeness.

######  Lemma 4.6.

Let $C({\bf a}(k))$ be a cycle with $k$ vertices, $c,h\in\mathbb{N}$ so that
$\gcd(c,k)=h$. Furthermore, let $k=k_{1}h$, $c=c_{1}h$,
$c_{1},k_{1}\in\mathbb{N}$. Then $C({\bf a}(k))^{(c)}$ is a digraph with $h$
cycles of order $k_{1}$, i.e $C({\bf a}(k))^{(c)}=\cup_{i=1}^{h}C_{i}$, where

$\displaystyle C_{i}=C\left(i\cdot{\bf e}+\langle c\cdot{\bf
a}_{0}(k_{1}-1)\rangle_{k}\right).$ (20)

###### Proof.

Since any vertex $i\in V(C({\bf a}(k)))$ has a unique vertex at a distance $c$
in $C({\bf a}(k))$, there is a unique edge outgoing from $i$: $(i,{\langle
i+c\rangle_{k}})\in E(C({\bf a}(k))^{(c)})$. Furthermore, for any
$i\in\\{1,2,\ldots,k\\}$, the vertices ${\langle i+\ell c\rangle_{k}}$,
$\ell\in\\{0,\ldots,k_{1}-1\\}$, form a cycle of order $k_{1}$ in $C({\bf
a}(k))^{(c)}$. This follows from $\langle i+k_{1}c\rangle_{k}=\langle
i\rangle_{k}$ and $\langle i+\ell c\rangle_{k}\neq\langle i\rangle_{k}$ for
any $\ell<k_{1}$. Finally, $k=k_{1}h$ implies that there are $h$ cycles of
order $k_{1}$ in $C({\bf a}(k))^{(c)}$. ∎

The next remark considers two special cases of the above lemma, that we will
encounter in the upcoming sections.

######  Remark 4.7.

We consider the $c$-th strong power of $C({\bf a}(k))$ in the case when $c$
divides $k$ and in the case when $\gcd(c,k)=1$.

  1. 1.

If $k=k_{1}c$ then $C({\bf a}(k))^{(c)}=\cup_{i=1}^{c}C_{i}$, where
$C_{i}=C(i\cdot{\bf e}+\langle c\cdot{\bf a}_{0}(k_{1}-1)\rangle_{k}).$

  2. 2.

If $\gcd(k,c)=1$, then $C({\bf a}(k))^{(c)}=C(\langle c\cdot{\bf
a}(k)\rangle_{k})$.

##  5 Powers of Sparsest Realising Matrices

###  5.1 Type II arc is a power of a Type I arc

In this subsection we assume $n=dq$, $\gcd(qd,z)=1$, $z\in\\{1,\ldots,q-1\\}$.
From Theorem 3.10 and Corollary 3.12 we have:

$\mathcal{K}_{dq}(dq-z,qd)^{d}=\mathcal{K}_{dq}(q,qd-z).$

The theorem below determines the partition class of $B^{d}$ for
$B\in\mathcal{M}_{n}^{0}(dq-z,qd)$.

######  Theorem 5.1.

Let $B\in\mathcal{M}_{n}^{0}(dq-z,qd)$, where $d\geq 2$, $n=qd$,
$\gcd(qd,z)=1$ and $z\in\\{1,\ldots,q-1\\}$. We define $\beta:=d-\langle
z\rangle_{d}$, $w:=\frac{z-\langle z\rangle_{d}}{d}$, and for $j=1,\ldots,d$:

$z(j):=\begin{cases}w&\text{ for }j=1,\ldots,\beta\\\ w+1&\text{ for
}j=\beta+1,\ldots,d.\end{cases}$

The elements of the partition class
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$ consist of the parts $z(j)$,
$j=1,\ldots,d$, where the part $z(j)$ is followed by the part $z(\langle
j-\beta\rangle_{d})$ in the partition.

###### Proof.

Let $B\in\mathcal{M}_{n}^{0}(\hat{q},\hat{s})$, where $\hat{q}=s=qd-z$,
$\hat{s}=qd$, $\gcd(\hat{q},n)=1$ and $2\hat{q}>n>\hat{q}$.

Digraph. By Theorem 4.1, $\Gamma(B)$ is isomorphic to
$\widehat{\Gamma}=C({\bf{a}}(n))+\\{(s,1)\\}$. First, we want to find a
digraph $\Gamma$ that is isomorphic to $\widehat{\Gamma}^{(d)}$.

Taking $k=n$, $c=d$ and $k_{1}=q$ in the first part of Remark 4.7, we get
$C({\bf a}(n))^{(d)}=C({\bf a}(qd))^{(d)}=\cup_{j=1}^{d}C_{j}$, where

$\displaystyle C_{j}:=C(j\cdot{\bf e}+d\cdot{\bf a}_{0}(q-1))$ (21)

is a $q$-cycle in $\widehat{\Gamma}^{(d)}$. Furthermore, the edge
$\hat{e}=(s,1)$ in $\widehat{\Gamma}$ contributes the following edges in
$\widehat{\Gamma}^{(d)}$:

$\displaystyle e_{t}:=(s-t+1,1+d-t),t=1,\ldots,d,$ (22)

where we define $e_{t}:=(v_{O}(t),v_{I}(t))$ for later use. With this, we have
determined $\widehat{\Gamma}^{(d)}$ to be:

$\widehat{\Gamma}^{(d)}=\cup_{j=1}^{d}C_{j}+\\{e_{t}:t=1,\ldots,d\\}.$

In addition, if the edge $\hat{e}$ has weight $1-\alpha$ in
$\widehat{\Gamma}$, then all the $q$-cycles, $C_{j},j=1,\ldots,d$, have equal
weight $\alpha$ in $\widehat{\Gamma}^{(d)}$.

Finally, note that the edges $e_{t},t=1,\ldots,d$, connect the $q$-cycles
$C_{j},j=1,\ldots,d$, to form an $s$-cycle in $\widehat{\Gamma}^{(d)}$. The
$s$-cycle in $\widehat{\Gamma}^{(d)}$ consists of all the edges $e_{t}$ and
certain paths that are subgraphs of $C_{j}$’s. The lengths of those paths will
help us to determine the partition class of $B^{d}$.

The ordering of parts in the partition. Let $z(j)$ be the number of vertices
in $V(C_{j})$ that do not belong to the $s$-cycle in $\widehat{\Gamma}^{(d)}$.
Note that the elements of $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$
consist of $z(j)$ in some order.

To determine the order of $z(j)$ in
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$ we fix $j\in\\{1,\ldots,d\\}$
and note that there exists a unique $t^{\prime}\in\\{1,\ldots,d\\}$ such that
$v_{I}(t^{\prime})\in V(C_{j})$. We say that $e_{t^{\prime}}$ is the incoming
edge for $C_{j}$. From $v_{I}(t^{\prime})=1+d-t^{\prime}$ and
$V(C_{j})=\\{j+\ell d:\ell=0,\ldots,q-1\\}$, we conclude that if
$e_{t^{\prime}}$ is the incoming edge for our fixed $C_{j}$, then
$j+t^{\prime}$ is congruent $1$ modulo $d$. Thus, $e_{\langle 1-j\rangle_{d}}$
is the incoming edge for $C_{j}$. Similarly, there exists a unique $t$ such
that $v_{O}(t)\in V(C_{j})$ and we say that $e_{t}$ is the outgoing edge from
$C_{j}$. For this to be true, we must have $j+t$ congruent to $1-z$ modulo
$d$. This relation, and the fact that $t\in\\{1,\ldots,d\\}$, uniquely define
$t$ to be:

$\displaystyle t:=\begin{cases}\beta+1-j,&\text{ for }j=1,\ldots,\beta,\\\
\beta+1+d-j,&\text{ for }j=\beta+1,\ldots,d,\end{cases}$ (23)

where $\beta=d-\langle z\rangle_{d}$. For this $t$ we get:

$v_{I}(t)=\begin{cases}d+(j-\beta),&\text{ for }j=1,\ldots,\beta,\\\
j-\beta,&\text{ for }j=\beta+1,\ldots,d,\end{cases}$

from (22) and (23). In particular, $v_{I}(t)\in C_{\langle
j-\beta\rangle_{d}}$ and $C_{j}$ is connected to $C_{\langle
j-\beta\rangle_{d}}$ in the $s$-cycle in $\widehat{\Gamma}^{(d)}$.
Equivalently, $z(j)$ is followed by $z(\langle j-\beta\rangle_{d})$ in the
partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$.

Parts of the partition. To determine the parts that appear in the partition
class of $B^{d}$, we need to determine the lengths of the paths that are
intersections of the $q$-cycles $C_{j}$ and the $s$-cycle in
$\widehat{\Gamma}^{(d)}$. In other words, the number of vertices in such a
path is the same as the number of vertices $C_{j}$ is contributing to the
$s$-cycle in $\widehat{\Gamma}^{(d)}$. It is clear from the discussion so far
that $v_{I}(\langle 1-j\rangle_{d})$ is the first and $v_{O}(\langle
1-z-j\rangle_{d})$ is the last vertex on this path. From (22) and (23) we get
$v_{I}(\langle j-1\rangle_{d})=j$ and

$\displaystyle v_{O}(t)$ $\displaystyle=\begin{cases}qd-z-\beta+j,&\text{ for
}j=1,\ldots,\beta\\\ qd-z-\beta-d+j,&\text{ for
}j=\beta+1,\ldots,d,\end{cases}$
$\displaystyle=\begin{cases}(q-w-1)d+j,&\text{ for }j=1,\ldots,\beta\\\
(q-w-2)d+j,&\text{ for }j=\beta+1,\ldots,d,\end{cases}$

where $\beta=d-\langle z\rangle_{d}$ and $w:=\frac{z-\langle
z\rangle_{d}}{d}$.

Let $k(j)$ denote the number of vertices from $C_{j}$ that are contained in
the $s$-cycle. Since vertices in $C_{j}$ are consecutively numbered by $j+\ell
d,\ell=0,\ldots,q-1$, we have:

$k(j)=\begin{cases}q-w,&\text{ for }j=1,\ldots,\beta\\\ q-w-1,&\text{ for
}j=\beta+1,\ldots,d,\end{cases}$

or equivalently, $z(j):=q-k(j)$ is the number of vertices from $C_{j}$ that
are not on the $s$-cycle. With this, we have determined the numbers that
appear in the partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$.
∎

######  Remark 5.2.

For $B\in\mathcal{M}_{n}^{0}(qd-z,qd)$, let us define the row vector ${\bf z}$
consisting of parts of the partition class
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$: ${\bf
z}:=\left(\begin{matrix}z(1)&\ldots&z(d)\end{matrix}\right)$ as in Theorem
5.1. Since, $z(j)$ is followed by $z(\langle j-\beta\rangle_{d})$ in the
partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$, we need to
permute the elements of ${\bf z}$ to get the row vector:

${\bf z^{\prime}}:=\left(\begin{matrix}z(1)&z(\langle
1-\beta\rangle_{d})&\ldots&z(\langle
1-(d-1)\beta)\rangle_{d}\end{matrix}\right).$

which belongs to the partition class
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{d})$.

######  Example 5.3.

For $n=120$ we have $\mathcal{K}_{n}(15,109)=\mathcal{K}_{n}(109,120)^{8}$.
Below we follow the steps of the proof of Theorem 5.1 for
$B\in\mathcal{M}_{n}^{0}(109,120)$. We assume the notation developed in the
proof. In particular, $q=15$, $s=109$, $d=8$, $\hat{q}=s=109$,
$\hat{s}=qd=120$ and $z=qd-s=11$.

Digraph. Let the digraph of $B$ be $\widehat{\Gamma}=C({\bf
a}(120))+\\{(109,1)\\}$. Then $\widehat{\Gamma}^{(8)}$ consists of $8$ cycles
of order $15$: $C(j\cdot{\bf e}+8\cdot{\bf a}_{0}(15))$, $j=1,\ldots,8$, and
additional edges $\\{(110-t,9-t):t=1,\ldots,8\\}$ that connect the $15$-cycles
to form a $109$-cycle in $\widehat{\Gamma}^{(8)}$. Note that the weights on
the edges $(110-t,9-t)$, $t=1,\ldots,8$, in $\widehat{\Gamma}^{(8)}$ are the
same as the weight on the edge $(109,1)$ in $\widehat{\Gamma}$.

Partition. From $\beta=5$ and $w=1$ we determine the parts of the partition
class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{8})$:

$z(j)=\begin{cases}1&\text{ for }j=1,\ldots,5\\\ 2&\text{ for
}j=6,7,8.\end{cases}$

The vector ${\bf z^{\prime}}$ defined in Remark 5.2 is:

$\displaystyle{\bf z^{\prime}}$
$\displaystyle=\left(\begin{matrix}z(1)&z(4)&z(7)&z(2)&z(5)&z(8)&z(3)&z(6)\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}1&1&2&1&1&2&1&2\\\ \end{matrix}\right),$

and $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{8})=\mathscr{T}({\bf
z^{\prime}})$.

######  Corollary 5.4.

Let $A\in\mathcal{M}_{n}^{0}(q,qd-z)$ have the associated partition
$\left(\begin{matrix}z_{1}&\ldots&z_{d}\end{matrix}\right)\in\leavevmode\nobreak\
\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$. Then $A=B^{d}$ for some
$B\in\mathcal{M}_{n}^{0}(qd-z,qd)$ if and only if:

  1. 1.

There exists $w$ such that $z_{j}\in\\{w,w+1\\}$. (If all $z_{j}$ are equal
then we say they are all equal to $w+1$).

We define $\beta:=|\\{j\in\\{1\ldots,d\\};z_{j}=w\\}|$ and :

$z(j)=\begin{cases}w&\text{ for }j=1,\ldots,\beta\\\ w+1&\text{ for
}j=\beta+1,\ldots,d.\end{cases}$

  2. 2.

The partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$ consists of the
parts $z(j)$, $j=1,\ldots,d$. Further, the part $z(j)$ is followed by the part
$z(\langle j-\beta\rangle_{d})$ in $\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$.

###### Proof.

Let $A\in\mathcal{M}_{n}^{0}(q,qd-z)$ with associated partition
$\left(\begin{matrix}z_{1}&\ldots&z_{d}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$
and $B\in\mathcal{M}_{n}^{0}(qd-z,qd)$. Then $A=B^{d}$ if and only if the
parts $z_{j}$ correspond to the parts $z(j)$ in Theorem 5.1 which is true if
and only if both the conditions of the corollary are satisfied. ∎

######  Example 5.5.

Let $n=120$, then $\mathcal{K}_{n}(15,107)=\mathcal{K}_{n}(107,120)^{8}$,
where $q=15$, $s=107$, $d=8$ and $z=13$. Recall, by Definition 4.3, that any
$8$ non-negative integers that sum to $13$ result in a partition class for a
matrix in $\mathcal{M}_{n}^{0}(15,107)$. So, let
$A\in\mathcal{M}_{n}^{0}(15,107)$ and $\bf
z=\left(\begin{matrix}z_{1}&\ldots&z_{8}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$.

If $A=B^{8}$ for some $B\in\mathcal{M}_{n}^{0}(15,120)$, then the elements in
${\bf z^{\prime}}_{A}$ must be in the set $\\{w,w+1\\}$ for some
$w\in\\{1,2,\ldots,13\\}$. If ${\bf z^{\prime}}_{A}$ either contains three
different numbers or numbers that are more than one apart, then $A$ will not
be a power of any matrix $B\in\mathcal{M}_{n}^{0}(107,120)$. Thus, the
necessary condition from the first part of the corollary leaves us just one
choice for the vector ${\bf z}$ defined in Remark 5.2:

${\bf z}=\left(\begin{matrix}1&1&1&2&2&2&2&2\end{matrix}\right).$

The above ${\bf z}$ gives $\beta=3$ and $w=1$. The entries of ${\bf z}$ can be
permuted in several ways, but ${\bf z}$ gives us the unique partition class
for $\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$ as defined in Corollary 5.4.
Therefore $A=B^{8}$ for some $B\in\mathcal{M}_{n}^{0}(107,120)$ if and only if
${\bf z^{\prime}}\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$, where:

$\displaystyle{\bf z^{\prime}}$
$\displaystyle=\left(\begin{matrix}z(1)&z(6)&z(3)&z(8)&z(5)&z(2)&z(7)&z(4)\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}1&2&1&2&2&1&2&2\end{matrix}\right).$

###  5.2 Type II arc is a power of a Type II arc

Throughout this subsection we assume: $n=c\hat{d}q$, $z\in\\{1,\ldots,q-1\\}$,
$\gcd(cq,z)=1$. By Theorem 3.10 we have:

$\mathcal{K}_{n}(cq,c\hat{d}q-z)^{c}=\mathcal{K}_{n}(q,c\hat{d}q-z).$

Given the partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)$ for
$B\in\mathcal{M}_{n}^{0}(cq,c\hat{d}q-z)$ we want to determine the partition
class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$.

######  Theorem 5.6.

Let $B\in\mathcal{M}_{n}^{0}(cq,c\hat{d}q-z)$ and
$\left(\begin{matrix}\hat{z}_{1}&\ldots&\hat{z}_{\hat{d}}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)$.
For $i=1\ldots,\hat{d}$ and $j=1\ldots,c$, we define
$\beta_{i}=c-\langle\hat{z}_{i}\rangle_{c}$,
$w_{i}=\frac{\hat{z}_{i}-\langle\hat{z}_{i}\rangle_{c}}{c}$, and

$z(i,j)=\begin{cases}w_{i}&\text{ for }j=1,\ldots,\beta_{i}\\\ w_{i}+1&\text{
for }j=\beta_{i}+1,\ldots,c.\end{cases}$

The partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ is defined
as follows:

  * •

the parts of the partition are equal to $z(i,j)$, $i=1,\ldots,\hat{d}$,
$j=1\ldots,c$,

  * •

in the partition $z(i,j)$ is followed by $z(\langle
i+1\rangle_{\hat{d}},\langle j-\beta_{i}\rangle_{c})$.

###### Proof.

Let $B\in\mathcal{M}_{n}^{0}(\hat{q},\hat{s})$, where $\hat{q}=cq$,
$\hat{s}=c\hat{d}q-z$.

Digraph of $\bf B^{c}$. Given a directed graph $\widehat{\Gamma}$ that is
isomporhic to $\Gamma(B)$, we first find a directed graph
$\Gamma=\widehat{\Gamma}^{(c)}$ that is isomorphic to $\Gamma(B^{c})$. By
Theorem 4.2, $\Gamma(B)$ is isomorphic to

$\widehat{\Gamma}=\cup_{i=1}^{\hat{d}}\left(C(\hat{q}(i-1)\cdot{\bf e}+{\bf
a}(\hat{q}))+\\{(i\hat{q}-\hat{z}_{i},\langle
1+i\hat{q}\rangle_{n})\\}\right),$

where
$\left(\begin{matrix}\hat{z}_{1}&\ldots&\hat{z}_{\hat{d}}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)$.
Denoting the $\hat{q}$-cycles in $\widehat{\Gamma}$ by
$\widehat{C}_{i}:=C(\hat{q}(i-1)\cdot e+{\bf a}(\hat{q}))$,
$i=1,\ldots,\hat{d}$, and taking $k=\hat{q}$, $k_{1}=q$ in the first part of
Remark 4.7, we get $\widehat{C}_{i}^{(c)}=\cup_{j=1}^{c}C_{i,j},$ where for
$i=1,\ldots,\hat{d}$ and $j=1,\ldots,c$, we denote:

$\displaystyle C_{i,j}:=C\left((qc(i-1)+j)\cdot{\bf e}+c\cdot{\bf
a}_{0}(q-1)\right).$ (24)

Note that each $C_{i,j}$ is a $q$-cycle in $\widehat{\Gamma}^{(c)}$.

Next, we consider contribution of the edges
$\hat{e}_{i}=(i\hat{q}-\hat{z}_{i},\langle
1+i\hat{q}\rangle_{n}),i=1,\ldots,\hat{d}$, to $\widehat{\Gamma}^{(c)}$. Note
that the edge $\hat{e}_{i}$ connects $\widehat{C}_{i}$ to
$\widehat{C}_{\langle i+1\rangle_{\hat{d}}}$ in $\widehat{\Gamma}$, and
contributes the edges $\\{e_{i,t}:t=1,\ldots,c\\}$ to
$\widehat{\Gamma}^{(c)}$, where:

$\displaystyle e_{i,t}:=(\langle i\hat{q}-\hat{z}_{i}-(t-1)\rangle_{n},\langle
i\hat{q}+c-(t-1)\rangle_{n}).$ (25)

Let us denote $e_{i,t}:=(v_{O}(i,t),v_{I}(i,t))$ for future use. Note that in
$\widehat{\Gamma}^{(c)}$, the edges $e_{i,t}$ connect the $q$-cycles to form
an $s$-cycle. This $s$-cycle is the union of the edges $e_{i,t}$ and paths
that are part of $C_{i,j}$’s. These paths are discussed in the third section
of the proof where we talk about the partition parts. At this point we can
write down $\widehat{\Gamma}^{(c)}$ as:

$\widehat{\Gamma}^{(c)}=\cup_{i=1}^{\hat{d}}\left(\cup_{j=1}^{c}C_{ij}+\\{e_{i,t}:t=1,\ldots,c\\}\right).$

The weight $\alpha$ on the edges $\hat{e}_{i},i=1,\ldots,\hat{d}$, in
$\widehat{\Gamma}$ implies the weight $\alpha$ on the edges
$e_{i,t},i=1,\ldots,\hat{d},t=1,\ldots,c$ in $\widehat{\Gamma}^{(c)}$. Thus,
the weights on all the $q$-cycles, $C_{i,j},i=1,\ldots,\hat{d},j=1,\ldots,c$,
are equal to $1-\alpha$ in $\widehat{\Gamma}^{(c)}$.

Connecting the $q$-cycles and ordering the parts in the partition. To
determine $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ we take a closer look
at how the edges $e_{i,t}$ connect the cycles $C_{i,j}$. In particular, let
$z(i,j)$ be the number of vertices in $V(C_{i,j})$ that are not on the
$s$-cycle in $\widehat{\Gamma}^{(c)}$. To determine the ordering of $z(i,j)$
in $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ we fix $i$ and $j$ and
determine how the $q$-cycles follow each other to form the $s$-cycle in
$\widehat{\Gamma}^{(c)}$.

For each pair $i,j$, $i\in\\{1,\ldots,\hat{d}\\}$ and $j\in\\{1,\ldots,c\\}$,
there exists precisely one $t^{\prime}\in\\{1,\ldots,c\\}$ so that
$v_{I}(i-1,t^{\prime})\in V(C_{i,j})$. We say that $e_{i-1,t^{\prime}}$ is _an
incoming edge_ for $C_{i,j}$. From
$v_{I}(i-1,t^{\prime})=\langle(i-1)\hat{q}+c-t^{\prime}+1)\rangle_{n}$ and
$V(C_{i,j})=\\{(qc(i-1)+\ell c+j),\ell=0,\ldots,q-1\\}$, we deduce that
$j+t^{\prime}$ is congruent to $1$ modulo $c$. In short, $e_{i-1,\langle
1-j\rangle_{c}}$ is the incoming edge for $C_{i,j}$. Similarly, there exists a
unique $t\in\\{1,\ldots,c\\}$ such that $v_{O}(i,t)\in V(C_{i,j})$ and we say
that $e_{i,t}$ is an _outgoing edge_ for $C_{i,j}$. This implies that $j+t$ is
congruent to $1-\hat{z}_{i}$ modulo $c$. This relation and the fact that
$t\in\\{1,\ldots,c\\}$ uniquely define $t$ to be:

$\displaystyle t:=\begin{cases}\beta_{i}+1-j&\text{ for
}j=1,\ldots,\beta_{i}\\\ \beta_{i}+1+c-j&\text{ for
}j=\beta_{i}+1,\ldots,c,\end{cases}$ (26)

where $\beta_{i}:=c-\langle\hat{z}_{i}\rangle_{c}$. Finally, to determine how
the cycles $C_{i,j}$ are ordered to form the $s$-cycle in
$\widehat{\Gamma}^{(c)}$, we use equation (25) and equation (26) to get:

$v_{I}(i,t)=\begin{cases}i\hat{q}+c+j-\beta_{i}&\text{ for
}j=1,\ldots,\beta_{i}\\\ i\hat{q}+j-\beta_{i}&\text{ for
}j=\beta_{i}+1,\ldots,c.\end{cases}$

This implies $v_{I}(i,t)\in C_{\langle i+1\rangle_{\hat{d}},\langle
j-\beta_{i}\rangle_{c}}$. Consequently, $z(i,j)$ is followed by $z(\langle
i+1\rangle_{\hat{d}},\langle j-\beta_{i}\rangle_{c})$ in
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$.

Parts of the partition. To determine the parts that appear in
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$, we want to determine how many
vertices from each $C_{i,j}$ cycle are (are not) contained on the $s$-cycle in
$\widehat{\Gamma}^{(c)}$. Equivalently, we want to know the number of vertices
on the path that is the intersection between $C_{i,j}$ and the $s$-cycle in
$\widehat{\Gamma}^{(c)}$. Let us denote this number by $k(i,j)$. From the
above discussion, we know that $v_{I}(i-1,\langle 1-j\rangle_{c})$ is the
first and $v_{O}(i,t)$ is the last vertex on this path for $t=\langle
1-j-\hat{z}_{i}\rangle_{c}$. Using equation (25) and equation (26), we get:

$\displaystyle v_{I}(i-1,\langle 1-j\rangle_{c}$
$\displaystyle=\hat{q}(i-1)+j,$ $\displaystyle v_{O}(i,t)$
$\displaystyle=\begin{cases}i\hat{q}-\hat{z}_{i}-\beta_{i}+j,&\text{ for
}j=1,\ldots,\beta_{i}\\\ i\hat{q}-\hat{z}_{i}-c-\beta_{i}+j&\text{ for
}j=\beta_{i}+1,\ldots,c.\end{cases}$

From here, we can write:

$\displaystyle v_{O}(i,t)$
$\displaystyle=\begin{cases}(i-1)\hat{q}+(q-w_{i}-1)c+j,&\text{ for
}j=1,\ldots,\beta_{i}\\\ (i-1)\hat{q}+(q-w_{i}-2)c+j&\text{ for
}j=\beta_{i}+1,\ldots,c,\end{cases}$

where $\beta_{i}=c-\langle\hat{z}_{i}\rangle_{c}$, and
$w_{i}=\frac{\hat{z}_{i}-\langle\hat{z}_{i}\rangle_{c}}{c}$. Recalling that
the vertices of $C_{i,j}$ are consecutively numbered by $(qc(i-1)+\ell c+j)$,
$\ell=0,\ldots,q-1$, we conclude that:

$k(i,j)=\begin{cases}q-w_{i},&\text{ for }j=1,\ldots,\beta_{i}\\\
q-w_{i}-1,&\text{ for }j=\beta_{i}+1,\ldots,c,\end{cases}$

or equivalently, $z(i,j):=q-k(i,j)$ is the number of vertices from $C_{i,j}$
that are not on the $s$-cycle. With this, we have determined the numbers that
appear in the partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$.

∎

######  Remark 5.7.

Given $\hat{\mathbf{z}}\in\mathcal{P}(B)$ we can define a matrix $Z^{\prime}$
that satisfies $\operatorname{vec}(Z^{\prime})^{T}\in\leavevmode\nobreak\
\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ as follows. From
$\hat{\mathbf{z}}$ we define the parts $z(i,j)$ as in the statement of Theorem
5.6, and consider the matrix:

$Z:=\left(\begin{array}[]{cccc}z(1,1)&z(1,2)&\ldots&z(1,c)\\\
\vdots&\vdots&\ddots&\vdots\\\
z(\hat{d},1)&z(\hat{d},2)&\ldots&z(\hat{d},c)\\\ \end{array}\right).$

The elements of $Z$ are the same as the parts of the partitions in
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ (with multiplicities). Next, we
determine their ordering in the partition. Using the fact that $z(i,j)$ is
followed by $z(\langle i+1\rangle_{\hat{d}},\langle j-\beta_{i}\rangle_{c})$,
we define the $j$-th column, $z^{\prime}_{\star,j}$, $j=1,\ldots,c$, of the
matrix $Z^{\prime}$ to be:

$z^{\prime}_{\star,j}:=\left(\begin{array}[]{c}z(1,\langle
1-(j-1)\beta\rangle_{c})\\\ \vdots\\\ z(i,\langle
1-(j-1)\beta-\sum_{k=1}^{i-1}\beta_{k}\rangle_{c})\\\ \vdots\\\
z(\hat{d},\langle 1-(j-1)\beta-\sum_{k=1}^{\hat{d}-1}\beta_{k}\rangle_{c})\\\
\end{array}\right).$

The partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ is equal to
$\mathscr{T}(\bf z)$, where ${\bf z}=\operatorname{vec}(Z^{\prime})^{T}$. Note
that the unordered multiset of elements in the $j$-th row of $Z$ is equal to
the unordered multiset of elements in the $j$-th row of $Z^{\prime}$ but the
elements appear in matrices $Z$ and $Z^{\prime}$ in different orders.

######  Example 5.8.

Let $n=120$, then $\mathcal{K}_{n}(6,115)=\mathcal{K}_{n}(24,115)^{4}$, where
$q=6$, $c=4$, $qc=\hat{q}=24$, $\hat{s}=115$, $\hat{d}=5$, $z=5$ and
$z=\hat{z}_{1}+\hat{z}_{2}+\hat{z}_{3}+\hat{z}_{4}+\hat{z}_{5}$.

Let $B\in\mathcal{M}_{n}^{0}(24,115)$. In this example, we consider a few
possibilities for partitions
${\bf\hat{z}}\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)$. In each case, we
illustrate parts of the proof and write down matrices $Z$ and $Z^{\prime}$
defined in Remark 5.7.

  1. 1.

$\left(\begin{matrix}\hat{z}_{1}&\hat{z}_{2}&\hat{z}_{3}&\hat{z}_{4}&\hat{z}_{5}\end{matrix}\right)=\left(\begin{matrix}5&0&0&0&0\end{matrix}\right).$

Digraph of $\bf B^{4}$. $\widehat{\Gamma}$ consists of $5$ cycles of order
$24$, $C(24(i-1)\cdot{\bf e}+{\bf a}(24))$, $i=1,\ldots,5$, and the edge set,
$\\{(19,25),(48,49),(72,73),(96,97),(120,1)\\}$ that connect the $24$-cycles
to make the $115$-cycle.

$\widehat{\Gamma}^{(4)}$ consists of $20$ cycles of order $6$,
$C\left((24(i-1)+j)\cdot{\bf e}+c\cdot{\bf a}_{0}(6)\right)$ for
$i=1,\ldots,5$, $j=1,\ldots,4$, and the edge set:

$(\langle 24i-\hat{z}_{i}-(t-1)\rangle_{n},\langle 24i+4-(t-1)\rangle_{n})$

for $i=1,\ldots,5$, $t=1,\ldots,4$, that connect the $6$-cycles to form a
cycle of order $115$. Note that each of these connecting edges has the weight
$\alpha$ in $\widehat{\Gamma}^{(4)}$ if the connecting edges in
$\widehat{\Gamma}$ have the weight $\alpha$.

Parts of the Partition. From $\hat{z}_{1}=5$ we get $\beta_{1}=3$ and
$w_{1}=1$. Similarly, $\hat{z}_{2}=\hat{z}_{3}=\hat{z}_{4}=\hat{z}_{5}=0$ give
$\beta_{2}=\beta_{3}=\beta_{4}=\beta_{5}=0$ and $w_{2}=w_{3}=w_{4}=w_{5}=-1$.

Thus, the matrix $Z$ defined in Remark 5.7 is equal to:

$Z=\left(\begin{array}[]{cccc}1&1&1&2\\\ 0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\
0&0&0&0\end{array}\right).$

At this point, we know that the elements in
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ will have three parts equal to
$1$, one part equal to $2$, and all other parts equal to $0$. Since all the
nonzero parts appear in the first row, we also know that every nonzero part
will be followed by precisely four zeros. As this observation already uniquely
defines the partition class, we move on to the next case.

  2. 2.

$\left(\begin{matrix}\hat{z}_{1}&\hat{z}_{2}&\hat{z}_{3}&\hat{z}_{4}&\hat{z}_{5}\end{matrix}\right)=\left(\begin{matrix}3&0&2&0&0\end{matrix}\right).$

Parts of the Partition. From $\hat{z}_{1}=3$ we get $\beta_{1}=1$, $w_{1}=0$.
Next, $\hat{z}_{3}=2$ gives $\beta_{3}=2$, $w_{3}=0$. Finally,
$\hat{z}_{2}=\hat{z}_{4}=\hat{z}_{5}=0$ gives
$\beta_{2}=\beta_{4}=\beta_{5}=0$ and $w_{2}=w_{4}=w_{5}=-1$. This implies:

$Z=\left(\begin{array}[]{cccc}0&1&1&1\\\ 0&0&0&0\\\ 0&0&1&1\\\ 0&0&0&0\\\
0&0&0&0\end{array}\right).$

The elements of $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ have $5$ parts
equal to $1$ and all other parts equal to $0$.

Ordering. This time the matrix $Z$ does not determine
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$, and we also need:

$Z^{\prime}=\left(\begin{array}[]{cccc}z(1,1)&z(1,2)&z(1,3)&z(1,4)\\\
z(2,4)&z(2,1)&z(2,2)&z(2,3)\\\ z(3,4)&z(3,1)&z(3,2)&z(3,3)\\\
z(4,2)&z(4,3)&z(4,4)&z(4,1)\\\
z(5,2)&z(5,3)&z(5,4)&z(5,1)\end{array}\right)=\left(\begin{array}[]{cccc}0&1&1&1\\\
0&0&0&0\\\ 1&0&0&1\\\ 0&0&0&0\\\ 0&0&0&0\end{array}\right).$

Thus, the partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{4})$ is
given by $\mathscr{T}(\operatorname{vec}(Z^{\prime})^{T})$.

  3. 3.

Taking
$\left(\begin{matrix}\hat{z}_{1}&\hat{z}_{2}&\hat{z}_{3}&\hat{z}_{4}&\hat{z}_{5}\end{matrix}\right)=\left(\begin{matrix}2&0&2&0&1\end{matrix}\right)$
we get:

$Z=\left(\begin{array}[]{cccc}0&0&1&1\\\ 0&0&0&0\\\ 0&0&1&1\\\ 0&0&0&0\\\
0&0&0&1\end{array}\right)\text{ and
}Z^{\prime}=\left(\begin{array}[]{cccc}0&0&1&1\\\ 0&0&0&0\\\ 1&1&0&0\\\
0&0&0&0\\\ 0&0&0&1\end{array}\right),$

and the partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{c})$ is
given by ${\bf z}=\mathscr{T}(\operatorname{vec}(Z^{\prime})^{T})$.

######  Corollary 5.9.

Let $A\in\mathcal{M}_{n}^{0}(q,c\hat{d}q-z)$ and
$\left(\begin{matrix}z_{1}&\ldots
z_{c\hat{d}}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$.
Then $A=B^{c}$ for some $B\in\mathcal{M}_{n}^{0}(cq,c\hat{d}q-z)$ if and only
if:

  1. 1.

For every $i\in\\{1,\ldots,\hat{d}\\}$ there exists $w_{i}$ so that
$z_{t\hat{d}+i}\in\\{w_{i},w_{i}+1\\}$ for $t=0,\ldots,c-1$. (If for some $i$
all $z_{t\hat{d}+i}$ are equal, then we say that they are equal to $w_{i}+1$.)

For $i=1\ldots,\hat{d}$, we define,
$\beta_{i}:=|\\{t\in\\{0\ldots,c-1\\};z_{t\hat{d}+i}=w_{i}\\}|$, and

$z(i,j):=\begin{cases}w_{i}&\text{ for }j=1,\ldots,\beta_{i}\\\ w_{i}+1&\text{
for }j=\beta_{i}+1,\ldots,c,\end{cases}$

where $i=1,\ldots,\hat{d},j=1,\ldots,c.$

  2. 2.

The partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$ consists of the
parts $z(i,j)$, $i=1,\ldots,\hat{d}$, $j=1\ldots,c$. Further, in the partition
$z(i,j)$ is followed by $z(\langle i+1\rangle_{\hat{d}},\langle
j-\beta_{i}\rangle_{c})$.

If the conditions above are satisfied, then $A=B^{c}$ for
$B\in\mathcal{M}_{n}^{0}(cq,c\hat{d}q-z)$ with
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)=\mathscr{T}(\left(\begin{matrix}\hat{z}_{1}&\ldots&\hat{z}_{\hat{d}}\end{matrix}\right)),$
where $\hat{z}_{i}:=c(w_{i}+1)-\beta_{i}$, for $i=1,\ldots,\hat{d}$.

###### Proof.

Let $A\in\mathcal{M}_{n}^{0}(q,c\hat{d}q-z)$ and
$\left(\begin{matrix}z_{1}&\ldots&z_{d}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$.
By Theorem 5.6, $A=B^{c}$ for some $B\in\mathcal{M}_{n}^{0}(cq,c\hat{d}q-z)$
if and only if the items 1. and 2. in Corollary 5.9 hold. ∎

######  Example 5.10.

Let $n=120$, $q=6$ and $s=115$. Then, $d=20$, $z=5$ and $n=qd$. By Definition
4.3, any partition class containing $20$ non-negative integers that sum to $5$
is a partition class for some matrix in $\mathcal{M}_{n}^{0}(6,115)$.

Let $A\in\mathcal{M}_{n}^{0}(6,115)$ and ${\bf
z}=\left(\begin{matrix}z_{1}&\ldots&z_{20}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$.
Let $Z^{\prime}_{A}$ be a $\hat{d}\times c$ matrix satisfying
$\operatorname{vec}(Z^{\prime}_{A})^{T}={\bf z}$:

$Z^{\prime}_{A}=\left(\begin{array}[]{cccc}z_{1}&z_{6}&z_{11}&z_{16}\\\
z_{2}&z_{7}&z_{12}&z_{17}\\\ z_{3}&z_{8}&z_{13}&z_{18}\\\
z_{4}&z_{9}&z_{14}&z_{19}\\\ z_{5}&z_{10}&z_{15}&z_{20}\end{array}\right).$

We want to determine when $A=B^{c}$ is a power of some matrix
$B\in\mathcal{M}_{n}^{0}(24,115)$.

From the first part of the corollary, we know that each row in
$Z^{\prime}_{A}$ must have elements from the set $\\{w_{i},w_{i}+1\\}$. That
is, if any row of $Z^{\prime}_{A}$ either contains three different numbers or
numbers that are more than one apart, we know that $A$ is not a power of any
matrix $B\in\mathcal{M}_{n}^{0}(24,115)$. The necessary condition to have
entries at most one apart in each row of $Z^{\prime}_{A}$, and the fact that
all elements of $Z^{\prime}_{A}$ sum up to $5$, imply that the maximal
possible entry in any one row of $Z^{\prime}_{A}$ is $2$, and if $2$ is an
element of $Z^{\prime}_{A}$, then the row that contains it is the only nonzero
row in the matrix. We consider two cases:

  1. 1.

$2$ is an element of $Z^{\prime}_{A}$. If $2$ is an entry in a row then the
other entries in that row have to be $1$. Without loss of generality, we can
put the entries $2$ and $1$ in the first row of $Z^{\prime}_{A}$. This gives
us

$Z=\left(\begin{array}[]{cccc}1&1&1&2\\\ 0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\
0&0&0&0\end{array}\right),$

and a unique partition class $\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$.
Referring back to Example 5.8, we see that
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$ is equivalent to
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(B^{4})$ for
$B\in\mathcal{M}_{n}^{0}(24,115)$ with associated partition class
$\mathscr{T}({\bf\hat{z}})$, where $\hat{\bf
z}=\left(\begin{matrix}5&0&0&0&0\end{matrix}\right)$. In order words,
$A=B^{4}$ for some matrix $B\in\mathcal{M}_{n}^{0}(24,115)$ with
$\left(\begin{matrix}5&0&0&0&0\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)$.

  2. 2.

All elements of $Z^{\prime}_{A}$ are either $0$ or $1$. Under this constraint
the first item in Corollary 5.9 automatically holds, and we have several
options for the matrix $Z$ as defined in Remark 5.7. In other words, we can
choose the row sums of $Z$ arbitrarily, as long as the sum of all the entries
in $Z$ is equal to $5$. Let us look at a few specific examples:

     * •

Letting

$Z=\left(\begin{array}[]{cccc}z(1,1)&z(1,2)&z(1,3)&z(1,4)\\\
z(2,1)&z(2,2)&z(2,3)&z(2,4)\\\ z(3,1)&z(3,2)&z(3,3)&z(3,4)\\\
z(4,1)&z(4,2)&z(4,3)&z(4,4)\\\
z(5,1)&z(5,2)&z(5,3)&z(5,4)\end{array}\right)=\left(\begin{array}[]{cccc}1&1&1&1\\\
0&0&0&1\\\ 0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\end{array}\right),$

we get $w_{1}=w_{2}=0$, $w_{3}=w_{4}=w_{5}=-1$ and $\beta_{1}=0$,
$\beta_{2}=3$, $\beta_{3}=\beta_{4}=\beta_{5}=0$.

In this case $Z^{\prime}=Z$, and any matrix $A\in\mathcal{M}_{n}^{0}(6,115)$
with
$\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)=\mathscr{T}(\operatorname{vec}({Z^{\prime}})^{T})$
is a fourth power of some a matrix $B\in\mathcal{M}_{n}^{0}(24,115)$.

     * •

For

$Z=\left(\begin{array}[]{cccc}0&0&1&1\\\ 0&0&1&1\\\ 0&0&0&0\\\ 0&0&0&1\\\
0&0&0&0\end{array}\right),$

we get $w_{1}=w_{2}=0$, $\beta_{1}=\beta_{2}=2$, $w_{3}=w_{5}=-1$,
$\beta_{3}=\beta_{5}=0$, $w_{4}=0$ and $\beta_{4}=3$. We can cyclically
permute the rows of $Z$ in many ways, but this $Z$ will give us only one
partition class as in Corollary 5.9.

Specifically, $A=B^{4}$ for some $B\in\mathcal{M}_{n}^{0}(24,115)$ if and only
if $\operatorname{vec}(Z^{\prime})^{T}\in\leavevmode\nobreak\
\mathscr{P}_{\text{\emph{\tiny{II}}}}(A)$, where:

$Z^{\prime}=\left(\begin{array}[]{cccc}z(1,1)&z(1,2)&z(1,3)&z(1,4)\\\
z(2,3)&z(2,4)&z(2,1)&z(2,2)\\\ z(3,1)&z(3,2)&z(3,3)&z(3,4)\\\
z(4,1)&z(4,2)&z(4,3)&z(4,4)\\\
z(5,2)&z(5,3)&z(5,4)&z(5,1)\end{array}\right)=\left(\begin{array}[]{cccc}0&0&1&1\\\
1&1&0&0\\\ 0&0&0&0\\\ 0&0&0&1\\\ 0&0&0&0\end{array}\right).$

In that case $\mathscr{P}_{\text{\emph{\tiny{II}}}}(B)=\mathscr{T}(\hat{\bf
z})$, where $\hat{\bf z}=\left(\begin{matrix}2&2&0&1&0\end{matrix}\right)$.

###  5.3 Type III arc is a power of a Type III arc

Throughout this subsection we assume $n=qc\hat{d}+y$, $d=c\hat{d}$,
$\gcd(qc,y)=1$. By Theorem 3.10:

$\mathcal{K}_{n}(q,qc\hat{d}+y)=\mathcal{K}_{n}(qc,qc\hat{d}+y)^{c}.$

The theorem below determines the partition class of $B^{c}$ for
$B\in\mathcal{M}_{n}^{0}(qc,qc\hat{d}+y)$.

######  Theorem 5.11.

Let $B\in\mathcal{M}_{n}^{0}(qc,qc\hat{d}+y)$ and
$\left(\begin{matrix}\hat{y}_{1}&\ldots&\hat{y}_{\hat{d}}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)$.
For $i=1\ldots,\hat{d}$, let $u_{i}$, $\beta_{i}$, $\eta_{i}$ and $\gamma_{i}$
be defined by:

$\hat{y}_{i}=u_{i}c+\beta_{i}\text{ and
}\sum_{k=1}^{i}\beta_{k}=\eta_{i}c+\gamma_{i}$

where $\beta_{i},\gamma_{i}\in\\{0,\ldots,c-1\\}$. For $i=1,\ldots,\hat{d}$
and $j=1,\ldots,c$, we define:

$\displaystyle
y(i,j)=\begin{cases}u_{i}+1,&j=\langle\gamma_{i-1}+1\rangle_{c},\ldots,\langle\gamma_{i-1}+\beta_{i}\rangle_{c}\\\
u_{i},&j=\langle\gamma_{i-1}+\beta_{i}+1\rangle_{c},\ldots,\langle\gamma_{i-1}+c\rangle_{c}.\end{cases}$
(27)

The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{c})$ is defined
as follows:

  * •

the parts of the partition are equal to $y(i,j)$, $i=1,\ldots,\hat{d}$,
$j=1\ldots,c$,

  * •

in the partition $y(i,j)$ is followed by $y(i+1,j)$ for
$i=1,\ldots,\hat{d}-1$. Further, $y(\hat{d},j)$ is followed by $y(1,\langle
j-y\rangle_{c})$.

###### Proof.

Let $B\in\mathcal{M}_{n}^{0}(\hat{q},\hat{s})$, $\hat{q}=qc$,
$\hat{s}=qc\hat{d}+y$, and
$\left(\begin{matrix}\hat{y}_{1}&\ldots&\hat{y}_{\hat{d}}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)$.

Digraph of $B^{c}$.  Let $\widehat{\Gamma}$ be a digraph isomorphic to
$\Gamma(B)$. In this first step, we will find a directed graph
$\widehat{\Gamma}^{(c)}$ that is isomorphic to $\Gamma(B^{c})$. By Theorem
4.4, $\Gamma(B)$ is isomorphic to:

$\widehat{\Gamma}=C({\bf a}(n))+\\{\hat{e}_{1},\ldots,\hat{e}_{\hat{d}}\\},$

where
$\hat{e}_{i}:=\\{(i\hat{q}+\sum_{k=1}^{i}\hat{y}_{k},1+(i-1)\hat{q}+\sum_{k=1}^{i}\hat{y}_{k})\\}$.

Since $\gcd(n,c)=1$, $C({\bf a}(n))^{(c)}$ is an $n$-cycle by Remark 4.7:

$\displaystyle C({\bf a}(n))^{(c)}=C(\langle c\cdot{\bf a}(n)\rangle_{n}).$
(28)

In addition, each edge $\hat{e}_{i}$ contributes the following $c$ edges to
$\widehat{\Gamma}^{(c)}$:

$\displaystyle e_{i,t}:=(\langle
1+i\hat{q}+\sum_{k=1}^{i}\hat{y}_{k}-t\rangle_{n},\langle
1+(i-1)\hat{q}+\sum_{k=1}^{i}\hat{y}_{k}+c-t\rangle_{n}),\,t=1,\ldots,c.$ (29)

We denote $e_{i,t}:=(v_{O}(i,t),v_{I}(i,t))$ for future use. We have:

$\widehat{\Gamma}^{(c)}=C(\langle c\cdot{\bf
a}(n)\rangle_{n})+\\{e_{i,t}:i=1,\ldots,\hat{d},t=1,\ldots c\\}.$

Note that $\widehat{\Gamma}^{(c)}$ consists of an $n$-cycle $C(\langle
c\cdot{\bf a}(n)\rangle_{n})$ together with $\hat{d}c$ $q$-cycles, where each
$q$-cycle is formed by an edge $e_{i,t}$ connecting two vertices of the
$n$-cycle. Also, the weight $1-\alpha$ on the edges
$\hat{e}_{i},i=1,\ldots,\hat{d}$, in $\widehat{\Gamma}$ gives the weight
$1-\alpha$ to the edges $e_{i,t},i=1,\ldots,\hat{d},t=1,\ldots,c$, in
$\widehat{\Gamma}^{(c)}$. Thus, the weights on all the $q$-cycles,
$C_{i,j},i=1,\ldots,\hat{d},j=1,\ldots,c$, are equal to $1-\alpha$ in in
$\widehat{\Gamma}^{(c)}$.

Congruence modulo $c$. To determine the partition class of $B^{c}$, we will
study separately each part of the graph $\widehat{\Gamma}^{(c)}$ that (for a
fixed $j$) involves vertices congruent to $j$ modulo $c$. Let
$\Pi_{j}:=P(j+c{\bf a}_{0}(h(j)))$, $j=1,\ldots,c$, where

$h(j):=\begin{cases}\lfloor\frac{n}{c}\rfloor+1&\text{ for }j=1,\ldots,\langle
n\rangle_{c}\\\ \lfloor\frac{n}{c}\rfloor&\text{ for }j=\langle
n\rangle_{c}+1,\ldots,c,\end{cases}$

or equivalently:

$h(j)=1+\hat{d}q+\left\lfloor\frac{y-j}{c}\right\rfloor.$

With this notation, we have:

$C({\bf
a}(n))^{(c)}=\cup_{j=1}^{c}\left(\Pi_{j}+\\{(j+y+(q\hat{d}-1)c,j)\\}\right).$

From $j+y+(q\hat{d}-1)c\in V(\Pi_{\langle j+y\rangle_{c}})$ and $j\in
V(\Pi_{j})$, we deduce that $\Pi_{\langle j+y\rangle_{c}}$ is connected to
$\Pi_{j}$ with the edge $(j+y+(q\hat{d}-1)c,j)$. In particular, $\Pi_{j}$ is
followed by $\Pi_{\langle j-y\rangle_{c}}$ in $\widehat{\Gamma}^{(c)}$.

From equation (29) we notice that $\langle v_{O}(i,t)\rangle_{c}=\langle
v_{I}(i,t)\rangle_{c}$. This implies that for any pair
$i\in\\{1,\ldots,\hat{d}\\}$ and $t\in\\{1,\ldots,c\\}$, there exists a unique
$j\in\\{1,\ldots,c\\}$ such that the edge $e_{i,t}$ connects two vertices in
$\Pi_{j}$. Moreover, the vertices of $e_{i,t}$ belong to $\Pi_{j}$ precisely
when $t$ is congruent to $(1-j+\sum_{k=1}^{i}\hat{y}_{k})\mod c$. We define
$e^{\prime}_{i,j}:=e_{i,\langle 1-j+\sum_{k=1}^{i}\hat{y}_{k}\rangle_{c}}$
with $e^{\prime}_{i,j}=(v^{\prime}_{O}(i,j),v^{\prime}_{I}(i,j))$, and note
that

$\\{e_{i,t}:i=1,\ldots,\hat{d},t=1,\ldots
c\\}=\\{e_{i,j}^{\prime}:i=1,\ldots,\hat{d},j=1,\ldots c\\}.$

From now on we will work with edges $e_{i,j}^{\prime}$. We write:
$v^{\prime}_{O}(i,j)=j+k(i,j)c$ and $v^{\prime}_{I}(i,j)=j+l(i,j)c$, where:

$\displaystyle k(i,j)$
$\displaystyle=iq+\left\lfloor\frac{\sum_{k=1}^{i}\hat{y}_{k}-j}{c}\right\rfloor,$
(30)

$\displaystyle l(i,j)$
$\displaystyle=1+(i-1)q+\left\lfloor\frac{\sum_{k=1}^{i}\hat{y}_{k}-j}{c}\right\rfloor.$
(31)

Parts of the partition.  We fix $j$, and consider those $q$-cycles in
$\widehat{\Gamma}^{(c)}$ whose vertices are contained in
$V(\Pi_{j})=\\{j,j+c,\ldots,j+(h(j)-1)c\\}$. From above we already know that
those are precisely the $q$-cycles in $\widehat{\Gamma}^{(c)}$ that contain an
edge $e_{i,j}^{\prime}$ for some $i=1,\ldots,\hat{d}$.

The first vertex in $\Pi_{j}$ is $j+0c$, followed by vertices $j+c$, $j+2\cdot
c$,…, $j+(h(j)-1)\cdot c$, in this order. From $k(1,j)<k(2,j)<\ldots<k(c,j)$
we deduce that the first $q$-cycle on $V(\Pi_{j})$ will contain
$e_{1,j}^{\prime}$, followed by the $q$-cycle containing $e_{2,j}^{\prime}$,
etc. The last $q$-cycle in $\Pi_{j}$, made by the edge
$e^{\prime}_{\hat{d},j}$, contains the vertex
$v^{\prime}_{O}(\hat{d},j)=j+k(\hat{d},j)c$. Since $k(\hat{d},j)=h(j)-1$, we
conclude that $v^{\prime}_{O}(\hat{d},j)$ is the last vertex in $\Pi_{j}$. In
other words, there are no vertices in $\Pi_{j}$ after the last $q$-cycle.

We define $y(1,j):=l(1,j)-0$ to be the number of vertices that lie before
$v^{\prime}_{I}(1,j)$ in $\Pi_{j}$. Next, we focus on the path between two
neighbouring $q$-cycles inside our fixed $\Pi_{j}$. More specifically, for
$i=2,\ldots,\hat{d}$, we want to determine the number of vertices that are not
contained in any $q$-cycle and are on the path connecting the $q-$cycles made
by the edges $e^{\prime}_{i-1,j}$ and $e^{\prime}_{i,j}$. The first vertex on
this path is $v^{\prime}_{O}(i-1,j)=j+k(i-1,j)c$ and the last vertex is
$v^{\prime}_{I}(i,j)=j+l(i,j)c$. The number of vertices on $\Pi_{j}$
(strictly) between $v^{\prime}_{O}(i-1,j)$ and $v^{\prime}_{I}(i,j)$ is equal
to: $y(i,j):=l(i,j)-k(i-1,j)-1.$

In summary, the vector ${\bf
y}(j):=\left(\begin{matrix}y(1,j)&\ldots&y(\hat{d},j)\end{matrix}\right)$
contains the contribution to partitions in the partition class of
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{c})$ coming from the part of the
graph involving $V(\Pi_{j})$.

To determine $y(i,j)$ we write $\hat{y}_{i}=u_{i}c+\beta_{i}$, where
$\beta_{i}\in\\{0,\ldots,c-1\\}$, and
$\sum_{k=1}^{i}\beta_{k}=\eta_{i}c+\gamma_{i}$, where
$\gamma_{i}\in\\{0,\ldots,c-1\\}$. Inserting $i=1$ in (31) we now get:

$\displaystyle y(1,j)$
$\displaystyle=1+\left\lfloor\frac{\hat{y}_{1}-j}{c}\right\rfloor=\begin{cases}u_{1}+1,&\text{
for }j\in\\{1,\ldots,\beta_{1}\\}\\\ u_{1}&\text{ for
}j\in\\{\beta_{1}+1,\ldots,c\\}.\end{cases}$

To determine $y(i,j)$ from (30) and (31) we compute:

$\displaystyle y(i,j)$ $\displaystyle=l(i,j)-k(i-1,j)-1$
$\displaystyle=u_{i}+\left\lfloor\frac{\sum_{k=1}^{i}\beta_{k}-j}{c}\right\rfloor-\left\lfloor\frac{\sum_{k=1}^{i-1}\beta_{k}-j}{c}\right\rfloor$
$\displaystyle=u_{i}+\left\lfloor\frac{\gamma_{i-1}+\beta_{i}-j}{c}\right\rfloor-\left\lfloor\frac{\gamma_{i-1}-j}{c}\right\rfloor.$

We distinguish between two cases: $\gamma_{i-1}+\beta_{i}<c$, and
$\gamma_{i-1}+\beta_{i}\geq c$. If $\gamma_{i-1}+\beta_{i}<c$, then
$\eta_{i}=\eta_{i-1}$, $\gamma_{i}=\gamma_{i-1}+\beta_{i}$, and

$y(i,j)=\begin{cases}u_{i},&j=1,\ldots,\gamma_{i-1}\\\
u_{i}+1,&j=\gamma_{i-1}+1,\ldots,\gamma_{i-1}+\beta_{i}\\\
u_{i},&j=\gamma_{i-1}+\beta_{i}+1,\ldots,c.\\\ \end{cases}$

For $\gamma_{i-1}+\beta_{i}\geq c$ we get $\eta_{i}=\eta_{i-1}+1$,
$\gamma_{i}=\gamma_{i-1}+\beta_{i}-c$, and

$y(i,j)=\begin{cases}u_{i}+1,&j=1,\ldots,\gamma_{i-1}+\beta_{i}-c\\\
u_{i},&j=\gamma_{i-1}+\beta_{i}-c+1,\ldots,\gamma_{i-1}\\\
u_{i}+1,&j=\gamma_{i-1}+1,\ldots,c.\\\ \end{cases}$

Both cases can be written in one expression as given by (27).

Final ordering. So far we have proved that ${\bf
y}\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{c})$ consists of ${\bf y}(j)$,
$j=1,\ldots,c$, in some order. Since we also know that $\Pi_{j}$ is followed
by $\Pi_{\langle j-y\rangle_{c}}$ in $\widehat{\Gamma}^{(c)}$, we conclude
that ${\bf y}(j)$ is followed by ${\bf y}({\langle j-y\rangle_{c}})$ in ${\bf
y}\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{c})$. With this final
observation, the partition class is uniquely defined. ∎

######  Remark 5.12.

Given $\hat{\mathbf{y}}\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)$ we can
define a matrix $Y^{\prime}$ that satisfies
$\operatorname{vec}(Y^{\prime})^{T}\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{c})$
as follows. From $\hat{\mathbf{y}}$ we define $y(i,j)$ as in the statement of
Theorem 5.11, and form the matrix:

$Y:=\left(\begin{array}[]{cccc}y(1,1)&y(1,2)&\ldots&y(1,c)\\\
\vdots&\vdots&\ddots&\vdots\\\
y(\hat{d},1)&y(\hat{d},2)&\ldots&y(\hat{d},c)\\\ \end{array}\right).$

The matrix $Y^{\prime}$ is obtained from $Y$ by a permutation of columns such
that the $j$-th column of $Y^{\prime}$ is equal to ${\bf y}(\langle
1-(j-1)y\rangle_{c})$, which is the $\langle 1-(j-1)y\rangle_{c}$-th column of
$Y$. The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{c})$ is
then equal to $\mathscr{T}(\bf y)$, where ${\bf
y}=\operatorname{vec}(Y^{\prime})^{T}$.

Let $n=337$ and consider the arc
$\mathcal{K}_{n}(q,s)=\mathcal{K}_{n}(27,337)$. Using Theorem 3.10 we have:

$\displaystyle\mathcal{K}_{n}(27,337)=\mathcal{K}_{n}(337,324)^{12}=\mathcal{K}_{n}(81,337)^{3}=\mathcal{K}_{n}(108,337)^{4}.$
(32)

We will consider the case
$\mathcal{K}_{n}(27,337)=\mathcal{K}_{n}(337,324)^{12}$ after Theorem 5.16. In
the example below we illustrate the proof of Theorem 5.11 for
$\mathcal{K}_{n}(27,337)=\mathcal{K}_{n}(81,337)^{3}$.

######  Example 5.13.

Let $n=337$, then $\mathcal{K}_{n}(27,337)=\mathcal{K}_{n}(81,337)^{3}$, where
$q=27$, $d=12$, $s=337$, $c=3$, $\hat{q}=81$, $\hat{d}=4$, $y=13$ and
$y=\hat{y}_{1}+\hat{y}_{2}+\hat{y}_{3}+\hat{y}_{4}$. Let
$B\in\mathcal{M}_{n}^{0}(81,337)$. We will illustrate the parts of the proof
of Theorem 5.11 for a few possible choices for
$\hat{\mathbf{y}}\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)$.

  1. 1.

Let
$\left(\begin{matrix}\hat{y}_{1}&\hat{y}_{2}&\hat{y}_{3}&\hat{y}_{4}\end{matrix}\right)=\left(\begin{matrix}5&3&3&2\end{matrix}\right).$

Digraph of $B^{c}$. $\Gamma(B)$ is isomorphic to the following digraph
$\widehat{\Gamma}$,

$\widehat{\Gamma}=C({\bf a}(337))+\\{\hat{e}_{i}:i=1,\ldots,4\\},$

where
$\hat{e}_{i}=\\{(81i+\sum_{k=1}^{i}\hat{y}_{k},1+81(i-1)+\sum_{k=1}^{i}\hat{y}_{k})\\}.$

Note that $\widehat{\Gamma}$ consists of a $337$-cycle $C({\bf a}(337))$ and
four cycles of order $81$ that are made by the edges $\hat{e}_{i}$. The
$337$-cycle and the edges $\hat{e}_{i}$ of $\widehat{\Gamma}$ give another
$337$-cycle and the edges $e_{i,t}$, respectively, in
$\widehat{\Gamma}^{(3)}$. These are explained below in detail.

By Theorem 5.11, $\Gamma(B^{3})$ is isomorphic to $\widehat{\Gamma}^{(3)}$,
given by:

$\widehat{\Gamma}^{(3)}=C(\langle 3\cdot{\bf
a}(337)\rangle_{n})+\\{e_{i,t}:i=1,\ldots,4,t=1,\ldots 3\\},$

where $e_{i,t}:=(\langle 81i+\sum_{k=1}^{i}\hat{y}_{k}-t+1\rangle_{n},\langle
81(i-1)+\sum_{k=1}^{i}\hat{y}_{k}+3-t\rangle_{n}).$ Table 1 shows the edges
$e_{i,t}$.

| $t=1$ | $t=2$ | $t=3$
---|---|---|---
$e_{1,t}$ | $(86,8)$ | $(85,7)$ | $(84,6)$
$e_{2,t}$ | $(170,92)$ | $(169,91)$ | $(168,90)$
$e_{3,t}$ | $(254,176)$ | $(253,175)$ | $(252,174)$
$e_{4,t}$ | $(337,259)$ | $(336,258)$ | $(335,257)$
Table 1:  The edges $e_{i,t}$

Congruence modulo $c$. The $n$-cycle of $\widehat{\Gamma}^{(3)}$ can be
written in terms of the paths $\Pi_{j},j=1,2,3$, as follows:

$C(\langle 3\cdot{\bf
a}(337)\rangle_{n})=\cup_{j=1}^{3}\left(\Pi_{j}+\\{(j+334,j)\\}\right),$

where $\Pi_{j}=P(j+3{\bf a}_{0}(h(j)))$ and
$h(j)=109+\left\lfloor\frac{13-j}{3}\right\rfloor$. Also, recall that the
vertices of the edge $e^{\prime}_{i,j}$ belong $\Pi_{j}$ where,
$e^{\prime}_{i,j}=e_{i,\langle 1-j+\sum_{k=1}^{i}\hat{y}_{k}\rangle_{c}}$.

For example, $j=1$ gives us the path $\Pi_{1}=P(1+3{\bf a}_{0}(113))$, and the
edges $e_{i,1}^{\prime}$, $i=1,2,3,4$, connect the vertices in $\Pi_{1}$ to
form four cycles of order $27$.

Writing $e^{\prime}_{i,1}=(1+3k(i,1),1+3l(i,1))$, we get the values given in
Table 2 for $k(i,1)$ and $l(i,1)$.

| $e^{\prime}_{i,1}$ | $k(i,1)$ | $l(i,1)$
---|---|---|---
$i=1$ | $(85,7)$ | $28$ | $2$
$i=2$ | $(169,91)$ | $56$ | $30$
$i=3$ | $(253,175)$ | $84$ | $58$
$i=4$ | $(337,259)$ | $112$ | $86$
Table 2: $k(i,1)$ and $l(i,1)$ for $\Pi_{1}$

Parts of the partition.  To illustrate the next part of the proof, let us
continue with $j=1$. Considering the vertices of $\Pi_{1}$ in the natural path
order i.e. $V(\Pi_{1})=\\{1,1+3,\ldots,1+3(113-1)\\}$, we see that the first
vertex in $\Pi_{1}$ contained in a $27$-cycle (made by the edge
$e^{\prime}_{1,1}$) is the vertex, $v^{\prime}_{I}(1,1)=7=1+3(2)$. This
implies, $l(1,1)=2$, and $v^{\prime}_{I}(1,1)$ is the third vertex of
$\Pi_{1}$. Therefore, $y(1,1)=2$ (recalling that $y(i,j)$ is defined to be the
number of vertices in $\Pi_{j}$ before the vertex $v^{\prime}_{I}(i,j)$).

Next, $y(2,1)$ is the number of vertices not contained in a $27$-cycle
strictly between $v^{\prime}_{O}(1,1)$ and $v^{\prime}_{I}(2,1)$. Since,
$v^{\prime}_{O}(1,1)=85=1+3(28)$ and $v^{\prime}_{I}(2,1)=91=1+3(30)$, we have
$k(1,1)=28$ and $l(2,1)=30$. This implies, $y(2,1)=l(2,1)-k(1,1)-1=1.$
Similarly, $y(3,1)=l(3,1)-k(2,1)-1=1$ and $y(4,1)=l(4,1)-k(3,1)-1=1.$ Also,
note that $v^{\prime}_{O}(4,1)=337=1+3(112)$ is the last vertex of $\Pi_{1}$.

More generally, to get all the parts of the partition we express the $k(i,j)$
and $l(i,j)$ in terms of the parameters $u_{i}$, $\beta_{i}$, and
$\gamma_{i}$. In this case, we write $\hat{y}_{i}=3u_{i}+\beta_{i}$ and
$\sum_{k=1}^{i}\beta_{k}=3\eta_{i}+\gamma_{i}$,
$\beta_{i},\gamma_{i}\in\\{0,1,2\\}$, to determine the following parameters:

$\displaystyle u_{1}$ $\displaystyle=u_{2}=u_{3}=1,\,u_{4}=0,$
$\displaystyle\beta_{1}$ $\displaystyle=\beta_{4}=2,\,\beta_{2}=\beta_{3}=0,$
$\displaystyle\gamma_{1}$
$\displaystyle=\gamma_{2}=\gamma_{3}=2,\,\gamma_{4}=1.$

Using equation (27), we get $y(i,j)$, $i=1,\ldots,4$, $j=1,\ldots,3$. Thus,
the $Y$ matrix (as defined in Remark 5.12) is equal to:

$Y=\left(\begin{array}[]{ccc}y(1,1)&y(1,2)&y(1,3)\\\ y(2,1)&y(2,2)&y(2,3)\\\
y(3,1)&y(3,2)&y(3,3)\\\ y(4,1)&y(4,2)&y(4,3)\\\
\end{array}\right)=\left(\begin{array}[]{ccc}2&2&1\\\ 1&1&1\\\ 1&1&1\\\
1&0&1\\\ \end{array}\right).$

In particular, the elements of $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{3})$
have one part equal to $2$, one part equal to $0$ and all other parts equal to
$1$.

Final ordering. To determine $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{3})$,
we still need the ordering of the parts. For this we look at the $Y^{\prime}$
matrix in Remark 5.12:

$Y^{\prime}=\left(\begin{array}[]{ccc}y(1,1)&y(1,3)&y(1,2)\\\
y(2,1)&y(2,3)&y(2,2)\\\ y(3,1)&y(3,3)&y(3,2)\\\ y(4,1)&y(4,3)&y(4,2)\\\
\end{array}\right)=\left(\begin{array}[]{ccc}2&1&2\\\ 1&1&1\\\ 1&1&1\\\
1&1&0\\\ \end{array}\right).$

Thus, the partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{3})$ is
given by ${\bf y}=\mathscr{T}(\operatorname{vec}(Y^{\prime})^{T}).$

  2. 2.

Let
$\left(\begin{matrix}\hat{y}_{1}&\hat{y}_{2}&\hat{y}_{3}&\hat{y}_{4}\end{matrix}\right)=\left(\begin{matrix}11&2&0&0\end{matrix}\right).$

Writing $\hat{y}_{i}=3u_{i}+\beta_{i}$ and
$\sum_{k=1}^{i}\beta_{k}=3\eta_{i}+\gamma_{i}$
$\beta_{i},\gamma_{i}\in\\{0,1,2\\}$, gives: $u_{1}=3$, $u_{2}=u_{3}=u_{4}=0$;
$\beta_{1}=\beta_{2}=2$, $\beta_{3}=\beta_{4}=0$ and $\gamma_{1}=2$,
$\gamma_{2}=\gamma_{3}=\gamma_{4}=1$. Using equation (27) to determine
$y(i,j)$, $i=1,\ldots,4$, $j=1,\ldots,3$, we get the following matrices
(defined in Remark 5.12):

$Y=\left(\begin{array}[]{cccc}4&4&3\\\ 1&0&1\\\ 0&0&0\\\ 0&0&0\\\
\end{array}\right)\text{ and }Y^{\prime}=\left(\begin{array}[]{cccc}4&3&4\\\
1&1&0\\\ 0&0&0\\\ 0&0&0\\\ \end{array}\right).$

The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{3})$ is given
by ${\bf y}=\mathscr{T}(\operatorname{vec}(Y^{\prime})^{T}).$

  3. 3.

Let
$\left(\begin{matrix}\hat{y}_{1}&\hat{y}_{2}&\hat{y}_{3}&\hat{y}_{4}\end{matrix}\right)=\left(\begin{matrix}13&0&0&0\end{matrix}\right).$
From $\hat{y}_{i}=3u_{i}+\beta_{i}$ and
$\sum_{k=1}^{i}\beta_{k}=3\eta_{i}+\gamma_{i}$,
$\beta_{i},\gamma_{i}\in\\{0,1,2\\}$, we get: $u_{1}=4$,
$u_{2}=u_{3}=u_{4}=0$; $\beta_{1}=1$, $\beta_{2}=\beta_{3}=\beta_{4}=0$ and
$\gamma_{1}=\gamma_{2}=\gamma_{3}=\gamma_{4}=1$. In this case:

$Y=Y^{\prime}=\left(\begin{array}[]{cccc}5&4&4\\\ 0&0&0\\\ 0&0&0\\\ 0&0&0\\\
\end{array}\right),$

and the partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{3})$ is
given by ${\bf y}=\mathscr{T}(\operatorname{vec}(Y^{\prime})^{T}).$

  4. 4.

Let
$\left(\begin{matrix}\hat{y}_{1}&\hat{y}_{2}&\hat{y}_{3}&\hat{y}_{4}\end{matrix}\right)=\left(\begin{matrix}4&3&3&3\end{matrix}\right).$
Writing $\hat{y}_{i}=3u_{i}+\beta_{i}$ and
$\sum_{k=1}^{i}\beta_{k}=\leavevmode\nobreak\ 3\eta_{i}+\leavevmode\nobreak\
\gamma_{i}$ $\beta_{i},\gamma_{i}\in\\{0,1,2\\}$ gives:
$u_{1}=\leavevmode\nobreak\ u_{2}=u_{3}=u_{4}=1$; $\beta_{1}=1$,
$\beta_{2}=\beta_{3}=\beta_{4}=0$ and
$\gamma_{1}=\gamma_{2}=\gamma_{3}=\leavevmode\nobreak\ \gamma_{4}=1$.

Again,

$Y=Y^{\prime}=\left(\begin{array}[]{cccc}2&1&1\\\ 1&1&1\\\ 1&1&1\\\ 1&1&1\\\
\end{array}\right)$

and the partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{3})$ is
given by ${\bf y}=\mathscr{T}(\operatorname{vec}(Y^{\prime})^{T}).$

######  Corollary 5.14.

Let $A\in\mathcal{M}_{n}^{0}(q,qc\hat{d}+y)$ and
$\left(\begin{matrix}y_{1}&\ldots&y_{c\hat{d}}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.
Then $A=B^{c}$ for some $B\in\mathcal{M}_{n}^{0}(qc,qc\hat{d}+y)$ if and only
if:

  1. 1.

For every $i\in\\{1,\ldots,\hat{d}\\}$ there exists $u_{i}$ so that
$y_{t\hat{d}+i}\in\\{u_{i},u_{i}+1\\}$ for $t=0,\ldots,c-1$. (If for some $i$
all $y_{t\hat{d}+i}$ are equal, then we say that they are equal to $u_{i}$.)

We define, $\beta_{i}:=|\\{t\in\\{0\ldots,c-1\\};y_{t\hat{d}+i}=u_{i}+1\\}|$,
$i=1,\ldots,\hat{d}$, and $\sum_{k=1}^{i}\beta_{i}:=\eta_{i}c+\gamma_{i}$,
where $\gamma_{i}\in\\{0,\ldots,c-1\\}$. In addition, $\gamma_{0}:=0$.

With these parameters we define $y(i,j)$ as follows :

$y(i,j):=\begin{cases}u_{i}+1,&j=\langle\gamma_{i-1}+1\rangle_{c},\ldots,\langle\gamma_{i-1}+\beta_{i}\rangle_{c}\\\
u_{i},&j=\langle\gamma_{i-1}+\beta_{i}+1\rangle_{c},\ldots,\langle\gamma_{i-1}+c\rangle_{c}\end{cases},$

where $i=1,\ldots,\hat{d}$, $j=1\ldots,c$.

  2. 2.

The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$ consists of
the parts $y(i,j)$, $i=1,\ldots,\hat{d}$, $j=1\ldots,c$. Further, the part
$y(i,j)$ is followed by $y(i+1,j)$ for $i=1,\ldots,\hat{d}-1$ and
$y(\hat{d},j)$ is followed by $y(1,\langle j-y\rangle_{c})$ in
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.

If the conditions above are satisfied, then $A=B^{c}$ for
$B\in\mathcal{M}_{n}^{0}(qc,qc\hat{d}+y)$ with
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)=\mathscr{T}(\left(\begin{matrix}\hat{y}_{1}&\ldots&\hat{y}_{\hat{d}}\end{matrix}\right)),$
where $\hat{y}_{i}:=\sum_{j=1}^{c}y(i,j)$, for $i=1,\ldots,\hat{d}$.

###### Proof.

The result follows directly from Theorem 5.11. ∎

######  Example 5.15.

Let $n=s=337$, $q=27$, $d=12$, $c=3$, $y=13$ and $n=s=qd+y$. By Definition
4.5, any partition class containing $12$ non-negative integers that sum to
$13$ is a partition class for some matrix in $\mathcal{M}_{n}^{0}(27,337)$.

Let $A\in\mathcal{M}_{n}^{0}(27,337)$ and ${\bf
y}=\left(\begin{matrix}y_{1}&\ldots&y_{12}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.
Let $Y^{\prime}_{A}$ be a $\hat{d}\times c$ matrix satisfying
$\operatorname{vec}(Y^{\prime}_{A})^{T}={\bf y}$:

$Y^{\prime}_{A}=\left(\begin{array}[]{ccc}y_{1}&y_{5}&y_{9}\\\
y_{2}&y_{6}&y_{10}\\\ y_{3}&y_{7}&y_{11}\\\ y_{4}&y_{8}&y_{12}\\\
\end{array}\right).$

We want to determine when $A=B^{3}$ for some matrix
$B\in\mathcal{M}_{n}^{0}(81,337)$.

From the first part of Corollary 5.14, we know that for $A$ to be a power of
any matrix $B\in\mathcal{M}_{n}^{0}(81,337)$, each row in $Y^{\prime}_{A}$
must have elements from a set of the form $\\{u_{i},u_{i}+1\\}$ for some
integer $u_{i}\geq 0$. Under this constraint, we can choose the row sums of
$Y^{\prime}_{A}$ in many possible ways taking care that the sum of all the
entries in $Y^{\prime}_{A}$ is equal to $13$. Let us look at a few specific
examples.

  1. 1.

Let

$Y^{\prime}_{A}=\left(\begin{array}[]{cccc}1&1&0\\\ 0&0&0\\\ 2&2&2\\\ 1&2&2\\\
\end{array}\right).$

From the first item of Corollary 5.14, we get: $u_{1}=u_{2}=0$, $u_{3}=2$,
$u_{4}=1$, $\beta_{1}=2$, $\beta_{2}=\beta_{3}=0$, $\beta_{4}=2$ and
$\gamma_{1}=\gamma_{2}=\gamma_{3}=2$, $\gamma_{4}=1.$

Thus,

$Y=\left(\begin{array}[]{ccc}y(1,1)&y(1,2)&y(1,3)\\\ y(2,1)&y(2,2)&y(2,3)\\\
y(3,1)&y(3,2)&y(3,3)\\\ y(4,1)&y(4,2)&y(4,3)\\\
\end{array}\right)=\left(\begin{array}[]{cccc}1&1&0\\\ 0&0&0\\\ 2&2&2\\\
2&1&2\\\ \end{array}\right).$

Using the second item of Corollary 5.14, we get:

$Y^{\prime}=\left(\begin{array}[]{ccc}y(1,1)&y(1,3)&y(1,2)\\\
y(2,1)&y(2,3)&y(2,2)\\\ y(3,1)&y(3,3)&y(3,2)\\\ y(4,1)&y(4,3)&y(4,2)\\\
\end{array}\right)=\left(\begin{array}[]{cccc}1&0&1\\\ 0&0&0\\\ 2&2&2\\\
2&2&1\\\ \end{array}\right).$

We see that $\operatorname{vec}(Y^{\prime}_{A})^{T}$ is permutationally
equivalent to $\operatorname{vec}(Y^{\prime})^{T}$ and thus satisfies all the
conditions of Corollary 5.14. Therefore, $A=B^{3}$ for
$B\in\mathcal{M}_{n}^{0}(81,337)$ with
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)=\mathscr{T}(\hat{\bf y})$, where
$\hat{\bf y}=\left(\begin{matrix}6&5&2&0\end{matrix}\right)$.

  2. 2.

For

$Y^{\prime}_{A}=\left(\begin{array}[]{cccc}4&4&3\\\ 1&0&1\\\ 0&0&0\\\ 0&0&0\\\
\end{array}\right),$

we get $u_{1}=3$, $u_{2}=u_{3}=u_{4}=0$; $\beta_{1}=\beta_{2}=2$,
$\beta_{3}=\beta_{4}=0$ and
$\gamma_{1}=2$,$\gamma_{2}=\gamma_{3}=\gamma_{4}=1$.

Thus,

$Y=\left(\begin{array}[]{cccc}4&4&3\\\ 1&0&1\\\ 0&0&0\\\ 0&0&0\\\
\end{array}\right).$

Referring back to Example 5.13 (Item 2.) we know that

$Y^{\prime}=\left(\begin{array}[]{cccc}4&3&4\\\ 1&1&0\\\ 0&0&0\\\ 0&0&0\\\
\end{array}\right).$

This time the second item of Corollary 5.14 is not satisfied. Hence, $A\neq
B^{3}$ for any $B\in\mathcal{M}_{n}^{0}(81,337)$.

  3. 3.

Let

$Y^{\prime}_{A}=\left(\begin{array}[]{cccc}2&1&1\\\ 1&1&1\\\ 1&1&1\\\ 1&1&1\\\
\end{array}\right).$

In this case we get: $u_{1}=u_{2}=u_{3}=u_{4}=1$; $\beta_{1}=1$,
$\beta_{2}=\beta_{3}=\beta_{4}=0$ and
$\gamma_{1}=\gamma_{2}=\gamma_{3}=\gamma_{4}=1$. Thus,

$Y=\left(\begin{array}[]{cccc}2&1&1\\\ 1&1&1\\\ 1&1&1\\\ 1&1&1\\\
\end{array}\right).$

From Item $4$ of Example 5.13 we note that $Y^{\prime}=Y$ and $A=B^{3}$ for
$B\in\mathcal{M}_{n}^{0}(81,337)$ with the
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B)=\mathscr{T}(\hat{\bf y})$, where
$\hat{\bf y}=\left(\begin{matrix}4&3&3&3\end{matrix}\right).$

###  5.4 Type III arc is a power of a Type I arc

In this subsection we assume $n=qd+y$, $\gcd(qd,y)=1$,
$y\in\\{1,\ldots,q-1\\}$. By Theorem 3.10:

$\mathcal{K}_{n}(qd+y,qd)^{d}=\mathcal{K}_{n}(q,qd+y).$

The following theorem determines the partition class of $B^{d}$ for
$B\in\mathcal{M}_{n}^{0}(qd+y,qd)$. We note that the result can also be
obtained from Theorem 5.11 by taking $i=1$, $\hat{d}=1$, and $c=d$.

######  Theorem 5.16.

Let $B\in\mathcal{M}_{n}^{0}(qd+y,qd)$, where $n=s=qd+y$, $\gcd(d,s)=1$ and
$y\in\\{1,\ldots,q-1\\}$. We define $u$ and $\beta$ by writing $y:=ud+\beta$,
where $\beta\in\\{0,\ldots,d-1\\}$. For $j=1,\ldots,d$ we define:

$\displaystyle y(j):=\begin{cases}u+1,&j=1,\ldots,\beta\\\
u,&j=\beta+1,\ldots,d.\end{cases}$ (33)

The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{d})$ is defined
as follows:

  * •

the parts of the partition are equal to $y(j)$, $j=1,\ldots,d$,

  * •

in the partition $y(j)$ is followed by $y(\langle j-y\rangle_{d})$.

###### Proof.

Let $B\in M_{n}^{0}(\hat{q},\hat{s})$, where $\hat{q}=qd$, $\hat{s}=qd+y$,
$\gcd(\hat{q},n)=1$. By Theorem 4.1, $\Gamma(B)$ is isomorphic to $C({\bf
a}(n))+\\{(qd,1)\\}$, which is isomorphic to:

$\widehat{\Gamma}:=C({\bf a}(n))+\\{(\hat{s},y+1)\\}.$

Digraph of $B^{d}$.  The digraph of $\Gamma(B^{d})$ is isomorphic to
$\widehat{\Gamma}^{(d)}$:

$\widehat{\Gamma}^{(d)}=C(\langle d\cdot{\bf
a}(n)\rangle_{n})+\\{e_{t}:t=1,\ldots d\\},$

where

$e_{t}=(s-t+1,y+d-t+1),t=1,\ldots d.$

In particular, $\widehat{\Gamma}^{(d)}$ consists of an $n$-cycle $C(\langle
d\cdot{\bf a}(n)\rangle_{n})$ together with $d$ $q$-cycles, where each
$q$-cycle is formed by an edge $e_{t}$ connecting two vertices of the
$n$-cycle. The edge $(\hat{s},y+1)$ in $\widehat{\Gamma}$ and the edges
$e_{t},t=1,\ldots,d$, in $\widehat{\Gamma}^{(d)}$ have weights equal to
$1-\alpha$. Equivalently, all the $q$-cycles in $\widehat{\Gamma}^{(d)}$ have
the weight $1-\alpha$.

Congruence modulo $d$. Let $\Pi_{j}:=P(j+d{\bf a}_{0}(h(j)))$, where
$h(j)=1+q+\left\lfloor\frac{y-j}{d}\right\rfloor$. We have:

$C({\bf a}(n))^{(d)}=\cup_{j=1}^{d}\left(\Pi_{j}+\\{((q-1)d+y+j,j)\\}\right),$

and note that $\Pi_{j}$ is followed by $\Pi_{\langle j-y\rangle_{d}}$
(equivalently, $\Pi_{\langle j+y\rangle_{d}}$ is followed by $\Pi_{j}$) in
$\widehat{\Gamma}^{(d)}$. Both vertices of $e_{t}$ belong to $\Pi_{j}$, where
$t$ is congruent to $\langle 1+y-j\rangle_{d}$. In other words, the edge
$e_{\langle 1+y-j\rangle_{d}}$ connects two vertices in $\Pi_{j}$ to form a
$q$-cycle in $\widehat{\Gamma}^{(d)}$. We define $e_{j}^{\prime}:=e_{\langle
1+y-j\rangle_{d}}$ and note that
$\\{e_{t}:t=1,\ldots,d\\}=\\{e_{j}^{\prime}:j=1,\ldots,d\\}$.

Let $e_{j}^{\prime}=(v_{O}^{\prime}(j),v_{I}^{\prime}(j))$ and $y=ud+\beta$,
$\beta\in\\{0,\ldots,d-1\\}$. Then, $v_{O}^{\prime}(j)=j+k(j)d$ and
$v_{I}^{\prime}(j)=j+l(j)d$, where

$\displaystyle k(j):=\begin{cases}q+u&\text{ for }j\leq\beta\\\ q+u-1&\text{
for }j>\beta,\end{cases}$ (34)

$\displaystyle l(j):=\begin{cases}u+1&\text{ for }j\leq\beta\\\ u&\text{ for
}j>\beta.\end{cases}$ (35)

Parts of the Partition. For a fixed $j$, there is only one $q$-cycle made by
the edge $e^{\prime}_{j}=(v^{\prime}_{O}(j),v^{\prime}_{I}(j))$ in $\Pi_{j}$.
Also, $k(j)=h(j)-1$ implies that $v^{\prime}_{O}(j)=j+k(j)d$ is the last
vertex in $\Pi_{j}$.

We define $y(j):=l(j)-0$ as the number of vertices that lie before
$v^{\prime}_{I}(j)$ in $\Pi_{j}$. Thus, $y(j)$ is equal to $l(j)$ and is as
defined in (33) in the statement of the theorem.

Ordering of Parts. Since the $q$-cycle with the edge $e_{j}^{\prime}$ is
followed by the $q$-cycle containing the edge $e^{\prime}_{\langle
j-y\rangle_{d}}$, the part $y(j)$ is followed by the part $y(\langle
j-y\rangle_{d})$ in the partition.

∎

######  Remark 5.17.

For $B\in\mathcal{M}_{n}^{0}(qd,qd+y)$, let us define the row vector ${\bf y}$
consisting of parts of the partition class
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{d})$, i.e ${\bf
y}:=\left(\begin{matrix}y(1)&\ldots&y(d)\end{matrix}\right).$ Since, $y(j)$ is
followed by $y(\langle j-y\rangle_{d})$ in the partition class
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{d})$, we can permute the elements
of ${\bf y}$ to get the row vector:

${\bf y^{\prime}}:=\left(\begin{matrix}y(1)&y(\langle
1-y\rangle_{d})&\ldots&y(\langle
1-(d-1)y)\rangle_{d}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{d}).$

The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{d})$ is equal
to $\mathscr{T}(\bf y^{\prime})$.

######  Example 5.18.

For $n=337$ we have $\mathcal{K}_{n}(27,337)=\mathcal{K}_{n}(337,324)^{12}$,
where $q=27$, $n=s=337$, $d=12$, $y=s-qd=13$ and
$\mathcal{M}_{n}^{0}(qd+y,qd)=\mathcal{M}_{n}^{0}(337,324).$ Let
$B\in\mathcal{M}_{n}^{0}(337,324)$.

Digraph of $B^{12}$. The digraph $\Gamma(B^{12})$ is isomorphic to
$\widehat{\Gamma}^{(12)}$:

$\widehat{\Gamma}^{(12)}=C(\langle 12\cdot{\bf
a}(337)\rangle_{n})+\\{e_{t}:t=1,\ldots,12\\},$

where

$e_{t}=(338-t,26-t),t=1,\ldots,12.$

Congruence modulo $d$. For $\Pi_{j}=(j+12{\bf a}_{0}(h(j))),$ with
$h(j)=28+\lfloor\frac{13-j}{12}\rfloor$, the edge $e^{\prime}_{j}=e_{\langle
14-j\rangle_{12}}$ connects the vertices in $\Pi_{j}$ to form a single
$27$-cycle.

For example, the edge $e^{\prime}_{1}=e_{1}=(337,25)$ forms a $27$-cycle by
connecting two vertices of $\Pi_{1}=P(1+12{\bf a}_{0}(29))$. Similarly, the
edge $e^{\prime}_{2}=e_{12}=(326,14)$ connects vertices in $\Pi_{2}=P(2+12{\bf
a}_{0}(28))$ to form a $27$-cycle.

Writing $e^{\prime}_{1}=(1+12k(1),1+12l(1))$ gives $k(1)=28$ and $l(1)=2$.
Similarly, $e^{\prime}_{2}=(2+12k(2),2+12l(2))$ gives $k(2)=27$ and $l(2)=1$.

Parts of the Partition. Recall that $y(j)$ is the number of vertices in
$\Pi_{j}$ before $v_{I}^{\prime}(j)=j+12l(j)$. Continuing with $\Pi_{1}$, from
$l(1)=2$ we get $y(1)=2$. Similarly, for $\Pi_{2}$ we have $l(2)=1$ which
gives $y(2)=1$. More generally, to get all the parts $y(j)$, we write $y$ in
terms of $u$ and $\beta$: $y=12u+\beta$, $\beta\in\\{0,\ldots,11\\}$. This
gives us:

$\displaystyle y(j):=\begin{cases}2&\text{ for }j\leq 1\\\ 1&\text{ for
}j>1.\end{cases}$

Ordering. From Remark 5.17, we have:

${\bf
y^{\prime}}=\left(\begin{array}[]{cccccccccccc}y(1)&y(12)&y(11)&y(10)&y(9)&y(8)&y(7)&y(6)&y(5)&y(4)&y(3)&y(2)\\\
\end{array}\right).\\\ $

Thus, ${\bf
y^{\prime}}=\left(\begin{array}[]{cccccccccccc}2&1&1&1&1&1&1&1&1&1&1&1\end{array}\right)$
and the partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{12})$ is
given by $\mathscr{T}({\bf y^{\prime}})$. Note that this uniquely defined
partition class for $B^{12}$ is same as the partition class
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{\prime 3})$, where
$B^{\prime}\in\mathcal{M}_{n}^{0}(81,337)$ and
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{\prime})=\mathscr{T}(\hat{\bf y})$
for $\hat{\bf y}=\left(\begin{matrix}4&3&3&3\end{matrix}\right)$ (Item $4$,
Example 5.13).

######  Corollary 5.19.

Let $A\in\mathcal{M}_{n}^{0}(q,qd+y)$ have the associated partition
$\left(\begin{matrix}y_{1}&\ldots&y_{d}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.
Then $A=B^{d}$ for some $B\in\mathcal{M}_{n}^{0}(qd,qd+y)$ if and only if:

  1. 1.

There exists $u$ such that $y_{j}\in\\{u,u+1\\}$. (If all $y_{j}$ are equal
then we say they are all equal to $u$).

We define $\beta:=|\\{j\in\\{1\ldots,d\\};y_{j}=u+1\\}|$ and

$y(j):=\begin{cases}u+1&\text{ for }j=1,\ldots,\beta\\\ u&\text{ for
}j=\beta+1,\ldots,d.\end{cases}$

  2. 2.

The partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$ consists of
the parts $y(j)$, $j=1,\ldots,d$, where the part $y(j)$ is followed by the
part $y(\langle j-y\rangle_{d})$ in
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.

######  Example 5.20.

For $n=337$ we have $\mathcal{K}_{n}(27,337)=\mathcal{K}_{n}(337,324)^{12}$.
In this case, the relevant parameters are $q=27$, $s=337$, $d=12$, and $y=13$.
By Definition 4.5 any $12$ non-negative integers that sum up to $13$ form a
partition class for some matrix in $\mathcal{M}_{n}^{0}(27,337)$. Let
$A\in\mathcal{M}_{n}^{0}(27,337)$ and ${\bf
y^{\prime}}=\left(\begin{matrix}y_{1}&\ldots&y_{12}\end{matrix}\right)\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$.

The first part of Corollary 5.19 restricts the elements in ${\bf y^{\prime}}$
to be in the set $\\{u,u+1\\}$ for some integer $u$. This necessary condition
leaves us with just one choice for the vector ${\bf y}$ (as defined in Remark
5.17), which contains the parts of the partition:

${\bf
y}=\left(\begin{array}[]{cccccccccccc}2&1&1&1&1&1&1&1&1&1&1&1\end{array}\right).$

The above ${\bf y}$ gives $\beta=1$ and $u=1$. With these parameters, we get
the unique partition class $\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$ which
is defined in Corollary 5.19. Therefore $A=B^{12}$ for some
$B\in\mathcal{M}_{n}^{0}(337,324)$ if and only if ${\bf
y^{\prime}}\in\mathscr{P}_{\text{\emph{\tiny{III}}}}(A)$, where:

$\displaystyle{\bf y^{\prime}}={\bf y}$
$\displaystyle=\left(\begin{array}[]{cccccccccccc}2&1&1&1&1&1&1&1&1&1&1&1\\\
\end{array}\right).$

In that case $A=B^{12}=B^{\prime 3}$ for $B\in\mathcal{M}_{n}^{0}(337,324)$
and $B^{\prime}\in\mathcal{M}_{n}^{0}(81,337)$, where
$\mathscr{P}_{\text{\emph{\tiny{III}}}}(B^{\prime})=\mathscr{T}(\hat{\bf y})$
for $\hat{\bf y}=\left(\begin{matrix}4&3&3&3\end{matrix}\right).$

Acknowledgement. This publication has emanated from research supported in part
by a grant from Science Foundation Ireland under Grant number 18/CRT/6049. For
the purpose of Open Access, the author has applied a CC BY public copyright
licence to any Author Accepted Manuscript version arising from this
submission. The research of the second author is supported in part by NSERC
Discovery Grant RGPIN-2019-05408.

## References

  * [1] Nicholas J. Higham and Lijing Lin.  On $p$th roots of stochastic matrices.  Linear Algebra Appl., 435(3):448–463, 2011.
  * [2] Hisashi Ito.  A new statement about the theorem determining the region of eigenvalues of stochastic matrices.  Linear Algebra Appl., 267:241–246, 1997.
  * [3] Charles R. Johnson and Pietro Paparella.  A matricial view of the Karpelevič theorem.  Linear Algebra Appl., 520:1–15, 2017.
  * [4] F. I. Karpelevič.  On the characteristic roots of matrices with nonnegative elements.  Izvestiya Akad. Nauk SSSR. Ser. Mat., 15:361–383, 1951.
  * [5] Bara Kim and Jeongsim Kim.  Proofs of conjectures on the Karpelevich arcs in the region of eigenvalues of stochastic matrices.  Linear Algebra Appl., 595:13–23, 2020.
  * [6] Stephen Kirkland, Thomas Laffey, and Helena Šmigoc.  The Karpelevič region revisited.  J. Math. Anal. Appl., 490(2):124332, 17, 2020.
  * [7] Stephen Kirkland and Helena Šmigoc.  Stochastic matrices realising the boundary of the Karpelevič region.  Linear Algebra Appl., 635:116–138, 2022.
  * [8] Andrei Nikolaevitch Kolmogorov.  Markov chains with a countable number of possible states.  Bull. Mosk. Gos. Univ. Math. Mekh, 1(3):1–15, 1937.