Under the auspices of the Computational Complexity Foundation (CCF)
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
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.