1
$\begingroup$

My question is related to my previous question How to prove existence of solutions to the system of Diophantine linear equations. In particular, to the theorem which I've used to prove some subset of my general problem. Theorem [2] (page 51):

Let $\mathbf{A} \in \mathbb{Z}^{m,n}$ be a rational matrix of full row rank, $rank(\mathbf{A}) = m$, with $m$ rows, and let $\mathbf{b}$ be a rational column $m$-vector. Then $\mathbf{Ax} = \mathbf{b}$ has an integral solution $\mathbf{x}$, if and only if each $m \times m$ minor of the matrix $[\mathbf{Ab}]$ is an integral multiple of the greatest common divisor of the $m \times m$ minors of the matrix $\mathbf{A}$.

Well, I've been thinking about this theorem, I came up with a conclusion that I really do not understand what kind of information $m\times m$ minors of the matrix $\mathbf{A}$ carry on.

@WillSawin wrote [3]

$\mathbf{A}$ gives a map from $\mathbb{Z}^n$ to $\mathbb{Z}^m$. To check existence of a solution, you first want to know the cokernel of this map. You can compute the size of this cokernel by taking the greatest common divisor of the $m\times m$ minors.

So, I guess there is something to do with number theory, but this relation is not obvious to me. I do not see a relation between minors and cokernel - which in short should give me information about constraints of a problem.

Could somebody give me some overview, or/and maybe recommend something to read?

References

[2] Theory of linear and integer programming, Alexander Schrijver, 1998

[3] https://mathoverflow.net/questions/101536/is-there-a-solution-to-system-of-linear-diophantine-equations

$\endgroup$
2
$\begingroup$

To understand the role of the minors, start with the (simple) case of a square matrix, i.e. $m=n$. Then, the above theorem reduces to:

There is an integral solution iff each minor of $[\mathbf{A \; b}]$ is a multiple of the (unique) minor of $\mathbf{A}$, namely $\det \mathbf{A}$.

Indeed, since $\mathbf{A}$ has full rank, it is invertible and the solutions (integral or not) are given by the Cramer formulae: $x_i = m_i/\det \mathbf{A}$, where $m_i$ is the minor of $[\mathbf{A \; b}]$ obtained by removing the $i$-th column. The proof is direct.

When $n>m$, the statement is less obvious, because the solution to the linear system is not unique among the reals, therefore, the problem is now finding an integral solution among the infinitely many real solutions. However, suppose that you have spotted some $m \times m$ nonzero minor in $\mathbf{A}$ (say columns $1$ through $m$ for the sake of simplicity); then setting $x_{m+1} = \cdots = x_n = 0$ brings you back to the previous (Cramer) case and to the condition of divisibility. If that divisibility condition does not hold with this particular minor, you will need to try another minor, or even a minor obtained after applying elementary (unimodular) column operations. Since you want to divide by the smallest possible minor (to increase the chances of getting an integer) you end up dividing by the gcd.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.