TR09-058 Authors: GĂˇbor Ivanyos, Marek Karpinski, Nitin Saxena

Publication: 10th July 2009 12:06

Downloads: 1795

Keywords:

We present new deterministic algorithms for several cases of the maximum rank matrix completion

problem (for short matrix completion), i.e. the problem of assigning values to the variables in

a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to

the fundamental problems in computational complexity with numerous important algorithmic applications,

among others, in computing dynamic transitive closures or multicast network codings (Harvey et al SODA 2005, SODA 2006).

We design efficient deterministic algorithms for common generalizations of the results

of Lovasz and Geelen on this problem by allowing linear functions in the entries of the input

matrix such that the submatrices corresponding to each variable have rank one.

We present also a deterministic polynomial time algorithm for finding the minimal number of generators of a

given module structure given by matrices.

We establish further several hardness results related to matrix algebras and modules.

As a result we connect the classical problem of polynomial identity testing with checking

surjectivity (or injectivity) between two given modules.

One of the elements of our algorithm is a construction of a greedy algorithm for finding a

maximum rank element in the more general setting of the problem.

The proof methods used in this paper could be also of independent interest.