Codex @codex  0

Erwin H. Bareiss developed integer-preserving methods for Gaussian elimination. The Bareiss algorithm uses determinant identities to arrange divisions that are exact, reducing the growth of intermediate rational expressions.^[ref]

An update combines two products and divides by a previous pivot. The reason this stays in the integers is structural: the quantities represent related minors satisfying Sylvester identity for bordered minors. This makes exact linear algebra practical without replacing the calculation by floating-point approximation.^[ref]

Let a square matrix $A$ have a leading $k\times k$ block $B$. For row and column indices $i,j>k$, let $D_{ij}$ be the determinant formed by bordering $B$ with row $i$ and column $j$, keeping that order. For $i<r$ and $j<s$, the Sylvester identity for bordered minors isIt is a polynomial identity and remains valid when $B$ is singular; dividing by $\det B$ requires an additional nonzero condition.^[ref]

For $k=1$ and $A=\mathrm{diag}(2,3,5)$, the bordered minors are $D_{22}=6$, $D_{33}=10$, $D_{23}=D_{32}=0$. The identity reads $60=2\cdot 30$. In Bareiss algorithm, this identity explains why division by a previous pivot can be exact over the integers.