A combinatorial algorithm for the determinant
Meena Mahajan, Vishwa Vinay · 1997
We show the first efficient combinatorial algorithm for the computation of the determinant. Hitherto, all (known) algorithms for determinant have been based on linear algebra. In contrast, our algorithm and its proof of correctness are totally combinatorial in nature. The algorithm requires no division and works on arbitrary commutative rings. It also lends itself to efficient sequential and parallel implementations. 1 Introduction The Determinant has been the subject of study for over 200 years. Its history can be traced back to Leibnitz, Crammer, Vandermode, Binet, Cauchy, Jacobi, Gauss and others. Given its importance in linear algebra in particular and in geometry in general, it is not surprising that a galaxy of great mathematicians investigated the determinant from varied viewpoints. The algorithmic history of the determinant is as old as the mathematical concept itself. After all, the determinant was invented to solve systems of linear equations. Much of the initial effort was...