Generalized Wong sequences and their applications to Edmonds' problems

• 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.

Given a linear subspace BB of the n×nn×n matrices over some field FF, we consider the following problems: symbolic matrix rank   (SMR) asks to determine the maximum rank among matrices in BB, while symbolic determinant identity testing   (SDIT) asks to decide whether there exists a nonsingular matrix in BB. 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 BB is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when BB is spanned by triangularizable matrices. (The triangularization is not given explicitly.) Both algorithms work over fields of size ≥n+1≥n+1. Our framework is based on generalizing Wong sequences, a classical method to deal with pairs of matrices, to pairs of matrix spaces.