MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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?

-
 The article you cite mention matrices with integer entries, which is a crucial hypothesis. With complex entries, I think 2 are enough. – Federico Poloni Dec 18 2011 at 14:42 @Federico: Thankyou, I am looking for integers for now. However where is the complex entries reference? – unknown (google) Dec 18 2011 at 16:53 I don't have a ready reference, just an idea for the proof (that's why I wrote "I think"). If a matrix has all distinct eigenvalues, then it is a $n$-th power (take $n$-th roots of the eigenvalues, keep the eigenvectors). So it is sufficient to find $C$ and $D$ with distinct eigenvalues such that $A=C+D$. We may assume without loss of generality that $A$ is in Jordan form, and then we can choose easily a diagonal $D$ such that $D$ and $C=A-D$ have distinct diagonal entries. – Federico Poloni Dec 18 2011 at 18:14 Is there a good algorithm for the "usual" Waring problem? The usual circle problem arguments seem to be purely enumerative, and not so much constructive... – Igor Rivin Dec 18 2011 at 21:44 @Igor Rivin: This one may be easier and that is probably why it was solved so quickly! – unknown (google) Dec 19 2011 at 0:56
show 3 more comments

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.
 The article tandfonline.com/doi/abs/10.1080/… clearly says $R$ is commutative and associative ring with $1$. Katre's works as I had inferred is more number-theoretic. – unknown (google) May 16 at 5:53 Yes, but the results in Katre's work are often also for an arbitrary commutative and associative ring with unity, see arxiv.org/abs/math/0702445. And you asked yourself for the special case $R=\mathbb{Z}[x_1,\ldots ,x_m]$. It seems very interesting to consider also rings of integers etc. From the algorithmic point of view this should be better, too. – Dietrich Burde May 16 at 9:01