ECCC-Report TR13-103https://eccc.weizmann.ac.il/report/2013/103Comments and Revisions published for TR13-103en-usWed, 24 Jul 2013 17:06:03 +0300
Paper TR13-103
| Generalized Wong sequences and their applications to Edmonds' problems |
GĂˇbor Ivanyos,
Marek Karpinski,
Youming Qiao,
Miklos Santha
https://eccc.weizmann.ac.il/report/2013/103We 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 $\mathcal{B}$ of the $n \times n$ matrices over some field $\mathbb{F}$, we consider the following problems: $\textit{symbolic matrix rank}$ (SMR) is the problem to determine the maximum rank among matrices in $\mathcal{B}$, while $\textit{symbolic determinant identity testing}$ (SDIT) is the question to decide whether there exists a nonsingular matrix in $\mathcal{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 $\mathcal{B}$ is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when $\mathcal{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 independently from 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. Wed, 24 Jul 2013 17:06:03 +0300https://eccc.weizmann.ac.il/report/2013/103