# A Short Proof of Tight Bounds on the Smallest Support Size of Integer
Solutions to Linear Equations

Yatharth Dubey<EMAIL_ADDRESS>Tepper School of Business, Carnegie
Mellon University  Siyue Liu<EMAIL_ADDRESS>Tepper School of
Business, Carnegie Mellon University

###### Abstract

In this note, we study the size of the support of solutions to linear
Diophantine equations $Ax=b,~{}x\in\mathbb{Z}^{n}$ where
$A\in\mathbb{Z}^{m\times n},b\in\mathbb{Z}^{n}$. We give an asymptotically
tight upper bound on the smallest support size, parameterized by
$\|A\|_{\infty}$ and $m$, and taken as a worst case over all $b$ such that the
above system has a solution. This bound is asymptotically tight, and in fact
matches the bound given in Aliev, Averkov, De Leora, Oertel Mathematical
Programming 2022, while the proof presented here is simpler, relying only on
linear algebra. It removes a factor of order $\log\log(\sqrt{m}\left\lVert
A\right\rVert_{\infty})$ to the current best bound given in Aliev, De Loera,
Eisenbrand, Oertel, Weismantel SIAM Journal on Optimization 2018.

##  1 Introduction

The main goal of this work is to establish upper and lower bounds on the
smallest support size of solutions to linear Diophantine equations. Let
$A\in\mathbb{Z}^{m\times n}$ be a matrix and denote by
$\mathcal{L}(A):=\\{Ax\mid x\in\mathbb{Z}^{n}\\}$ the lattice generated by the
columns of $A$. For any $b\in\mathcal{L}(A)$, we want to find an integer
solution to $Ax=b$ with smallest support size, i.e.

$\min~{}\\{\|x\|_{0}\mid Ax=b,x\in\mathbb{Z}^{n}\\},$ (1)

where $\|x\|_{0}:=|\\{j:x_{j}\not=0\\}|$. We will assume without loss of
generality that $A$ has full row rank, i.e. $\text{rank}(A)=m$, because the
system is trivially satisfied if and only if the independent rows of $A$ are
satisfied. According to [9], determining the exact solution to (1) is NP-hard.
In this note, we study the largest value of (1) taken over all points $b$ in
the lattice $\mathcal{L}(A)$. To be precise, for matrix
$A\in\mathbb{Z}^{m\times n}$, define $f(A)$ to be the maximum, taken over all
$b\in\mathcal{L}(A)$, of the smallest support size of an integer solution to
$Ax=b$, i.e.

$f(A):=\max\limits_{b\in\mathcal{L}(A)}\min~{}\\{\|x\|_{0}\mid
Ax=b,x\in\mathbb{Z}^{n}\\}.$ (2)

Note that this notion has been studied in the literature. For example, in [1],
$f(A)$ is called the integer linear rank of $A$, denoted by $ILR(A)$.
Nontrivial bounds on problem (2) have been leveraged in many areas of discrete
optimization; see, for example, references in Section 1 of [1] and in the
introduction of [2].

As a result, there have been several studies focused on achieving increasingly
strong upper bounds on Problem (2). Currently, the best available upper bound
of $f(A)$ is achieved in [1], which we will elaborate on in Section 2.

We parameterize our bound on $f(A)$ by $m$ and $\|A\|_{\infty}$. In
particular, denote by $h(m,t)$ the maximum, taken over all integer matrices
$A$ with $m$ rows with entries with absolute value no larger than $t$, and
vectors $b\in\mathcal{L}(A)$, of the smallest support size of an integer
solution to $Ax=b$, i.e.

$\displaystyle h(m,t):=$ $\displaystyle\max\limits_{A\in\mathbb{Z}^{m\times
n},\left\lVert A\right\rVert_{\infty}\leq
t,b\in\mathcal{L}(A)}\min~{}\\{\|x\|_{0}\mid Ax=b,x\in\mathbb{Z}^{n}\\}$ (3)
$\displaystyle=$ $\displaystyle\max\limits_{A\in\mathbb{Z}^{m\times
n},\left\lVert A\right\rVert_{\infty}\leq t}f(A).$

There have been several efforts in obtaining good bounds for $h(m,t)$. As far
as we know, the current explicitly stated best bound appears in [2] as
$h(m,t)\leq 2m\log(2\sqrt{m}t)$. We give the following bound in this paper.

######  Theorem 1.

$h(m,t)\leq O\left(\frac{m\log(\sqrt{m}~{}t)}{\log\log(\sqrt{m}~{}t)}\right).$
(4)

The bound in (4) improves the bound in [2] by a factor of order
$\log\log(\sqrt{m}t)$. To obtain this theorem, we prove the following result,
which may be of independent interest.

Let $A$ be an integer matrix with $m$ rows and at least $m$ columns. We will
denote by $\Gamma(A)$ the largest absolute value of an $m\times m$
subdeterminant, i.e. determinant of an $m\times m$ submatrix of $A$. We denote
by $\gcd(A)$ the greatest common divisor of all $\binom{n}{m}$ such
subdeterminants of $A$, i.e.

$\displaystyle\Gamma(A):=$
$\displaystyle\max\limits_{B}~{}\\{|\det(B)|\mid\text{$B$ is an $m\times m$
submatrix of $A$}\\};$ $\displaystyle\gcd(A):=$
$\displaystyle\gcd~{}\\{|\det(B)|\mid\text{$B$ is an $m\times m$ submatrix of
$A$}\\}.$

######  Theorem 2.

Let $A$ be an integer matrix with $m$ rows and full row rank. Let $p_{i}$ be
the $i$-th prime. Then, the following relation between $\Gamma(A)$, $\gcd(A)$
and $f(A)$ holds.

$\frac{\Gamma(A)}{\gcd(A)}\geq p_{2}^{m}p_{3}^{m}\cdots
p_{\left\lfloor\frac{f(A)}{m}\right\rfloor}^{m}p_{\left\lceil\frac{f(A)}{m}\right\rceil}^{f(A)-m\left\lfloor\frac{f(A)}{m}\right\rfloor}.$
(5)

Furthermore, the bound is asymptotically tight in the sense that for
arbitrarily large integers $m$ and $t$, there exist an integer matrix $A$ with
$m$ rows, full row rank, $\left\lVert A\right\rVert_{\infty}>t$, and a vector
$b\in\mathcal{L}(A)$ such that equality holds in (5).

We will see how the bound (5) is comparable to the bound of [1]; in
particular, the proof of Theorem 2 can easily be adapted to obtain the bound
of [1].

We intend for this paper to stand out for the strength of its result, but also
for its simplicity and readability.

#### Overview.

In Section 2, we discuss related work and how the results of this paper
compare with recent developments in bounding the support size of integer
solutions to systems of equations/inequalities. In Section 3.1 we introduce
the notion of integral independence, which will be useful throughout the
proofs of Theorems 1 and 2. In particular, in Section 3.2, we achieve a
nontrivial lower bound on the largest $m\times m$ subdeterminant of a matrix
$A$ with integrally independent columns, given by Theorem 1—furthermore, this
bound increases with the number of columns. In Section 3.3, we use the
relationship between the largest subdeterminant and largest entry given by the
Hardamard bound, we achieve the upper bound on the number of columns, i.e.
$h(m,t)$, given by Theorem 1. Finally, in Section 3.4 we exhibit the matrix
$A$ referred to in the latter statement of Theorem 2.

#### Notation.

Throughout this paper we use $p_{i}$ to denote the $i$-th prime number. In
particular, $p_{1}=2$. For any $p,q\in\mathbb{Z}$, we use $p\mid q$ to denote
that $p$ divides $q$, i.e. $q/p\in\mathbb{Z}$; similarly, $p\nmid q$ to denote
that $p$ does not divide $q$; we may use this interchangeably with the
language $q$ is (respectively, is not) divisible by $p$. We use the convention
that $\gcd(a,0)=|a|$ for any $a\in\mathbb{Z}$, including $0$. We use the
notation $[n]:=\\{1,2,...,n\\}$, and, for positive integers $i\leq j$,
$[i:j]:=\\{i,i+1,...,j\\}$. For any matrix $A\in\mathbb{R}^{m\times n}$, and
$I\subseteq[m]$, $J\subseteq[n]$, we denote by $A_{I\times J}$ the submatrix
of $A$ consisting of rows indexed by $I$ and columns indexed by $J$. For
$x\in\mathbb{R}$, denote by $\left\lfloor x\right\rfloor$ the largest integer
less than or equal to $x$; $\left\lceil x\right\rceil$ the smallest integer
greater than or equal to $x$. We use $\mathbb{Z}^{n}_{\geq
0}:=\\{x\in\mathbb{Z}^{n}\mid x_{j}\geq 0\text{ for all }j\in[n]\\}$, and
$\mathbb{R}^{n}_{\geq 0}$ analogously.

##  2 Related work

Problem (2) has garnered interest from multiple research disciplines. For
example, an interesting problem is to find nonnegative integer solutions to
$Ax=b$. Define the integer conic hull generated by the columns of $A$ to be
the vectors that can be represented as nonnegative integer combinations of the
columns of $A$, i.e. $\operatorname{int\\_cone}(A):=\\{Ax\mid
x\in\mathbb{Z}_{\geq 0}^{n}\\}$. Let

$\displaystyle g(m,t):=\max_{A\in\mathbb{Z}^{m\times n},~{}\left\lVert
A\right\rVert_{\infty}\leq
t,~{}b\in\operatorname{int\\_cone}(A)}\min~{}\\{\|x\|_{0}\mid
Ax=b,x\in\mathbb{Z}_{\geq 0}^{n}\\}.$ (6)

It is easy to see that $h(m,t)\leq g(m,t)$, since any solution to
$Ax=b,~{}x\in\mathbb{Z}_{\geq 0}^{n}$ is also a solution to
$Ax=b,~{}x\in\mathbb{Z}^{n}$. Thus an upper bound on $g(m,t)$ can serve as an
upper bound for $h(m,t)$. [7] establishes the first upper bound on $g(m,t)$
using the pigeonhole principle. They show $g(m,t)\leq 2m\log(4mt)$. The bound
has been improved by [2] to $g(m,t)\leq 2m\log(2\sqrt{m}t)$ using Siegel’s
lemma [3]. These upper bounds on $g(m,t)$ have often been used as the best
available upper bound on $h(m,t)$. Note that the bound of Theorem 1 improves
these bounds on $h(m,t)$ by a factor of $O(\log\log(\sqrt{m}t))$. [2] also
establishes an asymptotic lower bound for $g(m,t)$: for any $\epsilon>0$,
there exist a matrix $A\in\mathbb{Z}^{m\times n}$ with $n/m$ large enough and
a vector $b\in\operatorname{int\\_cone}(A)$, such that
$\min~{}\\{\|x\|_{0}\mid Ax=b,x\in\mathbb{Z}_{\geq 0}^{n}\\}\geq
m\log(\left\lVert A\right\rVert_{\infty})^{\frac{1}{1+\epsilon}}$.

Another interesting direction is when the columns of matrix $A$ form a Hilbert
basis, i.e. $\\{b:Ax,x\in\mathbb{Z}_{\geq
0}^{n}\\}=\\{b:Ax,x\in\mathbb{R}_{\geq 0}^{n}\\}\cap\mathbb{Z}^{n}$; in other
words, for any $b$ in $\operatorname{cone}(A)\cap\mathbb{Z}^{n}$, $b$ is also
in $\operatorname{int\\_cone}(A)$, where $\operatorname{cone}(A):=\\{Ax\mid
x\in\mathbb{R}_{\geq 0}^{n}\\}$. [5] shows that when $\operatorname{cone}(A)$
is pointed and the columns of $A$ form an integral Hilbert basis, $g(m,t)\leq
2m-1$. [12] improves this bound to $2m-2$. Note that the bound is independent
of $\left\lVert A\right\rVert_{\infty}$.

As far as we know, the most relevant paper in the literature is [1], where
they establish an upper bound for $f(A)$ and show that it is optimal. For any
$z\in\mathbb{Z}_{>0}$, consider the prime factorization $z=q_{1}^{s_{1}}\cdots
q_{k}^{s_{k}}$ such that $q_{1},...,q_{k}$ are pairwise distinct. [1]
introduces $\Omega_{m}(z):=\sum_{i=1}^{k}\min\\{s_{i},m\\}$, called truncated
prime $\Omega$-funciton. Let $\binom{[n]}{m}$ be all the subsets of $[n]$ of
cardinality $m$ and for $\tau\in\binom{[n]}{m}$, let $A_{\tau}$ be the
$m\times m$ submatrix of $A$ with columns indexed by $\tau$. They show

$\displaystyle f(A)\leq m+\min_{\tau\in\binom{[n]}{m},\det(A_{\tau})\neq
0}\Omega_{m}\left(\frac{|\det(A_{\tau})|}{\gcd(A)}\right).$ (7)

They also show this bound is optimal in the sense that neither $m$ can be
replaced by any smaller constant nor the function $\Omega_{m}$ can be replaced
by any smaller function.

The proof of bound (7) relies on the connection between the theory of finite
Abelian groups and lattice theory. In particular, they use the primary
decomposition theorem of finite Abelian groups (see e.g. Chapter 5.2 in [6])
and group representation of lattices (see e.g. Section 4.4 of [11]). In
contrast, the approach in this paper is significantly simpler, only using
linear algebra. The proof is self-contained and does not require knowledge of
group theory or lattice theory. Moreover, we will show how the bound (7) can
be obtained as a byproduct of our proof of Theorem 2.

##  3 Proof of Theorems 1 and 2

###  3.1 Integral independence

We introduce the notion of integral independence in this section.

######  Definition 3.

A set of vectors $\\{a_{1},...,a_{n}\\}$ is called _integrally dependent_ if
there is some $k\in[n]$ such that $a_{k}=\sum_{i\not=k}\mu_{i}a_{i}$, where
every $\mu_{i}$ is an integer, and _integrally independent_ otherwise.
Furthermore, if $A$ is a matrix with integrally independent columns, we call
the matrix itself integrally independent.

The integral independence is closely related to the smallest support of
integral solutions to equation $Ax=b$, which we will elaborate on in the
following proposition.

######  Proposition 4.

Let $A$ be a matrix with columns $a_{1},...,a_{n}\in\mathbb{Z}^{m}$. Then, the
following are equivalent:

  1. 1.

the vectors $\\{a_{1},...,a_{n}\\}$ are integrally independent;

  2. 2.

there exists a vector $b\in\mathcal{L}(A)$ such that $\left\lVert
x\right\rVert_{0}=n$ for any integer solution $x$ to $Ax=b$;

  3. 3.

there is no integer vector in the null space of $A$ with an entry equal to
$1$, i.e. $\\{x\in\mathbb{Z}^{n}:Ax=0,~{}\exists j\in[n]\text{ such that
}x_{j}=1\\}=\emptyset$.

###### Proof.

We start by proving $(1)\implies(2)$. Let $b=\sum_{i\in[n]}a_{i}$. Consider an
integral vector $x\in\mathbb{Z}^{n}$ such that
$\sum_{i\in[n]}a_{i}x_{i}=\sum_{i\in[n]}a_{i}$. For sake of contradiction,
assume some component of $x$ is zero; without loss of generality, assume
$x_{n}=0$. Then, $\sum_{i\in[n-1]}a_{i}x_{i}=\sum_{i\in[n]}a_{i}$. It follows
that $a_{n}=-\sum_{i\in[n-1]}(1-x_{i})a_{i}$, where $a_{n}$ is an integral
combination of $\\{a_{1},...,a_{n-1}\\}$, a contradiction.

We now prove $(2)\implies(1)$. Let $b\in\mathcal{L}(A)$ be such that every
integral $x$ with $Ax=b$ has $\left\lVert x\right\rVert_{0}=n$. Further let
$x^{\prime}$ be one such choice of $x$ and write
$b=\sum_{i\in[n]}a_{i}x^{\prime}_{i}$. Suppose for sake of contradiction that
$\\{a_{1},...,a_{n}\\}$ is integrally dependent. Then, by definition, there is
some $k\in[n]$ and $\mu\in\mathbb{Z}^{n-1}$ such that
$a_{k}=\sum_{i\not=k}\mu_{i}a_{i}$. So, we can write

$b=\sum_{i\not=k}a_{i}x^{\prime}_{i}+\sum_{i\not=k}x^{\prime}_{k}\mu_{i}a_{i}=\sum_{i\not=k}(x^{\prime}_{i}+\mu_{i}x^{\prime}_{k})a_{i}.$

It follows from $x^{\prime}$ and $\mu$ are both integral that each
$(x^{\prime}_{i}+\mu_{i}x^{\prime}_{k})$ is integral. Then, $b$ can be written
as an integral combination of $\\{a_{1},...,a_{n}\\}\setminus\\{a_{k}\\}$,
contradicting the fact that $\left\lVert x\right\rVert_{0}=n$ for every
integral $x$ such that $Ax=b$.

We now prove $(1)\implies(3)$. Suppose there is some
$x\in\mathbb{Z}^{n}\setminus\\{0\\}$ such that $\sum_{i\in n}a_{i}x_{i}=0$;
and without loss of generality, assume $x_{n}=1$. Then, we can rewrite this as
$a_{n}=\sum_{i\in[n-1]}\frac{x_{i}}{x_{n}}a_{i}=\sum_{i\in[n-1]}x_{i}a_{i}$.
Therefore, $\\{a_{1},...,a_{n}\\}$ is integrally dependent.

We now prove $(3)\implies(1)$. Suppose that $\\{a_{1},...,a_{n}\\}$ is
integrally dependent. Then, by definition, there exists a $k\in[n]$ such that
$a_{k}=\sum_{i\not=k}\mu_{i}a_{i}$, where every $\mu_{i}$ integer. Therefore,
vector
$\begin{pmatrix}-\mu_{1}&-\mu_{2}&...&-\mu_{k-1}&1&-\mu_{k+1}&...&\mu_{n}\end{pmatrix}$
is in the null space of $A$. ∎

###  3.2 Upper bound on $f(A)$

Applying unimodular column operations, we can bring $A$ into Hermite normal
form $H=\begin{pmatrix}D&0\end{pmatrix}$, where $D\in\mathbb{Z}^{m\times m}$
is a lower triangular matrix. We have the relation
$AU=\begin{pmatrix}D&0\end{pmatrix}$, where $U\in\mathbb{Z}^{n\times n}$ is a
unimodular matrix corresponding to the unimodular operations (see e.g. Section
1.5.2 in [4]). To proceed, we remind readers of some basic facts about
unimodular operations.

######  Fact 1.

Let $C$ be any $m\times n$ integer matrix where $m\leq n$, and $V$ be an
$n\times n$ unimodular matrix. Then, the greatest common divisor (GCD) of all
$m\times m$ subdeterminants of $CV$ is equal to the GCD of all $m\times m$
subdeterminants of $C$.

######  Fact 2.

The GCD of all $m\times m$ subdeterminants of $C$ is zero (i.e. all $m\times
m$ subdeterminants of $C$ are $0$) if and only if the rows of $C$ are linearly
dependent.

The first fact follows from the GCD of all $m\times m$ subdeterminants of $C$
being invariant under unimodular column operations (see, e.g., Section 4.4 of
[11]). To see the second fact, we can bring $C$ into its Hermite normal form
$\begin{pmatrix}C^{\prime}&0\end{pmatrix}$ by applying unimodular column
operations $V$, i.e. $CV=\begin{pmatrix}C^{\prime}&0\end{pmatrix}$. By the
first fact, the GCD of all $m\times m$ subdeterminants of $C$ equals to that
of $CV$, which is $\det(C^{\prime})$. Thus, the GCD is $0$ if and only if
$\det(C^{\prime})=0$, which means the rows of $C^{\prime}$ are linearly
dependent. Since $V$ is unimodular and thus nonsingular, the rows of
$C^{\prime}$ are linearly dependent if and only if the rows of $C$ are
linearly dependent. Furthermore, it may be useful to recall that the Hermite
normal form of a matrix is unique. Due to these facts and the properties of
unimodular matrices, we have the following lemma.

######  Lemma 5.

Let $A\in\mathbb{Z}^{m\times n}$ be a matrix with integrally independent
columns. Let $H=AU$ be the Hermite normal form of $A$, where $U$ is a
unimodular matrix. Suppose $U=\begin{pmatrix}U_{1}&U_{2}\end{pmatrix}$, where
$U_{1}\in\mathbb{Z}^{n\times m},U_{2}\in\mathbb{Z}^{n\times(n-m)}$. Then
$U_{2}$ must satisfy the following properties:

  1. (P1).

$U_{2}$ has at least one nonsingular $(n-m)\times(n-m)$ submatrix.

  2. (P2).

The GCD of all $(n-m)\times(n-m)$ subdeterminants of $U_{2}$ is $1$.

  3. (P3).

For each row $i$ of $U_{2}$, there exists some prime $q_{i}\geq 2$ such that
$q_{i}\mid(U_{2})_{ij}$ for all $j\in[n-m]$.

###### Proof.

It follows from $U^{-1}U=I$ that
$U_{2}^{\top}(U^{-1})^{\top}=\begin{pmatrix}I_{n-m}&0\end{pmatrix}$. Together
with the fact that $(U^{-1})^{\top}$ is unimodular we obtain that the Hermite
normal form of $U_{2}^{\top}$ is the $(n-m)\times(n-m)$ identity martix
$I_{n-m}$. According to Fact 1, the GCD of all $(n-m)\times(n-m)$
subdeterminants of $U_{2}$ equals to $1$, proving (P2). In particular, it is
nonzero and thus by Fact 2, $U_{2}$ has rank $n-m$ and therefore has a
nonsingular $(n-m)\times(n-m)$ submatrix, proving (P1).

It remains to prove property (P3). Since
$A\begin{pmatrix}U_{1}&U_{2}\end{pmatrix}=\begin{pmatrix}D&0\end{pmatrix}$,
for $D\in\mathbb{Z}^{m\times m}$ some lower triangular matrix, we notice that
columns of $U_{2}$ are in the null space of $A$. Since the columns of $A$ are
integrally independent, by Proposition 4, any integral $x$ in the null space
of $A$ has no entry equal to $1$. Suppose for the sake of contradiction, the
entries in row $i$ of $U_{2}$ have GCD $1$. Then, by Bézout’s theorem there
exists an integral $\mu\in\mathbb{Z}^{n-m}$ such that
$\sum_{j=1}^{n-m}\mu_{j}(U_{2})_{ij}=1$. Then $x=U_{2}\mu$ is an integral
vector in the null space of $A$ with $x_{i}=1$, which contradicts the integral
independence of $A$. Therefore, for any row of $U_{2}$, its entries must have
a common divisor strictly greater than $1$, and therefore a prime that is at
least $2$. ∎

The following is key to derive Theorem 2 of this paper. It establishes a lower
bound for the largest $m\times m$ subdeterminant of a matrix with integrally
independent columns.

######  Theorem 6.

Let matrix $A\in\mathbb{Z}^{m\times n}$ be of full row rank with integrally
independent columns. Let $p_{i}$ be the $i$-th prime. Then,

$\frac{\Gamma(A)}{\gcd(A)}\geq p_{2}^{m}p_{3}^{m}\cdots
p_{\left\lfloor\frac{n}{m}\right\rfloor}^{m}p_{\left\lceil\frac{n}{m}\right\rceil}^{n-m\left\lfloor\frac{n}{m}\right\rfloor}.$

To prove this theorem, we need to introduce Jacobi’s Theorem (see Theorem
2.5.2 of [10]), which uses linear algebra to establish the relation between
the subdeterminant of a matrix and its inverse.

######  Lemma 7.

[Jacobi] Let $A\in\mathbb{R}^{n\times n}$, $A=(a_{ij})_{1}^{n}$. For any
$I,J\subseteq[n]$, denote $A_{I\times J}$ be the submatrix of $A$ consisting
of rows indexed by $I$ and columns indexed by $J$. Let
$A^{*}=(a_{ij}^{*})_{1}^{n}$ be the classical adjoint of $A$, where

$a^{*}_{ij}=(-1)^{i+j}\det(A_{[n]\setminus\\{j\\}~{}\times~{}[n]\setminus\\{i\\}})$

is the cofactor of element $a_{ji}$ in $A$. Let
$\sigma=\begin{pmatrix}i_{1}&i_{2}&\cdots&i_{n}\\\
j_{1}&j_{2}&\cdots&j_{n}\end{pmatrix}$ be an arbitrary permutation. Let $1\leq
p\leq n$. Let $I=\\{i_{1},...i_{p}\\}$, $J=\\{j_{1},...,j_{p}\\}$,
$I^{\prime}=\\{i_{p+1},...,i_{n}\\}$, $J^{\prime}=\\{j_{p+1},...,j_{n}\\}$.
Then,

$\det(A^{*}_{I\times J})=(-1)^{\sigma}\det(A_{J^{\prime}\times
I^{\prime}})\cdot\det(A)^{p-1}.$

To prove Theorem 6, we will use the following direct corollary of Lemma 7.

######  Corollary 8.

Let $U\in\mathbb{R}^{n\times n}$ be a unimodular matrix. Then for any
$I\subseteq[n]$, $J\subseteq[n]$,

$det((U^{-1})_{I\times J})=\pm det(U_{[n]\backslash J~{}\times~{}[n]\backslash
I}),$ (8)

where $U_{I\times J}$ denotes the submatrix of $U$ consisting of rows indexed
by $I$ and columns indexed by $J$.

###### Proof of Theorem 6.

Suppose by applying unimodular column operations, we bring $A$ into Hermite
normal form $H=\begin{pmatrix}D&0\end{pmatrix}$, where
$D\in\mathbb{Z}^{m\times m}$ is a lower triangular matrix. We obtain the
relation of $AU=\begin{pmatrix}D&0\end{pmatrix}$, where
$U\in\mathbb{Z}^{n\times n}$ is a unimodular matrix. Let
$U=\begin{pmatrix}U_{1}&U_{2}\end{pmatrix}$, where
$U_{1}\in\mathbb{Z}^{n\times m},U_{2}\in\mathbb{Z}^{n\times(n-m)}$.

Recall property (P3) of $U_{2}$ in Lemma 5 saying that for each row $i$ of
$U_{2}$, there exists some prime $q_{i}\geq 2$ such that
$q_{i}\mid(U_{2})_{ij}$ for all $j\in[n-m]$. For any prime $q$, let
$I_{q}:=\\{i\in[n]:q\mid(U_{2})_{ij},\forall j\in[n-m]\\}$ be the indices of
rows of $U_{2}$ which are divisible by $q$. Notice for any prime $q$, $U_{2}$
must have a nonsingular $(n-m)\times(n-m)$ submatrix $(U_{2})_{I\times[n-m]}$
with $I\subseteq[n]\setminus I_{q}$, $|I|=n-m$. Suppose for sake of
contradiction that every nonsingular $(n-m)\times(n-m)$ submatrix of $U_{2}$
includes at least one row whose index is in $I_{q}$. Since such a row is
divisible by $q$, the determinant of such a submatrix must also be divisible
by $q$. Therefore if every nonsingular $(n-m)\times(n-m)$ submatrix of $U_{2}$
includes at least one such row, the GCD of the $\binom{n}{n-m}$ such
subdeterminants is at least $q\geq 2$, contradicting property (P2) in Lemma 5.
Therefore, by the pigeonhole principle, $|I_{q}|\leq n-|I|=m$ for any prime
$q$.

Recall $p_{i}$ is the $i$-th prime and $q_{i}\geq 2$ is a prime that divides
row $i$ of $U_{2}$. The above argument implies that $U_{2}$ has a nonsingular
$(n-m)\times(n-m)$ submatrix, denoted as $V$, whose row indices are in
$[n]\setminus I_{p_{1}}$. Assume $V$ consists of the first $n-m$ rows of
$U_{2}$ without loss of generality. Then, we have

$q_{1}q_{2}\cdots q_{n-m}~{}\Big{|}~{}|\det(V)|$

Notice that each prime $p_{i}$ appears at most $m$ times among
$\\{q_{1},...,q_{n-m}\\}$, since $|I_{q}|\leq m$ for any prime $q$ and $p_{1}$
never appears in $\\{q_{1},...,q_{n-m}\\}$. It follows from $\det(V)\neq 0$
that

$|\det(V)|\geq q_{1}q_{2}\cdots q_{n-m}\geq p_{2}^{m}p_{3}^{m}\cdots
p_{\left\lfloor\frac{n}{m}\right\rfloor}^{m}p_{\left\lceil\frac{n}{m}\right\rceil}^{n-m\left\lfloor\frac{n}{m}\right\rfloor}.$

Moreover, we use the relation between the determinant of the submatrix of $A$
and $U$ to bound above $\det(V)$. Notice
$A=\begin{pmatrix}D&0\end{pmatrix}U^{-1}$ and thus
$A_{[m]\times[n-m+1:n]}=D\cdot(U^{-1})_{[m]\times[n-m+1:n]}$. We have

$\displaystyle|\det(A_{[m]\times[n-m+1:n]})|=$
$\displaystyle|\det(D)|\cdot|\det((U^{-1})_{[m]\times[n-m+1:n]})|$
$\displaystyle=$
$\displaystyle\gcd(A)\cdot|\det((U^{-1})_{[m]\times[n-m+1:n]})|$
$\displaystyle=$ $\displaystyle\gcd(A)\cdot|\det(U_{[n-m]\times[m+1:n]})|$
$\displaystyle=$ $\displaystyle\gcd(A)\cdot|\det(V)|,$

where the second equality follows from Fact 1 and the third equality follows
from Corollary 8. Recall $\Gamma(A)$ is the largest absolute value of an
$m\times m$ subdeterminant of $A$. Combining them together we obtain

$\displaystyle\frac{\Gamma(A)}{\gcd(A)}\geq$
$\displaystyle\frac{|\det(A_{[m]\times[n-m+1:n]})|}{\gcd(A)}$ $\displaystyle=$
$\displaystyle|\det(V)|$ $\displaystyle\geq$ $\displaystyle
p_{2}^{m}p_{3}^{m}\cdots
p_{\left\lfloor\frac{n}{m}\right\rfloor}^{m}p_{\left\lceil\frac{n}{m}\right\rceil}^{n-m\left\lfloor\frac{n}{m}\right\rfloor},$

as desired. ∎

Recall from Proposition 4 that a matrix $A$ has integrally independent columns
if and only if there exists some $b$ such that every integer solution to
$Ax=b$ has full support. Taking advantage of this observation, Theorem 6 can
be naturally adapted to derive an upper bound for $f(A)$, i.e. the maximum,
taken over $b\in\mathcal{L}(A)$, of smallest support size of an integer
solution to $Ax=b$ (formally defined in (2)). This yields the proof of one of
our main results.

###### Proof of Theorem 2.

Take $b$ such that $Ax=b$ has maximum smallest support size of an integer
solution to $Ax=b$, i.e. $\min~{}\\{\|x\|_{0}\mid
Ax=b,x\in\mathbb{Z}^{n}\\}=f(A)$. Let $x^{*}$ be an integral solution to
$Ax=b$ with smallest support, i.e. $\left\lVert x^{*}\right\rVert_{0}=f(A)$.
We can assume without loss of generality that $A\in\mathbb{Z}^{m\times f(A)}$
by deleting the columns $j$ of $A$ corresponding to $x^{*}_{j}=0$ for
$j\in[n]$. This will not increase $\Gamma(A)$, the largest $m\times m$
subdeterminant of $A$, and will not decrease $\gcd(A)$, the GCD of all
$m\times m$ subdeterminants of $A$ (this is easily seen by the fact that
redundant columns can be zeroed out using unimodular column operations). Thus
it suffices to prove inequality (5) after deleting redundent columns of $A$.
By the minimality of support size of $x^{*}$, any integer solution to $Ax=b$
has full support. By Proposition 4, columns of $A$ are integrally independent.
It follows from Theorem 6 that inequality (5) holds. ∎

######  Remark 1.

We demonstrate how to modify the proof of Theorem 6 to obtain the bound (7)
given in [1]. We use the same notation as in the proof of Theorem 6. For any
$m\times m$ submatrix of $A$ whose columns are indexed by $J$ where $|J|=m$,
we have

$\displaystyle|\det(A_{[m]\times J})|=$
$\displaystyle|\det(D)|\cdot|\det((U^{-1})_{[m]\times J})|$ $\displaystyle=$
$\displaystyle\gcd(A)\cdot|\det((U^{-1})_{[m]\times J})|$ $\displaystyle=$
$\displaystyle\gcd(A)\cdot|\det(U_{[n]\backslash J~{}\times~{}[m+1:n]})|.$

We also know that

$\prod_{i\in[n]\backslash J}q_{i}~{}\Big{|}~{}|\det(U_{[n]\backslash
J~{}\times~{}[m+1:n]})|,$

and thus

$\prod_{i\in[n]\backslash J}q_{i}~{}\Big{|}~{}\frac{|\det(A_{[m]\times
J})|}{\gcd(A)},$

where $q_{i},i\in[n]\backslash J$ are primes numbers and with the same prime
repeating at most $m$ times in $\\{q_{i}\mid i\in[n]\backslash J\\}$. Recall
notation $\Omega_{m}(z)=\sum_{i=1}^{k}\min\\{s_{i},m\\}$ for the prime
factorization of $z=r_{1}^{s_{1}}\cdots r_{k}^{s_{k}}$ with multiplicities
$s_{1},...,s_{k}\in\mathbb{Z}_{>0}$. Clearly, when $x\mid y$,
$\Omega_{m}(x)\leq\Omega_{m}(y)$. Thus,
$\Omega_{m}\left(\prod_{i\in[n]\backslash
J}q_{i}\right)\leq\Omega_{m}\left(\frac{|\det(A_{[m]\times
J})|}{\gcd(A)}\right)$. Moreover, since the multiplicity of each $q_{i}$ in
$\prod_{i\in[n]\backslash J}q_{i}$ is at most $m$, we have
$\Omega_{m}\left(\prod_{i\in[n]\backslash J}q_{i}\right)=|[n]\backslash
J|=n-m$. Therefore, $n-m\leq\Omega_{m}\left(\frac{|\det(A_{[m]\times
J})|}{\gcd(A)}\right)$. Since $J$ is an arbitrary subset of $[n]$ with
cardinality $m$, we obtain $n\leq
m+\min_{\tau\in\binom{[n]}{m},\det(A_{\tau})\neq
0}\Omega_{m}\Big{(}\frac{|\det(A_{\tau})|}{\gcd(A)}\Big{)}$. Applying the same
argument as in the proof of Theorem 2 above, we obtain $f(A)\leq
m+\min_{\tau\in\binom{[n]}{m},\det(A_{\tau})\neq
0}\Omega_{m}\Big{(}\frac{|\det(A_{\tau})|}{\gcd(A)}\Big{)}$.

###  3.3 Upper bound on $h(m,t)$

Recall $h(m,t)$ is the maximum, taken over all integer matrices $A$ with $m$
rows and largest entry $t$, of the smallest support size of an integer
solution to $Ax=b$ for some $b\in\mathcal{L}(A)$ (formally defined in (3)).
Using a relation between the size of largest entry of a matrix and the size of
its subdeterminant, we want to use results in Section 3.2 to obtain an upper
bound for $h(m,t)$. We will use the well-known Hadamard inequality [8], which
gives us an upper bound on the determinant of a matrix, i.e. for any matrix
$B\in\mathbb{R}^{m\times m}$,

$|\det(B)|\leq(\sqrt{m}\left\lVert B\right\rVert_{\infty})^{m}.$

Applying this to inequality (5), we obtain the following corollary.

######  Corollary 9.

$h(m,t)$ satisfies

$(\sqrt{m}~{}t)^{m}\geq p_{2}^{m}p_{3}^{m}\cdots
p_{\left\lfloor\frac{h(m,t)}{m}\right\rfloor}^{m}p_{\left\lceil\frac{h(m,t)}{m}\right\rceil}^{h(m,t)-m\left\lfloor\frac{h(m,t)}{m}\right\rfloor}.$
(9)

###### Proof.

Suppose $A\in\mathbb{Z}^{m\times n}$ is a full row rank matrix with
$\left\lVert A\right\rVert_{\infty}\leq t$ and $b\in\mathcal{L}(A)$ such that
it has the smallest support of any integer solution to $Ax=b$ is the maximum
possible, i.e. $\min\\{\|x\|_{0}\mid Ax=b,x\in\mathbb{Z}^{n}\\}=h(m,t)$. Then
inequality (9) follows directly from Theorem 2 and Hadamard’s inequality. ∎

Furthermore, we can prove the upper bound on $h(m,t)$ of Theorem 1 by applying
prime number theorem to approximate the product of the first $k$ primes
$\prod\limits_{i=1}^{k}p_{i}$.

###### Proof of Theorem 1.

According to the prime number theorem, the product of the first $k$ primes
$\prod\limits_{i=1}^{k}p_{i}\sim e^{(1+o(1))k\log k}$, where $\log(\cdot)$ is
the natural logarithm (see e.g. [13]). Let $n=h(m,t)$. Relaxing (9), we have

$(\sqrt{m}~{}t)^{m}\geq p_{2}^{m}p_{3}^{m}\cdots
p_{\left\lfloor\frac{n}{m}\right\rfloor}^{m}p_{\left\lceil\frac{n}{m}\right\rceil}^{n-m\left\lfloor\frac{n}{m}\right\rfloor}\geq(p_{1}p_{2}\cdots
p_{\left\lfloor\frac{n}{m}\right\rfloor})^{m}/2^{m}.$

Taking logarithm and applying $\prod\limits_{i=1}^{k}p_{i}\sim
e^{(1+o(1))k\log k}$, we have

$\log(\sqrt{m}~{}t)\geq\log(p_{1}p_{2}\cdots
p_{\left\lfloor\frac{n}{m}\right\rfloor})-\log 2\geq
C\left\lfloor\frac{n}{m}\right\rfloor\log\left\lfloor\frac{n}{m}\right\rfloor$

for some constant $C$.

We claim that
$\left\lfloor\frac{n}{m}\right\rfloor=O\left(\frac{\log(\sqrt{m}~{}t)}{\log\log(\sqrt{m}~{}t)}\right)$.
Suppose not, we assume
$\left\lfloor\frac{n}{m}\right\rfloor>\frac{2\log(\sqrt{m}~{}t)}{C\log\log(\sqrt{m}~{}t)}$
for some $m$ that is arbitrarily large. Thus,

$\log(\sqrt{m}~{}t)\geq
C\left\lfloor\frac{n}{m}\right\rfloor\log\left\lfloor\frac{n}{m}\right\rfloor>\frac{2\log(\sqrt{m}~{}t)}{\log\log(\sqrt{m}~{}t)}\Big{(}\log\log(\sqrt{m}~{}t)-\log\big{(}C\log\log(\sqrt{m}~{}t)\big{)}\Big{)}.$

This will give us

$2\log\big{(}C\log\log(\sqrt{m}~{}t)\big{)}>\log\log(\sqrt{m}~{}t),$

which is not going to hold when $m$ is arbitrarily large, a contradiction.
Thus, we have
$\left\lfloor\frac{n}{m}\right\rfloor=O\left(\frac{\log(\sqrt{m}~{}t)}{\log\log(\sqrt{m}~{}t)}\right)$.
It follows that
$n=O\left(\frac{m\log(\sqrt{m}~{}t)}{\log\log(\sqrt{m}~{}t)}\right)$. ∎

###  3.4 Lower bound on $f(A)$

Finally, we prove the latter statement of Theorem 2 by giving an example
integer matrix $A$ with arbitrarily large number of rows $m$ and $\left\lVert
A\right\rVert_{\infty}$, showing that the upper bound on $f(A)$ is
asymptotically tight. A similar construction has appeared in [2, 1] to prove
lower bounds on support size of integer solutions.

######  Proposition 10.

For arbitrarily large $(m,t)$, there exists $A$ with $m$ rows, full row rank,
and $\left\lVert A\right\rVert_{\infty}>t$, and $b\in\mathcal{L}(A)$ such that
equality holds in (5). In other words, the bound in Theorem 2 is
asymptotically tight.

###### Proof.

Let $p_{i}$ be the $i$-th prime. There exists $k$ such that $p_{2}p_{3}\cdots
p_{k}>t$. Let $n=km$. Define $A\in\mathbb{Z}^{m\times n}$ as

$\displaystyle A_{ij}=\begin{cases}p_{1}p_{2}\cdots
p_{k}/p_{r}&~{}~{}j=(i-1)k+r,~{}1\leq r\leq k\\\
~{}~{}~{}0&~{}~{}o.w.\end{cases}$

and $b=A\mathbf{1}$. Then, $\left\lVert
A\right\rVert_{\infty}=p_{2}p_{3}\cdots p_{k}>t$. For any $i\in[m]$,
$b_{i}=\sum_{r=1}^{k}p_{1}p_{2}\cdots p_{k}/p_{r}$. Observe that $p_{j}\nmid
b_{i}$, $\forall i=1,...,m,j=1,...,k$. Any $x\in\mathbb{Z}^{n}$ with
$\left\lVert x\right\rVert_{0}<n$ would have $x_{j}=0$ for some $j=(i-1)k+r$
with $1\leq r\leq k$. Thus, $(Ax)_{i}=\sum_{s=1,s\neq r}^{k}(p_{1}p_{2}\cdots
p_{k}/p_{s})x_{(i-1)k+s}$. Since $p_{r}\mid(p_{1}p_{2}\cdots p_{k}/p_{s})$,
$\forall s\neq r$, we have $p_{r}\mid(Ax)_{i}$. Thus, $Ax\neq b$, which means
any integer $x$ with $\left\lVert x\right\rVert_{0}<n$ is not a solution to
$Ax=b$. Therefore, any integer solution of $Ax=b$ has smallest support size
$n=km$. Moreover, $\Gamma(A)=\max\limits_{B}~{}\\{|\det(B)|\mid\text{$B$ is an
$m\times m$ submatrix of $A$}\\}=p_{2}^{m}p_{3}^{m}\cdots p_{k}^{m}$, matching
the right hand side in (5). ∎

## Acknowledgements

This work was supported by ONR grant N00014-22-1-2528 and a Balas PhD
Fellowship. We acknowledge the invaluable discussions with Ahmad Abdi, Gérard
Cornuéjols, and Levent Tunçel, without whom this project would not have been
possible. We also thank Ahmad Abdi and Timm Oertel for feedback that very much
improved the presentation of these results.

## Declarations

The authors have no conflicts of interest or competing interests.

## References

  * AADLO [22] Iskander Aliev, Gennadiy Averkov, Jesús A De Loera, and Timm Oertel.  Sparse representation of vectors in lattices and semigroups.  Mathematical Programming, 192(1-2):519–546, 2022.
  * ADLE+ [18] I Aliev, JA De Loera, F Eisenbrand, T Oertel, and R Weismantel.  The support of integer optimal solutions.  SIAM Journal on Optimization, 28(3):2152–2157, 2018.
  * BV [83] Enrico Bombieri and Jeffrey Vaaler.  On siegel’s lemma.  Inventiones mathematicae, 73(1):11–32, 1983.
  * CCZ+ [14] Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al.  Integer programming, volume 271.  Springer, 2014.
  * CFS [86] William Cook, Jean Fonlupt, and Alexander Schrijver.  An integer analogue of caratheodory’s theorem.  Journal of Combinatorial Theory, Series B, 40(1):63–70, 1986.
  * DF [04] David Steven Dummit and Richard M Foote.  Abstract algebra, volume 3.  Wiley Hoboken, 2004.
  * ES [06] Friedrich Eisenbrand and Gennady Shmonin.  Carathéodory bounds for integer cones.  Operations Research Letters, 34(5):564–568, 2006.
  * Had [93] Jacques Hadamard.  Resolution d’une question relative aux determinants.  Bull. des sciences math., 2:240–246, 1893.
  * Nat [95] Balas Kausik Natarajan.  Sparse approximate solutions to linear systems.  SIAM journal on computing, 24(2):227–234, 1995.
  * Pra [94] Viktor Vasil_evich Prasolov.  Problems and theorems in linear algebra, volume 134.  American Mathematical Soc., 1994.
  * Sch [98] Alexander Schrijver.  Theory of linear and integer programming.  John Wiley & Sons, 1998.
  * Seb [90] András Sebö.  Hilbert bases, caratheodory’s theorem and combinatorial optimization.  In Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, pages 431–455, 1990.
  * Zag [97] Don Zagier.  Newman’s short proof of the prime number theorem.  The American mathematical monthly, 104(8):705–708, 1997.


$\sum_{i=1}^{A}\alpha_{i}=\sum_{j=1}^{B}(\mathcal{E}_{j}-\beta_{j})$ and for
all $s$ it holds $d_{0,\boldsymbol{X}_{s}}=d_{0,\boldsymbol{X}_{1}}$, we
obtain

$\sum_{j=1}^{B}\mathcal{E}_{j}\;\Big{(}\sum_{s=1}^{A}d_{0,\boldsymbol{X}_{s}}\theta_{j,s}^{X}\Big{)}=\sum_{j=1}^{B}\mathcal{E}_{j}\;\Big{(}\sum_{s=1}^{A}d_{0,\boldsymbol{X}_{s}}\Upsilon\frac{\alpha_{s}}{\sum_{i=1}^{A}\alpha_{i}}\frac{\mathcal{E}_{j}-\beta_{j}}{\mathcal{E}_{j}}\Big{)}=\Upsilon\,d_{0,\boldsymbol{X}_{1}}\sum_{i=1}^{A}\alpha_{i}.$

For the second one, we perform the following direct calculations

$\sum_{j=1}^{B}\mathcal{E}_{j}\;(\sum_{l=1}^{B}d_{0,\boldsymbol{Y}_{t}}\theta_{j,t}^{Y})=\sum_{j=1}^{B}\mathcal{E}_{j}\;\Big{(}\sum_{t\in\\{1,\dots,B\\}\setminus\\{j\\}}d_{0,\boldsymbol{Y}_{t}}\Upsilon\frac{\beta_{t}}{\mathcal{E}_{t}-\beta_{t}+1}\frac{\mathcal{E}_{j}-\beta_{j}}{\mathcal{E}_{j}}+d_{0,\boldsymbol{Y}_{j}}\Upsilon\frac{\beta_{j}}{\mathcal{E}_{j}}\Big{)}=\\\
\Upsilon\;\sum_{j=1}^{B}\Big{(}\sum_{t=1}^{B}d_{0,\boldsymbol{Y}_{t}}\cdot\frac{\beta_{t}}{\mathcal{E}_{t}-\beta_{t}+1}(\mathcal{E}_{j}-\beta_{j})-d_{0,\boldsymbol{Y}_{j}}\cdot\frac{\beta_{j}(\mathcal{E}_{j}-\beta_{j})}{\mathcal{E}_{j}-\beta_{j}+1}+d_{0,\boldsymbol{Y}_{j}}\beta_{j}\Big{)}=\\\
\Upsilon\;\sum_{j=1}^{B}(\mathcal{E}_{j}-\beta_{j})\Big{(}\sum_{t=1}^{B}d_{0,\boldsymbol{Y}_{t}}\cdot\frac{\beta_{t}}{\mathcal{E}_{t}-\beta_{t}+1}\Big{)}+\Upsilon\;\sum_{j=1}^{B}d_{0,\boldsymbol{Y}_{j}}\cdot\frac{\beta_{j}}{\mathcal{E}_{j}-\beta_{j}+1}=\\\
\Upsilon\;(1+\sum_{i=1}^{A}\alpha_{i})\Big{(}\sum_{t=1}^{B}d_{0,\boldsymbol{Y}_{t}}\cdot\frac{\beta_{t}}{\mathcal{E}_{t}-\beta_{t}+1}\Big{)}.$

At last we have the formula

$\displaystyle\deg(\mathrm{Res}_{\mathcal{P}}(\boldsymbol{d}_{0},\dots,\boldsymbol{d}_{n}))=\Upsilon\Big{(}1+d_{0,\boldsymbol{X}_{1}}\sum_{i=1}^{A}\alpha_{i}+(1+\sum_{i=1}^{A}\alpha_{i})\Big{(}\sum_{t=1}^{B}d_{0,\boldsymbol{Y}_{t}}\cdot\frac{\beta_{t}}{\mathcal{E}_{t}-\beta_{t}+1}\Big{)}\Big{)}.$

The proof follows from instantiating the values of
$d_{0,\boldsymbol{X}_{1}},d_{0,\boldsymbol{Y}_{1}},\dots,d_{0,\boldsymbol{Y}_{B}}$
according to the multidegree of $f_{0}$. ∎

###  A.2 Proof of Theorem 4.4

###### Proof of Theorem 4.4.

In this proof, we follow the same strategy as in the proof of Thm. 3.7. As we
did in Sec. 3.1, we can interpret the various multidegrees of $f_{0}$,
${\boldsymbol{d}_{0}}=(d_{0,{X}_{1}},\dots,d_{0,{X}_{A}},d_{0,{Y_{1}}},\dots,d_{0,{Y_{B}}})$,
that we want to prove that lead to determinantal formulas as solutions of the
following system of inequalities:

$\displaystyle\begin{cases}(\forall 1\leq i\leq A)\,&0\leq
d_{0,\boldsymbol{X}_{i}}\leq 1\\\ (\forall 1\leq j\leq B)\,&0\leq
d_{0,\boldsymbol{Y}_{j}}\leq 1\\\ &\sum_{i=1}^{A}d_{0,\boldsymbol{X}_{i}}\leq
1\\\ &\sum_{j=1}^{B}d_{0,\boldsymbol{Y}_{j}}\leq 1.\end{cases}$ (68)

Consider the set $\\{0,\dots,N\\}$ that corresponds to generic polynomials
$\boldsymbol{F}=(F_{0},\dots,F_{N})$ of multidegrees
${\boldsymbol{d}_{0}},\dots,{\boldsymbol{d}_{N}}$ (Def. 2.3), where
$(F_{1},\dots,F_{n})$ is a square bipartite bilinear system such that, for
each $i\in\\{1,\dots,A\\}$, $\sum_{j=1}^{B}\mathcal{E}_{i,j}\geq\alpha_{i}$
and for each $j\in\\{1,\dots,B\\}$,
$\sum_{i=1}^{A}\mathcal{E}_{i,j}\geq\beta_{j}$, and ${\boldsymbol{d}_{0}}$ is
the multidegree of $F_{0}$. As many of these polynomials have the same
support, similarly to (3.1), we can gather them to simplify the cohomologies
of (7). For that we introduce the following notation. For each tuple
$s_{0},s_{1,1},\dots,s_{A,B}\in\mathbb{N}$, let
$\mathcal{I}_{s_{0},s_{1,1},\dots,s_{A,B}}$ be the set of all the subsets of
$\\{0,\dots,N\\}$, such that

  * •

For $1\leq i\leq A$ and $1\leq j\leq B$, the index $s_{i,j}$ indicates that we
consider exactly $s_{i,j}$ polynomials from $(F_{1},\dots,F_{N})$ that belong
to
$\mathbb{Z}[\boldsymbol{u}][\boldsymbol{X}_{i},\boldsymbol{Y}_{j}]_{\boldsymbol{1}}$.

  * •

In addition, if $s_{0}=1$, then 0 belongs to all the sets in
$\mathcal{I}_{s_{0},s_{1,1},\dots,s_{A,B}}$

That is,

$\displaystyle\mathcal{I}_{s_{0},s_{1,1},\dots,s_{A,B}}:=\Big{\\{}I:$
$\displaystyle I\subset\\{0,\dots,n\\},\left(0\in
I\\!\Leftrightarrow\\!s_{0}=1\right)\text{ and }$ $\displaystyle(\forall 1\leq
i\leq A)(\forall 1\leq j\leq B)\;s_{i,j}=\\#\\{k\in
I:f_{k}\in\mathbb{K}[\boldsymbol{X}_{i},\boldsymbol{Y}_{j}]\\}\Big{\\}}.$ (69)

As in Lem. 3.5, we exploit the sets
$\mathcal{I}_{s_{0},s_{1,1},\dots,s_{A,B}}$ to rewrite the cohomologies
$K_{v}(\boldsymbol{m})=\bigoplus_{p=0}^{N+1}K_{v,p}\otimes\mathbb{Z}[\boldsymbol{u}]$
of (7) in the following way,

$\displaystyle K_{v,p}(\boldsymbol{m})=\bigoplus_{\begin{subarray}{c}0\leq
s_{0}\leq 1\\\ (\forall 1\leq i\leq A)(\forall 1\leq j\leq B)\;0\leq
s_{i,j}\leq\mathcal{E}_{i,j}\\\
s_{0}+\sum_{i=1}^{A}\sum_{j=1}^{B}s_{i,j}=p\end{subarray}}\Big{(}H^{p-v}_{\mathcal{P}}\big{(}\boldsymbol{m}-\big{(}\sum_{j=1}^{B}s_{1,j},\dots,\sum_{j=1}^{B}s_{A,j},\sum_{i=1}^{A}s_{i,1},\dots,\sum_{i=1}^{A}s_{i,B}\big{)}-s_{0}\,{\boldsymbol{d}_{0}}\big{)}$
$\displaystyle\otimes\bigoplus_{I\in\mathcal{I}_{s_{0},s_{1,1},\dots,s_{A,B}}}\bigwedge_{k\in
I}e_{k}\Big{)}.$ (70)

Hence, using the Künneth Formula (Prop. 2.7) with the degree vector
$\boldsymbol{m}$ defined in Thm. 4.4, we have the following isomorphisms of
cohomologies,

$H^{p-v}_{\mathcal{P}}\left(\boldsymbol{m}-\left(\sum_{j=1}^{B}s_{1,j},\dots,\sum_{j=1}^{B}s_{A,j},\sum_{i=1}^{A}s_{i,1},\dots,\sum_{i=1}^{A}s_{i,B}\right)-s_{0}\,{\boldsymbol{d}_{0}}\right)\cong\\\
\bigoplus_{r_{\boldsymbol{X}_{1}}+\dots+r_{\boldsymbol{X}_{A}}+r_{\boldsymbol{Y}_{1}}+\dots+r_{\boldsymbol{Y}_{B}}=p-v}\;\left(\displaystyle\begin{array}[]{l
c}\displaystyle\bigotimes_{i=1}^{A}H^{r_{\boldsymbol{X}_{i}}}_{\mathbb{P}^{\alpha_{i}}}\left(\sum_{j=1}^{B}(\mathcal{E}_{i,j}-s_{i,j})-\alpha_{i}+(1-s_{0})\,d_{0,X_{i}}\right)&\text{[Case
X]}\\\
\displaystyle\otimes\bigotimes_{j=1}^{B}H^{r_{\boldsymbol{Y}_{j}}}_{\mathbb{P}^{\beta_{j}}}\left(-1-\sum_{i=1}^{A}s_{i,j}-d_{0,Y_{j}}s_{0}\right)&\text{[Case
Y]}\end{array}\right)$ (71)

We will study the values for
$p,v,s_{0},s_{1,1},\dots,s_{A,B},r_{{\boldsymbol{X}_{1}}},\dots,r_{{\boldsymbol{X}_{A}}},r_{\boldsymbol{Y}_{1}},\dots,r_{\boldsymbol{Y}_{B}}$
such that $K_{v,p}(\boldsymbol{m})$ does not vanish. Clearly, if $0\leq
s_{0}\leq 1$ and $(\forall i\in\\{1,\dots,A\\})\,(\forall
j\in\\{1,\dots,B\\})\;0\leq s_{i,j}\leq\mathcal{E}_{i.j}$, then the module
$\bigoplus_{I\in\mathcal{I}_{s_{0},s_{1,1},\dots,s_{A,B}}}\bigwedge_{k\in
I}e_{k}$ is not zero. Hence, assuming $0\leq s_{0}\leq 1$ and $(\forall
i\in\\{1,\dots,A\\})\,(\forall j\in\\{1,\dots,B\\})\;0\leq
s_{i,j}\leq\mathcal{E}_{i.j}$ $(\forall i\in\\{1,\dots,B\\})\;0\leq
s_{i}\leq\mathcal{E}_{i}$, we study the vanishing of the modules in the right-
side part of (71). We will study the cohomologies independently. By Rem. 2.8,
the modules in the right hand side of (71) are not zero only when, for $1\leq
i\leq A$, $r_{\boldsymbol{X}_{i}}\in\\{0,\alpha_{i}\\}$ and, for $1\leq j\leq
B$, $r_{\boldsymbol{Y}_{j}}\in\\{0,\beta_{j}\\}$. At the end of the proof we
show that if (71) does not vanish then the following conditions hold,

$\displaystyle\begin{array}[]{| c | c | c |}\hline\cr\text{[Case X]}&\text{For }1\leq i\leq A&\begin{array}[]{c}r_{\boldsymbol{X}_{i}}=0\\\ \displaystyle\sum_{j=1}^{B}(\mathcal{E}_{i,j}-s_{i,j})-\alpha_{i}+(1-s_{0})\,d_{0,{\boldsymbol{X}_{i}}}\geq 0\end{array}\\\ \hline\cr\text{[Case Y]}&\text{For }1\leq j\leq B&\begin{array}[]{c}r_{\boldsymbol{Y}_{j}}=\beta_{j}\\\ \displaystyle\sum_{i=1}^{A}s_{i,j}+s_{0}\,d_{0,{\boldsymbol{Y}_{j}}}-\beta_{j}\geq 0\end{array}\\\ \hline\cr\end{array}$ (78)

Using (78), we study the possible values for $v$ such that
$K_{v,p}(\boldsymbol{m})$ does not vanish. From (A.2), it holds
$p=\sum_{i=1}^{A}\sum_{j=1}^{B}s_{i,j}+s_{0}$. By Prop. 2.7,
$p-v=\sum_{i=1}^{A}r_{\boldsymbol{X}_{i}}+\sum_{j=1}^{B}r_{{\boldsymbol{Y}_{j}}}$.
Hence, we deduce that, when $K_{v,p}(\boldsymbol{m})$ does not vanish, it
holds,

$v=\sum_{i=1}^{A}\sum_{j=1}^{B}s_{i,j}+s_{0}-\sum_{j=1}^{B}\beta_{j}=\sum_{j=1}^{B}\left(\sum_{i=1}^{A}s_{i,j}-\beta_{j}\right)+s_{0}.$

We bound the values for $v$ for which $K_{v,p}(\boldsymbol{m})$ does not
vanish.

  * •

First, we lower-bound $v$. Assume that the cohomologies involving
${\boldsymbol{Y}_{j}}$ are not zero. Hence, if we sum over
$j\in\\{1,\dots,B\\}$ the inequalities of [Case Y], we conclude that

$0\leq\sum_{j=1}^{B}(\sum_{i=1}^{A}s_{i,j}-\beta_{j})+s_{0}\,\sum_{j=1}^{B}d_{0,{\boldsymbol{Y}_{j}}}=v+s_{0}\,\left(\sum_{j=1}^{B}d_{0,{\boldsymbol{Y}_{j}}}-1\right).$

By definition, (68), $0\leq\sum_{j=1}^{B}d_{0,{\boldsymbol{Y}_{j}}}\leq 1$,
and $0\leq s_{0}\leq 1$, hence $0\leq v.$

  * •

Finally, we upper-bound $v$. Assume that the cohomologies involving
${\boldsymbol{X}_{j}}$ are not zero. Hence, if we sum over
$i\in\\{1,\dots,A\\}$ the inequalities of [Case X], we conclude that

$\displaystyle 0\leq$
$\displaystyle\sum_{i=1}^{A}\left(\sum_{j=1}^{B}(\mathcal{E}_{i,j}-s_{i,j})-\alpha_{i}+(1-s_{0})\,d_{0,{\boldsymbol{X}_{i}}}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{A}\sum_{j=1}^{B}\mathcal{E}_{i,j}-\sum_{i=1}^{A}\alpha_{i}-\sum_{i=1}^{A}\sum_{j=1}^{B}s_{i,j}+(1-s_{0})\,\left(\sum_{i=1}^{A}d_{0,{\boldsymbol{X}_{i}}}\right).$

Recall that
$N=\sum_{i=1}^{A}\sum_{j=1}^{B}\mathcal{E}_{i,j}=\sum_{i=1}^{A}\alpha_{i}+\sum_{i=j}^{B}\beta_{j}$
and $v=\sum_{i=1}^{A}\sum_{j=1}^{B}s_{i,j}+s_{0}-\sum_{i=j}^{B}\beta_{j}$.
Also, as $\boldsymbol{d}_{0}$ is a solution of (68), it holds
$0\leq\sum_{j=1}^{B}d_{0,{\boldsymbol{Y}_{j}}}\leq 1$, and $0\leq s_{0}\leq
1$. Hence

$v=\sum_{i=1}^{A}\sum_{j=1}^{B}s_{i,j}+s_{0}-\sum_{i=j}^{B}\beta_{j}\leq
s_{0}+(1-s_{0})\,\left(\sum_{i=1}^{A}d_{0,{\boldsymbol{X}_{i}}}\right)\leq 1.$

We conclude that the possible values for $v$, $p$,
$r_{\boldsymbol{X}_{1}},\dots,r_{\boldsymbol{X}_{A}}$,
$r_{\boldsymbol{Y}_{1}},\dots,r_{\boldsymbol{Y}_{B}}$ such that (71) is not
zero are $v\in\\{0,1\\}$, the possible values for
$r_{\boldsymbol{X}_{1}},\dots,r_{\boldsymbol{X}_{A}}$,
$r_{\boldsymbol{Y}_{1}},\dots,r_{\boldsymbol{Y}_{B}}$ are the ones in (78) and
$p=\sum_{j=1}^{B}\beta_{j}+v$. Hence, our Weyman complex looks like (9), where

$\delta_{1}(\boldsymbol{m}):K_{1,\sum_{j=1}^{B}\beta_{j}+1}(\boldsymbol{m})\to
K_{0,\sum_{j=1}^{B}\beta_{j}}(\boldsymbol{m})$

is a Koszul-type determinantal formula.

In what follows we prove each case in (78).

Case (X) We consider the modules that involve the variables in the block
${\boldsymbol{X}_{i}}$, for $1\leq i\leq A$. As $(\forall
j)\,s_{i,j}\leq\mathcal{E}_{i,j}$, $0\leq s_{0}\leq 1$ and $0\leq
d_{0,{\boldsymbol{X}_{i}}}\leq 1$, we have
$\sum_{j=1}^{B}(\mathcal{E}_{i,j}-s_{i,j})-\alpha_{i}+(1-s_{0})\,d_{0,{\boldsymbol{X}_{i}}}>-1-\alpha_{i}.$
Hence, by Rem. 2.9,

$\displaystyle\begin{gathered}H^{r_{\boldsymbol{X}_{i}}}_{\mathbb{P}^{\alpha_{i}}}(\sum_{j=1}^{B}(\mathcal{E}_{i,j}-s_{i,j})-\alpha_{i}+(1-s_{0})\,d_{0,{\boldsymbol{X}_{i}}})\neq
0\iff\\\ r_{\boldsymbol{X}_{i}}=0\quad\text{ and
}\quad\sum_{j=1}^{B}(\mathcal{E}_{i,j}-s_{i,j})-\alpha_{i}+(1-s_{0})\,d_{0,{\boldsymbol{X}_{i}}}\geq
0.\end{gathered}$

Case (Y) We consider the modules that involve the variables in the block
${\boldsymbol{Y}_{j}}$, for $1\leq j\leq B$. As $(\forall
j\in\\{1,\dots,B\\})\,s_{i,j}\geq 0$ and $s_{0},d_{0,{\boldsymbol{Y}_{j}}}\geq
0$, then $-1-\sum_{i=1}^{A}s_{i,j}-s_{0}\,d_{0,{\boldsymbol{Y}_{j}}}<0$, and
so by Rem. 2.9,

$\displaystyle\begin{gathered}H^{r_{\boldsymbol{Y}_{j}}}_{\mathbb{P}^{\beta_{j}}}(-1-\sum_{i=1}^{A}s_{i,j}-s_{0}\,d_{0,{\boldsymbol{Y}_{j}}})\neq
0\iff\\\ r_{\boldsymbol{Y}_{j}}=\beta_{j}\quad\text{ and
}\quad\sum_{i=1}^{A}s_{i,j}+s_{0}\,d_{0,{\boldsymbol{Y}_{j}}}-\beta_{j}\geq
0.\end{gathered}$

∎

###  A.3 Example of determinantal formula for bipartite bilinear system

Consider four blocks of variables such that $A=2$, $B=2$, $\alpha=(1,2)$,
$\beta=(1,2)$, and

$\left\\{\begin{array}[]{r l}X_{1}:=&\\{X_{1,0},X_{1,1}\\}\\\
X_{2}:=&\\{X_{2,0},X_{2,1},X_{2,2}\\}\\\ Y_{1}:=&\\{Y_{1,0},Y_{1,1}\\}\\\
Y_{2}:=&\\{Y_{2,0},Y_{2,1},Y_{2,2}\\}.\end{array}\right.$

Let $(f_{1},\dots,f_{6})$ be the square bipartite bilinear system represented
by the following graph:

${\boldsymbol{X}_{1}}$${\boldsymbol{X}_{2}}$${\boldsymbol{Y}_{1}}$${\boldsymbol{Y}_{2}}$$\mathcal{E}_{1,1}=1$$\mathcal{E}_{1,2}=2$$\mathcal{E}_{2,1}=1$$\mathcal{E}_{2,2}=2$

We introduce a polynomial
$f_{0}\in\mathbb{K}[\boldsymbol{X}_{1},\boldsymbol{Y}_{1}]_{\boldsymbol{1}}$
and consider the following overdetermined system $\boldsymbol{f}$ where,

$\displaystyle\boldsymbol{f}:=\left\\{\begin{array}[]{l
r}f_{0}:=&\left(a_{{1}}\,y_{1;{0}}+a_{{2}}\,y_{1;{1}}\right)x_{1;{0}}+\left(a_{{3}}\,y_{1;{0}}+a_{{4}}\,y_{1;{1}}\right)x_{1;{1}}\\\
f_{1}:=&\left(b_{{1}}\,y_{1;{0}}+b_{{2}}\,y_{1;{1}}\right)x_{1;{0}}+\left(b_{{3}}\,y_{1;{0}}+b_{{4}}\,y_{1;{1}}\right)x_{1;{1}}\\\
f_{2}:=&\left(c_{{1}}\,y_{1;{0}}+c_{{2}}\,y_{1;{1}}\right)x_{2;{0}}+\left(c_{{5}}\,y_{1;{0}}+c_{{6}}\,y_{1;{1}}\right)x_{2;{1}}+\left(c_{{3}}\,y_{1;{0}}+c_{{4}}\,y_{1;{1}}\right)x_{2;{2}}\\\
f_{3}:=&\left(d_{{1}}\,y_{2;{0}}+d_{{2}}\,y_{2;{2}}+d_{{3}}\,y_{2;{1}}\right)x_{1;{0}}+\left(d_{{4}}\,y_{2;{0}}+d_{{5}}\,y_{2;{2}}+d_{{6}}\,y_{2;{1}}\right)x_{1;{1}}\\\
f_{4}:=&\left(e_{{1}}\,y_{2;{0}}+e_{{2}}\,y_{2;{2}}+e_{{3}}\,y_{2;{1}}\right)x_{1;{0}}+\left(e_{{4}}\,y_{2;{0}}+e_{{5}}\,y_{2;{2}}+e_{{6}}\,y_{2;{1}}\right)x_{1;{1}}\\\
f_{5}:=&\left(g_{{1}}\,y_{2;{0}}+g_{{2}}\,y_{2;{2}}+g_{{3}}\,y_{2;{1}}\right)x_{2;{0}}+\left(g_{{7}}\,y_{2;{0}}+g_{{8}}\,y_{2;{2}}+g_{{9}}\,y_{2;{1}}\right)x_{2;{1}}\\\
&\hfill+\left(g_{{4}}\,y_{2;{0}}+g_{{5}}\,y_{2;{2}}+g_{{6}}\,y_{2;{1}}\right)x_{2;{2}}\\\
f_{6}:=&\left(h_{{1}}\,y_{2;{0}}+h_{{2}}\,y_{2;{2}}+h_{{3}}\,y_{2;{1}}\right)x_{2;{0}}+\left(h_{{7}}\,y_{2;{0}}+h_{{8}}\,y_{2;{2}}+h_{{9}}\,y_{2;{1}}\right)x_{2;{1}}\\\
&\hfill+\left(h_{{4}}\,y_{2;{0}}+h_{{5}}\,y_{2;{2}}+h_{{6}}\,y_{2;{1}}\right)x_{2;{2}}\end{array}\right.$
(88)

Following Thm. 4.4, we consider the degree vector
$\boldsymbol{m}=(3,1,-1,-1)$. The vector spaces of the Weyman complex
$K(\boldsymbol{m},\boldsymbol{f})$ looks like,

$\displaystyle K_{1}(\boldsymbol{m},\boldsymbol{f})=$
$\displaystyle\quad\,\,S_{\boldsymbol{X}_{1}}(0)\otimes
S_{\boldsymbol{X}_{2}}(0)\otimes S^{*}_{\boldsymbol{Y}_{1}}(0)\otimes
S^{*}_{\boldsymbol{Y}_{2}}(-1)\otimes\left\\{\begin{array}[]{l}(e_{0}\wedge
e_{3}\wedge e_{4}\wedge e_{5})\oplus(e_{0}\wedge e_{3}\wedge e_{4}\wedge
e_{6})\;\oplus\\\ (e_{2}\wedge e_{3}\wedge e_{4}\wedge
e_{5})\oplus(e_{2}\wedge e_{3}\wedge e_{4}\wedge e_{6})\end{array}\right\\}$
$\displaystyle\oplus S_{\boldsymbol{X}_{1}}(0)\otimes
S_{\boldsymbol{X}_{2}}(0)\otimes S^{*}_{\boldsymbol{Y}_{1}}(-1)\otimes
S^{*}_{\boldsymbol{Y}_{2}}(0)\otimes\left\\{\begin{array}[]{l}(e_{0}\wedge
e_{2}\wedge e_{3}\wedge e_{6})\oplus(e_{0}\wedge e_{2}\wedge e_{4}\wedge
e_{5})\;\oplus\\\ (e_{0}\wedge e_{2}\wedge e_{4}\wedge
e_{6})\oplus(e_{0}\wedge e_{2}\wedge e_{3}\wedge e_{4})\;\oplus\\\
(e_{2}\wedge e_{2}\wedge e_{3}\wedge e_{4})\oplus(e_{0}\wedge e_{2}\wedge
e_{3}\wedge e_{5})\end{array}\right\\}$ $\displaystyle
K_{0}(\boldsymbol{m},\boldsymbol{f})=$
$\displaystyle\quad\,\,S_{\boldsymbol{X}_{1}}(0)\otimes
S_{\boldsymbol{X}_{2}}(1)\otimes S^{*}_{\boldsymbol{Y}_{1}}(0)\otimes
S^{*}_{\boldsymbol{Y}_{2}}(0)\otimes\left\\{\begin{array}[]{l}(e_{0}\wedge
e_{3}\wedge e_{4})\oplus(e_{2}\wedge e_{3}\wedge e_{4})\end{array}\right\\}$
$\displaystyle\oplus S_{\boldsymbol{X}_{1}}(1)\otimes
S_{\boldsymbol{X}_{2}}(0)\otimes S^{*}_{\boldsymbol{Y}_{1}}(0)\otimes
S^{*}_{\boldsymbol{Y}_{2}}(0)\otimes\left\\{\begin{array}[]{l}(e_{0}\wedge
e_{3}\wedge e_{5})\oplus(e_{0}\wedge e_{3}\wedge e_{6})\;\oplus\\\
(e_{0}\wedge e_{4}\wedge e_{5})\oplus(e_{0}\wedge e_{4}\wedge
e_{6})\;\oplus\\\ (e_{1}\wedge e_{3}\wedge e_{5})\oplus(e_{1}\wedge
e_{3}\wedge e_{6})\;\oplus\\\ (e_{1}\wedge e_{4}\wedge
e_{5})\oplus(e_{1}\wedge e_{4}\wedge e_{6})\;\oplus\\\ (e_{2}\wedge
e_{3}\wedge e_{4})\end{array}\right\\}$

The Koszul determinantal matrix representing the map
$\delta_{1}(\boldsymbol{m},\boldsymbol{f})$ between the modules with respect
to a monomial basis is,

$\left[\begin{array}[]{cccccccccccccccccccccccc}&&&-b_{{1}}&-b_{{3}}&&&&&&&&&&a_{{1}}&a_{{3}}&&&&&&&&\\\
&&&-b_{{2}}&-b_{{4}}&&&&&&&&&&a_{{2}}&a_{{4}}&&&&&&&&\\\
&&&&&-b_{{1}}&-b_{{3}}&&&&&&&&&&a_{{1}}&a_{{3}}&&&&&&\\\
&&&&&-b_{{2}}&-b_{{4}}&&&&&&&&&&a_{{2}}&a_{{4}}&&&&&&\\\
&&&&&&&-b_{{1}}&-b_{{3}}&&&&&&&&&&a_{{1}}&a_{{3}}&&&&\\\
&&&&&&&-b_{{2}}&-b_{{4}}&&&&&&&&&&a_{{2}}&a_{{4}}&&&&\\\
&&&&&&&&&-b_{{1}}&-b_{{3}}&&&&&&&&&&a_{{1}}&a_{{3}}&&\\\
&&&&&&&&&-b_{{2}}&-b_{{4}}&&&&&&&&&&a_{{2}}&a_{{4}}&&\\\
-c_{{1}}&-c_{{5}}&-c_{{3}}&&&&&&&&&&&&&&&&&&&&a_{{1}}&a_{{3}}\\\
-c_{{2}}&-c_{{6}}&-c_{{4}}&&&&&&&&&&&&&&&&&&&&a_{{2}}&a_{{4}}\\\
-g_{{1}}&-g_{{7}}&-g_{{4}}&e_{{1}}&e_{{4}}&&&-d_{{1}}&-d_{{4}}&&&&&&&&&&&&&&&\\\
-g_{{3}}&-g_{{9}}&-g_{{6}}&e_{{3}}&e_{{6}}&&&-d_{{3}}&-d_{{6}}&&&&&&&&&&&&&&&\\\
-g_{{2}}&-g_{{8}}&-g_{{5}}&e_{{2}}&e_{{5}}&&&-d_{{2}}&-d_{{5}}&&&&&&&&&&&&&&&\\\
-h_{{1}}&-h_{{7}}&-h_{{4}}&&&e_{{1}}&e_{{4}}&&&-d_{{1}}&-d_{{4}}&&&&&&&&&&&&&\\\
-h_{{3}}&-h_{{9}}&-h_{{6}}&&&e_{{3}}&e_{{6}}&&&-d_{{3}}&-d_{{6}}&&&&&&&&&&&&&\\\
-h_{{2}}&-h_{{8}}&-h_{{5}}&&&e_{{2}}&e_{{5}}&&&-d_{{2}}&-d_{{5}}&&&&&&&&&&&&&\\\
&&&&&&&&&&&-c_{{1}}&-c_{{5}}&-c_{{3}}&&&&&&&&&b_{{1}}&b_{{3}}\\\
&&&&&&&&&&&-c_{{2}}&-c_{{6}}&-c_{{4}}&&&&&&&&&b_{{2}}&b_{{4}}\\\
&&&&&&&&&&&-g_{{1}}&-g_{{7}}&-g_{{4}}&e_{{1}}&e_{{4}}&&&-d_{{1}}&-d_{{4}}&&&&\\\
&&&&&&&&&&&-g_{{3}}&-g_{{9}}&-g_{{6}}&e_{{3}}&e_{{6}}&&&-d_{{3}}&-d_{{6}}&&&&\\\
&&&&&&&&&&&-g_{{2}}&-g_{{8}}&-g_{{5}}&e_{{2}}&e_{{5}}&&&-d_{{2}}&-d_{{5}}&&&&\\\
&&&&&&&&&&&-h_{{1}}&-h_{{7}}&-h_{{4}}&&&e_{{1}}&e_{{4}}&&&-d_{{1}}&-d_{{4}}&&\\\
&&&&&&&&&&&-h_{{3}}&-h_{{9}}&-h_{{6}}&&&e_{{3}}&e_{{6}}&&&-d_{{3}}&-d_{{6}}&&\\\
&&&&&&&&&&&-h_{{2}}&-h_{{8}}&-h_{{5}}&&&e_{{2}}&e_{{5}}&&&-d_{{2}}&-d_{{5}}&&\end{array}\right]$