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'm trying to prove that if we have the elementary symmetric polynomials that the following identity holds:(where $x = (x_1,..,x_n)$ is a vector of n variables) $$\sum_{k=0}^n e_k(x)^2 = x_1\cdots x_n \sum_{j=0}^{\lfloor n/2 \rfloor} {2j \choose j} e_{n-2j}(x_1+1/x_1,\cdots x_n+1/x_n).$$ I'm trying to prove this combinatorially, but I'm stuck so I'd love some hints or tips.

Update: I guess we can get some interpretation with strictly increasing functions, but that thought isn't fully developed yet.

share|improve this question
1  
Do you have combinatorial interpretations for either of the two sides? –  Qiaochu Yuan Jan 31 '11 at 23:23
    
Not really , no –  Dedalus Jan 31 '11 at 23:29
    
I have vague conceptions, but not really anything rigorous. –  Dedalus Jan 31 '11 at 23:32
    
And I have the most problems with the RHS, the LHS I think I could get something of. –  Dedalus Feb 1 '11 at 8:45
    
Here are some thoughts. First try the case where the x_i are all equal to 1. Then try the case where the x_i are all equal to the same variable, say t. –  Qiaochu Yuan Feb 1 '11 at 16:24

3 Answers 3

up vote 3 down vote accepted
+100

Consider the following experiment. There are $n$ boxes, with two identical coins each. We pick some $k \in \{0,\ldots,n\}$, pick $k$ coins from different boxes $A$, and then again pick $k$ coins from different boxes $B$. The left-hand side is exactly the generating function of all possible outcomes.

Here is another way of performing the same experiment. First choose a number $j < n/2$; this is going to be the size of $|A \setminus B| = |B \setminus A|$. Instead of choosing the elements in $(A \setminus B) \cup (B \setminus A)$, we will choose which elements are in $A \cap B$ and which in $\overline{A \cup B}$; we have to decide on $n-2j$ elements. If we start with assuming that each element is picked once (this is the factor $x_1\cdots x_n$), then putting an element $i$ in $A \cap B$ is like multiplying by $x_i$, and putting it in $\overline{A \cup B}$ is like multiplying by $1/x_i$. We are left with $2j$ elements, $j$ of which are in $A \setminus B$ and the rest in $B \setminus A$. There are $\binom{2j}{j}$ choices for that. Writing everything out, we get the right-hand side.

share|improve this answer

let $A$ be the invertible matrix whose eigenvalues are $x_1, . . . ,x_n$. We write $e_k(A)$ for $e_k(x_1,. . ., x_n)$. The generating function of the elementary symmetric polynomials:

$det(1+sA) = \sum_{k=0}^ne_k(A)s^k$

We have:

$\sum_{k=0}^ne_k^2=(2 \pi i)^{-1}\oint \frac{1}{s}det(1+sA)det(1+s^{-1}A) ds $

Where the integration is over a closed contour encircling the origin. (The contour integral just picks the coeficient of $s^0$). Therefore:

$\sum_{k=0}^ne_k^2=(2 \pi i)^{-1}\oint \frac{1}{s} det(A) (s+s^{-1})^n det(1+ (s+s^{-1})^{-1}(A+A^{-1})) ds $

$=\sum_{k=0}(2 \pi i)^{-1}\oint \frac{1}{s} (s+s^{-1})^k e_{n-k}(A+A^{-1}) ds $

Now, the polynomial $(s+s^{-1})^k$ has an $s^0$ only if k is even. Let k = 2j, then the binomial coefficient of $s^0$ is $2j \choose j $, which gives the required result.

share|improve this answer
    
Thank you, however, I fail to see the strong combinatorial interpretation. –  Dedalus Feb 1 '11 at 13:34

Let $L$ be a a multiset whose elements are elements of $\{1,\dots,n\}$. Then the coefficient of $x^L$ (which is the product of the $x_i$ with $i\in L$, taking into account multiplicities) in $\sum_ke_k^2$ is the cardinal of the set $$X_L=\{(I,J)\in\mathcal P(\mathbf n)\times\mathcal P(\mathbf n):|I|=|J|, I\cup J=L\}.$$ Here $\mathbf n$ is the set $\{1,\dots,n\}$, $\mathcal P(\mathbf n)$ is the set of subsets of $\mathbf n$ (not multisets), and $I\cup J$ is the union taking into account multiplicities, whose result is a multiset.

Count the elements of the set $X_L$ in another way to obtain your equality.

share|improve this answer
    
This is essentially equivalent to Yuval's approach, by the way. –  Mariano Suárez-Alvarez Feb 3 '11 at 1:14

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.