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!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.