# Matrix determinant computation

Input : An matrix $A$, whose entries are from $\mathbb{Z}$ (set of integers)

Output: det A (determinant of matrix A)

Question : Suppose we are solving this problem over $\mathbb{Q}$ using gaussian elimination, what could be the size of numerators and denominators of the intermediate results?

Gaussian elimination: By doing row elementary operations we will getting upper triangular matrix $U$, so $A = P_1\times P_2 \times P_2 ..P_k U$, where each $P_i$ is a permuatation matrix.

Please note that there efficient methods for the computation of determinant like modular determinant computation etc, but I want to compute with the method described above.

• I have no proof, but if you are doing simple Gaussian elimination. You could run into exponential growth. If you're using an adapted elimination method similar to Kannan-Bachem's algorithm for Euclidean Rings, you should get coefficients in $O(\textrm{det}(A))$. – clemens Nov 8 '17 at 9:26
• Does this note of Lovász help? (Taken from here.) – Yuval Filmus Dec 16 '19 at 12:00