Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: Integer matrix rank
Replies: 4   Last Post: Oct 22, 1999 7:18 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Thom Mulders

Posts: 8
Registered: 12/8/04
Re: Integer matrix rank
Posted: Oct 20, 1999 5:05 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.