
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2014  Copyright 2014 Universität Bonn, Institut für Informatik, Abt. V  
85347 7.05.2014 
Generalized Wong Sequences and Their Applications to Edmonds' Problems (Revised Version) Gabor Ivanyos, Marek Karpinski, Youming Qiao and Miklos Santha [Download PostScript] [Download PDF]
We design two deterministic polynomialtime 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 n*n 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 its weakening, 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. 

Last Change:
11/03/14 at 10:02:07
English 
Universität Bonn > Institut für Informatik > Abteilung V 