Generalized Wong sequences and their applications to Edmonds' problems
作者：
Highlights：
• Deterministic efficient algorithms for two special cases of Edmonds' problem are exhibited.
• A classical tool in matrix analysis called the Wong sequences is generalized.
• As a first result, an algorithm to compute the maximum rank in a rank-1 spanned matrix space is exhibited.
• The first result settles an open problem by Gurvits [18].
• As a second result, an algorithm to compute the maximum rank in a triangularizable matrix space is exhibited.
摘要
•Deterministic efficient algorithms for two special cases of Edmonds' problem are exhibited.•A classical tool in matrix analysis called the Wong sequences is generalized.•As a first result, an algorithm to compute the maximum rank in a rank-1 spanned matrix space is exhibited.•The first result settles an open problem by Gurvits [18].•As a second result, an algorithm to compute the maximum rank in a triangularizable matrix space is exhibited.
论文关键词：Symbolic determinantal identity testing,Edmonds' problem,Maximum rank matrix completion,Derandomization,Wong sequences
论文评审过程：Received 26 June 2014, Revised 13 February 2015, Accepted 24 April 2015, Available online 5 May 2015, Version of Record 10 June 2015.
论文官网地址：https://doi.org/10.1016/j.jcss.2015.04.006
