Write a homogeneous polynomial of degree $d$ as a sum of $d$-th power of linear polynomials I learned that the Warning rank of a homogeneous polynomial $h\in \mathbb{C}[x_1, \cdots, x_n]_d$ of degree $d$ is defined by the smallest
number of summands such that $h$ can be expressed as a sum of $d$-th powers of linear polynomials. For example, $XY=(\frac{X}{2}+\frac{Y}{2})^2+(i\frac{X}{2}-i\frac{Y}{2})^2$ so the Warning rank of $XY$ is $2$.
But how do we know that any homogeneous polynomial of degree $d$ can be writte as a sum of $d$-th powers of linear polynomials? I read a proof for the case of elementary symmetric polynomials, but I have no idea how to get the generalized result for arbitrary homogeneous polynomials.
I know that the dimension of $\mathbb{C}[x_1, \cdots, x_n]_d$ is $\binom{n+d-1}{d}$. I tried to find $\binom{n+d-1}{d}$ linearly independent polynomials each of which is a $d$-th power of a linear polynomial, but there is no progress so far.
 A: (Answer for the case $n=2$)
Put $ s = \dim \mathbb{C}[x, y]_d$ and let $0<a_1 < a_2 < \cdots < a_s$ be positive real numbers. Consider $L_i=(x+a_i y)^d$ for $1 \leq i \leq  s$. We can show that $L_1, \cdots, L_s$ are linearly independent, as follows.
Observe that $L_i = \sum_{r=0}^d \binom{d}{r} a_i^r x^{d-r} y^r$. So it sufficient to show that determinant of the following matrix is nonzero: (Note that here $s=d+1$)
\begin{bmatrix}
1 & \binom{d}{1}a_1 & \binom{d}{2}a_1^2 & \cdots & \binom{d}{d}a_1^d \\
1 & \binom{d}{1}a_2 & \binom{d}{2}a_2^2 & \cdots & \binom{d}{d}a_2^d \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & \binom{d}{1}a_s & \binom{d}{2}a_s^2 & \cdots & \binom{d}{d}a_s^d 
\end{bmatrix}
The determinant is given by $ (\det A)  \prod_{r=0}^d \binom{d}{r} $, where $A= \left( a_i^{j-1} \right)_{ij}$ is the Vandermonde matrix. Since the Vandermonde determinant is given by $\prod_{1 \leq i < j \leq s } (a_j-a_i) \neq 0$, we are done.

(Answer for the general case)
Let $s = \dim \mathbb{C}[x_1, \cdots, x_n]_d$ and $0<a_1 < a_2 < \cdots < a_s$ be positive real numbers. Choose positive integers $m_1, \cdots, m_n$ such that $m_j > s(m_{j-1}+\cdots+m_1)$ for all $1<j\leq n$. Define $L_i = \left( \sum_{j=1}^{n} a_j^{m_j} x_j \right)^d$ for $1\leq i \leq s$. We will show $L_1, \cdots, L_s$ are linearly independent by calculating determinant as follows:
First, give an anti-lexicographical order on the set of all monomials $\mathfrak{B}=\{\prod_{j=1}^{n} x_j^{r_j} \mid \sum r_j = d \}$, a basis for $\mathbb{C}[x_1, \cdots, x_n]_d$. Observe that $L_i= \sum \binom{d}{r_1, r_2, \cdots, r_n} a_i^{\sum_{j=1}^{n}m_j r_j} \prod_{j=1}^{n} x_j^{r_j}$, where the indices run over all nonnegative integers $r_1, \cdots, r_n$ such that $r_1 + \cdots + r_n = d$. Here $\prod_{j=1}^{n} x_j^{n_j} < \prod_{j=1}^{n} x_j^{r_j}$ implies $\sum_{j=1}^{n} m_j n_j < \sum_{j=1}^{n} m_j r_j$, by our choice of $m_1, \cdots, m_n$.
Now it suffices to show that determinant of the following matrix $A$ is nonzero. Note that multinomial coefficients can be ignored and the order of columns can be changed since the determinant is alternating multilinear in the columns.
$$A=
\begin{bmatrix}
a_1^{i_1} & a_1^{i_2} & a_1^{i_3} & \cdots & a_1^{i_s} \\
a_2^{i_1} & a_2^{i_2} & a_2^{i_3} & \cdots & a_2^{i_s} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_s^{i_1} & a_s^{i_2} & a_s^{i_3} & \cdots & a_s^{i_s} 
\end{bmatrix}
$$
Here $i_1>i_2 > \cdots > i_s$ are positive integers.
By the bialternant formula, $ \det A = s_\lambda(a_1, \cdots, a_s)\prod_{1\leq j<k\leq s} (a_j-a_k)$ holds, where $s_\lambda(x_1, \cdots, x_s)$ is the Schur polynomial associated to the partition $\lambda = (\lambda_1, \cdots, \lambda_s)$ with $\lambda_j = i_j - (s-j)$. Recall that the Schur polynomial is defined by the sum of monomials,
$$s_\lambda (x_1, \cdots, x_s) = \sum_T x^T = \sum_T x_1^{t_1} \cdots x_s^{t_s}$$
where the summation is over all semistandard Young tableaux $T$ of shape $λ$. The exponents $t_1, \cdots , t_s$ give the weight of $T$, in other words each $t_i$ counts the occurrences of the number $i$ in $T$.
Since $a_1, \cdots, a_s$ are distinct positive real numbers, $s_\lambda(a_1, \cdots, a_s) \neq 0$. Therefore, $ \det A = s_\lambda(a_1, \cdots, a_s)\prod_{1\leq j<k\leq s} (a_j-a_k)$ is nonzero. Hence the claim follows.

Alternatively, we can prove the result by induction; the method is essentially same to the case $n=2$, as suggested in the exercise 23.5 in Introduction to Lie algebras and Representation Theory written by J.Humphreys. For details, see this answer.
A: There is a rather straightforward and constructive argument that shows, for any field F of characteristic zero, the existence of a finite subset $S$ of $F^d$ with exactly $N:=\binom{n+d-1}{d}$ points with the property that the $F$-linear hull of the $N$ polynomials $(s_1 x_1 + \cdots + x_n s_n)^d$ with $(s_1,\ldots,s_n) \in S$ coincides with $F[x_1,\ldots,x_n]_{d}$ - the space of all $n$-variate homogeneous polynomials of degree $d$. Taking $F = \mathbb{C}$, one obtains the finiteness of the Waring rank for polynomials with complex coefficients.
Pick $S$ to be a set, for which there exists a system of polynomials $(p_s)_{s \in S}$ with $p_s \in F[x_1,\ldots,x_n]_{d}$ satisfying $p_s(t) = \delta_{s,t}$ for all $s, t \in S$, where $\delta_{s,t}$ is the Kronecker delta. That's a multivariate version of the Lagrange basis for the polynomial interpolation with the set of nodes $S$. Such a system of polynomials exists if $S$ is chosen generically in the algebraic sense, but there are also concrete choices that would work, like  $S = \{ (s_1,\ldots,s_n) \in \mathbb{Z}_{\ge 0}^n \,:\, s_1 + \cdots + s_n = d \}$.
The map $f \mapsto (f(s))_{s \in S}$, which takes $f$ and provides values of $f$ on $S$, is a linear bijection from $F[x_1,\ldots,x_n]_d$ to $F^N$. To see this, note that it acts between spaces of the same dimension and that it is surjective (as its application to polynomials $p_s$ with $s \in S$ gives all standard unit vectors of $F^N$). Having observed this, one sees that the identity
$$
f = \sum_{s \in S} f(s) p_s. 
$$
is true for every $f \in F[x_1,\ldots,x_n]_d$, since the evaluation of the left and the right hand side on each point of $S$ gives the same value.
One can write the latter identity in the coefficient-wise form:
$$
f_\alpha  = \sum_{s \in S} f(s) p_{s,\alpha}, \qquad (\ast)
$$
where $\alpha = (\alpha_1,\ldots,\alpha_n)$ is an exponent vector of the monomial $x^\alpha := x_1^{\alpha_1} \cdots x_n^{\alpha_n}$, while $f_\alpha$ and $p_{s,\alpha}$ are coefficients of $f$ and $p_{s}$, respectively, for this monomial.
Now, consider the polynomial
$$
   g(u,x) := (u_1 x_1 + \cdots + u_n x_n)^d \in F[u_1,\ldots,u_n,x_1,\ldots,x_n]
$$
depending on $u=(u_1,\ldots,u_n)$ and $x=(x_1,\ldots,x_n)$. By the multinomial theorem,
$$
 g(u,x) = \sum_{\alpha \in \mathbb{Z}_{\ge 0}^n \, : \, |\alpha|=d} \binom{d}{\alpha} u^\alpha x^\alpha. 
$$
With respect to the variables $u$, the polynomial $g(u,x)$ has the coefficient $\binom{d}{\alpha} x^\alpha$ for the monomial $u^\alpha$. Applying $(\ast)$ to $g$ as a polynomial in the variables $u$, one arrives at
$$
   \binom{d}{\alpha} x^\alpha  = \sum_{s \in S} g(s,x) p_{s,\alpha}
 = \sum_{(s_1,\ldots,s_n) \in S} (s_1 x_1 + \cdots + s_n x_n)^d p_{s,\alpha}. 
$$
This shows that every monomial $x^\alpha$ of degree $d$ is in the $F$-linear hull of the polynomials $(s_1 x_1 + \cdots + s_n x_n)^d$ with $(s_1,\ldots,s_n) \in S$. Consequently, the $F$-vector space $F[x_1,\ldots,x_n]_d$ is the $F$-linear hull of all $(s_1 x_1 + \cdots + s_n x_n)^d$ with $(s_1,\ldots,s_n) \in S$.
A: This is too long to be a comment, but is also not a complete solution.
If you fix a monomial order such that the monomials are well ordered (which happens, for example, in lexicographic ordering, although since you are dealing with homogeneous polynomials, you will only have a finite number of monomials of degree d, so this isn't exactly necessary, but it would be for some similar problems), then it suffices to show that you can find a linear combination of $d$th powers of a linear polynomials that has the same leading term as your polynomial.  Subtracting off those powers, you will then have a polynomial with a smaller leading term to consider.  Because the set of monomials of degree $d$ is well ordered, this process has to end after a finite number of steps.
From here, it suffices to find a linear combinations of $d$th powers of linear whose leading term is the desired leading term. I don't immediately see how to do this, but this at least reduces the problem to something slightly more manageable.
For example, if $x>y$, then the monomials of degree $2$ are ordered $x^2>xy>y^2$, and suppose we have $ax^2+bxy+cy^2$.  First, we subtract off a multiple of $x^2$ and we have something whose leading monomial is $xy$.  Then we subtract off a multiple of $(x+y)^2+(ix)^2=2xy+y^2$ and we will be left with something whose leading monomial is (less than or equal to) $y^2$.
So we don't need to be able to produce a linear combination of $d$th powers equal to every given monomial, just having a given leading monomial.  
For polynomials where the leading term is larger that all of its symmetries (e.g., $x^2y > xy^2$), you could use your result on symmetric polynomials.  For other monomials, I do not have an immediate answer.  If I think of one, I will update this answer.
