Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the standard Vandermonde $V(x_1, \ldots, x_n) = \prod_{i < j} (x_i - x_j)$. I am intersted in the calculation of the following expression for fixed $k$: $$\sum_i (x_i)^k (d/dx_i)^k V(x_1 , \ldots , x_n).$$ My guess is that it equals $c \cdot V(x_1, \ldots, x_n)$ where $c$ is an expression depending on $k$ and $n$ but not on the $x_i$'s. Is it true ? If yes, what is this constant $c$?

I think, if it is true, then it is pretty well-known. Would you be so kind to provide with the answer and/or proof and/or references? What can be the context people study it? Symmetric functions? Quantum Calogero-Moser?

share|improve this question
1  
Those question marks scare me. –  Andrej Bauer Oct 19 '11 at 6:27
    
Andrej, you checked this is wrong ? I see yours answer in my mail box, but not on forum. So I am puzzled, are you sure it is wrong. For k=1 it is right if we did not make mistake. –  Alexander Chervov Oct 19 '11 at 7:10
    
@Alexander: at first I put into Mathematica the Vandermonde matrix, I was confused. You probably received my confused answer by email while I was fixing it. –  Andrej Bauer Oct 19 '11 at 7:35

5 Answers 5

up vote 4 down vote accepted

Perhaps a little Mathematica program will help us form a conjecture. For $k \geq n$ the answer is $0$, so we list your $c$ for $k < n$, as follows:

In[1]:= V[x_] := Product[x[[i]] - x[[j]], {i,1,Length[x]},{j,1,i-1}]
In[2]:= V[x/@Range[3]]
Out[2]= (-x[1]+x[2]) (-x[1]+x[3]) (-x[2]+x[3])
In[3]:= s[k_,x_] := Sum[x[[i]]^k*D[V[x],{x[[i]],k}],{i,1,Length[x]}]
In[4]:= Table[s[k,x/@Range[n]]/V[x/@Range[n]], {n,1,6},{k,0,n-1}]//Simplify//TableForm
Out[4]//TableForm=
1
2       1                               
3       3       2                       
4       6       8       6               
5       10      20      30      24      
6       15      40      90      144     120

Each row is showing a fixed $n$, and each column a fixed $k$. The first column is easy. The second one is triangular number $n(n+1)/2$, OEIS tells me the third one is $2 {n \choose 3}$ and the fourth one $n(n+1)(n+2)(n+3)/4$. After a bit of experimentation:

In[19]:= c[n_,k_] := Product[(n-k+i),{i,0,k}]/(k+1)
In[20]:= Table[c[n,k],{n,1,6},{k,0,n-1}]//TableForm
Out[20]//TableForm=
1
2       1                               
3       3       2                       
4       6       8       6               
5       10      20      30      24      
6       15      40      90      144     120

There we have it, your constant seems to be $n (n-1) \cdots (n-k)/(1+k)$. A true combinatorist should now be able to prove that this is really so. I already believe it.

share|improve this answer
    
Great Thanks ! So if it is true it should be known. I believe should be some papers playing with such things. It is not the only calculation which I need... That is why I am interested in what people already know. –  Alexander Chervov Oct 19 '11 at 7:19
    
Denis's answer provide a derivation, then should be some simple formula like: n + n-1 + n-2 + ... + 1 = n(n-1) /2 –  Alexander Chervov Oct 19 '11 at 12:22
    
@Chernov This table matches OEIS-A111492: a(n,k) = (k-1)!C(n,k) For k > 1, a(n,k) = the number of permutations of the symmetric group S_n that are pure k-cycles. –  Tom Copeland Jun 28 '12 at 7:31

Your expression is a polynomial $V^k(x_1,\ldots,x_n)$ that is still skew-symmetric. Therefore it is divisible by $V$. In addition, $V^k$ has the same degree as $V$. Thus the quotient $V^k/V$ is a constant. Hence the answer to your question is Yes.

By looking at the coefficient of the monomial $x_1^{n-1}x_2^{n-2}\cdots x_{n-1}$, one finds the constant $$c=\sum_{r=k}^{n-1}\frac{r!}{(r-k)!}.$$

share|improve this answer
    
Thank You ! Any refrences where it might be discussed ? (Origin of the problem is this "the Harish-Chandra" map for invariant differential operators (from e.g. Etingof Ginzburg paper). I.e. obtaining Calogero as Hamiltonian reduction from D(gl_n), Vandermonde appears as volume of the group. Also it appears in matrix models by the same reason... –  Alexander Chervov Oct 19 '11 at 7:22
    
So, which one is right, Denis's formula or mine? They don't seem to be equal. –  Andrej Bauer Oct 19 '11 at 7:34
    
Good question :) I will try to check in an hour. –  Alexander Chervov Oct 19 '11 at 7:50
    
I checked Denis's answer. It seems it is correct. –  Alexander Chervov Oct 19 '11 at 9:46
    
It seems Denis's answers coincide with Yours ! I checked with WolframAlpha for several cases. It should be true in general. –  Alexander Chervov Oct 19 '11 at 12:21

Here is a direct way to obtain Denis Serre's formula: Just note that $x_i^k\frac{\partial^k}{\partial x_i^k}$ multiplies a monomial in the determinant by $\frac{r!}{(r-k)!}$ where $r$ is the power of $x_i$ in that monomial, provided that $r\geq k$. Otherwise, it acts by 0. That's all you need, since in each monomial, all powers between 1 and $n-1$ occur exactly once.

share|improve this answer

I think your guess is true, and using the formula for the derivative of a determinant, one can compute $c = (n-1)^{k-1}\prod_{j=k}^{j=n}\left(n-1 + \frac{(j-1)!}{(j-1-k)!}\right)$. The proof goes as follows: We have

$$x_m^k \frac{d^k}{dx_1^k}V = \mathrm{det}(V^m),$$ where $V_{ij}^m = x_i^{j-1}$ for $i \neq m$ and $V^m_{mj} = \frac{(j-1)!}{(j-1-k)!}x_m^j$ (this is $0$ by convention when $j < k$). Now notice that when $x_m= x_n$, $V_m$ and $V_n$ differ by an interchange of rows, and hence $det(V_m) + det(V_n) = 0$, while for $s\neq n,m$, $det(V_s) = 0$ since rows $m$ and $n$ are equal. This shows that $x_m - x_n$ is a factor of $S \triangleq \sum_{i}det(V_i)$, and hence $V$ is a factor too. By degree considerations, each of these terms is a factor with multiplicity at most $1$, and hence $S = cV$ for some constant $c$. To compute $c$, one can put in $x_i = i$ on both sides and compute. See the answer above by Denis Serre for a much simpler method to do this.

share|improve this answer

Dividing the $k$th column of the lower triangular matrix $T$ (OEIS A111492) in Andrej Bauer's answer by $(k-1)!$ for each column generates A135278 (the $f$-vectors, or face-vectors for the $n$-simplexes). Then ignoring the first column gives A104712, so $T$ acting on the column vector $(-0,d,-d^2/2!,d^3/3!,...)$ gives the Euler classes for hypersurfaces of degree $d$ in $CP^n$. (See Daniel Dugger, A Geometric Introduction to K-Theory, pg. 168.)

$T$ also has relations to the number of permutations of the symmetric group $S_n$ that are pure $k$-cycles, colored forests of "naturally-grown" trees, disposition of flags on flagpoles, the colorings of the vertices of the complete graphs $K_n$, encoded in their chromatic polynomials (see A130534), and the commutator $[log(D), x^nD^n]=d(x^nD^n)/d(xD)$ for $D=d/dx$ (cf. A238363).

Update (Apr 26 and May 20 2014):

The Vandermonde matrix $V_n$ is intimately connected to the $(n-1)$-simplex and its edge projection onto a plane, the complete graphs $K_n$. There are several definitions in use, so to be definite let

$$V_n=V_n(x_1,x_2,...,x_n) = \left[ \begin{array}{} 1 & 1 & \cdots & 1\\ x_1 & x_2 & \cdots & x_n \\ \vdots & \vdots & \ddots & \vdots\\ x^{n-1}_1 & x^{n-1}_2 & \cdots & x^{n-1}_{n}\end{array} \right]$$

and determinant

$$|V_n|=|V_n(x_1, \ldots, x_n)| = \prod_{1 \leq i < j \leq n} (x_j - x_i).$$

To obtain a generating function for the rows of $T$ from Chervov's operator, first note the action of the generalized shift/dilation operator $exp(t:xd/dx:)f(x)=f((1+t)x)$ (a generalization of $e^{td/dx}f(x)=f(x+t))$, where $(:x_i\frac{d}{dx_i}:)^n=x_i^n(\frac{d}{dx_i})^n$, i.e., the power distributes over the expressions between colons. Also let $p_k(x_1,...,x_n)$ be the power sum symmetric polynomial. Then act on $|V_n|$ with a sum of $exp(t:x_id/dx_i:)$ obtaining

$$W_n(x_1 , \ldots , x_n;t)=\sum_{k\geq0} \frac{t^k}{k!}\sum_{i=1}^{n} x_i^k \frac{d^k}{dx_i^k} |V_n|$$

$$=exp[t \cdot p.(:x_1\frac{d}{dx_1}:,...,:x_n\frac{d}{dx_n}:)]|V_n|$$

$$=\sum_{i=1}^{n}exp(t :x_i\frac{d}{dx_i}:) |V_n(x_1 , \ldots , x_n)|$$

$$= |V_n((1+t)x_1 ,x_2, \ldots , x_n)|+|V_n(x_1 ,(1+t)x_2, \ldots , x_n)|+ \ldots+|V_n(x_1 ,x_2,\ldots,(1+t) x_n)|$$

$$= [1+(1+t)+(1+t)^2+\;...+(1+t)^{n-1}]\; |V_n(x_1 , \ldots , x_n)|$$

$$= \frac{(1+t)^n-1}{t}\; |V_n(x_1 , \ldots , x_n)|.$$

Therefore, $$G_n(t)=\frac{W_n(x_1 , \ldots , x_n;t)}{|V_n(x_1 , \ldots , x_n)|}=\frac{(1+t)^n-1}{t},$$

which gives an exponential generating function for the rows of the matrix $T$ (OEIS A111492, A238363) in Bauer's guess that is in agreement with Serre's answer, and an ordinary generating function for the f-polynomials (f-vectors) of the number of k-faces of the $(n-1)$-simplex (OEIS A135278).

For example,

$$G_4(t)=\frac{(1+t)^4-1}{t}=4+6t+8 \frac{t^2}{2!}+6 \frac{t^3}{3!}=4+6t+4t^2+t^3.$$

$V_n,K_n,G_n$ are associated to the $(n−1)$-simplex, and the $3$-simplex is the tetrahedron with $4$ vertices, $6$ edges, $4$ triangles, $1$ polyhedron. (The number of factors in the product formula for $|V_n|$ is given by the number of edges of $K_n$ (OEIS A000217). See also the MO-Qs Cyclotomic Polynomials in Combinatorics and Geometric proof of the Vandermonde determinant.)

There is another expression for $G_n(t)$:

$G_n(t)=\left[ \begin{array}{} 1 & t & \frac{t^2}{2!} & \cdots & \frac{t^{n-1}}{(n-1)!}\end{array} \right]|V_n|^{-1}V_n(:x_1 \frac{d}{dx_1}:,...,:x_n \frac{d}{dx_n}:) |V_n| \left[ \begin{array}{} 1 \\ 1 \\ \; \vdots\\ 1\end{array} \right]$

since

$\left[ \begin{array}{} 1 & t & \frac{t^2}{2!} & \cdots & \frac{t^{n-1}}{(n-1)!}\end{array} \right]V_n\left[ \begin{array}{} 1 \\ 1 \\ \; \vdots\\ 1\end{array} \right]=\sum_{k<n} \frac{t^k}{k!}\sum_{i=1}^{n} x_i^k=\sum_{k<n} \frac{t^k}{k!}p_k(x_1,...,x_n),$

and when acting on a polynomial of degree $\leq (n-1)$, the finite operator sum $\sum_{k<n} \frac{t^k}{k!}p_k(:x_1d/dx_1:,...,:x_nd/dx_n:)$ is equivalent to $exp[t \cdot p.(:x_1\frac{d}{dx_1}:,...,:x_n\frac{d}{dx_n}:)]$ above.

The row polynomials of $T$ are given by replacing $t^j/j!$ by $t^j$ in the operator expression.

(Edit 6/2014)

Derivatives of the generating function $W_n(x_1,...,x_n;t)$ generate the inverse of $V_n$:

Note that $D^k_{t=-1}f[(1+t)x]=x^k f^{(k)}(0)=x^k D^k_{x=0}f(x)$, so acting on the two different expressions for $W_n$ gives, for $k=0,...,n-1$,

$$D^k_{t=-1} W_n(x_1,...,x_n;t)= \sum_{i=1}^n x_i^k D^k_{x_i=0} |V_n(x_1,...,x_n) |= k! |V_n(x_1,...,x_n)|.$$

Writing out the determinants in matrix form, you can identify the coefficients with the Cramer's rule soln. to the elements of the inverse of $V_n$. Each equation is then proportional to the inner product of a column covector of the adjugate matrix with a row vector of $V_n$.

share|improve this answer
    
    
One way to get a relation to the elementary symmetric polynomials $e_k$ is to express the power sums in terms of them. Also, the determinant can be written in terms of $e_k$, e.g., $$|V_3|=-|\left[ \begin{array}{} 1 & 1 & 1\\ e_1(x_2,x_3) & e_1(x_1,x_3) & e_1(x_1,x_2) \\ e_2(x_2,x_3) & e_2(x_1,x_3) & e_2(x_1,x_2)\end{array} \right]|$$. –  Tom Copeland May 20 at 6:57

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.