Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-009 | 12th March 1997 00:00

The Computational Complexity of Some Problems of Linear Algebra

RSS-Feed




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


Abstract:

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