Open AccessThe Computational Complexity of Some Problems of Linear Algebra
Author(s) -
Jonathan F. Buss,
Gudmund Skovbjerg Frandsen,
J. Shallit
Publication year - 1996
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v3i33.20013
Subject(s) - mathematics , invertible matrix , rank (graph theory) , combinatorics , commutative property , matrix (chemical analysis) , computational complexity theory , polynomial , discrete mathematics , algorithm , pure mathematics , chemistry , chromatography , mathematical analysis
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) and 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 unsolvable.