In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic operations, careless implementation can create numbers with exponentially many bits. As a simple example, suppose we want to diagonalize the following matrix:
$$\begin{bmatrix} 2 & 0 & 0 & \cdots & 0 \\ 1 & 2 & 0 & \cdots & 0 \\ 1 & 1 & 2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \cdots & 2 \\ \end{bmatrix}$$
If we use a version of the elimination algorithm without division, which only adds integer multiples of one row to another, and we always pivot on a diagonal entry of the matrix, the output matrix has the vector $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$ along the diagonal.
But what is the actual time complexity of Gaussian elimination? Most combinatorial optimization authors seem to be happy with “strongly polynomial”, but I'm curious what the polynomial actually is.
A 1967 paper of Jack Edmonds describes a version of Gaussian elimination (“possibly due to Gauss”) that runs in strongly polynomial time. Edmonds' key insight is that every entry in every intermediate matrix is the determinant of a minor of the original input matrix. For an $n\times n$ matrix with $m$-bit integer entries, Edmonds proves that his algorithm requires integers with at most $O(n(m+\log n))$ bits. Under the “reasonable” assumption that $m=O(\log n)$, Edmonds' algorithm runs in $O(n^5)$ time if we use textbook integer arithmetic, or in $\tilde{O}(n^4)$ time if we use FFT-based multiplication, on a standard integer RAM, which can perform $O(\log n)$-bit arithmetic in constant time. (Edmonds didn't do this time analysis; he only claimed that his algorithm is “good”.)
Is this still the best analysis known? Is there a standard reference that gives a better explicit time bound, or at least a better bound on the required precision?
More generally: What is the running time (on the integer RAM) of the fastest algorithm known for solving arbitrary systems of linear equations?