Ivanyos, Gábor ;
Karpinski, Marek ;
Qiao, Youming ;
Santha, Miklos
Generalized Wong sequences and their applications to Edmonds' problems
Abstract
We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace B of the nxn matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) is the problem to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) is the question to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems are asking to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one.
Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices, but the triangularization is not given explicitly. Both algorithms work over finite fields of size at least n+1 and over the rational numbers, and the first algorithm actually solves (the nonconstructive) SMR independent of the field size. Our main tool to obtain these results is to generalize Wong sequences, a classical method to deal with pairs of matrices, to the case of pairs of matrix spaces.
BibTeX  Entry
@InProceedings{ivanyos_et_al:LIPIcs:2014:4474,
author = {G{\'a}bor Ivanyos and Marek Karpinski and Youming Qiao and Miklos Santha},
title = {{Generalized Wong sequences and their applications to Edmonds' problems}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {397408},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4474},
URN = {urn:nbn:de:0030drops44741},
doi = {10.4230/LIPIcs.STACS.2014.397},
annote = {Keywords: symbolic determinantal identity testing, Edmonds' problem, maximum rank matrix completion, derandomization, Wong sequences}
}
05.03.2014
Keywords: 

symbolic determinantal identity testing, Edmonds' problem, maximum rank matrix completion, derandomization, Wong sequences 
Seminar: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Issue date: 

2014 
Date of publication: 

05.03.2014 