<p>In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as long as the algorithm is polynomial with respect to dimensions of the matrix and lengths of representations of the entries (I know that obtaining the best possible bounds is an active research area, as described <a href="https://cstheory.stackexchange.com/questions/5750/what-is-the-fastest-algorithm-to-compute-rank-of-a-rectangular-matrix">here</a>). I also know that Gaussian elimination can be made to work in polynomial time and that several other methods are possible (as discussed <a href="https://mathoverflow.net/questions/63278/complexity-of-computing-matrix-rank-over-integers/63298">here</a>). However, I'm not particularly concerned about which particular method is used, just that there exists a polynomial algorithm. I suppose what I'm ultimately looking for is a reference to a standard textbook or a classical paper, but as a person coming from a different field (mathematics), I'm not sure which source to cite. Any help would be very much appreciated!</p>

CC BY-SA 4.0
2020-10-09T01:55:09.703Z
Bini and Pan's book Polynomial and Matrix Computations may be one place to look and cite. https://link.springer.com/book/10.1007%2F978-1-4612-0265-3
Chandra Chekuri
CC BY-SA 4.0
2020-10-09T14:33:39.487Z
Another book that may be relevant is Shoup's book: A Computational Introduction to Number Theory and Algebra. https://shoup.net/ntb/
Chandra Chekuri
<cc.complexity-theory><reference-request><linear-algebra><matrices>
Reference for computing the rank of a matrix in polynomial time
Jakub Konieczny
# Reference for computing the rank of a matrix in polynomial time

(Asked by: username_0 on 2020-10-07)

In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as long as the algorithm is polynomial with respect to dimensions of the matrix and lengths of representations of the entries (I know that obtaining the best possible bounds is an active research area, as described [here](https://cstheory.stackexchange.com/questions/5750/what-is-the-fastest-algorithm-to-compute-rank-of-a-rectangular-matrix)). I also know that Gaussian elimination can be made to work in polynomial time and that several other methods are possible (as discussed [here](https://mathoverflow.net/questions/63278/complexity-of-computing-matrix-rank-over-integers/63298)). However, I'm not particularly concerned about which particular method is used, just that there exists a polynomial algorithm. I suppose what I'm ultimately looking for is a reference to a standard textbook or a classical paper, but as a person coming from a different field (mathematics), I'm not sure which source to cite. Any help would be very much appreciated!

**Tags:** cc.complexity-theory, reference-request, linear-algebra, matrices
> **Comments:**
> **username_1**: Bini and Pan's book Polynomial and Matrix Computations may be one place to look and cite. https://link.springer.com/book/10.1007%2F978-1-4612-0265-3  
> **username_1**: Another book that may be relevant is Shoup's book: A Computational Introduction to Number Theory and Algebra. https://shoup.net/ntb/  

---

## 0 answers

