TR22-042 Authors: Vikraman Arvind, Pushkar Joglekar

Publication: 31st March 2022 15:29

Downloads: 389

Keywords:

In continuation to our recent work on noncommutative

polynomial factorization, we consider the factorization problem for

matrices of polynomials and show the following results.

\begin{itemize}

\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.

\end{itemize}