11institutetext:  School of Mathematics, Cardiff University, Wales, United
Kingdom 22institutetext: Department of Mathematics, ETH Zürich, Switzerland

# On Matrices over a Polynomial Ring with Restricted Subdeterminants

Marcel Celaya 11 Stefan Kuhlmann 22 Robert Weismantel 22

Abstract. This paper introduces a framework to study discrete optimization
problems which are parametric in the following sense: their constraint
matrices correspond to matrices over the ring $\mathbb{Z}[x]$ of polynomials
in one variable. We investigate in particular matrices whose subdeterminants
all lie in a fixed set $S\subseteq\mathbb{Z}[x]$. Such matrices, which we call
_totally $S$-modular matrices_, are closed with respect to taking submatrices,
so it is natural to look at minimally non-totally $S$-modular matrices which
we call _forbidden minors for $S$_. Among other results, we prove that if $S$
is finite, then the set of all determinants attained by a forbidden minor for
$S$ is also finite. Specializing to the integers, we subsequently obtain the
following positive complexity result: for all but finitely many values of
$a\in\mathbb{Z}$, if a totally $\pm\\{0,1,a,a+1,2a+1\\}$-modular constraint
matrix has entries in $a$ and $a+1$, then the corresponding recognition
problem and the integer linear optimization problem can be solved in
polynomial time.

##  1 Introduction

For a matrix $\bm{M}$, let $\Delta(\bm{M})$ denote the maximal absolute value
of a subdeterminant of $\bm{M}$. Since decades it is well-known that the
number $\Delta(\bm{M})$ plays a crucial role in understanding complexity
questions related to integer programming problems whose associated constraint
matrix is $\bm{M}$. Important example include bounds on the diameter of
polyhedra [7], questions about the proximity between optimal LP solutions and
optimal integral solutions [3, 8], bounds on the size of the minimal support
of integer vectors in standard form programs [1, 2, 4, 10], and running time
functions for dynamic programming algorithms [11]. Largely unexplored however
remain two fundamental algorithmic questions: Given a finite set
$S\subseteq\mathbb{N}$ of allowed values for the subdeterminants in absolute
value of the matrix $\bm{M}$:

  1. 1.

What is the complexity of solving an ILP with associated constraint matrix
$\bm{M}$ in dependence of $\left|S\right|$ and $\max_{s\in S}s$? (Optimization
problem)

  2. 2.

How can we efficiently verify whether a matrix $\bm{M}$ has all its
subdeterminants in absolute value in $S$? (Recognition problem)

If $S=\\{0,1\\}$, both questions have been answered. Indeed, a famous theorem
of Hoffmann and Kruskal [13] and a decomposition theorem of Seymour for
totally unimodular matrices [24] allow us to tackle both questions. We refer
to [23] for further theory concerning totally unimodular matrices. If
$S=\\{0,1,2\\}$, there exists a polynomial time algorithm to solve Question 1
[6]. In this generality, further optimization results are not known to us.
There are other important results when one imposes additional restrictions on
the constraint matrix. For instance, if one assumes that each row of the
constraint matrix contains at most two non-zero entries, there is a polynomial
time algorithm for the optimization problem [12]. Other polynomial time
algorithms can be derived if the constraint matrix is $\\{0,\Delta\\}$-modular
for $\Delta\leq 4$ [17, 18].

The main reason why there are only few general results on optimization and
recognition problems is due to the lack of understanding integral matrices
with bounded subdeterminants. The purpose of this paper is to develop a
framework to investigate the structure of those matrices. Our point of
departure is to consider matrices with entries being elements in
$\mathbb{Z}[x]$, the ring of polynomials with integral coefficients in one
indeterminate $x$. Moreover, we specify a set of polynomials
$S\subseteq\mathbb{Z}[x]$ that corresponds to the allowed polynomials for the
subdeterminants of those matrices. All other polynomials in
$\mathbb{Z}[x]\backslash S$ are forbidden. Let us make this precise.

###### Definition 1

Let $S\subseteq\mathbb{Z}[x]$ be finite. Let $1\leq m,n$. A matrix
$\bm{M}\in\mathbb{Z}[x]^{m\times n}$ is _totally $S$-modular_ if every
$k\times k$ subdeterminant of $\bm{M}$ is contained in $S$ for $1\leq
k\leq\min\\{m,n\\}$. Let $2\leq l$. The matrix
$\bm{M}\in\mathbb{Z}[x]^{l\times l}$ is a _forbidden minor for_ $S$ if every
$(l-1)\times(l-1)$ submatrix is totally $S$-modular but $\det\bm{M}\notin S$.
By $F(S)$, we denote the set of all polynomials that arise as a determinant of
some forbidden minor for $S$.

The case $\mathbb{Z}$ can be recovered by restricting $S$ to consist of
constant polynomials.

One advantage of operating in $\mathbb{Z}[x]$ is that we can extract a certain
decomposition, Theorem 1.1, and simplify arguments due to arithmetic
properties of $\mathbb{Z}[x]$. This allows us to make progress towards
Question 1 and 2 if we evaluate the polynomials in $\bm{M}$ and $S$ at
integers. The disadvantage of our approach is that there are finitely many
values of $a\in\mathbb{Z}$ for which our statements do not hold. For those
values $a$, there exist a polynomial in $F(S)$ and a polynomial in $S$ whose
evaluations at $a$ admit the same value. This implies that $F(S(a))$ cannot be
the set of all forbidden minors for $S(a)$; cf. Lemma 3.

Let us remark that there is a related line of research. It involves
understanding the matroids that admit a representation as a
$\pm\\{0,1,2,\ldots,\Delta\\}$-modular matrix for $\Delta\geq 2$ [19, 20]. We
emphasize that there are crucial differences between this approach and the
totally $S$-modular direction proposed in this work. For instance, here the
notion of a forbidden minor depends on the concrete representation of the
matrix.

We will later be able to make general statements about the structure of the
set $F(S)$. However, when it comes to Questions 1 and 2, we need further
restrictions to derive general statements.

###  1.1 The smallest non-trivial cases

Given the requirements that $x\in S$ and $S$ is as small as possible, it turns
out that one of the first non-trivial cases is to study matrices with entries
in $\\{x,x+1\\}$ with an associated set $S=\pm\\{0,1,x,x+1,2x+1\\}$. Let us
next argue why this is the case. We assume that $0\in S$. This assumption can
be made without loss of generality because, if $0\notin S$, we are quite
restricted; see, for instance, [5]. So let $S=\pm\\{0,x\\}$. One can check
that there is no invertible totally $S$-modular matrix in dimension larger
than one. Hence, we may assume that $S$ contains at least three different
polynomials, i.e., $S=\pm\\{0,x,y\\}$ for $y\in\mathbb{Z}[x]$. The only ways
of choosing $y$ such that the set of totally $S$-modular matrices contains
invertible instances in every dimension is either $y=1$ or $y=x+1$. The
smallest $S$ which contains both of these families is $S=\pm\\{0,1,x,x+1\\}$.
One can show that the non-constant entries of any totally $S$-modular matrix
$\bm{M}$ form a submatrix $\bm{M}^{\prime}$ of $\bm{M}$, and this submatrix is
also a submatrix of the following matrix up to sign, row and column
permutations, and duplicates:

$\displaystyle\begin{pmatrix}x+1&\dots&\dots&x+1\\\ \vdots&&\iddots&x\\\
\vdots&\iddots&\iddots&\vdots\\\ x+1&x&\dots&x\end{pmatrix}.$

In other words, the rows and columns of $\bm{M}^{\prime}$ can be
lexicographically ordered, or, equivalently, $\bm{M}^{\prime}$ excludes the
submatrix

$\displaystyle\begin{pmatrix}x+1&x\\\ x&x+1\end{pmatrix}.$ (1)

This implies that the matrix (1) is a forbidden minor for $S$ with determinant
$2x+1$. We therefore obtain a purely combinatorial description which does not
take into account the knowledge about subdeterminants but still completely
characterizes totally $S$-modular matrices with entries $x$ and $x+1$. One of
the advantages of this observation is that the recognition problem for totally
$S$-modular matrices becomes surprisingly straightforward in large dimensions:
Up to row and column permutations and multiplying with minus one, one can
simply check whether every entry is contained in $\\{x,x+1\\}$ and the
forbidden submatrix in (1) does not appear. This leads to the natural question
of what happens when we allow the matrix (1) to be present, i.e., we add
$2x+1$ to the set $S$. Thus we have $S=\pm\\{0,1,x,x+1,2x+1\\}$. In this
setting, one can again show that the non-constant entries of any totally
$S$-modular matrix $\bm{M}$ form a submatrix $\bm{M}^{\prime}$ of $\bm{M}$,
and, furthermore, the entries of $\bm{M}^{\prime}$ can be assumed to be
contained in $\\{x,x+1\\}$. In this manuscript, we investigate totally
$S$-modular matrices $\bm{$}withthepropertythat$M’=M.

###  1.2 Statements of our results

A matrix $\bm{M}$ with entries contained in $\\{x,x+1\\}$ can be written as a
rank-1 update of the form $\bm{M}=\bm{T}+x\cdot\bm{1}\cdot\bm{1}^{\top}$ where
$\bm{T}$ has entries in $\\{0,1\\}$. Then the following slightly more general
decomposition result applies.

###### Theorem 1.1

Let $S\subseteq\mathbb{Z}[x]$ be finite. Let
$\bm{M}=\bm{T}+x\cdot\bm{u}\cdot\bm{v}^{\top}$ where $\bm{u},\bm{v}$ are
integral and $\bm{T}$ has integral entries. If $\bm{M}$ is totally
$S$-modular, then $\bm{T}$ is totally $\\{\lambda_{0}:\lambda_{1}\cdot
x+\lambda_{0}\in S\\}$-modular.

For instance, let $K_{0}\subseteq\mathbb{N}$ be finite and
$S=\pm\\{kx-1,kx,kx+1:k\in K_{0}\\}$. Then Theorem 1.1 states that $\bm{T}$ is
totally unimodular.

Theorem 1.1 can be significantly generalized. The assumption that
$\bm{M}=\bm{T}+x\cdot\bm{u}\cdot\bm{v}^{\top}$ can be replaced by
$\bm{M}=\bm{T}+x\cdot\bm{R}$ where $\bm{R}$ is an arbitrary integral matrix.
This general statement requires a more involved proof that we refrain from
explaining here in detail. The reason is that we only use Theorem 1.1 to
derive statements about optimization and recognition, but even then Theorem
1.1 itself is not enough. Further properties of the matrix $\bm{T}$ are
required to tackle the following constraint parametric optimization problem
over $\mathbb{Z}$ which is given in terms of a full-column-rank constraint
matrix $\bm{M}(a)\in\\{a,a+1\\}^{m\times n}$ parameterized by a specific value
$a\in\mathbb{Z}$:

$\displaystyle\operatorname{ILP}(\bm{M}(a),\bm{b},\bm{c}):\max\bm{c}^{\top}\bm{x}\
\text{s.t.}\ \bm{M}(a)\bm{x}\leq\bm{b},\ \bm{x}\in\mathbb{Z}^{n}$

where $\bm{b}$ is integral. The following two results can be derived with the
tools developed in this paper.

###### Theorem 1.2

Let $a\in\mathbb{Z}\backslash\\{-3,-2,1,2\\}$ and
$S(a)=\pm\\{0,1,a,a+1,2a+1\\}$. Given a matrix
$\bm{M}(a)\in\\{a,a+1\\}^{m\times n}$, one can decide in polynomial time
whether $\bm{M}(a)$ is totally $S(a)$-modular.

###### Theorem 1.3

Let $a\in\mathbb{Z}\backslash\\{-3,-2,1,2\\}$ and
$S(a)=\pm\\{0,1,a,a+1,2a+1\\}$. Let $\bm{M}(a)\in\\{a,a+1\\}^{m\times n}$ have
full column rank and be totally $S(a)$-modular. Then one can solve
$\operatorname{ILP}(\bm{M}(a),\bm{b},\bm{c})$ for integral $\bm{b}$ and
$\bm{c}$ in polynomial time.

###### Remark 1

With a slightly modified proof of Theorem 1.3, one can show that there exists
a polynomial time algorithm that solves
$\operatorname{ILP}(\bm{M}(a),\bm{b},\bm{c})$ for a totally
$\pm\\{0,a,a+1,2a+1\\}$-modular matrix $\bm{M}(a)$ with _arbitrary_ entries
for $a\in\mathbb{Z}\backslash\\{-2,1\\}$.

##  2 Tools

Throughout this paper we work with the lexicographical order of
$\mathbb{Z}[x]$ which is defined by $s<t$ if and only if the leading
coefficient of $t-s$ is positive. With respect to this ordering we further
define the absolute value of $s\in\mathbb{Z}[x]$ to be

$\displaystyle|s|=\begin{cases}s,&\text{if }s\geq 0,\\\
-s,&\text{otherwise}\end{cases}.$

Also, we interchangeably pass from polynomials $s\in\mathbb{Z}[x]$ to
polynomial functions, denoted by $s(a)$, when evaluating polynomials. This can
be done since the polynomial function is uniquely determined by the polynomial
over $\mathbb{Z}[x]$; see [15, Chapter 4].

Let $I\subseteq[n]$ and $J\subseteq[n]$. We denote by $\bm{M}_{\backslash
I,\backslash J}$ the submatrix of $\bm{M}$ without the rows indexed by $I$ and
columns indexed by $J$. In what follows, the notation
$\bm{A}_{(k)}\subseteq\bm{M}$ is shorthand for specifying that $\bm{A}_{(k)}$
is a $k\times k$ submatrix of $\bm{M}$. Given a submatrix $\bm{A}$ of $\bm{M}$
and $i,j\in[n]$, we denote by $\bm{A}[i,j]$ the submatrix of $\bm{M}$ that
contains $\bm{A}$ along with the extra row and column indexed by $i$ and $j$
respectively.

We now show two results that can be viewed as a generalization of the well-
known fact that every matrix that is not totally unimodular and has entries in
$\pm\\{0,1\\}$ contains a submatrix with determinant two in absolute value.
For that purpose, we utilize a well-known determinant identity from linear
algebra which is due to Sylvester [25] and commonly referred to as
_Sylvester’s determinant identity_.

######  Lemma 1 (Sylvester’s determinant identity)

Let $\bm{M}\in\mathbb{Z}[x]^{n\times n}$ for $n\geq 2$ and let
$\bm{A}_{(k)}\subseteq\bm{M}$ for $k=0,\ldots,n$ with
$\bm{A}_{(k)}=\bm{M}_{\backslash I,\backslash J}$ for the ordered sets
$I=\\{i_{1},\ldots,i_{n-k}\\}$ and $J=\\{j_{1},\ldots,j_{n-k}\\}$. Then we get

$\displaystyle\det\bm{M}\cdot(\det\bm{A}_{(k)})^{n-1-k}=\det\begin{pmatrix}\det\bm{A}_{(k)}[i_{1},j_{1}]&\ldots&\det\bm{A}_{(k)}[i_{1},j_{n-k}]\\\
\vdots&\ddots&\vdots\\\
\det\bm{A}_{(k)}[i_{n-k},j_{1}]&\ldots&\det\bm{A}_{(k)}[i_{n-k},j_{n-k}]\end{pmatrix}.$

For the most part, we work with the special case when $k=n-2$, which is also
known as the _Desnanont-Jacobi identity_. In this case, we get the equation

$\displaystyle\det\bm{M}\cdot\det\bm{A}_{(k)}=\det\begin{pmatrix}\det\bm{A}_{(k)}[i_{1},j_{1}]&\det\bm{A}_{(k)}[i_{1},j_{2}]\\\
\det\bm{A}_{(k)}[i_{2},j_{1}]&\det\bm{A}_{(k)}[i_{2},j_{2}]\end{pmatrix}$ (2)

for $I=\\{i_{1},i_{2}\\}$ and $J=\\{j_{1},j_{2}\\}$. This identity already
implies our first bound:

###### Lemma 2

Let $S\subseteq\mathbb{Z}[x]$ be finite. Then the set $F(S)$ of determinants
given by the forbidden minors of $S$ is finite and

$\displaystyle\max_{x\in F(S)}|x|\leq 2\cdot\max_{s\in S}s^{2}.$

###### Proof

Select some forbidden minor $\bm{M}$ for $S$ such that $\det\bm{M}\neq 0$.
There exists an invertible submatrix $\bm{A}_{(n-2)}\subseteq\bm{M}$. By the
Desnanot-Jacobi identity (2) applied to $\bm{A}_{(n-2)}$, we obtain that

$\displaystyle\det\bm{M}=\frac{1}{\det\bm{A}_{(n-2)}}\cdot\left(s_{1}s_{2}-s_{3}s_{4}\right),$

where $s_{i}\in S$ for $i=1,2,3,4$. Since $\det\bm{A}_{(n-2)}\in S$, the right
hand side only attains finitely many values as $S$ is finite. Hence, there are
only finitely many values possible for $\det\bm{M}$. To obtain the inequality,
we take absolute values on both sides, apply the triangle inequality, and
observe that $\left|s_{i}\right|\leq\max_{s\in S}\left|s\right|$. The claim
follows then from $1\leq\left|\det\bm{A}_{(n-2)}\right|$.∎

We immediately obtain that every forbidden minor for totally
$\pm\\{0,1,\ldots,\Delta\\}$-modular matrices over $\mathbb{Z}$ admits a
determinant bounded by $2\Delta^{2}$ in absolute value. The bound in Lemma 2
is tight: Let $S\subseteq\mathbb{Z}[x]$ be finite such that $s\in S$ implies
$-s\in S$ and $\\{0\\}\neq S$. Select $\tau=\max_{s\in S}\left|s\right|$. Then

$\displaystyle\begin{pmatrix}\tau&\tau\\\ -\tau&\tau\end{pmatrix}$

is a forbidden minor for $S$ and has determinant $2\tau^{2}$. One can
strengthen the bound in Lemma 2 if the dimension is sufficiently large.

###### Theorem 2.1

Let $S\subseteq\mathbb{Z}$ be finite. Let $\tau=\max_{s\in S}\left|s\right|$.
Given a forbidden minor $\bm{M}\in\mathbb{Z}^{n\times n}$ for $S$ such that
the dimension satisfies $n\geq\left\lceil\log_{2}\tau+1\right\rceil$, then

$\displaystyle\left|\det\bm{M}\right|\leq
2\cdot\lceil\log_{2}\tau+1\rceil\cdot\tau.$

###### Proof

Suppose that the matrix $\bm{M}$ is invertible, otherwise we are done. Let
$\Delta_{k}=\max\left\\{\left|\det\bm{A}_{(k)}\right|:\bm{A}_{(k)}\subseteq\bm{M}\right\\}$
for all $k=0,\ldots,n$ and $\kappa=\lceil\log_{2}\tau\rceil$. If $\kappa=0$,
we have $\tau=1$ and, thus, $\Delta_{n-1}/\Delta_{n-2}\leq 1$. So the
Desnanont-Jacobi identity (2) applied to some invertible $(n-2)\times(n-2)$
submatrix implies

$\displaystyle\left|\det\bm{M}\right|\leq
2\cdot\Delta_{n-1}/\Delta_{n-2}\cdot\Delta_{n-1}\leq 2\cdot\Delta_{n-1}\leq
2\cdot\tau$

as $\Delta_{n-2}\geq 1$.

For the remainder of the proof, we suppose that $1\leq\kappa$. Observe that
$\kappa+1\leq n$. Assume that $\Delta_{n-j}/\Delta_{n-j-1}>2$ for all
$j=1,\ldots,\kappa$. This yields

$\displaystyle\prod_{j=1}^{\kappa}\Delta_{n-j}/\Delta_{n-j-1}>2^{\kappa}\geq\tau.$

However, we also have

$\displaystyle\prod_{j=1}^{\kappa}\Delta_{n-j}/\Delta_{n-j-1}=\Delta_{n-1}/\Delta_{n-\kappa-1}\leq\tau$

as $\Delta_{n-\kappa-1}\geq 1$ and $\Delta_{n-1}\leq\tau$, which is a
contradiction. So we know there exists an index $l^{*}\in[\kappa]$ such that
$\Delta_{n-l^{*}}/\Delta_{n-l^{*}-1}\leq 2$, where we have $n-l^{*}-1\geq 0$
by construction. Let $\bm{A}:=\bm{A}_{(n-l^{*}-1)}\subseteq\bm{M}$ attain
$\Delta_{n-l^{*}-1}$. Then applying Sylvester’s determinant identity, Lemma 1,
to $\bm{A}$ gives us

$\displaystyle\det\bm{M}\cdot(\det\bm{A})^{l^{*}}=\det\underbrace{\begin{pmatrix}\det\bm{A}[i_{1},j_{1}]&\ldots&\det\bm{A}[i_{1},j_{l^{*}+1}]\\\
\vdots&\ddots&\vdots\\\
\det\bm{A}[i_{l^{*}+1},j_{1}]&\ldots&\det\bm{A}[i_{l^{*}+1},j_{l^{*}+1}]\end{pmatrix}}_{=\bm{D}}$

for suitable sets $I$ and $J$. Dividing by $(\det\bm{A})^{l^{*}}$ and applying
Laplace expansion to the first row on the right hand side yields

$\displaystyle\det\bm{M}=\frac{1}{(\det\bm{A})^{l^{*}}}\cdot\sum_{k=1}^{l^{*}+1}(-1)^{k}\cdot\det\bm{A}[i_{1},j_{k}]\cdot\det\bm{D}_{\backslash
1,\backslash k}.$

Observe that $\det\bm{D}_{\backslash 1,\backslash k}=\det\bm{M}_{\backslash
i_{1},\backslash j_{k}}\cdot(\det\bm{A})^{l^{*}-1}$ by Lemma 1. Hence,

$\displaystyle\det\bm{M}=\frac{1}{\det\bm{A}}\cdot\sum_{k=1}^{l^{*}+1}(-1)^{k}\cdot\det\bm{A}[i_{1},j_{k}]\cdot\det\bm{M}_{\backslash
i_{1},\backslash j_{k}}.$

Taking absolute values and using that
$\left|\det\bm{A}\right|=\Delta_{n-l^{*}-1}$ gives

$\displaystyle\left|\det\bm{M}\right|\leq(l^{*}+1)\cdot\Delta_{n-l^{*}}/\Delta_{n-l^{*}-1}\cdot\Delta_{n-1}\leq(\kappa+1)\cdot
2\cdot\tau.$

The claim follows from $\kappa=\lceil\log_{2}\tau\rceil$.∎

Let $S\subseteq\mathbb{Z}[x]$ be finite. If $\bm{M}$ is totally $S$-modular
over $\mathbb{Z}[x]$, then $\bm{M}(a)$ is totally $S(a)$-modular for every
$a\in\mathbb{Z}$. This raises the question of whether totally $S(a)$-modular
matrices over $\mathbb{Z}$ for a fixed value $a\in\mathbb{Z}$ are also totally
$S$-modular over $\mathbb{Z}[x]$, i.e., totally $S(a)$-modular for all
$a\in\mathbb{Z}$. This is in general not true: Let
$S=\pm\\{0,x,x+1,2x+1\\}\subseteq\mathbb{Z}[x]$ and $a=1$. We define the
matrix

$\displaystyle\bm{M}=\begin{pmatrix}x&x+1&x&x\\\ x+1&x+1&x+1&x\\\
x&x+1&x+1&x+1\\\ x&x&x+1&x\end{pmatrix}\in\mathbb{Z}[x]^{4\times 4}.$

One can check that $\bm{M}(1)$ is totally $S(1)$-modular. However, the matrix
$\bm{M}$ satisfies $\det\bm{M}=1\notin S$. Nevertheless, if we evaluate at
some $a\in\mathbb{Z}\backslash\\{-2,-1,0,1\\}$, we avoid this issue for this
particular matrix since $\det\bm{M}(a)=1\notin S(a)$. One of our main results
in this section states that this is a general phenomenon. Let

$\displaystyle I(S)=\\{a\in\mathbb{Z}:s(a)=f(a)\text{ for }s\in S\text{ and
}f\in F(S)\\}$

denote the set of integer valued intersections between the polynomial
functions given by the elements in $S$ and $F(S)$.

###### Lemma 3

Let $S\subseteq\mathbb{Z}[x]$ be finite and $a\in\mathbb{Z}\backslash I(S)$.
Then $\bm{M}(a)$ is totally $S(a)$-modular if and only if $\bm{M}$ is totally
$S$-modular over $\mathbb{Z}[x]$. Also, the matrix $\bm{M}(a)$ is a forbidden
minor for $S(a)$ if and only if $\bm{M}$ is a forbidden minor for $S$.
Furthermore, the set $I(S)$ is finite.

###### Proof

Note that the statement about the forbidden minors follows directly from the
first statement about totally $S$-modular matrices. Therefore, we only need to
prove the first part of the statement. Recall that every totally $S$-modular
matrix over $\mathbb{Z}[x]$ is totally $S(a)$-modular for every evaluation at
$a\in\mathbb{Z}$. So it suffices to show the other direction.

A totally $S(a)$-modular matrix that is not the evaluation of a totally
$S$-modular matrix over $\mathbb{Z}[x]$ contains a forbidden minor $\bm{M}$
for $S$ by definition. This forbidden minor $\bm{M}$ satisfies
$\det\bm{M}(a)\in S(a)$ and $\det\bm{M}\notin S$. In other words, let $f\in
F(S)$ be the polynomial corresponding to $\det\bm{M}$, then $f\notin S$ but
$f(a)=s(a)$ for some $s\in S$. Thus, we obtain $a\in I(S)$, a contradiction.
So $\bm{M}$ does not contain a forbidden minor for $S$ and is therefore
totally $S$-modular. Since $S$ and $F(S)$ are finite, see Lemma 2, we get that
there are only finitely many of those intersections. ∎

Lemma 3 allows us to introduce a framework for analyzing matrices that arise
as rank-1 updates, that is, matrices given by
$\bm{M}=\bm{T}+x\cdot\bm{u}\cdot\bm{v}^{\top}\in\mathbb{Z}[x]^{n\times n}$ for
$\bm{T}$ having integral entries and $\bm{u},\bm{v}\in\mathbb{Z}^{n}$. The
goal is to analyze the structure of the matrix $\bm{T}$ if $\bm{M}$ is totally
$S$-modular for some finite set $S\subseteq\mathbb{Z}[x]$.

First, we establish that subdeterminants of $\bm{M}$ correspond to polynomials
of degree at most one. This is a consequence of the well-known matrix
determinant lemma for rank-1 updates. A variant of this lemma that can be
derived from it is stated below.

######  Lemma 4 (Matrix determinant lemma)

Let $n\geq 1$, $\bm{T}\in\mathbb{Z}^{n\times n}$,
$\bm{u},\bm{v}\in\mathbb{Z}^{n}$, and
$\bm{M}=\bm{T}+x\cdot\bm{u}\cdot\bm{v}^{\top}\in\mathbb{Z}[x]^{n\times n}$.
Then we have

$\displaystyle\det\bm{M}=\left(\det\bm{T}-\det\left(\bm{T}-\bm{u}\cdot\bm{v}^{\top}\right)\right)\cdot
x+\det\bm{T}.$

In this section, the important implication of Lemma 4 is that the determinant
corresponds to a polynomial of degree at most one in $\mathbb{Z}[x]$. This is
the essential ingredient to prove Theorem 1.1.

######  Proof (of Theorem 1.1)

Let $\bm{M}=\bm{T}+x\cdot\bm{u}\cdot\bm{v}^{\top}$ be totally $S$-modular.
Then Lemma 4 implies that $\det\bm{M}=\lambda_{1}x+\lambda_{0}$ for
$\lambda_{0},\lambda_{1}\in\mathbb{Z}$ and $\det\bm{T}=\lambda_{0}$. This
holds for all such totally $S$-modular matrices. So the claim follows.∎

We will also use an implication of Theorem 1.1 for matrices over $\mathbb{Z}$.

###### Corollary 1

Let $S\subseteq\mathbb{Z}[x]$ be finite and $a\in\mathbb{Z}\backslash I(S)$.
If $\bm{M}(a)=\bm{T}+a\cdot\bm{u}\cdot\bm{v}^{\top}$ with $\bm{T}$, $\bm{u}$,
and $\bm{v}$ being integral is totally $S(a)$-modular, then the matrix
$\bm{T}$ is totally $\\{\lambda_{0}:\lambda_{1}\cdot x+\lambda_{0}\in
S\\}$-modular.

###### Proof

Since $a\in\mathbb{Z}\backslash I(S)$, we know that every totally
$S(a)$-modular matrix $\bm{M}(a)=\bm{T}+a\cdot\bm{u}\cdot\bm{v}^{\top}$
corresponds to a totally $S$-modular matrix
$\bm{M}=\bm{T}+x\cdot\bm{u}\cdot\bm{v}^{\top}$ over $\mathbb{Z}[x]$ by Lemma
3. From Theorem 1.1 it follows that $\bm{T}$ is totally
$\\{\lambda_{0}:\lambda_{1}\cdot x+\lambda_{0}\in S\\}$-modular.∎

##  3 Properties of $I(S)$

Let $S=\pm\\{0,1,x,x+1,2x+1\\}$. Following Lemma 3, we calculate all
intersections between the polynomial functions in $S$ and the polynomial
functions in $F(S)$. We start by proving a lemma which holds under more
general assumptions. For that purpose, we remark that the ring $\mathbb{Z}[x]$
is a unique factorization domain. So every element in $\mathbb{Z}[x]$ admits a
unique factorization into smaller irreducible elements up to multiplying with
$\pm 1$. Therefore, the notion of greatest common divisors carries naturally
over from $\mathbb{Z}$ to $\mathbb{Z}[x]$. Analogously to $\mathbb{Z}$,
elements in $\mathbb{Z}[x]$ are relatively prime if their greatest common
divisor is $1$. We call a matrix $\bm{M}\in\mathbb{Z}[x]^{m\times n}$ _totally
unimodular_ if every subdeterminant is contained in $\pm\\{0,1\\}$.

###### Lemma 5

Let $S\subseteq\mathbb{Z}[x]$ be such that all non-zero $x,y\in S$ are
relatively prime or $\left|x\right|=\left|y\right|$ and $2\notin S$. Let
$n\geq 3$ and $\bm{M}\in\mathbb{Z}[x]^{n\times n}$ be invertible and every
$(n-1)\times(n-1)$ submatrix of $\bm{M}$ is totally $S$-modular. Then either
$\bm{M}$ is totally unimodular or there exist invertible submatrices
$\bm{A}_{(n-2)},\tilde{\bm{A}}_{(n-2)}\subseteq\bm{M}$ such that

$\displaystyle\left|\det\bm{A}_{(n-2)}\right|\neq\bigl{|}\det\tilde{\bm{A}}_{(n-2)}\bigr{|}.$

###### Proof

Let $n=3$. The $(n-2)\times(n-2)$ submatrices of $\bm{M}$ are the entries of
$\bm{M}$. Assume that every entry of $\bm{M}$ is in $\pm\\{0,s\\}$ for some
$s\in S$. If $s=1$, we get that $\bm{M}\in\pm\\{0,1\\}^{3\times 3}$. Since
$2\notin S$, the matrix $\bm{M}$ is totally unimodular, cf. [23, Theorem
19.3]. If we assume $s\neq 1$, we have
$\det\bm{A}_{(2)}\in\pm\\{s^{2},2s^{2}\\}$ for an invertible submatrix
$\bm{A}_{(2)}\subseteq\bm{M}$ as every entry is contained in $\pm\\{0,s\\}$.
Since the non-zero elements in $S$ are pairwise relatively prime and $s\in S$,
we get $\det\bm{A}_{(2)}\notin S$, contradicting that $\bm{A}_{(2)}$ is
totally $S$-modular.

So we suppose that $n\geq 4$. Let $\bm{M}$ not be totally unimodular. Again,
we assume that every invertible $(n-2)\times(n-2)$ submatrix has determinant
$s$ or $-s$ for some $s\in S$. By the induction hypothesis applied to some
invertible submatrix $\bm{A}_{(n-1)}\subseteq\bm{M}$, there exists an
invertible submatrix $\bm{A}_{(n-3)}\subseteq\bm{A}_{(n-1)}$ with
$\bigl{|}\det\bm{A}_{(n-3)}\bigr{|}\neq\left|s\right|$. We apply the
Desnanont-Jacobi identity, (2), to $\bm{A}_{(n-3)}\subseteq\bm{A}_{(n-1)}$ and
obtain that

$\displaystyle\det\bm{A}_{(n-1)}=\frac{1}{\det\bm{A}_{(n-3)}}\left(s_{1}s_{2}-s_{3}s_{4}\right)\in\pm\frac{1}{\det\bm{A}_{(n-3)}}\cdot\\{s^{2},2s^{2}\\}$

with $s_{i}\in\pm\\{0,s\\}$ for $i=1,2,3,4$. If
$\left|\det\bm{A}_{(n-3)}\right|\neq 1$, then $\det\bm{A}_{(n-3)}$ does not
divide $s^{2}$ or $2s^{2}$ as the non-zero elements in $S$ are pairwise
relatively prime and $2\notin S$. However, this implies that
$\det\bm{A}_{(n-1)}\notin\mathbb{Z}[x]$, a contradiction. If
$\left|\det\bm{A}_{(n-3)}\right|=1$, we get that
$\det\bm{A}_{(n-1)}\in\pm\\{s^{2},2s^{2}\\}$. This gives us a contradiction
since $\det\bm{A}_{(n-1)}$ and $s$ are not relatively prime. ∎

We are in the position to determine the set of possible determinants given by
the forbidden minors for $S=\pm\\{0,1,x,x+1,2x+1\\}$.

###### Lemma 6

Let $S=\pm\\{0,1,x,x+1,2x+1\\}$ and $D$ be the set of all determinants
attained by a $2\times 2$ forbidden minor for $S$. Then we have

$\displaystyle F(S)\subseteq\pm\\{2,x-1,x+2,2x,2x+2,3x+1,3x+2,4x+2\\}\cup D.$

###### Proof

Let $n\geq 3$ and $\bm{M}$ be a forbidden minor. There exists an invertible
submatrix $\bm{A}_{(n-2)}\subseteq\bm{M}$. Applying the Desnanont-Jacobi
identity (2), we get

$\displaystyle\det\bm{M}\cdot\det\bm{A}_{(n-2)}=s_{1}s_{2}-s_{3}s_{4}$

with $s_{i}\in S$ for $i=1,2,3,4$. This equation needs to have a solution for
$\det\bm{M}$ in $\mathbb{Z}[x]$. Suppose that $\det\bm{M}$ has degree larger
than one. This implies $\left|\det\bm{A}_{(n-2)}\right|=1$, an equality that
has to hold for every invertible $(n-2)\times(n-2)$ subdeterminant. By Lemma
5, we deduce that $\bm{M}$ is totally unimodular and, thus, not a forbidden
minor. So we assume $\det\bm{M}$ has degree at most one. Using suitable
software such as SageMath, one can enumerate all feasible solutions to the
Desnanont-Jacobi identity with degree at most one. This gives us the following
feasible values for $\det\bm{M}$ up to a sign:

$\displaystyle 2S\backslash
0\cup\\{x-1,x+2,2x-1,2x+3,3x+1,3x+2,4x,4x+1,4x+3,4x+4\\}.$

However, it is possible to show that the values
$\pm\\{2x-1,2x+3,4x,4x+1,4x+3,4x+4\\}$ for $\det\bm{M}$ can only appear for a
unique choice of $\left|\det\bm{A}_{(n-2)}\right|$. Therefore, if there exists
a forbidden minor with such a determinant, every invertible $(n-2)\times(n-2)$
submatrix needs to have the same determinant in absolute value. This
contradicts Lemma 5. Hence, we can exclude these values and obtain the
determinants from the statement.∎

Computing the intersections of the elements in $S$ and the set in Lemma 6
yields that $I(S)\subseteq\\{-3,\ldots,2\\}$ in Theorem 1.1. We remark that it
is possible to show that both sets are indeed equal.

##  4 Proofs of Theorems 1.2 and 1.3

Let $S=\pm\\{0,1,x,x+1,2x+1\\}$. For $a\in\\{-1,0\\}$, we recover that
$S(a)=\pm\\{0,1\\}$. Since one can optimize
$\operatorname{ILP}(\bm{M}(a),\bm{b},\bm{c})$ in polynomial time for totally
unimodular constraint matrices, see, for instance, [23, Chapter 19], and
recognize totally unimodular matrices in polynomial time [23, Chapter 20],
both theorems hold in this case. In the following, we prove Theorems 1.2 and
1.3 for the other values of $a$, that is,
$a\in\mathbb{Z}\backslash\\{-3,-2,1,2\\}$.

###  4.1 Proof of Theorem 1.2

For $\bm{M}\in\\{x,x+1\\}^{m\times n}$, we want to test whether
$\bm{M}=\bm{T}+x\cdot\bm{1}\cdot\bm{1}^{\top}$ is totally $S$-modular over
$\mathbb{Z}[x]$. To prove Theorem 1.2 we use the complete characterization
given below and the fact that one can recognize totally unimodular matrices in
polynomial time; see [23, Chapter 20]. Given $\bm{T}\in\\{0,1\\}^{m\times n}$,
we define $\bar{\bm{T}}$ to be the matrix that results from $\bm{T}$ by
swapping $1$’s with $0$’s and $0$’s with $1$’s, that is,
$\bar{\bm{T}}=-(\bm{T}-\bm{1}\cdot\bm{1}^{\top})$.

###### Lemma 7

Let $\bm{T}\in\\{0,1\\}^{m\times n}$. The matrix
$\bm{M}=\bm{T}+x\cdot\bm{1}\cdot\bm{1}^{\top}$ is totally $S$-modular if and
only if $\bm{T}$ and $\bar{\bm{T}}$ are totally unimodular.

###### Proof

It suffices to show the statement for square matrices. So we assume without
loss of generality that $m=n$. Let $\bm{T}$ and $\bar{\bm{T}}$ be totally
unimodular. We have

$\displaystyle\det\bm{M}=\left(\det\bm{T}-(-1)^{n}\det\bar{\bm{T}}\right)\cdot
x+\det\bm{T}$ (3)

by Lemma 4. So $\det\bm{M}$ is completely determined by $\det\bm{T}$ and
$\det\bar{\bm{T}}$. As $\det\bm{T}$ and $\det\bar{\bm{T}}$ are both in
$\pm\\{0,1\\}$, we obtain that $\det\bm{M}\in\pm\\{0,1,x,x+1,2x+1\\}=S$ by
going through all feasible cases. The other direction follows directly by
evaluating $S$, $\bm{M}$, and (3) at $x\in\\{-1,0\\}$.∎

By Lemma 3 and $I(S)\subseteq\\{-3,\ldots,2\\}$ from the previous section, we
can now derive Theorem 1.2 by replacing $S$ with $S(a)$ for
$a\in\mathbb{Z}\backslash\\{-3,-2,1,2\\}$.

###  4.2 Proof of Theorem 1.3

We start by showing that forbidden minors for $S$ satisfy an arithmetic
property. Here $\bm{M}_{i,\cdot}$ and $\bm{M}_{\cdot,i}$ denote the row and
column indexed by $i\in[n]$.

###### Lemma 8

Let $\bm{M}\in\\{x,x+1\\}^{n\times n}$ be a forbidden minor for $S$. Then we
have $\gcd\bm{M}_{i,\cdot}=1=\gcd\bm{M}_{\cdot,i}$ for all $i\in[n]$.

###### Proof

The claim holds for $n=2$. So we assume that $n\geq 3$. Suppose without loss
of generality that the last row of $\bm{M}$ has greatest common divisor larger
than $1$. We derive a contradiction.

We observe that $\gcd\bm{M}_{n,\cdot}\in S$. By Lemma 6, we have
$\left|\det\bm{M}\right|=2\cdot\gcd\bm{M}_{n,\cdot}$ as $\det\bm{M}$ has to be
divisible by $\gcd\bm{M}_{n,\cdot}$. Let $\bm{A}_{(n-1)}\subseteq\bm{M}$ be an
invertible submatrix not containing the last row such that
$\left|\det\bm{A}_{(n-1)}\right|\neq\gcd\bm{M}_{n,\cdot}$. Such a submatrix
exists because otherwise $\det\bm{M}$ has to divide
$(\gcd\bm{M}_{n,\cdot})^{2}$ by Laplace expansion, which is not possible. Take
an invertible submatrix $\bm{A}_{(n-2)}\subseteq\bm{A}_{(n-1)}$. The
Desnanont-Jacobi identity, (2), applied to $\bm{A}_{(n-2)}$ yields

$\displaystyle
2\gcd\bm{M}_{n,\cdot}\bigl{|}\det\bm{A}_{(n-2)}\bigr{|}=\bigl{|}\det\bm{M}\bigr{|}\bigl{|}\det\bm{A}_{(n-2)}\bigr{|}=\gcd\bm{M}_{n,\cdot}\bigl{|}\det\bm{A}_{(n-1)}-s\bigr{|},$

where $s\in S$. So we have
$2\cdot\left|\det\bm{A}_{(n-2)}\right|=\left|\det\bm{A}_{(n-1)}-s\right|$. The
only solution over $S$ for this equation is given by $-s=\det\bm{A}_{n-1}$ and
$\left|\det\bm{A}_{(n-1)}\right|=\left|\det\bm{A}_{(n-2)}\right|$. So every
invertible $(n-2)\times(n-2)$ submatrix of $\bm{A}_{(n-1)}$ has the same
determinant as $\bm{A}_{(n-1)}$ in absolute value. If $n=3$, this implies that
the $(n-2)\times(n-2)$ subdeterminants correspond to entries. As the entries
of $\bm{M}$ are in $\\{x,x+1\\}$, this means that all the entries in
$\bm{A}_{(n-1)}$ are the same which gives us $\det\bm{A}_{(n-1)}=0$, a
contradiction. So let $n\geq 4$. Take an invertible submatrix
$\bm{A}_{(n-3)}\subseteq\bm{A}_{(n-1)}$. We apply the Desnanont-Jacobi
identity, (2), to $\bm{A}_{(n-3)}\subseteq\bm{A}_{(n-1)}$ and get
$\det\bm{A}_{(n-3)}\in\pm\\{\det\bm{A}_{(n-1)},2\det\bm{A}_{(n-1)}\\}$ which
yields $\left|\det\bm{A}_{(n-3)}\right|=\left|\det\bm{A}_{(n-1)}\right|$. This
holds for all invertible $(n-3)\times(n-3)$ submatrices of $\bm{A}_{(n-1)}$.
By Lemma 5, this implies that $\bm{A}_{(n-1)}$ is totally unimodular. However,
this contradicts the assumption that the entries of $\bm{A}_{(n-1)}$ are in
$\\{x,x+1\\}$.∎

###### Theorem 4.1

Let $n\geq 2$ and $\bm{M}\in\\{x,x+1\\}^{n\times(n-1)}$ be totally
$S$-modular. Then $\det[\bm{M}|\bm{1}]\in\pm\\{0,1\\}$. Here $[\bm{M}|\bm{1}]$
denotes the matrix $\bm{M}$ with an extra column given by $\bm{1}$.

###### Proof

For the purpose of deriving a contradiction, assume that the statement does
not hold. We multiply the all-ones column with $x+1$. So we deduce that
$\det[\bm{M}|(x+1)\cdot\bm{1}]\notin\pm\\{0,x+1\\}$ by assumption. Note that
$\det[\bm{M}|(x+1)\cdot\bm{1}]$ is divisible by $x+1$. So we obtain that
$\det[\bm{M}|(x+1)\cdot\bm{1}]\notin S$. Thus, the matrix
$[\bm{M}|(x+1)\cdot\bm{1}]$ contains a forbidden minor for $S$. As $\bm{M}$ is
totally $S$-modular, the forbidden minor contains the all-$(x+1)$’s column. By
Lemma 8, this is not possible.∎

As before, we fix some $a\in\mathbb{Z}\backslash\\{-3,\ldots,2\\}$. To prove
Theorem 1.3, we utilize the decomposition
$\bm{M}(a)=\bm{T}+a\cdot\bm{1}\cdot\bm{1}^{\top}$ and set
$y=\bm{1}^{\top}\bm{x}$ to reformulate
$\operatorname{ILP}(\bm{M}(a),\bm{b},\bm{c})$ in the form of the mixed integer
linear program

$\displaystyle\max\bm{c}^{\top}\bm{x}\ \text{ s.t. }\
\bm{T}\bm{x}\leq\bm{b}-a\cdot\bm{1}\cdot y,\ \bm{1}^{\top}\bm{x}=y,\
y\in\mathbb{Z}.$

Corollary 1 implies that $\bm{T}$ is totally unimodular. Observe that
subtracting $x\cdot\bm{1}$ in Theorem 4.1 from the first $n-1$ columns does
not change the determinant. So we get
$\det[\bm{T}^{\prime}|\bm{1}]\in\pm\\{0,1\\}$ for all $k\times(k-1)$
submatrices $\bm{T}^{\prime}$ of $\bm{T}$. Hence, we can append
$\bm{1}^{\top}$ to the totally unimodular matrix $\bm{T}$ and remain totally
unimodular. Then a solution of the mixed integer linear program, that can be
obtained in polynomial time using Lenstra’s algorithm [16] or its improved
successors [9, 14, 21], corresponds to a solution of
$\operatorname{ILP}(\bm{M}(a),\bm{b},\bm{c})$.

##  5 Finiteness of forbidden minors

Recall from the introduction that totally $\pm\\{0,x,x+1\\}$-modular matrices
with entries in $\\{x,x+1\\}$ are completely characterized by excluding the
submatrix (1). In light of the celebrated Robertson-Seymour theorem [22], one
might ask whether there is always a finite list of forbidden minors for a
finite and symmetric set $S\subseteq\mathbb{Z}[x]$ and matrices with entries
in $\\{x,x+1\\}$. This is not the case. An intriguing example with infinitely
many forbidden minors is already given by the set $S=\pm\\{0,1,x,x+1,2x+1\\}$;
see Figure 1 for an incomplete list. Interestingly, if one removes the $1$
from $S$ and passes to $\pm\\{0,x,x+1,2x+1\\}$, then we are only aware of
finitely many forbidden minors; see Figure 1. This might support the following
conjecture: there exists a finite list of forbidden minors for a finite and
symmetric set $S\subseteq\mathbb{Z}[x]$ if and only if $1\notin S$.

Figure 1: The blue boxes depict the value $x$ and the green boxes $x+1$ or
vice versa. The first row of matrices corresponds to the first five elements
of an infinite sequence of matrices that can be obtained by generalizing the
existing pattern. It can be shown that those infinitely many matrices are
forbidden minors for $\pm\\{0,1,x,x+1,2x+1\\}$. The matrices in the last row
correspond to five forbidden minors for $\pm\\{0,x,x+1,2x+1\\}$.

## References

  * [1] I. Aliev, G. Averkov, J. A. de Loera, and T. Oertel.  Sparse representation of vectors in lattices and semigroups.  Mathematical Programming, 192:519–546, 2022.
  * [2] I. Aliev, J. A. De Loera, F. Eisenbrand, T. Oertel, and R. Weismantel.  The support of integer optimal solutions.  SIAM Journal on Optimization, 28(3):2152–2157, 2018.
  * [3] I. Aliev, M. Henk, and T. Oertel.  Distances to lattice points in knapsack polyhedra.  Mathematical Programming, 182:175–198, 2020.
  * [4] I. Aliev, J. A. De Loera, T. Oertel, and C. O’Neill.  Sparse solutions of linear diophantine equations.  SIAM Journal on Applied Algebra and Geometry, 1:239–253, 2017.
  * [5] S. Artmann, F. Eisenbrand, C. Glanzer, T. Oertel, S. Vempala, and R. Weismantel.  A note on non-degenerate integer programs with small sub-determinants.  Operations Research Letters, 44(5):635–639, 2016.
  * [6] S. Artmann, R. Weismantel, and R. Zenklusen.  A strongly polynomial algorithm for bimodular integer linear programming.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206–1219, 2017.
  * [7] N. Bonifas, M. Di Summa, F. Eisenbrand, N. Hähnle, and M. Niemeier.  On sub-determinants and the diameter of polyhedra.  Discrete and Computational Geometry, 52:102–115, 2014.
  * [8] M. Celaya, S. Kuhlmann, J. Paat, and R. Weismantel.  Proximity and flatness bounds for integer linear optimization.  to appear in Mathematics of Operations Research, http://arxiv.org/abs/2211.14941, 2022.
  * [9] D. Dadush.  Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation.  PhD thesis, Georgia Institute of Technology, 2012.
  * [10] F. Eisenbrand and G. Shmonin.  Carathéodory bounds for integer cones.  Operations Research Letters, 34:564, 568:2006, 2006.
  * [11] F. Eisenbrand and R. Weismantel.  Proximity results and faster algorithms for integer programming using the Steinitz lemma.  ACM Trans. Algorithms, 16(1), 2019.
  * [12] S. Fiorini, G. Joret, S. Weltge, and Y. Yuditsky.  Integer programs with bounded subdeterminants and two nonzeros per row.  2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 13–24, 2022.
  * [13] A.J. Hoffman and J.B. Kruskal.  Integral boundary points of convex polyhedra.  Linear Inequalities and Related Systems (H.W. Kuhn and A.J. Tucker, eds.), pages 223–246, 1956.
  * [14] R. Kannan.  Minkowski’s convex body theorem and integer programming.  Mathematics of Operations Research, 12(3):415–440, 1987.
  * [15] S. Lang.  Algebra.  Graduate Texts in Mathematics. Springer New York, 2005.
  * [16] H. W. Lenstra.  Integer programming with a fixed number of variables.  Mathematics of Operations Research, 8(4):538–548, 1983.
  * [17] M. Nägele, C. Nöbel, R. Santiago, and R. Zenklusen.  Advances on strictly $\Delta$-Modular IPs.  In Integer Programming and Combinatorial Optimization, pages 393–407. Springer International Publishing, 2023.
  * [18] M. Nägele, R. Santiago, and R. Zenklusen.  Congruency-constrained TU problems beyond the bimodular case.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2743–2790. SIAM, 2022.
  * [19] J. Oxley and Z. Walsh.  2-modular matrices.  SIAM Journal on Discrete Mathematics, 36(2):1231–1248, 2022.
  * [20] J. Paat, I. Stallknecht, L. Xu, and Z. Walsh.  On the column number and forbidden submatrices for delta-modular matrices.  to appear in SIAM Journal on Discrete Mathematics, https://arxiv.org/pdf/2212.03819, 2022.
  * [21] V. Reis and T. Rothvoss.  The subspace flatness conjecture and faster integer programming.  to appear in FOCS 2023, https://arxiv.org/abs/2303.14605, 2023.
  * [22] N. Robertson and P.D. Seymour.  Graph minors. XX. Wagner’s conjecture.  Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004\.  Special Issue Dedicated to Professor W.T. Tutte.
  * [23] A. Schrijver.  Theory of Linear and Integer Programming.  Wiley, 1986.
  * [24] P.D Seymour.  Decomposition of regular matroids.  Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980\.
  * [25] J.J. Sylvester.  On the relation between the minor determinants of linearly equivalent quadratic functions.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 1(4):295–305, 1851.