Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix

In this paper, we address the following algebraic generalization of the bipartite stable set problem. We are given a block-structured matrix (partitioned matrix) $A=(A_{\alpha \beta })$, where $A_{\alpha \beta }$ is an $m_{\alpha }$ by $n_{\beta }$ matrix over field $\mathbf{F}$ for $\alpha =1,2,\dots ,\mu$ and $\beta =1,2,\dots ,\nu$. The maximum vanishing subspace problem (MVSP) is to maximize $\sum_{\alpha} \dim X_{\alpha} + \sum_{\beta} \dim Y_{\beta}$overvectorsubspaces$X_{\alpha} \subseteq {\bf F}^{m_{\alpha}}$for$\alpha=1,2,\ldots,\mu$and$Y_{\beta} \subseteq {\bf F}^{n_{\beta}}$for$\beta = 1,2,\ldots,\nu$suchthateach$A_{\alpha \beta}$vanisheson$X_{\alpha} \times Y_{\beta}$when$A_{\alpha \beta}$ is viewed as a bilinear form ${\mathbf{F}}^{m_{\alpha }}\times {\mathbf{F}}^{n_{\beta }}\to \mathbf{F}$. This problem arises from a study of a canonical block-triangular form of $A$ by Ito, Iwata, and Murota~(1994), and is closely related to the noncommutative rank of a matrix with indeterminates. We prove that a weighted version (WMVP) of MVSP can be solved in psuedo polynomial time, provided arithmetic operations on $\mathbf{F}$ can be done in constant time. Our proof is a novel combination of submodular optimization on modular lattice and convex optimization on CAT(0)-space. We present implications of this result on block-triangularization of partitioned matrix.