Explicit constructions of connections on the projective line with a maximally ramified irregular singularity
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 matrices2020 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 is whether there exists a differential equation with specified local behavior at its singularities. Consider the ODE , where is an matrix whose coefficients are rational functions over . This ODE determines a collection of local differential equations by expanding as a Laurent series at each point in . 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 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.e., is the matrix with ones on the superdiagonal, in the lower-left entry, and zeroes elsewhere—then the Airy equation is and the Kloosterman equation is .
In this special case of the Deligne–Simpson problem, the specified local behavior at and is given by a polynomial of degree with and an adjoint orbit (or simply a Jordan canonical form). The polynomial determines a “formal type of slope ” for the irregular singular point at , while the adjoint orbit corresponds to the residue of the regular singular point at . For example, for the Kloosterman equation, , , and the Jordan canonical form is a single nilpotent Jordan block. For the Airy equation, , , and the adjoint orbit at is the zero orbit (meaning that 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 be a nilpotent matrix, let be the partition of with parts corresponding to the Jordan block sizes of , and let be a partition of dominating . Show that there exists a strictly upper triangular matrix such that is nilpotent with Jordan block sizes .
To describe how this works, let us restrict to the simplest case where , , and the adjoint orbit is nilpotent with Jordan form corresponding to a partition of . In this case, we showed in [24] that there exists a connection with the specified local behavior if and only if has at most parts, or equivalently if and only if the Jordan canonical form has at most blocks. For example, suppose that , the matrix with ones in each entry of the th diagonal and zeroes in all other entries. A (constructive) solution to the Upper Nilpotent Completion Problem with determines an explicit ODE with the given local behavior. Indeed, if is strictly upper triangular such that is nilpotent of type , then 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 . If is any partition of with at most parts, the output of this algorithm is a strictly upper triangular binary matrix such that is nilpotent of type . As a result, the ODEs are explicit “homogeneous” Coxeter ODEs with a maximally ramified irregular singularity of slope at and unipotent monodromy of type at .
The Deligne–Simpson problem is often stated in the equivalent language of connections on trivializable vector bundles over . The meromorphic ODE with an matrix corresponds to the meromorphic connection on a rank 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 to be a multiset of positive integers that sum to . Let denote the multiplicity in a partition of an integer . We allow the multiplicity to take the value zero. Define the support of a partition to be the set of integers with positive multiplicity in ; i.e., . If , then we represent the partition as . Define to be the sum . Thus, if is a partition of , then ; each of the summands in the expansion of this double summation is called a part in .
We find it convenient to sometimes view a partition as a monotonically decreasing tuple of the parts in . The dominance order (also known as the majorization order, e.g., [22]) on the set of partitions of is the partial order defined by if and only if and for all .
2.2. Nilpotent orbits
If is a commutative ring with unity, then the general linear group of degree over is the group of matrices over with invertible determinant. Its Lie algebra is the vector space of matrices over , equipped with the Lie bracket defined by . We also view elements of as endomorphisms of . The adjoint action of on is defined by , for any and . In this paper, the term “adjoint orbit” always refers to a complex adjoint orbit. We denote the adjoint orbit of an element by ; i.e., .
An element is nilpotent if for some . The adjoint orbit of a nilpotent element is called a nilpotent orbit. Any nilpotent orbit 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 and the set of partitions of , where each nilpotent orbit corresponds with the multiset of its Jordan block sizes. We say that —and each element of —has type if the sizes of the Jordan blocks for are given by the partition .
The set of nilpotent orbits are partially ordered: is less than or equal to if and only if is contained in the Zariski closure of . 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 . Define (resp. ) to be the matrix with ones in each entry of the th subdiagonal (resp. th superdiagonal) and zeroes in all other entries.
The following lemma shows that the orbit of is the minimal orbit with blocks and its closure consists of all orbits with at most blocks. The proof is given in [24, §2].
Lemma 2.2.
Suppose . Let be the remainder when dividing by . Then:
-
(1)
is nilpotent and has type ; and
-
(2)
a partition of dominates if and only if .
3. Coxeter connections and the Deligne–Simpson Problem
3.1. Connections with maximally ramified singularities
Let be a rank trivializable vector bundle over the Riemann sphere endowed with a meromorphic connection . After fixing a trivialization, the connection has the form , where is an matrix of rational functions. The local behavior at is determined by the associated formal connection at . Explicitly, this is obtained by expanding as a Laurent series in term of a local parameter at : if is finite and otherwise (i.e., if ). Changing the trivialization of the global or formal vector bundle induces an action on the connection matrix called gauge change. If is a formal connection with , then acts on the connection operator via . In the global case, , so the nonlinear gauge term is zero.
Let be a singular point of the connection, and denote the induced formal connection at by
where and . When the leading term is well-behaved, it gives important information about the connection. For example, if is not nilpotent, then the integer is an invariant of the connection known as the slope at . The slope can roughly be viewed as a measure of the irregularity of the singularity; a singular point is regular singular if the slope is zero, and irregular otherwise. If 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
where are diagonal and 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 . 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 can be any nonnegative rational number with denominator at most , and if this slope is not an integer, the leading term will always be nilpotent. For example, the Frenkel–Gross connection [10]
has two singular points, a regular singular point at and an irregular singular point at with slope . This is the smallest possible slope of an irregular singularity [17]. The Frenkel–Gross connection is maximally ramified at , meaning that the slope has the largest possible denominator (i.e., ) 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 for some relatively prime with —i.e., if the singularity is maximally ramified—then the connection is locally gauge equivalent to a connection of the form , where is a polynomial of degree and [24, Theorem 4.4]. The one-forms are the “maximally ramified formal types of slope ”.
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 ;
-
•
a corresponding collection of formal types333A formal type may be viewed as a rational canonical form for a formal connection. See [27] for more details. ;
-
•
a finite set of regular singularities disjoint from ; and
-
•
a corresponding collection of “nonresonant”444An adjoint orbit is called nonresonant if no two eigenvalues differ by a nonzero integer. adjoint orbits .
We consider the category of connections defined over the rank , trivializable vector bundle on satisfying the following properties:
-
•
has an irregular singularity at each , a regular singularity at each , and no other singularities;
-
•
at each , is “framable” (see, e.g., [26]) and has formal type ; and
-
•
at each , has residue in .
Boalch gave a general construction of the corresponding moduli space 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 with a maximally ramified singularity at , (possibly) a regular singularity at , 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 be the subgroup of upper triangular matrices. Its Lie algebra is the set of upper triangular matrices in . Let denote the “Iwahori subgroup” of corresponding to , and let denote its Lie algebra. Explicitly, this means that (resp. ) is the preimage of (resp. ) via the map (resp. ) induced by the “evaluation at zero” map .
Recall that the residue of a one-form with is .
Proposition 3.1 (Proposition 5.3 in [24]).
Let be a maximally ramified formal type, and let be a nonresonant adjoint orbit. Then
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 is a monomial. Without loss of generality, we can assume that (with ) [18].
Theorem 3.2.
Let and be relatively prime positive integers, and let be the nilpotent orbit of type . Then is nonempty if and only if . In particular, this is always the case if .
While the results of [24] determine exactly when is nonempty, they do not provide an explicit element of the moduli space. When , it is easy to find such an connection. Indeed, if is strictly upper triangular (for example, if is the Jordan canonical form of ), then has the desired local behavior. Constructing an explicit connection in the moduli space is more complicated for and , 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 , where and 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 nilpotent, determine the nilpotent orbits which intersect the coset . 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 is the partition of corresponding to the nilpotent orbit of and is a partition dominating , then there exists an element in .
Let us now restrict to the case , and let be the corresponding partition. It is shown in [24] that the partitions dominating are precisely those with at most parts. Let be such a partition. If is a strictly upper triangular matrix such that is nilpotent of type , then one can show that corresponds to the element with and . Krupnik and Leibman’s result guarantees the existence of such an . 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 , 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 , 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 be a positive integer, and let be a set of elements, called vertices. Fix a bijection , called an ordinal function, which imposes a total ordering on . We define a -graph to be a pair consisting of:
-
(1)
a subset , whose elements are called arrows; and
-
(2)
a weight function .
We define a bijective correspondence between and the set of -graphs as follows. Let be an element of . Define to be the -graph with the property that two vertices and are joined by an arrow if and only if , and the weight of each arrow is . Define to be the inverse of the function .
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 -graph of a binary matrix is weighted by one. Since such -graphs will be our focus, we assume (for the sake of simplicity) that any arrow lacking an explicit weight is implicitly weighted by one.
We consider embeddings of -graphs—or more precisely, their vertex sets—into . The image of a vertex has position and level . Henceforth, we use the term “graph” to refer to a -graph equipped with an embedding into . We frequently refer to a vertex in a graph via its coordinates, and write to denote the ordinal of .
A vertex is above (resp. below) a vertex if and (resp. ). An arrow goes down if , and goes down-right if and . A graph is downward if each of its arrows go down. A graph is properly downward if:
-
•
is downward;
-
•
for every vertex with , there is a vertex below and an arrow ; and
-
•
every arrow with goes down-right.
We define the domain of a graph with vertex set by . The column in a graph at position —or, more concisely, column in —is . If is a column in a graph, then the height of is . If , then we denote the height of column in by , and the multiset of heights in by .
Proposition 4.2 ([22, Proposition 3.2]).
Let be a graph on vertices. If is downward, then is nilpotent. If is properly downward, then is a partition of and is nilpotent of type .
We say that a column in a properly downward graph is a downward path in if the following condition holds: for each vertex , there exists an arrow if and only if is below , and there exists an arrow if and only if is above .
Let be a subset of the vertex set of a graph . We say that is ordered by type-writer traversal if, for each pair of vertices in , if and only if one of the following holds: , or and . 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 . There exists a unique graph such that , is properly downward, the vertex set is ordered by type-writer traversal, and the following conditions are satisfied:
-
(1)
;
-
(2)
each column is a downward path;
-
(3)
each column has height or ; and
-
(4)
if , then .
4.2. Transformations of a graph
Let be a graph, and let be the associated embedding of the vertex set into . Any change of the coordinates of the vertices of is called a geometric transformation of . In other words, a geometric transformation of is the replacement of with another embedding . Geometric transformations preserve the matrix associated to . More generally, a transformation of a graph describes any finite sequence of the following:
-
•
an addition or deletion of an arrow ;
-
•
a change of the weight of an arrow ; 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 ;
-
•
two indices and (which we call the scion and stock, respectively) in with the property that column is a downward path and ; and
-
•
an integer satisfying (the number of vertices that will be grafted).
To graft vertices in from to , perform the following two transformations on :
-
Step 1:
Add an arrow .
-
Step 2:
“Translate” the top vertices of column to the top of column ; i.e., for each , change the embedding of vertex to .
Example 4.5.
Let be the graph of as described in Lemma 4.3. Figure 3 shows Steps 1 and 2 involved in grafting vertices in from column to column .
Lemma 4.6.
Let be a properly downward graph, and let , be indices in with the property that column is a downward path and . Let be the graph that is the result of grafting vertices from to , where . Then:
-
(1)
If , then ; otherwise .
-
(2)
, , and for all with .
-
(3)
If column is a downward path in and , then column is a downward path in .
-
(4)
For each , . In particular, . If is a vertex in with , then is a vertex in and .
-
(5)
If , then is properly downward.
-
(6)
If , then is obtained from 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 and with , and a partition of with at most parts. The algorithm consists of the following objects, each of which has a state that changes over the course of execution:
-
•
a graph ;
-
•
two integers and (which we call “column pointers”); and
-
•
two multisets and .
The initial state of is the graph of as described in Lemma 4.3. The column pointers and multisets are initialized in lines 3–10. The algorithm makes use of three operations on multisets: , , and . To define these operations, let and be multisets. The sum is the multiset with multiplicity function for all . The difference is the multiset with multiplicity function for all . Finally, is the maximum value in .
After initialization, Loop 1 (lines 11–32) and Loop 2 (lines 33–55) are executed. We refer to these two loops as the primary loops (as opposed to the “Little Loop” defined in lines 34–36). Each iteration of a primary loop performs at least one graft transformation to , reduces the cardinality of and/or by one, and increases the column pointer (and possibly increases 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 satisfies the specified postconditions.
is the graph of as described in Lemma 4.3,
is a partition of with at most parts
is binary and nilpotent of type
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 and and all partitions of satisfying and .
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 satisfies the specified postconditions. With this goal in mind, let and be positive integers with , let be the remainder when is divided by , and let be a partition with at most parts. Initialize a graph , multisets and , and column pointers and as specified in lines 3–10.
Our proof is inductive on the number of times that a primary loop has executed; i.e., equals the sum of the number of times Loop 1 (lines 11–32) has executed with the number of times Loop 2 (lines 33–55) has executed. For each object (i.e., a graph, multiset, or pointer) , let denote the state of at the end of the th iteration, with denoting the state of after initialization (i.e., after execution of lines 3–10). Fix once and for all a constant column pointer .
The proof involves a simultaneous induction over the following propositional functions of :
-
Each instruction is well-defined in iteration .
-
for some strictly upper triangular matrix .
-
and , with at least one subset relation strict.
-
is properly downward.
-
.
-
If satisfies , then:
-
(1)
;
-
(2)
column is a downward path;
-
(3)
or ;
-
(4)
if , then ; and
-
(5)
if is nonempty, then , and if is nonempty, then .
Moreover, the set of vertices with are ordered by type-writer traversal.
-
(1)
-
. If is nonempty, then and .
-
If is nonempty, then . If is nonempty, then .
-
If is nonempty, then .
-
If is nonempty, then is nonempty.
For all (resp. for all ), the domain of is the set of all (resp. all ) such that or 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 holds for all , and holds for all and all with the property that or is nonempty, then the algorithm terminates after some number of steps . Moreover, for some strictly upper triangular matrix , and is nilpotent of type .
Proof.
Suppose that the hypothesis of Lemma 5.1 holds. Define and . Proposition holds, and thus the algorithm runs, for all iterations . Since holds for all , it follows that . Since for all , it follows that ; Loop 1 iterates for all , and Loop 2 iterates for all , with execution terminating after iteration . Proposition implies that the terminal state, , of the graph is properly downward. Thus is nilpotent of type by Proposition 4.2 and . Since holds for all such that is nonempty, it follows that for some strictly upper triangular matrix . ∎
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 , , , , and follow trivially (mostly as a consequence of Lemma 4.3). Proposition holds since . To prove , suppose for a contradiction that is nonempty and is empty. Then at most parts in equal . The remaining parts are at most , with at least one part being strictly less. But this implies , a contradiction.
To prove the inductive step, let be a positive integer with the property that is nonempty or is nonempty. Suppose that the algorithm executes for well-defined iterations of the primary loops, and suppose that holds for each and each . We proceed to prove that is true for all . One of the following two cases is satisfied at the start of the th iteration:
-
Case 1:
is nonempty; or
-
Case 2:
is empty and 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
That is, suppose that is nonempty. Then the th iteration is an iteration of Loop 1. Consider the following four conditional expressions:
-
Case 1a:
and ;
-
Case 1b:
and Case 1a is not satisfied;
-
Case 1c:
; and
-
Case 1d:
.
Note that implies that 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 whenever
(1) |
Suppose, for a contradiction, that holds but . Then implies that . Hence
a contradiction. Hence 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 .
As discussed above, it follows that . Since , it follows (by ) that , , and .
We walk through the execution of the Case 1a instructions (i.e., lines 13–17). The graph is formed by grafting vertices in from column to column . This grafting operation is well-defined since is properly downward and column is a downward path in (by ). Finally, multisets and column pointers are reassigned—resulting in , , , and —and iteration concludes. Since each of the expressions evaluated and instructions executed during iteration are well-defined, follows. Proposition is clear.
The remainder of the proof for Case 1a largely relies on Lemma 4.6. By , it follows that . Thus Lemma 4.6(5) implies . It is straight-forward to verify . Proposition follows immediately since and .
Proposition follows from the combination of Lemma 4.6(6) and the fact that
Proposition follows since
with the second equality following by . To prove , it suffices to show if is nonempty. Suppose, for a contradiction, that is nonempty and . Then
This is a contradiction, so follows. Then follows from Lemma 4.6 and .
Finally, we prove . Suppose that is nonempty. Suppose, for a proof by contradiction, that is empty. Then
It follows that
(2) |
Moreover, since
it follows that
(3) |
Note that by . Also for all . Hence
a contradiction. Proposition follows.
5.2. Suppose Case 2 is satisfied at the start of iteration .
That is, suppose that is empty and is nonempty. Then the th iteration of a primary loop is an iteration of Loop 2. Three of the propositional functions have simpler, logically equivalent formulations for this case:
-
is empty and .
-
.
-
If is nonempty, then .
Observe that if is empty, then and follow trivially.
The first step in executing the instruction set for Loop 2 is the execution of the Little Loop (lines 34–36). Let (resp. ) denote the state of the graph (resp. column pointer) at the end of the th iteration of the Little Loop during the th iteration, with (resp. ) denoting the initial state (resp. ). Define the following propositional functions:
-
Each instruction is well-defined in iteration of the Little Loop during iteration .
-
for some strictly upper triangular matrix .
-
.
-
is properly downward.
-
.
-
If satisfies , then:
-
(1)
;
-
(2)
column is a downward path;
-
(3)
or ;
-
(4)
if , then ; and
-
(5)
if is nonempty, then for all .
The set of vertices with are ordered by type-writer traversal.
-
(1)
-
If , then .
-
.
We prove for all , and for all and for all such that . Propositions for follow immediately from for , which are assumed as part of our inductive hypothesis. Let satisfy , and suppose for an inductive hypothesis that holds for all . We step through the two instructions (lines 35 and 36) in the th iteration of the Little Loop. First, column is grafted to column , to form the graph . Since is properly downward by and , it follows that the grafting transformation is well-defined. Next, is set to , and iteration of the Little Loop concludes.
Propositions for each follow immediately, mostly as direct consequences of Lemma 4.6. To prove , observe that Lemma 4.6(4) implies . But this is less than . Since and , the claim follows. To prove , suppose, for a contradiction, that . Then
a contradiction. This concludes the proof of for all and for all such that .
Since and holds for all such that , it follows that each iteration of the Little Loop is well-defined, and that the Little Loop eventually terminates. Define to be if —i.e., if the Little Loop iterated at least once—and zero otherwise.
Exactly one of the following cases holds:
-
Case 2a:
and ;
-
Case 2b:
and ;
-
Case 2c:
; and
-
Case 2d:
.
To verify that the conditional expressions for Cases 2a and 2b are well-defined, we show that if
(4) |
Assume that (4) holds. Suppose, for a contradiction, that . Then implies that . Hence
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 , , and . The Case 2a instruction set is executed. The graph is formed by grafting column in to . Recall from the discussion immediately preceding this section that . Hence column is a downward path by . Since is properly downward by , and since column is a downward path, it follows that the grafting operation is well-defined. Lemma 4.6(2) implies that . The next instructions set , , and .
Proposition follows since each of the expressions and instructions above are well-defined, and since holds for all such that . Proposition is immediately clear. Proposition follows from Lemma 4.6(5). Since holds for all such that , it follows that . It is straight-forward to verify that follows from Lemma 4.6 and . Proposition is a straight-forward consequence of and Lemma 4.6(4).
Finally, we prove . Assume that is nonempty. Suppose, for a contradiction, that . Then
a contradiction since . Proposition 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 -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 -types for flat -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 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 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.