ECCC-Report TR09-058https://eccc.weizmann.ac.il/report/2009/058Comments and Revisions published for TR09-058en-usFri, 10 Jul 2009 12:06:17 +0300
Paper TR09-058
| Deterministic Polynomial Time Algorithms for Matrix Completion Problems |
GĂˇbor Ivanyos,
Marek Karpinski,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2009/058We 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.
Fri, 10 Jul 2009 12:06:17 +0300https://eccc.weizmann.ac.il/report/2009/058