The Computational Complexity of Some Problems of Linear Algebra

✍ Scribed by Jonathan F Buss; Gudmund S Frandsen; Jeffrey O Shallit

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 330 KB
• Volume: 58
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1608

✦ Synopsis

We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x 1 , x 2 , ..., x t be variables. Given a matrix M=M(x 1 , x 2 , ..., x t ) with entries chosen from E _ [x 1 , x 2 , ..., x t ], we want to determine maxrank S (M)=max (a 1 , a 2 , ..., a t ) # S t rank M(a 1 , a 2 , ..., a t ) and minrank S (M) = min (a 1 , a 2 , ..., a t ) # S t rank M(a 1 , a 2 , ..., a t ). 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, they ask if there is some substitution of the variables that makes the matrix invertible or noninvertible. Depending on E, S, and which variant is studied,