The Computational Complexity of Some Problems of Linear Algebra

  • Jonathan F. Buss
  • Gudmund Skovbjerg Frandsen
  • Jeffery O. Shallit


We consider the computational complexity of some problems dealing with matrix rank.
Let E, S be subsets of a commutative ring R.
Let x1, x2, ..., xt be variables. Given a matrix M = M(x1, x2, ..., xt)
with entries chosen from E union {x1, x2, ..., xt}, we want to determine
maxrankS(M) = max rank M(a1, a2, ... , at)
minrankS(M) = min rank M(a1, a2, ..., at).
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
How to Cite
Buss, J., Frandsen, G., & Shallit, J. (1996). The Computational Complexity of Some Problems of Linear Algebra. BRICS Report Series, 3(33).