The Computational Complexity of Some Problems of Linear Algebra

Forfattere

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

DOI:

https://doi.org/10.7146/brics.v3i33.20013

Resumé

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.

Downloads

Publiceret

1996-06-03

Citation/Eksport

Buss, J. F., Frandsen, G. S., & Shallit, J. O. (1996). The Computational Complexity of Some Problems of Linear Algebra. BRICS Report Series, 3(33). https://doi.org/10.7146/brics.v3i33.20013

Nummer

Nr. 33 (1996): RS-33 The Computational Complexity of Some Problems of Linear Algebra

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).