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.