Bareiss algorithm

Remarks

Clause 1 is proved by induction on $k$ with Sylvester's determinant identity, which expresses a bordered minor of the reduced matrix as a ratio of minors of $A$. For $k = 1$ it is the direct check $a^{(1)}_{ij} = a_{11} a_{ij} - a_{i1} a_{1j} = \det \begin{pmatrix} a_{11} & a_{1j} \\ a_{i1} & a_{ij} \end{pmatrix}$. Example: for $A = \begin{pmatrix} 2 & 3 & 1 \\ 4 & 1 & 5 \\ 6 & 2 & 3 \end{pmatrix}$ over $\Z$, step $1$ gives $a^{(1)}_{22} = -10$, $a^{(1)}_{23} = 6$, $a^{(1)}_{32} = -14$, $a^{(1)}_{33} = 0$, and step $2$ gives $a^{(2)}_{33} = \big((-10) \cdot 0 - 6 \cdot (-14)\big)/2 = 42 = \det A$. Over $\Z$, clause 1 and Hadamard's inequality bound the size of every intermediate entry. So the bit length of the numbers grows only polynomially, unlike naive fraction-free elimination, where it can double at each step. If a pivot is zero, rows can be exchanged as in Gaussian elimination, which changes the sign of the determinant. The algorithm uses $O(n^3)$ operations in $R$.

Going deeper

For a student

It is fraction-free Gaussian elimination: the work is the same order as ordinary elimination, but all intermediate values are minors of the input matrix. It is a standard method in computer algebra for determinants, ranks and exact solutions of linear systems over $\Z$ or over polynomial rings. The final pivot is the determinant, and the earlier pivots are the leading principal minors.