MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

In "Random Matrices Random Permutations", the longest increasing subsequence of a permutation is related to an expectation over Hermitian matrices.

$$ \frac{1}{2^{|k|} n^{|k|/2}} \left\langle \prod_{j=1}^s \mathrm{tr}H^{k_j} \right\rangle$$

Can anyone clarify this relation? I vaguely remember this coming from a paper of Gessel.

In general, I wonder is there a "gadget" turning permutation statistics (such as inversion number, or number of cycles) into integrals over unitary matrices?

share|cite|improve this question

There is a roundabout way of putting this. A discrete analogue of random matrix spectra is random partitions (=Young diagrams). There clearly is a 'gadget' relating random permutations with random Young diagrams - the celebrated Robinson-Schensted correspondence. On the other hand, the passage from random Young diagrams to random matrices is rather well understood (mainly, from the algebraic point of view). In particular, many random matrix ensembles arise from random Young diagrams via certain degenerations. And of course, in various limit regimes the asymptotic distributions of random partition and random matrix ensembles are precisely the same (the Airy ensembles, etc.).

On the other hand, maybe a look on some generalizations of your identity (arXiv:math/9905083) can help?

share|cite|improve this answer
Does doing "On the other hand" twice get you back to the hand you started on? – Gerry Myerson Dec 12 '10 at 11:15
Well, we started from "permutations-matrices" connection, I suggest "permutations-partitions-matrices", and now I see that the two "matrices" here are quite different. The first is about uniform measures on compact classical groups, and the second is about random matrices (i.e., Gaussian Unitary Ensemble, etc.). So here I say "no" to your comment. – Leonid Petrov Dec 12 '10 at 11:25
What if I'm not looking for increasing subsequences. What if I want to count cycles, fixed points or some other statistic? I wonder what makes RS correspondence so fundamental. – john mangual Dec 12 '10 at 11:28
John: Depends on the statistic. I believe that for most combinatorial properties of permutations you need there is some correspondence. E.g., for cycles the reasonable way is to consider corresponding partitions of the set {1,..,n} and then reduce this also to partitions, for uniform random permutations this has much to do with Poisson-Dirichlet distributions. RS correspondence is another correspondence of this sort. It is very natural when you consider representations of symmetric groups. – Leonid Petrov Dec 12 '10 at 19:32

You might want to check out this article by a master of the subject:

Random matrices and permutations, matrix integrals and integrable systems

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.