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

(Answer for the case $$n=2$$)

Put $$s = \dim \mathbb{C}[x, y]_d$$ and let $$0 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 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. 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 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 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.

• Great answer but here are a few comments: the "anti-lexicographic" order seems not to have been used (at least there is no need to define a sum or a product. Maybe to choose an (ordered) basis before writing an explicit matrix?). In the same paragraph $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}$ should simply be $L_i= \sum \binom{d}{r_1, r_2, \cdots, r_n} \prod_{j=1}^{n} (a_j^{m_j} x_j)^{r_j}$ and finally I do not get the business with $\prod_{j=1}^{n} x_j^{n_j} < \prod_{j=1}^{n} x_j^{r_j}$. Do we evaluate at some precise $(x_1, ... ,x_n)$ Jan 23 '20 at 16:08
• and anyway it seems again not to be used afterwards Jan 23 '20 at 16:10
• @Noix07 I agree that the proof could be done without the monomial order. It was intended to show all $i_1, i_2, \dots, i_s$ are distinct, i.e. $\sum m_j r_j$ are all distinct. Otherwise the determinant of $A$ turns to be zero. Jan 24 '20 at 6:29

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.