Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
Masaki Hamada, Hiroshi Hirai
Abstract
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.
Topics & Concepts
MathematicsRank (graph theory)Noncommutative geometrySubmodular set functionTime complexityRegular polygonField (mathematics)Gaussian eliminationDiscrete mathematicsCombinatoricsAlgebra over a fieldPure mathematicsGaussianQuantum mechanicsPhysicsGeometryComplexity and Algorithms in Graphsgraph theory and CDMA systemsAlgebraic structures and combinatorial models