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). I also know that Gaussian elimination can be made to work in polynomial time and that several other methods are possible (as discussed here). 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!
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Bini and Pan's book Polynomial and Matrix Computations may be one place to look and cite. link.springer.com/book/10.1007%2F978-1-4612-0265-3 $\endgroup$– Chandra ChekuriOct 9, 2020 at 1:55
-
1$\begingroup$ Another book that may be relevant is Shoup's book: A Computational Introduction to Number Theory and Algebra. shoup.net/ntb $\endgroup$– Chandra ChekuriOct 9, 2020 at 14:33
Add a comment
|