2022/03/31 by Arvind, V., Joglekar, Pushkar S.
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2203.16978
In continuation to our recent work on noncommutative polynomial factorization, we consider the factorization problem for matrices of polynomials and show the following results. (1) Given as input a full rank d× d matrix M whose entries Mij are polynomials in the free noncommutative ring \mathbbFq⟨ x1,x2,…,xn ⟩, where each Mij is given by a noncommutative arithmetic formula of size at most s, we give a randomized algorithm that runs in time polynomial in d,s, n and log2q that computes a factorization of M as a matrix product M=M1M2⋯ Mr, where each d× d matrix factor Mi is irreducible (in a well-defined sense) and the entries of each Mi are polynomials in \mathbbFq ⟨ x1,x2,…,xn ⟩ that are output as algebraic branching programs. We also obtain a deterministic algorithm for the problem that runs in poly(d,n,s,q). (2)A special case is the efficient factorization of matrices whose entries are univariate polynomials in \mathbbF[x]. When \mathbbF is a finite field the above result applies. When \mathbbF is the field of rationals we obtain a deterministic polynomial-time algorithm for the problem.