
> 
> *Condition* : Given a $4 \times 5$ matrix, where each element is denoted by $p/q$, we have $|p|<10$ and $1\leq |q|<10$.
> 
> 
> 


Example: $A$ given by



```
-9/7 -5/8 -1 4/5 4
-1 9/7 -6/5 -7 2/9
-1/3 -2 5/7 -2/9 -7
3 0 -5/3 8/9 -2/5

```

I have found that when I calculate the row reduced echelon form (RREF) of a $4\times 5$ matrix satisfying the condition above, it produces larger numbers than I expected.


For example, the RREF of $A$ is



```
1 0 0 0 -13325864657/7239264390 
0 1 0 0 10141123216/3619632195 
0 0 1 0 -3549396949/1447852878 
0 0 0 1 562768523/482617626 

```

How long is the maximum length of numerator/denominator?


It looks like $a\_{1,5}$ has longest length and it's under $10^{10}$, but I can't prove it.



Maximum length of numerator/denominator in calculating RREF
Surprisingly the question hasn't been closed yet, so I'm posting the solution, as promised. As I said, bringing the matrix to the row echelon form is equivalent to the left multiplication by the inverse to the $4\times 4$ sub-matrix (if the rank is full) or smaller size sub-matrix if the rank is smaller than $4$. I'll consider the full rank case only. Let's look at the first entry of $A^{-1}x$. By Cramer's rule, it is just the ratio of the determinants of matrices with the same three columns (from where it is obvious that the longest possible numerator is the same as the longest possible denominator).


Now let $C\_1,C\_2,C\_3$ be those common columns. In each column we can write each entry as a fraction with the denominator from $1$ to $9$. We will not care if the fraction is reducible or not. Now for each of these columns we will compute two quantities: the least common multiple of the denominators $D\_j$ and the square root $M\_j$ of the sum of squares of the entries. Then all $3\times 3$ minors have the common denominator $D=D\_1D\_2D\_3$ and so each of the two full determinants is just an integer divided by $2520D\_1D\_2D\_3$ ($2520$ is the least common multiple of the numbers from $1$ to $9$). This integer can become the numerator/denominator of the result if no further cancellations take place. By the Hadamard inequality (the volume of a parallelepiped does not exceed the product of its sides), that integer is at most $9\times 2\times 2520\times M\_1M\_2M\_3D\_1D\_2D\_3$.


Now let us look at the product $M\_1D\_1$, say. Notice that there are $4$ primes up to $9$: $2,3,5,7$. Having the same prime in two different denominators in $C\_1$ is not optimal because we can leave only the highest power and increase $M\_1$ without changing $D\_1$, so each prime occurs in at most one denominator in the (formal) worst case scenario. If $2$ and $3$ occur together (the denominator $6$), then there is a denominator-free entry and we can increase $6$ to $8$ and put $9$ on that entry, increasing $D\_1$ $12$ times and decreasing $M\_1$ at most $9$ times. Finally, if we can increase the power of some prime $p$ in the denominator by $1$, we'd better do it because $M\_1$ will decrease at most $p$ times but $D\_1$ will increase $p$ times. Thus, the largest product $M\_1D\_1$ is achieved (formally) at the column $(9/5,9/7,9/8,9/9)$, which gives $M\_1D\_1\le Q=9\times\sqrt{5^{-2}+7^{-2}+8^{-2}+9^{-2}}\times 2520$.


The final estimate for the numerator/denominator is then
$9\times 2520\times 2\times Q^3\le 1.4\times 10^{16}$, so the number of digits cannot be greater than $17$.


Plugging {8/9,9/5,9/8,9/7}\*inverse({{9,9,9,9},{9/5,-9/8,-9/7,8/9},{-9/8,-9/7,8/9,9/5},{-9/7,8/9,-9/5,9/8}}) into Wolfram Alpha (or any other computational tool), we see that 17 digits are attainable (the matrix has the same sign pattern as the Hadamard $4\times 4$ matrix of $\pm 1$'s, so our estimate is not too crude and the denominator $12,887,816,516,918,280$ is actually rather close to our upper bound).


