The Computational Complexity of Some Problems of Linear Algebra

Jonathan F. Buss
Gudmund Skovbjerg Frandsen
Jeffrey Outlaw Shallit

September 1996

Abstract:

We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let tex2html_wrap_inline29 be variables. Given a matrix tex2html_wrap_inline31 with entries chosen from tex2html_wrap_inline33 , we want to determine

displaymath35

and

displaymath37

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.

Available as PostScript, PDF.

 

Last modified: 2003-06-08 by webmaster.