Generalized Wong sequences and their applications to Edmonds' problems

Ivanyos, G; Karpinski, M; Qiao, Y; Santha, M

Generalized Wong sequences and their applications to Edmonds' problems

Ivanyos, G Karpinski, M Qiao, Y

Santha, M

Permalink

Publication Type:: Journal Article
Citation:: Journal of Computer and System Sciences, 2015, 81 (7), pp. 1373 - 1386
Issue Date:: 2015-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (274.43 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ivanyos, G	en_US
dc.contributor.author	Karpinski, M	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.contributor.author	Santha, M	en_US
dc.date.issued	2015-01-01	en_US
dc.identifier.citation	Journal of Computer and System Sciences, 2015, 81 (7), pp. 1373 - 1386	en_US
dc.identifier.issn	0022-0000	en_US
dc.identifier.uri	http://hdl.handle.net/10453/130879
dc.description.abstract	© 2015 Elsevier Inc. Given a linear subspace B of the n×n matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) asks to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) asks to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems ask 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. (The triangularization is not given explicitly.) Both algorithms work over fields of size ≥n+1. Our framework is based on generalizing Wong sequences, a classical method to deal with pairs of matrices, to pairs of matrix spaces.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DE150100720
dc.relation.ispartof	Journal of Computer and System Sciences	en_US
dc.relation.isbasedon	10.1016/j.jcss.2015.04.006	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Generalized Wong sequences and their applications to Edmonds' problems	en_US
dc.type	Journal Article
utslib.citation.volume	7	en_US
utslib.citation.volume	81	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	0806 Information Systems	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.issue	7	en_US
pubs.publication-status	Published	en_US
pubs.volume	81	en_US

Abstract:

© 2015 Elsevier Inc. Given a linear subspace B of the n×n matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) asks to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) asks to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems ask 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. (The triangularization is not given explicitly.) Both algorithms work over fields of size ≥n+1. Our framework is based on generalizing Wong sequences, a classical method to deal with pairs of matrices, to pairs of matrix spaces.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/130879