Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-042 | 31st March 2022 14:42

Matrix Polynomial Factorization via Higman Linearization



In continuation to our recent work on noncommutative
polynomial factorization, we consider the factorization problem for
matrices of polynomials and show the following results.
\item Given as input a full rank $d\times d$ matrix $M$ whose entries
$M_{ij}$ are polynomials in the free noncommutative ring
$\mathbb{F}_q\langle x_1,x_2,\ldots,x_n \rangle$, where each $M_{ij}$ 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
$\log_2q$ that computes a factorization of $M$ as a matrix product
$M=M_1M_2\cdots M_r$, where each $d\times d$ matrix factor $M_i$ is
irreducible (in a well-defined sense) and the entries of each $M_i$
are polynomials in $\mathbb{F}_q \langle x_1,x_2,\ldots,x_n \rangle$ that are output
as algebraic branching programs. We also obtain a deterministic
algorithm for the problem that runs in $poly(d,n,s,q)$.
\item A special case is the efficient factorization of matrices whose
entries are univariate polynomials in $\mathbb{F}[x]$. When $\mathbb{F}$ is a finite
field the above result applies. When $\mathbb{F}$ is the field of rationals
we obtain a deterministic polynomial-time algorithm for the problem.

ISSN 1433-8092 | Imprint