Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-016 | 30th January 2002 00:00

On the Enumerability of the Determinant and the Rank


Authors: Alina Beygelzimer, Mitsunori Ogihara
Publication: 27th February 2002 17:43
Downloads: 1194


We investigate the complexity of enumerative approximation of
two elementary problems in linear algebra, computing the rank
and the determinant of a matrix. In particular, we show that
if there exists an enumerator that, given a matrix, outputs a
list of constantly many numbers, one of which is guaranteed to
be the rank of the matrix, then it can be determined in $\AC^0$
(with oracle access to the enumerator) which of these numbers
is the rank. Thus, for example, if the enumerator is an FL
function, then the problem of computing the rank is in FL.
The result holds for matrices over any commutative ring whose
size grows at most polynomially with the size of the matrix.
The existence of such an enumerator also implies a slightly
stronger collapse of the exact counting logspace hierarchy.

For the determinant function DET we establish the following
two results:

1. If DET is poly-enumerable in logspace, then DET is in FL.

2. For any prime $p$, if DET modulo $p$ is $(p-1)$-enumerable in
Mod_pL, then DET modulo $p$ is in FL.

ISSN 1433-8092 | Imprint