8
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Does doing "On the other hand" twice get you back to the hand you started on? $\endgroup$
    – Gerry Myerson
    Dec 12, 2010 at 11:15
  • $\begingroup$ 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. $\endgroup$
    – Leonid Petrov
    Dec 12, 2010 at 11:25
  • $\begingroup$ 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. $\endgroup$
    – john mangual
    Dec 12, 2010 at 11:28
  • $\begingroup$ 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. $\endgroup$
    – Leonid Petrov
    Dec 12, 2010 at 19:32
1
$\begingroup$

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

Random matrices and permutations, matrix integrals and integrable systems

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.