Theme and variations: the Newton-Girard identities

Time for another gemstone from symmetric function theory! (I am studying for my Ph.D. qualifying exam at the moment, and as a consequence, the next several posts will feature yet more gemstones from symmetric function theory. You can refer back to this post for the basic definitions.)

Start with a polynomial p(x) that factors as

p(x)=(x-\alpha_1)(x-\alpha_2)\cdots(x-\alpha_n).

The coefficients of p(x) are symmetric functions in \alpha_1,\ldots,\alpha_n – in fact, they are, up to sign, the elementary symmetric functions in \alpha_1,\ldots,\alpha_n.

In particular, if e_i denotes \sum_{j_1<\cdots<j_i} \alpha_{j_1}\alpha_{j_2}\cdots\alpha_{j_i}, then

p(x)=x^n-e_1x^{n-1}+e_{2}x^{n-2}-\cdots+(-1)^n e_n.

(These coefficients are sometimes referred to as Vieta’s Formulas.)

Since p(\alpha_i)=0 for all i, we can actually turn the equation above into a symmetric function identity by plugging in \alpha_1,\ldots,\alpha_n:

\alpha_1^n-e_1\alpha_1^{n-1}+e_{2}\alpha_1^{n-2}-\cdots+(-1)^n e_n=0
\alpha_2^n-e_1\alpha_2^{n-1}+e_{2}\alpha_2^{n-2}-\cdots+(-1)^n e_n=0
\vdots

and then summing these equations:

(\alpha_1^n+\cdots+\alpha_n^n)-e_1(\alpha_1^{n-1}+\cdots+\alpha_n^{n-1})+\cdots+(-1)^n\cdot ne_n=0

…and we have stumbled across another important basis of the symmetric functions, the power sum symmetric functions. Defining p_i=\alpha_1^i+\cdots+\alpha_n^i, every symmetric function in \{\alpha_j\} can be uniquely expressed as a linear combination of products of these p_i`s (we write p_\lambda=p_{\lambda_1}p_{\lambda_2}\cdots p_{\lambda_n}.)

So, we have

p_n-e_1p_{n-1}+e_2 p_{n-2}-\cdots+(-1)^n\cdot ne_n=0.

This is called the nth Newton-Girard identity, and it gives us a recursive way of expressing the p`s in terms of the e`s.

Well, almost. We have so far only shown that this identity holds when dealing with n variables. However, we can plug in any number of zeros for the \alpha_i`s to see that the identity also holds for any number of variables k<n. And, if we had more than n variables, we can compare coefficients of each monomial individually, which only can involve at most n of the variables at a time since the equation is homogeneous of degree n. Setting the rest of the variables equal to zero for each such monomial will do the trick.

So now we have it! The Newton-Girard identities allow us to recursively solve for p_n in terms of the e_i`s. Wikipedia does this nicely and explains the computation, and the result is:

p_n=\det\left(\begin{array}{cccccc}     e_1        & 1       & 0       & 0        &\cdots & 0 \\    2e_2       & e_1     & 1       & 0        & \cdots & 0 \\    3e_3       & e_2     & e_1     &  1       & \cdots & 0 \\    \vdots    & \vdots & \vdots  & \vdots &  \ddots & \vdots \\  (n-1)e_{n-1} & e_{n-2} & e_{n-3} &  e_{n-4}  & \ddots & 1  \\    ne_n       & e_{n-1} & e_{n-2} &  e_{n-3}   & \cdots & e_1   \end{array}\right)

For instance, this gives us p_2=e_1^2-2e_2, which is true:

x^2+y^2+z^2=(x+y+z)^2-2(xy+yz+zx).

The Wikipedia page derives a similar identity for expressing the e`s in terms of the p`s. It also does the same for expressing the complete homogeneous symmetric functions h_n in terms of the p`s and vice versa. However, it does not explicitly express the e`s in terms of the h`s or vice versa. In the name of completeness of the Internet, let’s treat these here.

Fix some number of variables x_1,\ldots,x_n. For any d, define h_d to be the sum of all monomials of degree d in x_1,\ldots,x_n. This is clearly symmetric, and we define

h_\lambda = h_{\lambda_1}h_{\lambda_2}\cdots h_{\lambda_k}

for any partition \lambda, as we did for the elementary symmetric functions last week. The h_\lambda`s, called the complete homogeneous symmetric functions, form a basis for the space of symmetric functions.

It’s a fun exercise to derive the following generating function identities for e_n and h_n:

H(t)=\sum_n h_n t^n = \prod_{i=1}^n \frac{1}{1-x_i t}
E(t)=\sum_n e_n t^n = \prod_{i=1}^n (1+x_i t)

(The first requires expanding out each factor as a geometric series, and then comparing coefficients. Try it!)

From these, we notice that H(t)E(-t)=1, and by multiplying the generating functions together and comparing coefficients, we find the identities

h_n=h_{n-1}e_1-h_{n-2}e_2+\cdots+(-1)^{n-1}e_n

Just as before, this gives us a recursion for h_n in terms of the e_i`s. With a bit of straightforward algebra, involving Cramer’s Rule, we can solve for h_n:

h_n=\det\left(\begin{array}{cccccc}     e_1        & 1       & 0       & 0        &\cdots & 0 \\    e_2       & e_1     & 1       & 0        & \cdots & 0 \\    e_3       & e_2     & e_1     &  1       & \cdots & 0 \\    \vdots    & \vdots & \vdots  & \vdots &  \ddots & \vdots \\    e_{n-1} & e_{n-2} & e_{n-3} &  e_{n-4}  & \ddots & 1  \\    e_n       & e_{n-1} & e_{n-2} &  e_{n-3}   & \cdots & e_1   \end{array}\right)

We can also use the same equations to solve for e_n in terms of h_n:

e_n=\det \left(\begin{array}{cccccc}     h_1       & 1       & 0       & 0        &\cdots & 0 \\    h_2       & h_1     & 1       & 0        & \cdots & 0 \\    h_3       & h_2     & h_1     &  1       & \cdots & 0 \\    \vdots   & \vdots & \vdots  & \vdots &  \ddots & \vdots \\    h_{n-1}   & h_{n-2} & h_{n-3} &  h_{n-4}  & \ddots & 1  \\    h_n       & h_{n-1} & h_{n-2} &  h_{n-3}   & \cdots & h_1   \end{array}\right)

I find these two formulas to be more aesthetically appealing than the standard Newton-Gerard formulas between the p_n`s and e_n`s, since they lack the pesky integer coefficients that appear in the first column of the matrix in the p-to-e case. While perhaps not as mainstream, they are gemstones in their own right, and deserve a day to shine.

Advertisements

About mariamonks

I am currently a graduate student in mathematics at UC Berkeley.
This entry was posted in Obsidian, Uncategorized. Bookmark the permalink.

2 Responses to Theme and variations: the Newton-Girard identities

  1. Pingback: The hidden basis | Finding Gemstones

  2. Pingback: A bridge between two worlds: the Frobenius map | Finding Gemstones

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s