  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\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)$.
  (2)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.
