Determinant: Combinatorics, Algorithms, and Complexity

Mahajan, Meena ; V, Vinay (1997) Determinant: Combinatorics, Algorithms, and Complexity Chicago Journal of Theoretical Computer Science, 1997 (5).

[img] PDF


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.

Item Type:Article
Source:Copyright of this article belongs to AI2.
ID Code:127977
Deposited On:14 Oct 2022 11:32
Last Modified:14 Oct 2022 11:32

Repository Staff Only: item control page