Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
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}).$ –  Charles Apr 28 '11 at 15:36

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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