CJTCS Volume 1997 Article 5

Determinant: Combinatorics, Algorithms, and Complexity

Meena Mahajan (Institute of Mathematical Sciences, Chennai India) V. Vinay (Indian Institute of Science, Bangalore India) 31 December 1997

Abstract

We prove a new combinatorial characterization of the determinant . The characterization yields a simple combinatorial algorithm for computing the determinant. Hitherto, all (known) algorithms for the determinant have been based on linear algebra. Our combinatorial algorithm requires no division, and works over arbitrary commutative rings. It also lends itself to efficient parallel implementations.

It has been known for some time now that the complexity class GapL characterizes the complexity of computing the determinant of matrices over the integers. We present a direct proof of this characterization.

• Preformatted versions of the article
  • DVI (110,100 bytes)
  • PostScript (499,531 bytes)
  • PDF (392,063 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj97-05.tex , 89,677 bytes)
  • BIBTeX ( cj97-05.bib , 9,317 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 164 bytes)
  • Self citation in BIBTeX (345 bytes)
• Online discussion
• Instructions for Readers

---

Article 4 Volume 1998, Article 1
Volume 1997 Published articles

Last modified: Tue Mar 10 20:37:33 CST