10
$\begingroup$

Does computing the rank of an integer matrix have complexity polynomial in the size of the input?

The Gaussian elimination algorithm is polynomial in the number of elementary operations (addition and multiplication), but the intermediate size of of the matrix entries may go up exponentially. Are there other algorithms with better complexity? Can anyone give a reference?

$\endgroup$
10
$\begingroup$

Gaussian elimination is a polynomial-time algorithm. While it may not be obvious on the first sight, it can be implemented so that the intermediate entries have only polynomial size (bit length), because they happen to be equal to determinants of certain submatrices of the original matrix (or ratios thereof, depending on the version). See e.g. Edmonds and Bareiss.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Right, using Bareiss' algorithm space needed is at most 0.5 n lg n + O(n) due to a theorem of Hadamard. This means that each operation takes time $O(n(\log n)^{2+\varepsilon})$ giving overall time complexity $O(n^4(\log n)^{2+\varepsilon}).$ $\endgroup$ – Charles Apr 28 '11 at 15:36
6
$\begingroup$

The answer to your question is yes. Note that you can bound determinant(in fact you need to bound the size of lattice spanned by rows of the matrix) of the matrix with integer of size polynomial in the length input. Let $p$ be a prime with is large than this bound then the rank of the integer matrix will be equal to the rank of the matrix mod $p$.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

I asked more-or-less the same question 12 years ago on sci.math.num-analysis, but for the case when the integer entries are small. Thom Mulders replied describing this wonderful modular method.

Edit: the link above seems to be dead, so I include the reply verbatim here

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.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.