文章基本信息

标题：Generalized Wong sequences and their applications to Edmonds' problems
本地全文：下载
作者：G{\'a}bor Ivanyos ; Marek Karpinski ; Youming Qiao 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：397-408
DOI：10.4230/LIPIcs.STACS.2014.397
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 non-constructive) 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.
关键词：symbolic determinantal identity testing; Edmonds' problem; maximum rank matrix completion; derandomization; Wong sequences