# Quasi-Triangularization of Matrix Polynomials
over Arbitrary Fields ††thanks: This publication is part of the “Proyecto de
I+D+i PID2019-106362GB-I00 financiado por MCIN/AEI/10.13039/501100011033”. It
has been also funded by “Ministerio de Economía, Industria y Competitividad
(MINECO)” of Spain through grants MTM-2015-65798-P and BES-2013-065688.

L.M. Anguas Departamento de Matemática e Informática Aplicadas a las
Ingenierías Civil y Naval, Escuela Técnica Superior de Ingenieros de Caminos,
Canales y Puertos, Universidad Politécnica de Madrid, Profesor Aranguren, 3,
28040 Madrid, Spain<EMAIL_ADDRESS>F. M. Dopico Departamento de
Matemáticas, Universidad Carlos III de Madrid, Avda. Universidad 30, 28911
Leganés, Spain<EMAIL_ADDRESS>R. Hollister Department of Mathematics,
University at Buffalo, Buffalo NY 14260 USA<EMAIL_ADDRESS>D.S. Mackey
Department of Mathematics, Western Michigan University, Kalamazoo MI
49008-5248 USA<EMAIL_ADDRESS>
###### Abstract

In [19], Taslaman, Tisseur, and Zaballa show that any regular matrix
polynomial $P(\lambda)$ over an algebraically closed field is spectrally
equivalent to a triangular matrix polynomial of the same degree. When
$P(\lambda)$ is real and regular, they also show that there is a real quasi-
triangular matrix polynomial of the same degree that is spectrally equivalent
to $P(\lambda)$, in which the diagonal blocks are of size at most $2\times 2$.
This paper generalizes these results to regular matrix polynomials
$P(\lambda)$ over _arbitrary fields_ $\mathbb{F}$, showing that any such
$P(\lambda)$ can be quasi-triangularized to a spectrally equivalent matrix
polynomial over $\mathbb{F}$ of the same degree, in which the largest diagonal
block size is bounded by the highest degree appearing among all of the
$\mathbb{F}$-irreducible factors in the Smith form for $P(\lambda)$.

Key words. matrix polynomials, triangularization, arbitrary field,
majorization, inverse problem, Mobius transformation.

AMS subject classification. 15A18, 15A21, 15A54.

##  1 Introduction

Triangularizations of matrix polynomials that preserve degree as well as the
finite and infinite spectral structure via unimodular equivalence are
essentially Schur-like forms for matrices whose entries are polynomials. These
have been achieved over algebraically closed fields for regular quadratic
matrix polynomials in [20], and for regular matrix polynomials of arbitrary
degree in [19]. There are also some results in [19] on singular matrix
polynomials, but these will not be addressed in this paper. Also in [19, 20],
when the underlying field is $\mathbb{R}$, the authors show how to produce
quasi-triangularizations with diagonal blocks of size at most 2$\times$2.

The goal of this paper is similar: given a regular matrix polynomial
$P(\lambda)$, to show how to construct a regular quasi-triangular matrix
polynomial with the same finite and infinite spectral structure as
$P(\lambda)$, i.e., is spectrally equivalent to $P(\lambda)$, and has the same
degree as $P(\lambda)$. However, this work is an extension of [19] in that the
results presented here are for matrix polynomials over an _arbitrary field_.
In order to achieve this generalization, though, the possibility of diagonal
blocks of sizes even larger than 2$\times$2 must be allowed. We show that a
quasi-triangularization can always be constructed in which the sizes of the
diagonal blocks do not exceed $k\times k$, where $k$ is the highest degree
among all of the irreducible factors of the invariant polynomials in the Smith
form of the given polynomial matrix $P(\lambda)$. Note that the term _quasi-
triangular_ is used throughout this paper to refer to square matrices that are
block upper (or lower) triangular with square blocks along the main diagonal,
at least one of which has size 2$\times$2 or larger. A matrix is _$k$ -quasi-
triangular_ if the diagonal blocks are no larger than $k\times k$.

Here is a brief overview of the paper. After some preliminary discussion of
concepts, notation, and terminology in Section 2, we begin in Section 3 by
solving the quasi-triangular _realization problem_ for finite spectral data
over an arbitrary field $\mathbb{F}$. That is, we take as starting point a
collection of finite spectral data rather than a matrix polynomial, and show
how to construct a strictly regular $k$-quasi-triangular matrix polynomial
over $\mathbb{F}$ having exactly the given spectral data; here $k$ is the
largest degree among the irreducible divisors of the given data. The solution
of this inverse problem is the main technical result of the paper; all other
results depend on and follow from this. The central idea of the proof is to
take the given spectral data, form the corresponding Smith form, and then
systematically “un-diagonalize” in a way that moves the matrix polynomial
toward the desired degree, while maintaining quasi-triangularity. This is a
proof technique used in [8], and then developed by [19]; some antecedents of
this technique can also be found in [13]. We develop it further here, adapting
it to the arbitrary field setting. Indeed, a number of nontrivial ingredients
go into proving this quasi-triangular realization result by this method —
majorization plays a role, as well as a new combinatorial lemma on the
partitioning of integer multisets. In Section 4 we extend this realization
result to include elementary divisors at $\infty$ in the given spectral data.
In order to achieve this extension, we use the well-known tool of Möbius
transformations [12], although once again we will need to do a significant
amount of work to adapt them to work smoothly for matrix polynomials over
arbitrary fields. At this point the signature result of the paper — the quasi-
triangularization of any regular matrix polynomial over an arbitrary field in
Theorem 4.9 — now follows easily. Finally, in Section 5 we investigate
conditions for describing when exact triangularization is possible in the
arbitrary field setting; we also display several families of examples, some
that illustrate the sharpness of $k$ as a general upper bound on the size of
the diagonal blocks in quasi-triangularizations, and others that show that
this upper bound $k$ can sometimes be a huge overestimate of the diagonal
block size that is actually attainable.

##  2 Preliminaries

In this paper, we deal with _polynomial matrices_ (also referred to as _matrix
polynomials_) over an arbitrary field $\mathbb{F}$, i.e., matrices whose
entries are polynomials with coefficients from $\mathbb{F}$. In particular, we
will be working only with _regular_ matrix polynomials, that is, square matrix
polynomials with determinant different from the zero polynomial. A polynomial
matrix is _unimodular_ if it is regular and has a (nonzero) constant
determinant. Throughout the paper the set of natural numbers are denoted by
$\mathbb{N}$, and includes zero; $\mathbb{N}^{+}$ is then the set of positive
integers.

The Smith form is a canonical representation of matrix polynomials under
_unimodular equivalence_ , i.e., obtained by left and right multiplication by
unimodular matrix polynomials. This form was first defined for integer
matrices [18]. We will use the extension given in [6] for matrix polynomials:

######  Theorem 2.1 (Smith form).

Let $P(\lambda)$ be an $m\times n$ matrix polynomial over an arbitrary field
$\mathbb{F}$. Then there exists $r\in\mathbb{N}$, and unimodular matrix
polynomials $U(\lambda)$ and $V(\lambda)$ such that

$U(\lambda)P(\lambda)V(\lambda)={\rm diag}(s_{1}(\lambda),\dots,s_{\mathop{\rm
min}\\{m,n\\}}(\lambda))=:S(\lambda)$

where $s_{i}(\lambda)\in\mathbb{F}[\lambda]$, for $i=1,\dots,\mathop{\rm
min}\\{m,n\\}$, $s_{1}(\lambda),\dots,s_{r}(\lambda)$ are monic,
$s_{r+1}(\lambda),\dots,s_{\mathop{\rm min}\\{m,n\\}}(\lambda)$ are
identically-zero, and $s_{i}(\lambda)$ is a divisor of $s_{i+1}(\lambda)$ for
$i=1,\dots,r-1$. Moreover, the number $r$ is equal to the rank of $P$, and the
diagonal entries of the $m\times n$ matrix polynomial $S(\lambda)$ are
uniquely determined by the multiplicative relations

$s_{1}(\lambda)s_{2}(\lambda)\dotsb
s_{j}(\lambda)\;=\;\gcd\bigl{\\{}\,\text{all }j\times j\text{ minors of
$P(\lambda)$\,}\bigr{\\}}\,,\;\text{ for }\;j=1,\dotsc,r\,.$ (2.1)

When $P(\lambda)$ is regular, then $r=m=n$, and $S(\lambda)$ is a nonsingular
diagonal matrix.

The diagonal matrix $S(\lambda)$ featuring in this theorem is called the
_Smith form_ of $P(\lambda)$. The nonzero diagonal entries of $S(\lambda)$ are
called the _invariant polynomials_ of $P(\lambda)$, and their zeros are the
_finite eigenvalues_ of $P(\lambda)$. An invariant polynomial will be called
_trivial_ if it is identically equal to 1 and _nontrivial_ otherwise.

A non-constant irreducible polynomial $\chi(\lambda)\in\mathbb{F}[\lambda]$
that divides some invariant polynomial of $P(\lambda)$ will be called an
_irreducible divisor_ of $P(\lambda)$. This new concept and terminology is
adopted in this work because of the central role that will be played here by
these objects. Given an invariant polynomial $s_{i}(\lambda)$ and an
irreducible divisor $\chi(\lambda)$, or indeed any irreducible polynomial
$\chi(\lambda)$, there is a unique natural number $\alpha_{i}$ (perhaps zero)
such that

$s_{i}(\lambda)\,=\,\chi(\lambda)^{\alpha_{i}}\mkern 1.0mu\mkern
1.0mu\widehat{s}_{i}(\lambda)\,,$

with $\widehat{s}_{i}(\lambda)$ not divisible by $\chi(\lambda)$. Any factor
$\chi(\lambda)^{\alpha_{i}}$ with $\alpha_{i}>0$ is traditionally called an
_elementary divisor_ [7] of $P(\lambda)$. The number $\alpha_{i}$, whether it
is zero or nonzero, is called the _partial multiplicity_ of the irreducible
$\chi(\lambda)$ with respect to the invariant polynomial $s_{i}(\lambda)$,
while the sequence $(\alpha_{1},\alpha_{2},\dotsc,\alpha_{r})$, with
$0\leq\alpha_{1}\leq\alpha_{2}\leq\dotsb\leq\alpha_{r}$, is called the
_partial multiplicity sequence_ of $P(\lambda)$ at $\chi(\lambda)$, which we
will denote by

${\cal P}\\!{\cal M}(P,\chi):=\,(\alpha_{1},\alpha_{2},\dotsc,\alpha_{r})\,.$
(2.2)

Note that ${\cal P}\\!{\cal M}(P,\chi)$ may consist of all zeroes, and $\chi$
is an irreducible divisor of $P$ exactly when some $\alpha_{i}$ is nonzero.
The partial multiplicity sequence of a degree one irreducible divisor
$\chi(\lambda)=\lambda-\lambda_{0}$ is also sometimes referred to as the
partial multiplicity sequence of the eigenvalue $\lambda_{0}$. An abbreviated
notation, ${\cal P}\\!{\cal M}(\chi)$, will also be used for the partial
multiplicity sequence associated to $\chi(\lambda)$. This may be used when the
underlying matrix polynomial is understood, but more commonly it will be
employed when there is _no_ matrix polynomial in the background at all, and
the sequence being specified (and its association with $\chi$) is part of a
collection of given spectral data that is yet to be realized. To emphasize
this role of being input data for a realization problem, we will sometimes
instead write ${\cal P}\\!{\cal M}_{\text{given}}(\chi)$.

In using the notation (2.2), it is very useful to _abandon_ a standard
convention, i.e., the convention that only _monic_ irreducibles should be
allowed or considered. As far as partial multiplicities are concerned, there
is no important difference between an irreducible $\chi(\lambda)$ and any
nonzero scalar multiple $c\chi(\lambda)$. In particular, since for any
invariant polynomial $s_{i}(\lambda)$ we have

$s_{i}(\lambda)\,=\,\chi(\lambda)^{\alpha_{i}}\,\mkern
1.0mu\widehat{s}_{i}(\lambda)\,=\,\bigl{(}c\chi(\lambda)\bigr{)}^{\alpha_{i}}\,\mkern
1.0mu\frac{\,\widehat{s}_{i}(\lambda)\,}{c^{\alpha_{i}}}\,=\,\bigl{(}c\chi(\lambda)\bigr{)}^{\alpha_{i}}\,\mkern
1.0mu\widetilde{s}_{i}(\lambda)$

where $c\chi$ and $\widetilde{s_{i}}$ are coprime, we see that the definition
of the partial multiplicity sequence $(\alpha_{1},\dotsc,\alpha_{r})$ is
unaffected by allowing non-monic irreducibles. Thus we may consistently say
that

${\cal P}\\!{\cal M}(P,c\chi)\;=\;{\cal P}\\!{\cal M}(P,\chi)$ (2.3)

for any nonzero scalar $c\in\mathbb{F}$, and thereby simply ignore whether an
irreducible is monic or not. In line with this, we will say that two
$\mathbb{F}$-irreducible polynomials are _distinct irreducibles_ if neither is
a nonzero scalar multiple of the other.

######  Remark 2.2.

In effect we are implicitly defining an equivalence relation on the set of
$\mathbb{F}$-irreducible polynomials. That is, two irreducibles are equivalent
(with respect to partial multiplicity sequences) if one is a nonzero scalar
multiple of the other. Distinct irreducibles are then just representatives of
different equivalence classes under this relation.

######  Remark 2.3.

It is important to keep in mind that there are fields $\mathbb{F}$ that
support the presence of $\mathbb{F}$-irreducible polynomials of arbitrarily
high degree. A simple example of this is the field $\mathbb{Q}$ of rational
numbers. Using the Eisenstein criterion [2], it is easy to see that the
polynomial $\,x^{n}+p\,$ is $\mathbb{Q}$-irreducible for any prime number
$p\geq 2$ and any $n\geq 1$.

######  Definition 2.4.

The _finite spectral structure_ of $P(\lambda)$ refers to any of the following
equivalent (and easily inter-convertible) collections of data:

  1. (a)

the set of all distinct irreducible divisors of $P(\lambda)$, each equipped
with their partial multiplicity sequence,

  2. (b)

the multiset of all elementary divisors of $P(\lambda)$, together with the
number $\mathop{\rm rank}P$,

  3. (c)

the multiset of all invariant polynomials of $P(\lambda)$, including the
trivial ones.

(Recall that a multiset is like a set, but with repetitions allowed, i.e., a
“set with multiplicities” [10].)

######  Remark 2.5.

Note that the rank of a matrix polynomial is encoded in each partial
multiplicity sequence by its length.

Some regular matrix polynomials have structure that is not completely captured
by their finite spectral structure alone. To get the full story for these
matrix polynomials, it is also necessary to include their “spectral structure
at $\infty$”. For this, some additional terminology is needed. The _grade_ of
a matrix polynomial $P(\lambda)$ is a natural number $g$ such that

$P(\lambda)\,=\,P_{0}+P_{1}\lambda+\dotsb+P_{g}\lambda^{g}\,,$

with each $P_{j}\in\mathbb{F}^{n\times n}$. Note, however, that unlike in the
definition of the degree $d$ of $P(\lambda)$, there is no requirement here for
the leading coefficient $P_{g}$ to be nonzero. Thus we see that $g\geq d$
always holds, no matter what the choice of grade might be. And we emphasize
that, in contrast with degree, grade is indeed a choice, although a very
common choice is for $g$ to be taken to be equal to $d$. The _grade $g$
reversal_ of $P(\lambda)$ is the matrix polynomial

$(\textstyle{\mathop{\rm
rev}_{g}}P)(\lambda)\,:=\;\lambda^{g}P(\nicefrac{{1}}{{\lambda}}),$

and $P(\lambda)$ has an _eigenvalue at infinity_ if $(\mathop{\rm
rev}_{g}P)(\lambda)$ has an eigenvalue at zero. Moreover, the partial
multiplicity sequence of the eigenvalue at infinity for $P(\lambda)$ is, by
definition, identical to the partial multiplicity sequence of the eigenvalue
zero for $(\mathop{\rm rev}_{g}P)(\lambda)$. We will use ${\cal P}\\!{\cal
M}(P,\infty)$ as temporary notation for the partial multiplicity sequence of
$P$ at $\infty$, so that this definition can be expressed as

${\cal P}\\!{\cal M}(P,\infty)\,:=\;{\cal P}\\!{\cal M}(\textstyle{\mathop{\rm
rev}_{g}}P,\lambda)\,.$

However, later in Section 4 we will have reason to change this notation to
something that is more consistent with the notation in (2.2), and also works
more smoothly with Möbius transformations and their properties.

######  Definition 2.6.

The _infinite spectral structure_ of $P(\lambda)$ refers to the eigenvalue at
infinity (if it exists), together with its partial multiplicity sequence.

The relationship of grade to degree (e.g., whether $g=d$ or $g>d$) is
reflected in the infinite spectral structure, in particular in the first
partial multiplicity at $\infty$. Note that some of the following result
appeared previously in [3, Lemma 2.17], but without proof.

######  Lemma 2.7.

Suppose $P(\lambda)$ is any $m\times n$ matrix polynomial over a field
$\,\mathbb{F}$, with rank $r$, degree $d$, and grade $g$. Let
$(\alpha_{1},\alpha_{2},\dotsc,\alpha_{r})$ with
$0\leq\alpha_{1}\leq\alpha_{2}\leq\dotsb\leq\alpha_{r}$ be the partial
multiplicity sequence of $P$ at $\infty$. Then

$\alpha_{1}\,=\,g-d\,,$ (2.4)

and hence $\,g=d\,$ if and only if $\,\alpha_{1}=0$. (Equivalently, $g>d$ if
and only if $\alpha_{1}>0$.) Furthermore, suppose $\widetilde{P}(\lambda)$ is
an $m\times n$ matrix polynomial that is entry-wise identical to $P(\lambda)$,
but its grade has been chosen to be equal to its degree $d$. Then the partial
multiplicity sequences at $\infty$ of $P(\lambda)$ and
$\widetilde{P}(\lambda)$ are related by a constant “shift” of $g-d$, that is,

${\cal P}\\!{\cal M}(P,\infty)\;=\;{\cal P}\\!{\cal
M}(\widetilde{P},\infty)\,+\,(g-d)\cdot(1,1,\dotsc,1)\,.$ (2.5)

###### Proof.

Begin by expressing
$P(\lambda)=P_{g}\lambda^{g}+\dotsb+P_{d}\lambda^{d}+\dotsb+P_{1}\lambda+P_{0}$,
so that $\widetilde{P}(\lambda)=P_{d}\lambda^{d}+\dotsb+P_{1}\lambda+P_{0}$,
with $P_{d}\neq 0$ and $P_{j}=0$ for the $g-d$ leading coefficients with
$j=d+1,\dotsc,g$. Then the reversals of $P$ and $\widetilde{P}$ are related by

$\textstyle{\mathop{\rm
rev}_{g}}P\,=\,\lambda^{g}P\bigl{(}\nicefrac{{1}}{{\lambda}}\bigr{)}\,=\,\lambda^{g-d}\lambda^{d}P\bigl{(}\nicefrac{{1}}{{\lambda}}\bigr{)}\,=\,\lambda^{g-d}\bigl{(}\textstyle{\mathop{\rm
rev}_{d}}\widetilde{P}\bigr{)}\,.$ (2.6)

Note that the constant term of $\mathop{\rm rev}_{d}\widetilde{P}$ is the
_nonzero_ matrix $P_{d}$.

Next observe that for any constant $\mu_{0}\in\mathbb{F}$ and any matrix
polynomial $Q(\lambda)$ over $\mathbb{F}$, the number of initial _zero_
partial multiplicities in the sequence ${\cal P}\\!{\cal M}(Q,\chi)$ with
$\chi(\lambda)=\lambda-\mu_{0}$ is equal to $\mathop{\rm rank}Q(\mu_{0})$.
This can be easily seen from the Smith form

$U(\lambda)Q(\lambda)V(\lambda)\;=\;\widehat{S}(\lambda)\,$ (2.7)

by evaluating (2.7) at $\mu_{0}$, then computing ranks to get $\mathop{\rm
rank}\bigl{(}Q(\mu_{0})\bigr{)}\,=\,\mathop{\rm
rank}\bigl{(}\widehat{S}(\mu_{0})\bigr{)}$ . But any diagonal entry of
$\widehat{S}(\lambda)$ corresponding to a nonzero partial multiplicity of
$\lambda-\mu_{0}$ will be zeroed out in $\widehat{S}(\mu_{0})$, so the
remaining nonzero diagonal entries of $\widehat{S}(\mu_{0})$, there are
$\mathop{\rm rank}\widehat{S}(\mu_{0})=\mathop{\rm rank}Q(\mu_{0})$ many of
them, will count the zero partial multiplicities of $\lambda-\mu_{0}$ for $Q$.
Applying this to $Q(\lambda)=\mathop{\rm rev}_{d}\widetilde{P}$, we see that

$\displaystyle(\text{no. of zero partial multiplicities for $\widetilde{P}$ at
$\infty$})$ $\displaystyle\;=\;(\text{no.\ of zero partial multiplicities for
$\textstyle{\mathop{\rm rev}_{d}}\widetilde{P}$ at $(\lambda-0)$})$
$\displaystyle\;=\;\mathop{\rm rank}\bigl{(}\textstyle{\mathop{\rm
rev}_{d}}\widetilde{P}(0)\bigr{)}\;=\;\mathop{\rm rank}P_{d}\,>\,0\,,$

since $P_{d}$ is nonzero. Thus ${\cal P}\\!{\cal
M}(\widetilde{P},\infty):={\cal P}\\!{\cal M}\bigl{(}\textstyle{\mathop{\rm
rev}_{d}}\widetilde{P},(\lambda-0)\bigr{)}=(0,\dotsc)$. Hence in the Smith
form $\widetilde{S}(\lambda)$ for $\mathop{\rm rev}_{d}\widetilde{P}$, i.e.,
$\widetilde{S}(\lambda)=\mathop{\rm
diag}(\widetilde{s}_{1}(\lambda),\widetilde{s}_{2}(\lambda),\dotsc)$, we see
that $\widetilde{s}_{1}(\lambda)$ must be coprime to $\lambda$. Now from (2.6)
it follows that the Smith form $S(\lambda)$ for $\mathop{\rm rev}_{g}P$ is
related to $\widetilde{S}(\lambda)$ by

$S(\lambda)\;=\;\lambda^{g-d}\mkern 1.0mu\widetilde{S}(\lambda)\,.$

Hence we can immmediately conclude that $\alpha_{1}=g-d$, and that the “shift”
relation in (2.5) holds. ∎

The first major result in this paper will be concerned with a special class of
regular matrix polynomials, as in the following definition.

######  Definition 2.8.

Regular matrix polynomials that have _no_ infinite spectral structure at all
will be referred to as _strictly regular_.

For a regular $n\times n$ matrix polynomial $P(\lambda)$ of grade $g$, being
strictly regular is equivalent to the leading coefficient $P_{g}$ being
_nonsingular_ (and hence necessarily also that $g=d$), or equivalently to
$\deg\bigl{(}\mathop{\rm det}P(\lambda)\bigr{)}$ being equal to $gn$.

######  Definition 2.9.

The _complete spectral data_ of a matrix polynomial $P(\lambda)$ is the
combination of the finite and infinite spectral structures. Two regular matrix
polynomials with the same complete spectral data are said to be _spectrally
equivalent_.

The notion of spectral equivalence was introduced in [3] as a way to compare
matrix polynomials, both regular and singular, even if they have different
sizes or degrees. Although the definition given in [3] is quite different than
Definition 2.9, it was shown in [3] that for regular polynomials being
spectrally equivalent is the same as having the same complete spectral data.
Note that in [19], having the same complete spectral data is termed _strongly
equivalent_.

It is important to keep firmly in mind the contrast between unimodular
equivalence and spectral equivalence. Unimodular equivalence preserves all
finite spectral structure, but carries with it the unfortunate possibility of
altering any infinite spectral structure that might be present. We will see a
concrete illustration of this phenomenon in Example 4.8, but a more detailed
discussion of the possible effects of unimodular transformations on infinite
spectral structure can be found in [3, Sect. 4.3]. In this paper the ultimate
aim is to produce quasi-triangularizations that are spectrally equivalent to
the given matrix polynomial, and not just unimodularly equivalent.

The following theorem, dubbed the Index Sum Theorem in [3], appeared for the
first time in [21] for the complex field, and in [16] and [17] for the real
field. This theorem describes the fundamental relationship between the grade,
rank, and structural data (elementary divisors together with minimal indices)
of _any_ matrix polynomial, and was recently extended to arbitrary fields in
[3]. Here we state the result only for regular matrix polynomials over an
arbitrary field; the result in its full generality can be found in [3]. For
more on the history of this theorem, as well as its connection to other
fundamental results, see [1].

######  Theorem 2.10 (Index Sum Theorem for Regular Matrix Polynomials).

Let $P(\lambda)$ be a regular $n\times n$ matrix polynomial of degree $d$ and
grade $g$ having the the complete spectral data:

  * •

invariant polynomials $p_{j}(\lambda)$ of degrees $\delta_{j}$, for
$j=1,\dots,n$,

  * •

infinite partial multiplicities $\gamma_{1},\dots,\gamma_{n}$,

where some of the degrees or partial multiplicities can be zero. Then the
index sum $\sigma$ satisfies the relation

$\sigma\,:=\;\sum_{j=1}^{n}\delta_{j}\,+\,\sum_{j=1}^{n}\gamma_{j}\;=\;gn\,.$
(2.8)

If $P(\lambda)$ is strictly regular, so that all of the $\gamma_{i}$’s are
zero and $g=d$, then (2.8) simplifies to just the relation

$\sigma\;=\;\sum_{j=1}^{n}\delta_{j}\;=\;dn\,.$ (2.9)

The index sum theorem plays a key role in the following theorem, which is a
very special case of a much more general result in [4]. The corollary
immediately following it will be used at a key moment in the proof of our
first main result, Theorem 3.1.

######  Theorem 2.11 (Fundamental Realization Theorem for Strictly Regular
Matrix Polynomials).

Let $\,\mathbb{F}$ be an arbitrary field, and $n,d\in\mathbb{N}^{+}$ be given
positive integers. Consider a collection of $n$ monic polynomials
$p_{1}(\lambda),\dots,p_{n}(\lambda)$ with coefficients in $\,\mathbb{F}$ and
respective degrees $\delta_{1},\dots,\delta_{n}$, such that $p_{j}(\lambda)$
divides $p_{j+1}(\lambda)$ for $j=1,\dots,n-1$. Then there exists a strictly
regular $n\times n$ matrix polynomial $P(\lambda)$ over $\,\mathbb{F}$ with
degree $d$ and invariant polynomials $p_{1}(\lambda),\dots,p_{n}(\lambda)$, if
and only if (2.9) holds.

######  Corollary 2.12.

Let $\,\mathbb{F}$ be an arbitrary field, and $Q(\lambda)$ a regular $n\times
n$ polynomial matrix over $\,\mathbb{F}$. Suppose that
$\sigma:=\deg\bigl{(}\mathop{\rm det}Q(\lambda)\bigr{)}$ is divisible by $n$,
in particular that $\sigma=dn$. Then there is a strictly regular $n\times n$
matrix polynomial $P(\lambda)$ over $\,\mathbb{F}$ of degree $d$ that is
unimodularly equivalent to $Q(\lambda)$.

###### Proof.

Let $q_{1}(\lambda),\dots,q_{n}(\lambda)$ be the invariant polynomials of
$Q(\lambda)$, with degrees $\delta_{1},\dots,\delta_{n}$, respectively. Then
from the Smith form of $Q(\lambda)$ we know that
$\sum_{j=1}^{n}\delta_{j}=\sigma=dn$, i.e., that (2.9) holds. Thus by Theorem
2.11 there exists a strictly regular $n\times n$ matrix polynomial
$P(\lambda)$ over $\,\mathbb{F}$ with degree $d$ and the same invariant
polynomials as $Q(\lambda)$. Now since $P(\lambda)$ and $Q(\lambda)$ have the
same Smith form, they must be unimodularly equivalent. ∎

An important concept, used in [4] and [19] for handling regular matrix
polynomials that have nontrivial infinite spectral structure, is that of
Möbius transformations of matrix polynomials. These transformations and their
properties were studied in [12], and will be important for the results in
Section 4.

######  Definition 2.13 (Möbius transformations of matrix polynomials).

Let $P(\lambda)$ be a matrix polynomial of grade $g$ over the field
$\mathbb{F}$, and suppose $A=\bigl{[}\begin{smallmatrix}a&b\\\
c&d\end{smallmatrix}\bigr{]}\in\mathbb{F}^{2\times 2}$ is nonsingular. The
matrix polynomial

$\mathbf{M}_{A}(P)(\lambda)\,:=\;(c\lambda+d)^{g}P\left(\frac{a\lambda+b}{c\lambda+d}\right)$
(2.10)

is the _Möbius transformation_ of $P(\lambda)$ with respect to $A$.

######  Example 2.14.

Note that the grade $g$ reversal operation is an example of a Möbius
transformation, specifically $\,\mathop{\rm rev}_{g}P=\mathbf{M}_{R}(P)\,$ for
$\,R=\bigl{[}\begin{smallmatrix}0&1\\\ 1&0\end{smallmatrix}\bigr{]}$.

For conceptual clarity, it is important to keep in mind that for any fixed
field $\mathbb{F}$ and grade $g$, the formula in (2.10) actually defines a
whole _family_ of transformations, one for each matrix size $m\times n$. Once
one has fixed the underlying field $\mathbb{F}$, grade $g$, input matrix size
$m\times n$, and matrix $A$, then it is known [12] that the Möbius
transformation $\mathbf{M}_{A}$ defines a _bijection_ on the set of all
$m\times n$, grade $g$ matrix polynomials over $\mathbb{F}$. However, even by
staying within the confines of one of these bijections, the transformation
$\mathbf{M}_{A}(P)$ does _not_ in general preserve the degree of the input
$P$; degree may increase, decrease, or remain unchanged [12]. This lack of
degree preservation happens even for the simplest size matrix polynomials,
i.e., for scalar ($1\times 1$) polynomials. However, for scalar polynomials
the following lemma describes one simple scenario, important for this paper,
where degree preservation by Möbius transformations is guaranteed. The proof
of this result will be postponed until Section 4.1, where a number of results
about the properties of Möbius transformations and their effect on partial
multiplicity sequences will be developed.

######  Lemma 2.15.

Suppose $\mathbb{F}$ is an arbitrary field, and $\chi(\lambda)$ is any
$\mathbb{F}$-irreducible scalar polynomial with $\deg\chi\geq 2$. Let
$\mathbf{M}_{A}$ be the Möbius transformation associated with any
$A=\bigl{[}\begin{smallmatrix}a&b\\\ c&d\end{smallmatrix}\bigr{]}\in
GL(2,\mathbb{F})$. Then with $\mathop{\rm grade}(\chi)$ taken to be equal to
$\deg(\chi)$, the transformation $\mathbf{M}_{A}$ preserves both the degree
and the $\mathbb{F}$-irreducibility of $\chi$. That is, $\mathbf{M}_{A}(\chi)$
is $\mathbb{F}$-irreducible, and
$\,\deg\bigl{(}\mathbf{M}_{A}(\chi)\bigr{)}=\deg(\chi)$.

##  3 Quasi-triangular realization of finite spectral data

Our first result is the construction of a quasi-triangular realization of a
given list of finite spectral data, with a choice of degree that is compatible
with the index sum theorem.

######  Theorem 3.1 (Quasi-Triangular Realization: Strictly Regular Case).

Suppose a list of $m$ nonconstant monic polynomials
$s_{1}(\lambda),\dots,s_{m}(\lambda)$ over an arbitrary field $\,\mathbb{F}$
is given, satisfying the divisibility chain condition
$s_{1}(\lambda)\,|\,s_{2}(\lambda)\,|\,\dotsb\,|\,s_{m}(\lambda)$. Let
$\sigma:=\sum_{i=1}^{m}\deg\bigl{(}s_{i}(\lambda)\bigr{)}$, and define $k$ to
be the maximum degree among all of the $\mathbb{F}$-irreducible factors of the
polynomials $s_{i}(\lambda)$ for $i=1,\dotsc,m$. Then for any choice of
nonzero $d,n\in\mathbb{N}$ such that $n\geq m$ and $dn=\sigma$, there exists
an $n\times n$, degree $d$, strictly regular matrix polynomial $Q(\lambda)$
over $\mathbb{F}$ that is $k$-quasi-triangular, and has exactly the given
polynomials $s_{1}(\lambda),\dots,s_{m}(\lambda)$ as its nontrivial invariant
polynomials, together with $n-m$ trivial invariant polynomials. In addition,
$Q(\lambda)$ can always be chosen so that the degree of every entry in any
off-diagonal block of $Q(\lambda)$ is strictly less than $d$.

Note that the two conditions in this theorem, i.e., that $n\geq m$ and
$dn=\sigma$, are both necessary conditions for _any_ strictly regular
realization of the given data, whether that realization is quasi-triangular or
not. The restriction $n\geq m$ simply says that the realization (and its Smith
form) needs to be big enough to accommodate all of the nontrivial invariant
polynomials. The condition $dn=\sigma$ is simply the Index Sum Theorem in the
form (2.9) required of any strictly regular realization of data with the given
$\sigma$.

Now before embarking on the extensive technical details of the proof of
Theorem 3.1, which will occupy our attention for the rest of Section 3, it
will be helpful to give a brief idea of the overall strategy of the argument.
The first step in our process of quasi-triangular realization is to construct
the Smith form corresponding to the given data and the choice of $n$, i.e.,

$S(\lambda)=I_{(n-m)\times(n-m)}\oplus\mathop{\rm
diag}\\{s_{1}(\lambda),s_{2}(\lambda),\dotsc,s_{m}(\lambda)\\}\,.$

We take this as our starting point, and begin changing $S(\lambda)$ by
unimodular transformations, “un-diagonalizing” it and slowly turning it into
the desired quasi-triangularization. The first phase of this un-
diagonalization of the Smith form aims to shift irreducible factors around on
the diagonal, in such a way as to try to make the degrees of all of the
diagonal entries as close to the target degree $d$ as possible. This is a
proof idea pioneered in [8], and developed further in [19]. Although the
diagonal form is sacrificed, in this first stage at least upper triangularity
is maintained.

Now for some collections of spectral data, this phase may succeed in making
the diagonal entries all have exactly the target degree $d$; in this case a
triangularization is obtained. As shown in [19], this can always be achieved
when the underlying field is algebraically closed. However, for arbitrary
fields we have to be satisfied with something less. The best that can be
achieved in general is to rearrange the irreducible factors along the diagonal
so that no two diagonal entries differ in degree by more than $k$ (the maximum
degree among all of the irreducible divisors of the given spectral data), and
so that the vector of diagonal entries can be grouped into contiguous blocks
$D_{1},\dotsc,D_{\ell}$ for some $\ell\leq n$, each of size at most $k$, where
the _average_ degree of the entries in each $D_{j}$ is exactly the target
degree $d$.

In the second phase of construction, the upper triangular matrix attained so
far is partitioned into blocks, with square (upper triangular) blocks down the
diagonal that correspond to the contiguous blocks $D_{j}$ of diagonal entries
just mentioned. Each of these diagonal blocks is now “un-triangularized” so
that it has exactly degree $d$. We now have a quasi-triangular realization in
which all of the diagonal blocks have degree $d$, but the off-diagonal blocks
have been left uncontrolled, and may still have degree larger than $d$.

The final step, then, is to visit each of the off-diagonal blocks in a “sweep
by super-diagonals pattern”, using matrix polynomial division to force the
degree of all of the off-diagonal blocks to be strictly less than $d$. This
completes the construction of a $k$-quasi-triangular realization of degree $d$
for the given spectral data.

######  Example 3.2.

Throughout this paper, we will keep returning to a single illustrative
example, continually developing it as we go. To start, consider the finite
spectral data over the two-element field $\mathbb{F}=\mathbb{Z}_{2}$,
consisting of the invariant polynomials

$s_{1}(\lambda)=\phi\psi\,,\quad s_{2}(\lambda)=\chi\phi\psi\,,\quad
s_{3}(\lambda)=\chi^{2}\phi\psi^{2}\,,\quad
s_{4}(\lambda)=\chi^{3}\phi\psi^{2}\,,\;\text{ and
}\;s_{5}(\lambda)=\chi^{3}\phi^{3}\psi^{4}\,,$

where $\chi(\lambda)=\lambda^{4}+\lambda^{3}+1$,
$\phi(\lambda)=\lambda^{2}+\lambda+1$, and $\psi(\lambda)=\lambda$ are
$\mathbb{F}$-irreducible. The sum of the degrees of these invariant
polynomials is $\sigma=60$, so we may choose the target degree to be $d=10$.
As a consequence, the size of the realization must be $6\times 6$, and so the
Smith form for our given data is

$S(\lambda)=\mathop{\rm
diag}\\{1,s_{1}(\lambda),s_{2}(\lambda),s_{3}(\lambda),s_{4}(\lambda),s_{5}(\lambda)\\}\,.$

The irreducible divisors together with their associated partial multiplicity
sequences are

$\displaystyle{\cal P}\\!{\cal M}_{\text{given}}(\chi)$
$\displaystyle\,=\,(0,0,1,2,3,3)$ $\displaystyle{\cal P}\\!{\cal
M}_{\text{given}}(\phi)$ $\displaystyle\,=\,(0,1,1,1,1,3)$ $\displaystyle{\cal
P}\\!{\cal M}_{\text{given}}(\psi)$ $\displaystyle\,=\,(0,1,1,2,2,4)\,,$

which provides an alternative way to present the given finite spectral data.

###  3.1 Coprime partitions, factor-counting vectors, and the unimodular
transfer lemma

In this section we develop the tools needed to implement the first phase of
the construction of a quasi-triangular realization from given finite spectral
data. That is, we will see how it is possible to rearrange irreducible factors
along the diagonal via unimodular equivalence, while at the same time
maintaining upper triangularity. However, before we present these tools, some
additional concepts and terminology will be required.

Let ${\cal M}$ be the multiset of all of the $\mathbb{F}$-irreducible factors
of a scalar polynomial $p(\lambda)$. A partition of ${\cal M}$ into a disjoint
union ${\cal M}={\cal F}\sqcup{\cal G}$ of multisets ${\cal F}$ and ${\cal G}$
is called a _coprime partition_ if every $f\in{\cal F}$ is coprime to every
$g\in{\cal G}$. This is equivalent to saying that there is no irreducible
factor of $p$ that appears in both ${\cal F}$ and ${\cal G}$. Given such a
coprime partition, we can uniquely factor $p(\lambda)$ into

$p(\lambda)\;=\;p_{{}_{\scriptstyle{\cal F}}}(\lambda)\cdot
p_{{}_{\scriptstyle{\cal G}}}(\lambda)\,,$

where $p_{{}_{\scriptstyle{\cal F}}}(\lambda)$ denotes the product of all of
the $\mathbb{F}$-irreducible factors in $p(\lambda)$ from $\mathcal{F}$, and
$p_{{}_{\scriptstyle{\cal G}}}(\lambda)$ denotes the product of all of the
$\mathbb{F}$-irreducible factors in $p(\lambda)$ from $\mathcal{G}$. We also
denote by $|p(\lambda)|_{{}_{\scriptstyle{\cal F}}}$ the total _number_ of
$\mathbb{F}$-irreducible factors from $\mathcal{F}$ in $p(\lambda)$, with a
similar meaning for $|p(\lambda)|_{{}_{\scriptstyle{\cal G}}}$. Note that
$|p_{{}_{\scriptstyle{\cal F}}}(\lambda)|_{{}_{\scriptstyle{\cal
F}}}=|p(\lambda)|_{{}_{\scriptstyle{\cal F}}}$.

If $\mathbf{v}(\lambda)$ is a polynomial $n$-vector and ${\cal F}\sqcup{\cal
G}$ is a coprime partition of the multiset of all of the
$\mathbb{F}$-irreducible factors of all of the entries of
$\mathbf{v}(\lambda)$, then the integer vector

$|\mathbf{v}(\lambda)|_{{}_{\scriptstyle{\cal
F}}}\,:=\;\bigl{(}|v_{1}(\lambda)|_{{}_{\scriptstyle{\cal
F}}},\dotsc,|v_{n}(\lambda)|_{{}_{\scriptstyle{\cal F}}}\bigr{)}$

is the _factor-counting vector_ of $\mathbf{v}(\lambda)$ with respect to
${\cal F}$. Also useful is the integer _degree vector_

$\deg\mathbf{v}:=\,\bigl{(}\deg v_{1}(\lambda),\dotsc,\deg
v_{n}(\lambda)\bigr{)}\,.$

Finally, given an $n\times n$ matrix polynomial $P(\lambda)$, its main
diagonal vector $\mathbf{p}(\lambda):=\mathop{\rm diag}P(\lambda)$, and a
coprime partition $\mathcal{F}\sqcup\mathcal{G}$ of the multiset $\mathcal{M}$
of all of the $\mathbb{F}$-irreducible factors of the entries of
$\mathbf{p}(\lambda)$, we define the _diagonal factor-counting vector_ of
$P(\lambda)$ with respect to $\mathcal{F}$ to be the integer vector

$\mathbf{d}_{{}_{\scriptstyle{\cal
F}}}(P)\,:=\;|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}}}\,.$ (3.1)

With these concepts, terminology, and notation in hand, we can now describe
and develop the tool for transferring irreducible factors along the diagonal
of an upper triangular matrix polynomial.

######  Lemma 3.3 ($2\times 2$ Unimodular Transfer Lemma).

Let

$T(\lambda)\,=\,\left[\begin{array}[]{cc}p(\lambda)&q(\lambda)\\\
0&r(\lambda)\end{array}\right]$

be a regular $2\times 2$ upper triangular matrix polynomial over an arbitrary
field $\mathbb{F}$. Let $\mathcal{F}\sqcup\mathcal{G}$ be any coprime
partition of the multiset of all of the $\mathbb{F}$-irreducible factors in
the product $p(\lambda)r(\lambda)$. Let $m=|p|_{{}_{\scriptstyle{\cal F}}}$
and $n=|r|_{{}_{\scriptstyle{\cal F}}}$ so that
$\mathbf{d}_{{}_{\scriptstyle{\cal F}}}(T)=(m,n)$. Then for any
$\alpha,\beta\in\mathbb{N}$ such that $\alpha+\beta=m+n$ and $\mathop{\rm
min}\\{m,n\\}\leq\alpha,\beta\leq\mathop{\rm max}\\{m,n\\}$, there exists a
regular upper triangular matrix polynomial $\widetilde{T}(\lambda)$ of the
form

$\widetilde{T}(\lambda)=\left[\begin{array}[]{cc}\widetilde{p}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\cdot p_{{}_{\scriptstyle{\cal
G}}}(\lambda)&\widetilde{q}(\lambda)\\\ 0&\widetilde{r}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\cdot r_{{}_{\scriptstyle{\cal G}}}(\lambda)\end{array}\right]$
(3.2)

with $\mathbf{d}_{{}_{\scriptstyle{\cal F}}}(\widetilde{T})=(\alpha,\beta)$,
such that $T(\lambda)$ is unimodularly equivalent to $\widetilde{T}(\lambda)$.

###### Proof.

If $m=n$ there is nothing to do, so assume that $m\neq n$. Let
$g(\lambda):=\gcd\bigl{\\{}p(\lambda),q(\lambda),r(\lambda)\bigr{\\}}$, and
factor

$p(\lambda)=g(\lambda)\cdot\widehat{p}(\lambda)\mbox{$\quad\mbox{ and
}\quad$}r(\lambda)=g(\lambda)\cdot\widehat{r}(\lambda)\,.$ (3.3)

Then the Smith form of $T(\lambda)$ is $\mathop{\rm
diag}\\{g(\lambda),g(\lambda)\,\widehat{p}(\lambda)\,\widehat{r}(\lambda)\\}$,
so any $\widetilde{T}$ as in (3.2) that we construct that has this Smith form
will be unimodularly equivalent to $T$. Here is how to construct many such
$\widetilde{T}$’s.

Begin by refining the factorizations of $p$ and $r$ in (3.3), in a way that is
compatible with the given coprime partition ${\cal F}\sqcup{\cal G}$:

$\displaystyle p(\lambda)=g(\lambda)\cdot\widehat{p}(\lambda)$
$\displaystyle=\bigl{(}g_{{}_{\scriptstyle{\cal
F}}}(\lambda)g_{{}_{\scriptstyle{\cal
G}}}(\lambda)\bigr{)}\cdot\bigl{(}\widehat{p}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\widehat{p}_{{}_{\scriptstyle{\cal G}}}(\lambda)\bigr{)}$
$\displaystyle=\bigl{(}g_{{}_{\scriptstyle{\cal
F}}}(\lambda)\widehat{p}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\bigr{)}\cdot\bigl{(}g_{{}_{\scriptstyle{\cal
G}}}(\lambda)\widehat{p}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\bigr{)}=p_{{}_{\scriptstyle{\cal F}}}(\lambda)\cdot
p_{{}_{\scriptstyle{\cal G}}}(\lambda)$ (3.4)

and

$\displaystyle r(\lambda)=g(\lambda)\cdot\widehat{r}(\lambda)$
$\displaystyle=\bigl{(}g_{{}_{\scriptstyle{\cal
F}}}(\lambda)g_{{}_{\scriptstyle{\cal
G}}}(\lambda)\bigr{)}\cdot\bigl{(}\widehat{r}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal G}}}(\lambda)\bigr{)}$
$\displaystyle=\bigl{(}g_{{}_{\scriptstyle{\cal
F}}}(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\bigr{)}\cdot\bigl{(}g_{{}_{\scriptstyle{\cal
G}}}(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\bigr{)}=r_{{}_{\scriptstyle{\cal F}}}(\lambda)\cdot
r_{{}_{\scriptstyle{\cal G}}}(\lambda).$ (3.5)

Since we wish to leave $p_{{}_{\scriptstyle{\cal G}}}(\lambda)$ and
$r_{{}_{\scriptstyle{\cal G}}}(\lambda)$ completely undisturbed in going from
$T$ to $\widetilde{T}$, and also to have $g(\lambda)$ present in both diagonal
entries of $\widetilde{T}$ in order to preserve the Smith form, this means
that the only room for maneuvering is with the factors in
$\widehat{p}_{{}_{\scriptstyle{\cal F}}}(\lambda)$ and
$\widehat{r}_{{}_{\scriptstyle{\cal F}}}(\lambda)$. So let $a(\lambda)$ and
$b(\lambda)$ be _any_ two polynomials (including possibly $a\equiv 1$ or
$b\equiv 1$) over $\mathbb{F}$ such that

$a(\lambda)\cdot b(\lambda)\,=\,\widehat{p}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\cdot\widehat{r}_{{}_{\scriptstyle{\cal F}}}(\lambda)\,,$ (3.6)

and consider the polynomial matrix

$\widetilde{T}(\lambda)\,=\,\left[\begin{array}[]{cc}g_{{}_{\scriptstyle{\cal
F}}}(\lambda)a(\lambda)\cdot p_{{}_{\scriptstyle{\cal
G}}}(\lambda)&g(\lambda)\\\ 0&g_{{}_{\scriptstyle{\cal
F}}}(\lambda)b(\lambda)\cdot r_{{}_{\scriptstyle{\cal
G}}}(\lambda)\end{array}\right]\,=\,\left[\begin{array}[]{cc}g(\lambda)\cdot
a(\lambda)\widehat{p}_{{}_{\scriptstyle{\cal G}}}(\lambda)&g(\lambda)\\\
0&g(\lambda)\cdot b(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\end{array}\right]\,,$ (3.7)

of the form in (3.2) with $\widetilde{p}_{{}_{\scriptstyle{\cal
F}}}(\lambda)=g_{{}_{\scriptstyle{\cal F}}}(\lambda)a(\lambda)$,
$\widetilde{q}(\lambda)=g(\lambda)$, and $\widetilde{r}_{{}_{\scriptstyle{\cal
F}}}(\lambda)=g_{{}_{\scriptstyle{\cal F}}}(\lambda)b(\lambda)$. Then the
$\gcd$ of the entries of $\widetilde{T}$ is easily seen to be $g(\lambda)$, so
the Smith form of $\widetilde{T}(\lambda)$ is

$\displaystyle\mathop{\rm
diag}\left\\{g(\lambda),\,g(\lambda)\bigl{[}a(\lambda)b(\lambda)\bigr{]}\\!\cdot\bigl{[}\widehat{p}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\bigr{]}\right\\}$ $\displaystyle=\,\mathop{\rm
diag}\left\\{g(\lambda),\,g(\lambda)\bigl{[}\widehat{p}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal
F}}}(\lambda)\bigr{]}\\!\cdot\bigl{[}\widehat{p}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\widehat{r}_{{}_{\scriptstyle{\cal
G}}}(\lambda)\bigr{]}\right\\}$ $\displaystyle=\,\mathop{\rm
diag}\left\\{g(\lambda),\,g(\lambda)\widehat{p}(\lambda)\widehat{r}(\lambda)\right\\}\,,$

which is identical to the Smith form of $T(\lambda)$. Thus for any choice of
$a(\lambda)$ and $b(\lambda)$ in (3.6), we have $\widetilde{T}\sim T$. Letting
$\delta=\lvert\,g(\lambda)\,\rvert_{{}_{\scriptstyle{\cal F}}}$, we see that
the diagonal factor-counting vector $\mathbf{d}_{{}_{\scriptstyle{\cal
F}}}(\widetilde{T})$ for $\widetilde{T}(\lambda)$ in (3.7) can be
$(\alpha,\beta)$ for any $\alpha+\beta=m+n$ with $\delta\leq\alpha,\beta\leq
m+n-\delta$. Since

$\delta\,\leq\,\mathop{\rm min}(m,n)\,\leq\,\mathop{\rm
max}(m,n)\,\leq\,m+n-\delta\,,$

any $(\alpha,\beta)$ pair given in the statement of the lemma is always
achievable for $\mathbf{d}_{{}_{\scriptstyle{\cal F}}}(\widetilde{T})$. ∎

This lemma for $2\times 2$ triangular matrices can now be used on a triangular
matrix of any size to “transfer” irreducible factors belonging to a family
$\mathcal{F}$ between any two _adjacent_ diagonal entries, while maintaining
triangularity, and without disturbing any of the factors that belong to the
complementary family $\mathcal{G}$. This is done by embedding the $2\times 2$
unimodular transformations provided by Lemma 3.3 into larger identity
matrices.

######  Corollary 3.4.

Let $P(\lambda)$ be a regular $n\times n$ upper triangular polynomial matrix,
and let ${\cal M}={\cal F}\sqcup{\cal G}$ be a coprime partition of the
multiset of all irreducible factors of the diagonal entries of $P(\lambda)$.
Consider any $2\times 2$ principal submatrix of $P(\lambda)$ with _adjacent_
diagonal entries, i.e.,

$T(\lambda)=\left[\begin{array}[]{cc}p_{ii}(\lambda)&p_{ij}(\lambda)\\\
0&p_{jj}(\lambda)\end{array}\right]\quad\text{ with }\quad j=i+1\,,$

and let $\mathbf{d}_{{}_{\scriptstyle{\cal F}}}(T)=(m,n)$. Then for any
integers $\alpha,\beta$ such that $\alpha+\beta=m+n$ and $\mathop{\rm
min}\\{m,n\\}\leq\alpha,\beta\leq\mathop{\rm max}\\{m,n\\}$, there exists a
regular upper triangular matrix polynomial $\widetilde{P}(\lambda)$ such that

  * •

$\widetilde{p}_{ii}(\lambda)=[\widetilde{p}_{ii}(\lambda)]_{{}_{\scriptstyle{\cal
F}}}\cdot p_{{}_{\scriptstyle{\cal G}}}(\lambda)$ with
$\lvert\,\widetilde{p}_{ii}(\lambda)\,\rvert_{{}_{\scriptstyle{\cal
F}}}=\alpha$ ,

  * •

$\widetilde{p}_{jj}(\lambda)=[\widetilde{p}_{jj}(\lambda)]_{{}_{\scriptstyle{\cal
F}}}\cdot p_{{}_{\scriptstyle{\cal G}}}(\lambda)$ with
$\lvert\,\widetilde{p}_{ii}(\lambda)\,\rvert_{{}_{\scriptstyle{\cal
F}}}=\beta$ ,

  * •

$\widetilde{p}_{kk}(\lambda)=p_{kk}(\lambda)$ for all $k\neq i,j$ ,

  * •

$\widetilde{P}(\lambda)$ is unimodularly equivalent to $P(\lambda)$.

###### Proof.

Apply Lemma 3.3 to the submatrix $T$ to get two $2\times 2$ unimodular
matrices $E(\lambda)$ and $F(\lambda)$ such that

$E(\lambda)T(\lambda)F(\lambda)=\left[\begin{array}[]{cc}[\widetilde{p}_{ii}(\lambda)]_{{}_{\scriptstyle{\cal
F}}}\cdot p_{{}_{\scriptstyle{\cal
G}}}(\lambda)&\widetilde{p}_{ij}(\lambda)\\\
0&[\widetilde{p}_{jj}(\lambda)]_{{}_{\scriptstyle{\cal F}}}\cdot
p_{{}_{\scriptstyle{\cal G}}}(\lambda)\end{array}\right]$

with diagonal ${\cal F}$-factor-counting vector $(\alpha,\beta)$. Then
construct the $n\times n$ unimodular matrices

$\widehat{E}(\lambda)\,=\,\left[\begin{array}[]{c|c|c}I_{i-1}&&\\\
\hline\cr\\\\[-12.0pt] &\rule{0.0pt}{11.66563pt}E(\lambda)&\\\
\hline\cr\\\\[-12.0pt]
&&\rule{0.0pt}{11.66563pt}I_{n-i-1}\end{array}\right]\quad\text{ and
}\quad\widehat{F}(\lambda)\,=\,\left[\begin{array}[]{c|c|c}I_{i-1}&&\\\
\hline\cr\\\\[-12.0pt] &\rule{0.0pt}{11.66563pt}F(\lambda)&\\\
\hline\cr\\\\[-12.0pt]
&&\rule{0.0pt}{11.66563pt}I_{n-i-1}\end{array}\right]\,.$

Transforming $P(\lambda)$ using these two unimodular matrices, we obtain the
desired matrix
$\widetilde{P}(\lambda)=\widehat{E}(\lambda)P(\lambda)\widehat{F}(\lambda)$. ∎

######  Example 3.5.

Consider the Smith form $S(\lambda)$ from Example 3.2. The multiset ${\cal M}$
of all of the irreducible factors in the entries of $S(\lambda)$ contains many
copies of $\chi$, $\phi$, and $\psi$, but we can partition it into ${\cal
M}={\cal F}_{1}\sqcup{\cal F}_{2}\sqcup{\cal F}_{3}\sqcup{\cal F}_{4}$, where
${\cal F}_{j}$ contains all of the irreducible factors of degree $j$. Thus we
see that ${\cal F}_{1}$ contains all of the copies of $\psi$, ${\cal F}_{2}$
contains all of the copies of $\phi$, ${\cal F}_{3}$ is empty, and ${\cal
F}_{4}$ contains all of the copies of $\chi$. The diagonal factor-counting
vectors of $S(\lambda)$ then are

$\displaystyle\mathbf{d}_{{}_{\scriptstyle{\cal F}_{1}}}(S)$
$\displaystyle\;=\;(0,1,1,2,2,4)\,,\hskip
34.1433pt\mathbf{d}_{{}_{\scriptstyle{\cal F}_{3}}}(S)\;=\;(0,0,0,0,0,0)\,,$
$\displaystyle\mathbf{d}_{{}_{\scriptstyle{\cal F}_{2}}}(S)$
$\displaystyle\;=\;(0,1,1,1,1,3)\,,\hskip
34.1433pt\mathbf{d}_{{}_{\scriptstyle{\cal F}_{4}}}(S)\;=\;(0,0,1,2,3,3)\,.$

Note that we include $\mathbf{d}_{{\cal F}_{3}}(S)$ here not only for the sake
of completeness, but also to show that having any of the partition multisets
be empty is allowed. Later on, we will use Corollary 3.4 to rearrange the
irreducible factors along the diagonal so that these diagonal factor-counting
vectors will have the property of being _1-homogeneous_ , a concept to be
defined in the next section.

Note that these diagonal factor-counting vectors just happen to match up with
the partial multiplicity sequences in this example. But this is not typical,
and follows from there being at most one irreducible divisor in each piece of
the given coprime partition of ${\cal M}$. For general coprime partitions,
diagonal factor-counting vectors of Smith forms will each be a _sum_ of
partial multiplicity sequences.

###  3.2 Homogenization of natural vectors and un-diagonalizing the Smith form

With the ability to transfer irreducible factors along the diagonal (Corollary
3.4) now in our tool box, it is time to see how to employ that tool to
rearrange the diagonal irreducible factors so as to make the new diagonal
entries as close in degree to each other as possible. This is phase $1$ of our
quasi-triangular realization construction. It will be shown that the best that
can be done in general is to make these diagonal entry degrees differ by at
most $k$, where $k$ is the highest degree among all of the irreducible factors
along the diagonal. To facilitate the discussion of this process, we introduce
the following two concepts. Note that vectors whose entries are natural
numbers, in particular diagonal factor-counting vectors, appear frequently in
this discussion; such vectors will be referred in brief as _natural vectors_.
Keep in mind that in this paper the natural numbers $\mathbb{N}$ _includes
zero_.

######  Definition 3.6.

A natural vector $\mathbf{v}=(v_{1},\dots,v_{r})\in\mathbb{N}^{r}$ is _$k$
-homogeneous_ if $|v_{i}-v_{j}|\leq k$ for any $1\leq i,j\leq r$.

######  Definition 3.7.

Let $\mathbf{v}=(v_{1},\dots,v_{r})\in\mathbb{N}^{r}$ with component sum
$s=v_{1}+v_{2}+\dotsb+v_{r}$, and divide $s$ by $r$ to get $s=qr+t$, with
$0\leq t<r$. Then any permutation of the $1$-homogeneous vector

$(q,q,\dotsc,q,\underbrace{q+1,q+1,\dotsc,q+1}_{t\,\text{
copies}})\,\in\,\mathbb{N}^{r}$

is called a _homogenization_ of $\mathbf{v}$.

Before addressing our primary objective, that is, the phase $1$ rearrangement
of diagonal irreducible factors, it will be useful to do a preliminary
examination of the process of homogenizing natural vectors via two very simple
operations that we will refer to as “interchange” and “compression”. We will
see that these two operations on natural vectors are closely related to
transformations of the diagonal of upper triangular polynomial matrices
achievable by the Unimodular Transfer Corollary 3.4. The operations of
interchange and compression also bring us into contact with the classical
notion of majorization of vectors, which we recall next.

######  Definition 3.8 (Majorization [14]).

For vectors $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$, let
$\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$ denote the permutations of
those vectors in which the entries have been arranged in decreasing order. We
say that _$\mathbf{x}$ majorizes $\mathbf{y}$_, or _$\mathbf{y}$ is majorized
by $\mathbf{x}$_, and write $\,\mathbf{x}\succeq\mathbf{y}\,$, if

$\displaystyle\sum_{i=1}^{\ell}x_{i}^{\prime}\;\geq\;\sum_{i=1}^{\ell}y_{i}^{\prime}\quad\text{
for }\quad\ell=1,2,\dotsc,n\;,$ (3.8)

with equality when $\ell=n$. Clearly this definition also applies without
change when restricted to integer vectors
$\mathbf{x},\mathbf{y}\in\mathbb{Z}^{n}$, or even to natural vectors
$\mathbf{x},\mathbf{y}\in\mathbb{N}^{n}$.

######  Remark 3.9.

It is useful to keep in mind the basic intuition about majorization, i.e.,
that if $\mathbf{x}$ majorizes $\mathbf{y}$, then the entries of $\mathbf{x}$
are more “spread out” than those of $\mathbf{y}$. This can be seen, at least
in part, by examining the two extreme components of the ordered vectors
$\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$. From the $\ell=1$ inequality
in (3.8) we have $x^{\prime}_{1}\geq y^{\prime}_{1}$, and by combining the
$\ell=n$ and $\ell=n-1$ parts of (3.8) we see that $y^{\prime}_{n}\geq
x^{\prime}_{n}$. Thus we have $x^{\prime}_{1}\geq y^{\prime}_{1}\geq\dotsb\geq
y^{\prime}_{n}\geq x^{\prime}_{n}$, displaying some of the greater dispersion
of the entries of $\mathbf{x}^{\prime}$.

It is a classical result of the study of majorization (attributed in [14] to a
1903 article of Muirhead [15]) that for natural vectors $\mathbf{x}$ and
$\mathbf{y}$, $\mathbf{x}$ majorizes $\mathbf{y}$
$(\mathbf{x}\succeq\mathbf{y})$ if and only if $\,\mathbf{x}$ can be
transformed into $\mathbf{y}$ by a finite sequence of operations known
variously as _transfers_ , _Dalton transfers_ , or more recently (and
colorfully) as _Robin Hood transfers_ – think “rob from the rich and give to
the poor”. Such an operation takes any two components of a natural vector
$\mathbf{v}$, say $v_{i}$ and $v_{j}$, and replaces them by natural numbers
$\alpha$ and $\beta$ that are closer together in size; more specifically,
where $\alpha+\beta=v_{i}+v_{j}$ and $|\alpha-\beta|\leq|v_{i}-v_{j}|$. (Note
that in his proof of this result, Muirhead uses only transfers in which
$v_{i}$ and $v_{j}$ change by exactly $1$, i.e., $\alpha=v_{i}\pm 1$ and
$\beta=v_{j}\mp 1$.)

For our purposes, we need to have a Muirhead-like result for converting a
natural vector into a homogenization of itself. However, since we will
ultimately need to implement these conversions by unimodular transformations
that preserve upper triangularity (see Corollary 3.4), it is essential that we
limit our operations on natural vectors to ones that act only on _adjacent
entries_ of a vector, which is more restrictive than the Robin Hood transfers
used by Muirhead. Thus we introduce the following two operations acting on
natural vectors:

  * •

Interchange of _adjacent_ components:

$(v_{1},\dots,v_{i},v_{i+1},\dots,v_{r})\leadsto(v_{1},\dots,v_{i+1},v_{i},\dots,v_{r})\in\mathbb{N}^{r}$

  * •

Compression of _adjacent_ components:

$(v_{1},\dots,v_{i-1},v_{i},v_{i+1},v_{i+2},\dots,v_{r})\leadsto(v_{1},\dots,v_{i-1},\alpha,\beta,v_{i+2},\dots,v_{r})\in\mathbb{N}^{r}\,,$

where $\alpha+\beta=v_{i}+v_{i+1}$ and $|\alpha-\beta|<|v_{i}-v_{i+1}|$.
Equivalently, we can instead require that $\alpha+\beta=v_{i}+v_{i+1}$ and
$\mathop{\rm min}\\{v_{i},v_{i+1}\\}<\alpha,\beta<\mathop{\rm
max}\\{v_{i},v_{i+1}\\}$.

Note that we use the new terminology “interchange” and “compression” here for
these more limited operations, to try to avoid any confusion with the more
flexible Robin Hood transfers. We now state and prove the modified version of
the classic Muirhead result, specialized to the transformation of a natural
vector into a homogenization of itself. As an immediate consequence of Lemma
3.10 and the Muirhead theorem, we see that any natural vector $\mathbf{v}$
majorizes any homogenization of itself.

######  Lemma 3.10 (Homogenization Lemma).

Consider any $\mathbf{v}=(v_{1},\dots,v_{r})\in\mathbb{N}^{r}$, with component
sum $s=v_{1}+\dots+v_{r}$, and average component value $a=s/r$. Let
$q\in\mathbb{N}$ be an integer such that the average $a$ is contained in the
closed interval $[\mkern 1.0muq,q+1\mkern 1.0mu]$. Then by a finite sequence
of interchanges and at most $r-1$ compressions, $\mathbf{v}$ can be
transformed into a homogenization of itself, comprised of only $q$ and $q+1$
components, ordered arbitrarily. Writing $s=qr+t$ with $0\leq t\leq r$, then
in the homogenization of $\mathbf{v}$ there are exactly $t$ copies of $q+1$
and $r-t$ copies of $q$.

###### Proof.

The proof will proceed by a pair of inductions, each on the length $r$ of the
vector $\mathbf{v}$. The first induction considers only vectors $\mathbf{v}$
whose average component value $a$ is an integer, either $q$ or $q+1$. In this
case we will see that the homogenization of $\mathbf{v}$ is the vector
$(a,a,\dotsc,a)$. The second induction, which builds on the result of the
first, considers the vectors $\mathbf{v}$ where $a$ is _not_ an integer, i.e.,
$q<a<q+1$. For this second case the homogenization will have both $q$ and
$q+1$ entries.

Part 1 ($a$ is an integer)
The case $r=1$ is trivial, and the case $r=2$ is also very easy – just do a
single ($r-1=1$) compression to produce the homogenization $(a,a)$. So now
assume that every $k$-vector $\mathbf{v}\in\mathbb{N}^{k}$ with $k<r$ and
integer average $a$ can be finitely transformed into a homogenization
$(a,a,\dotsc,a)$ using at most $k-1$ compressions. Let
$\mathbf{v}\in\mathbb{N}^{r}$ be any $r$-vector with average value $a=q$. If
$\mathbf{v}$ already has any component equal to $q$, then finitely many
interchanges move this component to the end, producing
$\mathbf{v}\leadsto(\widetilde{\mathbf{v}},q)$. If not, then one can find at
least one component larger than $q$ and one component smaller than $q$. By
interchanges make these components adjacent, and then a compression on these
two components can produce at least one $q$ component. Finitely many more
interchanges then moves this newly-produced $q$ to the end, again producing
$\mathbf{v}\leadsto(\widetilde{\mathbf{v}},q)$. In either case, the
$(r-1)$-vector $\widetilde{\mathbf{v}}$ has average component value
$\widetilde{a}=(s-q)/(r-1)=(ar-a)/(r-1)=a=q$. By the induction hypothesis the
vector $\widetilde{\mathbf{v}}$ can now be transformed by finitely many
interchanges and at most $r-2$ compressions into the vector $(a,a,\dotsc,a)$,
and thus we have the desired conclusion for the $r$-vector $\mathbf{v}$. The
same argument works, mutatis mutandis, for vectors
$\mathbf{v}\in\mathbb{N}^{r}$ with average value $a=q+1$.

Part 2 ($a$ is _not_ an integer, i.e., $q<a<q+1$ and $0<t<r$)
Here the base case for the induction cannot be $r=1$; it must be $r=2$, with
$a=q+\frac{1}{\mkern 1.0mu2\mkern 1.0mu}$. In this $r=2$ case, then, a single
compression can produce the vector $(q,q+1)$, as desired. Again as in Part 1,
now assume that every $k$-vector $\mathbf{v}\in\mathbb{N}^{k}$ with $k<r$ and
average $q<a<q+1$ can be finitely transformed into a homogenized version
containing only $q$ and $q+1$ components, using at most $k-1$ compressions.
Let $\mathbf{v}\in\mathbb{N}^{r}$ be any $r$-vector with non-integer average
value $q<a<q+1$. If $\mathbf{v}$ already has any component equal to $q$ or
$q+1$, then finitely many interchanges moves this component to the end,
producing $\mathbf{v}\leadsto(\widetilde{\mathbf{v}},q)$ or
$(\widetilde{\mathbf{v}},q+1)$. If no component of $\mathbf{v}$ is $q$ or
$q+1$, then there must be at least one component larger than $q+1$ and one
component smaller than $q$. Make these components adjacent by interchanges,
and compress these two components to produce at least one $q$ or $q+1$ entry
(possibly both, or perhaps even two $q$’s or two $q+1$’s). Move this $q$ or
$q+1$ entry to the end by interchanges, once again transforming $\mathbf{v}$
into the form $(\widetilde{\mathbf{v}},q)$ or $(\widetilde{\mathbf{v}},q+1)$.
The $(r-1)$-vector $\widetilde{\mathbf{v}}$ now has a component average

$\widetilde{a}\,=\,\begin{cases}\frac{\,s-q\,}{r-1}\,=\,\frac{\,qr+t-q\,}{r-1}\,=\,q+\frac{t}{\,r-1\,}\,\leq\,q+1&\text{\,if\;
$\mathbf{v}\leadsto(\widetilde{\mathbf{v}},q)$,}\\\\[5.0pt]
\frac{\,s-(q+1)\,}{r-1}\,=\,\frac{\,qr+t-q-1\,}{r-1}\,=\,q+\frac{t-1}{\,r-1\,}\,\geq\,q&\text{\,if\;
$\mathbf{v}\leadsto(\widetilde{\mathbf{v}},q+1)$.}\end{cases}$

If $\widetilde{a}$ is $q$ or $q+1$, then we are done by Part 1. Otherwise
$q<\widetilde{a}<q+1$, and we are done by the induction hypothesis of Part 2.

This completes the inductive argument that a homogenization of $\mathbf{v}$
can always be achieved. The expression of the component sum $s$ in the form
$s=qr+t$ with $0\leq t\leq r$ then uniquely determines the number of $q$ and
$q+1$ entries in the homogenization. A final sequence of interchanges can put
the entries of the homogenization into any desired order, thus completing the
proof of the lemma. ∎

With the Homogenization Lemma in hand, we return to the first phase of our
quasi-triangular realization process, the “un-diagonalizing” of a Smith form.
The next result addresses the combinatorial essence of this problem, showing
how it is possible to take a multiset of irreducible polynomials and
distribute them among the entries of a vector in a way that minimizes the
degree differences, and at the same time produces a viable configuration for
the diagonal vector of an upper triangular un-diagonalized Smith form. The
corollary immediately following shows that the target diagonal produced by
Lemma 3.11 is in fact reachable from the Smith form via the type of
triangularity-preserving unimodular transformations developed in Corollary
3.4.

######  Lemma 3.11.

Let $\,\mathbb{F}$ be an arbitrary field, and consider a finite multiset
${\cal M}$ of $\,\mathbb{F}$-irreducible polynomials of degree less than or
equal to $k$. Also let $n$ be any positive integer. Let ${\cal M}={\cal
F}_{1}\sqcup\dotsb\sqcup{\cal F}_{k}$ be the coprime partition of ${\cal M}$
in which ${\cal F}_{j}$ contains all of the $\,\mathbb{F}$-irreducible factors
in ${\cal M}$ of degree $j$. Then there exists a polynomial $n$-vector
$\,\mathbf{p}(\lambda)$ with all nonzero entries such that

  * •

the multiset of all of the $\,\mathbb{F}$-irreducible factors of all the
entries of $\,\mathbf{p}(\lambda)$ is exactly ${\cal M}$,

  * •

the degree vector $\,\deg\mathbf{p}:=\,\bigl{(}\deg p_{1}(\lambda),\dotsc,\deg
p_{n}(\lambda)\bigr{)}$ is $k$-homogeneous,

  * •

and each of the factor-counting vectors
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ for $j=1,\dotsc,k$ is
$1$-homogeneous.

###### Proof.

For notational convenience, we first append enough copies of the constant
polynomial $1$ to the multiset ${\cal M}$ so that the total number $m$ of
elements in ${\cal M}$ is a multiple of $n$, i.e., $|{\cal M}|=:m=(q+1)n$ with
$q\geq 0$. The presence of these copies of $1$ will have no impact on the
vector $\mathbf{p}$ that is constructed, but the exposition will be simplified
by including them.

Next order the elements of ${\cal M}$ into a list ${\cal L}$ so that the
sequence of degrees is decreasing. That is, let ${\cal
L}=\bigl{[}a_{1}(\lambda),a_{2}(\lambda),\dotsc,a_{m}(\lambda)\bigr{]}$, where
$\deg a_{\ell}\geq\deg a_{\ell+1}$ for every $\ell=1,2,\dotsc,m-1$. Now
partition the list ${\cal L}$ into $q+1$ contiguous sublists of $n$
polynomials each, and stack them up as in the following diagram. (Keep in mind
that $qn+n=m$.)

$\begin{array}[]{cc@{\hspace{5mm}}l@{\hspace{5mm}}lll}{\cal
L}_{0}&=\hfil\hskip 14.22636pt&\;[\,a_{1},\hfil\hskip
14.22636pt&\;a_{2},&\dotsc&\;\;,a_{n}]\\\ {\cal L}_{1}&=\hfil\hskip
14.22636pt&[\,a_{n+1},\hfil\hskip 14.22636pt&a_{n+2},&\dotsc&\;\,,a_{2n}\,]\\\
&\vdots\hfil\hskip 14.22636pt&\hfil\hskip 14.22636pt&&&\\\ {\cal
L}_{j}&=\hfil\hskip 14.22636pt&\\![\,a_{jn+1},\hfil\hskip
14.22636pt&a_{jn+2},&\dotsc&\,,a_{jn+n}\,]\\\ &\vdots\hfil\hskip
14.22636pt&\hfil\hskip 14.22636pt&&&\\\ {\cal L}_{q}&=\hfil\hskip
14.22636pt&\\![\,a_{qn+1},\hfil\hskip
14.22636pt&a_{qn+2},&\dotsc&,a_{qn+n}\,]\end{array}$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{1}(\lambda)$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{2}(\lambda)$$\dotsc$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{n}(\lambda)$

The $n$ component polynomials of the desired vector $\mathbf{p}(\lambda)$ are
formed by taking the column-wise products indicated by the blue ovals. For
example, $p_{1}(\lambda):=a_{1}(\lambda)a_{n+1}(\lambda)\dotsb
a_{qn+1}(\lambda)$ , $p_{2}(\lambda):=a_{2}(\lambda)a_{n+2}(\lambda)\dotsb
a_{qn+2}(\lambda)$ , etc. It is clear by construction that the multiset of all
of the $\,\mathbb{F}$-irreducible factors of all the entries of
$\,\mathbf{p}(\lambda)$ is exactly ${\cal M}$. All that remains is to see why
this $\mathbf{p}(\lambda)$ has the other two desired properties.

To see why the degree vector $\deg\mathbf{p}$ is $k$-homogeneous, first
observe that the component degrees are decreasing, i.e., $\deg p_{1}\geq\deg
p_{2}\geq\dotsb\geq\deg p_{n}$. This follows immediately from the elements of
the list ${\cal L}$ being in decreasing order. Consequently the largest degree
difference in $\mathbf{p}$ will be between the first and last components
$p_{1}(\lambda)$ and $p_{n}(\lambda)$. But we have

$\displaystyle\deg p_{1}-\deg p_{n}\;$ $\displaystyle=\;(\deg a_{1}+\deg
a_{n+1}+\dotsb+\deg a_{(qn+1)})-(\deg a_{n}+\deg a_{2n}+\dotsb+\deg
a_{(qn+n)})$ $\displaystyle=\;\deg a_{1}-\bigl{[}(\deg a_{n}-\deg
a_{n+1})+(\deg a_{2n}-\deg a_{2n+1})+\dotsb+(\deg a_{qn}-\deg a_{qn+1})+\deg
a_{m}\bigr{]}$ $\displaystyle\leq\;k\,,$

since $\deg a_{1}(\lambda)\leq k$, and the expression inside the brackets is a
sum of non-negative numbers (due to the list ${\cal L}$ being in decreasing-
degree order). Hence the degree vector $\deg\mathbf{p}(\lambda)$ is
$k$-homogeneous.

Finally, consider the factor-counting vectors
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$. To see why these
vectors are all $1$-homogeneous, observe that because the irreducible
polynomials are listed in ${\cal L}$ in order of decreasing degree, the degree
$j$ irreducibles in ${\cal L}$ form a contiguous segment of ${\cal L}$, and
hence are distributed among consecutive sublists ${\cal L}_{\delta}$ in a
manner analogous to the green entries in the following diagram. On the other
hand, if $\alpha<\beta$, then

$\begin{array}[]{cclllllll}&\vdots&&&&&&&\\\ {\cal L}_{\alpha}&=&\\{a_{\alpha
n+1}\,,&\dotsc&\,,\boxed{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{\alpha
n+i}}\,,&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&,\,\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{\alpha
n+\ell}\,,&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&,\;\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{\alpha
n+n}\\}\\\ {\cal
L}_{\alpha+1}&=&\\{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{(\alpha+1)n+1},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&\,,\,\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{(\alpha+1)n+i},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&,\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{(\alpha+1)n+\ell},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&,\;\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{(\alpha+1)n+n}\\}\\\
&\vdots&&&&&&&\\\ {\cal
L}_{\beta}&=&\\{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{\beta
n+1}\,,&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&\,,\,\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{\beta
n+i}\,,&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\dotsc&,\boxed{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}a_{\beta
n+\ell}}\,,&\dotsc&,\;a_{\beta n+n}\\}\\\ &\vdots&&&&&&&\\\
\end{array}$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{1}$$\dotsc$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{i}$$\dotsc$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{\ell}$$\dotsc$$\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}v_{n}$

The first instance of a degree $j$ irreducible is the boxed entry $a_{\alpha
n+i}$ with $1\leq i\leq n$ in some sublist ${\cal L}_{\alpha}$, and the last
degree $j$ irreducible is the boxed entry $a_{\beta n+\ell}$, where
$\alpha\leq\beta$.

If $\alpha=\beta$, then $i\leq\ell$, and all of the degree $j$ irreducibles in
${\cal L}$ are in the sublist ${\cal L}_{\alpha}$, so the factor-counting
vector $|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ has only $0$
and $1$ entries; this certainly constitutes a $1$-homogeneous vector. On the
other hand, if $\alpha<\beta$ then we may have either $\ell<i-1$, $\ell=i-1$,
or $\ell>i-1$. Consider each of these possibilities in turn:

  * •

$\ell<i-1$: In this case the combined contribution of the degree $j$ entries
in ${\cal L}_{\alpha}$ and ${\cal L}_{\beta}$ to
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ is the $n$-vector

$(1,1,\dotsc,\underbrace{1}_{\ell},0,\dotsc,0,\underbrace{1}_{i},\dotsc,1)\,,$

while the contribution of the sublists ${\cal L}_{\delta}$ with
$\alpha<\delta<\beta$ is a constant vector with $n$ entries all equal to
$\beta-\alpha-1$. The sum of these two vectors is
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$, and is clearly
$1$-homogeneous.

  * •

$\ell=i-1$: Now the contribution to
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ from ${\cal
L}_{\alpha}$ and ${\cal L}_{\beta}$ combined is just the constant $n$-vector
$(1,1,\dotsc,1)$, which together with the contribution from the sublists
between ${\cal L}_{\alpha}$ and ${\cal L}_{\beta}$ gives a constant vector for
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$, with entries all
equal to $\beta-\alpha$. This is certainly $1$-homogeneous, indeed even
$0$-homogeneous.

  * •

$\ell>i-1$: In this final case the combined contribution of the degree $j$
entries in ${\cal L}_{\alpha}$ and ${\cal L}_{\beta}$ to
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ is the $n$-vector

$(1,\dotsc,1,\underbrace{2}_{i},2,\dotsc,\underbrace{2}_{\ell},1,\dotsc,1)\,.$

Together with the constant vector contribution from the sublists between
${\cal L}_{\alpha}$ and ${\cal L}_{\beta}$, we again see that
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ is $1$-homogeneous.

∎

######  Remark 3.12.

Note that $k$-homogeneity for $\mathbf{p}(\lambda)$ in Lemma 3.11 is the best
possible general result here, as illustrated by the following simple example.
Suppose ${\cal M}$ contains _only_ irreducible polynomials of degree $k$, say
$\ell$ of them, and $n>\ell$. Then clearly the $n$-vector
$\mathbf{p}(\lambda)$ that minimizes the degree differences has
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal
F}_{k}}}=(k,k,\dotsc,k,0,\dotsc,0)$, and $k$-homogeneity cannot be improved
upon in this situation.

We return to our running illustration of the results of this paper, as begun
earlier in Examples 3.2 and 3.5. The next example demonstrates the application
of Lemma 3.11 to this data.

######  Example 3.13.

Recall the $\,6\times 6\,$ Smith form from Example 3.2, i.e.,

$S(\lambda)=\mathop{\rm
diag}\\{1,\phi\psi,\chi\phi\psi,\chi^{2}\phi\psi^{2},\chi^{3}\phi\psi^{2},\chi^{3}\phi^{3}\psi^{4}\\}\,,$

and consider the coprime partition of the list of irreducible divisors as in
Example 3.5, with

${\cal
F}_{1}\,=\,\\{\underbrace{{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}\psi,\psi,\psi,\psi,\psi,\psi,\psi,\psi,\psi,\psi}}_{10}\\}\,,\quad\;{\cal
F}_{2}\,=\,\\{\underbrace{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\phi,\phi,\phi,\phi,\phi,\phi,\phi}}_{7}\\}\,,\quad\;{\cal
F}_{4}\,=\,\\{\underbrace{{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}\chi,\chi,\chi,\chi,\chi,\chi,\chi,\chi,\chi}}_{9}\\}\,,$

and an ${\cal F}_{3}$ that is empty. Following the proof of Lemma 3.11 gives
us five sublists, each of length $6$:

$\begin{array}[]{lclccccr}{\cal
L}_{0}&=&\\{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi}\\}\\\
{\cal
L}_{1}&=&\\{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}{\chi},&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi},&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi},&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi}\\}\\\
{\cal
L}_{2}&=&\\{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi},&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi},&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi},&\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\phi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi}\\}\\\
{\cal
L}_{3}&=&\\{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi}\\}\\\
{\cal
L}_{4}&=&\\{\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&\color[rgb]{0.0,0.7,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.7,0.0}{\psi},&1,&1,&1,&1\\}\,.\end{array}$

Then taking the products going down the columns, we get
$\mathbf{p}(\lambda)=\bigl{(}p_{1}(\lambda),\dotsc,p_{6}(\lambda)\bigr{)}$
with

$\begin{array}[]{llllll}p_{1}(\lambda)=\chi^{2}\phi\psi^{2}\,,&\;p_{2}(\lambda)=\chi^{2}\phi\psi^{2}\,,&\;p_{3}(\lambda)=\chi^{2}\phi\psi\,,&\;p_{4}(\lambda)=\chi\phi^{2}\psi\,,&\;p_{5}(\lambda)=\chi\phi\psi^{2}\,,&\;p_{6}(\lambda)=\chi\phi\psi^{2}\,.\end{array}$

The vector $\mathbf{p}(\lambda)$ has factor-counting vectors

$\displaystyle|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{1}}}$
$\displaystyle=(2,2,1,1,2,2)$
$\displaystyle|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{2}}}$
$\displaystyle=(1,1,1,2,1,1)$
$\displaystyle|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{3}}}$
$\displaystyle=(0,0,0,0,0,0)$
$\displaystyle|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{4}}}$
$\displaystyle=(2,2,2,1,1,1)\,,$

which are all $1$-homogeneous, and a $4$-homogeneous degree vector
$\deg\mathbf{p}=(12,12,11,9,8,8)$, just as guaranteed by Lemma 3.11.

We now have the tools needed to reach the next milestone in our construction
of a quasi-triangular realization of given finite spectral data. The following
corollary is the main result to carry forward into the next stages of this
construction.

######  Corollary 3.14 (Un-diagonalizing the Smith form).

Let $\,\mathbb{F}$ be an arbitrary field, and consider any regular $n\times n$
diagonal polynomial matrix $S(\lambda)$ over $\,\mathbb{F}$ that is in Smith
form. Let ${\cal M}$ be the multiset of all of the $\,\mathbb{F}$-irreducible
factors of all of the invariant polynomials in $S(\lambda)$, and let $k$ be
the maximum degree among all elements of ${\cal M}$. Consider also the coprime
partition ${\cal M}={\cal F}_{1}\sqcup\dotsb\sqcup{\cal F}_{k}$, in which each
${\cal F}_{j}$ contains all of the $\,\mathbb{F}$-irreducible factors in
${\cal M}$ of degree $j$. Then there is an upper triangular polynomial matrix
$T(\lambda)$ that is unimodularly equivalent to $S(\lambda)$, with diagonal
degree vector $\,\deg\bigl{(}\mathop{\rm diag}T(\lambda)\bigr{)}$ that is
$k$-homogeneous, and such that each diagonal factor-counting vector
$\mathbf{d}_{{}_{\scriptstyle{\cal F}_{j}}}(T)$ is $1$-homogeneous.

###### Proof.

Use the given multiset ${\cal M}$ of $\mathbb{F}$-irreducible polynomials as
input to Lemma 3.11. The output vector $\mathbf{p}(\lambda)$ from that Lemma
is now the target diagonal for the desired upper triangular $T(\lambda)$.
Since each factor-counting vector
$|\mathbf{p}(\lambda)|_{{}_{\scriptstyle{\cal F}_{j}}}$ is $1$-homogeneous,
the Homogenization Lemma 3.10 guarantees that the transition from the vector
$\mathop{\rm diag}S(\lambda)$ to the vector $\mathbf{p}(\lambda)$ can be
achieved using a finite number of compressions and interchanges. But Corollary
3.4 gives us the means to implement all of these compressions and interchanges
as unimodular transformations applied to $S(\lambda)$. Doing this then
converts $S(\lambda)$ into the desired upper triangular $T(\lambda)$. ∎

###  3.3 A combinatorial lemma

In this short section we focus on establishing a new combinatorial property of
“tightly packed” _integer_ multisets, that is, multisets that contain more,
perhaps even many more elements than the width of the interval into which they
are packed. This property will enable us to permute the diagonal entries of
the $T(\lambda)$ from Corollary 3.14 in preparation for the final phase of our
quasi-triangular realization construction. Note that for ease of expression,
in this section we use the word “list” as a synonym for multiset; however,
nothing about any ordering of these lists is of any relevance for the
development here.

######  Lemma 3.15 (Homogeneous Partitioning Property).

Let ${\cal I}=[\,j,j+k\,]$ be a closed interval with _integer_ endpoints and
length $k\geq 1$, and consider a list
$\mathcal{L}=\\{n_{1},n_{2},\dotsc,n_{m}\\}$ of $m$ integers, all in ${\cal
I}$. If the average value of all of the entries in ${\cal L}$ is an _integer_
$\mu\in{\cal I}$, then ${\cal L}$ can be partitioned into sublists ${\cal
S}_{1},{\cal S}_{2},\dotsc,{\cal S}_{\ell}$ such that the number of entries in
each ${\cal S}_{i}$ does not exceed $k$, and the average value of each sublist
is exactly $\mu$.

To help prove this result, we need another lemma characterizing the solution
set of a certain diophantine equation in two variables.

######  Lemma 3.16.

Let $a$ and $b$ be positive integers, with $d:=\gcd\\{a,b\\}$. Then the set of
integer solutions $(x,y)$ of the equation $ax=by$ consists of all the integer
multiples of the pair $(\widetilde{b},\widetilde{a})$, where
$\widetilde{a}=a/d$ and $\widetilde{b}=b/d$.

###### Proof.

We can immediately reduce to the equation $\widetilde{a}x=\widetilde{b}y$,
which has exactly the same solution set as $ax=by$. Since $\widetilde{a}$ and
$\widetilde{b}$ are relatively prime, for any solution pair $(x,y)$ it must be
true that $\widetilde{a}|y$ and $\widetilde{b}|x$. Letting $x=\widetilde{b}k$
and $y=\widetilde{a}\ell$, then
$\widetilde{a}\widetilde{b}k=\widetilde{b}\widetilde{a}\ell$ implies that
$k=\ell$. Thus the solutions of $\widetilde{a}x=\widetilde{b}y$ (and hence
also of $ax=by$) are exactly the integer multiples of
$(\widetilde{b},\widetilde{a})$. ∎

We now prove the Homogeneous Partitioning Property.

###### Proof.

(of Lemma 3.15) One strategy to achieve this homogeneous partitioning is to
first translate all the given data (i.e., the interval ${\cal I}$ and the list
${\cal L}$) by any fixed constant $c\in\mathbb{Z}$, solve the translated
problem, and then “un-translate” the solution back to the original location.
Thus it suffices to solve the problem for the case when $\mu=0$ and the
interval ${\cal I}$ is $[\,e_{\ell},e_{r}\,]$, with endpoints $e_{\ell}\leq 0$
and $e_{r}\geq 0$ such that $e_{r}-e_{\ell}=k$. The goal in this more
specialized scenario, then, is to partition ${\cal L}$ into sublists of no
more than $k$ entries each, such that the _sum_ (equals the average) of the
entries of each sublist ${\cal S}_{i}$ is zero.

The proof for this special scenario proceeds by an induction on $m$, the
number of elements in the list ${\cal L}$. (Note that this induction can be
easily converted into an algorithm for computing the desired partition.) The
base case(s) for this induction are all $m$ such that $1\leq m\leq k$, for
which the result is trivially true. So now suppose that the homogeneous
partitioning property holds for all number lists satisfying the hypotheses of
Lemma 3.15 with $m\leq h$, and consider a list ${\cal L}$ of $m=h+1$ integers
with values in ${\cal I}=[\,e_{\ell},e_{r}\,]$ and average value $\mu=0$.
There are now three cases to consider:

  1. (a)

_Some $n_{i}\in{\cal L}$ is equal to zero._
In this case we can split off the singleton sublist ${\cal S}_{1}=\\{n_{i}\\}$
from ${\cal L}$, leaving a smaller list $\widehat{{\cal L}}$ with $m=h$
entries, and average value $\widehat{\mu}=0$. Applying the inductive
hypothesis to $\widehat{{\cal L}}$ completes the homogeneous partitioning of
${\cal L}$.

  2. (b)

_No element of ${\cal L}$ is zero, and all elements of ${\cal L}$ lie at the
endpoints $e_{\ell}$ and $e_{r}$ of $\,{\cal I}$._
Suppose there are $\alpha$ copies of $e_{\ell}$ and $\beta$ copies of $e_{r}$,
so that $\,\alpha+\beta=h+1>k$, and $\,\alpha e_{\ell}+\beta e_{r}=0$, or
equivalently $(-e_{\ell})\alpha=e_{r}\beta$. Let
$d=\gcd\\{-e_{\ell},e_{r}\\}$. Applying Lemma 3.16 to the equation $ax=by$
with $a=-e_{\ell}$ and $b=e_{r}$, we see that the solution
$(x,y)=(\alpha,\beta)$ to $ax=by$ is an integer multiple of
$(\frac{\,e_{r}\,}{d},\frac{\,-e_{\ell}\,}{d})$. Thus we can completely
partition ${\cal L}$ into sublists ${\cal S}_{i}$, each consisting of
$\frac{\,e_{r}\,}{d}$ copies of $e_{\ell}$ and $\frac{\,-e_{\ell}\,}{d}$
copies of $e_{r}$. Since
$\,\frac{\,e_{r}\,}{d}+\frac{\,-e_{\ell}\,}{d}=\frac{\,k\,}{d}$, each of these
sublists has $\frac{\,k\,}{d}\leq k$ elements, and sum zero, as desired.

  3. (c)

_No element of ${\cal L}$ is zero, but there is some $n_{i_{1}}$ from ${\cal
L}$ in the _open_ interval $\,\widetilde{{\cal I}}=(e_{\ell},e_{r})$._
Begin building a sublist ${\cal S}$ with the given (nonzero) element
$\,n_{i_{1}}$ in $\widetilde{{\cal I}}$. Pick from among the remaining
elements of ${\cal L}$ to update ${\cal
S}=\\{n_{i_{1}},n_{i_{2}},\dotsc,n_{i_{j}},\dotsc\\}$, and keep track of the
“partial sums” $\sigma_{j}:=\sum_{\ell=1}^{j}n_{i_{\ell}}$ as you go to see if
a zero sum has been achieved.

At each stage, the element $n_{i_{j}}$ to be appended to ${\cal S}$ is chosen
to be any one of the remaining elements of ${\cal L}$ that have a sign
_opposite_ to that of $\sigma_{j-1}$, in order to try to drive the partial sum
value to zero. Observe that there must always exist such an “opposite-sign”
element remaining in ${\cal L}$, since otherwise the sum (hence also the
average) of all of the elements in ${\cal L}$ would not be zero. Another
consequence of this opposite-sign strategy is that the $\sigma_{j}$ values can
never be equal to either endpoint $e_{\ell}$ or $e_{r}$ of the interval ${\cal
I}$; each $\sigma_{j}$ must be one of the $k-1$ integers in the interior of
${\cal I}$, i.e. in $\,\widetilde{{\cal I}}$. To see why this is so, first
observe that $\sigma_{1}=n_{i_{1}}$ is in $\,\widetilde{{\cal I}}$ by
construction. For the passage from $\sigma_{j}$ to $\sigma_{j+1}$ with $j\geq
1$, there are three scenarios:

$\text{(i)}\;\;e_{\ell}<\sigma_{j}<0\,,\qquad\text{(ii)}\;\;\sigma_{j}=0\,,\quad\text{
or }\quad\text{(iii)}\;\;0<\sigma_{j}<e_{r}\,.$

In case (i), $\sigma_{j+1}$ can be at most $e_{r}$ larger than $\sigma_{j}$,
so $\sigma_{j+1}\in\,\widetilde{{\cal I}}$. In case (ii), the construction
will cease, and there will be no $\sigma_{j+1}$. And in case (iii),
$\sigma_{j+1}$ can be at most $\lvert e_{\ell}\rvert$ smaller than
$\sigma_{j}$, so once again $\sigma_{j+1}\in\,\widetilde{{\cal I}}$.

Now carry on the building up of the sublist ${\cal S}$ using the “opposite-
sign” strategy, until either (a) a partial sum $\sigma_{j}=0$ with $j\leq k-1$
is attained, or (b) the sublist contains $k-1$ elements with _every_ partial
sum $\sigma_{1},\dotsc,\sigma_{k-1}$ being nonzero. If (a) occurs, then split
off the sublist ${\cal S}=\\{n_{i_{1}},n_{i_{2}},\dotsc,n_{i_{j}}\\}$ from
${\cal L}$, and the remaining sublist $\widehat{{\cal L}}$ can be
homogeneously partitioned by the inductive hypothesis. On the other hand, if
(b) occurs, then the $k-1$ nonzero partial sums must have some repetitions,
since there are only $k-2$ nonzero integers in the open interval
$\,\widetilde{{\cal I}}$. So suppose that $\sigma_{i_{p}}=\sigma_{i_{j}}$ for
some $p<j\leq k-1$, and let $\widehat{{\cal
S}}:=\\{n_{i_{p+1}},\dotsc,n_{i_{j}}\\}$, with at most $k-2$ elements. Observe
that the sum of the elements in $\widehat{{\cal S}}$ is

$\sum_{\ell=p+1}^{j}n_{i_{\ell}}\;=\;\biggl{(}\,\sum_{\ell=1}^{j}n_{i_{\ell}}-\sum_{\ell=1}^{p}n_{i_{\ell}}\biggr{)}\;=\;\sigma_{i_{j}}-\sigma_{i_{p}}\;=\;0\,,$

so splitting off the sublist $\widehat{{\cal S}}$ from ${\cal L}$ starts the
homogeneous partitioning, leaving a remaining sublist $\widehat{{\cal L}}$
that can be homogeneously partitioned by the inductive hypothesis.

The result for the general interval ${\cal I}=[\,j,j+k\,]$ now follows by
translation. ∎

######  Remark 3.17.

A closer examination of the proof of the Homogeneous Partitioning property
indicates that the presence of sublists of “full length” $k$ in a homogeneous
partitioning may be somewhat rare. In most of the scenarios for splitting off
a sublist ${\cal S}$ from the main list ${\cal L}$, the length of the split-
off sublist is strictly less than $k$. In fact, the _only_ scenario that can
force a sublist to have length $k$ is very special; with all data translated
so that $\mu=0$, _all_ of the elements of ${\cal L}$ must be at the endpoints
$e_{\ell}$ and $e_{r}$, _and_ these endpoints must be relatively prime.

Another feature of the homogeneous partitioning problem that is hinted at in
the proof is that often these partitions are _not unique_. Indeed, in the
partitioning procedure described in the proof, in particular for case (c),
there may be many arbitrary choices that can be made, all of which lead to an
admissible partitioning. In addition, there may be other homogeneous
partitionings that cannot be generated from the procedure in the proof at all,
no matter what choices are made.

######  Remark 3.18.

It is worth noting that Lemma 3.15 can be extended to apply to the situation
in which the average $\mu\in{\cal I}$ is _not_ necessarily an integer. For
this general case the statement looks like the following:

> General Homogeneous Partitioning Property
>  Let ${\cal I}=[\,j,j+k\,]$ be a closed interval with _integer_ endpoints
> and length $k\geq 1$, and consider a list
> $\mathcal{L}=\\{n_{1},n_{2},\dotsc,n_{m}\\}$ of $m$ integers, all in ${\cal
> I}$. Let $\mu\in{\cal I}$ denote the average value of all of the entries in
> ${\cal L}$. Then ${\cal L}$ can be partitioned into sublists ${\cal
> S}_{1},{\cal S}_{2},\dotsc,{\cal S}_{\ell}$ such that the number of entries
> in each ${\cal S}_{i}$ does not exceed $k$, and the average value of each
> sublist is in the closed interval
> $\bigl{[}\,\lfloor\mu\rfloor,\lceil\mu\rceil\,\bigr{]}$.

Note that this more general partitioning result reduces to exactly Lemma 3.15
when the average $\mu$ is an integer. However, since we will not need the
general property for this paper, we omit the proof.

######  Example 3.19.

Recall that in Example 3.13 we took the diagonal vector of a Smith form
$S(\lambda)$, and rearranged the $\mathbb{F}$-irreducible factors via Lemma
3.11 to obtain a vector $\mathbf{p}(\lambda)$ with average degree $10$ and
$4$-homogeneous degree vector $\deg\mathbf{p}=(12,12,11,9,8,8)$. Lemma 3.15
now guarantees that there is a partitioning of $\,\deg\mathbf{p}\,$ (and a
corresponding partitioning of the entries of $\mathbf{p}$ itself) into
sublists of size at most $4$, where _each_ sublist also has average degree
$10$. Applying the procedure described in the proof of the Lemma produces the
partition $(12,8\mid 12,8\mid 11,9)$ for $\,\deg\mathbf{p}\,$, and the
corresponding rearrangement and partition

$\bigl{(}p_{1}(\lambda),p_{6}(\lambda)\mid p_{2}(\lambda),p_{5}(\lambda)\mid
p_{3}(\lambda),p_{4}(\lambda)\bigr{)}\,=\,\bigl{(}\chi^{2}\phi\psi^{2},\chi\phi\psi^{2}\mid\chi^{2}\phi\psi^{2},\chi\phi\psi^{2}\mid\chi^{2}\phi\psi,\chi\phi^{2}\psi\bigr{)}$
(3.9)

of the entries of $\,\mathbf{p}(\lambda)$. It is interesting to note that
there are several pathways through the partitioning procedure for this
example, but all of them lead to the partitioning in (3.9). However, there are
two other homogeneous partitionings of $\,\deg\mathbf{p}\,$ with sublist size
at most $k=4$, neither of which can be generated by the procedure of the
Lemma. They are $(12,8,12,8\mid 11,9)$ and $(12,8\mid 12,8,11,9)$.

###  3.4 Un-triangularizing $T(\lambda)$

One final tool is needed in order to complete the construction of our
$k$-quasi-triangular realization. After our realization is initially brought
into quasi-triangular form, it may happen that the off-diagonal blocks have
increased in degree beyond the target for the final matrix polynomial, since
no control of these blocks has even been attempted in the early stages of the
construction. Thus we need some method to bring these degrees back within the
target range. Furthermore, it is important to do this by unimodular
transformations, so that the desired finite spectral structure will not be
spoiled. Lemma 3.22, a generalization of Lemma 2.4 from [20], shows how to
achieve this goal.

Two preliminaries are needed for Lemma 3.22. First it will be helpful to
recall the notion of the “diagonals” of a matrix, and more generally the
block-diagonals of a block-partitioned matrix.

######  Definition 3.20 (Diagonals of a matrix).

The _$\ell^{th}$ -diagonal_ of a matrix $A$ is the set of entries $a_{ij}$ of
$A$ such that $j-i=\ell$. (Note that the $0^{th}$-diagonal is conventionally
known as the main diagonal of $A$.) If $A$ is block-partitioned with blocks
$A_{ij}$, then the _$\ell^{th}$ -block-diagonal_ of $A$ is the collection of
blocks $A_{ij}$ with $j-i=\ell$.

A second important background fact concerns the division of matrix
polynomials. We recall now this fundamental result for the convenience of the
reader.

######  Lemma 3.21 (Division of matrix polynomials).

Suppose $A(\lambda)$ is any $m\times n$ matrix polynomial over an arbitrary
field $\,\mathbb{F}$. Furthermore, let $B(\lambda)$ and $C(\lambda)$ be any
two _strictly regular_ matrix polynomials over $\,\mathbb{F}$, with size
$m\times m$ and $n\times n$, respectively. Then we have:

  1. (a)

Left division by $B$: There exist unique $m\times n$ matrix polynomials
$Q_{\ell}(\lambda)$ and $R_{\ell}(\lambda)$ such that

$A(\lambda)\;=\;B(\lambda)Q_{\ell}(\lambda)\,+\,R_{\ell}(\lambda)\,,$

and either $R_{\ell}(\lambda)=0$, or $R_{\ell}(\lambda)$ is nonzero with $\deg
R_{\ell}<\deg B$. The matrices $Q_{\ell}(\lambda)$ and $R_{\ell}(\lambda)$ are
called the left quotient and left remainder of $A(\lambda)$, respectively,
upon (left) division by $B(\lambda)$.

  2. (b)

Right division by $C$: There exist unique $m\times n$ matrix polynomials
$Q_{r}(\lambda)$ and $R_{r}(\lambda)$ such that

$A(\lambda)\;=\;Q_{r}(\lambda)C(\lambda)\,+\,R_{r}(\lambda)\,,$

and either $R_{r}(\lambda)=0$, or $R_{r}(\lambda)$ is nonzero with $\deg
R_{r}<\deg C$. The matrices $Q_{r}(\lambda)$ and $R_{r}(\lambda)$ are called
the right quotient and right remainder of $A(\lambda)$, respectively, upon
(right) division by $C(\lambda)$.

###### Proof.

See [7, Ch. 4], [9, Sect. 6.3], or [11, Sect. 7.2]. ∎

######  Lemma 3.22 (Degree reduction of off-diagonal blocks).

Let $T(\lambda)\in\mathbb{F}[\lambda]^{n\times n}$ be a block upper triangular
matrix polynomial, partitioned into blocks such that all of the $s$ diagonal
blocks $T_{ii}(\lambda)\in\mathbb{F}[\lambda]^{n_{i}\times n_{i}}$ are
_strictly regular_. Then $T(\lambda)$ is unimodularly equivalent to a block
upper triangular matrix polynomial $\widetilde{T}(\lambda)$ with exactly the
same diagonal blocks as $T(\lambda)$, and with off-diagonal blocks satisfying

$\deg\widetilde{T}_{ij}(\lambda)\;<\;\mathop{\rm min}\bigl{\\{}\,\deg
T_{ii}(\lambda),\,\deg T_{jj}(\lambda)\,\bigr{\\}}$ (3.10)

for $\,1\leq i<j\leq s$.

_Proof._ Let us begin by focusing on a single fixed but arbitrary off-diagonal
block $T_{ij}(\lambda)$ with $i<j$, and showing how to reduce its degree by a
unimodular transformation so as to satisfy the condition (3.10). It may be
that (3.10) is already satisfied; in this case do nothing. Otherwise, suppose
first that $\deg T_{ii}\leq\deg T_{jj}$. Then by Lemma 3.21 we can divide
$T_{ij}(\lambda)$ by $T_{ii}(\lambda)$ _on the left_ to obtain

$T_{ij}(\lambda)\,=\,T_{ii}(\lambda)Q_{ij}(\lambda)+R_{ij}(\lambda)\;\text{
with }\;R_{ij}(\lambda)\,=\,0\;\text{ or }\;\deg R_{ij}(\lambda)<\deg
T_{ii}(\lambda)\,,$

and hence $T_{ij}(\lambda)-T_{ii}(\lambda)Q_{ij}(\lambda)=R_{ij}(\lambda)$.
Now define the unimodular matrix

$V_{ij}(\lambda)\,:=\;\left[\begin{array}[]{ccccc}I_{a}&&&&\\\
&I_{n_{i}}&&-Q_{ij}(\lambda)&\\\ &&I_{b}&&\\\ &&&I_{n_{j}}&\\\
&&&&I_{c}\end{array}\right]\,,\;\text{ where }\quad
a=\sum_{m=1}^{i-1}n_{m}\,,\;b=\sum_{m=i+1}^{j-1}n_{m}\,,\;c=\sum_{m=j+1}^{s}n_{m}\,.$

Multiplying $T(\lambda)$ on the right by $V_{ij}(\lambda)$ has the effect of
an elementary block-column operation, which replaces the block
$T_{ij}(\lambda)$ by $\widetilde{T}_{ij}(\lambda)=R_{ij}(\lambda)$, thus
satisfying condition (3.10) at this one location. In addition we see that the
diagonal blocks of $T(\lambda)$ remain unchanged by this block-column
operation. Indeed, the _only_ other blocks of $T(\lambda)$ that may even
possibly be affected are the ones directly above the $(i,j)$-block, i.e.,
blocks $T_{\ell j}(\lambda)$ with $\ell\leq i$.

On the other hand, if $\deg T_{ii}>\deg T_{jj}$ then something analogous can
be done. In this case use Lemma 3.21 to divide $T_{ij}(\lambda)$ by
$T_{jj}(\lambda)$ _on the right_ to obtain

$T_{ij}(\lambda)\,=\,\widehat{Q}_{ij}(\lambda)T_{jj}(\lambda)+\widehat{R}_{ij}(\lambda)\;\text{
with }\;\widehat{R}_{ij}(\lambda)\,=\,0\;\text{ or
}\;\deg\widehat{R}_{ij}(\lambda)<\deg T_{jj}(\lambda)\,,$

and hence
$T_{ij}(\lambda)-\widehat{Q}_{ij}(\lambda)T_{jj}(\lambda)=\widehat{R}_{ij}(\lambda)$.
Define the unimodular matrix

$U_{ij}(\lambda)\,:=\;\left[\begin{array}[]{ccccc}I_{a}&&&&\\\
&I_{n_{i}}&&-\widehat{Q}_{ij}(\lambda)&\\\ &&I_{b}&&\\\ &&&I_{n_{j}}&\\\
&&&&I_{c}\end{array}\right]\,,\;\text{ where }\quad
a=\sum_{m=1}^{i-1}n_{m}\,,\;b=\sum_{m=i+1}^{j-1}n_{m}\,,\;c=\sum_{m=j+1}^{s}n_{m}\,,$

and multiply $T(\lambda)$ on the left by $U_{ij}(\lambda)$. This has the
effect of an elementary block-row operation, which replaces the block
$T_{ij}(\lambda)$ by $\widetilde{T}_{ij}(\lambda)=\widehat{R}_{ij}(\lambda)$,
once again satisfying condition (3.10) at this one location. In the product
$U_{ij}(\lambda)T(\lambda)$, the only other blocks of $T(\lambda)$ that can
possibly affected are those to the right of the $(i,j)$-block, i.e., blocks
$T_{i\ell}(\lambda)$ with $\ell\geq j$. Altogether, then, the only possible
collateral damage that can be inflicted on $T(\lambda)$ by this degree
reduction of the $(i,j)$-block is to the blocks of $T(\lambda)$ in the
L-shaped region marked in (3.11).

$T(\lambda)\;=\;\left[\begin{array}[]{cccccccc}\diamond&&&&{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}\bigl{\|}}&&&\\\\[-5.0pt]
&\ddots&&&{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}\Bigl{\lVert}}&&&\\\\[4.0pt]
&&T_{ii}&&T_{ij}&{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}***}&{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}***\,*}&{\color[rgb]{1.0,0.0,0.0}\definecolor[named]{pgfstrokecolor}{rgb}{1.0,0.0,0.0}***}\\\
&&&\ddots&&&&\\\ &&&&T_{jj}&&&\\\ &&&&&\ddots&&\\\ &&&&&&\ddots&\\\
&&&&&&&\diamond\end{array}\right]$ (3.11)

It is important to keep this L-shape firmly in mind as we see how to order the
block degree reductions so that no individual block’s degree reduction spoils
a block that has already had its degree reduced.

The key observation here is that whenever a block $T_{ij}(\lambda)$ has its
degree reduced by the procedure described above, then all of the other blocks
in $T(\lambda)$ that are affected by that reduction lie on “higher” diagonals
of $T(\lambda)$ than the diagonal of $T_{ij}(\lambda)$. More precisely, if
$T_{ij}(\lambda)$ lies on the $\ell^{th}$-block-diagonal of $T(\lambda)$, then
all other blocks affected by that degree reduction lie on an $m^{th}$-block-
diagonal with $m>\ell$. Thus a single _sweep-by-diagonals_ through the off-
diagonal blocks will have the desired effect of achieving condition (3.10) on
_all_ off-diagonal blocks simultaneously. To do this kind of sweep, first
target each of the blocks in the $1^{th}$-block-diagonal for degree reduction,
in any order. After visiting each block in the $1^{th}$-block-diagonal, go
next to the $2^{th}$-block-diagonal and do a degree reduction on each of these
blocks, again in any order. Because of the key observation, none of the degree
reductions done in the $1^{th}$-block-diagonal will be spoiled by the degree
reductions done in the $2^{th}$-block-diagonal, and none of the
$2^{th}$-block-diagonal degree reductions will spoil each other. Continue in
this manner, moving up one block-diagonal at a time, until each off-diagonal
block has been visited exactly once. At this point, the desired matrix
polynomial $\widetilde{T}(\lambda)$ will have been attained. $\square$

We finally have all the tools we will need to “un-triangularize” $T(\lambda)$
into a degree-$d$, $k$-quasi-triangular realization of the original list of
finite spectral data. For convenience, we recall the statement of Theorem 3.1
here.

######  Theorem (Quasi-Triangular Realization: Strictly Regular Case).

Suppose a list of $m$ nonconstant monic polynomials
$s_{1}(\lambda),\dots,s_{m}(\lambda)$ over an arbitrary field $\,\mathbb{F}$
is given, satisfying the divisibility chain condition
$s_{1}(\lambda)\,|\,s_{2}(\lambda)\,|\,\dotsb\,|\,s_{m}(\lambda)$. Let
$\sigma:=\sum_{i=1}^{m}\deg\bigl{(}s_{i}(\lambda)\bigr{)}$, and define $k$ to
be the maximum degree among all of the $\mathbb{F}$-irreducible factors of the
polynomials $s_{i}(\lambda)$ for $i=1,\dotsc,m$. Then for any choice of
nonzero $d,n\in\mathbb{N}$ such that $n\geq m$ and $dn=\sigma$, there exists
an $n\times n$, degree $d$, strictly regular matrix polynomial $Q(\lambda)$
over $\mathbb{F}$ that is $k$-quasi-triangular, and has exactly the given
polynomials $s_{1}(\lambda),\dots,s_{m}(\lambda)$ as its nontrivial invariant
polynomials, together with $n-m$ trivial invariant polynomials. In addition,
$Q(\lambda)$ can always be chosen so that the degree of every entry in any
off-diagonal block of $Q(\lambda)$ is strictly less than $d$.

###### Proof.

From the given spectral data, begin by constructing the $n\times n$ Smith form

$S(\lambda)=\mathop{\rm
diag}\\{\,\,\underbrace{1,\dotsc,1}_{n-m},s_{1}(\lambda),\dotsc,s_{m}(\lambda)\,\\}\,.$

Now we can use the tools developed in Corollary 3.14, Lemma 3.15, Corollary
3.4, Corollary 2.12, and Lemma 3.22 to build the desired $k$-quasi-triangular
realization of the spectral data contained in $S(\lambda)$, in the following
five steps:

  * •

Use $S(\lambda)$ as input to Corollary 3.14 to generate an upper triangular
$T(\lambda)$ that is unimodularly equivalent to $S(\lambda)$, and has a
diagonal degree vector $\,\deg\bigl{(}\mathop{\rm diag}T(\lambda)\bigr{)}$
that is $k$-homogeneous.

  * •

Use the natural vector $\,\deg\bigl{(}\mathop{\rm diag}T(\lambda)\bigr{)}$,
with average value $\mu=d$, as input to Lemma 3.15, and find a homogeneous
partitioning of the degrees of the diagonal entries of $T(\lambda)$ into
$\ell$ sublists. The corresponding partitioning of the diagonal entries
themselves, with the elements of the entry sublists arranged into $\ell$
contiguous groups, provides a target for the rearrangement of the entries on
the diagonal of $T(\lambda)$.

  * •

Implement this rearrangement of the diagonal entries of $T(\lambda)$ via the
triangularity-preserving unimodular transformations of $T(\lambda)$ provided
by Corollary 3.4, each of which has the effect of simply performing an
interchange of adjacent diagonal entries. (Of course some of the off-diagonal
entries are being changed in the process, but we do not try to keep any
control of them at this stage of the construction.) Denote the resulting upper
triangular matrix by $\widehat{T}(\lambda)$, and partition this
$\widehat{T}(\lambda)$ into blocks

$\widehat{T}(\lambda)\;=\;\left[\begin{array}[]{cccc}\widehat{T}_{11}(\lambda)&\widehat{T}_{12}(\lambda)&\dotsm&\widehat{T}_{1\ell}(\lambda)\\\
&\widehat{T}_{22}(\lambda)&\dotsm&\widehat{T}_{2\ell}(\lambda)\\\\[-2.0pt]
&&\ddots&\vdots\\\ &&&\widehat{T}_{\ell\ell}(\lambda)\end{array}\right]\,,$
(3.12)

so that each (upper triangular and square) diagonal block
$\widehat{T}_{jj}(\lambda)$ has diagonal entries that correspond to the
sublist ${\cal S}_{j}$ of the homogeneous partitioning of
$\,\deg\bigl{(}\mathop{\rm diag}T(\lambda)\bigr{)}$. For each $j$, if we
denote the size of the block $\widehat{T}_{jj}(\lambda)$ by $n_{j}\times
n_{j}$, then from the Homogeneous Partitioning property we know that
$n_{j}\leq k$, and the average degree of the diagonal entries of
$\widehat{T}_{jj}(\lambda)$ is $d$. So the sum of the degrees of the diagonal
entries of $\widehat{T}_{jj}(\lambda)$ is $dn_{j}$.

  * •

By Corollary 2.12 we know that each _diagonal_ block
$\widehat{T}_{jj}(\lambda)$ is unimodularly equivalent to a strictly regular
polynomial matrix $P_{jj}(\lambda)$ of degree $d$, which is (probably) no
longer upper triangular. Let these equivalences be denoted by

$P_{jj}(\lambda):=\,\widehat{U}_{jj}(\lambda)\widehat{T}_{jj}(\lambda)\widehat{V}_{jj}(\lambda)\,,$

where each $\widehat{U}_{jj}(\lambda)$ and $\widehat{V}_{jj}(\lambda)$ is
$n_{j}\times n_{j}$ and unimodular. Now define the $n\times n$ block-diagonal
unimodular matrices

$\widehat{U}(\lambda):=\,\mathop{\rm
diag}\bigl{\\{}\,\widehat{U}_{11}(\lambda),\widehat{U}_{22}(\lambda),\dotsc,\widehat{U}_{\ell\ell}(\lambda)\,\bigr{\\}}\quad\text{
and }\quad\widehat{V}(\lambda):=\,\mathop{\rm
diag}\bigl{\\{}\,\widehat{V}_{11}(\lambda),\widehat{V}_{22}(\lambda),\dotsc,\widehat{V}_{\ell\ell}(\lambda)\,\bigr{\\}}\,,$

and apply them to the full $\widehat{T}(\lambda)$, to get

$P(\lambda):=\,\widehat{U}(\lambda)\widehat{T}(\lambda)\widehat{V}(\lambda)\,=\,\left[\begin{array}[]{cccc}P_{11}(\lambda)&P_{12}(\lambda)&\dotsm&P_{1\ell}(\lambda)\\\
&P_{22}(\lambda)&\dotsm&P_{2\ell}(\lambda)\\\ &&\ddots&\vdots\\\
&&&P_{\ell\ell}(\lambda)\end{array}\right].$ (3.13)

This matrix $P(\lambda)$ is now $k$-quasi-triangular, with strictly regular
diagonal blocks each of degree $d$. But $P(\lambda)$ as a whole may not yet be
of degree $d$, because the off-diagonal blocks have not been kept under any
control at all.

  * •

The final step brings the degrees of the off-diagonal blocks back under
control, while at the same time not disturbing the diagonal blocks in the
process. Lemma 3.22 applied to $P(\lambda)$ achieves this, reducing the degree
of each off-diagonal block to be strictly less than $d$, and leaving the
diagonal blocks unchanged, to obtain the final desired realization

$Q(\lambda)\;=\;\left[\begin{array}[]{cccc}Q_{11}(\lambda)&Q_{12}(\lambda)&\dotsm&Q_{1\ell}(\lambda)\\\
&Q_{22}(\lambda)&\dotsm&Q_{2\ell}(\lambda)\\\ &&\ddots&\vdots\\\
&&&Q_{\ell\ell}(\lambda)\end{array}\right]\,.$ (3.14)

with $Q_{jj}(\lambda)=P_{jj}(\lambda)$ for $j=1,\dotsc,\ell$.

This polynomial matrix $Q(\lambda)$ is $k$-quasi-triangular, has degree $d$,
and is unimodularly equivalent to the original $S(\lambda)$, and hence has
exactly the given finite spectral data. To see that $Q(\lambda)$ is strictly
regular, we regard $\mathop{\rm grade}(Q)$ as being equal to the degree $d$;
by Lemma 2.7, any other choice will force $Q(\lambda)$ to have nontrivial
infinite spectral structure. Since by construction the sum of the degrees of
all of the invariant polynomials of $Q(\lambda)$ is $dn$, the Index Sum
Theorem 2.10 immediately shows that the sum of the partial multiplicities of
$Q(\lambda)$ at infinity must be zero, and hence that $Q(\lambda)$ is strictly
regular. ∎

######  Example 3.23.

We now bring the extended illustrative example (started in Example 3.2 and
continuing through Examples 3.5, 3.13, and 3.19) to a culmination, using the
proof of Theorem 3.1 to complete the construction of a strictly regular,
$k$-quasi-triangular realization (over the field $\mathbb{F}=\mathbb{Z}_{2}$)
of the given finite spectral data from back in Example 3.2. Recall that $k=4$,
the target size is $6\times 6$ with degree $10$, and the three irreducible
divisors in the original spectral data are
$\,\chi(\lambda)=\lambda^{4}+\lambda^{3}+1$,
$\,\phi(\lambda)=\lambda^{2}+\lambda+1$, and $\,\psi(\lambda)=\lambda$.

In Example 3.19, we found a homogeneous partitioning $(12,8\mid 12,8\mid
11,9)$ of diagonal degrees, and corresponding permutation of diagonal entries
to give us the target diagonal

$\bigl{(}\,\chi^{2}\phi\psi^{2},\,\chi\phi\psi^{2},\,\chi^{2}\phi\psi^{2},\,\chi\phi\psi^{2},\,\chi^{2}\phi\psi\,,\,\chi\phi^{2}\psi\,\bigr{)}$
(3.15)

for the upper triangular matrix (3.12) in our construction. Now the theory we
have developed guarantees that the $S(\lambda)$ in Example 3.2 can be
unimodularly transformed into an upper triangular $\widehat{T}(\lambda)$ such
that $\mathop{\rm diag}\widehat{T}(\lambda)$ is exactly the vector in (3.15).
And furthermore, that this transformation can be implemented as a finite
sequence of embedded $2\times 2$ unimodular transformations acting only on
adjacent diagonal entries. It would be very tedious to display all of these
transformations, and the resulting upper triangular $\widehat{T}(\lambda)$ is
very likely to have a densely populated upper triangular part. So instead, for
ease of exposition we exhibit an alternative $\widehat{T}(\lambda)$ with the
desired diagonal vector that is not only sparse, but is also easily checked to
be unimodularly equivalent to $S(\lambda)$.

$\widehat{T}(\lambda)\,=\,\left[\begin{array}[]{cc|cc|cc}\chi^{2}\phi\psi^{2}&\chi\phi\psi&0&0&0&0\\\
0&\chi\phi\psi^{2}&0&0&0&1\\\ \hline\cr\\\\[-12.0pt]
&&\rule{0.0pt}{10.5275pt}\chi^{2}\phi\psi^{2}&0&0&0\\\
&&0&\chi\phi\psi^{2}&\phi\psi&0\\\ \hline\cr\\\\[-12.0pt]
&&&&\rule{0.0pt}{10.5275pt}\chi^{2}\phi\psi&0\\\
&&&&0&\chi\phi^{2}\psi\end{array}\right]$

Observe that this $\widehat{T}(\lambda)$ has been partitioned into blocks as
in (3.12), in a manner that conforms to the partitioning of the diagonal
vector (3.9) arising from the homogeneous partitioning of the diagonal
degrees.

Each of the diagonal blocks of $\widehat{T}(\lambda)$ can now be transformed
into 2$\times$2 blocks having degree 10, via simple unimodular
transformations. Define the unimodular matrices

$U_{1}:=\left[\begin{array}[]{cc}1&\phi+1\\\ 0&1\end{array}\right]\,,\quad
U_{2}:=U_{1}\,,\quad U_{3}:=\left[\begin{array}[]{cc}1&\psi\\\
0&1\end{array}\right]\,,\quad V_{1}:=\left[\begin{array}[]{cc}1&0\\\
\psi^{2}&1\end{array}\right]\,,\quad V_{2}:=V_{1}\,,\;\;\text{ and
}\;\;V_{3}:=U_{3}^{T}\,.$

Since the underlying field here is $\mathbb{F}=\mathbb{Z}_{2}$, we then have

$\displaystyle
U_{1}\widehat{T}_{11}V_{1}\,=\,\chi\phi\psi\cdot\left[\begin{array}[]{cc}1&\phi+1\\\
0&1\end{array}\right]\left[\begin{array}[]{cc}\chi\psi&1\\\
0&\psi\end{array}\right]\left[\begin{array}[]{cc}1&0\\\
\psi^{2}&1\end{array}\right]$
$\displaystyle\,=\;\chi\phi\psi\cdot\left[\begin{array}[]{cc}\phi+1&\phi\psi+\psi+1\\\
\psi^{3}&\psi\end{array}\right]\,,$ $\displaystyle
U_{2}\widehat{T}_{22}V_{2}\,=\,\chi\phi\psi^{2}\cdot\left[\begin{array}[]{cc}1&\phi+1\\\
0&1\end{array}\right]\left[\begin{array}[]{cc}\chi&0\\\
0&1\end{array}\right]\left[\begin{array}[]{cc}1&0\\\
\psi^{2}&1\end{array}\right]$
$\displaystyle\,=\;\chi\phi\psi^{2}\cdot\left[\begin{array}[]{cc}1&\phi+1\\\
\psi^{2}&1\end{array}\right]\,,$ $\displaystyle
U_{3}\widehat{T}_{33}V_{3}\,=\,\chi\phi\psi\cdot\left[\begin{array}[]{cc}1&\psi\\\
0&1\end{array}\right]\left[\begin{array}[]{cc}\chi&0\\\
0&\phi\end{array}\right]\left[\begin{array}[]{cc}1&0\\\
\psi&1\end{array}\right]$
$\displaystyle\,=\;\chi\phi\psi\cdot\left[\begin{array}[]{cc}\psi^{2}+1&\phi\psi\\\
\phi\psi&\phi\end{array}\right]\,,$

which are each readily seen to have degree $10$.

Applying these transformations collectively to all of $\widehat{T}(\lambda)$
via $U:=\mathop{\rm diag}\\{U_{1},U_{2},U_{3}\\}$ and $V:=\mathop{\rm
diag}\\{V_{1},V_{2},V_{3}\\}$ produces the 2-quasi-triangular realization

$P(\lambda):=\,U\widehat{T}(\lambda)V=\left[\begin{array}[]{cc|cc|cc}\chi\phi\psi(\phi+1)&\chi\phi\psi(\phi\psi+\psi+1)&0&0&\psi(\phi+1)&\phi+1\\\
\chi\phi\psi^{4}&\chi\phi\psi^{2}&0&0&\psi&1\\\ \hline\cr\\\\[-12.0pt]
&&\rule{0.0pt}{10.5275pt}\chi\phi\psi^{2}&\chi\phi\psi^{2}(\phi+1)&\phi\psi(\phi+1)&0\\\
&&\chi\phi\psi^{4}&\chi\phi\psi^{2}&\phi\psi&0\\\ \hline\cr\\\\[-12.0pt]
&&&&\rule{0.0pt}{10.5275pt}\chi\phi\psi(\psi^{2}+1)&\chi\phi^{2}\psi^{2}\\\
&&&&\chi\phi^{2}\psi^{2}&\chi\phi^{2}\psi\end{array}\right].$

with diagonal blocks that are all of degree $10$. Observe that all of the off-
diagonal blocks of $P(\lambda)$ have degree strictly less than $10$. Hence we
can skip the final step (i.e., using Lemma 3.22 to reduce the degrees of the
off-diagonal blocks) of the general procedure, and declare that our final
degree $10$, strictly regular, $2$-quasi-triangular realization $Q(\lambda)$
is identical to $P(\lambda)$ in this example.

Finally, note that there are at least two ways to see that our final
realization $Q(\lambda)$ is indeed strictly regular. One is by an index sum
argument – taking $\mathop{\rm grade}Q$ to be equal to $\deg Q=10$, we see
that there is no room in the index sum constraint (2.8) for any infinite
partial multiplicities to be nonzero, hence $Q(\lambda)$ must be strictly
regular. The second way is simply to examine the leading coefficient of
$Q(\lambda)$ as a matrix polynomial, i.e., the matrix coefficient of
$\lambda^{10}$. That matrix is easily seen to be just $\mathop{\rm
diag}(R,R,R)$, where $R$ is the $2\times 2$ matrix
$\bigl{[}\begin{smallmatrix}0&1\\\ 1&0\end{smallmatrix}\bigr{]}$; clearly this
coefficient is nonsingular. Hence $Q(\lambda)$ is strictly regular (see
comments just after Definition 2.8).

##  4 Including infinite spectral data in a realization

In this section we extend the range of our quasi-triangular realization
construction to handle spectral data arising from a general regular matrix
polynomial — i.e., data that may now include nontrivial infinite spectral
structure. The main tool that allows us to achieve this extension are Möbius
transformations, employing a now well-used technique; see [4], [12], and [19].
In a nutshell, the strategy of this technique is to use an appropriately
chosen Möbius transformation to translate a realization problem involving a
mixture of finite and infinite spectral data into one that has _only_ finite
spectral data, solve this strictly regular realization problem, and then
translate the solution back to the original spectral data using the inverse
Möbius transformation.

However, before we are able to implement this strategy, it will be necessary
to reexamine one of the fundamental properties of Möbius transformations from
[12], and recast it in a way that enables us to work with these
transformations more smoothly in the context of arbitrary fields $\mathbb{F}$,
in particular in the presence of higher degree $\mathbb{F}$-irreducible
divisors in spectral data. This will be the task of Section 4.1. With this
reimagined property of Möbius transformations in hand, in Section 4.2 we then
solve the quasi-triangular realization problem with nontrivial infinite
spectral structure. This gives us the final result needed to now easily prove
in Section 4.3 the featured result of the paper, the quasi-triangularization
of arbitrary regular matrix polynomials.

Before embarking on this final stage, though, it is worth pointing out several
subtle issues that arise in the course of carrying out this strategy. The
first concerns an extra hypothesis that is only needed if the field
$\mathbb{F}$ is finite, and even then only to exclude very special types of
spectral data set. When $\mathbb{F}$ is finite, then it is possible that
_every_ element of $\mathbb{F}$, as well as $\infty$, may appear in a given
spectral data set as an eigenvalue. If that happens, then any possible Möbius
transformation that one might attempt to use will simply map the set of
eigenvalues bijectively to itself, and thus will not be able to transform the
given spectral data into one that has only finite spectral data. To exclude
this one problematic scenario, it has been necessary to include an additional
hypothesis, i.e., that there must be some element of $\mathbb{F}$ that is
_not_ an eigenvalue in the given spectral data. Of course for any infinite
field $\mathbb{F}$, this hypothesis always holds, and so has no impact on the
range of spectral data sets to which the argument applies. But for finite
fields, having this one additional condition satisfied is sufficient to make
the rest of the argument work smoothly. (When this condition is violated, it
is not known whether quasi-triangular realizations exist or not.)

A second issue concerns the reduction of off-diagonal degrees to be less than
the target degree, as was done in the strictly regular case. When there is
nontrivial spectral structure at $\infty$, such a reduction may not be
possible. The difficulty is that this reduction is achieved via unimodular
transformations, which may alter the spectral structure at $\infty$. Indeed,
Example 4.8 in Section 4.2 gives a concrete illustration of how not only the
infinite spectral structure, but even the overall degree of the realization
itself, can be spoiled by doing the kind of degree reduction of off-diagonal
blocks described in Lemma 3.22.

###  4.1 Möbius transformation of spectral structure over an arbitrary field

We begin this section by reviewing the effect of Möbius transformations on the
spectral structure of a matrix polynomial, in the manner developed in [12]. In
that paper the emphasis was on scalars in the ambient field $\mathbb{F}$ (plus
$\infty$) as potential eigenvalues, and so the development was best adapted to
algebraically closed fields. However, when working with matrix polynomials
over arbitrary fields, with irreducible divisors of higher degree, the
formulation in [12] can be rather inconvenient, even a bit clumsy to use. Thus
our aim in this section is to reformulate the relationship between partial
multiplicity sequences and Möbius transformations in such a way that it works
smoothly and efficiently over all fields, and is well-adapted to our extended
notion of partial multiplicity sequences for irreducible divisors of any
degree, as defined in (2.2). We begin, though, with a brief review of the
relevant concepts, notation, and results from [12], in particular Theorem 5.3
from that paper.

If $P(\lambda)$ is a matrix polynomial over $\mathbb{F}$, and
$\mu_{0}\in\mathbb{F}_{\infty}$ is any scalar in the “extended” field
$\mathbb{F}_{\infty}:=\mathbb{F}\cup\\{\infty\\}$, then in [12] the partial
multiplicity sequence associated with $\mu_{0}$ was denoted by ${\cal
J}(P,\mu_{0})$. Note that the letter ${\cal J}$ was chosen there because the
partial multiplicity sequences for $P$ for _all_ scalars
$\mu_{0}\in\mathbb{F}_{\infty}$ was collectively termed the “Jordan
characteristic” of $P$. In the current paper, the partial multiplicity
sequence ${\cal J}(P,\mu_{0})$ is associated with the degree one irreducible
polynomial $\lambda-\mu_{0}$, rather than with the scalar $\mu_{0}$. Thus we
have the following equivalence between notations:

${\cal J}(P,\mu_{0})\;\equiv\;{\cal P}\\!{\cal M}(P,\lambda-\mu_{0})\,.$ (4.1)

Continuing the review of [12] — to any nonsingular
$A=\bigl{[}\begin{smallmatrix}a&b\\\ c&d\end{smallmatrix}\bigr{]}$ over
$\mathbb{F}$ there is an associated _Möbius function_
$\mathsf{m}_{A}(\lambda):\mathbb{F}_{\infty}\rightarrow\mathbb{F}_{\infty}$,
which is a bijection of scalars given by the formula

$\mathsf{m}_{A}(\lambda)\,:=\;\frac{a\lambda+b}{\,c\lambda+d\,}\,,$

and a Möbius transformation on matrix polynomials of grade $g$ given by

$\mathbf{M}_{A}\bigl{(}P(\lambda)\bigr{)}\,:=\;(c\lambda+d)^{g}\,P\bigl{(}\mathsf{m}_{A}(\lambda)\bigr{)}\,.$

Note that this is exactly the same as in Definition 2.13. Now a key result
from [12] establishes a simple relationship between the Jordan characteristics
of $P$ and $\mathbf{M}_{A}(P)$.

######  Theorem 4.1 (Theorem 5.3 from [12]).

Suppose $P(\lambda)$ is an $m\times n$ matrix polynomial of grade $g$ over an
arbitrary field $\,\mathbb{F}$, and $A\in GL(2,\mathbb{F})$ is a nonsingular
matrix with associated Möbius function $\mathsf{m}_{A}(\lambda)$ and Möbius
transformation $\mathbf{M}_{A}$. Then for any $\mu_{0}\in\mathbb{F}_{\infty}$,

${\cal J}\bigl{(}\mathbf{M}_{A}(P),\mu_{0}\bigr{)}\;=\;{\cal
J}\bigl{(}P,\mathsf{m}_{A}(\mu_{0})\bigr{)}\,,$ (4.2)

or equivalently,

${\cal
J}\bigl{(}\mathbf{M}_{A}(P),\mathsf{m}_{A^{-1}}(\mu_{0})\bigr{)}\;=\;{\cal
J}\bigl{(}P,\mu_{0}\bigr{)}\,.$ (4.3)

The formulas in Theorem 4.1 have one glaring drawback when trying to capture
the effect of a Möbius transformation on the complete spectral structure of a
matrix polynomial $P$ over a field $\mathbb{F}$ that is _not_ algebraically
closed. The problem is that the irreducible divisors of $P$ may all have
degree $2$ or larger, and thus have _no_ eigenvalues in $\mathbb{F}_{\infty}$
at all. In this scenario the formulas in Theorem 4.1 tell us nothing at all
about the spectral effects of the Möbius transformation. At least not
directly. The only way to recover any information about the spectral effects
of $\mathbf{M}_{A}$ would be to pass to the algebraic closure
$\overline{\mathbb{F}}$, which though feasible, may become an unwelcome
annoyance. It would be very useful to instead have some analog of Theorem 4.1
that applies directly to partial multiplicity sequences associated with
irreducible divisors of any degree, i.e., to the ${\cal P}\\!{\cal M}(P,\chi)$
defined earlier in (2.2). There is indeed such an analog, and the goal of the
remainder of this section is to establish this extension of Theorem 4.1. We
claim that the following relationship holds:

${\cal P}\\!{\cal
M}\bigl{(}\mathbf{M}_{A}(P),\mathbf{M}_{A}(\chi)\bigr{)}\;=\;{\cal P}\\!{\cal
M}(P,\chi)\,.$ (4.4)

To properly interpret this formula, however, two conventions must be observed:

  * •

On the left-hand side of (4.4), $\mathbf{M}_{A}(P)$ is taken with respect to
the specified grade for $P$, but $\mathbf{M}_{A}(\chi)$ should always be taken
with _$\mathop{\rm grade}\chi$ equal to $\deg\chi$_, with just the one
exception described next.

  * •

If $\chi(\lambda)=\beta$ is any _nonzero_ constant, then $\chi$ is to be
regarded as a _grade one_ polynomial, i.e., as $\alpha\lambda+\beta$ with
$\alpha=0$.

Note that the naive intuition underlying this second convention is that the
“root” of $0\lambda+\beta$ is $\lambda=-\beta/0=\infty$, and so
$0\lambda+\beta$ can play the role of a “polynomial stand-in” for an
eigenvalue at $\infty$. Thus we will now use the notation ${\cal P}\\!{\cal
M}(P,0\lambda+\beta)$ to replace the earlier temporary notation ${\cal
P}\\!{\cal M}(P,\infty)$ for the partial multiplicity sequence associated with
an eigenvalue at $\infty$. We will see in Theorem 4.6 and its proof that this
now makes the formula (4.4) internally consistent and universally applicable
to all partial multiplicity sequences, both for finite and for infinite
spectral structure. Some additional motivation and justification for this
(perhaps unexpected?) second convention is given in Remark 4.2.

######  Remark 4.2.

Let ${\cal G}_{1}$ denote the set of all _nonzero_ grade one scalar (i.e.,
$1\times 1$) polynomials $L(\lambda)=\alpha\lambda+\beta$ over $\mathbb{F}$.
It is well known [12] that any Möbius transformation $\mathbf{M}_{A}$ defines
a bijection ${\cal G}_{1}\rightarrow{\cal G}_{1}$, and the associated Möbius
function $\mathsf{m}_{A}$ defines a bijection
$\mathbb{F}_{\infty}\rightarrow\mathbb{F}_{\infty}$ on the extended field of
scalars $\mathbb{F}_{\infty}$. The purpose of this remark is to briefly
explore the parallelism between the bijection $\mathbf{M}_{A}$ and the
bijection $\mathsf{m}_{A^{-1}}$ (_not_ $\mathsf{m}_{A}$).

What underlies this parallelism is the simple calculation of
$\mathbf{M}_{A}(\lambda-\mu_{0})$, which also plays a central role in the
proof of Theorem 4.6. Using Definition 2.13, it is not hard to see that
$\mathbf{M}_{A}(\lambda-\mu_{0})$ is (usually) a nonzero scalar multiple of
$\lambda-\mathsf{m}_{A^{-1}}(\mu_{0})$, with the one possible exception of
being just a nonzero scalar. Now recall that in the context of discussing
spectral data, we are associating the degree one $\mathbb{F}$-irreducible
$(\lambda-\mu_{0})$ with the eigenvalue $\mu_{0}$. So we see that the mapping
of degree one irreducibles by $\mathbf{M}_{A}$ is mirrored by the mapping of
eigenvalues in $\mathbb{F}$ by $\mathsf{m}_{A^{-1}}$, at least for most
$\mu_{0}$.

To make this parallelism more precise, let us define a map $\rho:{\cal
G}_{1}\rightarrow\mathbb{F}_{\infty}$ that sends $\alpha\lambda+\beta\in{\cal
G}_{1}$ with $\alpha\neq 0$ to its root
$\frac{\,-\beta\,}{\alpha}\in\mathbb{F}$, i.e., define
$\rho(\alpha\lambda+\beta):=\frac{\,-\beta\,}{\alpha}$. This specifies $\rho$
on most of the desired domain ${\cal G}_{1}$, and enables us to express the
parallelism in the diagram

$\begin{CD}{\cal G}_{1}@>{\mathbf{M}_{A}}>{}>{\cal G}_{1}\\\
@V{\rho}V{}V@V{}V{\rho}V\\\
<EMAIL_ADDRESS>(4.5)

For all elements of ${\cal G}_{1}$ with $\alpha\neq 0$ (with at most one
exception), we see that the diagram (4.5) commutes. But what about elements of
${\cal G}_{1}$ with $\alpha=0$ (and hence $\beta\neq 0$), and the one possible
exceptional case when $\mathbf{M}_{A}(\lambda-\mu_{0})$ is just a nonzero
scalar? Is there a “natural” way to complete the definition of the map $\rho$
to the whole domain ${\cal G}_{1}$, and to do so in such a way that (4.5)
commutes? There is indeed a unique way to achieve this, and that is to define
$\rho(0\lambda+\beta):=\infty\in\mathbb{F}_{\infty}$, for any $\beta\neq 0$.
Thus we see from another direction why it is natural to associate the grade
$1$ polynomial $0\lambda+\beta$ with an eigenvalue at $\infty$. Note that the
commuting of the diagram (4.5) holds for any $A\in GL(2,\mathbb{F})$ and its
associated Möbius transformation and function.

The simplest (and perhaps most revealing) example of (4.5) uses
$\mathbf{M}_{R}$ with $R=\bigl{[}\begin{smallmatrix}0&1\\\
1&0\end{smallmatrix}\bigr{]}$ i.e., $\mathbf{M}_{R}=\mathop{\rm rev}_{1}$. In
this case with $\alpha\neq 0$ and $\beta\neq 0$ we have
$\mathbf{M}_{R}(\alpha\lambda+\beta)=\beta\lambda+\alpha$ with reciprocal
roots $\frac{\,-\beta\,}{\alpha}$ and $\frac{\,-\alpha\,}{\beta}$,
respectively, and also
$\mathsf{m}_{R^{-1}}(\mu_{0})=\mathsf{m}_{R}(\mu_{0})=\frac{1}{\,\mu_{0}\,}$
is the reciprocal map. So clearly everything in the diagram commutes when
$\alpha$ and $\beta$ are _both_ nonzero. But if $\alpha=0$, then with our
convention we have $\mathbf{M}_{R}(0\lambda+\beta)=\beta\lambda$, with roots
$\infty$ and $0$, which are commonly regarded in the literature as being
“reciprocal”. Thus we see directly when $A=R$ that (4.5) commutes for all
elements of ${\cal G}_{1}$.

It is also useful to note that (4.5) still commutes if we pass to the
equivalence classes discussed earlier in Remark 2.2. That is, let us declare
that two $\mathbb{F}$-irreducible polynomials are equivalent if one is a
nonzero scalar multiple of the other, i.e., $\chi\sim c\chi$ for any nonzero
scalar $c\in\mathbb{F}$. Letting $\widetilde{{\cal G}}_{1}$ denote the
resulting set of equivalence classes of grade one polynomials over
$\mathbb{F}$, then both of the maps $\mathbf{M}_{A}$ and $\rho$ respect these
equivalence classes, and so induce well-defined quotient maps
$\widetilde{\mathbf{M}}_{A}$ and $\widetilde{\rho}$, which are both
bijections. This, then, gives us the following commutative diagram in which
all of the mappings are bijective.

$\begin{CD}\widetilde{{\cal
G}}_{1}@>{\widetilde{\mathbf{M}}_{A}}>{}>\widetilde{{\cal G}}_{1}\\\
@V{\widetilde{\rho}}V{}V@V{}V{\widetilde{\rho}}V\\\
\mathbb{F}_{\infty}@>{\mathsf{m}_{A^{-1}}}>{}>\mathbb{F}_{\infty}\end{CD}$
(4.6)

Finally, note that with our conventions, the scenario
$\mathbf{M}_{A}(\chi)=\beta$ _cannot_ arise in (4.4) if the
$\mathbb{F}$-irreducible $\chi$ has $\deg(\chi)\geq 2$; it can only occur if
$\chi\in{\cal G}_{1}$. This is not obvious, but follows from a property to be
proved in Lemma 4.4, namely that for any $\mathbb{F}$-irreducible $\chi$ with
$\deg(\chi)\geq 2$, and $\mathbf{M}_{A}(\chi)$ taken with respect to degree,
then $\deg\mathbf{M}_{A}(\chi)=\deg(\chi)$.

Before proceeding to prove (4.4) in Theorem 4.6, we first establish some
preliminary lemmas. The first of these lemmas appeared in [12] as Corollary
3.24a, but we recall it here together with its simple proof for the
convenience of the reader.

######  Lemma 4.3 (Basic product property of Möbius transformations).

Let $p,q\in\mathbb{F}[\lambda]$ be nonzero scalar polynomials, and let
$A=\bigl{[}\begin{smallmatrix}a&b\\\ c&d\end{smallmatrix}\bigr{]}\in
GL(2,\mathbb{F})$. Letting the grades of $p$, $q$, and $pq$ all be chosen to
be equal to their degrees, then we have
$\mathbf{M}_{A}(pq)=\mathbf{M}_{A}(p)\mathbf{M}_{A}(q)$.

###### Proof.

Let $d_{1}=\deg p$ and $d_{2}=\deg q$. Then from Definition 2.13 we have

$\displaystyle\mathbf{M}_{A}(pq)$
$\displaystyle\;=\;(c\lambda+d)^{d_{1}+d_{2}}\,p\bigl{(}\mathsf{m}_{A}(\lambda)\bigr{)}\,q\bigl{(}\mathsf{m}_{A}(\lambda)\bigr{)}$
$\displaystyle\;=\;(c\lambda+d)^{d_{1}}\,p\bigl{(}\mathsf{m}_{A}(\lambda)\bigr{)}\cdot(c\lambda+d)^{d_{2}}\,q\bigl{(}\mathsf{m}_{A}(\lambda)\bigr{)}\;=\;\mathbf{M}_{A}(p)\,\mathbf{M}_{A}(q)\,.$

∎

The next result was mentioned in Section 2 under the name Lemma 2.15. We
recall it here and provide the proof postponed from earlier.

######  Lemma 4.4.

Suppose $\mathbb{F}$ is an arbitrary field, and $\chi(\lambda)$ is any
$\mathbb{F}$-irreducible scalar polynomial with $\deg\chi\geq 2$. Let
$\mathbf{M}_{A}$ be the Möbius transformation associated with any
$A=\bigl{[}\begin{smallmatrix}a&b\\\ c&d\end{smallmatrix}\bigr{]}\in
GL(2,\mathbb{F})$. Then with $\mathop{\rm grade}(\chi)$ taken to be equal to
$\deg(\chi)$, the transformation $\mathbf{M}_{A}$ preserves both the degree
and the $\mathbb{F}$-irreducibility of $\chi$. That is, $\mathbf{M}_{A}(\chi)$
is $\mathbb{F}$-irreducible, and
$\,\deg\bigl{(}\mathbf{M}_{A}(\chi)\bigr{)}=\deg(\chi)$.

###### Proof.

That $\mathbf{M}_{A}$ preserves $\mathbb{F}$-irreducibility was shown in [12,
Corollary 3.24]. To see why degree is preserved, we look at $\chi(\lambda)$
over the algebraic closure $\overline{\mathbb{F}}$ of $\mathbb{F}$. Over
$\overline{\mathbb{F}}$ we may factor $\chi$ completely into linear factors,
i.e., $\,\chi(\lambda)\,=\,k(\lambda-r_{1})(\lambda-r_{2})\dotsb(\lambda-
r_{d})$, where $d=\deg\chi\geq 2$ and $k\in\mathbb{F}$. Now observe that for
$\chi$ to be $\mathbb{F}$-irreducible, _all_ of these roots $r_{i}$ must be in
$\overline{\mathbb{F}}\setminus\mathbb{F}$, otherwise $\chi$ would be
$\mathbb{F}$-reducible. Computing $\mathbf{M}_{A}(\chi)$ with grade equal to
degree $d$, and using the multiplicative property of Möbius transformations in