Q:

What is the actual time complexity of Gaussian elimination?

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?

A:

I think the answer is $\widetilde O(n^3 \log( \|A\| + \|b\|))$, where
we omit the (poly)logarithmic factors.  The bound is presented in
"W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann,
G. Villard. Solving sparse integer linear systems. Proc. ISSAC'06,
Genova, Italy, ACM Press, 63-70, July 2006", but it is based on a
paper by Dixon: "Exact solution of linear equations using P-adic
expansions, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Number 1,
137-141".

A:

I think the answer to your first question is also $\widetilde O(n^3 \log( \|A\| + \|b\|))$ due to the following arguments: Edmonds' paper does not describe a variant of Gaussian elimination but it proves that any number computed in a step of the algorithm is a determinant of some submatrix of A. By Schrijver's book on Theory of Linear and Integer Programming we know that if A's encoding needs b bits (b should be in $\widetilde O(\log( \|A\|)$) then any of its subdeterminants needs at most 2b bits (Theorem 3.2). In order to make Gaussian elimination a polynomial time algorithm we have to care about the computed quotients: We have to cancel out common factors from every fraction we compute in any intermediate step and then all numbers have encoding length linear in the encoding length of A.

