Optimization, Complexity and Invariant Theory

In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an $n \times n$ matrix $M_1x_1 + \dotsb + M_mx_m$ whose entries are homogeneous linear polynomials in commuting variables $x_1, x_2, \dotsc, x_m$ with integer coefficients.

We consider the non-commutative version of Edmonds’s problem over an arbitrary field. The “non-commutative” rank can be interpreted as the rank of the linear matrix $M_1x_1+ \dotsb +M_mx_m$ in the free skew field generated by the non-commuting variables $x_1, \dotsc, x_m$. This non-commutative rank is an upper bound for the rank of $M_1x_1+ \dotsb +M_mx_m$ in the commuting variables $x_1, \dotsc, x_m$.

We present a deterministic polynomial time algorithm which, given a collection $M_1, \dotsc, M_m$ of $n$ by $n$ matrices over the field $F$, computes the non-commutative rank $r$, and outputs $d$ by $d$ matrices $T_1,\dotsc, T_m$ such that the $nd$ by $nd$ block matrix $M_1 \otimes T_1+ \dotsb + M_m \otimes T_m$ has rank $rd$.

When $r < n$ we also compute $n$ by $n$ invertible matrices $L$ and $R$ such that for some integer $\ell$ the upper right $r- \ell$ by $\ell$ block of $LM_jR$ is zero for all $j = 1, \dotsc, m$ providing evidence to the fact that all these matrices compress a subspace of dimension $\ell$ into a subspace of dimension $n-(r- \ell)$.

The key ingredient of the algorithm is an analogue of augmenting paths for matchings in bipartite graphs, combined with a regularity property of “blown up” matrix spaces. (The $d$-blowup of the matrix space generated by $M_1, \dotsc, M_m$ is just the matrix space where the output sits: the space of $nd$ by $nd$ matrices of the form $M_1 \otimes T_1+ \dotsb +M_m \otimes T_m$, where the$T_j$ are arbitrary $d$ by $d$ matrices.)

It is known that this problem relates to the following ring of matrix semi-invariants denoted $R(n, m)$. For a field $\mathbb F$ it is the ring of semi-invariant polynomials for the action of $GL(n,\mathbb F) \times GL(n,\mathbb F)$ on tuples of matrices: $(A, C) \in GL(n,\mathbb F) \times GL(n,\mathbb F)$ sending $(M_1, \dotsc, M_m)$ to $(AM_1C^T, \dotsc, AM_mC^T)$. Then $(M_1, M_2, \dotsc, M_m)$ with non-commutative rank $r < n$, correspond to points where all non constant polynomials in $R(n, m)$ vanish.

This is joint work with Gábor Ivanyos and Youming Qiao.