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?



Complexity of computing matrix rank over integers
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](http://www.ams.org/mathscinet-getitem?mr=229540) and [Bareiss](http://www.jstor.org/stable/2004533).


