Bareiss algorithm (source code)

= Bareiss algorithm
{c}

The <Bareiss algorithm> is fraction-free <Gaussian elimination> for exact <determinants>. For an integer <matrix>, put $A^{(0)}=A$ and $p_0=1$. At step $k$, choose a nonzero <pivot element> $p_k=a_{kk}^{(k-1)}$ and update the trailing entries by
$$
a_{ij}^{(k)}=\frac{p_k a_{ij}^{(k-1)}-a_{ik}^{(k-1)}a_{kj}^{(k-1)}}{p_{k-1}},\qquad i,j>k.
$$
Set the eliminated entries below the pivot to zero. The determinant identities behind the method make division by $p_{k-1}$ exact, so intermediate entries remain integers. Without row exchanges, the last pivot $a_{nn}^{(n-1)}$ is $\det A$; row exchanges change its sign in the usual way. A zero pivot needs an exchange before continuing.

For $A=\left(\begin{smallmatrix}2&1&0\\1&2&1\\0&1&2\end{smallmatrix}\right)$, the first trailing block becomes $\left(\begin{smallmatrix}3&2\\2&4\end{smallmatrix}\right)$. The last update is $(3\cdot4-2\cdot2)/2=4$, giving the <determinant> without rational intermediate entries. Exact division is different from having no division at all.<Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination by Erwin H. Bareiss>[Section I, pp. 565–567, equations (3), (6) and (8): bordered minors and exact-divisibility recurrence]{ref}