TR97-009 Authors: Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

Publication: 24th March 1997 14:29

Downloads: 1867

Keywords:

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.