Determinant: Combinatorics, Algorithms, and Complexity

Abstract

<F4.793e+05> We prove a new combinatorial characterization of the<F3.928e+05> determi-<F2.522e+05> Abstract-1<F3.928e+05><F4.793e+05> nant. 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 e#cient parallel implementations. It has been known for some time now that the complexity class<F2.522e+05> Abstract-2<F4.793e+05> GapL characterizes the complexity of computing the determinant of matrices over the integers. We present a direct proof of this characterization. <F7.59e+05> 1 Introduction<F6.349e+05> The determinant has been a subject of study for over 200 years. Its history<F2.522e+05> 1-1<F6.349e+05> can be traced back to Leibnitz, Cramer, Vandermode, Binet, Cauchy, Jacobi, Gauss, and others. Given its importance in linear algebra i...