Time: Monday, 19 March 2001, 14.15 - 15.00
Place: N030

The presentation will be held in Danish.

Abstract:

Adapted from Journal of Computer and Systems Sciences, vol. 58, 1999.

We consider the computational complexity of some problems dealing with matrix rank. Let $E$, $S$ be subsets of some commutative ring. Let $x_1, x_2, \ldots, x_t$ be variables. Given a matrix $M = M(x_1, x_2, \ldots, x_t)$ with entries chosen from $E \cup \{x_1, x_2, \ldots, x_t\}$, we want to determine $$\mbox{maxrank}_{S}(M) = \max_{(a_1, a_2, \ldots, a_t) \in S^{t}} \mbox{ rank } M(a_1, a_2, \ldots, a_t)$$ and $$\mbox{minrank}_S(M) = min_{(a_1, a_2, \ldots, a_t) \in S^{t}} \mbox{ rank } M(a_1, a_2, \ldots, 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, the complexity of these problems can range from polynomial-time solvable to random polynomial-time solvable to NP-complete to PSPACE-solvable to unsolvable. An approximation version of the minrank problem is shown to be MAXSNP-hard.