Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Integer matrix rank
Posted:
Oct 20, 1999 5:05 AM


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
In article <s8x904zn11i.fsf@gold.cics.shef.ac.uk>, john green <ap1jjg@gold.cics.shef.ac.uk> writes: > 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



