Efficient evaluation of noncommutative polynomials using tensor and noncommutative Waring decompositions
This paper analyses a Waring type decomposition of a noncommuting (NC) polynomial $p$ with respect to the goal of evaluating $p$ efficiently on tuples of matrices. Such a decomposition can reduce the number of matrix multiplications needed to evaluate a noncommutative polynomial and is valuable when a single polynomial must be evaluated on many matrix tuples.In pursuit of this goal we examine a noncommutative analog of the classical Waring problem and various related decompositions. For example, we consider a "Waring decomposition" in which each product of linear terms is actually a power of a single linear NC polynomial or more generally a power of a homogeneous NC polynomial. We describe how NC polynomials compare to commutative ones with regard to these decompositions, describe a method for computing the NC decompositions and compare the effect of various decompositions on the speed of evaluation of generic NC polynomials.
\section{Introduction}
\ \ \
The Waring problem has had a long history since it was first proposed in 1770 by Edward Waring. Initially it was a question about integers, asking whether a natural number could be written as the sum of powers of natural numbers. Later it was extended to polynomials. It concerns the question whether a given polynomial, $f(x_1, x_2, \dots, x_n)$, can be represented by sums of powers of polynomials, where $x_i$'s are variables which commute. In this form, the Waring problem is closely related to symmetric tensor decomposition, see section \ref{sec:ClassicalBackground}. This problem
was treated successfully in \cite{RS00} and \cite{FOS12} and
has been studied extensively, as is shown, for example, in \cite{BC11} and \cite{GV08}. In this paper, we assume that $x_i$'s are noncommutative variables, and derive solutions for the noncommutative version of the  Waring problem. Our results can be used to efficiently evaluate noncommutative polynomials on tuples of matrices.


Pursuing the  noncommutative \ Waring Problem \  is in the spirit of the burgeoning area called {\it free analysis}.
Here one takes classical problems and works out analogs with noncommutative \ variables,
which are {\it free} of constraints.
These free analogues typically have interpretations for matrix or operator variables
and their development often impacts various areas.


One of the original efforts here was Voiculescu's free probability,
which started by developing a notion of entropy for operator variables
and which has a become a big area having many associations to
random matrix theory, \cite{MS17}.
Some other directions are  free
analytic function theory, cf. \cite{KVV14} and   free real algebraic geometry \cite{BKP16}
with some consequences for system engineering being \cite{HMPV09}. Our paper develops the noncommutative \ analogue of the classical Waring problem.








\subsection{Problem statement}
\ \ \ \
We now state a natural noncommutative version of the classical polynomial Waring problem. We shall work with functions of
 $g$ noncommutative variables
$$x = (x_1, x_2, ..., x_g)$$
and be interested in  powers of
  linear functions
$$L_s(x): = A^s_1x_1 + A^s_2x_2 + ... A^s_g x_g,$$
where $s$ is an index and $A^s_i
 \in \mathbb{R} \ or \ \mathbb{C}$ for $1 \le i \le g$.

For any (index) tuple $\alpha = (\alpha_1, \alpha_2, ..., \alpha_d)$, where $\alpha_i $ for $1 \le i \le d$ are  integers between 1 and g, we denote
$$ x^\alpha = x_{\alpha_1}x_{\alpha_2}x_{\alpha_3}...x_{\alpha_d}.$$
For example,
if $\alpha = ( 1, 2, 1,3)$, then
$x^\alpha = x_1x_2x_1x_3$.


\begin{defi}
An homogeneous NC degree $d$   polynomial $p$ has a
$t$-term \df{real Waring  (resp. complex Waring)
decomposition}
provided that
$p(x)$ can be written
as the sum of $t$ terms of  the $d^{th}$-power of  linear functions of $x$, i.e.,
\begin{equation} \label{Waring_rep}
p(x)=\sum_{s=1}^t [ A^s_1x_1 + A^s_2x_2 + ... A^s_gx_g]^d
\end{equation}
with real (resp. complex) numbers $A_j^s$.
\qed \end{defi}


\def{\mathbb C}{{\mathbb C}}

\noindent \df{NC Waring Problem: }

{\bf Determine if a noncommutative homogeneous degree $d$ polynomial $p$ has a $t$-term Waring decomposition.}

\bigskip

In this paper we will reduce this problem to the classical commutative variable Waring problem, thereby effectively solving it over ${\mathbb C}$.

We also examine the

\bigskip

 \noindent
 \df{General NC Waring Problem:}

 {\bf Determine if a homogeneous noncommutative polynomial is the sum of $d^{th}$ powers of homogeneous polynomials
of degree $\delta$.}

\bigskip

In a similar spirit, we reduce the NC general Waring problem to a classical Waring problem, but in more variables.

\subsection{Background on the Waring Problem}
\ \ \ \
The classical commutative versions of these problems are well summarized in \cite{FOS12}.
\bigskip

\subsubsection{Classical  Waring Problem.}
\label{sec:ClassicalBackground}
\ \ \ \
According to Theorem 2.2 of \cite{OO12}, we have the following theorem for the  classical Waring decomposition of linear terms:

\begin{thm} \label{classical_result}
 A homogeneous polynomial of degree $d$ in $g$ variables can always be expressed as the sum of powers of linear forms with complex coefficients. Moreover, for a general homogeneous polynomial, the number of linear forms needed is $\lceil \frac 1g  {{g+d-1} \choose d} \rceil$, except for
 \begin{itemize}
     \item $d = 2$, where $g$ terms are needed
     \item $(d,g) = (3,5),(4,3),(4,4),(4,5)$ where $\lceil \frac 1g  {{g+d-1} \choose d} \rceil + 1$ terms are needed.
 \end{itemize}
\end{thm}

\noindent
{\bf Waring vs Tensor Decomposition.}
\ \ \ \
It is well known that the classical polynomial Waring problem is equivalent to symmetric tensor decomposition. Let $T \in (\mathbb C^{g})^{\otimes d}$ be a symmetric tensor, i.e. a symmetric multiidexed array, with entries $T_\alpha \in \mathbb C$ where $\alpha= (\alpha_1, \dots, \alpha_d)$ is a $d$-tuple of integers between $1$ and $g$. We may associate $T$ to a homogeneous degree d polynomial $p_T (x)$ in the commutative variables $z=(z_1, \dots, z_g)$ by setting
\[
p_T (z)= \sum_{|\alpha|=d} T_\alpha z^\alpha.
\]

Suppose $T$ has rank $r$ symmetric tensor decomposition
\[
T= \sum_{s=1}^r A^s \otimes \cdots \otimes A^s \quad \quad \mathrm{where \ } d \mathrm{\ copies \ of \ } A^s \mathrm{\ appear \ in \ each \ tensor \ product.}
\]
Here $A^s=(A_1^s, \dots, A_g^s) \in \mathbb C^{g}$ for each $s$. Then it is straightforward to check that
\[
p_T (z) = \sum_{s=1}^r \left( \sum_{i=1}^g A_i^s z_i \right)^d.
\]
That is, a rank $r$ symmetric tensor decomposition of $T$ corresponds to a rank $r$ Waring decomposition for $p_T (z)$. By reversing this correspondence one sees that a rank $r$ Waring decomposition for a homogeneous polynomial gives a rank $r$ symmetric tensor decomposition for the associated symmetric tensor.

\noindent
\subsubsection{Classical General Waring Problem.}
\ \ \ \
The classical commutative Waring problem can be generalized from representation by powers of linear functions to powers of any degree homogeneous polynomials. The generalized classical Waring  problem has also been well studied.
According to Theorem 4 in \cite{FOS12},
there is an upper bound for the number of terms needed for
such  problems:

\begin{thm}
A general homogeneous polynomial of degree $\delta d$ in $g$ variables, where $d \ge 2$, can be expressed as a sum of at most
$d^{g - 1}$ $d^{th}$ powers of degree $\delta$ homogeneous
complex coefficient polynomials. Moreover, for a fixed $g$, this bound is sharp for all sufficiently large $\delta$.
\end{thm}

\subsection{An easily stated result}
\ \ \ \
Before stating a result we need a definition.
Define an \df{indicator function} on
 an index $d$-tuple $\alpha=(\alpha_1, \dots, \alpha_d)$ by first defining
\index{$\mathbbm{1}_j^{\alpha_i}$ }
$$\mathbbm{1}_j^{\alpha_i}  =
\begin{cases}
1 & \textrm{if }  \alpha_i = j \\
0 & \textrm{if }  \alpha_i \neq j
\end{cases}.
$$
Then the indicator function $\mathbbm{1}_j^\alpha$ which gives the number of $j$'s appearing in $\alpha$ is
\index{$\mathbbm{1}_j^{\alpha}$ }
$$
\mathbbm{1}_j^\alpha := \sum_{i=1}^d \mathbbm{1}_j^{\alpha_i}.
$$

A corollary for ${\delta}=1$ of Theorem \ref{thm:LinearWaring} is:
\begin{cor}  \label{cor}
Suppose a NC homogeneous polynomial $p(x) = \sum_\alpha {P_\alpha x^\alpha}$, where $P_\alpha = P_{\alpha_1, \alpha_2, ..., \alpha_d}$ $\in \mathbb{C} $,  satisfies $P_\alpha = P_{\tilde{\alpha}}$ for any index sets $\alpha, \tilde{\alpha}$ such that $\mathbbm{1}_j^\alpha = \mathbbm{1}_j^{\tilde{\alpha}}$  for all $1 \le j \le g$. Then $p$ has an NC complex coefficient Waring decomposition \ with linear powers.
Moreover, for such a NC homogeneous polynomial,
the number of terms needed is
$$
\left \lceil \frac{\binom{g+d-1}{d}} g  \right \rceil,
$$
except in the cases
\begin{itemize}
     \item $d = 2$, where $g$ terms are needed
     \item $(d,g) = (3,5),(4,3),(4,4),(4,5)$ where $\lceil \frac 1g  {{g+d-1} \choose d} \rceil + 1$ terms are needed.
 \end{itemize}
\end{cor}

\begin{proof}
This corollary is a combination of Theorem \ref{thm:LinearWaring}, our main result in Section \ref{main_result}, and the well developed solutions for the
classical Waring Theorem stated in Theorem \ref{classical_result}.
\end{proof}

\subsection{NC polynomial evaluation}

Let $p(x)=\sum_{|\alpha| \leq d} P_\alpha x^\alpha$ be a noncommutative polynomial. Then for any $n$ and for any $g$-tuple of $n \times n$ matrices $X=(X_1, \dots, X_g)$, we define the \df{evaluation} of $p$ on $X$ by
\[
p(X)=\sum_{|\alpha| \leq d} P_\alpha X^\alpha
\]
where $X^0=I_n$. In the case where $p$ is a homogeneous noncommutative polynomial and has a NC Waring decomposition, the NC Waring decomposition of $p$ may be used to efficiently evaluate $p$ on matrix tuples. This is especially useful in situations where a single $p$ must be evaluated on many different tuples of matrices.

Suppose $p$ has the NC Waring decomposition
\[
p(x)=\sum_{s=1}^t [A_1^s x_1 + A_2^2 x_2 + \cdots + A_g^s x_g]^d.
\]
Then for any matrix tuple $X$ we may evaluate $p(X)$ using $tg-1$ matrix additions and $t$ matrix exponentiations of degree $d$, where $t \leq \lceil \frac 1g  {{g+d-1} \choose d} \rceil + 1$ by Corollary \ref{cor}. We note that powers of a matrix may be efficiently computed either by decomposing the exponent as a sum of powers of two, or by first computing the Jordan form of the matrix.

In contrast, a naive evaluation of a single degree $d$ NC monomial requires $d-1$ matrix multiplications. As a consequence, the naive approach to evaluating a homogeneous degree $d$ NC polynomial in $g$ variables on a matrix tuple can require up to $g^d (d-1)$ matrix multiplications and $g^d-1$ matrix additions.

A matrix exponentiation of degree $d$ can easily be evaluated with at most $d-1$ matrix multiplications, so to compare the computation complexity of these methods we may compare $g^d$ and $\lceil \frac 1g  {{g+d-1} \choose d} \rceil + 1$. A more informative comparison on the comparison comes from Stirling’s approximation which shows
\[
\left\lceil \frac 1g  {{g+d-1} \choose d} \right\rceil + 1 \lessapprox \frac{1}{g} \left( \frac{e(g+d)}{d} \right)^d.
\]
It follows that the ratio of $\lceil \frac 1g  {{g+d-1} \choose d} \rceil$ to $g^d$ is approximately bounded above by
\[
\frac{1}{g} \left( \frac{e(g+d)}{gd} \right)^d,
\]
a quantity that rapidly (geometrically) approaches zero as $g$ or $d$ increase, provided $3 \leq d,g$.

The authors thank Ignat Domanov for suggesting efficient polynomial evaluation as an application of NC Waring decompositions.


\subsection{Numerical computation of NC Waring decompositions}
\ \ \ \
We conclude the introduction with an example which computes an NC Waring decomposition by using popular tensor decomposition software. Consider the homogeneous noncommutative polynomial
\[
\begin{array}{rclcl}
p(x)&=& x_1^3-4 x_2^3 -4 x_3^3 + 5 x_1 x_1 x_2+ 5 x_1 x_2 x_1 + 5 x_2 x_1 x_1 -3 x_1 x_1 x_3-3 x_1 x_3 x_1-3 x_3 x_1 x_1 \\
& & +7 x_2 x_2 x_1 + 7 x_2 x_1 x_2 + 7 x_1 x_2 x_2-11 x_2 x_2 x_3 - 11 x_2 x_3 x_2 - 11 x_3 x_2 x_2 \\
& & + 6 x_3 x_3 x_1 + 6 x_3 x_1 x_3 +6 x_1 x_3 x_3 - 6 x_3 x_3 x_2 -6 x_3 x_2 x_3-6 x_2 x_3 x_3 \\
& &  + x_1 x_2 x_3 +x_1 x_3 x_2 + x_2 x_1 x_3 +x_2 x_3 x_1+ x_3 x_1 x_2+x_3 x_2 x_1.
\end{array}
\]
We associate $p(x)$ to the symmetric tensor $T$ defined by its frontal slices
\[
T(:,:,1)=\begin{pmatrix}
1 & 5 & -3 \\
5 & 7 & 1 \\
-3 & 1 & 6
\end{pmatrix}
\quad \quad
\mathrm{and}
\quad \quad
T(:,:,2)=\begin{pmatrix}
5 & 7 & 1 \\
7 & -4 & -11 \\
1 & -11 & -6
\end{pmatrix}
\]
and
\[
T(:,:,3)=\begin{pmatrix}
-3 & 1 & 6 \\
1 & -11 & -6 \\
6 & -6 & -4
\end{pmatrix},
\]
where $T(:,:,i)$ is the standard Matlab index notation.

Using Tensorlab \cite{VDSBL16}  we compute that $T$ is a rank $4$ tensor and has symmetric tensor decomposition
\[
T= v_1 \otimes v_1 \otimes v_1 +v_2 \otimes v_2 \otimes v_2 +v_3 \otimes v_3 \otimes v_3 + v_4 \otimes v_4 \otimes v_4
\]
where
\[
v_1=\begin{pmatrix}
3.839 \\
-1.591 \\
2.593
\end{pmatrix}
\quad \quad
v_2=(-1)^{1/3} \begin{pmatrix}
-1.577 \\
-1.697 \\
0.902
\end{pmatrix}
\]
and
\[
v_3=\begin{pmatrix}
0.821 \\
-2.121 \\
-1.793
\end{pmatrix}
\quad \quad
v_4=\begin{pmatrix}
-3.917 \\
1.673 \\
-2.462
\end{pmatrix}.
\]
It follows that $p$ has the rank 4 NC Waring decomposition
\[
\begin{array}{rclcl}
p(x)&=& (3.839 x_1 - 1.591 x_2 +  2.593 x_3)^3 \\
& & + ((-1)^{1/3} (-1.577 x_1 - 1.697 x_2 + .902 x_3))^3 \\
& & + (.821 x_1 - 2.121 x_2 - 1.793 x_3)^3 \\
& & + (-3.917 x_1 + 1.673 x_2 -2.462 x_3)^3.
\end{array}
\]
This is easy to numerically verify using NCAlgebra \cite{OHMS}.

A naive evaluation of $p$ on a matrix tuple using the original definition of $p$ requires $54$ matrix multiplications. In contrast, evaluating $p$ on a matrix tuple using its NC Waring decomposition only requires $8$ matrix multiplications.

\subsection{Guide to readers}
\ \ \ \
In Section \ref{sec:linear} we show that the NC Waring problem reduces to the classical Waring problem. The section begins by introducing a compatibility condition which is necessary for a NC homogeneous polynomial $p$ to have a Waring decomposition. The main result of this section is Theorem \ref{thm:LinearWaring} which shows that a NC homogeneous polynomial $p$ has a $t$-term Waring decomposition if and only if it satisfies our compatibility condition and its commutative collapse has a $t$-term Waring decomposition.

Section \ref{sec:general} considers the general NC Waring problem. Similar to the $\delta=1$ case, we begin by introducing a general $\delta$-compatibility condition which is necessary for the existence of a $(\delta,d)$-NC Waring decomposition. The main result of the section is Proposition \ref{prop:GenNCWaringMain} which shows that, under the $\delta$-compatibility condition, the general NC Waring problem is equivalent to a commutative Waring problem for a polynomial with an increased number of variables. We end with Section \ref{sec:NeedExtraVars} which illustrates that an increase in our number of variables is necessary to reduce the general NC Waring decomposition \ to a commutative Waring decomposition .





\section{The  noncommutative Waring problem} \label{sec:linear}
\ \ \ \
In this section we will present our main results on the linear noncommutative Waring problem.

\subsection{Commutative collapse}
\ \ \ \
Our results are associated with commutative problems through a correspondence we now describe.


For a NC polynomial $p$, the associated \df{commutative collapse}, $p^c$, is the commutative polynomial obtained by considering the variables of $p$ to be commutative.
Our notation for commutative collapse for an NC monomial $x^\alpha = x_{\alpha_1} x_{\alpha_2} \dots x_{\alpha_d}$ is $X^\alpha  = X_{\alpha_1} X_{\alpha_2} \dots X_{\alpha_d}$. For example, when $\alpha = (1, 2, 1, 2 )$, $x^\alpha = x_1x_2x_1x_2$ collapses to $X^\alpha = X_1^2X_2^2$.


We impose an equivalence relation $\sim_c$ \index{$\sim_c$} on NC monomials by saying that $x^\alpha$ and $x^{\tilde{\alpha}}$ are \df{commutative equivalent} if they have the same commutative collapse:
$$
x^\alpha \sim_c  x^{\tilde{\alpha}} \quad   \text{iff} \quad
X^\alpha = X^{\tilde{\alpha}}.
$$
Moreover, two index tuples $\alpha$ and $\tilde{\alpha}$ are \df{commutative equivalent}, denoted $\alpha \sim_c  {\tilde{\alpha}}$,
iff $x^\alpha \sim_c  x^{\tilde{\alpha}}$.
Note that
$$\alpha \sim_c  {\tilde{\alpha}}\qquad \mbox{ iff} \qquad  \bmone^\alpha_i = \mathbbm{1}^{\widetilde \alpha}_i
\ \ for \ i = 1, \dots, g.$$

\subsection{Main results on the NC Waring decomposition}
\ \ \ \
Our results contain two parts. First we state a compatibility condition necessary for the existence of a Waring decomposition \S \ref{sssec:Compatibility}. Second, if the compatibility condition holds,
we reduce the NC Waring problem to the classical commutative
Waring problem \S \ref{main_result}.

\subsubsection{The Compatibility Condition}
\label{sssec:Compatibility}
\ \ \ \
As we next  see the following condition is necessary for existence
of a NC Waring decomposition.

\begin{defi}
A noncommutative homogeneous degree $d$ polynomial $p(x)$,
$$
p(x) = \sum_{|\alpha|=d} {P_\alpha x^\alpha}\qquad P_\alpha := P_{\alpha_1, \alpha_2, ..., \alpha_d} \in \mathbb{R} \ or \ \mathbb{C},
$$
satisfies the \df{compatibility condition} means
\begin{equation}
\label{eq:Paequiv}
P_\alpha = P_{\tilde{\alpha}} \qquad for \ all \
\alpha \sim_c \tilde{\alpha}.
\end{equation}
Sometimes we say {$p$ is compatible}.
\qed \end{defi}

A noncommutative homogeneous polynomial $p$ of degree $d$ which satisfies the compatibility condition can be thought of as a ``symmetric\footnote{The term symmetric typically refers to a noncommutative polynomial $p$ which is equal to its transpose $p^T$, which is different than the notion discussed here.} noncommutative homogeneous polynomial of degree $d$" in the sense that $p$ is invariant under the following action of the symmetric group. Given tuple a tuple $\alpha=(\alpha_1,\alpha_2, \dots, \alpha_d)$ of length $d$ and a permutation $\pi \in \mathcal{S}_d$ define
\[
\pi (\alpha)=(\alpha_{\pi(1)}, \alpha_{\pi(2)}, \dots, \alpha_{\pi(d)}) \quad \mathrm{that \ is} \quad \pi (x^\alpha)=x^{\pi(\alpha)}.
\]
It is then straight forward to check that $x^\alpha \sim_c  x^{\tilde{\alpha}}$ and $\alpha \sim_c \tilde{\alpha}$ if and only if there is a permutation $\pi \in \mathcal{S}_d$ such that $\pi(\alpha)=\tilde{\alpha}$.

We extend the action of $\mathcal{S}_d$ to noncommutative homogeneous polynomials of degree $d$ by
\[
\pi (p(x))=  \sum_{|\alpha|=d} {P_\alpha x^{\pi(\alpha)}}.
\]
Then $p$ meets the compatibility condition if and only if
\[
\pi(p(x))=p(x)
\]
for all permutations $\pi \in \mathcal{S}_d$.

The following lemma shows that the compatibility condition is necessary for existence of an NC Waring decomposition.


\begin{lem} \label{NecessaryCond}
If a NC homogeneous polynomial of degree $d$
has a  $t$-term NC Waring decomposition,
then the compatibility condition \eqref{eq:Paequiv} holds. Moreover, if $p$ meets the compatibility condition, then $p$ has a $t$-term NC Waring decomposition over the complex numbers (resp. real numbers) if and only if
\begin{equation} \label {Peq}
P_\alpha = \sum_{s=1}^t \prod_{j=1}^g \left(  A_j^s \right)^{\mathbbm{1}_j^\alpha}
\end{equation}
has a solution $A_j^s \in \mathbbm{C} ( \textrm{resp. } A_j^s \in \mathbbm{R} ).$
\end{lem}

\begin {proof}
$p$ has a $t$-term Waring decomposition \ if and only if
\begin{equation*}
\label{eq:pcore}
\sum_{|\alpha|=d} P_\alpha x^\alpha   = \sum_{s=1}^t [L_s(x)]^d
 =  \sum_{s=1}^t   \sum_{|\alpha|=d} \left( \prod_{i=1}^d A_{\alpha_i}^s \right) x^\alpha
= \sum_{|\alpha|=d} \left( \sum_{s=1}^t \prod_{i=1}^d A_{\alpha_i}^s \right) x^\alpha.
\end{equation*}
Comparing the coefficients of $x^\alpha$ on both sides, we get
\begin{equation}
\label{eq:pwkeyG}
P_\alpha  = \sum_{s=1}^t \prod_{i=1}^d A_{\alpha_i}^s
= \sum_{s=1}^t \prod_{j=1}^g \left(  A_j^s \right)^{\mathbbm{1}_j^\alpha}
\end{equation}
This also implies $P_\alpha = P_{\tilde{\alpha}}$ if $\mathbbm{1}_j^\alpha
= \mathbbm{1}_j^{\tilde{\alpha}}$ for all $1 \le j \le g $.
\end {proof}

\begin{exa}
\rm A NC homogeneous polynomial $p(x) = \sum_\alpha {P_\alpha x^\alpha}$ has the complex (resp. real) $2$-term Waring decomposition \
$$
p(x) = (a x_1 + c x_2)^3 + (b x_1 + d x_2)^3
$$
if and only if
\begin{equation}
\begin{aligned}
P_{1,1,1}  &
=   a^3  + b^3
\\
P_{1,1,2}  &= a^2 c + b^2 d = \frac 1 6 ((a+c)^3 +(b+d)^3- (a-c)^3-(b-d)^3)- \frac 1 3 P_{2,2,2}
\\
P_{1,2,2}  &=   a c^2 + b d^2 = \frac 1 6 ((a+c)^3 +(b+d)^3+ (a-c)^3+(b-d)^3) - \frac 1 3 P_{1,1,1}
\\
P_{2,2,2}  &= c^3  + d^3
\end{aligned}
\end{equation}
has a solution $a,b,c,d \in \mathbbm{C}$ (resp. $\mathbbm{R}$)
\qed
\end{exa}




\subsubsection{Reduction of NC Waring to Classical Waring}
\label{main_result}
\ \ \ \
There has been extensive work on the Waring problem in the classical commutative case and what we see in this section is that the NC Waring problem reduces to the commutative one.



\begin{lem}\label{lem:count_eta}
For an index tuple $\alpha$, denote $\eta[\alpha]$ as the number of $\tilde{\alpha}$'s that satisfy $\bmone^\alpha_j = \bmone^{\talpha}_j$  for all $1 \le j \le g$. Then
$$
\eta[\alpha] = \frac {d !} {\prod_{j = 1}^{g} (\mathbbm{1}_j^\alpha) !}
$$
\end{lem}

\begin{proof}
The problem is equivalent to calculating how many d-tuples can be formed by elements from
$
\alpha = ( \alpha_1, \alpha_2, \dots, \alpha_d )
$, which is equivalent to
$$
\eta[\alpha] = \frac {\text{\# of permutations of }d\text{ items}} {\text{\# of permutations of repetitions}} =\frac {d !} {\prod_{j = 1}^{g} (\mathbbm{1}_j^\alpha) !}.
$$
\end{proof}

\begin{thm} \label{thm:LinearWaring}
Suppose $p$ is an NC homogeneous polynomial which satisfies the compatibility conditions \eqref{eq:Paequiv}.
Then the commutative collapse $p^c$ has the Waring decomposition \
\begin{equation} \label{eq:comm_WR}
p^c(X)=\sum_{s=1}^t [ A^s_1X_1 + A^s_2X_2 + \cdots + A^s_g X_g]^d
\end{equation}
(with $X_i$ being commuting variables) if and only if $p$ has the
nc Waring decomposition \
\begin{equation} \label{eq:nc_WR}
p(x)=\sum_{s=1}^t [ A^s_1x_1 + A^s_2x_2 + \cdots +A^s_g x_g]^d .
\end{equation}
Note that the number of terms is the same and the
real coefficients
(resp. complex coefficients) $A_j^s$  are the same.
\end{thm}

\def{\mathcal R}{{\mathcal R}}


\begin{proof}
The proof begins by laying out the algebraic connection
between $p$ and $p^c$. Let ${\mathcal R}$ denote a set consisting of one  representative from each $\sim_c$ equivalence class. Then from \eqref{eq:Paequiv}, the NC polynomial
$
p(x) = \sum_{|\alpha| = d}  P_\alpha x^\alpha
$
has
commutative collapse satisfying
$$
p^c(X)
 =
 \sum_{\alpha \in {\mathcal R}  }
\quad  \sum_{ \tilde{\alpha} \sim_c  \alpha } P_{\tilde{\alpha}} X^{\alpha}
 =
 \sum_{\alpha \in {\mathcal R} }
 P_\alpha^c \  X^{\alpha},
$$
where
$
P_\alpha^c =
 \sum_{ \tilde{\alpha} \sim_c  \alpha } P_{\tilde{\alpha}}
$.

Thus if $p$ satisfies the compatibility condition
 \eqref{eq:Paequiv}, then
\begin{equation}
 \label{ncToc}
P_\alpha^c =  \eta[\alpha ]    P_{\widetilde \alpha} \qquad for \ {\alpha} \in {\mathcal R}
\ \ and \ \
{\alpha} \sim_c {\widetilde \alpha}.
\end{equation}
Therefore, $p^c$ is the commutative collapse of a
compatible NC homogeneous degree $d$ polynomial $p$
 iff $P_\alpha^c =  \eta[\alpha ]    P_\alpha$ for all index tuples $\alpha$ of length $d$.

Now we proceed to prove our theorem. Assume $p$ has the NC Waring decomposition \ \eqref{eq:nc_WR}, we shall obtain a reversible formula for the Waring decomposition \ of $p^c$.
By equation \eqref{ncToc} and Lemma \ref{NecessaryCond}, the commutative collapse $p^c$ is
\begin{equation} \label{eq:collapse}
p^c(X) =
 \sum_{\alpha \in {\mathcal R}, \  | \alpha | = d  }\eta[\alpha ]    P_\alpha X^\alpha  = \sum_{|\alpha|=d} P_\alpha X^\alpha  = \sum_{|\alpha|=d} \sum_{s=1}^t \prod_{j=1}^g \left( A_j^s \right)^{\mathbbm{1}_j^\alpha} X^\alpha
\end{equation}
Thus
\begin{equation} \label{eq:collapse2}
p^c(X)
  = \sum_{s=1}^t \sum_{|\alpha|=d} \prod_{i=1}^d A^s_{\alpha_i} X^\alpha
  = \sum_{s=1}^t [ A^s_1X_1 + A^s_2X_2 + ... A^s_g X_g]^d
\end{equation}




On the other hand, suppose $p$'s commutative collapse, $p^c$, has the commutative Waring decomposition \ \eqref{eq:comm_WR}, then
the calculations in \eqref{eq:collapse} and \eqref{eq:collapse2} can be reversed. By comparing coefficients, this is equivalent to
$$
P^c_\alpha = \eta[\alpha ]
 \sum_{s=1}^t \prod_{j=1}^g \left( A_j^s \right)^{\mathbbm{1}_j^\alpha}
$$
for all $\alpha \in {\mathcal R}$.
Therefore by \eqref{ncToc},
$p$ satisfies
 $$
P_\alpha =\sum_{s=1}^t \prod_{j=1}^g \left( A_j^s \right)^{\mathbbm{1}_j^\alpha}
$$
for all index tuples $\alpha$ of length $d$. Hence by Lemma \ref{NecessaryCond}, $p$ has the Waring decomposition \ \eqref{eq:nc_WR}.
Thus under the compatibility condition \eqref{eq:Paequiv}, the NC polynomial $p$ has a Waring decomposition \ iff its commutative collapse $p^c$ has the same Waring decomposition.
\end{proof}



\section {The general noncommutative Waring problem} \label{sec:general}
\ \ \ \
 We now consider a more general situation of which the problem in the preceding section is the base case. As you will see, the bookkeeping and notation is formidable, so it is very helpful to have done a simpler case. In the previous section our focus was to determine if a degree $d$ noncommutative \  homogeneous polynomial can be expressed as sums of powers of linear terms. Now we examine when a degree ${\delta} d$ noncommutative \  homogeneous polynomial can be expressed as sums of powers of homogeneous degree ${\delta}$ terms.


\subsection{Problem formulation and notation}
\ \ \ \
Let \index{$T^g_\delta$} $T^g_\delta$ be the set of all possible $\delta$-tuples whose elements are integers between $1$ and $g$, i.e.,
$$
T^g_\delta = \{ (\alpha^1, \alpha^2, \dots, \alpha^\delta) \mid 1 \le \alpha^i \le g \}.
$$
Additionally, define \index{$( T^g_\delta )^d $} $( T^g_\delta )^d $ by
$$
( T^g_\delta )^d = \{ (\alpha_1, \alpha_2, \dots, \alpha_d) \mid \alpha_i \in T^g_\delta \}.
$$
That is, $( T^g_\delta )^d$ is the set of $d$-tuples of $\delta$ tuples of indices.
For any $\alpha = (\alpha_1, \dots, \alpha_d) \in (T^g_\delta)^d$, where $\alpha_i = (\alpha_i^1, \dots, \alpha_i^{\delta}) \in T^g_\delta, $
we can write
\[
x^{\alpha} = x^{\alpha_1}x^{\alpha_2} \dots x^{\alpha_d}.
\]
It is natural to identify $ x^\alpha$ with
\[
x_{\alpha_1^1} x_{\alpha_1^2} \dots x_{\alpha_1^\delta} x_{\alpha_2^1}
\dots x_{\alpha_d^1}
\dots x_{\alpha_d^\delta}.
\]

Recall our notation for a degree $\delta$ homogeneous polynomial is
$$
H(x) = \sum_{\beta \in T^g_\delta} A_{\beta} x^\beta,
$$
where $A_{\beta} = A_{(\beta^1, \beta^2, \dots, \beta^\delta)} \in \mathbb{C}$.

\begin{rmk}
\rm For any $ \alpha = (\alpha_1, \alpha_2, \dots, \alpha_d) \in (T^g_\delta)^d$,  we can identify
$$\alpha = ((\alpha_1^1, \alpha_1^2, \dots, \alpha_1^\delta), \dots, (\alpha_d^1, \alpha_d^2, \dots, \alpha_d^\delta))$$
with
$$
 (\alpha_1^1, \alpha_1^2, \dots, \alpha_1^\delta, \dots, \alpha_d^\delta) \in T^g_{\delta d}.$$ On the other hand, for any element of $T^g_{\delta d}$, we can reverse this identification and form groups of size $\delta$ to get a $d$-tuple of $\delta$-tuples. Hence $(T^g_\delta)^d$ and $T^g_{\delta d}$ are isomorphic
and we let $\tau$ \index{$\tau$} denote the isomorphism
 $$\tau : T^g_{\delta d}  \to (T^g_\delta)^d$$
 which accomplishes this grouping.
\qed
\end{rmk}

\bigskip

\noindent
{\bf The} \df{General NC Waring Problem:}

 {\bf
\ \ \ \ Given a NC homogeneous degree $\delta d$ polynomial p, does it have a t-term $d^{th}$ power real NC Waring (resp. complex NC Waring)
decomposition of  degree $\delta$. That is, can $p(x)$ be written as
\begin{equation}
\label{eq:deldWaring}
p(x) = \sum_{s = 1}^t (H_s(x))^d = \sum_{s = 1}^t \left ( \sum_{\beta \in T^g_\delta} A^s_{\beta} x^{\beta} \right )^d?
\end{equation}}

\bigskip

We call this problem the $({\delta},d)$-NC Waring problem and say a a decomposition of the form \eqref{eq:deldWaring} is a \df{$t$-term $({\delta},d)$-NC Waring decomposition}. Similarly for a commutative polynomial $p^c$, we say a decomposition of the form \eqref{eq:deldWaring} (with $x^\beta$ replaced by $X^\beta$) is a \df{$t$-term $({\delta},d)$-Waring decomposition}. Note that the problem treated in Section \ref{sec:linear} is exactly the $(1,d)$-NC Waring problem.

An obvious fact is, if $p$ is a degree $\delta d$ NC homogeneous polynomial and $p$ has a $t$-term $(\delta,d)$-NC Waring decomposition ,
then its commutative collapse $p^c$ has a $t$-term $(\delta,d)$-Waring decomposition .

\subsubsection{Tuple indicator functions}
\ \ \ \
We now extend the notion of indicator function to tuples of ${\delta}$-tuples.
For two $\delta-$tuples $\beta,\gamma \in T^g_{\delta}$, denote
\index{$\mathbbm{1}_\beta^{\gamma}$ }
$$
\mathbbm{1}_\beta^{\gamma} =
\begin{cases}
1 & \textrm{if }  \gamma = \beta \\
0 & \textrm{otherwise},
\end{cases}.
$$
Then for an index tuple $\mu \in (T^g_\delta)^d$, the number of times a particular $\delta-$tuple $\beta \in T^g_\delta$ appears in $\mu$ is
$$
\mathbbm{1}_\beta^\mu := \sum_{k=1}^d \mathbbm{1}_\beta^{\mu_k}.
$$
Furthermore, denote


\begin{equation}\label{eq:1abi}
\mathbbm{1}_i^\mu
:= \sum_{\beta \in T^g_\delta, i \in \beta}
\mathbbm{1}^\mu_\beta
= \sum_{\beta \in T^g_\delta} \mathbbm{1}^\mu_\beta \bmone^\beta_i
\end{equation}
as the number of integers $i$ appearing in all the $\delta$-tuples in $\alpha$.



\subsection{Main results on the general Waring decomposition}
\ \ \ \
Similar to Section 2, we first state a compatibility
condition which is necessary for the existence of a generalized NC Waring decomposition . We then prove that, if this condition holds, then we can reduce the generalized NC Waring problem to a commutative one at the price of an increase our number of variables.



\subsubsection{The Compatibility Condition}
\ \ \ \
The generalized version of the $\delta = 1$ compatibility condition is defined as follows:
\begin{defi}
A noncommutative homogeneous polynomial of degree $\delta d$ in g variables of the form

\begin{equation} \label{eq:ncPoly}
p(x) = \sum_{\alpha \in {T^g_{\delta d} }} {P_\alpha x^\alpha} \qquad P_\alpha
 \in \mathbb{R} \ or \ \mathbb{C}
\end{equation}
satisfies the \df {$\delta$-compatibility condition} means
\begin{equation} \label{eq:GeneralPaEquiv}
P_{\alpha} = P_{\tilde{\alpha}}
\end{equation}
for all index sets, $\alpha$, $\tilde{\alpha} \in {T^g_{\delta d} }$
such that $\bmone^{\tau(\alpha)}_\beta = \bmone^{\tau(\tilde \alpha) }_\beta \text{ for all }
\beta \in T^g_\delta $.
Consistent with this,
we define the \df{$\delta$-equivalence relation}, denoted $\sim_\delta$ \index{$\sim_\delta$}, on ${T^g_{\delta d} }$ by

$$
\alpha \sim_{\delta} \tilde{\alpha}
\quad
\text{iff}
\quad
\bmone^{\tau(\alpha)}_\beta  = \bmone^{\tau(\tilde \alpha) }_\beta
$$
for all $\beta \in T^g_\delta$.
\qed \end{defi}





\begin{rmk}
\label{rem:tupequiv}
\rm Here are a few bookkeeping properties of $\delta$-equivalences.

\begin{enumerate}

\item
\label{it:1EquivIsCommEquiv}
We have $\alpha \sim_1 \tilde{\alpha}$ if and only if $\alpha \sim_c \tilde{\alpha}$.

\item
\label{it:monEquivCompare}
Let $\delta_1,\delta_2 \in \mathbb{N}$ and let $\alpha,\tilde{\alpha} \in T_{\delta_2 d}^g$. If $\delta_2$ divides $\delta_1$, then $\alpha \sim_{\delta_1} \tilde{\alpha}$ implies $\alpha \sim_{\delta_2} \tilde{\alpha}$. In the case where $\delta_2=1$ this follows from equation \eqref{eq:1abi}. The general case is similar.

\item
\label{it:polyEquivCompare}
Let $\delta_1, \delta_2, d \in \mathbb{N}$ and let $p$ be a degree $\delta_1 d$ NC homogeneous polynomial. If $\delta_2$ divides $\delta_1$ and $p$ satisfies the $\delta_2$-compatibility condition then $p$ satisfies the $\delta_1$-compatibility condition.
\end{enumerate}
Items \eqref{it:monEquivCompare} and \eqref{it:polyEquivCompare} highlight that, as $\delta$ grows, it becomes increasingly difficult for fixed monomials $\alpha$ and $\tilde{\alpha}$ of degree divisible by $\delta$ to be $\delta$-equivalent. As an immediate consequence, as $\delta$ grows, it become more likely that a fixed NC homogeneous polynomial $p$ of degree divisible by $\delta$ satisfies the $\delta$-compatibility condition. In the extreme case, monomials $\alpha$ and $\tilde{\alpha}$ of degree $\delta$ are $\delta$-equivalent if and only if $\alpha=\tilde{\alpha}$. As a result, every degree $\delta$ NC homogeneous polynomial satisfies the $\delta$-compatibility condition. \qed

\end{rmk}

\begin{exa}
\rm Let
\[
\alpha=x_1 x_2 x_2 x_1 \quad \quad \quad \quad \tilde{\alpha}=x_2 x_1 x_1 x_2.
\]
Then
\[
\alpha \sim_1 \tilde{\alpha} \quad \mathrm{and} \quad  \alpha \sim_2 \tilde{\alpha} \quad  \mathrm{however} \quad  \alpha \not\sim_4 \tilde{\alpha}.
\]
Now let $p$ be the degree four homogeneous NC polynomial
\[
p(x)=\alpha+\tilde{\alpha}=x_1 x_2 x_2 x_1+x_2 x_1 x_1 x_2.
\]
Then $p$ satisfies the $2$-compatibility condition and the $4$-compatibility condition. However, $p$ does not satisfy the $1$-compatibility condition, since the coefficient of $x_1 x_1 x_2 x_2$ in $p$ is $0$ but the coefficient of $x_1 x_2 x_2 x_1$ is $1$ and
\[
x_1 x_1 x_2 x_2 \sim_1 x_1 x_2 x_2 x_1. \qed
\]
\end{exa}



 The following lemma shows that the $\delta$-compatibility condition is necessary for the general NC Waring problem.

\begin{lem}
\label{lem:condgen}
Suppose a NC homogeneous polynomial $p$ of degree
$\delta d$ in $g$ variables has a $t$-term $({\delta},d)$-NC Waring decomposition ,
 then $p$  satisfies the $\delta$-compatibility condition,
 $P_{\alpha} = P_{\widetilde \alpha}$  if ${\alpha} \sim_\delta {\widetilde \alpha}$.
 Here $p$ has  coefficients  $P_{\alpha}$.

Moreover, the $({\delta},d)$-NC
 Waring problem  has a
solution over the complex numbers (resp. real numbers) if and only if the equation
\begin{equation} \label {eq:pcoef}
P_\alpha = \sum_{s=1}^t \prod_{\beta \in T^g_\delta}
\left (A^s_\beta \right)^{\bmone^{\tau(\alpha)}_\beta}
\qquad {\alpha} \in T_{{\delta} d}^g
\end{equation}
has a solution $A_\beta^s \in \mathbbm{C}$ (resp. $A_\beta^s \in \mathbbm{R}$).
\end{lem}

\begin{proof}
$p$ has a $t$-term $(\delta,d)$-NC Waring decomposition \,
iff $\exists$ $\delta^{th}$ degree  homogeneous polynomials,
$H_1, H_2, \dots, H_t$ satisfying
\begin{align}
\sum_{\alpha \in {T^g_{\delta d} }} P_\alpha x^\alpha
& = \sum_{s=1}^t [H_s(x)]^d
  = \sum_{s=1}^t \left [\sum_{\beta \in T^g_\delta}
  A_{\beta}^s x^{\beta} \right ]^d\\
  %
& = \sum_{s=1}^t   \sum_{\alpha \in {T^g_{\delta d} } }
 \left( \prod_{ \substack { 1 \le j \le d}}
 A_{\tau(\alpha)_j}^s x^{\alpha_j}\right) \\
 & = \sum_{\alpha \in {T^g_{\delta d} }}
 \left( \sum_{s=1}^t \prod_{ \substack { 1 \le j \le d}}
 A_{\tau(\alpha)_j}^s \right) x^\alpha.
 \label{eq:pmain}
\end{align}
\newline
Comparing coefficients we see, equivalent to the $(\delta, d)$-NC Waring
decomposition is:
$$
P_\alpha  = \sum_{s=1}^t \prod_{ \substack {
1 \le j \le d}} A_{\tau(\alpha)_j}^s
= \sum_{s=1}^t \prod_{\substack{{j_1, \dots,j_\delta }\\
1 \le j_k \le g}}^g
\left(  A_{(j_1, \dots,j_\delta)}^s \right)^{\mathbbm{1}_{(j_1, \dots,j_\delta)}^{\tau(\alpha)}}
= \sum_{s=1}^t \prod_{\beta \in T^g_\delta} \left (A^s_\beta \right)^{\bmone^{\tau(\alpha)}_\beta},
$$
yielding \eqref{eq:pcoef}.

As a consequence
$
P_\alpha = P_{\tilde{\alpha}}
$
for any
$\alpha$
satisfying
$\bmone^{\tau(\alpha)}_\beta = \bmone^{\tau(\tilde \alpha) }_\beta$
for every
$
\beta \in T^g_\delta
$, yielding the first assertion of the theorem.
\end{proof}


\begin{exa}
\rm
Let
$$
    p(x) = (x_1x_2 + x_1^2)(x_2x_1 + x_1^2)
      = x_1x_2^2x_1 + x_1x_2x_1^2 + x_1^2x_2x_1 + x_1^4.
$$
Then $p$ is an example where there is no $({\delta},d)=(2,2)$-NC
Waring decomposition; indeed
the $2$-compatibility condition is violated because
$
P_{(1,1,1,2)} = 0 \neq 1 = P_{(1,2,1,1)}
$.
However, its commutative collapse does have the Waring decomposition :
\begin{equation*}
    p^c(X)=X_1^2X_2^2 + 2 X_1^3 X_2 + X_1^4
          = (X_1X_2 + X_1^2)^2.  \qquad \qed
\end{equation*}

\end{exa}


\subsection{Reduction to classical Waring in more variables}
\label{sec:GenWaringReduction}
\ \ \ \

To solve the general $(\delta,d)$-noncommutative \  Waring  problem we reduce to the  $\delta=1$ case solved by Theorem \ref{thm:LinearWaring}.
This reduction is accomplished by identifying a monomial $x^\beta$
with a new variable $z_\beta$. Namely, fix $\delta$ and define the map $\phi$ on monomials of the form $x^\beta$ for $\beta \in T_\delta^g$ by
$$
\phi (x^\beta) := z_\beta \qquad for \ each \ \beta \in T_\delta^g
$$
where the $z_\beta$ are noncommutative indeterminates indexed by elements of $T_\delta^g$.

We extend or definition of $\phi$ to a noncommutative homogeneous polynomial
\[
p(x)=\sum_{\mu \in (T_\delta^g)d} P_\mu x^{\mu_1} x^{\mu_2} \cdots x^{\mu_d}
\]
 of degree $\delta d$
 by
\begin{equation}
\label{eq:phiOnPolys}
\phi(p(x))=\sum_{\mu \in (T_\delta^g)d} P_\mu \phi(x^{\mu_1}) \phi(x^{\mu_2}) \cdots \phi(x^{\mu_d})=\sum_{\mu \in (T_\delta^g)d} P_\mu z_{\mu_1} z_{\mu_2}  \cdots z_{\mu_d}.
\end{equation}

\begin{lem}
\label{lem:phiAlgIso}
The map $\phi$ as defined in equation \eqref{eq:phiOnPolys} defines an algebra isomorphism on the algebra of noncommutative homogeneous polynomials of degree divisible by $\delta$ in the noncommutative indeterminate $x=(x_1,x_2, \dots, x_g)$ which maps to the algebra of noncommutative homogeneous polynomials in the noncommutative indeterminates $\{z_\beta\}_{\beta \in T_\delta^g}$.
\end{lem}
\begin{proof}
This is straight forward from the definition of $\phi$ on a noncommutative homogeneous polynomial of degree $d\delta$.
\end{proof}

We now give our main result for the $(\delta,d)$-NC Waring problem.

\begin{prop}
\label{prop:GenNCWaringMain}
Let $p$ be a noncommutative homogeneous polynomial of degree $\delta d$ in the indeterminate $x=(x_1, \dots, x_g)$, and let $\phi$ be as defined in equation \eqref{eq:phiOnPolys}. Then we have the following.
\begin{enumerate}
\item
\label{it:GenMain1}
$p(x)$ has a $t$-term  $({\delta},d)$-noncommutative \  Waring decomposition if and only if
$\phi(p(x))$ has a $t$-term $(1,d)$-noncommutative Waring decomposition.

\item
\label{it:GenMain2}
$p(x)$ satisfies the ${\delta}$-compatibility condition if and only if $\phi(p(x))$ satisfies the  $1$-compatibility condition.

\item
\label{it:GenMain3}
$p(x)$ has a $t$-term  $({\delta},d)$-noncommutative \  Waring decomposition if and only if $p(x)$ satisfies the ${\delta}$-compatibility condition  and the commutative collapse of $\phi(p(x))$ has a $t$-term $(1,d)$-Waring decomposition.
\end{enumerate}
\end{prop}
\begin{proof}
To prove item \eqref{it:GenMain1}, assume $p(x)$ has a $t$-term $(\delta,d)$-noncommutative Waring decomposition
\[
p(x)= \sum_{s=1}^t  [\sum_{\beta \in T_{\delta}^g } A_\beta \; x^\beta  ]^d.
\]
By Lemma \ref{lem:phiAlgIso}, $\phi$ is an algebra isomorphism so
\[
\phi(p(x))=\phi\left(\sum_{s=1}^t  [\sum_{\beta \in T_{\delta}^g } A_\beta \; x^\beta  ]^d \right) = \sum_{s=1}^t  [\sum_{\beta \in T_{\delta}^g } A_\beta \; \phi(x^\beta)  ]^d = \sum_{s=1}^t  [\sum_{\beta \in T_{\delta}^g } A_\beta \; z_\beta  ]^d.
\]
This shows $\phi(p(x))$ has a $t$-term $(1,d)$ noncommutative Waring decomposition. The reverse direction is follows the same reasoning using $\phi^{-1}$ instead of $\phi$.

To prove item \eqref{it:GenMain2} let
\[
p(x)=\sum_{\mu \in (T_\delta^g)d} P_\mu x^{\mu_1} x^{\mu_2} \cdots x^{mu_d}.
\]
Then
\[
\phi(p(x))=\sum_{\mu \in (T_\delta^g)d} P_\mu z_{\mu_1} z_{\mu_2}  \cdots z_{\mu_d}.
\]
Observe
\[
(\mu_1, \dots, \mu_d) \sim_1 (\tilde \mu_1, \dots \tilde \mu_d)
\]
where the $\mu_j$ are viewed as elements of the index set $T_\delta^g$ if and only if
\[
(\mu_1, \dots, \mu_d) \sim_{\delta} (\tilde \mu_1, \dots \tilde \mu_d)
\]
where the $\mu_j$ are viewed as as $\delta$ tuples of elements of $T_{\delta}^g$. It follows that
\[
P_{(\mu_1, \dots, \mu_d)}=P_{(\tilde \mu_1, \dots \tilde \mu_d)} \quad \quad \mathrm{for\ all\ } (\mu_1, \dots, \mu_d) \sim_1 (\tilde \mu_1, \dots \tilde \mu_d).
\]
where the $\mu_j$ are viewed as elements of the index set $T_\delta^g$ if and only if
\[
P_{(\mu_1, \dots, \mu_d)}=P_{(\tilde \mu_1, \dots \tilde \mu_d)} \quad \quad \mathrm{for\ all\ } (\mu_1, \dots, \mu_d) \sim_{\delta} (\tilde \mu_1, \dots \tilde \mu_d).
\]
where the $\mu_j$ are viewed as as $\delta$ tuples of elements of $T_{\delta}^g$.


Item \eqref{it:GenMain3} is an immediate consequence of items \eqref{it:GenMain1} and \eqref{it:GenMain2} with Theorem \ref{thm:LinearWaring}, our main result for $(1,d)$-NC  Waring decompositions.
\end{proof}

\subsection{Additional variables are necessary for the reduction}
\label{sec:NeedExtraVars}
\ \ \ \
It is tempting to try to solve the general $({\delta},d)$-NC Waring problem by reducing to the commutative case without introducing additional variables. This section will show that this is not possible.

One may hope that the following are true:

\begin{enumerate}
\item
\label{it:comm_WR_general}
\textit{If $p$ is a degree $\delta d$ NC homogeneous polynomial, which satisfies the $\delta$-compatibility condition \eqref{eq:GeneralPaEquiv},
then its commutative collapse $p^c$ has the Waring decomposition \
\begin{equation} \label{comm_WR_general}
p^c(X) = \sum_{s = 1}^t \left ( \sum_{\beta \in T^g_\delta} A^s_{\beta} X^{\beta} \right )^d
\end{equation}
(with $X_i$ being commuting variables) if and only if $p$ has the
NC Waring decomposition \
\begin{equation} \label{nc_WR_general}
p(x)=\sum_{s=1}^t \left ( \sum_{\beta \in T^g_\delta} A^s_{\beta} x^{\beta} \right )^d.
\end{equation}
}

\item
\label{it:nc_WR_general}
\textit{The commutative collapse $p^c$ of $p$
has a $t$-term  $({\delta},d)$-NC Waring decomposition
iff
the commutative collapse
$\phi(p)^c$ of $\phi(p)$ has a $t$-term
$(1,d)$-NC Waring decomposition.}

\end{enumerate}

The following polynomial gives a counter example to both items. Let
\[
p(x)=x_1^4+x_1 x_2 x_2 x_1 + x_2 x_1 x_1 x_2 +x_2^4
\]
and let $\delta=d=2$. Then $p$ satisfies the $2$-compatibility condition. We will show that the commutative collapse of $p$ has a two term $(2,2)$-Waring decomposition \  but that $p$ does not have a two term $(2,2)$-NC  Waring decomposition.

It is straight forward to check
\[
p^c(X)=X_1^4+2X_1^2 X_2^2 +X_2^4=(X_1^2+X_2^2)^2.
\]
Item \eqref{it:comm_WR_general} would imply that
\[
p(x)=(x_1^2+x_2^2)^2=x_1^4+x_1^2 x_2^2+x_2^2 x_1^2 +x_2^4 \neq x_1^4+x_1 x_2 x_2 x_1 + x_2 x_1 x_1 x_2 +x_2^4 = p(x)
\]
which is contradiction. This shows that item \eqref{it:comm_WR_general} cannot be correct.

In fact, $p$ does not have a two term $(2,2)$-NC  Waring decomposition. To check this set
\[
z_{(1,1)}=x_1 x_1 \quad \quad z_{(1,2)}= x_1 x_2 \quad \quad z_{(2,1)}=x_2 x_1 \quad \quad z_{(2,2)}=x_2 x_2.
\]
Then $\phi(p) (z)=z_{(1,1)}^2+z_{(1,2)} z_{(2,1)} +z_{(2,1)} z_{(1,2)} +z_{(2,2)}^2$ satisfies the $1$-compatibility condition but
\[
(\phi(p))^c (Z)= Z_{(1,1)}^2+ 2 Z_{(1,2)} Z_{(2,1)} + Z_{(2,2)} ^2
\]
does not have a two term $(1,2)$-Waring decomposition.\footnote{This is a straight forward calculation.}
It follows from Proposition \ref{prop:GenNCWaringMain} \eqref{it:GenMain3} that $p$ does not have a two term $(2,2)$-NC Waring decomposition.


2019-03-15T01:15:45.000
1903
1903.05910
en
https://arxiv.org/abs/1903.05910
This paper analyses a Waring type decomposition of a noncommuting (NC) polynomial $p$ with respect to the goal of evaluating $p$ efficiently on tuples of matrices. Such a decomposition can reduce the number of matrix multiplications needed to evaluate a noncommutative polynomial and is valuable when a single polynomial must be evaluated on many matrix tuples.In pursuit of this goal we examine a noncommutative analog of the classical Waring problem and various related decompositions. For example, we consider a "Waring decomposition" in which each product of linear terms is actually a power of a single linear NC polynomial or more generally a power of a homogeneous NC polynomial. We describe how NC polynomials compare to commutative ones with regard to these decompositions, describe a method for computing the NC decompositions and compare the effect of various decompositions on the speed of evaluation of generic NC polynomials.
Functional Analysis (math.FA)
Efficient evaluation of noncommutative polynomials using tensor and noncommutative Waring decompositions
Qwen/Qwen-72B
1. YES
2. YES