  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 ${\bf F}$ for
$\alpha=1,2,\ldots,\mu$ and $\beta = 1,2,\ldots,\nu$. The maximum vanishing
subspace problem (MVSP) is to maximize $\sum_{\alpha} \dim X_{\alpha} +
\sum_{\beta} \dim Y_{\beta}$ over vector subspaces $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$ such that each $A_{\alpha \beta}$
vanishes on $X_{\alpha} \times Y_{\beta}$ when $A_{\alpha \beta}$ is viewed as
a bilinear form ${\bf F}^{m_{\alpha}} \times {\bf F}^{n_{\beta}} \to {\bf 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 ${\bf 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.
