Integer matrix rank

john green

unread,

Oct 19, 1999, 3:00:00 AM10/19/99

to

Hello all.

I was wondering if anyone knew of a method
specific to the problem of finding the rank
of a large dense matrix with (small) integer
entries.

Thanks.

Jim Green
--
J.J.Green, Dept. Applied Math. University of Sheffield, UK
http://www.arbs.demon.co.uk

Peter Spellucci

unread,

Oct 19, 1999, 3:00:00 AM10/19/99

to

In article <s8x904z...@gold.cics.shef.ac.uk>,

snip
I think there is no other way to do it (roundoff free, of course)
than by "division-free" gaussian elimination.
this is the ordinary LR-decomposition with complete pivoting , each step followed
by a row scaling, i.e. avoiding division by the pivot .
this should be faster than using rational arithmetic for ordinary gaussian
elimination. Since arbitrary precision integer arithmetic is not too costly,
this may work also for larger matrices. however, if "large" really means large,
then even this might lead to considerable effort (and memory requirements).
Systems like Mathematica and Maple have this operation built in, but I never
tried the limitations with respect to dimensions on my computer.
good luck
peter

Thom Mulders

unread,

Oct 20, 1999, 3:00:00 AM10/20/99

to

Dear Jim,

You can use a modular method. When A is your matrix, compute for N different
primes p the rank of (A modulo p). When the product of the primes you use
is sufficiently big, then the rank will be equal to the maximum of the ranks
you have computed.
To be specific. Let A be an n by m matrix (n<=m) and ||A|| a bound on the
entries in A. When r is the rank of A there is an r by r submatrix B of A
with det(B)<>0. When the product Q of the primes exceeds det(B), there must
be at least one prime p such that the rank of (B modulo p) is r and thus the
rank of (A modulo p) is r. Using Hadamard's bound we have
det(B) <= r^{r/2}||A||^r <= n^{n/2}||A||^n,
so you need at most n((log n)/2 + log ||A||) different primes.
Since the complexity of computing the rank of (A modulo p) is O(mn^2) (assuming
the prime is not too big, e.g. fits into a machine word), the complexity of
this algorithm is (up to some log factors) O(mn^3). This is better than the
complexity (O(mn^4)) of the fraction free algorithm proposed before.

You can also use a probabilistic version of the above. Take a set S of at least
2n((log n)/2 + log ||A||) different primes and compute the rank of (A modulo p)
for different random primes from S. For such a random prime, the probability
that the rank of (A modulo p) is the rank of A is at least 1/2. When you find
that the rank does not increase for N choices of p, then the probability
that you have found the right rank is at least 1-(1/2)^N. Taking N=20, the
probability of failure is less than one in a million. Increasing the set S
improves the probability of success.

I hope this helps.

Regards,

Thom Mulders

Thom Mulders
Institute of Scientific Computing
ETH Zurich

john green

unread,

Oct 21, 1999, 3:00:00 AM10/21/99

to

mul...@zuseinf.ethz.ch (Thom Mulders) writes:
> You can use a modular method. When A is your matrix, compute for...
[algorithm snipped]

This is sweet, very sweet. Would anyone have a reference
for this sort of technique? (an email to Thom bounced).

Cheers

Jim

Thom Mulders

unread,

Oct 22, 1999, 3:00:00 AM10/22/99

to

Hi Jim,

My email address is

mul...@inf.ethz.ch

What I described is a very common technique in computer algebra. In computer
algebra one computes exact and symbolically. Therefore expressions get often
very big and computing with them very slow. To avoid this, modular techniques
can be used. You can find some examples of this in books on computer algebra,
e.g.:

- Geddes, Czapor, Labahn: Algorithms for computer algebra, Kluwer, 1992
- Davenport, Siret, Tournier: Computer algebra, systems and algorithms
for algebraic computation, Academic Press, 1993
- von zur Gathen, Gerhard: Modern computer algebra, Cambridge, 1999

Regards,

Thom Mulders

Thom Mulders
Institute of Scientific Computing
ETH Zurich

mul...@inf.ethz.ch