Efficient Algorithm for Matrix Version of Waring's Problem Given an $n \times n$ matrix $A$ with entries in a commutative and associative ring with $1$ (say $Z[x_{1},\dots,x_{n^{2}}]$), the following paper guarantees existence of seven $B_{i}$s such that $A = \sum_{i=1}^{7}B_{i}^{k}$  with $k \le n$.
http://www.tandfonline.com/doi/abs/10.1080/03081088708817831
Is there an explicit algorithm to find the seven $B_{i}$ matrices?
 A: The result mentioned above is Waring's problem for matrices (respectively for algebraic
number fields). The result is:
Theorem (Katre, Kuhle 1990): Let $R$ be an order in an algebraic number field $K$. 
Let $n\ge k \ge 2$. Then every $n\times n$ matrix over $R$ is a sum of $k$-th powers
if and only if it is the sum of seven $k$-th powers if and only if $(k, disc (R)) = 1$.
If this is true, then the question is if the seven matrices can be constructed explicitly.
For the case $k=n=2$ and $R=\mathbb{Z}$ this seems to be the case (article of Newman
 "Sums of squares of matrices"), by constructing certain companion matrices to characteristic polynomials: every integral 
$2 \times 2$ matrix is the sum of at most $3$ integral squares. The proof for the general
case however uses an argument of the form "every $n\times n$-matrix is a sum of $k$-th powers
in $M_n(R)$ if every $m\times m$-matrix is a sum of $k$-th powers in $M_m(R)$ for
$n\ge m\ge 1$ and $k\ge 2$", which does not seem to be constructive.
