Division-Free Algorithms for Determinants and Pfaffians

an $n\times n$ matrix is Gaussian elimination and needs
$O(n^3)$ additions, subtractions, multiplications, and divisions.
On the other hand, the explicit definition of the determinant
as the sum of $n!$ products shows that the determinant can be
computed \emph{without} divisions.
Avoiding divisions seems attractive when
working over a commutative ring which is not a field, for example
when the entries are integers, polynomials, or rationals
or even more complicated expressions.

The best algorithms take $O(n^4)$ steps. We will look at these
algorithms from a combinatorial and an algebraic viewpoint.

We will also consider the \emph{Pfaffian} of a skew-symmetric matrix,
a quantity that is defined via matchings in graphs
and closely related to the determinant. The results are in many ways
analogous to those for the determinant, but the algebraic aspect
of the algorithms is not explored yet.