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.

Denote by $D(a_1,\dots,a_n)$ the product $\prod_{j>i}(a_j-a_i)$. Assuming that $a_i$ are integers s.t. $a_1\le a_2\le\dots\le a_n$, proove that $D(a_1,...,a_n)/D(1,...,n)$ is the number of Gelfand-Zetlin triangles (that is, triangles consisting of $\frac{n(n+1)}2$ integers, s.t. each number is greater it's lower-left neighbor but not greater than lower-right neighbor) with the base $a_i$.

For example, for n=3 one needs to prove that number of b1, b2, b' s.t. $a_1\le b_1<a_2\le b_2<a_3$, $b_1\le b'<b_2$ is exactly $\frac{(a_3-a_2)(a_3-a_1)(a_2-a_1)}{3}$.

As one can guess from the name “Gelfand-Zetlin”, this fact is well-known in representation theory (namely, in LHS we count dimension of a $gl_n$-representation by Weyl formula, and in RHS we count elements in Gelfand-Zetlin basis of the same representation). But maybe someone can come with more or less direct proof? (Some kind of bijective proof, maybe.)


Informal probabilistic argument

For simplicity, consider the case $n=3$: D(a_1,a_2,a_3) counts the number of triangles s.t. $a_1\le b_1<a_2\le b_2<a_3$, $a_1\le b'<a_3$ — and we're interested only in G-Z triangles, i.e. in triangles s.t. $b_1\le b'< b_2$. Now, mathematical expectation of the length of the interval $(b_1,b_2)$ is exactly one half of the length of the interval from which $b'$ is chosen. So one may expect that the probability that random triangle is G-Z is $1/2$ — and the answer is indeed $D(a_1,a_2,a_3)/D(1,2,3)$.

(The main problem with this computation is that we're multiplying probabilities for events that are clearly not independent. And although for n=3 it's not hard to transform this heuristic argument into a formal proof, even for n=4 I failed to do such thing.)

share|improve this question
1  
There is a beautiful identity I learned from Gjergji Zaimi (artofproblemsolving.com/Forum/viewtopic.php?f=590&t=290405) which is probably relevant here, but I haven't thought about how to complete the argument; I am guessing an inclusion-exclusion argument, possibly using the Lindstrom-Gessel-Viennot lemma. –  Qiaochu Yuan Aug 5 '10 at 22:06

3 Answers 3

up vote 3 down vote accepted

As Qiaochu points out the formula given by Gjergji Zaimi is certainly relevant. It realizes $D(a_1,\ldots,a_n)/D(1,\ldots,n)$ as the determinant of the $n$-by-$n$ matrix $M$ with $(i,j)$-entry $${a_i\choose j-1}.$$ By row operations this equals the determinant of the $(n-1)$-by-$(n-1)$ matrix $N$ with $(i,j)$-entry $${a_{i+1}\choose j}-{a_i\choose j}.$$ The $i$-th row of $n$ is the sum of vectors $v_{a_i},v_{a_i+1},\ldots,v_{a_{i+1}-1}$ where the $j$-th entry of $v_c$ is $${c\choose j-1}.$$ By the multilinearity of the determinant as a function of its rows, $N$ is the sum the determinants with rows $v_{b_1},\ldots,v_{b_{n-1}}$ where $a_1\le b_i < a_2\le b_2 < a_3\le\cdots$. These tuples $(b_1,\ldots,b_{n-1})$ are precisely the admissible penultimate rows in GZ triangles with bottom row $(a_1,\ldots,a_n)$. Hence both sides of the sought equality satisfy the same recurrence.

share|improve this answer
1  
Combinatorial interpretation (from a friend of mine): the determinant = the number of non-intersecting paths from points $0,1,\dots,n-1$ on Y-axis to points $a_1,\dots,a_n$ on X-axis = number of Gelfand-Zetlin triangles. –  Grigory M Aug 6 '10 at 15:06
    
See also: I. Gessel. Binomial determinants, paths, and hook length formulae in Adv. Math. (from non-intersecting paths to binomial determinant and computation of binomial determinant). –  Grigory M Aug 21 '12 at 17:42

Schur polynomials proof

Observe that $D(a_1,\ldots,a_n)/D(1,\ldots,n)=s_\lambda(1,\ldots,1)$ (for $a_i=\lambda_i+i$). But by Giambelli (aka Jacobi-Trudi) formula $s_\lambda=\det h_{\lambda_i+j-1}$, so $s_\lambda(1,\ldots,1)=\det\binom{a_i}{j-1}$. Now by Lindstrom-Gessel-Viennot lemma last determinant counts non-intersecting lattice paths from the set $0,1,\ldots,n$ on Y-axis to the set $a_1,\ldots,a_n$ on X-axis. Finally, observe that any such path is characterized by x-coordinates of "steps down" — which are subject to conditions from the definition of GZ triangle.

/* Well, it's not that direct and it's more or less the proof from Robin Chapman's answer. Nevertheless, it explains something, I hope. */

share|improve this answer

Just to make sure: you know that what you are asking for is actually Weyl's dimension formula for the highest weight representation in the case of SL(n,C) resp. SU(n)? I suppose there is no direct combinatorial proof that does not make use of this fact.

share|improve this answer
1  
Why not? Many similar results about e.g. Young tableaux have purely combinatorial proofs. –  Qiaochu Yuan Aug 5 '10 at 22:31
    
Yes, LHS is the Weyl dimension formula for a representation of gl_n, and RHS is the number of elements in Gelfand-Zetlin basis in the same representation. –  Grigory M Aug 6 '10 at 7:47

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.