# Complexity of computing matrix rank over integers

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?

-

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