ECCC-Report TR02-016https://eccc.weizmann.ac.il/report/2002/016Comments and Revisions published for TR02-016en-usWed, 27 Feb 2002 17:43:48 +0200
Paper TR02-016
| On the Enumerability of the Determinant and the Rank |
Alina Beygelzimer,
Mitsunori Ogihara
https://eccc.weizmann.ac.il/report/2002/016We 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.
Wed, 27 Feb 2002 17:43:48 +0200https://eccc.weizmann.ac.il/report/2002/016