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.

  • $\begingroup$ 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))$. $\endgroup$ – clemens Nov 8 '17 at 9:26
  • $\begingroup$ Does this note of Lovász help? (Taken from here.) $\endgroup$ – Yuval Filmus Dec 16 '19 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.