ON SYSTEMS OF LINEAR DIOPHANTINE EQUATIONS


EXAMPLE. Solve the system of diophantine equations Ax = b, where

Solution. Consider a sequence of elementary transformations of rows and columns of A. It is
well known that they can be achieved by multiplying A by unimodular matrices. Let us represent the
transformation of rows by 2×2 matrices Li’s and the ones of columns by 3×3 matrices Rj ’s, where
the lower indices reflect the order of multiplications. We consider the following transformations
(matrices):

Let L = L4 and R = R1R2R3R5R6. Then

and .

Solving Dy = c, and taking x = Ry, we get

and the problem is solved.

Another application is concerned with a special instance of the following fundamental question
in number theory. Let denote the ring of polynomials in t variables with integral
coefficients, and let . It is clear that if the equation F(x) = 0 has an integer
solution, then for any integer n ≥ 1, the congruence F(x) ≡ 0 (mod n) has a solution. The
converse, in general, is false, even for the case of one variable. A simple counterexample is provided
by F(x) = (2x+1)(3x+1). To show that (2x+1)(3x+1) ≡ 0 (mod n) has a solution, write n in
the form n = 2a3bm, where gcd(m, 2) = gcd(m, 3) = 1, and a and b are nonnegative integers. Then
use the Chinese Remainder Theorem. For more on the relation between congruences and equations
see, e.g., [2]. Nevertheless the following is valid.

PROPOSITION 3. Let , and b ∈ Zn. Then the system of linear equations Ax = b
has an integer solution if and only if the corresponding system of congruences Ax ≡ b (mod n)
has a solution for every positive integer n.

Proof. Obviously, the first statement implies the second. Suppose the system of congruences
has a solution for every positive integer n. Let L,R,D, y and c be as in Proposition 2, and let N ∈ Z
be such that the transition from Ax = b to Dy = c uses integers with absolute values smaller than
N. Then for every n ≥ N, Ax ≡ b (mod n) Dy ≡ c (mod n) (mod n),
i = 1, . . . , s. The latter system of congruences is solvable in particular when n is a multiple of ds.
Since di | ds for every i, 1≤  i ≤ s, this implies , hence di | ci for all i = 1, . . . , s.
Therefore Dy = c has an integer solution, and so does Ax = b.

The following statement allows one easily to compute the index of a subgroup of the additive
group Zn, when the index is finite.

PROPOSITION 4. Let f : ZnZn be a Z–linear map and be its matrix with
respect to some choice of bases. Suppose A has rank n. Then the index of f(Zn) in Zn is equal to
| detA |.

Proof. By Theorem 1 we can find two unimodular matrices L and R such that LAR = D =
. Since A is of rank n, all . Therefore the abelian group
, and the order of Zn/f(Zn) is. Since L and R are
unimodular, | detD | = | detA |.

EXAMPLE. Let f : Z2Z2 be defined by f((x, y)) = (28x + 38y, 12x + 16y). Choosing both
bases to be the standard basis of Z2, we get . Therefore the index [Z2 : f(Z2)] is
equal to | detA | = 8. The Smith normal form of A is , hence .

Our next application is related to Proposition 4. It deals with some basic notions of the
geometric number theory. Let R denote the field of real numbers, and be a
linearly independent set of vectors in Rn. The additive subgroup L =< S > of Rn generated by S
is called the lattice generated by S. A fundamental domain T = T(S) of the lattice L is defined
as

The volume v(T) of T is defined in the usual way, as the square root of the absolute value of the
determinant of an m×m matrix whose i–th row is the coordinate vector of in the standard basis.
Though T itself depends on a particular set of generators of L, the volume of T does not!

PROPOSITION 5. Let and be two sets of linearly independent
vectors which generate the same lattice L. Then m = t and v(T(S)) = v(T(U)).

Proof. We leave it to the reader. In case of difficulties, look through [13, pp. 30-33 and
pp.168-169].

If one considers A with entries from a field, then by elementary operations of rows and columns,
A can be brought to a diagonal form. It is a trivial exercise to check that an elementary row (column)
operation preserves the dimensions of both row and column spaces of A. Therefore matrices LAR
and A have equal dimensions of their row spaces and equal dimensions of their column spaces. Since
the dimensions of row space and column space for a diagonal matrix are equal, we have a proof of
the following fundamental result.

PROPOSITION 6. The dimension of row space of a matrix with entries from a field is equal to
the dimension of its column space.

Acknowledgements. References [3], [11], and remarks concerning the algorithmic aspects of finding the Smith
normal form of an integer matrix were kindly suggested to the author by an anonymous referee. I am also very grateful to
Gary Ebert, Todd Powers, Andrew Woldar, the editor and referees, whose numerous comments substantially improved the
original version of this paper.