# The Computational Complexity of Some Problems of Linear Algebra

### Abstract

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.

Published

1996-06-03

How to Cite

*BRICS Report Series*,

*3*(33). https://doi.org/10.7146/brics.v3i33.20013

Section

Articles

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.