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}