Welcome to MathOverflow

Question

4

2

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?

flag	asked Apr 28 2011 at 10:01 XX 253●5

Emil Jeřábek · Accepted Answer · 2011-04-28 13:14:14Z UTC

7

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.

edited Apr 28 2011 at 13:14

answered Apr 28 2011 at 11:13

Emil Jeřábek
10.6k●1●24●41

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 2011 at 15:36

J.J. Green · Answer 2 · 2011-04-28 14:55:27Z UTC

3

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.

answered Apr 28 2011 at 14:55

J.J. Green
686●5●9

Klim Efremenko · Answer 3 · 2011-04-28 11:03:17Z UTC

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

Complexity of computing matrix rank over integers

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.