Subject: Re: Null-space of an integer matrix
From: Dave Rusin <rusin@washington.math.niu.edu>
Date: 19 Jan 1995 17:27:35 GMT
Newsgroups: sci.math.research

In article <VLADIMIR.95Jan18160826@gemini.cs.cornell.edu>,
Vladimir Kotlyar <vladimir@CS.Cornell.EDU> wrote:
>
>Is there an algorithm for computing a basis for the null-space of an
>integer matrix, so that the basis has small (bounded) entries?

There are several ways to interpret your question. (Assuming, as I will,
that you meant for the basis vectors also to be integral.)

If you want to know what the method is to compute the null space with the goal
of minimizing the largest entry, I'd have to say 'I don't know'.
You could meld Gaussian elimination (as below) with the Euclidean
algorithm, as is done when classifying matrices over a PID (see e.g.
Jacobson's "Basic Algebra") but I've never tried to do it efficiently;
things that work theoretically are fine with me :-).

If you want to know if the entries can be made 'small', I'd say the
answer is 'not particularly'. Indeed, consider a diagonal matrix with  N  rows
containing relatively prime entries on the diagonal, all roughly equal to  K.
Adjoin a single column consisting of all  1's. Then the null-space is
one-dimensional, spanned by a vector the last entry of which is the
product of the diagonal entries, i.e. roughly  K^N. Is this 'small'?

If you want to know if there is any upper bound on the entries of the
null-space, I'd say 'sure'.  If you just modify Gaussian elimination so as not
to do division, you can keep track of how big the entries will grow. Let  M_0
be the greatest magnitude of any entry in the matrix at the beginning. After
n steps you can arrange the matrix to have a diagonal nxn matrix in the
top left with zeros under it. If the greatest magnitude of the entries
at this stage is  M_n, then at worst you must multiply rows by
a number this big and then add in another such, so when you consider
the entries you have left you see  M_(n+1) <= M_n^2 + M_n < 2M_n^2.
By induction this shows  M_n <= 2^(s-1) M_0^s where  s=2^n. Once you
end up with the linearly independent rows diagonalized, you can write down
a null space pretty easily -- although as the previous example shows,
the entries may be as big as the product of all the diagonal entries.
Thus you can write down _an_ upper bound for the null space entries:
(2M_0)^(N.2^N). I have no doubt someone will chime in with a significant
reduction of the exponent  N.2^N, but at least this does give you _a_
bound.

Finally, let me add that you need to decide whether you're interested
in null-spaces or annihilators; that will affect your answer.
Let me clarify: As in the previous paragraph, you can write a sequence
of integral vectors with the property that any rational (or real or...)
vector in the null space is a rational (real...) linear combination of
these. That even applies to integral vectors in the null space. If you
want to find a collection of integral vectors with the property that
any integral vector in the null space is an _integral_ linear combination
of the ones in the first set, then you are asking a question about
free modules over the integers. This is more subtle than the linear
algebra; for example, you run into the question of whether a submodule
of a free module is itself free (true for integers, not true for other rings).
The method outlined in the previous paragraph gives a null-space basis of
the following form: if the gcd if the diagonal entries is  D, then a
typical basis vector has most of the initial entries zero except for
one, which is a divisor of  D; all the final entries (those not corresponding
to the diagonalized rows) are multiples of  D. Clearly not all integral
vectors in the null-space need to be an _integral_ linear combination
of such vectors.

dave
==============================================================================

Date: Fri, 20 Jan 95 09:57:09 CST
From: [Permission pending]
To: rusin
Subject: Re: Null-space of an integer matrix

Dave,

I read with interest your recent news article with the above title (article
758 in sci.math.research). I am just a "news voyeur" in that I read the
articles, but never post any. I don't even know how to go about posting.
However, I think I have something worthwhile to add to your discussion of
finding "small" solutions to homogeneous systems of linear equations.

The idea is this. Suppose

a_{11}X_1+    +a_{1n}X_n=0
....

a_{m1}X_1+    +a_{mn}X_n=0

is a system with a_{ij} integral and |a_{ij}|\le A for all i and j. Suppose
that m<n (so there is a non-trivial integral solution). Then there should be
a "small" solution, where "small" is , of course, relative to A. This idea
was first used by A. Thue early this century, and later formalized by C. L.
Siegel. The following is called "Siegel's Lemma":

Lemma. With the notation and hypotheses above, there is a non-trivial integral
solution x=(x_1,...,x_n) to the above system that satisfies

|x_i|<1+(nA)^{m/(n-m)}.

For an excellent discussion of this, see W. Schmidt's "Diophantine
approximations and Diophantine equations" Lecture Notes in Mathematics #1467.
This is on the first page, I believe. The exponent on A above is best-possible.
(I was there when he gave these lectures. It was an exercise then. He gives
 a proof I believe in the published notes.) Suffice it to say that this is a
very interesting subject, to me at least. However, I have never looked into
an "algorithmic" approach. Perhaps there are those out there who know of
algorithms for classical geometry of numbers problems.

Yours,

[sig deleted -- djr]

==============================================================================

Date: Fri, 20 Jan 95 11:07:09 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Null-space of an integer matrix

Thanks for your information; this is new to me, and I'll have to look it up.

This is a very sharp bound for the size of the vector. I would be surprised
if there is an algorithm to compute a vector this small. Also lacking is
a description of the size of the rest of the null-space, although there
ought to be some way of adjoining another equation which would force the
solution set to drop to a subset of the original nullspace which excludes
the basis vector already obtained. I'm not sure that adding the equation that
forces these other null vectors to be perpendicular to the first (for example)
is anywhere close to the optimal situation.

[deletia] 

dave

PS -- If I don't see a post from you, I'll come back asking if it's OK for
me to post what you sent me. With attribution of course.

==============================================================================

Date: Fri, 20 Jan 95 11:56:43 CST
From: [Permission pending]
To: rusin
Subject: Re: Null-space of an integer matrix

Thanks for your reply. A much more precise result can be obtained if one is
more precise about the "size" of the matrix you start with. Suppose M is an
m by n matrix with rank m <n of rational entries. Compute the Grassmann (note
spelling!) coordinates of the rowspace, and rescale so that this vector (in
Q^(n\choose m) has relatively prime integral coordinates. The norm of this
vector (usual L2 norm) is the "height" of the rowspace. By dusty old facts
from linear algebra, this is also the "height" of the nullspace. Geometry of
numbers guarantees the existance of a basis {x_1, ... ,x_{n-m}} of the
nullspace where
1. each x_i has relatively prime integral coordinates
2. the product of the norms of the x_is is bounded above by a constant
(involving volumes of balls, etc..) multiple of the height of M (the height of
the nullspace as above).

One can even have the x_is form a basis of the lattice of integral points in
the nullspace (though with a bigger constant in 2 above). Further, one can
use any "norm" on the x_is you like, though of course this would change the
constant in 2 again. These constants are easily given in the case I describe
above, and also in other cases of interest, e.g. , using the maximum norm for
the vectors x_i. Check out any reasonable book on geometry of numbers and look
up Minkowski's second convex-bodies theorem for the straight poop.

Since these constants are explicitly given, and there are only finitely many
integral points in a given ball about the origin, I'm sure one could actually
find these vectors in a deterministic way. 

Yours, 
[Permission pending]
==============================================================================

From: mosh@ramanujan.cs.albany.edu (Mohsin-Ahmed)
Newsgroups: sci.math.research
Subject: Re: Null-space of an integer matrix
Date: 23 Jan 1995 01:17:33 GMT

Vladimir Kotlyar (vladimir@CS.Cornell.EDU) writes:

: Is there an algorithm for computing a basis for the null-space of an
: integer matrix, so that the basis has small (bounded) entries?

: Thanks

: Vladimir Kotlyar

Look at:

  Adkins, W.A. and Weintraub, S.H.:
  Algebra, an Approach via Module Theory,
  Springer, NY, 1992
  Chp 5, "Matrices over PID."

--
- Mohsin.

==============================================================================

From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.research
Subject: Re: Null-space of an integer matrix
Date: 26 Jan 1995 19:56:44 GMT

The original query concerned bounds on the entries in basis vectors
for the nullspace of an integer matrix. Subsequent posts showed that
there are a few different ways to analyze this. My colleague Jeff Thunder
(jthunder@math.niu.edu) sent me a good statement of what's possible.
With his permission I am quoting some of his email to me on the subject.
dave
[begin quoted material]

... I think I have something worthwhile to add to your discussion of
finding "small" solutions to homogeneous systems of linear equations.

The idea is this. Suppose

a_{11}X_1+...+a_{1n}X_n=0
...
a_{m1}X_1+...+a_{mn}X_n=0

is a system with a_{ij} integral and |a_{ij}|\le A for all i and j. Suppose
that m<n (so there is a non-trivial integral solution). Then there should be
a "small" solution, where "small" is , of course, relative to A. This idea
was first used by A. Thue early this century, and later formalized by C. L.
Siegel. The following is called "Siegel's Lemma":

Lemma. With the notation and hypotheses above, there is a non-trivial integral
solution x=(x_1,...,x_n) to the above system that satisfies

|x_i|<1+(nA)^{m/(n-m)}.

For an excellent discussion of this, see W. Schmidt's "Diophantine
approximations and Diophantine equations" Lecture Notes in Mathematics #1467.
This is on the first page, I believe. The exponent on A above is best-possible.

[I asked about the possibility of finding the entire null-space,
and the feasibility of a deterministic solution, to which he replied...]

... A much more precise result can be obtained if one is
more precise about the "size" of the matrix you start with. Suppose M is an
m by n matrix with rank m <n of rational entries. Compute the Grassmann (note
spelling!) coordinates of the rowspace, and rescale so that this vector (in
Q^(n\choose m)) has relatively prime integral coordinates. The norm of this
vector (usual L2 norm) is the "height" of the rowspace. By dusty old facts
from linear algebra, this is also the "height" of the nullspace. Geometry of
numbers guarantees the existence of a basis {x_1, ... ,x_{n-m}} of the
nullspace where
1. each x_i has relatively prime integral coordinates
2. the product of the norms of the x_is is bounded above by a constant
(involving volumes of balls, etc..) multiple of the height of M (the height of
the nullspace as above).

One can even have the x_is form a basis of the lattice of integral points in
the nullspace (though with a bigger constant in 2 above). Further, one can
use any "norm" on the x_is you like, though of course this would change the
constant in 2 again. These constants are easily given in the case I describe
above, and also in other cases of interest, e.g. , using the maximum norm for
the vectors x_i. Check out any reasonable book on geometry of numbers and look
up Minkowski's second convex-bodies theorem for the straight poop.

Since these constants are explicitly given, and there are only finitely many
integral points in a given ball about the origin, I'm sure one could actually
find these vectors in a deterministic way. 

[end of quoted material]