If a matrix $A$ consists of rational elements, and we have access to only row operations of the form
- Row addition/subtraction from row $i$ to row $j$
- Row exchanging row $i$ with row $j$
What is the time complexity of reducing the matrix to a triangular form.
If we write the matrix as a set of fractions of the form $a_{i,j}=u_{i,j}/v_{i,j}$ where $u,v$ are integers. Then we could factor out all the denominators to be left with a matrix $A'$ of integers such that
$$A=\frac{1}{c}A'$$
where
$$c=\left(\prod_{i,j}v_{i,j}\right)$$
and each element is multiplied by $c$, i.e. $a_{i,j}'=a_{i,j}c$.
We could then perform integer Gaussian elimination which in itself can be performed in polynomial time.
However, $c$ is exponential in the size of the matrix. Is there any algorithm that exists which can perform Gaussian elimination of this form in polynomial time?
