Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing the "other" symmetric polynomials.

For instance (I use here the notation $\sigma_n^k$ for the $k$-th symmetric polynomial in $n$ variables), the Vieta formulae allow me to compute a bunch of symmetric polynomials all at once like so:

$$\begin{align*} &(x+t)(x+u)(x+v)(x+w)\\ &\qquad =x^4+\sigma_4^1(t,u,v,w)x^3+\sigma_4^2(t,u,v,w)x^2+\sigma_4^3(t,u,v,w)x+\sigma_4^4(t,u,v,w) \end{align*}$$

and, as I have said, $\sigma_4^1$ and $\sigma_4^4$ are trivial to compute on their own without having to resort to Vieta.

But what if I want to compute $\sigma_4^3$ only without having to compute all the other symmetric polynomials? More generally, my application involves a large-ish number of arguments, and I want to be able to compute "isolated" symmetric polynomials without having to compute all of them.

Thus, I'm looking for an algorithm for computing $\sigma_n^k$ given only $k$ and the arguments themselves, without computing the other symmetric polynomials. Are there any, or can I not do better than Vieta?

share|improve this question
add comment

2 Answers 2

Let us use the symbols $u_1, u_2, ....$, for the indeterminates $t, u, v, ...$ in the question. The computation will be given in terms of a new set of indeterminates, $x_1, x_2, ....$, whose connection to the original indeterminates is given by:

$x_j = \sum_{i=1}^{n} u_i^j$

We define the derivation operator $\Delta$ acting on the new set of indeterminates as follows:

$\Delta x_j = j x_{j+1}$

$\Delta ab = a \Delta b + b \Delta a$

Then the $i$-th elementary symmetric polynomial is given by:

$\sigma_n^i = \frac{1}{i!}(x_1-\Delta)^{i-1}x_1$

The evaluation is performed in terms of the new indeterminates, after the evaluation, the expressions of the new determinates in terms of the original indeterminates need to be substituted.

share|improve this answer
    
Apllying $i=2$ gives $\frac12 (x_1x_1 - \Delta x_1)=\frac12 (x_1x_1 - 2 x_2)$, or did I miss something...? –  draks ... Dec 23 '12 at 22:53
add comment

You can use Newton-Girard formulae. The elementary symmetric polynomial have representation as determinants: $$ e_n=\frac1{n!} \begin{vmatrix}p_1 & 1 & 0 & \cdots\\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots&& \ddots & \ddots \\ p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix} $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.