This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Explicit constructions of connections on the projective line with a maximally ramified irregular singularity

Neal Livesay Roux Institute, Northeastern University, Boston, MA n.livesay@northeastern.edu Daniel S. Sage Department of Mathematics, Louisiana State University, Baton Rouge, LA. sage@math.lsu.edu  and  Bach Nguyen Department of Mathematics, Xavier University of Louisiana, New Orleans, LA. bnguye22@xula.edu
Abstract.

The Deligne–Simpson problem is an existence problem for connections with specified local behavior. Almost all previous work on this problem has restricted attention to connections with regular or unramified singularities. Recently, the authors, together with Kulkarni and Matherne, formulated a version of the Deligne–Simpson problem where certain ramified singular points are allowed and solved it for the case of Coxeter connections, i.e., connections on the Riemann sphere with a maximally ramified singularity at zero and (possibly) an additional regular singular point at infinity. A certain matrix completion problem, which we call the Upper Nilpotent Completion Problem, plays a key role in our solution. This problem was solved by Krupnik and Leibman, but their work does not provide a practical way of constructing explicit matrix completions. Accordingly, our previous work does not give explicit Coxeter connections with specified singularities. In this paper, we provide a numerically stable and highly efficient algorithm for producing upper nilpotent completions of certain matrices that arise in the theory of Coxeter connections. Moreover, we show how the matrices generated by this algorithm can be used to provide explicit constructions of Coxeter connections with arbitrary unipotent monodromy in each case that such a connection exists.

Key words and phrases:
matrix completion problem, Deligne–Simpson problem, meromorphic connections, irregular singularities, nilpotent matrices
2020 Mathematics Subject Classification:
15A83, 34M50 (Primary); 14D05, 34M35 (Secondary)

1. Introduction

A fundamental question in the theory of meromorphic systems of linear differential equations on the Riemann sphere 1\mathbb{P}^{1} is whether there exists a differential equation with specified local behavior at its singularities. Consider the ODE Y+A(z)Y=0Y^{\prime}+A(z)Y=0, where A(z)A(z) is an n×nn\times n matrix whose coefficients are rational functions over \mathbb{C}. This ODE determines a collection of local differential equations by expanding A(z)A(z) as a Laurent series at each point in 1\mathbb{P}^{1}. We view these local differential equations as ODEs with coefficients in the field of formal Laurent series in one variable. The local behavior of a meromorphic ODE is the collection of isomorphism classes of formal ODEs at the singular points. One can then pose the natural question: given a finite subset of singular points in 1\mathbb{P}^{1} and a set of corresponding isomorphism classes of formal ODEs, does there exist a meromorphic ODE with this local behavior? The Deligne–Simpson problem is a closely-related problem [27].

Almost all previous work on the Deligne–Simpson problem has assumed that each singular point is either regular singular [9] (i.e., a simple pole) or “unramified” [15, 14].111A formal ODE is called unramified if its Levelt–Turrittin form (an ODE version of Jordan canonical form) can be obtained without introducing roots of the local parameter. Recently, the authors, together with Kulkarni and Matherne, formulated a version of the Deligne–Simpson problem where ”toral” ramified singular points are allowed and solved it for the case of ODEs on the Riemann sphere with a maximally ramified singularity at zero and (possibly) an additional regular singular point at infinity [24]. This class of differential equations, which we call Coxeter ODEs, includes important hypergeometric differential equations such as the Airy equation and the Kloosterman (or Frenkel–Gross) equation [19, 20, 10]. Explicitly, if we set ω=i=1n1ei,i+1+zen,1\omega=\sum_{i=1}^{n-1}e_{i,i+1}+ze_{n,1}—i.e., ω\omega is the matrix with ones on the superdiagonal, zz in the lower-left entry, and zeroes elsewhere—then the Airy equation is Y+z2ω1Y=0Y^{\prime}+z^{-2}\omega^{-1}Y=0 and the Kloosterman equation is Y+z1ω1Y=0Y^{\prime}+z^{-1}\omega^{-1}Y=0.

In this special case of the Deligne–Simpson problem, the specified local behavior at 0 and \infty is given by a polynomial p(ω1)p(\omega^{-1}) of degree rr with gcd(r,n)=1\gcd(r,n)=1 and an adjoint orbit (or simply a Jordan canonical form). The polynomial pp determines a “formal type of slope r/nr/n” for the irregular singular point at 0, while the adjoint orbit corresponds to the residue of the regular singular point at \infty. For example, for the Kloosterman equation, p(ω1)=ω1p(\omega^{-1})=\omega^{-1}, r=1r=1, and the Jordan canonical form is a single nilpotent Jordan block. For the Airy equation, p(ω1)=(ω1)n+1p(\omega^{-1})=(\omega^{-1})^{n+1}, r=n+1r=n+1, and the adjoint orbit at \infty is the zero orbit (meaning that \infty is not a singular point).

A key discovery in [24] is a relationship between the Deligne–Simpson problem for Coxeter ODEs and the following matrix completion problem, which we call the Upper Nilpotent Completion Problem:

Let AA be a nilpotent n×nn\times n matrix, let μ\mu be the partition of nn with parts corresponding to the Jordan block sizes of AA, and let λ\lambda be a partition of nn dominating μ\mu. Show that there exists a strictly upper triangular matrix XX such that A+XA+X is nilpotent with Jordan block sizes λ\lambda.

To describe how this works, let us restrict to the simplest case where 0<r<n0<r<n, p(ω1)=ωrp(\omega^{-1})=\omega^{-r}, and the adjoint orbit is nilpotent with Jordan form corresponding to a partition λ\lambda of nn. In this case, we showed in [24] that there exists a connection with the specified local behavior if and only if λ\lambda has at most rr parts, or equivalently if and only if the Jordan canonical form has at most rr blocks. For example, suppose that A=NrA=N_{r}, the matrix with ones in each entry of the rrth diagonal and zeroes in all other entries. A (constructive) solution to the Upper Nilpotent Completion Problem with A=NrA=N_{r} determines an explicit ODE with the given local behavior. Indeed, if XX is strictly upper triangular such that Nr+XN_{r}+X is nilpotent of type λ\lambda, then Y+z1(Nnrz1+Nr+X)Y=0Y^{\prime}+z^{-1}(N_{n-r}^{\top}z^{-1}+N_{r}+X)Y=0 has the desired properties.

The Upper Nilpotent Completion Problem was originally stated by Rodman and Shalom [25], and it was solved by Krupnik and Leibman [22]. This result, together with the solution of an extension of this problem to more general orbits by Krupnik [21], plays a crucial role in [24]. However, although Krupnik and Leibman describe an algorithm for constructing the desired nilpotent completion, the algorithm cannot be carried out effectively in practice to the best of our knowledge. Indeed, even in simple cases, the algorithm requires repeatedly transforming matrices into a form similar to Jordan canonical form, and we are not aware of any numerically stable way of carrying out their algorithm.

In this paper, we give a numerically stable and highly efficient algorithm which constructs explicit (as well as binary and sparse) solutions to the Upper Nilpotent Completion Problem for the special case that A=NrA=N_{r}. If λ\lambda is any partition of nn with at most rr parts, the output of this algorithm is a strictly upper triangular binary matrix XλX_{\lambda} such that Nr+XλN_{r}+X_{\lambda} is nilpotent of type λ\lambda. As a result, the ODEs Y+z1(Nnrz1+Nr+Xλ)Y=0Y^{\prime}+z^{-1}(N_{n-r}^{\top}z^{-1}+N_{r}+X_{\lambda})Y=0 are explicit “homogeneous” Coxeter ODEs with a maximally ramified irregular singularity of slope r/nr/n at 0 and unipotent monodromy of type λ\lambda at \infty.

The Deligne–Simpson problem is often stated in the equivalent language of connections on trivializable vector bundles over 1\mathbb{P}^{1}. The meromorphic ODE Y+A(z)Y=0Y^{\prime}+A(z)Y=0 with A(z)A(z) an n×nn\times n matrix corresponds to the meromorphic connection d+A(z)dzd+A(z)dz on a rank nn trivial vector bundle. In the remainder of this paper, we will consider connections instead of ODEs.

Acknowledgements

The authors received support from the SQuaRE program of the American Institute of Mathematics and are grateful to AIM for its hospitality. The authors would like to thank the American Institute of Mathematics for its hospitality during an AIM SQuaRE where much of the work for this paper was completed. N.L. received support from the Roux Institute and the Harold Alfond Foundation. D.S.S. received support from Simons Collaboration Grant 637367. B.N. received support from an AMS–Simons Travel Grant.

2. Nilpotent orbits and the dominance order

2.1. Integer partitions

We define a partition of a positive integer nn to be a multiset of positive integers that sum to nn. Let mλ(x)\operatorname{\mathrm{m}}_{\lambda}(x) denote the multiplicity in a partition λ\lambda of an integer xx. We allow the multiplicity to take the value zero. Define the support Supp(λ)\operatorname{\mathrm{Supp}}(\lambda) of a partition λ\lambda to be the set of integers with positive multiplicity in λ\lambda; i.e., Supp(λ)={x>0:mλ(x)>0}\operatorname{\mathrm{Supp}}(\lambda)=\{x\in\mathbb{Z}_{>0}:\operatorname{\mathrm{m}}_{\lambda}(x)>0\}. If Supp(λ)={λ1,λ2,,λk}\operatorname{\mathrm{Supp}}(\lambda)=\{\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\}, then we represent the partition λ\lambda as {λ1mλ(λ1),λ2mλ(λ2),,λkmλ(λk)}\{\lambda_{1}^{\operatorname{\mathrm{m}}_{\lambda}(\lambda_{1})},\lambda_{2}^{\operatorname{\mathrm{m}}_{\lambda}(\lambda_{2})},\ldots,\lambda_{k}^{\operatorname{\mathrm{m}}_{\lambda}(\lambda_{k})}\}. Define |λ||\lambda| to be the sum xSupp(λ)mλ(x)\sum_{x\in\operatorname{\mathrm{Supp}}(\lambda)}\operatorname{\mathrm{m}}_{\lambda}(x). Thus, if λ\lambda is a partition of nn, then xSupp(λ)(i=1mλ(x)x)=n\sum_{x\in\operatorname{\mathrm{Supp}}(\lambda)}\left(\sum_{i=1}^{\operatorname{\mathrm{m}}_{\lambda}(x)}x\right)=n; each of the |λ||\lambda| summands in the expansion of this double summation is called a part in λ\lambda.

We find it convenient to sometimes view a partition λ\lambda as a monotonically decreasing tuple (λi)i=1|λ|(\lambda_{i})_{i=1}^{|\lambda|} of the parts in λ\lambda. The dominance order (also known as the majorization order, e.g., [22]) on the set of partitions of nn is the partial order \succeq defined by λμ\lambda\succeq\mu if and only if |λ||μ||\lambda|\leq|\mu| and i=1jλii=1jμi\sum_{i=1}^{j}\lambda_{i}\geq\sum_{i=1}^{j}\mu_{i} for all j[1,|λ|]j\in[1,|\lambda|].

2.2. Nilpotent orbits

If RR is a commutative ring with unity, then the general linear group GLn(R)\operatorname{GL}_{n}(R) of degree nn over RR is the group of n×nn\times n matrices over RR with invertible determinant. Its Lie algebra 𝔤𝔩n(R)=Lie(GLn(R))\operatorname{\mathfrak{gl}}_{n}(R)=\operatorname{\mathrm{Lie}}(\operatorname{GL}_{n}(R)) is the vector space of n×nn\times n matrices over RR, equipped with the Lie bracket [,][\cdot,\cdot] defined by [X,Y]=XYYX[X,Y]=XY-YX. We also view elements of 𝔤𝔩n(R)\operatorname{\mathfrak{gl}}_{n}(R) as endomorphisms of RnR^{n}. The adjoint action of GLn(R)\operatorname{GL}_{n}(R) on 𝔤𝔩n(R)\operatorname{\mathfrak{gl}}_{n}(R) is defined by Adg(X)=gXg1\mathrm{Ad}_{g}(X)=gXg^{-1}, for any gGLn(R)g\in\operatorname{GL}_{n}(R) and X𝔤𝔩n(R)X\in\operatorname{\mathfrak{gl}}_{n}(R). In this paper, the term “adjoint orbit” always refers to a complex adjoint orbit. We denote the adjoint orbit of an element X𝔤𝔩n()X\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) by 𝒪X\mathscr{O}_{X}; i.e., 𝒪X={Adg(X)gGLn()}\mathscr{O}_{X}=\{\mathrm{Ad}_{g}(X)\mid g\in\operatorname{GL}_{n}(\mathbb{C})\}.

An element X𝔤𝔩n()X\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) is nilpotent if Xm=0X^{m}=0 for some m>0m>0. The adjoint orbit 𝒪X\mathscr{O}_{X} of a nilpotent element X𝔤𝔩n()X\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) is called a nilpotent orbit. Any nilpotent orbit 𝒪\mathscr{O} contains a block-diagonal representative in Jordan canonical form, which is unique up to permutations of its blocks (known as “Jordan blocks”). Hence, there is a bijective correspondence between the set of nilpotent orbits in 𝔤𝔩n()\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) and the set of partitions of nn, where each nilpotent orbit corresponds with the multiset of its Jordan block sizes. We say that 𝒪\mathscr{O}—and each element of 𝒪\mathscr{O}has type λ\lambda if the sizes of the Jordan blocks for 𝒪\mathscr{O} are given by the partition λ\lambda.

The set of nilpotent orbits are partially ordered: 𝒪1\mathscr{O}^{1} is less than or equal to 𝒪2\mathscr{O}^{2} if and only if 𝒪1\mathscr{O}^{1} is contained in the Zariski closure of 𝒪2\mathscr{O}^{2}. This partial order is known as the closure order. The bijection between nilpotent orbits and partitions described above defines a poset isomorphism when the sets are endowed with the closure order and the dominance order respectively [8].

Next, we define two nilpotent matrices that arise in the study of Coxeter connections (see Section 3).

Definition 2.1.

Let 0<r<n0<r<n. Define Nr𝔤𝔩n()N_{r}\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) (resp. Er𝔤𝔩n()E_{r}\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C})) to be the matrix with ones in each entry of the rrth subdiagonal (resp. (nr)(n-r)th superdiagonal) and zeroes in all other entries.

N1=[000100010],E1=[001000000],N2=[000000100],E2=[010001000]N_{1}=\begin{bmatrix}0&0&0\\ 1&0&0\\ 0&1&0\end{bmatrix},\qquad E_{1}=\begin{bmatrix}0&0&1\\ 0&0&0\\ 0&0&0\end{bmatrix},\quad N_{2}=\begin{bmatrix}0&0&0\\ 0&0&0\\ 1&0&0\end{bmatrix},\quad E_{2}=\begin{bmatrix}0&1&0\\ 0&0&1\\ 0&0&0\end{bmatrix}
Figure 1. The matrices N1N_{1}, E1E_{1}, N2N_{2}, and E2E_{2} in 𝔤𝔩3()\operatorname{\mathfrak{gl}}_{3}(\mathbb{C}).

The following lemma shows that the orbit 𝒪Nr\mathscr{O}_{N_{r}} of NrN_{r} is the minimal orbit with rr blocks and its closure consists of all orbits with at most rr blocks. The proof is given in [24, §2].

Lemma 2.2.

Suppose 0<r<n0<r<n. Let rr^{\prime} be the remainder when dividing nn by rr. Then:

  1. (1)

    NrN_{r} is nilpotent and has type {n/rr,n/rrr}\{\lceil n/r\rceil^{r^{\prime}},\lfloor n/r\rfloor^{r-r^{\prime}}\}; and

  2. (2)

    a partition λ\lambda of nn dominates {n/rr,n/rrr}\{\lceil n/r\rceil^{r^{\prime}},\lfloor n/r\rfloor^{r-r^{\prime}}\} if and only if |λ|r|\lambda|\leq r.

3. Coxeter connections and the Deligne–Simpson Problem

3.1. Connections with maximally ramified singularities

Let VV be a rank nn trivializable vector bundle over the Riemann sphere 1\mathbb{P}^{1} endowed with a meromorphic connection \nabla. After fixing a trivialization, the connection has the form d+M(z)dzzd+M(z)\frac{dz}{z}, where M(z)𝔤𝔩n((z))M(z)\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}(z)) is an n×nn\times n matrix of rational functions. The local behavior at y1y\in\mathbb{P}^{1} is determined by the associated formal connection at yy. Explicitly, this is obtained by expanding M(z)M(z) as a Laurent series in term of a local parameter uu at yy: zyz-y if yy is finite and z1z^{-1} otherwise (i.e., if y=y=\infty). Changing the trivialization of the global or formal vector bundle induces an action on the connection matrix called gauge change. If d+A(u)dzzd+A(u)\frac{dz}{z} is a formal connection with A(u)𝔤𝔩n(((u)))A(u)\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}(\!(u)\!)), then gGLn(((u)))g\in\operatorname{GL}_{n}(\mathbb{C}(\!(u)\!)) acts on the connection operator via g(d+A(u))duu=d+(gA(u)g1)duu(dg)g1g\cdot(d+A(u))\frac{du}{u}=d+(gA(u)g^{-1})\frac{du}{u}-(dg)g^{-1}. In the global case, gGLn()g\in\operatorname{GL}_{n}(\mathbb{C}), so the nonlinear gauge term is zero.

Let yy be a singular point of the connection, and denote the induced formal connection at yy by

d+(Mrur+Mr+1ur+1+)duu,d+(M_{-r}u^{-r}+M_{-r+1}u^{-r+1}+\cdots)\mbox{\small$\displaystyle\frac{du}{u}$},

where Mi𝔤𝔩n()M_{i}\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) and r0r\geq 0. When the leading term MrM_{-r} is well-behaved, it gives important information about the connection. For example, if MrM_{-r} is not nilpotent, then the integer rr is an invariant of the connection known as the slope at yy. The slope can roughly be viewed as a measure of the irregularity of the singularity; a singular point yy is regular singular if the slope is zero, and irregular otherwise. If MrM_{-r} is regular semisimple (i.e., diagonalizable with distinct eigenvalues), then a classical result due to Wasow [29] states that the connection is locally gauge equivalent to a connection of the form

d+(Drur+Dr+1ur+1++D0)duu,d+(D_{-r}u^{-r}+D_{-r+1}u^{-r+1}+\cdots+D_{0})\mbox{\small$\displaystyle\frac{du}{u}$},

where Di𝔤𝔩n()D_{i}\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) are diagonal and DrD_{-r} is regular semisimple. Diagonal representatives of this form are called regular unramified formal types.222Any formal connection can be put into upper triangular form after passing to a finite extension of ((u))\mathbb{C}(\!(u)\!). It is called unramified if this can be done over the ground field and ramified otherwise.

However, there are many singularities for which the leading term of this expansion is nilpotent, regardless of the choice of formal trivialization. Indeed, the slope at yy can be any nonnegative rational number with denominator at most nn, and if this slope is not an integer, the leading term will always be nilpotent. For example, the Frenkel–Gross connection [10]

d+(E1z1+N1)dzzd+(E_{1}z^{-1}+N_{1})\mbox{\small$\displaystyle\frac{dz}{z}$}

has two singular points, a regular singular point at \infty and an irregular singular point at 0 with slope 1/n1/n. This is the smallest possible slope of an irregular singularity [17]. The Frenkel–Gross connection is maximally ramified at y=0y=0, meaning that the slope has the largest possible denominator (i.e., nn) when reduced to lowest terms.

To better understand formal connections with nonintegral slope, Bremer and Sage developed a generalization of leading terms known as fundamental strata [6, 4, 7, 5]. Every formal connection “contains” a fundamental stratum [6, Lemma 4.5], and the slope of a connection is equal to the “depth” of any fundamental stratum it contains ([6, Theorem 4.10],[7, Theorem 2.14]). Regular semisimple leading terms are generalized by regular strata, and a generalization of Wasow’s result states that any connection containing a regular stratum can be “diagonalized” into a ramified formal type [6, 5]. In particular, if a singularity has slope equal to r/nr/n for some rr relatively prime with nn—i.e., if the singularity is maximally ramified—then the connection is locally gauge equivalent to a connection of the form d+p(ω1)dzzd+p(\omega^{-1})\frac{dz}{z}, where pp is a polynomial of degree rr and ω1=E1z1+N1\omega^{-1}=E_{1}z^{-1}+N_{1} [24, Theorem 4.4]. The one-forms p(ω1)dzzp(\omega^{-1})\frac{dz}{z} are the “maximally ramified formal types of slope r/nr/n”.

3.2. Moduli spaces and Coxeter connections

An important problem in the study of meromorphic connections is the extent to which a globally defined connection is determined by its local behavior. Here, “local behavior” consists of:

  • a nonempty, finite set of irregular singular points {xi}i\{x_{i}\}_{i};

  • a corresponding collection 𝐀=(𝒜i)i\mathbf{A}=(\mathscr{A}_{i})_{i} of formal types333A formal type may be viewed as a rational canonical form for a formal connection. See [27] for more details. 𝒜i\mathscr{A}_{i};

  • a finite set of regular singularities {yj}j\{y_{j}\}_{j} disjoint from {xi}i\{x_{i}\}_{i}; and

  • a corresponding collection 𝐎=(𝒪j)j\mathbf{O}=(\mathscr{O}_{j})_{j} of “nonresonant”444An adjoint orbit is called nonresonant if no two eigenvalues differ by a nonzero integer. adjoint orbits 𝒪j\mathscr{O}_{j}.

We consider the category 𝒞(𝐀,𝐎)\operatorname{\mathcal{C}}(\mathbf{A},\mathbf{O}) of connections \nabla defined over the rank nn, trivializable vector bundle VV on 1\mathbb{P}^{1} satisfying the following properties:

  • \nabla has an irregular singularity at each xix_{i}, a regular singularity at each yjy_{j}, and no other singularities;

  • at each xix_{i}, \nabla is “framable” (see, e.g., [26]) and has formal type AiA_{i}; and

  • at each yjy_{j}, \nabla has residue in 𝒪j\mathscr{O}_{j}.

Boalch gave a general construction of the corresponding moduli space (𝐀,𝐎)\operatorname{\mathcal{M}}(\mathbf{A},\mathbf{O}) in the case that each of the formal types are diagonal with regular semisimple leading term [3, Proposition 2.1]. This construction was extended to include “toral” ramified formal types by Bremer and Sage [6, Theorem 5.6].

Here, we give a relatively simple version of this construction for the important special case of connections on 1\mathbb{P}^{1} with a maximally ramified singularity at 0, (possibly) a regular singularity at \infty, and no other singularities [24, Proposition 5.3]. Such connections are called Coxeter connections (for reasons discussed in [18, 24]); they include both the Frenkel–Gross and Airy connections.

Let BGLn()B\subseteq\operatorname{GL}_{n}(\mathbb{C}) be the subgroup of upper triangular matrices. Its Lie algebra 𝔟\mathfrak{b} is the set of upper triangular matrices in 𝔤𝔩n()\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}). Let II denote the “Iwahori subgroup” of GLn([[z]])\operatorname{GL}_{n}(\mathbb{C}[\![z]\!]) corresponding to BB, and let 𝔦\mathfrak{i} denote its Lie algebra. Explicitly, this means that II (resp. 𝔦\mathfrak{i}) is the preimage of BB (resp. 𝔟\mathfrak{b}) via the map GLn([[z]])GLn()\operatorname{GL}_{n}(\mathbb{C}[\![z]\!])\rightarrow\operatorname{GL}_{n}(\mathbb{C}) (resp. 𝔤𝔩n([[z]])𝔤𝔩n()\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}[\![z]\!])\rightarrow\operatorname{\mathfrak{gl}}_{n}(\mathbb{C})) induced by the “evaluation at zero” map z0z\mapsto 0.

Recall that the residue of a one-form (i=rMizi)dzz(\sum_{i=-r}^{\infty}M_{i}z^{i})\frac{dz}{z} with r0r\geq 0 is M0M_{0}.

Proposition 3.1 (Proposition 5.3 in [24]).

Let 𝒜\mathscr{A} be a maximally ramified formal type, and let 𝒪\mathscr{O} be a nonresonant adjoint orbit. Then

(𝒜,𝒪){(α,Y)α𝔤𝔩n([z1])dzz,Y𝒪,α+𝔦Ad(I)(𝒜)+𝔦, and Res(α)+Y=0}/B.\operatorname{\mathcal{M}}(\mathscr{A},\mathscr{O})\cong\{(\alpha,Y)\mid\alpha\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}[z^{-1}])\frac{dz}{z},Y\in\mathscr{O},\alpha+\mathfrak{i}\subseteq\mathrm{Ad}(I)(\mathscr{A})+\mathfrak{i},\text{ and }\operatorname{\mathrm{Res}}(\alpha)+Y=0\}/B.

3.3. The Deligne–Simpson problem

Very little is known about these moduli spaces when ramified singular points are allowed. Indeed, it is not even known when these moduli spaces are nonempty; this is the Deligne–Simpson problem. The original Deligne–Simpson problem, involving connections with only regular singular points, was solved by Crawley–Boevey in 2003 [9]. The unramified version, where unramified singular points are allowed, was solved more recently by Hiroe [14]. Recently, we solved the Deligne–Simpson problem for Coxeter connections [24, Theorem 5.4] together with Kulkarni and Matherne. Theorem 3.2 is a restatement of this result for the special case of homogeneous Coxeter connections, i.e., Coxeter connections where the formal type 𝒜\mathscr{A} is a monomial. Without loss of generality, we can assume that 𝒜=ωrdzz\mathscr{A}=\omega^{-r}\frac{dz}{z} (with gcd(r,n)=1\gcd(r,n)=1[18].

Theorem 3.2.

Let rr and nn be relatively prime positive integers, and let 𝒪λ𝔤𝔩n()\mathscr{O}_{\lambda}\subseteq\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) be the nilpotent orbit of type λ\lambda. Then (ωrdzz,𝒪λ)\operatorname{\mathcal{M}}(\omega^{-r}\frac{dz}{z},\mathscr{O}_{\lambda}) is nonempty if and only if |λ|r|\lambda|\leq r. In particular, this is always the case if r>nr>n.

While the results of [24] determine exactly when (ωrdzz,𝒪λ)\operatorname{\mathcal{M}}(\omega^{-r}\frac{dz}{z},\mathscr{O}_{\lambda}) is nonempty, they do not provide an explicit element of the moduli space. When r>nr>n, it is easy to find such an connection. Indeed, if X𝒪λX\in\mathscr{O}_{\lambda} is strictly upper triangular (for example, if XX is the Jordan canonical form of 𝒪λ\mathscr{O}_{\lambda}), then d+(ωr+X)dzzd+(\omega^{-r}+X)\frac{dz}{z} has the desired local behavior. Constructing an explicit connection in the moduli space is more complicated for r<nr<n and |λ|r|\lambda|\leq r, but it can be translated into a certain problem in matrix theory.

In linear algebra, an “upper matrix completion problem” is a problem where one studies various properties of the cosets A+𝔲A+\mathfrak{u}, where A𝔤𝔩n()A\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) and 𝔲\mathfrak{u} is the space of strictly upper triangular matrices. These problems have attracted great interest in the matrix theory community; see, for example, [1, 11, 12, 30, 2, 23, 25, 22, 21], as well as the survey in [16, Chapter 35]. Here, we are interested in the Upper Nilpotent Completion Problem: given AA nilpotent, determine the nilpotent orbits which intersect the coset A+𝔲A+\mathfrak{u}. The most general result on this problem was conjectured by Rodman and Shalom [25] and proved by Krupnik and Leibman [22]. It states that if μ\mu is the partition of nn corresponding to the nilpotent orbit of AA and λ\lambda is a partition dominating μ\mu, then there exists an element in (A+𝔲)𝒪λ(A+\mathfrak{u})\cap\mathscr{O}_{\lambda}.

Let us now restrict to the case A=NrA=N_{r}, and let μr\mu_{r} be the corresponding partition. It is shown in [24] that the partitions dominating μr\mu_{r} are precisely those with at most rr parts. Let λ\lambda be such a partition. If XX is a strictly upper triangular matrix such that Nr+XN_{r}+X is nilpotent of type λ\lambda, then one can show that d+(ωr+X)dzzd+(\omega^{-r}+X)\frac{dz}{z} corresponds to the element B(α,Y)(ωrdzz,𝒪λ)B\cdot(\alpha,Y)\in\operatorname{\mathcal{M}}(\omega^{-r}\frac{dz}{z},\mathscr{O}_{\lambda}) with α=(ωr+X)dzz\alpha=(\omega^{-r}+X)\frac{dz}{z} and Y=(Nr+X)Y=-(N_{r}+X). Krupnik and Leibman’s result guarantees the existence of such an XX. However, their proof, while constructive in theory, does not seem possible to carry out in practice. Indeed, their algorithm requires repeatedly transforming matrices into special Jordan-like forms, and even when starting with A=NrA=N_{r}, we are not aware of a numerically stable way of carrying out this algorithm.

In the next section, we specify a numerically stable and highly efficient algorithm that generates explicit solutions to the Upper Nilpotent Completion Problem for NrN_{r}, and hence leads to the construction of explicit Coxeter connections with arbitrary specified local behavior.

4. The algorithm

In this section, we introduce our algorithm. The specification of the algorithm (in Section 4.3) and its proof of correctness (in Section 5) are based on many of the same graph-theoretic tools used by Krupnik and Leibman [22]. Section 4.1 mostly recalls terminology and a key result (Proposition 4.2) from [22]. Section 4.2 recalls the notion of a “graph transformation” from [22], and introduces a class of graph transformations that we call “graft transformations”, which are the fundamental operations in our algorithm.

4.1. The graph of a matrix

Let nn be a positive integer, and let VV be a set of nn elements, called vertices. Fix a bijection n:V[1,n]\mathrm{n}\colon V\rightarrow[1,n], called an ordinal function, which imposes a total ordering on VV. We define a 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graph to be a pair consisting of:

  1. (1)

    a subset EV×VE\subseteq V\times V, whose elements are called arrows; and

  2. (2)

    a weight function α:E{0}\alpha\colon E\rightarrow\mathbb{C}-\{0\}.

We define a bijective correspondence graph\mathrm{graph} between 𝔤𝔩n()\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) and the set of 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graphs as follows. Let A=(αi,j)i,j=1nA=(\alpha_{i,j})_{i,j=1}^{n} be an element of 𝔤𝔩n()\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}). Define graph(A)\mathrm{graph}(A) to be the 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graph with the property that two vertices uu and vv are joined by an arrow uvu\mapsto v if and only if αn(v),n(u)0\alpha_{\mathrm{n}(v),\mathrm{n}(u)}\neq 0, and the weight of each arrow uvu\mapsto v is αn(v),n(u)\alpha_{\mathrm{n}(v),\mathrm{n}(u)}. Define matrix\mathrm{matrix} to be the inverse of the function graph\mathrm{graph}.

Remark 4.1.

Starting in Section 4.3, we work exclusively with binary matrices, i.e., matrices where each entry is either zero or one. Each arrow in the 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graph of a binary matrix is weighted by one. Since such 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graphs will be our focus, we assume (for the sake of simplicity) that any arrow uvu\mapsto v lacking an explicit weight is implicitly weighted by one.

We consider embeddings ϕ\phi of 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graphs—or more precisely, their vertex sets—into >0×>0\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}. The image ϕ(v)=(x,y)\phi(v)=(x,y) of a vertex vVv\in V has position x=x(v)x=x(v) and level y=y(v)y=y(v). Henceforth, we use the term “graph” to refer to a 𝔤𝔩n\operatorname{\mathfrak{gl}}_{n}-graph equipped with an embedding into >0×>0\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}. We frequently refer to a vertex in a graph Γ\Gamma via its coordinates, and write nΓ(x,y)\mathrm{n}_{\Gamma}(x,y) to denote the ordinal of ϕ1((x,y))\phi^{-1}((x,y)).

A vertex vv is above (resp. below) a vertex ww if x(v)=x(w)x(v)=x(w) and y(v)=y(w)+1y(v)=y(w)+1 (resp. y(v)=y(w)1y(v)=y(w)-1). An arrow vwv\mapsto w goes down if y(v)>y(w)y(v)>y(w), and goes down-right if y(v)>y(w)y(v)>y(w) and x(v)x(w)x(v)\leq x(w). A graph Γ\Gamma is downward if each of its arrows go down. A graph Γ\Gamma is properly downward if:

  • Γ\Gamma is downward;

  • for every vertex vv with y(v)>1y(v)>1, there is a vertex ww below vv and an arrow vwv\mapsto w; and

  • every arrow vwv\mapsto w with y(v)=y(w)+1y(v)=y(w)+1 goes down-right.

We define the domain Dom(Γ)\mathrm{Dom}(\Gamma) of a graph Γ\Gamma with vertex set VV by Dom(Γ)={x(v)vV}\mathrm{Dom}(\Gamma)=\{x(v)\mid v\in V\}. The column in a graph Γ\Gamma at position ii—or, more concisely, column ii in Γ\Gamma—is {vVx(v)=i}\{v\in V\mid x(v)=i\}. If CC is a column in a graph, then the height of CC is max{y(v)vC}\max\{y(v)\mid v\in C\}. If iDom(Γ)i\in\mathrm{Dom}(\Gamma), then we denote the height of column ii in Γ\Gamma by htΓ(i)\mathrm{ht}_{\Gamma}({i}), and the multiset of heights in Γ\Gamma by Part(Γ)\mathrm{Part}(\Gamma).

Proposition 4.2 ([22, Proposition 3.2]).

Let Γ\Gamma be a graph on nn vertices. If Γ\Gamma is downward, then matrix(Γ)\mathrm{matrix}(\Gamma) is nilpotent. If Γ\Gamma is properly downward, then Part(Γ)\mathrm{Part}(\Gamma) is a partition of nn and matrix(Γ)\mathrm{matrix}(\Gamma) is nilpotent of type Part(Γ)\mathrm{Part}(\Gamma).

We say that a column CC in a properly downward graph Γ\Gamma is a downward path in Γ\Gamma if the following condition holds: for each vertex vCv\in C, there exists an arrow vwv\mapsto w if and only if ww is below vv, and there exists an arrow wvw\mapsto v if and only if ww is above vv.

Let XX be a subset of the vertex set of a graph Γ\Gamma. We say that XX is ordered by type-writer traversal if, for each pair v,wv,w of vertices in XX, n(v)<n(w)\mathrm{n}(v)<\mathrm{n}(w) if and only if one of the following holds: y(v)>y(w)y(v)>y(w), or y(v)=y(w)y(v)=y(w) and x(v)<x(w)x(v)<x(w). Note that if any subset of vertices is removed from a set ordered by type-writer traversal, then the resulting set remains ordered by type-writer traversal.

Lemma 4.3.

Let 0<r<n0<r<n. There exists a unique graph Γ\Gamma such that matrix(Γ)=Nr\mathrm{matrix}(\Gamma)=N_{r}, Γ\Gamma is properly downward, the vertex set is ordered by type-writer traversal, and the following conditions are satisfied:

  1. (1)

    Dom(Γ)=[1,r]\mathrm{Dom}(\Gamma)=[1,r];

  2. (2)

    each column is a downward path;

  3. (3)

    each column has height n/r\lfloor{n/r}\rfloor or n/r\lceil{n/r}\rceil; and

  4. (4)

    if 1i<jr1\leq i<j\leq r, then htΓ(i)htΓ(j)\mathrm{ht}_{\Gamma}({i})\leq\mathrm{ht}_{\Gamma}({j}).

8 5 2 9 6 3 10 7 4 1
Figure 2. The graph Γ\Gamma of N3𝔤𝔩10()N_{3}\in\operatorname{\mathfrak{gl}}_{10}(\mathbb{C}) as described in Lemma 4.3.

4.2. Transformations of a graph

Let Γ\Gamma be a graph, and let ϕ\phi be the associated embedding of the vertex set into >0×>0\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}. Any change of the coordinates of the vertices of Γ\Gamma is called a geometric transformation of Γ\Gamma. In other words, a geometric transformation of Γ\Gamma is the replacement of ϕ\phi with another embedding ϕ\phi^{\prime}. Geometric transformations preserve the matrix associated to Γ\Gamma. More generally, a transformation of a graph Γ\Gamma describes any finite sequence of the following:

  • an addition or deletion of an arrow uvu\mapsto v;

  • a change of the weight αn(v),n(u)\alpha_{\mathrm{n}(v),\mathrm{n}(u)} of an arrow uvu\mapsto v; or

  • a geometric transformation.

We focus on one class of graph transformations that we call “graft transformations”, defined in Definition 4.4. Our algorithm (Algorithm 1) performs a finite sequence of these graft transformations.

Definition 4.4.

A graft transformation takes as input:

  • a properly downward graph Γ\Gamma;

  • two indices s\mathit{s} and c\mathit{c} (which we call the scion and stock, respectively) in Dom(Γ)\mathrm{Dom}(\Gamma) with the property that column c\mathit{c} is a downward path and s<c\mathit{s}<\mathit{c}; and

  • an integer mm satisfying 0<mhtΓ(c)0<m\leq\mathrm{ht}_{\Gamma}({\mathit{c}}) (the number of vertices that will be grafted).

To graft mm vertices in Γ\Gamma from c\mathit{c} to s\mathit{s}, perform the following two transformations on Γ\Gamma:

  • Step 1:

    Add an arrow (c,htΓ(c)m+1)(s,htΓ(s))(\mathit{c},\mathrm{ht}_{\Gamma}({\mathit{c}})-m+1)\mapsto(\mathit{s},\mathrm{ht}_{\Gamma}({\mathit{s}})).

  • Step 2:

    “Translate” the top mm vertices of column c\mathit{c} to the top of column s\mathit{s}; i.e., for each i[1,m]i\in[1,m], change the embedding of vertex (c,htΓ(c)m+i)(\mathit{c},\mathrm{ht}_{\Gamma}({\mathit{c}})-m+i) to (s,htΓ(s)+i)(\mathit{s},\mathrm{ht}_{\Gamma}({\mathit{s}})+i).

Example 4.5.

Let Γ\Gamma be the graph of N3𝔤𝔩10N_{3}\in\operatorname{\mathfrak{gl}}_{10} as described in Lemma 4.3. Figure 3 shows Steps 1 and 2 involved in grafting m=2m=2 vertices in Γ\Gamma from column c=3\mathit{c}=3 to column s=2\mathit{s}=2.

8 5 2 9 6 3 10 7 4 1 8 5 2 9 6 3 10 7 4 1 8 5 2 9 6 3 10 7 4 1 Step 1Step 2
Figure 3. On the left is the graph Γ\Gamma of N3𝔤𝔩10N_{3}\in\operatorname{\mathfrak{gl}}_{10} as described in Lemma 4.3. On the right is the result of grafting m=2m=2 vertices in Γ\Gamma from column c=3\mathit{c}=3 to column s=2\mathit{s}=2 (see Definition 4.4).
Lemma 4.6.

Let Γ1\Gamma^{1} be a properly downward graph, and let c\mathit{c}, s\mathit{s} be indices in Dom(Γ1)\mathrm{Dom}(\Gamma^{1}) with the property that column c\mathit{c} is a downward path and s<c\mathit{s}<\mathit{c}. Let Γ2\Gamma^{2} be the graph that is the result of grafting mm vertices from c\mathit{c} to s\mathit{s}, where 0<mhtΓ1(c)0<m\leq\mathrm{ht}_{\Gamma^{1}}({\mathit{c}}). Then:

  1. (1)

    If m=htΓ1(c)m=\mathrm{ht}_{\Gamma^{1}}({\mathit{c}}), then Dom(Γ2)=Dom(Γ1){c}\mathrm{Dom}(\Gamma^{2})=\mathrm{Dom}(\Gamma^{1})-\{\mathit{c}\}; otherwise Dom(Γ2)=Dom(Γ1)\mathrm{Dom}(\Gamma^{2})=\mathrm{Dom}(\Gamma^{1}).

  2. (2)

    htΓ2(c)=htΓ1(c)m\mathrm{ht}_{\Gamma^{2}}({\mathit{c}})=\mathrm{ht}_{\Gamma^{1}}({\mathit{c}})-m, htΓ2(s)=htΓ1(s)+m\mathrm{ht}_{\Gamma^{2}}({\mathit{s}})=\mathrm{ht}_{\Gamma^{1}}({\mathit{s}})+m, and htΓ2(i)=htΓ1(i)\mathrm{ht}_{\Gamma^{2}}({i})=\mathrm{ht}_{\Gamma^{1}}({i}) for all iDom(Γ2)i\in\mathrm{Dom}(\Gamma^{2}) with i{s,c}i\notin\{\mathit{s},\mathit{c}\}.

  3. (3)

    If column ii is a downward path in Γ1\Gamma^{1} and i{s,c}i\notin\{\mathit{s},\mathit{c}\}, then column ii is a downward path in Γ2\Gamma^{2}.

  4. (4)

    For each i[1,m]i\in[1,m], nΓ2(s,htΓ1(s)+i)=nΓ1(c,htΓ1(c)m+i)\mathrm{n}_{\Gamma^{2}}(\mathit{s},\mathrm{ht}_{\Gamma^{1}}({\mathit{s}})+i)=\mathrm{n}_{\Gamma^{1}}(\mathit{c},\mathrm{ht}_{\Gamma^{1}}({\mathit{c}})-m+i). In particular, nΓ2(s,htΓ2(s))=nΓ1(c,htΓ1(c))\mathrm{n}_{\Gamma^{2}}(\mathit{s},\mathrm{ht}_{\Gamma^{2}}({\mathit{s}}))=\mathrm{n}_{\Gamma^{1}}(\mathit{c},\mathrm{ht}_{\Gamma^{1}}({\mathit{c}})). If (x,y)(x,y) is a vertex in Γ2\Gamma^{2} with xsx\neq\mathit{s}, then (x,y)(x,y) is a vertex in Γ1\Gamma^{1} and nΓ1(x,y)=nΓ2(x,y)\mathrm{n}_{\Gamma^{1}}(x,y)=\mathrm{n}_{\Gamma^{2}}(x,y).

  5. (5)

    If htΓ1(s)>htΓ1(c)m\mathrm{ht}_{\Gamma^{1}}({\mathit{s}})>\mathrm{ht}_{\Gamma^{1}}({\mathit{c}})-m, then Γ2\Gamma^{2} is properly downward.

  6. (6)

    If nΓ1(s,htΓ1(s))<nΓ1(c,htΓ1(c)m+1)\mathrm{n}_{\Gamma^{1}}(\mathit{s},\mathrm{ht}_{\Gamma^{1}}({\mathit{s}}))<\mathrm{n}_{\Gamma^{1}}(\mathit{c},\mathrm{ht}_{\Gamma^{1}}({\mathit{c}})-m+1), then matrix(Γ2)\mathrm{matrix}(\Gamma^{2}) is obtained from matrix(Γ1)\mathrm{matrix}(\Gamma^{1}) by changing a single upper triangular entry from zero to one.

4.3. The algorithm

Our algorithm, Algorithm 1, is specified below. The algorithm takes as input two positive integers rr and nn with r<nr<n, and a partition λ\lambda of nn with at most rr parts. The algorithm consists of the following objects, each of which has a state that changes over the course of execution:

  • a graph Γ\Gamma;

  • two integers s\mathit{s} and c\mathit{c} (which we call “column pointers”); and

  • two multisets 𝖳\mathsf{T} and 𝖲\mathsf{S}.

The initial state of Γ\Gamma is the graph of Nr𝔤𝔩n()N_{r}\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) as described in Lemma 4.3. The column pointers and multisets are initialized in lines 310. The algorithm makes use of three operations on multisets: ++, -, and max\max. To define these operations, let λ\lambda and μ\mu be multisets. The sum λ+μ\lambda+\mu is the multiset with multiplicity function mλ+μ(x)=mλ(x)+mμ(x)\operatorname{\mathrm{m}}_{\lambda+\mu}(x)=\operatorname{\mathrm{m}}_{\lambda}(x)+\operatorname{\mathrm{m}}_{\mu}(x) for all xx. The difference λμ\lambda-\mu is the multiset with multiplicity function mλμ(x)=max{0,mλ(x)mμ(x)}\operatorname{\mathrm{m}}_{\lambda-\mu}(x)=\max\{0,\operatorname{\mathrm{m}}_{\lambda}(x)-\operatorname{\mathrm{m}}_{\mu}(x)\} for all xx. Finally, max(λ)\max(\lambda) is the maximum value in Supp(λ)\operatorname{\mathrm{Supp}}(\lambda).

After initialization, Loop 1 (lines 1132) and Loop 2 (lines 3355) are executed. We refer to these two loops as the primary loops (as opposed to the “Little Loop” defined in lines 3436). Each iteration of a primary loop performs at least one graft transformation to Γ\Gamma, reduces the cardinality of 𝖲\mathsf{S} and/or 𝖳\mathsf{T} by one, and increases the column pointer c\mathit{c} (and possibly increases s\mathit{s} as well). In Section 5, we prove that Algorithm 1 terminates after some finite number of iterations of the primary loops, and that the terminal state of Γ\Gamma satisfies the specified postconditions.

Algorithm 1
1:rr and nn are positive integers with r<nr<n, rr^{\prime} is the remainder when nn is divided by rr,
Γ\Gamma is the graph of Nr𝔤𝔩n()N_{r}\in\operatorname{\mathfrak{gl}}_{n}(\mathbb{C}) as described in Lemma 4.3,
λ\lambda is a partition of nn with at most rr parts
2:matrix(Γ)=Nr+X\mathrm{matrix}(\Gamma)=N_{r}+X where XX is strictly upper triangular,
matrix(Γ)\mathrm{matrix}(\Gamma) is binary and nilpotent of type λ\lambda
3:𝖳{xmλ(x)xSupp(λ),x>n/r}\mathsf{T}\leftarrow\{x^{\operatorname{\mathrm{m}}_{\lambda}(x)}\mid x\in\operatorname{\mathrm{Supp}}(\lambda),x>\lceil n/r\rceil\}
4:if r0r^{\prime}\neq 0 and mλ(n/r)>r\operatorname{\mathrm{m}}_{\lambda}(\lceil{n/r}\rceil)>r^{\prime} then
5:     𝖳𝖳+{n/rmλ(n/r)r}\mathsf{T}\leftarrow\mathsf{T}+\{\lceil{n/r}\rceil^{\operatorname{\mathrm{m}}_{\lambda}(\lceil{n/r}\rceil)-r^{\prime}}\}
6:𝖲{xmλ(x)xSupp(λ),x<n/r}\mathsf{S}\leftarrow\{x^{\operatorname{\mathrm{m}}_{\lambda}(x)}\mid x\in\operatorname{\mathrm{Supp}}(\lambda),x<\lfloor{n/r}\rfloor\}
7:if mλ(n/r)>rr\operatorname{\mathrm{m}}_{\lambda}(\lfloor{n/r}\rfloor)>r-r^{\prime} then
8:     𝖲𝖲+{n/rmλ(n/r)(rr)}\mathsf{S}\leftarrow\mathsf{S}+\{\lfloor{n/r}\rfloor^{\operatorname{\mathrm{m}}_{\lambda}(\lfloor{n/r}\rfloor)-(r-r^{\prime})}\}
9:smin{mλ(n/r),rr}+1\mathit{s}\leftarrow\min\{\operatorname{\mathrm{m}}_{\lambda}(\lfloor{n/r}\rfloor),r-r^{\prime}\}+1
10:cs+1\mathit{c}\leftarrow\mathit{s}+1
11:while 𝖲\mathsf{S} is nonempty do \triangleright Loop 1
12:     if max(𝖳)htΓ(s)=htΓ(c)max(𝖲)+1\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})=\mathrm{ht}_{\Gamma}({\mathit{c}})-\max(\mathsf{S})+1 and htΓ(c)<htΓ(c+1)\mathrm{ht}_{\Gamma}({\mathit{c}})<\mathrm{ht}_{\Gamma}({\mathit{c}+1}) then \triangleright Case 1a
13:          graft htΓ(c+1)max(𝖲)\mathrm{ht}_{\Gamma}({\mathit{c}+1})-\max(\mathsf{S}) vertices from column c+1\mathit{c}+1 to column s\mathit{s}
14:         𝖲𝖲{max(𝖲)}\mathsf{S}\leftarrow\mathsf{S}-\{\max(\mathsf{S})\}
15:         𝖳𝖳{max(𝖳)}\mathsf{T}\leftarrow\mathsf{T}-\{\max(\mathsf{T})\}
16:         sc\mathit{s}\leftarrow\mathit{c}
17:         cc+2\mathit{c}\leftarrow\mathit{c}+2
18:     else if max(𝖳)htΓ(s)>htΓ(c)max(𝖲)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})>\mathrm{ht}_{\Gamma}({\mathit{c}})-\max(\mathsf{S}) then \triangleright Case 1b
19:         graft htΓ(c)max(𝖲)\mathrm{ht}_{\Gamma}({\mathit{c}})-\max(\mathsf{S}) vertices from column c\mathit{c} to column s\mathit{s}
20:         𝖲𝖲{max(𝖲)}\mathsf{S}\leftarrow\mathsf{S}-\{\max(\mathsf{S})\}
21:         cc+1\mathit{c}\leftarrow\mathit{c}+1
22:     else if max(𝖳)htΓ(s)=htΓ(c)max(𝖲)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})=\mathrm{ht}_{\Gamma}({\mathit{c}})-\max(\mathsf{S}) then \triangleright Case 1c
23:         graft htΓ(c)max(𝖲)\mathrm{ht}_{\Gamma}({\mathit{c}})-\max(\mathsf{S}) vertices from column c\mathit{c} to column s\mathit{s}
24:         𝖲𝖲{max(𝖲)}\mathsf{S}\leftarrow\mathsf{S}-\{\max(\mathsf{S})\}
25:         𝖳𝖳{max(𝖳)}\mathsf{T}\leftarrow\mathsf{T}-\{\max(\mathsf{T})\}
26:         sc+1\mathit{s}\leftarrow\mathit{c}+1
27:         cc+2\mathit{c}\leftarrow\mathit{c}+2
28:     else if max(𝖳)htΓ(s)<htΓ(c)max(𝖲)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})<\mathrm{ht}_{\Gamma}({\mathit{c}})-\max(\mathsf{S}) then \triangleright Case 1d
29:         graft max(𝖳)htΓ(s)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}}) vertices from column c\mathit{c} to column s\mathit{s}
30:         𝖳𝖳{max(𝖳)}\mathsf{T}\leftarrow\mathsf{T}-\{\max(\mathsf{T})\}
31:         sc\mathit{s}\leftarrow\mathit{c}
32:         cc+1\mathit{c}\leftarrow\mathit{c}+1      
33:while 𝖳\mathsf{T} is nonempty do \triangleright Loop 2
34:     while max(𝖳)htΓ(s)>n/r\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})>\lceil{n/r}\rceil do \triangleright Little Loop
35:         graft htΓ(c)\mathrm{ht}_{\Gamma}({\mathit{c}}) vertices from column c\mathit{c} to column s\mathit{s}
36:         cc+1\mathit{c}\leftarrow\mathit{c}+1      
37:     if max(𝖳)htΓ(s)>htΓ(c)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})>\mathrm{ht}_{\Gamma}({\mathit{c}}) and htΓ(c+1)=n/r\mathrm{ht}_{\Gamma}({\mathit{c}+1})=\lceil{n/r}\rceil then \triangleright Case 2a
38:         graft htΓ(c+1)\mathrm{ht}_{\Gamma}({\mathit{c}+1}) vertices from column c+1\mathit{c}+1 to column s\mathit{s}
39:         sc\mathit{s}\leftarrow\mathit{c}
40:         cc+2\mathit{c}\leftarrow\mathit{c}+2
41:     else if max(𝖳)htΓ(s)>htΓ(c)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})>\mathrm{ht}_{\Gamma}({\mathit{c}}) and htΓ(c+1)=n/r\mathrm{ht}_{\Gamma}({\mathit{c}+1})=\lfloor{n/r}\rfloor then \triangleright Case 2b
42:         graft htΓ(c)\mathrm{ht}_{\Gamma}({\mathit{c}}) vertices from column c\mathit{c} to column s\mathit{s}
43:         cc+1\mathit{c}\leftarrow\mathit{c}+1
44:         graft one vertex from column c\mathit{c} to column s\mathit{s}
45:         sc\mathit{s}\leftarrow\mathit{c}
46:         cc+1\mathit{c}\leftarrow\mathit{c}+1
47:     else if max(𝖳)htΓ(s)=htΓ(c)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})=\mathrm{ht}_{\Gamma}({\mathit{c}}) then \triangleright Case 2c
48:         graft htΓ(c)\mathrm{ht}_{\Gamma}({\mathit{c}}) vertices from column c\mathit{c} to column s\mathit{s}
49:         sc+1\mathit{s}\leftarrow\mathit{c}+1
50:         cc+2\mathit{c}\leftarrow\mathit{c}+2
51:     else if max(𝖳)htΓ(s)<htΓ(c)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}})<\mathrm{ht}_{\Gamma}({\mathit{c}}) then \triangleright Case 2d
52:         graft max(𝖳)htΓ(s)\max(\mathsf{T})-\mathrm{ht}_{\Gamma}({\mathit{s}}) vertices from column c\mathit{c} to column s\mathit{s}
53:         sc\mathit{s}\leftarrow\mathit{c}
54:         cc+1\mathit{c}\leftarrow\mathit{c}+1      
55:     𝖳𝖳{max(𝖳)}\mathsf{T}\leftarrow\mathsf{T}-\{\max(\mathsf{T})\}

We have implemented Algorithm 1 in the SageMath computer algebra system [28], as well as the NumPy array and matrix computing library [13] for the Python programming language.555Our Python implementation is publicly available at https:/​/github.com/neallivesay/nilpotent-completions. We have tested our SageMath implementation for all positive integers rr and nn and all partitions λ\lambda of nn satisfying 0<r<n300<r<n\leq 30 and |λ|r|\lambda|\leq r.

5. Proof of correctness

In this section, we prove that Algorithm 1 is correct. In other words, we prove that given any valid input, the algorithm is well-defined and terminates, and that the matrix associated to the terminal state of the graph Γ\Gamma satisfies the specified postconditions. With this goal in mind, let rr and nn be positive integers with r<nr<n, let rr^{\prime} be the remainder when nn is divided by rr, and let λ\lambda be a partition with at most rr parts. Initialize a graph Γ\Gamma, multisets 𝖳\mathsf{T} and 𝖲\mathsf{S}, and column pointers s\mathit{s} and c\mathit{c} as specified in lines 310.

Our proof is inductive on the number kk of times that a primary loop has executed; i.e., kk equals the sum of the number of times Loop 1 (lines 1132) has executed with the number of times Loop 2 (lines 3355) has executed. For each object (i.e., a graph, multiset, or pointer) ZZ, let ZkZ^{k} denote the state of ZZ at the end of the kkth iteration, with Z0Z^{0} denoting the state of ZZ after initialization (i.e., after execution of lines 310). Fix once and for all a constant column pointer 𝑒𝑛𝑑=rmin{r,mλ(n/r)}\mathit{end}=r-\min\{r^{\prime},\operatorname{\mathrm{m}}_{\lambda}(\lceil{n/r}\rceil)\}.

The proof involves a simultaneous induction over the following propositional functions of kk:

  • P1(k):P_{1}({k}):

    Each instruction is well-defined in iteration kk.

  • P2(k):P_{2}({k}):

    matrix(Γk)=matrix(Γk1)+X\mathrm{matrix}(\Gamma^{k})=\mathrm{matrix}(\Gamma^{k-1})+X for some strictly upper triangular matrix XX.

  • P3(k):P_{3}({k}):

    𝖲k𝖲k1\mathsf{S}^{k}\subseteq\mathsf{S}^{k-1} and 𝖳k𝖳k1\mathsf{T}^{k}\subseteq\mathsf{T}^{k-1}, with at least one subset relation strict.

  • P4(k):P_{4}({k}):

    Γk\Gamma^{k} is properly downward.

  • P5(k):P_{5}({k}):

    {htΓk(i)iDom(Γk),i[ck,𝑒𝑛𝑑],isk}=λ(𝖳k+𝖲k)\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}=\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k}).

  • P6(k):P_{6}({k}):

    If ii satisfies cki𝑒𝑛𝑑\mathit{c}^{k}\leq i\leq\mathit{end}, then:

    1. (1)

      iDom(Γk)i\in\mathrm{Dom}(\Gamma^{k});

    2. (2)

      column ii is a downward path;

    3. (3)

      htΓk(i)=n/r\mathrm{ht}_{\Gamma^{k}}({i})=\lfloor{n/r}\rfloor or htΓk(i)=n/r\mathrm{ht}_{\Gamma^{k}}({i})=\lceil{n/r}\rceil;

    4. (4)

      if i<j𝑒𝑛𝑑i<j\leq\mathit{end}, then htΓk(i)htΓk(j)\mathrm{ht}_{\Gamma^{k}}({i})\leq\mathrm{ht}_{\Gamma^{k}}({j}); and

    5. (5)

      if 𝖲k\mathsf{S}^{k} is nonempty, then htΓk(i)>max(𝖲k)\mathrm{ht}_{\Gamma^{k}}({i})>\max(\mathsf{S}^{k}), and if 𝖳k\mathsf{T}^{k} is nonempty, then htΓk(i)<max(𝖳k)\mathrm{ht}_{\Gamma^{k}}({i})<\max(\mathsf{T}^{k}).

    Moreover, the set of vertices vv with ckx(v)𝑒𝑛𝑑\mathit{c}^{k}\leq x(v)\leq\mathit{end} are ordered by type-writer traversal.

  • P7(k):P_{7}({k}):

    sk<ck\mathit{s}^{k}<\mathit{c}^{k}. If 𝖳k\mathsf{T}^{k} is nonempty, then sk,ckDom(Γk)\mathit{s}^{k},\mathit{c}^{k}\in\mathrm{Dom}(\Gamma^{k}) and ck𝑒𝑛𝑑\mathit{c}^{k}\leq\mathit{end}.

  • P8(k):P_{8}({k}):

    If 𝖲k\mathsf{S}^{k} is nonempty, then nΓk(sk,htΓk(sk))<nΓk(ck,max(𝖲k)+1)\mathrm{n}_{\Gamma^{k}}(\mathit{s}^{k},\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}}))<\mathrm{n}_{\Gamma^{k}}(\mathit{c}^{k},\max(\mathsf{S}^{k})+1). If 𝖳k\mathsf{T}^{k} is nonempty, then nΓk(sk,htΓk(sk))<nΓk(ck,max{1,htΓk(ck)(max(𝖳k)htΓk(sk))+1})\mathrm{n}_{\Gamma^{k}}(\mathit{s}^{k},\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}}))<\mathrm{n}_{\Gamma^{k}}(\mathit{c}^{k},\max\{1,\mathrm{ht}_{\Gamma^{k}}({\mathit{c}^{k}})-(\max(\mathsf{T}^{k})-\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}}))+1\}).

  • P9(k):P_{9}({k}):

    If 𝖲k\mathsf{S}^{k} is nonempty, then htΓk(sk)>max(𝖲k)\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})>\max(\mathsf{S}^{k}).

  • P10(k):P_{10}({k}):

    If 𝖲k\mathsf{S}^{k} is nonempty, then 𝖳k\mathsf{T}^{k} is nonempty.

For all i[1,3]i\in[1,3] (resp. for all i[4,10]i\in[4,10]), the domain of PiP_{i} is the set of all k1k\geq 1 (resp. all k0k\geq 0) such that 𝖲k1\mathsf{S}^{k-1} or 𝖳k1\mathsf{T}^{k-1} is nonempty. Lemma 5.1 establishes the sufficiency of the universal quantifications of the above propositional functions for proving correctness of Algorithm 1.

Lemma 5.1.

If Pi(0)P_{i}(0) holds for all 4i104\leq i\leq 10, and Pi(k)P_{i}(k) holds for all 1i101\leq i\leq 10 and all k1k\geq 1 with the property that 𝖲k1\mathsf{S}^{k-1} or 𝖳k1\mathsf{T}^{k-1} is nonempty, then the algorithm terminates after some number of steps klastk_{\mathrm{last}}. Moreover, matrix(Γklast)=Nr+X\mathrm{matrix}(\Gamma^{k_{\mathrm{last}}})=N_{r}+X for some strictly upper triangular matrix XX, and matrix(Γklast)\mathrm{matrix}(\Gamma^{k_{\mathrm{last}}}) is nilpotent of type λ\lambda.

Proof.

Suppose that the hypothesis of Lemma 5.1 holds. Define X𝖲={k>0𝖲k1 is nonempty}X_{\mathsf{S}}=\{k\in\mathbb{Z}_{>0}\mid\mathsf{S}^{k-1}\text{ is nonempty}\} and X𝖳={k>0𝖳k1 is nonempty}X_{\mathsf{T}}=\{k\in\mathbb{Z}_{>0}\mid\mathsf{T}^{k-1}\text{ is nonempty}\}. Proposition P1(k)P_{1}({k}) holds, and thus the algorithm runs, for all iterations kX𝖲X𝖳k\in X_{\mathsf{S}}\cup X_{\mathsf{T}}. Since P10(k)P_{10}({k}) holds for all kX𝖲X𝖳k\in X_{\mathsf{S}}\cup X_{\mathsf{T}}, it follows that X𝖲X𝖳X_{\mathsf{S}}\subseteq X_{\mathsf{T}}. Since P3(k)P_{3}({k}) for all kX𝖲X𝖳k\in X_{\mathsf{S}}\cup X_{\mathsf{T}}, it follows that max(X𝖲)max(X𝖳)<\max(X_{\mathsf{S}})\leq\max(X_{\mathsf{T}})<\infty; Loop 1 iterates for all kX𝖲k\in X_{\mathsf{S}}, and Loop 2 iterates for all kX𝖳X𝖲k\in X_{\mathsf{T}}-X_{\mathsf{S}}, with execution terminating after iteration klast=max(X𝖳)k_{\mathrm{last}}=\max(X_{\mathsf{T}}). Proposition P4(klast)P_{4}({k_{\mathrm{last}}}) implies that the terminal state, Γklast\Gamma^{k_{\mathrm{last}}}, of the graph is properly downward. Thus matrix(Γklast)\mathrm{matrix}(\Gamma^{k_{\mathrm{last}}}) is nilpotent of type λ\lambda by Proposition 4.2 and P5(klast)P_{5}({k_{\mathrm{last}}}). Since P2(k)P_{2}({k}) holds for all kk such that 𝖳k1\mathsf{T}^{k-1} is nonempty, it follows that matrix(Γklast)=Nr+X\mathrm{matrix}(\Gamma^{k_{\mathrm{last}}})=N_{r}+X for some strictly upper triangular matrix XX. ∎

The remainder of this section is dedicated to proving the hypothesis of Lemma 5.1 via simultaneous induction. We begin by establishing a basis for induction. Propositions P4(0)P_{4}({0}), P6(0)P_{6}({0}), P7(0)P_{7}({0}), P8(0)P_{8}({0}), and P9(0)P_{9}({0}) follow trivially (mostly as a consequence of Lemma 4.3). Proposition P5(0)P_{5}({0}) holds since {htΓ0(i)iDom(Γ0),i[c0,𝑒𝑛𝑑],is0}={htΓ0(i)i[1,s0)(𝑒𝑛𝑑,r]}={n/rmin{mλ(n/r),rr},n/rmin{r,mλ(n/r)}}=λ(𝖳0+𝖲0)\{\mathrm{ht}_{\Gamma^{0}}({i})\mid i\in\mathrm{Dom}(\Gamma^{0}),i\notin[\mathit{c}^{0},\mathit{end}],i\neq\mathit{s}^{0}\}=\{\mathrm{ht}_{\Gamma^{0}}({i})\mid i\in[1,\mathit{s}^{0})\cup(\mathit{end},r]\}=\{\lfloor{n/r}\rfloor^{\min\{\operatorname{\mathrm{m}}_{\lambda}(\lfloor{n/r}\rfloor),r-r^{\prime}\}},\lceil{n/r}\rceil^{\min\{r^{\prime},\operatorname{\mathrm{m}}_{\lambda}(\lceil{n/r}\rceil)\}}\}=\lambda-(\mathsf{T}^{0}+\mathsf{S}^{0}). To prove P10(0)P_{10}({0}), suppose for a contradiction that 𝖲0\mathsf{S}^{0} is nonempty and 𝖳0\mathsf{T}^{0} is empty. Then at most rr^{\prime} parts in λ\lambda equal n/r\lceil{n/r}\rceil. The remaining parts are at most n/r\lfloor{n/r}\rfloor, with at least one part being strictly less. But this implies n=sum(λ)<(rr)n/r+rn/r=nn=\operatorname{\mathrm{sum}}(\lambda)<(r-r^{\prime})\lfloor{n/r}\rfloor+r^{\prime}\lceil{n/r}\rceil=n, a contradiction.

To prove the inductive step, let kk be a positive integer with the property that 𝖲k1\mathsf{S}^{k-1} is nonempty or 𝖳k1\mathsf{T}^{k-1} is nonempty. Suppose that the algorithm executes for k1k-1 well-defined iterations of the primary loops, and suppose that Pi(j)P_{i}({j}) holds for each 1j<k1\leq j<k and each 1i111\leq i\leq 11. We proceed to prove that Pi(k)P_{i}({k}) is true for all 1i111\leq i\leq 11. One of the following two cases is satisfied at the start of the kkth iteration:

  • Case 1:

    𝖲k1\mathsf{S}^{k-1} is nonempty; or

  • Case 2:

    𝖲k1\mathsf{S}^{k-1} is empty and 𝖳k1\mathsf{T}^{k-1} is nonempty.

Case 1 is considered in Section 5.1 and Case 2 is considered in Section 5.2.

5.1. Suppose Case 1 is satisfied at the start of iteration kk

That is, suppose that 𝖲k1\mathsf{S}^{k-1} is nonempty. Then the kkth iteration is an iteration of Loop 1. Consider the following four conditional expressions:

  • Case 1a:

    max(𝖳k1)htΓk1(sk1)=htΓk1(ck1)max(𝖲k1)+1\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})=\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1})+1

    and htΓk1(ck1)<htΓk1(ck1+1)\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})<\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}+1});

  • Case 1b:

    max(𝖳k1)htΓk1(sk1)>htΓk1(ck1)max(𝖲k1)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})>\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1}) and Case 1a is not satisfied;

  • Case 1c:

    max(𝖳k1)htΓk1(sk1)=htΓk1(ck1)max(𝖲k1)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})=\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1}); and

  • Case 1d:

    max(𝖳k1)htΓk1(sk1)<htΓk1(ck1)max(𝖲k1)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})<\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1}).

Note that P10(k1)P_{10}({k-1}) implies that 𝖳k1\mathsf{T}^{k-1} is nonempty. Hence each of the conditional expressions in Cases 1b, 1c, and 1d are well-defined. To verify that the Case 1a conditional expression is well-defined, it suffices to show that ck1+1𝑒𝑛𝑑\mathit{c}^{k-1}+1\leq\mathit{end} whenever

(1) max(𝖳k1)htΓk1(sk1)=htΓk1(ck1)max(𝖲k1)+1.\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})=\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1})+1.

Suppose, for a contradiction, that (1)(\ref{uniquelabel}) holds but ck1+1>𝑒𝑛𝑑\mathit{c}^{k-1}+1>\mathit{end}. Then P6(k1)P_{6}({k-1}) implies that ck1=𝑒𝑛𝑑\mathit{c}^{k-1}=\mathit{end}. Hence

n={iiDom(Γk1),i[ck1,𝑒𝑛𝑑],isk1}htΓk1(i)+htΓk1(sk1)+htΓk1(ck1)=sum(λ(𝖳k1+𝖲k1))+htΓk1(sk1)+htΓk1(ck1)(by P5(k1))<sum(λ(𝖳k1+𝖲k1))+max(𝖳k1)+max(𝖲k1)(by (1))n,\begin{array}[]{rll}n&=\sum_{\{i\mid i\in\mathrm{Dom}(\Gamma^{k-1}),i\notin[\mathit{c}^{k-1},\mathit{end}],i\neq\mathit{s}^{k-1}\}}\mathrm{ht}_{\Gamma^{k-1}}({i})+\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})+\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})\\ &=\operatorname{\mathrm{sum}}(\lambda-(\mathsf{T}^{k-1}+\mathsf{S}^{k-1}))+\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})+\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})&\text{(by $P_{5}({k-1})$)}\\ &<\operatorname{\mathrm{sum}}(\lambda-(\mathsf{T}^{k-1}+\mathsf{S}^{k-1}))+\max(\mathsf{T}^{k-1})+\max(\mathsf{S}^{k-1})&\text{(by (\ref{uniquelabel}))}\\ &\leq n,\end{array}

a contradiction. Hence ck1+1𝑒𝑛𝑑\mathit{c}^{k-1}+1\leq\mathit{end} if (1) is satisfied, which implies that the conditional expression for Case 1a is well-defined.

It is easily verified that the conditional expressions for Cases 1a–d are mutually exclusive and exhaustive. A different set of instructions executes for each of the four cases. We now prove the inductive step for Case 1a; the proofs for Cases 1b–d are similar and thus are omitted.

5.1.1. Suppose that Case 1a is satisfied at the start of iteration kk.

As discussed above, it follows that ck1+1𝑒𝑛𝑑\mathit{c}^{k-1}+1\leq\mathit{end}. Since htΓk1(ck1)<htΓk1(ck1+1)\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})<\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}+1}), it follows (by P6(k1)P_{6}({k-1})) that htΓk1(ck1)=n/r\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})=\lfloor{n/r}\rfloor, htΓk1(ck1+1)=n/r\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}+1})=\lceil{n/r}\rceil, and n/rn/r\lfloor{n/r}\rfloor\neq\lceil{n/r}\rceil.

We walk through the execution of the Case 1a instructions (i.e., lines 1317). The graph Γk\Gamma^{k} is formed by grafting htΓk1(ck1+1)max(𝖲k1)\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}+1})-\max(\mathsf{S}^{k-1}) vertices in Γk1\Gamma^{k-1} from column ck1+1\mathit{c}^{k-1}+1 to column sk1\mathit{s}^{k-1}. This grafting operation is well-defined since Γk1\Gamma^{k-1} is properly downward and column ck1+1\mathit{c}^{k-1}+1 is a downward path in Γk1\Gamma^{k-1} (by P6(k1)P_{6}({k-1})). Finally, multisets and column pointers are reassigned—resulting in 𝖲k=𝖲k1{max(𝖲k1)}\mathsf{S}^{k}=\mathsf{S}^{k-1}-\{\max(\mathsf{S}^{k-1})\}, 𝖳k=𝖳k1{max(𝖳k1)}\mathsf{T}^{k}=\mathsf{T}^{k-1}-\{\max(\mathsf{T}^{k-1})\}, sk=ck1\mathit{s}^{k}=\mathit{c}^{k-1}, and ck=ck1+2\mathit{c}^{k}=\mathit{c}^{k-1}+2—and iteration kk concludes. Since each of the expressions evaluated and instructions executed during iteration kk are well-defined, P1(k)P_{1}({k}) follows. Proposition P3(k)P_{3}({k}) is clear.

The remainder of the proof for Case 1a largely relies on Lemma 4.6. By P9(k1)P_{9}({k-1}), it follows that htΓk1(sk1)>htΓk1(ck1)(htΓk1(ck1)max(𝖲k1))\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})>\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-(\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1})). Thus Lemma 4.6(5) implies P4(k)P_{4}({k}). It is straight-forward to verify P6(k)P_{6}({k}). Proposition P9(k)P_{9}({k}) follows immediately since sk=ck1Dom(Γk)\mathit{s}^{k}=\mathit{c}^{k-1}\in\mathrm{Dom}(\Gamma^{k}) and htΓk(sk)=n/r\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})=\lfloor{n/r}\rfloor.

Proposition P2(k)P_{2}({k}) follows from the combination of Lemma 4.6(6) and the fact that

nΓk1(sk1,htΓk1(sk1))<nΓk1(ck1,max(𝖲k1)+1)(by P8(k1))<nΓk1(ck1+1,max(𝖲k1)+1)(by P6(k1))=nΓk1(ck1,htΓk1(ck1)(htΓk1(ck1)max(𝖲k1))).\begin{array}[]{rll}\mathrm{n}_{\Gamma^{k-1}}(\mathit{s}^{k-1},\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}}))&<\mathrm{n}_{\Gamma^{k-1}}(\mathit{c}^{k-1},\max(\mathsf{S}^{k-1})+1)&(\text{by }P_{8}({k-1}))\\ &<\mathrm{n}_{\Gamma^{k-1}}(\mathit{c}^{k-1}+1,\max(\mathsf{S}^{k-1})+1)&(\text{by }P_{6}({k-1}))\\ &=\mathrm{n}_{\Gamma^{k-1}}(\mathit{c}^{k-1},\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})\\ &\hskip 28.45274pt-(\mathrm{ht}_{\Gamma^{k-1}}({\mathit{c}^{k-1}})-\max(\mathsf{S}^{k-1}))).\end{array}

Proposition P5(k)P_{5}({k}) follows since

{htΓk(i)iDom(Γk),i[ck,𝑒𝑛𝑑],isk}={htΓk1(i)iDom(Γk1),i[ck1,𝑒𝑛𝑑],isk1}+{htΓk(sk1),htΓk(ck1)}=λ(𝖳k1+𝖲k1)+{max(𝖲k1),max(𝖳k1)}=λ((𝖳k1max(𝖳k1))+(𝖲k1max(𝖲k1)))=λ(𝖳k+𝖲k),\begin{array}[]{rll}&\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}\\ &=\{\mathrm{ht}_{\Gamma^{k-1}}({i})\mid i\in\mathrm{Dom}(\Gamma^{k-1}),i\notin[\mathit{c}^{k-1},\mathit{end}],i\neq\mathit{s}^{k-1}\}+\{\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k-1}}),\mathrm{ht}_{\Gamma^{k}}({\mathit{c}^{k-1}})\}\\ &=\lambda-(\mathsf{T}^{k-1}+\mathsf{S}^{k-1})+\{\max(\mathsf{S}^{k-1}),\max(\mathsf{T}^{k-1})\}\\ &=\lambda-((\mathsf{T}^{k-1}-\max(\mathsf{T}^{k-1}))+(\mathsf{S}^{k-1}-\max(\mathsf{S}^{k-1})))\\ &=\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k}),\end{array}

with the second equality following by P5(k1)P_{5}({k-1}). To prove P7(k)P_{7}({k}), it suffices to show ck𝑒𝑛𝑑\mathit{c}^{k}\leq\mathit{end} if 𝖳k\mathsf{T}^{k} is nonempty. Suppose, for a contradiction, that 𝖳k\mathsf{T}^{k} is nonempty and ck>𝑒𝑛𝑑\mathit{c}^{k}>\mathit{end}. Then

n=iDom(Γk)htΓk(i)=sum(λ(𝖳k+𝖲k))+htΓk(sk)(by P5(k))nmax(𝖳k)+n/r(since 𝖳k is nonempty)<n(since max(𝖳k)>n/r).\begin{array}[]{rll}n&=\sum_{i\in\mathrm{Dom}(\Gamma^{k})}\mathrm{ht}_{\Gamma^{k}}({i})\\ &=\operatorname{\mathrm{sum}}(\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k}))+\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})&(\text{by }P_{5}({k}))\\ &\leq n-\max(\mathsf{T}^{k})+\lfloor{n/r}\rfloor&\text{(since $\mathsf{T}^{k}$ is nonempty)}\\ &<n&\text{(since $\max(\mathsf{T}^{k})>\lfloor{n/r}\rfloor$)}.\end{array}

This is a contradiction, so P7(k)P_{7}({k}) follows. Then P8(k)P_{8}({k}) follows from Lemma 4.6 and P6(k1)P_{6}({k-1}).

Finally, we prove P10(k)P_{10}({k}). Suppose that 𝖲k\mathsf{S}^{k} is nonempty. Suppose, for a proof by contradiction, that 𝖳k\mathsf{T}^{k} is empty. Then

|λ(𝖳k+𝖲k)|+|𝖲k|=|λ|=r=|Dom(Γk)|=|{iiDom(Γk),i[ck,𝑒𝑛𝑑],isk}|+|{sk}[ck,𝑒𝑛𝑑]|=|{htΓk(i)iDom(Γk),i[ck,𝑒𝑛𝑑],isk}|+|{sk}[ck,𝑒𝑛𝑑]|=|λ(𝖳k+𝖲k)|+|{sk}[ck,𝑒𝑛𝑑]|.\begin{array}[]{rll}|\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k})|+|\mathsf{S}^{k}|&=|\lambda|=r=|\mathrm{Dom}(\Gamma^{k})|\\ &=|\{i\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}|+|\{\mathit{s}^{k}\}\cup[\mathit{c}^{k},\mathit{end}]|\\ &=|\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}|+|\{\mathit{s}^{k}\}\cup[\mathit{c}^{k},\mathit{end}]|\\ &=|\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k})|+|\{\mathit{s}^{k}\}\cup[\mathit{c}^{k},\mathit{end}]|.\end{array}

It follows that

(2) |{sk}[ck,𝑒𝑛𝑑]|=|𝖲k|.|\{\mathit{s}^{k}\}\cup[\mathit{c}^{k},\mathit{end}]|=|\mathsf{S}^{k}|.

Moreover, since

sum(λ(𝖳k+𝖲k))+sum(𝖳k+𝖲k)=sum(λ)=n=iDom(Γk)htΓk(i)=iDom(Γk),i[ck,𝑒𝑛𝑑],iskhtΓk(i)+htΓk(sk)+i=ck𝑒𝑛𝑑htΓk(i)=sum(λ(𝖳k+𝖲k))+htΓk(sk)+i=ck𝑒𝑛𝑑htΓk(i),\begin{array}[]{rll}\operatorname{\mathrm{sum}}(\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k}))+\operatorname{\mathrm{sum}}(\mathsf{T}^{k}+\mathsf{S}^{k})&=\operatorname{\mathrm{sum}}(\lambda)=n=\sum_{i\in\mathrm{Dom}(\Gamma^{k})}\mathrm{ht}_{\Gamma^{k}}({i})\\ &=\sum_{i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}}\mathrm{ht}_{\Gamma^{k}}({i})+\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})+\sum_{i=\mathit{c}^{k}}^{\mathit{end}}\mathrm{ht}_{\Gamma^{k}}({i})\\ &=\operatorname{\mathrm{sum}}(\lambda-(\mathsf{T}^{k}+\mathsf{S}^{k}))+\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})+\sum_{i=\mathit{c}^{k}}^{\mathit{end}}\mathrm{ht}_{\Gamma^{k}}({i}),\end{array}

it follows that

(3) sum(𝖲k)=htΓk(sk)+i=ck𝑒𝑛𝑑htΓk(i).\operatorname{\mathrm{sum}}(\mathsf{S}^{k})=\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})+\sum_{i=\mathit{c}^{k}}^{\mathit{end}}\mathrm{ht}_{\Gamma^{k}}({i}).

Note that htΓk(sk)>max(𝖲k)\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})>\max(\mathsf{S}^{k}) by P9(k)P_{9}({k}). Also htΓk(i)>max(𝖲k)\mathrm{ht}_{\Gamma^{k}}({i})>\max(\mathsf{S}^{k}) for all i[ck,𝑒𝑛𝑑]i\in[\mathit{c}^{k},\mathit{end}]. Hence

max(𝖲k)|𝖲k|<htΓk(sk)+i=ck𝑒𝑛𝑑htΓk(i)(by (2))=sum(𝖲k)(by (3))max(𝖲k)|𝖲k|,\begin{array}[]{rll}\max(\mathsf{S}^{k})\cdot|\mathsf{S}^{k}|&<\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})+\sum_{i=\mathit{c}^{k}}^{\mathit{end}}\mathrm{ht}_{\Gamma^{k}}({i})&(\text{by (\ref{eqone})})\\ &=\operatorname{\mathrm{sum}}(\mathsf{S}^{k})&(\text{by (\ref{eqtwo})})\\ &\leq\max(\mathsf{S}^{k})\cdot|\mathsf{S}^{k}|,\end{array}

a contradiction. Proposition P10(k)P_{10}({k}) follows.

5.2. Suppose Case 2 is satisfied at the start of iteration kk.

That is, suppose that 𝖲k1\mathsf{S}^{k-1} is empty and 𝖳k1\mathsf{T}^{k-1} is nonempty. Then the kkth iteration of a primary loop is an iteration of Loop 2. Three of the propositional functions have simpler, logically equivalent formulations for this case:

  • P3(k):P_{3}({k}):

    𝖲k\mathsf{S}^{k} is empty and 𝖳k𝖳k1\mathsf{T}^{k}\subsetneq\mathsf{T}^{k-1}.

  • P5(k):P_{5}({k}):

    {htΓk(i)iDom(Γk),i[ck,𝑒𝑛𝑑],isk}=λ𝖳k\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}=\lambda-\mathsf{T}^{k}.

  • P8(k):P_{8}({k}):

    If 𝖳k\mathsf{T}^{k} is nonempty, then nΓk(sk,htΓk(sk))<nΓk(ck,max{1,htΓk(ck)(max(𝖳k)htΓk(sk))+1})\mathrm{n}_{\Gamma^{k}}(\mathit{s}^{k},\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}}))<\mathrm{n}_{\Gamma^{k}}(\mathit{c}^{k},\max\{1,\mathrm{ht}_{\Gamma^{k}}({\mathit{c}^{k}})-(\max(\mathsf{T}^{k})-\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}}))+1\}).

Observe that if 𝖲k\mathsf{S}^{k} is empty, then P9(k)P_{9}({k}) and P10(k)P_{10}({k}) follow trivially.

The first step in executing the instruction set for Loop 2 is the execution of the Little Loop (lines 3436). Let Γk1,\Gamma^{{k-1},{\ell}} (resp. ck1,\mathit{c}^{{k-1},{\ell}}) denote the state of the graph (resp. column pointer) at the end of the \ellth iteration of the Little Loop during the kkth iteration, with Γk1,0\Gamma^{{k-1},{0}} (resp. ck1,0\mathit{c}^{{k-1},{0}}) denoting the initial state Γk1\Gamma^{k-1} (resp. ck1\mathit{c}^{k-1}). Define the following propositional functions:

  • Q1k():Q_{1}^{k}({\ell}):

    Each instruction is well-defined in iteration \ell of the Little Loop during iteration kk.

  • Q2k():Q_{2}^{k}({\ell}):

    matrix(Γk1,)=matrix(Γk1,1)+X\mathrm{matrix}(\Gamma^{{k-1},{\ell}})=\mathrm{matrix}(\Gamma^{{k-1},{\ell-1}})+X for some strictly upper triangular matrix XX.

  • Q3k():Q_{3}^{k}({\ell}):

    htΓk1,(sk1)>htΓk1,1(sk1)\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\mathrm{ht}_{\Gamma^{{k-1},{\ell-1}}}({\mathit{s}^{k-1}}).

  • Q4k():Q_{4}^{k}({\ell}):

    Γk1,l\Gamma^{{k-1},{l}} is properly downward.

  • Q5k():Q_{5}^{k}({\ell}):

    {htΓk1,(i)iDom(Γk1,),i[ck1,,𝑒𝑛𝑑],isk1}=λ𝖳k1\{\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})\mid i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell}}),i\notin[\mathit{c}^{{k-1},{\ell}},\mathit{end}],i\neq\mathit{s}^{k-1}\}=\lambda-\mathsf{T}^{k-1}.

  • Q6k():Q_{6}^{k}({\ell}):

    If ii satisfies ck1,i𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell}}\leq i\leq\mathit{end}, then:

    1. (1)

      iDom(Γk1,)i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell}});

    2. (2)

      column ii is a downward path;

    3. (3)

      htΓk1,(i)=n/r\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})=\lfloor{n/r}\rfloor or htΓk1,(i)=n/r\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})=\lceil{n/r}\rceil;

    4. (4)

      if i<j𝑒𝑛𝑑i<j\leq\mathit{end}, then htΓk1,(i)htΓk1,(j)\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})\leq\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({j}); and

    5. (5)

      if 𝖳k\mathsf{T}^{k} is nonempty, then htΓk1,(i)<max(𝖳k)\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})<\max(\mathsf{T}^{k}) for all i[ck1,,𝑒𝑛𝑑]i\in[\mathit{c}^{{k-1},{\ell}},\mathit{end}].

    The set of vertices vv with ck1,x(v)𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell}}\leq x(v)\leq\mathit{end} are ordered by type-writer traversal.

  • Q7k():Q_{7}^{k}({\ell}):

    If htΓk1,(sk1)<max(𝖳k1)\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})<\max(\mathsf{T}^{k-1}), then ck1,𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell}}\leq\mathit{end}.

  • Q8k():Q_{8}^{k}({\ell}):

    nΓk1,(sk1,htΓk1,(sk1))\mathrm{n}_{\Gamma^{{k-1},{\ell}}}(\mathit{s}^{k-1},\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}}))
    <nΓk1,(ck1,,max{1,htΓk1,(ck1,)(max(𝖳k)htΓk1,(sk1))+1})<\mathrm{n}_{\Gamma^{{k-1},{\ell}}}(\mathit{c}^{{k-1},{\ell}},\max\{1,\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{c}^{{k-1},{\ell}}})-(\max(\mathsf{T}^{k})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}}))+1\}).

We prove Qik(0)Q_{i}^{k}({0}) for all i[4,8]i\in[4,8], and Qik()Q_{i}^{k}({\ell}) for all i[1,8]i\in[1,8] and for all \ell such that max(𝖳k1)htΓk1,(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil. Propositions Qik(0)Q_{i}^{k}({0}) for i[4,8]i\in[4,8] follow immediately from Pi(k1)P_{i}({k-1}) for i[4,8]i\in[4,8], which are assumed as part of our inductive hypothesis. Let >0\ell>0 satisfy max(𝖳k1)htΓk1,(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil, and suppose for an inductive hypothesis that Qik(1)Q_{i}^{k}({\ell-1}) holds for all i[1,8]i\in[1,8]. We step through the two instructions (lines 35 and 36) in the \ellth iteration of the Little Loop. First, column ck1,1\mathit{c}^{{k-1},{\ell-1}} is grafted to column sk1\mathit{s}^{k-1}, to form the graph Γk1,\Gamma^{{k-1},{\ell}}. Since Γk1,1\Gamma^{{k-1},{\ell-1}} is properly downward by Q1k1(1)Q_{1}^{k-1}({\ell-1}) and sk1ck1,1\mathit{s}^{k-1}\neq\mathit{c}^{{k-1},{\ell-1}}, it follows that the grafting transformation is well-defined. Next, ck1,\mathit{c}^{{k-1},{\ell}} is set to ck1,1+1\mathit{c}^{{k-1},{\ell-1}}+1, and iteration \ell of the Little Loop concludes.

Propositions Qik()Q_{i}^{k}({\ell}) for each i[1,6]i\in[1,6] follow immediately, mostly as direct consequences of Lemma 4.6. To prove Q8k()Q_{8}^{k}({\ell}), observe that Lemma 4.6(4) implies nΓk1,(sk1,htΓk1,(sk1))=nΓk1,1(ck1,1,htΓk1,1(ck1,1))\mathrm{n}_{\Gamma^{{k-1},{\ell}}}(\mathit{s}^{k-1},\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}}))=\mathrm{n}_{\Gamma^{{k-1},{\ell-1}}}(\mathit{c}^{{k-1},{\ell-1}},\mathrm{ht}_{\Gamma^{{k-1},{\ell-1}}}({\mathit{c}^{{k-1},{\ell-1}}})). But this is less than nΓk1,(ck1,,max{1,htΓk1,(ck1,)(max(𝖳k)htΓk1,(sk1))+1})\mathrm{n}_{\Gamma^{{k-1},{\ell}}}(\mathit{c}^{{k-1},{\ell}},\max\{1,\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{c}^{{k-1},{\ell}}})-(\max(\mathsf{T}^{k})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}}))+1\}). Since ck1,1<ck1,\mathit{c}^{{k-1},{\ell-1}}<\mathit{c}^{{k-1},{\ell}} and htΓk1,1(ck1,1)htΓk1,(ck1,)(max(𝖳k)htΓk1,(sk1))\mathrm{ht}_{\Gamma^{{k-1},{\ell-1}}}({\mathit{c}^{{k-1},{\ell-1}}})\geq\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{c}^{{k-1},{\ell}}})-(\max(\mathsf{T}^{k})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})), the claim follows. To prove Q7k()Q_{7}^{k}({\ell}), suppose, for a contradiction, that ck1,>𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell}}>\mathit{end}. Then

nmax(𝖳k1)<nhtΓk1,(sk1)=iDom(Γk1,),isk1htΓk1,(i)=iDom(Γk1,),i[ck1,,𝑒𝑛𝑑],isk1htΓk1,(i)=sum(λ𝖳k1)(by Q5k())nmax(𝖳k1),\begin{array}[]{rll}n-\max(\mathsf{T}^{k-1})&<n-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})\\ &=\sum_{i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell}}),i\neq\mathit{s}^{k-1}}\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})\\ &=\sum_{i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell}}),i\notin[\mathit{c}^{{k-1},{\ell}},\mathit{end}],i\neq\mathit{s}^{k-1}}\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({i})\\ &=\operatorname{\mathrm{sum}}(\lambda-\mathsf{T}^{k-1})&\text{(by $Q_{5}^{k}({\ell})$)}\\ &\leq n-\max(\mathsf{T}^{k-1}),\end{array}

a contradiction. This concludes the proof of Qik()Q_{i}^{k}({\ell}) for all i[1,8]i\in[1,8] and for all \ell such that max(𝖳k1)htΓk1,(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil.

Since Q1k()Q_{1}^{k}({\ell}) and Q3k()Q_{3}^{k}({\ell}) holds for all \ell such that max(𝖳k1)htΓk1,(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil, it follows that each iteration of the Little Loop is well-defined, and that the Little Loop eventually terminates. Define last\ell_{\mathrm{last}} to be max{max(𝖳k1)htΓk1,1(sk1)>n/r}\max\{\ell\mid\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell-1}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil\} if max(𝖳k1)htΓk1(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil—i.e., if the Little Loop iterated at least once—and zero otherwise.

Exactly one of the following cases holds:

  • Case 2a:

    max(𝖳k1)htΓk1(sk1)>htΓk1,last(ck1,last)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})>\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}}) and htΓk1,last(ck1,last+1)=n/r\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1})=\lceil{n/r}\rceil;

  • Case 2b:

    max(𝖳k1)htΓk1(sk1)>htΓk1,last(ck1,last)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})>\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}}) and htΓk1,last(ck1,last+1)=n/r\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1})=\lfloor{n/r}\rfloor;

  • Case 2c:

    max(𝖳k1)htΓk1(sk1)=htΓk1,last(ck1,last)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})=\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}}); and

  • Case 2d:

    max(𝖳k1)htΓk1(sk1)<htΓk1,last(ck1,last)\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})<\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}}).

To verify that the conditional expressions for Cases 2a and 2b are well-defined, we show that ck1,last+1Dom(Γk1,last)\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1\in\mathrm{Dom}(\Gamma^{{k-1},{\ell_{\mathrm{last}}}}) if

(4) max(𝖳k1)htΓk1(sk1)>htΓk1,last(ck1,last).\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})>\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}}).

Assume that (4) holds. Suppose, for a contradiction, that ck1,last+1>𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1>\mathit{end}. Then Q6k1(last)Q_{6}^{k-1}({\ell_{\mathrm{last}}}) implies that ck1,last=𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}=\mathit{end}. Hence

n=iDom(Γk1,last),i[ck1,last,𝑒𝑛𝑑],isk1htΓk1,last(i)+htΓk1,last(ck1,last)+htΓk1,last(sk1)=sum(λ𝖳k1)+htΓk1,last(ck1,last)+htΓk1,last(sk1)(by Q5k(last))<sum(λ𝖳k1)+max(𝖳k1)(by (4))n,\begin{array}[]{rll}n&=\sum_{i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell_{\mathrm{last}}}}),i\notin[\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}},\mathit{end}],i\neq\mathit{s}^{k-1}}\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({i})\\ &\hskip 28.45274pt+\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}})+\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{s}^{k-1}})\\ &=\operatorname{\mathrm{sum}}(\lambda-\mathsf{T}^{k-1})+\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}})+\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{s}^{k-1}})&\text{(by $Q_{5}^{k}({\ell_{\mathrm{last}}})$)}\\ &<\operatorname{\mathrm{sum}}(\lambda-\mathsf{T}^{k-1})+\max(\mathsf{T}^{k-1})&\text{(by (\ref{distinctivelabel}))}\\ &\leq n,\end{array}

a contradiction. The claim follows.

A different set of instructions executes for each case. We prove the inductive step for Case 2a in Section 5.2.1; Cases 2b–d can be proved similarly.

5.2.1. Suppose Case 2a holds.

Then htΓk1,last(ck1,last)=n/r\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}})=\lfloor{n/r}\rfloor, htΓk1,last(ck1,last+1)=n/r\mathrm{ht}_{\Gamma^{{k-1},{\ell_{\mathrm{last}}}}}({\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1})=\lceil{n/r}\rceil, and max(𝖳k1)htΓk1(sk1)=n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{k-1}}({\mathit{s}^{k-1}})=\lceil{n/r}\rceil. The Case 2a instruction set is executed. The graph Γk\Gamma^{k} is formed by grafting column ck1,last+1\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1 in Γk1,last\Gamma^{{k-1},{\ell_{\mathrm{last}}}} to sk1\mathit{s}^{k-1}. Recall from the discussion immediately preceding this section that ck1,last+1𝑒𝑛𝑑\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1\leq\mathit{end}. Hence column ck1,last+1\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1 is a downward path by Q6k1(last)Q_{6}^{k-1}({\ell_{\mathrm{last}}}). Since Γk1,last\Gamma^{{k-1},{\ell_{\mathrm{last}}}} is properly downward by Q4k1(last)Q_{4}^{k-1}({\ell_{\mathrm{last}}}), and since column ck1,last+1\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1 is a downward path, it follows that the grafting operation is well-defined. Lemma 4.6(2) implies that htΓk(sk1)=max(𝖳k1)\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k-1}})=\max(\mathsf{T}^{k-1}). The next instructions set sk=ck1,last\mathit{s}^{k}=\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}, ck=ck1,last+1\mathit{c}^{k}=\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1, and 𝖳k=𝖳k1{max(𝖳k1)}\mathsf{T}^{k}=\mathsf{T}^{k-1}-\{\max(\mathsf{T}^{k-1})\}.

Proposition P1(k)P_{1}({k}) follows since each of the expressions and instructions above are well-defined, and since Q1(k)Q_{1}^{\ell}({k}) holds for all \ell such that max(𝖳k1)htΓk1,(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil. Proposition P3(k)P_{3}({k}) is immediately clear. Proposition P4(k)P_{4}({k}) follows from Lemma 4.6(5). Since Q2k()Q_{2}^{k}({\ell}) holds for all \ell such that max(𝖳k1)htΓk1,(sk1)>n/r\max(\mathsf{T}^{k-1})-\mathrm{ht}_{\Gamma^{{k-1},{\ell}}}({\mathit{s}^{k-1}})>\lceil{n/r}\rceil, it follows that P2(k)P_{2}({k}). It is straight-forward to verify that P6(k)P_{6}({k}) follows from Lemma 4.6 and Q6k(last)Q_{6}^{k}({\ell_{\mathrm{last}}}). Proposition P8(k)P_{8}({k}) is a straight-forward consequence of Q6k(last)Q_{6}^{k}({\ell_{\mathrm{last}}}) and Lemma 4.6(4).

To prove P5(k)P_{5}({k}), first observe that Lemma 4.6(1) implies that

{iiDom(Γk),i[ck,𝑒𝑛𝑑],isk}={iiDom(Γk1,last){ck1,last+1},i[ck1,last+2,𝑒𝑛𝑑],ick1,last}={iiDom(Γk1,last),i[ck1,last,𝑒𝑛𝑑]}.\begin{array}[]{rll}&\{i\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}\\ &=\{i\mid i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell_{\mathrm{last}}}})-\{\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+1\},i\notin[\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}+2,\mathit{end}],i\neq\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}}\}\\ &=\{i\mid i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell_{\mathrm{last}}}}),i\notin[\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}},\mathit{end}]\}.\\ \end{array}

Hence

{htΓk(i)iDom(Γk),i[ck,𝑒𝑛𝑑],isk}={htΓk(i)iDom(Γk1,last),i[ck1,last,𝑒𝑛𝑑]}={htΓk(i)iDom(Γk1,last),i[ck1,last,𝑒𝑛𝑑],isk1}+{htΓk(sk1)}=(λ𝖳k1)+{max(𝖳k1)}(by Q5k(last))=λ𝖳k.\begin{array}[]{rll}&\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}\}\\ &=\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell_{\mathrm{last}}}}),i\notin[\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}},\mathit{end}]\}\\ &=\{\mathrm{ht}_{\Gamma^{k}}({i})\mid i\in\mathrm{Dom}(\Gamma^{{k-1},{\ell_{\mathrm{last}}}}),i\notin[\mathit{c}^{{k-1},{\ell_{\mathrm{last}}}},\mathit{end}],i\neq\mathit{s}^{k-1}\}+\{\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k-1}})\}\\ &=(\lambda-\mathsf{T}^{k-1})+\{\max(\mathsf{T}^{k-1})\}\hskip 28.45274pt\text{(by $Q_{5}^{k}({\ell_{\mathrm{last}}})$)}\\ &=\lambda-\mathsf{T}^{k}.\end{array}

Proposition P5(k)P_{5}({k}) follows.

Finally, we prove P7(k)P_{7}({k}). Assume that 𝖳k\mathsf{T}^{k} is nonempty. Suppose, for a contradiction, that ck>𝑒𝑛𝑑\mathit{c}^{k}>\mathit{end}. Then

nn/r=iDom(Γk)htΓk(i)htΓk(sk)=iDom(Γk),i[ck,𝑒𝑛𝑑],iskhtΓk(i)=sum(λ𝖳k)(by P5(k))nmax(𝖳k),\begin{array}[]{rll}n-\lfloor{n/r}\rfloor&=\sum_{i\in\mathrm{Dom}(\Gamma^{k})}\mathrm{ht}_{\Gamma^{k}}({i})-\mathrm{ht}_{\Gamma^{k}}({\mathit{s}^{k}})\\ &=\sum_{i\in\mathrm{Dom}(\Gamma^{k}),i\notin[\mathit{c}^{k},\mathit{end}],i\neq\mathit{s}^{k}}\mathrm{ht}_{\Gamma^{k}}({i})\\ &=\operatorname{\mathrm{sum}}(\lambda-\mathsf{T}^{k})&\text{(by $P_{5}({k})$)}\\ &\leq n-\max(\mathsf{T}^{k}),\end{array}

a contradiction since max(𝖳k)>n/r\max(\mathsf{T}^{k})>\lfloor{n/r}\rfloor. Proposition P7(k)P_{7}({k}) follows.

References

  • [1] J. A. Ball, I. Gohberg, L. Rodman, and T. Shalom, On the eigenvalues of matrices with given upper triangular part, Integr. Equat. Oper. Th. 13 (1990), no. 4, 488–497.
  • [2] A. Berman and M. Krupnik, Spectrum preserving lower triangular completions-the nonnegative nilpotent case, Electron. J. Linear Algebra 2 (1997), 9–16.
  • [3] P. Boalch, Symplectic manifolds and isomonodromic deformations, Adv. Math. 163 (2001), 137–205.
  • [4] C. Bremer and D. S. Sage, Isomonodromic deformations of connections with singularities of parahoric formal type, Comm. Math. Phys. 313 (2012), 175–208.
  • [5] by same author, Flat G{\mathrm{G}}-bundles and regular strata for reductive groups, arXiv:1309.6060, 2013.
  • [6] by same author, Moduli spaces of irregular singular connections, Int. Math. Res. Not. IMRN (2013), 1800–1872.
  • [7] by same author, A theory of minimal KK-types for flat GG-bundles, Int. Math. Res. Not. IMRN (2018), 3507–3555.
  • [8] D. H. Collingwood and W. M. McGovern, Nilpotent orbits in semisimple Lie algebras, Van Nostrand Reinhold Mathematics Series, Van Nostrand Reinhold Co., New York, 1993.
  • [9] W. Crawley-Boevey, On matrices in prescribed conjugacy classes with no common invariant subspace and sum zero, Duke Math. J. 118 (2003), 339–352.
  • [10] E. Frenkel and B. Gross, A rigid irregular connection on the projective line, Ann. of Math. (2) 170 (2009), 1469–1512.
  • [11] I. Gohberg, L. Rodman, T. Shalom, and H. J. Woerdeman, Bounds for eigenvalues and singular values of matrix completions, Linear and Multilinear Algebra 33 (1992), no. 3–4, 233–249.
  • [12] L. Gurvits, L. Rodman, and T. Shalom, Controllability and completion of partial upper triangular matrices over rings, Linear Algebra Appl. 172 (1992), 135–149.
  • [13] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, J. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant, Array programming with NumPy, Nature 585 (2020), no. 7825, 357–362.
  • [14] K. Hiroe, Linear differential equations on the Riemann sphere and representations of quivers, Duke Math. J. 166 (2017), 855–935.
  • [15] K. Hiroe and D. Yamakawa, Moduli spaces of meromorphic connections and quiver varieties, Adv. Math. 266 (2014), 120–151.
  • [16] L. Hogben and A. Wangsness, Matrix completion problems, Handbook of Linear Algebra (L. Hogben, ed.), Chapman & Hall/CRC Press, 1st ed., 2007.
  • [17] M. Kamgarpour and D. S. Sage, A geometric analogue of a conjecture of Gross and Reeder, Amer. J. Math. 141 (2019), 1457–1476.
  • [18] by same author, Rigid connections on 1\mathbb{P}^{1} via the Bruhat–Tits building, Proc. Lond. Math. Soc. 122 (2021), 359–376.
  • [19] N. M. Katz, Gauss sums, Kloosterman sums, and monodromy groups., Ann. Math. Stud., vol. 116, Princeton University Press, 1988.
  • [20] by same author, Exponential sums and differential equations., Ann. Math. Stud., vol. 124, Princeton University Press, 1990.
  • [21] M. Krupnik, Jordan structures of upper equivalent matrices, Linear Algebra Appl. 261 (1997), 167–172.
  • [22] M. Krupnik and A. Leibman, Jordan structures of strictly lower triangular completions of nilpotent matrices, Integr. Equat. Oper. Th. 23 (1995), 459–471.
  • [23] M. Krupnik and L. Rodman, Completions of partial jordan and hessenberg matrices, Linear Algebra Appl. 212–213 (1994), 267–287.
  • [24] M. C. Kulkarni, N. Livesay, J. P. Matherne, B. Nguyen, and D. S. Sage, The Deligne–Simpson problem for connections on 𝔾m\mathbb{G}_{m} with a maximally ramified singularity, Adv. Math. 408 (2022), 108596.
  • [25] L. Rodman and T. Shalom, Jordan forms of completions of partial upper triangular matrices, Linear Algebra Appl. 168 (1992), 221–249.
  • [26] D. S. Sage, Regular strata and moduli spaces of irregular singular connections, New trends in analysis and interdisciplinary applications, Trends Math. Res. Perspect., Birkhäuser/Springer, Cham, 2017, pp. 69–75.
  • [27] by same author, Meromorphic connections on the projective line with specified local behavior, arXiv:2212.14108, 2022.
  • [28] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.1), 2017, https://www.sagemath.org.
  • [29] W. Wasow, Asymptotic expansions for ordinary differential equations, Wiley Interscience, New York, 1976.
  • [30] H. J. Woerdeman, Minimal rank completions for block matrices, Linear Algebra Appl. 121 (1989), 105–122.