Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-024 | 21st March 1996 00:00

The complexity of matrix rank and feasible systems of linear equations


Authors: Eric Allender, Robert Beals, Mitsunori Ogihara
Publication: 22nd March 1996 14:19
Downloads: 2047


We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, (as well as other problems), are complete under
logspace reductions.

As an important part of presenting this classification, we show
that the ``exact counting logspace hierarchy'' collapses to near the
bottom level. (We review the definition of this hierarchy below.)
We further show that this class is closed under NC^1-reducibility,
and that it consists of exactly those languages that have
logspace uniform span programs (introduced by Karchmer and Wigderson)
over the rationals.

In addition, we contrast the complexity of these problems with the
complexity of determining if a system of linear equations has an
integer solution.

ISSN 1433-8092 | Imprint