Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
Masaki Hamada, Hiroshi Hirai · SIAM Journal on Applied Algebra and Geometry · 2021
We study the noncommutative rank (nc-rank) computation of a symbolic matrix whose entries are linear forms in noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson over the rational numbers, and by Ivanyos, Qiao, and Subrahmanyam over arbitrary fields. We present a significantly different polynomial time algorithm that works for any field. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.