Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-009 | 12th March 1997 00:00

The Computational Complexity of Some Problems of Linear Algebra


Authors: Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit
Publication: 24th March 1997 14:29
Downloads: 1177


We consider the computational complexity of some problems
dealing with matrix rank. Let E,S be subsets of a
commutative ring R. Let x_1, x_2, ..., x_t be variables.
Given a matrix M = M(x_1, x_2, ..., x_t) with entries
chosen from E union {x_1, x_2, ..., x_t}, we want
to determine maxrank_S (M), i.e. the maximum possible rank
M(a_1, a_2, ..., a_t) can attain when (a_1, a_2, ..., a_t)
are chosen from S^t, and similarly, we want to determine
minrank_S (M), i.e. the minimum possible rank
M(a_1, a_2, ..., a_t) can attain when (a_1, a_2, ..., a_t)
are chosen from S^t. There are also variants of these
problems that specify more about the structure of M,
or instead of asking for the minimum or maximum rank,
ask if there is some substitution of the variables that
makes the matrix invertible or noninvertible.

Depending on E,S, and on which variant is studied,
the complexity of these problems can range from
polynomial-time solvable to random polynomial-time solvable
to NP-complete to PSPACE-solvable to unsolvable.

ISSN 1433-8092 | Imprint