Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
How would you use Vita to calculate the polynomials? Vita mixes them all up.. – Thomas Ahle Dec 14 '14 at 18:43

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|cite|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
How fast is this then? After expanding the $(x_1-\triangle)^{i-1}$ don't you still have to do $O(n^2)$ work? – Thomas Ahle Dec 14 '14 at 18:51

You can use Newton-Girard formulae. The elementary symmetric polynomial have representation as determinants: $$ p_k(x_1,\ldots,x_n)=\sum_{i=1}^nx_i^k = x_1^k+\cdots+x_n^k \\ e_2(x_1,\ldots,x_n)=\sum_{1 \leq i_1<i_2<...<i_k\leq n}x_{i_1}x_{i_2}\cdots x_{i_k} $$ $$ 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|cite|improve this answer
Do you also have a fast way of computing those determinants? The raw method takes O(n^2.4) operations. I suppose the near symmetry might help? or maybe not? Perhaps it can play into some sampling/approximation algorithm... – Thomas Ahle Dec 14 '14 at 18:37
@Thomas, a lower Hessenberg matrix like the one in this answer can be decomposed in $O(n^2)$ operations; the determinant is then easily obtained from the triangular factor. Have a look at "Hyman's method", for instance. – J. M. Mar 13 at 9:21

A simple divide-and-conquer recursion looks like it comes in at $O(nk)$, just like the recurrence given by @BenKuhn. Split the variables into two halves, and inductively compute $\sigma_{n/2}^j$ for $j=0,\ldots,k$ evaluated on both halves. Iterate $r$ times, where $n\approx 2^r k$; the total work required is $2^r$ evaluations of $\{\sigma_k^j\mid 0\le j\le k\}$. But each of these sets can be done in $O(k^2)$ work using Vieta, so the total work is $O(2^r k^2)=O(nk)$.

It's probably worth remarking that you can evaluate $\sigma_n^{n-k}$ by evaluating $\sigma_n^k$ on the reciprocals of the variables. So you're in good shape if $k$ is either very small, or nearly $n$.

share|cite|improve this answer

There's a dynamic programming algorithm that is $O(nk)$ using a recurrence relation. If we define $S_n^k = \sigma_n^k(x_1, \dots, x_n)$, then we have $$S_n^k = S_{n-1}^k + x_n S_{n-1}^{k-1}$$ which allows one to compute $S_n^k$ by filling an $n \times k$ matrix, where (almost) every cell takes constant time to fill.

(The base case is of course $S_n^0 = 1$ for all $n$ and $S_n^k = 0$ for all $n$ and $k \neq 0$.)

share|cite|improve this answer

Your Answer


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.