# 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 '11 at 14:42
@Federico: Thankyou, I am looking for integers for now. However where is the complex entries reference? – Turbo Dec 18 '11 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 '11 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 '11 at 21:44
@Igor Rivin: This one may be easier and that is probably why it was solved so quickly! – Turbo Dec 19 '11 at 0:56

## 1 Answer

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.

-
The article tandfonline.com/doi/abs/10.1080/03081088708817831#.UZRzpKKnznM clearly says $R$ is commutative and associative ring with $1$. Katre's works as I had inferred is more number-theoretic. – Turbo May 16 '13 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 '13 at 9:01