\documentclass[12pt]{article} %% The lines between the two rows of %'s are more or less compulsory. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in} \setlength{\topmargin}{0pt} \setlength{\headsep}{0pt} \setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt} \setlength{\evensidemargin}{0pt} \makeatletter \newfont{\footsc}{cmcsc10 at 8truept} \newfont{\footbf}{cmbx10 at 8truept} \newfont{\footrm}{cmr10 at 10truept} \renewcommand{\ps@plain}{% \renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics {\footbf 11}(2) (2004), \#R2\hfil\footrm\thepage}} \makeatother \pagestyle{plain} %\documentclass[11pt]{amsart} \usepackage{amsmath,amsfonts,amsthm,amscd,amssymb,euscript, graphics,psfrag} \usepackage{pictex} \def\Z{{\mathbb Z}} \def\H{{\mathbb H}} \newcommand{\calO}{{\cal{O}}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \def\mmtrx#1#2#3#4{\begin{bmatrix} #1 & #2 \\ #3 & #4\end{bmatrix}} \def\mtrx#1#2#3#4#5#6#7#8#9{\begin{bmatrix} #1 & #2 & #3\\ #4 & #5 & #6 \\ #7 & #8 & #9\end{bmatrix}} %%%%%%%%%%%%%%%%% For numbering Theorem 1, Definition 1, Lemma 1, Lemma 2,etc. \theoremstyle{definition} \newtheorem{definition}{Definition} \newtheorem{remark} {Remark} \newtheorem{example} {Example} \newtheorem{conjecture} {Conjecture} \newtheorem*{utheorem}{Theorem} %%%%%%%%%%%%%%%%% \theoremstyle{plain} %%% for statements in italic typeface \newtheorem{theorem} {Theorem} \newtheorem{proposition}[theorem] {Proposition} \newtheorem{corollary}[theorem] {Corollary} \newtheorem{lemma} [theorem]{Lemma} \newcommand{\natls}{{\mathbb N}} \newcommand{\col}{{\hbox{col}}} \newcommand{\row}{{\hbox{row}}} \newcommand{\sh}{{\hbox{sh}}} \newcommand{\type}{{\hbox{type}}} \newcommand{\vol}{{\hbox{vol}}} \newcommand{\Prob}{{\hbox{Prob}}} \newcommand{\injrad}{{\hbox{\rm inj. rad.}}} \newcommand{\genus}{{\hbox{\rm genus}}} \newcommand{\Tr}{{\hbox{\rm Tr}}} \newcommand{\Sc}{{\hbox{\rm Sc}}} %\newcommand{\det}{{\hbox{\rm det}}} \newcommand{\Van}{{\hbox{\rm Van}}} \newcommand{\diam}{{\hbox{\rm diam}}} \newcommand{\fp}{{\mathbb F_p}} \newcommand{\cx}{{\mathbb C}} \newcommand{\reals}{{\mathbb R}} \newcommand{\zed}{{\mathbb Z}} \newcommand{\E}{{\mathbb E}} \newcommand{\Eh}{\E_{\mu_N}} \newcommand{\Eu}{\E_{U_N}} \newcommand{\Sp}{{\rm Sp}} \newcommand{\oO}{{\rm O}} \newcommand{\SU}{{\rm SU}} \newcommand{\SL}{{\rm SL}} \newcommand{\SLtwofp}{\SL_2(\fp)} \newcommand{\SLtwoZ}{\SL_2(\zed)} \newcommand{\SLtwoR}{\SL_2(\reals)} \newcommand{\SLtwoC}{\SL_2(\cx)} \newcommand{\SO}{{\rm SO}} \newcommand{\GL}{{\rm GL}} \newcommand{\RG}{\reals[G]} \newcommand{\cH}{{\mathcal{H}}} \newcommand{\gl}{\lambda} \newcommand{\fix}{{\rm fix}} \newcommand{\Inv}{{\rm Inv}} \newcommand{\trans}{{\rm trans}} \newcommand{\cyc}{{\rm cyc}} \title{Random Matrices, Magic Squares and Matching Polynomials} \author{Persi Diaconis \\ \small Departments of Mathematics and Statistics\\[-0.8ex] \small Stanford University, Stanford, CA 94305 \\[-0.8ex] \small \texttt{diaconis@math.stanford.edu} \and Alex Gamburd\thanks{The second author was supported in part by the NSF postdoctoral fellowship.}\\ \small Department of Mathematics \\[-0.8ex] \small Stanford University, Stanford, CA 94305\\[-0.8ex] \small \texttt{agamburd@math.stanford.edu} } \date{\small Submitted: Jul 22, 2003; Accepted: Dec 23, 2003; Published: Jun 3, 2004\\ \small MR Subject Classifications: 05A15, 05E05, 05E10, 05E35, 11M06, 15A52, 60B11, 60B15} \begin{document} \maketitle %% \dedicatory \centerline{ \emph{Dedicated to Richard Stanley on the occasion of his 60th birthday}} % \vspace*{.5\baselineskip} % {\it Dedicated to Richard Stanley on the occasion of his 60th birthday} %\vspace*{1.5\baselineskip} \begin{abstract} Characteristic polynomials of random unitary matrices have been intensively studied in recent years: by number theorists in connection with Riemann zeta-function, and by theoretical physicists in connection with Quantum Chaos. In particular, Haake and collaborators have computed the variance of the coefficients of these polynomials and raised the question of computing the higher moments. The answer turns out to be intimately related to counting integer stochastic matrices (magic squares). Similar results are obtained for the moments of secular coefficients of random matrices from orthogonal and symplectic groups. Combinatorial meaning of the moments of the secular coefficients of GUE matrices is also investigated and the connection with matching polynomials is discussed. \end{abstract} \section{Introduction} \label{sec:intro} Two noteworthy developments took place recently in Random Matrix Theory. One is the discovery and exploitation of the connections between eigenvalue statistics and the longest-increasing subsequence problem in enumerative combinatorics \cite{AD99, BDJ99, BR01, AO00, TW02}; another is the outburst of interest in characteristic polynomials of Random Matrices and associated global statistics, particularly in connection with the moments of the Riemann zeta function and other L-functions \cite{KS00, CF00, HKO1, HKO2, CFKRS1, CFKRS2}. The purpose of this paper is to point out some connections between the distribution of the coefficients of characteristic polynomials of random matrices and some classical problems in enumerative combinatorics. \section{Secular coefficients of CUE matrices and magic squares} \subsection{Secular coefficients of the characteristic polynomial} Let $M$ be a matrix in $U(N)$ chosen uniformly with respect to Haar measure. Denote by $e^{i \theta_1}, \dots, e^{i \theta_N}$ its eigenvalues and consider the characteristic polynomial of $M$: \beq \label{cpu} P_M(z)=\det(M-zI)=\prod_{j=1}^{N}(e^{i \theta_j}-z)= (-1)^N \sum_{j=0}^{N}\Sc_j(M)z^{N-j}(-1)^j, \eeq where $\Sc_j(M)$ is the $j$-th \emph{secular coefficient} of the characteristic polynomial. Note that \beq \Sc_1(M)=\Tr(M),\eeq and \beq \Sc_N(M)=\det(M).\eeq The moments of traces were studied by Diaconis and Shahshahani \cite{DS94} and Diaconis and Evans \cite{DiEv1} who proved the following result: \begin{theorem} \label{thm:dish} (a) Consider $\mathbf{a}=(a_1, \dots, a_l)$ and $\mathbf{b}=(b_1, \dots, b_l)$ with $a_j$, $b_j$ nonnegative natural numbers. Let $Z_1, \dots, Z_n$ be independent standard complex normal variables. Then for $N \geq \max\left(\sum_1^l ja_j, \sum_1^l j b_j \right)$ we have \begin{multline} \label{e:disha} \Eu \prod\limits^l_{j=1} (\Tr M^j)^{a_j} \overline{(\Tr M^j)} ^{b_j} = \int_{U_N} \prod\limits^l_{j=1} (\Tr M^j)^{a_j} \overline{(\Tr M^j)} ^{b_j} d M \\ = \delta_{ab} \prod\limits^l_{j=1} j^{a_j} a_j ! = E \Bigg(\prod\limits^l_{j=1} (\sqrt{j}Z_j)^{a_j} (\sqrt {j} \bar{Z}_j)^{b_j}\Bigg).\end{multline} (b) For any $j, k, \; \Eu\Tr(M^j) \;\overline{\Tr(M^k)}= \delta_{jk} \;\mbox{min}\;(j,k).$ \end{theorem} Moments of the higher secular coefficients were studied by Haake and collaborators \cite{Ha1, Ha2} who obtained: \beq \label{e:haake} \E_{U(N)} \Sc_j(M) =0, \quad \E_{U(N)} |\Sc_j(M)|^2 =1; \eeq and posed the question of computing the higher moments. The answer is given by Theorem \ref{thm:ms}, which we state below after pausing to give the following definition. \begin{definition} If $A$ is an $m$ by $n$ matrix with nonnegative integer entries and with row and column sums $$r_i=\sum_{j=1}^{n}a_{ij},$$ $$c_j=\sum_{i=1}^{m}a_{ij};$$ then the the row-sum vector $\row(A)$ and column-sum vector $\col(A)$ are defined by $$\row(A)=(r_1, \dots, r_m),$$ $$\col(A)=(c_1, \dots, c_n).$$ \end{definition} Given two partitions $\mu=(\mu_1, \dots, \mu_m)$ and $\tilde{\mu}=(\tilde{\mu}_1, \dots, \tilde{\mu}_n)$ (see section \ref{sec:cue} for the partition notations) we denote by $N_{\mu \tilde{\mu}}$ the number of nonnegative integer matrices $A$ with $\row(A) = \mu$ and $\col(A) = \tilde{\mu}$. For example, for $\mu=(2, 1, 1)$ and $\tilde{\mu}=(3, 1)$ we have $N_{\mu \tilde{\mu}}=3;$ and the matrices in question are $$\begin{bmatrix} 2&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 0&1\\ 1&0 \end{bmatrix}, \begin{bmatrix} 1&1\\ 1&0\\ 1&0 \end{bmatrix}. $$ For $\mu=(2, 2, 1)$ and $\tilde{\mu}=(3, 1,1)$ we have $N_{\mu \tilde{\mu}}=8;$ and the matrices in question are %\begin{multline*} $$\begin{bmatrix} 0&1&1\\ 2&0&0\\ 1&0&0 \end{bmatrix}, \begin{bmatrix} 1&1&0\\ 1&0&1\\ 1&0&0 \end{bmatrix}, \begin{bmatrix} 1&0&1\\ 1&1&0\\ 1&0&0 \end{bmatrix}, \begin{bmatrix} 2&0&0\\ 0&1&1\\ 1&0&0 \end{bmatrix},$$ $$\begin{bmatrix} 2&0&0\\ 1&1&0\\ 0&0&1 \end{bmatrix}, \begin{bmatrix} 2&0&0\\ 1&0&1\\ 0&1&0 \end{bmatrix}, \begin{bmatrix} 1&1&0\\ 2&0&0\\ 0&0&1 \end{bmatrix}, \begin{bmatrix} 1&0&1\\ 2&0&0\\ 0&1&0 \end{bmatrix}.$$ %\end{multline*} We are ready to state the following Theorem, proved in section \ref{sec:cue}. \begin{theorem} \label{thm:ms} (a) Consider $\mathbf{a}=(a_1, \dots, a_l)$ and $\mathbf{b}=(b_1, \dots, b_l)$ with $a_j$, $b_j$ nonnegative natural numbers. Then for $N \geq \max\left(\sum_1^l ja_j, \sum_1^l j b_j \right)$ we have \beq \label{e:mixedmom} \Eu \prod\limits^l_{j=1} (\Sc_j(M))^{a_j} \overline{(\Sc_j(M))} ^{b_j} = N_{\mu \tilde{\mu}}. \eeq Here $\mu$ and $\tilde{\mu}$ are partitions $\mu=\langle 1^{a_1}\dots l^{a_l}\rangle $, $\tilde{\mu}=\langle 1^{b_1}\dots l^{b_l}\rangle $ (see section \ref{sec:cue} for the partition notations) and $N_{\mu \tilde{\mu}}$ is the number of nonnegative integer matrices $A$ with $\row(A) = \mu$ and $\col(A) = \tilde{\mu}$. (b) In particular, for $N \geq j k$ we have \beq \label{cuemom} E_{U(N)}|\Sc_j(M)|^{2k}= H_k(j), \eeq where $H_k(j)$ is the number of $k\times k$ nonnegative integer matrices with each row and column summing up to $j$ -- ``magic squares''. \end{theorem} \subsection{Magic Squares} The reader is likely to have encountered objects, which following Ehrhart~\cite{EE77} are refereed to as ``historical magic squares''. These are square matrices of order $k$, whose entries are nonnegative integers ($1, \dots, k^2$) and whose rows and columns sum up to the same number. The oldest such object, \begin{equation} \label{hm} \mtrx{4}{9}{2}{3}{5}{7}{8}{1}{6} \end{equation} first appeared in ancient Chinese literature under the name \emph{Lo Shu} in the third millennium BC and repeatedly reappeared in the cabbalistic and occult literature in the middle ages. Not knowing ancient Chinese, Latin, or Hebrew it is difficult to understand what is ``magic'' about \emph{Lo Shu}; it is quite easy to understand however why it keeps reappearing: there is (modulo reflections) only one historic magic square of order $3$. Following MacMahon \cite{PM15} and Stanley \cite{RS73}, what is referred to as magic squares in modern combinatorics are square matrices of order $k$, whose entries are nonnegative integers and whose rows and columns sum up to the same number $j$. The number of magic squares of order $k$ with row and column sum $j$, denoted by $H_k(j)$, is of great interest; see \cite{DG} and references therein. The first few values are easily obtained: \begin{equation} \label{hk1} H_k(1)=k!, \eeq corresponding to all $k$ by $k$ permutation matrices (this is the $k$-th moment of the traces leading in the work of Diaconis and Shahshahani to the result on the asymptotic normality, see section \ref{sec:cons} below); \beq \label{e:h1} H_1(j)=1, \eeq corresponding to $1 \times 1$ matrix $[j]$. We also easily obtain $ H_2(j)= j+1, $ corresponding to $ \mmtrx{i}{j-i}{j-i}{i} $, but the value of $H_3(j)$ is considerably more involved: \begin{equation}\label{h3j} H_3(j)= \binom{j+2}{4} +\binom{j+3}{4} +\binom{j+4}{4}. \eeq This expression was first obtained by Mac Mahon in 1915 \cite{PM15} and a simple proof was found only a few years ago by M. Bona \cite{MB97}. The main result on $H_k(j)$ is given by the following theorem, proved by Stanley and Ehrhart (see \cite{EE73, EE77, RS73, RS74, stanley86}): \begin{theorem} \label{stan} %\begin{description} (a) $H_k(j)$ is a polynomial in $j$ of degree $(k-1)^2$. (b) The following relations hold: \beq \label{e:rec1} H_k(-1)=H_k(-2)=\dots=H_k(-k+1)=0, \eeq and \beq \label{e:rec2} H_k(-k-j)=(-1)^{k-1}H_k(j).\eeq It can be shown that the two statements above are equivalent to \beq \sum_{j\geq 0}H_k(j) x^{j}=\frac{h_0+h_1 x +\dots +h_d x^{d}}{(1-x)^{(k-1)^2 +1}}, \quad d=k^2-3k+2, \eeq with $h_0+h_1+\dots h_d \ne 0$ and $h_i=h_{d-i}$. (c) The leading coefficient of $H_k(j)$ is the relative volume of $\mathcal{B}_{k}$ - the $k$-th Birkhoff polytope, i.e. leading coefficient is equal to $\frac{\vol(\mathcal{B}_{k})}{k^{k-1}}$. %\end{description} \end{theorem} By definition, the $k$-th Birkhoff polytope is the convex hull of permutation matrices: \beq \label{e:bp} \mathcal{B}_k= \left\{ (x_{ij}) \in \reals^{k^2} \biggm | x_{ij}\geq 0; \quad \sum_{i=1}^{k}x_{ij} = 1; \quad \sum_{j=1}^{k}x_{ij} = 1 \right\} .\eeq For example, $$ H_3(j)=\frac{1}{8}j^4+\frac{3}{4}j^3+\frac{15}{8}j^2+\frac{9}{4}j+1, $$ and $$ \sum_{j\geq 0}H_3(j) x^{j}=\frac{1+x+x^2}{(1-x)^{5}}. $$ Further, in the example above, $$\vol(\mathcal{B}_{3})=\frac{1}{8}\times 9. $$ Of course, the joint mixed moments in \eqref{e:mixedmom}involve counting rectangular arrays with general row and column sums. This subject has an extensive literature; see the survey article \cite{DG}. The latest results on the complexity of this problem may be found in \cite{CrDy}. We will return to the discussion of computational aspects in section \ref{sec:cons}. \subsection{Proof of Theorem \ref{thm:ms}} \label{sec:cue} Before proceeding with the proof of Theorem \ref{thm:ms} we review some basic notions and notations of symmetric function theory, referring the reader to \cite{Mac, BrSa, stanleyv2} for more details. A partition $\lambda$ of a nonnegative integer $n$ is a sequence $(\lambda_1, \dots, \lambda_r) \in \natls^r$ satisfying $\lambda_1 \geq \dots \geq \lambda_r$ and $\sum \lambda_i =n$. We call $|\lambda| = \sum \lambda_i$ the size of $\lambda$. The number of parts of $\lambda$ is the length of $\lambda$, denoted $l(\lambda)$. Write $m_i=m_i(\lambda)$ for the number of parts of $\lambda$ that are equal to $i$, so we have $\lambda = \langle 1^{m_1}2^{m_2} \dots\rangle$. The Young diagram of a partition $\lambda$ is defined as the set of points $(i, j) \in \zed^2$ such that $1 \leq i \leq \lambda_j$; it is often convenient to replace the set of points above by squares. The conjugate partition $\lambda'$ of $\lambda$ is defined by the condition that the Young diagram of $\lambda'$ is the transpose of the Young diagram of $\lambda$; equivalently $m_i(\lambda')=\lambda_i-\lambda_{i+1}$. A semi-standard Young tableau (SSYT) of shape $\lambda $ is a filling of the boxes of $\lambda $ with positive integers such that the rows are weakly increasing and the columns are strictly increasing. \begin{figure}[!h] \abovedisplayskip-.5\baselineskip \belowdisplayskip-\baselineskip \begin{equation*} \begin{matrix}\beginpicture \setcoordinatesystem units <0.5cm,0.5cm> \setplotarea x from 0 to 4, y from 1 to 3 \linethickness =0.5pt \putrule from 0 6 to 5 6 \putrule from 0 5 to 5 5 \putrule from 0 4 to 5 4 \putrule from 0 3 to 3 3 \putrule from 0 2 to 2 2 \putrule from 0 2 to 0 6 \putrule from 1 2 to 1 6 \putrule from 2 2 to 2 6 \putrule from 3 3 to 3 6 \putrule from 4 4 to 4 6 \putrule from 5 4 to 5 6 \endpicture &\qquad \qquad & \beginpicture \setcoordinatesystem units <0.5cm,0.5cm> \setplotarea x from 0 to 4, y from 1 to 3 \linethickness =0.5pt \put {6} at 0.5 2.5 \put {5} at 0.5 3.5 \put {2} at 0.5 4.5 \put {1} at 0.5 5.5 \put {7} at 1.5 2.5 \put {6} at 1.5 3.5 \put {3} at 1.5 4.5 \put {1} at 1.5 5.5 \put {6} at 2.5 3.5 \put {3} at 2.5 4.5 \put {2} at 2.5 5.5 \put {5} at 3.5 4.5 \put {2} at 3.5 5.5 \put {6} at 4.5 4.5 \put {3} at 4.5 5.5 \putrule from 0 6 to 5 6 \putrule from 0 5 to 5 5 \putrule from 0 4 to 5 4 \putrule from 0 3 to 3 3 \putrule from 0 2 to 2 2 \putrule from 0 2 to 0 6 \putrule from 1 2 to 1 6 \putrule from 2 2 to 2 6 \putrule from 3 3 to 3 6 \putrule from 4 4 to 4 6 \putrule from 5 4 to 5 6 \endpicture \\ \hbox {Partition $\lambda$} &&\hbox {SSYT $T$} \end{matrix} \end{equation*} \caption{} \end{figure} In the figure we exhibited a partition $\lambda = (5, 5, 3, 2) =\langle 1^0 2^1 3^1 5^2 \rangle$, and a SSYT $T$ of shape $\lambda$ (we write $\lambda = \sh(T)$). We say that $T$ has type $\alpha =(\alpha_1, \alpha_2, \dots )$, denoted $\alpha = \type(T)$, if $T$ has $\alpha_i =\alpha_i(T)$ parts equal to $i$. Thus, the SSYT in the figure has type $(2, 3, 3, 0, 2, 4, 1)$. For any SSYT $T$ of type $\alpha$ write $$ x^T = x_1^{\alpha_1(T)}x_2^{\alpha_2(T)} \dots . $$ In our example we have $$ x^T = x_1^2 x_2^3 x_3^3 x_4^0 x_5^2 x_6^4 x_7^1 $$ Let $\lambda$ be a partition. We define the Schur function $s_{\lambda}$ in the variables $x =(x_1, x_2, \dots)$ as the formal power series \beq s_{\lambda}(x)= \sum_{T} x^T, \eeq where the sum is over all SSYT's $T$ of shape $\lambda$. The number of SSYT of shape $\lambda$ and type $\alpha$ is denoted $K_{\lambda \alpha}$, and is called the Kostka number. We have \beq \label{e:kost} s_{\lambda}=\sum_{\alpha} K_{\lambda \alpha} x^{\alpha} . \eeq In the course of this paper, in addition to the combinatorial definition given above, we will make use of (all of) the following equivalent definitions of Schur functions. The classical definition of Schur functions is as a ratio of two determinants: \beq \label{classchur} s_{\lambda}(x)=\frac{\det\left(x_i^{\lambda_{j}+n-j}\right)_{i, j=1}^{n}} {\det\left(x_i^{n-j}\right)_{i, j=1}^{n}}. \eeq Before proceeding with the next definition of Schur functions we remind the reader that the elementary symmetric functions $e_r(x_1, \dots, x_n)$ are given by \beq \label{e:elsim1} e_r(x_1, \dots, x_n) =\sum_{i_1 < \dots < i_r}x_{i_1} \dots x_{i_r}, \eeq and for a partition $\lambda$ we denote \beq \label{e:elsim2} e_{\lambda}=\prod e_{\lambda_j}.\eeq We now ready to give another definition of Schur functions, known as Jacobi-Trudi identity: \beq \label{e:jti} s_{\lambda} = \det \left(e_{\lambda'_{i} -i+j}\right)_{i, j=1}^{n}.\ \eeq Finally, the Schur functions give the irreducible characters of $U(N)$: \beq \label{e:schch} \E_{U}\left(s_{\lambda}(M) \overline{s_{\mu}(M)} \right)= \delta_{\lambda \mu}; \eeq here $\lambda$ and $\mu$ have at most $N$ rows. We now turn to the proof of Theorem \ref{thm:ms}. First of all we observe that \beq \Sc_j(M) = e_j(M), \eeq where $e_j$ are the elementary symmetric functions defined in \eqref{e:elsim1}, and that \beq \prod\limits^l_{j=1} (\Sc_j(M))^{a_j} \overline{(\Sc_j(M))} ^{b_j} = e_{\mu}(M) e_{\tilde{\mu}}(\overline{M}), \eeq where $\mu$ and $\tilde{\mu}$ are partitions $\mu=\langle 1^{a_1}\dots l^{a_l}\rangle $, $\tilde{\mu}=\langle 1^{b_1}\dots l^{b_l}\rangle $ and $e_{\mu}$, $e_{\tilde{\mu}}$ are elementary symmetric functions defined in \eqref{e:elsim2}. We express the elementary symmetric functions in terms of Schur functions (see p. 335 in \cite{stanleyv2}): \beq e_{\mu} = \sum_{\lambda}K_{\lambda' \mu}s_{\lambda}, \eeq where $K_{\lambda \mu}$ is the Kostka number defined preceding \eqref{e:kost}. We now integrate over the unitary group and use the fact that the Schur function are irreducible characters expressed in \eqref{e:schch}, to obtain: \beq \label{e:integration} \int_{U(N)}e_{\mu}(M) e_{\tilde{\mu}}(\overline{M})dM = \sum_{\lambda' \vdash |\mu|=|\tilde{\mu}|}K_{\lambda' \mu}K_{\lambda' \tilde{\mu}} = N_{\mu \tilde{\mu}}\eeq where $N_{\mu \tilde{\mu}}$ is the number of nonnegative integer matrices $A$ with $\row(A) = \mu$ and $\col(A) = \tilde{\mu}$. The last equality in \eqref{e:integration} is the consequence of the Knuth correspondence \cite{knuth}, establishing a bijection between $\natls$ -matrices $A$ of finite support and ordered pairs of $(P, Q)$ of SSYT of the same shape with $\type(P) = \col(A)$ and $\type(Q) =\row(A)$. This completes proof of Theorem \ref{thm:ms}. \subsection{Some consequences} \label{sec:cons} Theorem \ref{thm:ms} shows that $\Eu(\Sc_j^a(M))=0$ for any fixed $j, a \geq 1$ ; further for any fixed $j_1, \dots, j_k$ and $a_1, \dots, a_k$ we have $$\Eu(\Sc_{j_1}^{a_1}(M) \dots \Sc_{j_k}^{a_k}(M))=0; $$ it also easily implies that $\Sc_j(M)$ are not independent: $$\Eu |\Sc_j(M)|^2 |\Sc_k(M)|^2 =j+1 \neq 1.$$ We further remark, that as a consequence of Theorem \ref{thm:dish}, Diaconis and Shahshahani have shown that if $M$ is chosen from Haar measure on $U_N$, the traces of successive powers have limiting Gaussian distributions: as $N\rightarrow \infty$, for any fixed $k$ and Borel sets $B_1,\ldots,B_k$ \begin{equation} \label{e:normality} P (\Tr M \in B_1,\ldots, \Tr M^k \in B_k) \rightarrow\; \prod\limits^k_{j=1} \; P(\sqrt{j}\,Z \in B_j), \end{equation} where $Z$ is standard complex normal. This has the following implication for secular coefficients \begin{proposition} \label{prop:norm} Let $M$ be chosen uniformly in $U_N$. For fixed $j$ and for any Borel set $B$ we have \beq P \{\Sc_j(M) \in B\} \to P\{W_j \in B\}, \eeq where $W_j$ is the polynomial in independent standard complex Gaussian variables $Z_1, \dots, Z_j$, given by \beq \label{e:gauspoly} W_j = \frac{1}{j!}\left| \begin{matrix} Z_1 & 1 & 0 & \dots & 0\\ \sqrt{2}Z_2 & Z_1 & 2 & \dots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \sqrt{j-1}Z_{j-1} & \sqrt{j-2}Z_{j-2} & \sqrt{j-3}Z_{j-3}& \dots &j-1 \\ \sqrt{j}Z_{j}& \sqrt{j-1}Z_{j-1} & \sqrt{j-2} Z_{j-2} & \dots & Z_1 \end{matrix} \right|. \eeq \end{proposition} For example, $$ \Sc_3(M) \sim \frac{1}{6}Z_1^3 -\frac{1}{\sqrt{2}}Z_1 Z_2+\frac{1}{\sqrt{3}}Z_3 $$ This proposition follows easily from \eqref{e:normality} and the Newton formula relating elementary and power sum symmetric functions \cite[p.28]{Mac}. Now, since the number of magic squares $H_k(j)$ can be expressed as the $k$-th power of this Gaussian polynomial, this proposition might be useful in computing $H_k(j)$ and its leading coefficient $\vol(\mathcal{B}_{k})$ --- a subject which has received much recent attention (see \cite{BP99, CR99, CrDy, JDLBS, DKM97, JM00}). The connection with Toeplitz determinants, which is discussed in the next section, might also be of interest in connection with computing $H_k(j)$. Formula \eqref{e:gauspoly} gives the asymptotic distribution of the $j$th secular coefficient for fixed $j$ as $N$ tends to infinity as a polynomial of degree $j$ in independent Gaussian variables. It is natural to ask for limiting distribution as $j$ grows with $N$. For example what is the limiting distribution of the $\lfloor N/2 \rfloor$ secular coefficient? On the one hand, \eqref{e:gauspoly} suggests it is a complex sum of independent random variables, so perhaps normal. On the other hand, \eqref{e:haake} holds for all $j$ making normality questionable. Finally, we note that Theorem \ref{thm:ms} served as one of the motivations for \cite{BCAG}, where integral moments of partial sums of the Riemann zeta function on the critical line were computed and the following result was proved. \begin{theorem} \label{bcagzeta} Let $a_k$ be the arithmetic factor given by \beq \label {e:af}a_k=\prod_{p}\left(1-\frac{1}{p}\right)^{k^2} \sum_{j=0}^{\infty}\frac{d_k(p^j)^2}{p^j}, \eeq where $d_k(n)$ is the number of ways of expressing $n$ as a product of $k$ factors. Then \beq \label{e:main} \lim_{T \to \infty} \frac{1}{T}\int_{0}^{T} \left \vert \sum_{n=1}^{X} \frac{1}{n^{\frac{1}{2}+i t}} \right \vert^{2k} d t= a_k \gamma_k (\log X)^{k^2} + O\left( (\log X)^{k^2-1} \right). \eeq Here %\beq a_k=\prod_{p}\left(1-\frac{1}{p}\right)^{k^2} %\sum_{j=0}^{\infty}\frac{d_k(p^j)^2}{p^j}, \eeq $\gamma_k$ is the geometric factor, $\gamma_k =\vol(\mathcal{P}_k)$, where $\mathcal{P}_k$ is the convex polytope of substochastic matrices, defined by the following inequalities (note the similarity with \eqref{e:bp}): \beq \label{e:pkt} \mathcal{P}_k= \left\{ (x_{ij}) \in \reals^{k^2} \biggm | x_{ij}\geq 0; \quad \sum_{i=1}^{k}x_{ij} \leq 1; \quad \sum_{j=1}^{k}x_{ij} \leq 1 \right\} .\eeq \end{theorem} \section{Connection with the Toeplitz determinants} \label{sec:toep} For certain functions $f$ an alternative approach to computing the averages $\int_{U(N)}f(M) dM$ over the unitary group can be based on the Heine-Szego formula. \begin{proposition}\label{p:hs}[Heine-Szego formula] For $f \in L^1(S^1)$ we have: \begin{equation}\label{e:hsf} \frac{1}{(2\pi)^N} \int^{2\pi}_0 \ldots \int^{2\pi}_0 \prod\limits^N_{j=1} \; f(e^{i\theta_j}) \; \prod\limits_{1\leq \; k\leq \; l\leq \; N} |e^{i\theta_k} - e^{i\theta_l}|^2\; d\theta_1\ldots d\theta_N =\; D_N(f). \end{equation} \end{proposition} Here $D_N(f)$ is the $N \times N$ Toeplitz determinant with symbol $f$: \beq D_N(f)= \det \left( \hat{f}(j-k)\right)_{0\leq j, k \leq N}, \eeq where $\hat{f} (r) = \frac{1}{2\pi}\int^{2\pi}_0 f(e^{ir\theta})\;d\theta.$ See \cite{BD02} for a proof and references to early literature. K. Johansson \cite{Johan2} gave a proof of Diaconis and Shahshahani result \eqref{e:normality} using \eqref{e:hsf} and Szego strong limit theorem for Toeplitz determinats; on the other hand, as explained in \cite{BD02}, the asymptotic normality \eqref{e:normality} gives a new proof (and some extensions) of the strong Szego limit theorem. To apply proposition Proposition \ref{p:hs} in our setting it is convenient to introduce the following polynomial \beq Q_M(z) = \det(I+Mz) = \sum_{j=0}^{N}\Sc_j(M)z^{j}. \eeq The polynomial $Q_M(z)$ is closely related to the characteristic polynomial, in fact \beq Q_M\left(-\frac{1}{z}\right)=\frac{(-1)^N}{z^{N}} P_M(z). \eeq With $\overline{Q_M(z)}=\sum_{j=0}^{N}\overline{\Sc_j(M)}z^{-j}$ we then have: \beq \Eu \left[Q_M(z_1)\dots Q_M(z_l) \overline{Q_M(z_{l+1})} \dots \overline{Q_M(z_{m})}\right]=\frac{1}{(z_{l+1} \dots z_m)^N} D_N(f), \eeq where \beq \label{e:symb} f(t)= \frac{1}{t^{m-l}}\prod _{i=1}^{m}(1+z_i t)=\sum_{r \geq l-m}t^{r}e_{r+m-l}(z_1, \dots, z_m). \eeq Following \cite{BD02}, the Toeplitz determinant with symbol \eqref{e:symb} can be computed using the Jacobi-Trudi identity \eqref{e:jti} and is found to be equal to $s_{N^{m-l}}(z_1, \dots, z_m)$. %where $S_{\lambda}$ is the Schur function associated with %partition $\lambda.$ We thus obtain an alternative simple proof of the following result, first established in \cite{CFKRS2}: \begin{theorem}\label{p:shur} Notation being as above, we have \beq \Eu \left[Q_M(z_1)\dots Q_M(z_l) \overline{Q_M(z_{l+1})} \dots \overline{Q_M(z_{m})}\right]= \frac{s_{N^{m-l}}(z_1, \dots, z_m)}{(z_{l+1} \dots z_m)^N} \eeq \end{theorem} %\subsection{Haake's proof} We remark that for computing higher moments of secular coefficients the approach presented in section \ref{sec:cue} seems to be more advantageous. Theorem \ref{p:shur} straightforwardly implies only the following hard-to-unravel result: \beq \Eu \Sc_{\alpha_1}(M) \dots \Sc_{\alpha_l}(M) \overline{\Sc_{N-\alpha_{l+1}}(M)} \dots \overline{\Sc_{N-\alpha_{m}}(M)} = K_{N^{l-m} \alpha}. \eeq The Toeplitz determinant associated with the symbol given by \eqref{e:symb} is also closely related to a classical formula of Schmidt and Spitzer; before stating it we briefly review Haake's derivation of \eqref{e:haake}. It is implicitly based on the following lemma due to Andr\'{e}ief \cite{A1883} (see also \cite{TrWi3}): \begin{lemma} Let $f(z)$, $g(z)$ be square-integrable functions on $S^1$. Then \beq \label{e:and} \Eu \det(f(M)) \det(g(M^{\dagger}))=\det\left(\frac{1}{2 \pi}\int_{0}^{2 \pi}f(e^{i \theta})g(e^{-i \theta})e^{i (j-k) \theta} \, d \theta\right)_{0 \leq j, k \leq N}. \eeq \end{lemma} Applying this lemma with $f(z)=z-\lambda$ and $g(z)=z-\mu$ with $z=e^{i \phi}$ and $\mu =e^{i \chi}$ and letting $x=e^{i(\phi-\chi)}$, we have that the integral on the right-hand side of equation \eqref{e:and}is given by \beq \frac{1}{2 \pi}\int_{0}^{2 \pi}(e^{i \theta}-x)(e^{-i \theta}-1)e^{i (j-k) \theta} \, d \theta = (1+x)\delta(j-k) -\delta(j-k+1)-x\delta(j-k-1), \eeq where $\delta(k)$ is $0$ or $1$ as $k$ is nonzero or zero. Denoting the determinant on the right-hand side of \eqref{e:and} by $D_N(x)$ it is easy to see that for this choice of $f$ and $g$ it satisfies the recurrence $$D_N(x) =D_{N-1}(x)x +1, $$ whence \beq \label{e:hd} D_N(x)=\sum_{j=0}^{N} x^j, \eeq yielding the proof of \eqref{e:haake}. Formula \eqref{e:hd} is also an easy consequence of the following result of Schmidt and Spitzer \cite{SS60} on Toeplitz determinants: \begin{theorem} \label{t:SS} Let $a$ be given by \beq a(t)= t^{-p} \prod_{j=1}^{p+q}(t-\rho_j) \qquad (t=e^{i \theta}). \eeq If the zeroes $\rho_1, \dots \rho_{p+q}$ are pairwise distinct then for every $N \geq 1$, \beq D_N(a)=\sum_{L}C_L w_{L}^{N}, \eeq where the sum is taken over all $\binom{p+q}{q}$ subsets $L \in \{1, 2, \dots, p+q \}$ of cardinality $|L|=p$ and with $\bar{L}=\{1, \dots, p+q\}\setminus L$, \beq w_L =(-1)^{q} \prod_{j\in \bar{L}}\rho_{j}, \qquad C_L=\prod_{j\in \bar{L}} \rho_{j}^{p} \prod_{\substack{j\in\bar{L}\\ k \in L }}(\rho_j-\rho_k)^{-1}. \eeq \end{theorem} If we let \beq a(t) =a_{-1}t^{-1} +a_0+t = t^{-1}(t-\rho)(t-\sigma) \eeq with $\rho \ne \sigma,$ then theorem \ref{t:SS} gives \beq D_N(a) =\frac{\sigma}{\sigma-\rho}(\-\sigma)^{N}+\frac{\rho}{\rho-\sigma}(-\rho)^{N}= (-1)^N\frac{\sigma^{N+1}-\rho^{N+1}}{\sigma - \rho}; \eeq and setting $\sigma =x, \, \rho =1$ this is easily seen to be equivalent to \eqref{e:hd}. We now give a simple proof of Theorem \ref{t:SS} using Theorem \ref{p:shur}. We have \beq D_N(a(t))=\prod_{j=1}^{p+q}\left(\frac{1}{-\rho_j}\right)^{N} D_N(g(t)),\eeq where \beq g(t)=t^{-p}\prod_{j=1}^{p+q}(1-\rho_j t). \eeq Consequently \beq \label{e:sss} D_N(a(t))=\prod_{j=1}^{p+q}\left(-\frac{1}{\rho_j}\right)^{N} s_{N^p}(-\rho_1, \dots, -\rho_{p+q}) = (-1)^{qN} \prod_{j=1}^{p+q}\left(\frac{1}{\rho_j}\right)^{N}s_{N^p}(\rho_1, \dots, \rho_{p+q}).\eeq Now using the classical definition of Schur fucntions \eqref{classchur}, and recalling that %\beq S_{\lambda}(x_1, \dots, x_n) =\frac{\det(x_i^{\lambda_j +n %-j})_{1 \leq i, j \leq n}}{\det(x_i^{n-j})}, \eeq \beq \det(x_i^{n-j})=\prod_{1 \leq i < j\leq n}(x_i -x_j), \eeq we obtain the Schmidt-Spitzer formula by using Laplace expansion\footnote{We recall the definition of Laplace expansion. Fix $p$ rows of matrix $A$. Then the sum of products of the minors of order $p$ that belong to these rows by their cofactors is equal to the determinant of $A$.} in the first $p$ rows of the determinant appearing in the numerator of $S_{N^p}$ in formula \eqref{e:sss}: \beq \left| \begin{matrix} \rho_1^{p+q-1+N} & \rho_1^{p+q-2+N} & \dots & \rho_1^{N}\\ \vdots & \vdots & \ddots & \vdots \\ \rho_p^{p+q-1+N} & \rho_p^{p+q-2+N} & \dots & \rho_p^{N}\\ \rho_{p+1}^{p+q-1} & \rho_{p+1}^{p+q-2} & \dots & \rho_{p+1}^{0}\\ \vdots & \vdots & \ddots & \vdots \\ \rho_{p+q}^{p+q-1} & \rho_{p+q}^{p+q-2} & \dots & \rho_{p+q}^{0} \end{matrix} \right| \left| \begin{matrix} \rho_{1}^{p+q-1} & \rho_{1}^{p+q-2} & \dots & \rho_{1}^{0}\\ \vdots & \vdots & \ddots & \vdots \\ \rho_{p+q}^{p+q-1} & \rho_{p+1q}^{p+q-2} & \dots & \rho_{p+q}^{0} \end{matrix} \right|^{-1}. \eeq %\newpage \section{Secular coefficients of random orthogonal and symplectic matrices} \label{sec:coecse} In this section we prove the analogues of Theorem \ref{thm:ms} for the orthogonal group $\oO(N)$ and for the symplectic group $\Sp(2N)$. \begin{theorem} \label{thm:oms} (a) Consider $\mathbf{a}=(a_1, \dots, a_l)$ with $a_j$ nonnegative natural numbers. Let $\mu$ be a partition $\mu=\langle 1^{a_1}\dots l^{a_l}\rangle.$ Then for $N \geq \sum_1^l ja_j$ and $|\mu|$ \emph{even} we have \beq \label{e:mixedmomo} \E_{\oO(N)}\prod\limits^l_{j=1} (\Sc_j(M))^{a_j} = NSO_{\mu}. \eeq Here $NSO_{\mu}$ is the number of nonnegative \emph{symmetric} integer matrices $A$ with $\row(A) = \col(A) = \mu$ and with all diagonal entries of $A$ equal to $0$. For $|\mu|$ odd the expected value in \eqref{e:mixedmomo} is $0$. (b) In particular, for $N \geq j k$ and $jk$ even we have \beq \label{coemom} E_{\oO(N)}\Sc_j(M)^{k}= S^{o}_k(j), \eeq where $S^{o}_k(j)$ is the number of $k\times k$ symmetric nonnegative integer matrices with each row and column summing up to $j$ and all diagonal entries equal to zero (equivalently j-regular graphs on k vertices without loops). For $jk$ odd the expected value in \eqref{coemom} is $0$. \end{theorem} {\bf Proof:} We have $\Sc_j(M) = e_j(M)$ and $\prod\limits^l_{j=1} (\Sc_j(M))^{a_j} = e_{\mu}(M)$; as in the proof of theorem \ref{thm:ms}, we begin by expressing the elementary symmetric functions in terms of Schur functions $e_{\mu} = \sum_{\lambda}K_{\lambda' \mu}s_{\lambda}$. We now integrate over the orthogonal group and use the fact that for integrals of Schur functions we have the following expression (see \cite{ER98}): \beq \label{e:schurorth} \E_{\oO(N)}s_{\lambda}(M)= \begin{cases} 1, &\text{if $\lambda = 2 \nu, \, l(\lambda) \leq N$;}\\ 0, &\text{otherwise}, \end{cases} \eeq where $2 \nu$ represents the partition produced by doubling each elements of $\nu$. Note that if $\lambda = 2\nu$, then $\lambda' = \nu'^{2}$, where $\nu^2$ represents the partition produced by writing each element of $\nu$ twice. We thus obtain \beq \label{momorthog} \E_{\oO(N)}e_{\mu}(M) = \sum_{\lambda = \nu^{2}}K_{\lambda \mu}. \eeq Next we observe that the condition $\lambda =\nu^2$ is equivalent to the condition that the associated tableau have all columns of even length. Now we recall that a version of the Knuth correspondence \cite{knuth} establishes a bijection between symmetric matrices of nonnegative integers with column sums given by $\mu$ and tableaux of any shape with content $\mu$; and that furthermore in this correspondence the trace of the matrix is the number of odd length columns of the corresponding tableau. We finally note that symmetric nonnegative matrix whose diagonal elements are all zero corresponds to an adjacency matrix of a graph without loops. This completes the proof of Theorem \ref{thm:oms}. We remark that for the case of the $2k$-th moment of the first secular coefficient, that is the moments of trace studied in \cite{DS94}, \eqref{momorthog} specializes to the following formula: \beq \E_{\oO(N)}\Tr(M)^{2k} = \sum_{\lambda' = 2 \nu }K_{\lambda 1^{2k}} = \sum_{\lambda' = 2 \nu } f^{\lambda} = 1 \times 3 \dots \times (2k-1), \eeq where $f^{\lambda}$ denotes the number of standard tableaux of shape $\lambda$. We refer the reader to \cite{IRS} for the representation-theoretic significance of this formula and its generalizations. \begin{theorem} \label{thm:spms} (a) Consider $\mathbf{a}=(a_1, \dots, a_l)$ with $a_j$ nonnegative natural numbers. Let $\mu$ be a partition $\mu=\langle 1^{a_1}\dots l^{a_l}\rangle.$ Then for $N \geq \sum_1^l ja_j$ and $|\mu|$ \emph{even} we have \beq \label{e:mixedmomsp} \E_{\Sp(2N)}\prod\limits^l_{j=1} (\Sc_j(M))^{a_j} = NSP_{\mu}. \eeq Here $NSP_{\mu}$ is the number of nonnegative \emph{symmetric} integer matrices $A$ with $\row(A) = \col(A) = \mu$ and with all diagonal entries of $A$ even. For $|\mu|$ odd the expected value in \eqref{e:mixedmomsp} is $0$. (b) In particular, for $N \geq j k$ and $jk$ even we have \beq \label{csemom} E_{\Sp(2N)}\Sc_j(M)^{k}= S^{sp}_k(j), \eeq where $S^{sp}_k(j)$ is the number of $k\times k$ symmetric nonnegative integer matrices with each row and column summing up to $j$ and all diagonal entries even (equivalently, the number of j-regular graphs on k vertices with loops and multiple edges). For $jk$ odd the expected value in \eqref{csemom} is $0$. \end{theorem} {\bf Proof:} We proceed as in the proof of Theorem \ref{thm:oms}, this time using the following expression for integrals of the Schur functions over the symplectic group: \beq \label{e:schursymp} \E_{\Sp(2N)}s_{\lambda}(M)= \begin{cases} 1, &\text{if $\lambda = \nu^{2},\, l(\lambda) \leq 2N$;}\\ 0, &\text{otherwise}, \end{cases} \eeq to obtain \beq \E_{\Sp(2N)}e_{\mu}(M) = \sum_{\lambda = 2 \nu}K_{\lambda \mu}. \eeq Next we observe that the condition $\lambda =2 \nu$ is equivalent to the condition that the associated tableau have all rows of even length. Now we recall that a version of Knuth correspondence introduced by Burge \cite{burge} establishes a bijection between symmetric matrices of nonnegative integers with column sums given by $\mu$ and tableaux of any shape with content $\mu$; and that furthermore in this correspondence the number of odd diagonal elements of the matrix is equal to the number of odd length rows of the corresponding tableau. We finally note that symmetric nonnegative matrix whose diagonal elements are all even corresponds to an adjacency matrix of a graph with loops and multiple edges. This completes the proof of Theorem \ref{thm:spms}. %\newpage %$\begin =\left[\begin{array}{cccc} E&0 &\hdots &0 \\ %0&E&\hdots &0\\ \vdots&\vdots&\ddots&\vdots \\ %0&0&\hdots&E\end{array}\right], \; E=\left[\begin{array}{cc}0&1\\ %-1&0\end{array}\right] \begin{remark} The limiting distiribution of the secular coefficients for both orthogonal and symplectic group can be obtained in exact analogy with the Proposition \ref{prop:norm} by invoking Newton's identities to express the secular coefficients in terms of power sums and then using limit theorems for power sums proved in \cite{DiEv1, DS94}. The analogues of Theorem \ref{bcagzeta} for $L$-functions with orthogonal and symplectic symmetries are proved in \cite{BCAG1}. \end{remark} \section{Secular coefficients of GUE matrices and matching polynomials} \label{sec:gue} %\subsection{Connection with matching polynomials} Let $\mu_N(dM)$ denote the GUE measure on the space $\cH_N$ of hermitian $N\times N$ matrices; ``G'' and ``U'' refer to it being Gaussian and $U(N)$-invariant. If we denote the matrix elements by $m_{jk}=x_{jk}+iy_{jk}$, \begin{equation} \label{7:1} \mu_N(dM) =\prod_{1\leq j < k\leq N} \frac{1}{\pi} e^{-|m_{jk}|^2} dx_{jk}dy_{jk} \prod_{k=1}^{N} \frac{1}{\sqrt{2}\pi} e^{-\frac{x_{kk}^2}{2}} dx_{kk}. \end{equation} The eigenvalues of a matrix $M$ chosen at random with respect to \eqref{7:1} are distributed with the density \beq \label{7:2} P_N(\lambda_1, \ldots, \lambda_N) = \prod_{1\leq j < k\leq N} (\lambda_j -\lambda_k)^2 \prod_{k=1}^{N}\frac{e^{-\frac{\lambda_k^2}{2}}}{k!\sqrt{2}\pi}. \eeq We will denote the Vandermonde determinant by $\Van(f_1, \ldots, f_N)$: \beq \label{7:3} \Van(f_1, \ldots, f_N)=\prod_{1\leq j < k\leq N} (f_j -f_k). \eeq Now consider the characteristic polynomial \beq \label{9:1} P_M(x)=\det(I x-M)=\prod_{j=1}^{N}(x-\lambda_j)= \sum_{j=0}^{N}\Sc_j(M)x^{N-j}(-1)^j, \eeq where $\Sc_j(M)$ is the $j$-th secular coefficient. We are interested in moments of $\Sc_j(M)$ with respect to $\mu_N(M)$. The combinatorial significance of the higher moments of the first secular coefficient $\Sc_1(M)$, i.e. the moments of traces, has been thoroughly investigated, starting with the work of Harer and Zagier \cite{HZ}; see also \cite{HSS, GoJa95}. Let $$C(k, N) = \E_{\mu_N} \Tr M^{2k}.$$ Harer and Zagier have shown that this integral is always a positive integer and using the Wick formula obtained the following combinatorial interpretation: \beq C(k, N) = \sum_{0 \leq g \leq k/2} \epsilon_g(k) N^{k+1-2g}, \eeq where $\epsilon_g(k)$ denotes the number of ways to obtain an orientable surface of genus $g$ by identifying in pairs the sides of $2k$-gon. They also proved the following formula for $C(k, N)$ by using rather complicated manipulations with generating functions: \beq \label{eq:ckn} C(k, N) = (2k-1)!!\sum_{j=0}^{k} \binom{N}{j+1}\binom{k}{j}2^j .\eeq We refer to \cite{zvon} for an elegant account of this work and further developments. In one of his last papers \cite{kerov} Sergei Kerov gave a simple combinatorial interpretation of the numbers $C(k, N)$ in terms of rook polynomials or, equivalently, in terms of appropriate involutions. As we show below the combinatorial significance of the moments of higher secular coefficients can also be obtained by considering appropriate involutions, or equivalently, \emph{matching polynomials}. We start with the following simple observation (which cannot possibly be new). \begin{proposition} \label{pr:9} Notation being as above we have $$ \E_{\mu_N}(P_M(x))=\int P_M(x)d \mu_N(x) = h_N(x), $$ where $h_N(x)$ is the $N$th normalized Hermite polynomial (see the definition in Remark \ref{rem:herm} below). \end{proposition} {\bf Proof:} This follows from Heine's formula \cite[p. 27]{GS39}, which can be stated as follows: %{\bf Heine's Formula:} Let $\alpha(x)$ be a weight function on the interval $[a, b]$ (where we allow $a=-\infty, b=+\infty$). Then \beq \label{11:1} p_N(x) = \underbrace{ \int_{a}^{b} \ldots \int_{a}^{b}}_{N}\prod_{i=1}^{N}(x-x_i) \prod_{i K$, \beq |\frac{\sigma(G) p(G, k)}{p(G)}- \frac{1}{\sqrt{2 \pi}} e^{-(k-m(G))^2/2 \sigma^{2}(G)}| < \frac{L}{\sqrt{\sigma(G)}}. \eeq \end{utheorem} We also easily obtain the following result which can be viewed as a very simple instance of the universality phenomenon in random matrix theory. \begin{proposition} \label{prop:nongaus} Let M be a random symmetric matrix of size $N$ with zeroes on the main diagonal and off-diagonal entries taking values $\{+1, -1\}$ with probability $\frac{1}{2}$. Then the expected value of the characteristic polynomial of $M$ is $h_N(x)$. \end{proposition} {\bf Proof:} Let $G$ be a graph with $n$ vertices and $m$ edges. Let $u=(u_1, \dots, u_m)\in\{-1, 1\}^m$. Let $G_u$ be the weighted graph obtained from $G$ by associating the weight $u_i$ with the edge $e_i$ for $i=1,\dots, m.$ Let further $P(G_u)$ be the characteristic polynomial of $G_u$. It was proved by Godsil and Gutman \cite{GG} (Corollary 2.2) that \beq \alpha(G)=2^{-m}\sum_{u}P(G_{u}), \eeq where the summation is ranging over all $2^m$ distinct $m$-tuples $u$. The proposition follows at once by applying this result to the complete graph $G=K_N$ and recalling that $\alpha(K_N)=h_N$. \begin{remark} In fact it is easy to see that the proof of Corollary 2.2. in \cite{GG} applies to any symmetric distribution of the entries. \end{remark} Now we prove the following generalization of Proposition \ref{pr:9}: \begin{theorem} \label{th:9} Let $2k$ be a nonnegative integer. Notation being as above, we have $$ \E_{\mu_N}(P_M^{2k}(x))= h_N^{(k)}(x), $$ where $h_N^{(k)}(x)$ is the $N$th monic generalized Hermite polynomial. These are orthogonal polynomials with respect to the weight $|x|^{2k}e^{-x^2}$. \end{theorem} We will give explicit formulas for generalized Hermite polynomials and will discuss their combinatorial significance following the proof of the Theorem. % Note that %$$ %\Eh(P_M^k(x))= \sum_{j_1, \ldots, j_k}\Eh[\Sc_{j_1}(M)\ldots %\Sc_{j_k}(M)]x^{Nk-\sum_{l=1}^{k}j_l}(-1)^{\sum_{l=1}^{k}j_l}; $$ %we will discuss the combinatorial properties of the generalized %Hermite polynomials at the end of the section. {\bf Proof:} %\subsection{Higher Moments} Consider the product of characteristic polynomials at $k$ values of $x$ and integrate it with respect to $\mu_N$: \beq \label{15:1} \begin{split} f_k(x_1, \ldots, x_k)&=\E_{\mu_N}[P_M(x_1) \ldots P_M(x_k)]\\ &\sum_{j_1, \ldots, j_k}\E_{\mu_N}[\Sc_{j_1}(M)\ldots \Sc_{j_k}(M)]x_1^{N-j_1}\ldots x_{k}^{N-j_k} (-1)^{j_1+\ldots + j_k}\\ &=\frac{1}{Z_N} \underbrace{ \int_{-\infty}^{\infty} \ldots \int_{-\infty}^{\infty}}_{N}\prod_{i=1}^{N}d \mu(\lambda_j) \Van^2(\lambda_1, \ldots, \lambda_N)\prod_{i=1}^k\prod_{j=1}^N(x_i-\lambda_j), \end{split} \eeq where $Z_N$ is the normalization in the definition of $\mu_N$: \beq \label{15:2} \mu_N=\frac{1}{Z_N} e^{-\frac{1}{2}\sum_{i=1}^N \lambda_i^2}\Van^2(\lambda_1, \ldots, \lambda_N) \eeq and $$ d\mu(\lambda)=e^{-\frac{\lambda^2}{2}}d \lambda. $$ As is well known \cite{zvon}, \beq \label{15:3} Z_N=\prod_{k=1}^N k! \eeq If we set all of the $x_1, \ldots, x_k$ to be equal, we obtain a generating function $f_k(x)$: \beq \label{17:1} f_k(x)= \Eh(P_M^k(x))= \sum_{j_1, \ldots, j_k}\Eh[\Sc_{j_1}(M)\ldots \Sc_{j_k}(M)]x^{Nk-\sum_{l=1}^{k}j_l}(-1)^{\sum_{l=1}^{k}j_l}. \eeq Our approach up to \eqref{21:1} follows the method in \cite{BH00}. In formula \eqref{15:1} we can rewrite the integrand as follows: \beq \label{17:2} \Van(\lambda_1, \ldots, \lambda_N)\prod_{i=1}^{k}\prod_{j=1}^{N}(x_i-\lambda_j)= \frac{\Van(\lambda_1, \ldots, \lambda_N; x_1, \ldots, x_k)}{\Van(x_1, \ldots, x_k)}. \eeq Furthermore, we can express $\Van(\lambda_1, \ldots, \lambda_N)$ as the determinant \beq \label{17:3} \Van(\lambda_1, \ldots, \lambda_N)=\det[p_n(\lambda_j)]_{1 \leq j \leq N}^{0 \leq n \leq N-1}, \eeq where $p_n(x)$ are arbitrary monic polynomials of degree $n$. Combining \eqref{17:3} with \eqref{17:2} we can rewrite the latter as follows \beq \label{19:1} \Van(\gl_1, \ldots, \gl_N; x_1, \ldots, x_k)=\det[p_{\alpha}(v_{\beta})], \eeq where $$ \begin{cases} 0 \leq &\alpha \leq N+k-1\\ 1 \leq &\beta \leq N+k \end{cases} $$ and $$ v_{\beta}= \begin{cases} \gl_{\beta}, &\text{if $\beta \leq N$;}\\ x_{\beta-N}, &\text{if $N < \beta \leq N+k$;}. \end{cases} $$ If we now choose the polynomials $p_n$ to be orthogonal with respect to the measure $d \mu(\gl)=e^{-\frac{\gl^2}{2}}$, i.e. choose them to be \emph{monic} Hermite polynomials $h_n$ we obtain after integrating over the $N$ eigenvalues: %$$ \begin{align*} &f_k(x_1, \ldots, x_k) =\\ &\frac{1}{Z_N} \underbrace{ \int_{-\infty}^{\infty} \ldots \int_{-\infty}^{\infty}}_{N}\prod_{i=1}^{N}d \mu(\lambda_j) \Van(\lambda_1, \ldots, \lambda_N;x_1, \ldots, x_k) \Van(\lambda_1, \ldots, \gl_N)\\ &=\frac{N! \prod_{n=0}^{N-1}n!}{Z_N} \det[h_{\alpha}(x_{\beta})]_{1 \leq \beta \leq k}^{N \leq \alpha \leq N+k-1}. \end{align*} %$$ Now \eqref{15:3} and \eqref{12:3} imply that the factor $\frac{N!\prod_{n=0}^{N-1}n!}{Z_N}$ is equal to $1$, so we obtain \beq \label{21:1} f_k(x_1, \ldots, x_k)= \frac{1}{\Van(x_1, \ldots, x_k)}\det \left| \begin{matrix} h_N(x_1) & h_{N+1}(x_1)& \dots & h_{N+k-1}(x_1)\\ h_N(x_2) & h_{N+1}(x_2)& \dots & h_{N+k-1}(x_2)\\ \vdots & \vdots & \ddots & \vdots \\ h_N(x_k) & h_{N+1}(x_k)& \dots & h_{N+k-1}(x_k) \end{matrix} \right|. \eeq If we now set all $x_1=\dots=x_k=x$ in \eqref{21:1} we get: \beq \label{23:1} \begin{split} f_k(x)&=\frac{(-1)^{\frac{k(k-1)}{2}}}{\prod_{j=0}^{k-1}j!} \det \left| \begin{matrix} h_N(x) & h_{N+1}(x)& \dots & h_{N+k-1}(x)\\ h'_N(x) & h'_{N+1}(x)& \dots & h'_{N+k-1}(x)\\ \vdots & \vdots & \ddots & \vdots \\ h'_N(x) & h'_{N+1}(x)& \dots & h'_{N+k-1}(x) \end{matrix} \right|\\ &=C_k W\left(h_N(x), h_{N+1}(x), \dots, h_{N+k-1}(x)\right). \end{split} \eeq Here $W\left(h_N(x), h_{N+1}(x), \dots, h_{N+k-1}(x)\right)$ is the \emph{Wronskian} of polynomials $$h_N(x), h_{N+1}(x), \dots, h_{N+k-1}(x).$$ Now by the Christoffel formula \cite[p.30]{GS39}, $$ W\left(h_N(x), h_{N+1}(x), \dots, h_{N+k-1}(x)\right) = h_N^{(k/2)}(x), $$ where $h_N^{(k/2)}(x)$ are monic \emph{generalized Hermite polynomials} \cite[p.156-157]{Chih}, orthogonal with respect to the weight $|x|^{k}e^{-x^2}$. This concludes the proof of Theorem \ref{th:9}. Monic generalized Hermite polynomials $h_N^{(k)}(x)$ are related to generalized Hermite polynomials $H_n^{(k)}(x)$ by the following formula (cf. \eqref{13:3}): \beq \label{13:3gen} h_n^{(k)}(x)=2^{-\frac{n}{2}}H_n^{(k)}(\frac{x}{\sqrt{2}}). \eeq Generalized Hermite polynomials where defined by G. Szeg\"{o}\cite[p.380, Problem 25]{GS39} and studied by Chihara \cite{chiph} in his Ph.D. thesis. Generalized Hermite polynomials can be expressed in terms of Laguerre polynomials as follows: $$ H_{2n}^{(k)}(x)=(-1)^{k}2^{2n}n!L_n^{k-\frac{1}{2}}(x^2), $$ $$ H_{2n+1}^{(k)}(x)=(-1)^{k}2^{2n+1}n!L_n^{k+\frac{1}{2}}(x^2). $$ Recall that Laguerre polynomials \cite[p. 100]{GS39}, $L_n^{\alpha}(x)$ with $\alpha > -1$ are orthogonal on $[0, \infty)$ with respect to the weight $e^{-x} x^{\alpha}$; they are explicitly given by \beq L_n^{\alpha}(x)=\sum_{j=0}^{n}\binom{n+\alpha}{n-j}\frac{(-x)^j}{j!}. \eeq The first few generalized Hermite polynomials are as follows: $$ H_0^{(k)}(x)=1. $$ $$ H_1^{(k)}(x)=2x. $$ $$ H_2^{(k)}(x)=4 x^2-2(1+2k). $$ $$ H_3^{(k)}(x)=8x^3-4(3+2k)x. $$ $$ H_4^{(k)}(x)=16x^4-16(3+2k)x^2+4(1+2k)(3+2k). $$ \vskip 5pt The connection between Laguerre polynomials and rook placements goes back to Kaplansky and Riordan~\cite{KR46, JR58}. Combinatorial properties of generalized Hermite polynomials $H_n^{(k)}(x)$ were studied by Strehl \cite{VS}; we summarize his results in \eqref{vst1} and \eqref{vst2} below. First of all, we note that the number of $j$-matchings in a complete graph $K_N$, figuring in Corollary \ref{cor:mat} is equal to the number of involutions of $S_N$ having $j$ transpositions. Thus, denoting the set of involutions of the set $\{1, \dots, N \}$ by $\Inv_{[N]}$, and for any $\sigma \in \Inv_{[N]}$ letting $\fix(\sigma)$ stand for the number of fixed points and $\trans(\sigma)$ stand for the number of transpositions, we have the following alternative description of normalized Hermite polynomials $h_N(x)$: \beq h_N(x)=\sum_{\sigma \in \Inv_{[N]}} x^{\fix(\sigma)} (-1)^{\trans(\sigma)}. \eeq We now give a parallel combinatorial description of $h_N^{(k)}$. Let $$[-N,N]=\{-N, \dots, -1, 1,\dots, N\}$$ and $$[-N,N]_0=\{-N, \dots, -1, 0, 1,\dots, N\}.$$ Denote by $\Inv_{[-N,N]}$ the set of involutions of $[-N, N]$ (and by $\Inv_{[-N,N]_0}$ the set of involutions of $[-N, N]_0$) and for $\sigma \in \Inv_{[-N, N]}$ let $\cyc(\sigma)$ stand for the number of cycles in the action of $\sigma$ combined with the action of the ``mirror'' involution sending each $i$ to $-i$ for all $i= 1, \dots, N$. Then \beq \label{vst1} h_{2N}^{(k)}(x)=\sum_{\sigma \in \Inv_{[N, N]}} (2k+1)^{\cyc(\sigma)} x^{\fix(\sigma)} (-1)^{\trans(\sigma)}, \eeq and \beq \label{vst2} h_{2N+1}^{(k)}(x)=\sum_{\sigma \in \Inv_{[N, N]_0}} (2k+1)^{\cyc(\sigma)} x^{\fix(\sigma)} (-1)^{\trans(\sigma)}. \eeq \section{Concluding Remarks} \begin{enumerate} \item It should be possible to prove part (a) of Theorem \ref{stan}, purely probabilistically from the expression for $H_k(j)$ as moments of the polynomial in the i.i.d. Gaussians given in Proposition \ref{prop:norm}. On the other hand, it would be interesting to understand the probabilistic implications of part(b) of Theorem \ref{stan}. \item We also note that $E_{U(N)}|\Sc_j(M)|^{2 \nu}= H_{\nu}(j)$ makes sense for any real values of $\nu$ and that the resulting expression can be thought of as a generalization of $H_k(j)$ for integral values of $k$. The methods based on using symmetric functions theory do not easily extend to the non-integral situation; however the methods based on using the Toeplitz determinants, as discussed in Section \ref{sec:toep}, do apply. %In more detail, it was %proved by Diaconis and Shahshahani, that $\Tr M^j \sim \sqrt{j} %Z$, where $Z$ is the standard complex normal. So we have, for %example, using the relation between $e_j$ and $p_j$, that $$ %\Sc_3(M) \sim Z_1^3 -3\sqrt{2}Z_1Z_2+2\sqrt{3}Z_3 .$$ %The expression in terms of Gaussians (as well as expression in %terms of Topelitz determinant) might perhaps also be useful in %computing the leading coefficient of $H_k(j)$ (the record so far %is $k=9$). \vskip 10pt \item The type of determinant given in \eqref{21:1} appears in the work of Karlin and McGregor \cite{KM57} in connection with coincidence probabilities so there might be connections with queues, etc. \vskip 10pt \item It would be very interesting to generalize the universality result of Proposition \ref{prop:nongaus} to the higher moments, in particular to $h_N^k$ and to the expression for $C(k, N) = \E_{\mu_N} \Tr(M)^{2k}$. \vskip 10pt \item It would be interesting to extend the results of Section 5 to other Gaussian ensembles. \vskip 10pt \item In the limit (suitably interpreted) as $N \to \infty$, the coefficients of CUE and GUE matrices should have the same universal behavior. The GUE case seems to be more amenable to Riemann-Hilbert asymptotic analysis. \vskip 10pt \item Finally we remark that a unitary matrix $M$ is conjugate on the one hand to the diagonal matrix with eigenvalues on the diagonal, and on the other hand to the Frobenius, or companion matrix, with first row consisting of the secular coefficients, ones below the main diagonal, and remaining entries zero. This strongly suggests that secular coefficients are (as Gian-Carlo Rota might have put it) ``nearly equi-primordial'' with the eigenvalues and indicates that computing their moments is not the only, and perhaps not the most natural, question to ask. \end{enumerate} %\begin{remark} %The moments of the determinant of GUE matrices have been %investigated in \cite{}. %\end{remark} %\noindent {\bf Proposed Research:} T \begin{thebibliography}{99} \bibitem{AD99} D. Aldous, P. Diaconis, \emph{Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson\ theorem}, BAMS, \textbf{36}, 1999, 413-432. \bibitem{ADG66} H. Anand, V. G. Dumir, and H. Gupta, \emph{A combinatorial distribution problem}, Duke. Math. J., \textbf{33}, 1966, 757-770. \bibitem{A1883} C. Andr\'{e}ief, \emph{Note sur une relation entre les int\'{e}grales d\'{e}finies des produits des fonctions}, M\'{e}m. de la Soc. Sci. Bordeaux, \textbf{3}, 1883, 1-14. \bibitem{BDJ99} J. Baik, P.Deift, and K. Johansson, \emph{On the distribution of the length of the longest increasing subsequence of random permutaions}, J. Amer. Math. Soc., \textbf{12}, 1999, 1119-1178. \bibitem{BR01} J. Baik and E. Rains, \emph{Symmetrized random permutations}, Random Matrix Models and their Applications, eds. P. Bleher and A. Its, MSRI Publications \textbf{40}, Cambridge University Press, 1999, 91-147. \bibitem{BP99} A. Barvinok and J. E. Pommersheim, \emph{An algorithmic theory of lattice points in polyhedra}, New Perspectives in Algebraic Combinatorics, MSRI Publications \textbf{38}, Cambridge University Press, 2001, 1-19. \bibitem{MB97} M. Bona, \emph{A New Proof of the Formula for the Number of the $3 \times 3$ magic squares}, Mathematics Magazine \textbf{70}, 1997, 201-203. \bibitem{BH00} E. Br\'{e}zin and S. Hikami, \emph{Characteristic polynomials of random matrices}, Comm. Math. Phys., \textbf{214}, 2000, 111-135. \bibitem{BD02} D. Bump and P. Diaconis, \emph{Toeplitz minors}, Journal of Combinatorial Theory A, \textbf{97}, 2002, 252-271. \bibitem{burge} W. Burge, \emph{Four correspondences between graphs and generalized Young tableaux}, J. of Combin. Theory (A), \textbf{17}, 1974, 12-30. \bibitem{CR99} C. Chan and D. Robbins, \emph{On the volume of the polytope of doubly stochastic matrices}, Experimental Mathemtics, \textbf{8}, 1999, 291-300. \bibitem{chiph} T. S. Chihara, \emph{Generalized Hermite polynomials}, Thesis, Purdue, 1955. \bibitem{Chih} T.S. Chihara, \emph{An introduction to orthogonal polynomials}, Gordon and Breach, 1978. \bibitem{CF00} J. B. Conrey and D. W. Farmer, \emph{Mean values of $L$-functions and symmetry}, Int. Math. Res. Notices, \textbf{17}, 2000, 883-908. \bibitem{CFKRS1} J. B. Conrey, D. W. Farmer, J. P. Keating, M. O. Rubinstein, and N. C. Snaith, \emph{Integral moments of zeta and L-functions}, preprint 2002. \bibitem{CFKRS2} J. B. Conrey, D. W. Farmer, J. P. Keating, M. O. Rubinstein, and N. C. Snaith, \emph{Autocorrelation of random matrix polynomials}, preprint 2002. \bibitem{BCAG} B. Conrey and A. Gamburd, \emph{Pseudomoments of the Riemann zeta-function and pseudomagic squares}, preprint, 2003. \bibitem{BCAG1} B. Conrey and A. Gamburd, \emph{Integral moments of the partial sums of $L$-functions and symmetry}, preprint, 2003. \bibitem{CrDy} M. Cryan and M. Dyer, \emph{A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant}, Proceedings of the 34th annual ACM Symposium on Theory of Computing, 2002, 240-249. \bibitem{JDLBS} J. DeLoera and B. Sturmfels, \emph{Algebraic unimodular counting}, preprint. \bibitem{DiEv1} P. Diaconis and S. Evans, {Linear Functionals of Eigenvalues of Random Matrices.} Transactions Amer. Math. Soc. \textbf{353}, 2001, 2615--2633. \bibitem{DG} P. Diaconis and A. Gangolli, \emph{Rectangular arrays with fixed margins}, in: D. Aldous, P. P. Varaiya, J. Spencer, J. M. Steele (Eds.), Discrete Probability and Algorithms, IMA Volumes Math. Appl., \textbf{72}, 1995, 15-41. \bibitem{DS94} P.Diaconis and M.Shahshahani, \emph{On the eigenvalues of random matrices}, J. Appl. Probab., \textbf{31A}, 1994, 49-62. \bibitem{DKM97} M. Dyer, R. Kannan, J. Mount, \emph{Sampling contingency tables}, Random Structures and Algorithms, \textbf{10}, 1997, 487-506. \bibitem{EE73} E. Ehrhart, \emph{Sur les carr\'{e}s magiques}, C. R. Acad. Sci. Paris, \textbf{227 A}, 1973, 575-577. \bibitem{EE77} E. Ehrhart, \emph{Polyn\^{o}mes arithm\'{e}tiques et M\'{e}thode des Poly\`{e}dres en combinatoire}, Birkhäuser, 1977. %\bibitem{JEG} %Jackson, Even, Gillis \bibitem{godsil1} C. D. Godsil, \emph{Matching behavior is asymptotically normal}, Combinatorica, \textbf{1}, 1981, 369-376. \bibitem{GG} C. D. Godsil and I. Gutman, \emph{On the matching polynomial of a graph}, Coll. Math. Soc. J. Bolyai, \textbf{25}, 1978, 241-249. \bibitem{GoJa95} I. P. Goulden and D. M. Jackson, \emph{Combinatorial constructions for integrals over normally ditributed random matrices}, Proceedings of the AMS, \textbf{123}, 1995, 995-1003. \bibitem{Ha1} F. Haake, \emph{Quantum signatures of chaos}, Springer, 2000. \bibitem{Ha2} F. Haake, M. Kus, H. -J. Sommers, H. Schomerus, K. Zyckowski, \emph{Secular determinants of random unitary matrices}, J. Phys. A.: Math. Gen. \textbf{29}, 1996, 3641-3658. \bibitem{HSS} P. Hanlon, R. Stanley, J. Stembridge, \emph{Some combinaotial aspects of the spectra of normally distributed random matrices}, in Hypergeometric Functions on Domains of Positivity, Jack Polynomials, and Applications, D. St. Richards, ed., Contemp. Math., \textbf{138}, 1992, 151-174. \bibitem{HZ} J. Harer and D. Zagier, \emph{The Euler characteristic of the moduli space of curves}, Invent. Math., \textbf{85}, 1986, 457-485. \bibitem{HeLi72} O. J. Heilmann and E. H. Lieb, \emph{Theory of monomer-dimer systems}, Commun. Math. Physics, \textbf{25}, 1972, 190-232. \bibitem{HKO1} C. P. Hughes, J. P. Keating, and N. O'Connell, \emph{Random matrix theory and the derivative of the Riemann zeta function}, Proc. R. Soc. London A, \textbf{456}, 2000, 2611-2627. \bibitem{HKO2} C. P. Hughes, J. P. Keating, and N. O'Connell, \emph{On the characteristic polynomial of a random unitary matrix}, Comm. Math. Phys. , \textbf{220}, 2001, 429-451. \bibitem{IRS} N. F. J. Inglis, R. W. Richardson and J. Saxl, \emph{An explicit model for the complex representations of $S_n$}, Arch. Math. \textbf{54}, 1990, 258-259. \bibitem{Johan2} K. Johansson, \emph{On Random Matrices from the Compact Classical Groups} Ann. Math. \textbf {145}, 1997, 519--545. \bibitem{KR46} I. Kaplansky and J. Riordan, \emph{The problem of the rooks and its applications}, Duke Math. J., \textbf{13}, 1946, 259-268. \bibitem{KM57} S. Karlin and J. McGregor, \emph{The diffferential equations of birth and death processes and the Stieltjes moment problem}, Transactions AMS, \textbf{85}, 1957, 489-546. \bibitem{KS00} J. P. Keating and N. C. Snaith, \emph{Random matrix theory and L-functions at $s=\frac{1}{2}$}, Commun. Math. Phys., \textbf{214}, 2000, 91-110. \bibitem{kerov} S. Kerov, \emph{Rooks on Ferrers boards and matrix integrals}, J. Math. Sci., \textbf{96}, 1999, 3531-3536. \bibitem{knuth} D. Knuth, \emph{Permutations, matrices, and generalized Young tableaux}, Pacific J. Math., \textbf{34}, 1970, 709-727. \bibitem{Mac} I. G. Macdonald, {\em Symmetric functions and Hall polynomials}, Second edition, Oxford University Press, New York, 1995. \bibitem{PM15} P. A. MacMahon, \emph{Combinatory Analysis}, Cambridge University Press, 1915. \bibitem{JM00} J. Mount, \emph{Fast unimodular counting}, Combin. Probab. Comput. \textbf{9}, 2000, 277-285. \bibitem{AO00} A. Okounkov, {\em Random matrices and random permutations}, Internat. Math. Res. Notices, \textbf{20}, 2000, 1043-1095. \bibitem{ER98} E. Rains, {\em Normal limit theorems for symmetric random matrices}, Probab. Theory Relat. Fields, \textbf{112}, 1998, 411-423. \bibitem{JR58} J. Riordan, \emph{An Introduction to Combinatorial Analysis}, Wiley, New York, 1958. \bibitem{BrSa} B. Sagan, {\em The Symmetric Group}, 2nd edition, Springer, 2000. %\bibitem{JS80} %J. H. Spencer, %\emph{Counting magic squares}, %Amer. Math. Monthly, textbf{87}, 1980, 397-399. \bibitem{SS60} P. Schmidt and F. Spitzer, \emph{The Toeplitz matrices of an arbitrary Laurent polynomial}, Math. Scand., \textbf{8}, 1960, 15-38. \bibitem{RS73} R. Stanley, \emph{Linear homogeneous diophantine equations and magic labelings of graphs}, Duke Math. J., \textbf{40}, 1973, 607-632. \bibitem{RS74} R. Stanley, \emph{Combinatorial reciprocity theorems}, Adv. in Math., \textbf{14}, 1974, 194-253. \bibitem{stanley86} R.~P. Stanley. {\em Enumerative Combinatorics, Vol I.} Wadsworth \& Brooks/Cole, Monterey, California, 1986. \bibitem{stanleyv2} R.~Stanley. {\em Enumerative Combinatorics, Vol. 2}. Cambridge University Press, 1999. \bibitem{VS} V. Strehl, \emph{Polyn\^{o}mes d'Hermite g\'{e}n\'{e}ralis\'{e}s et identit\'{e}s de Szeg\"{o} - une version combinatoire}, in Springer Lecture Notes 1171, pp.128-138. \bibitem{GS39} G. Szeg\"{o}, \emph{Orthogonal Polynomials}, AMS, 1967. \bibitem{TrWi3}C. Tracy and H. Widom, {\em On the Relations Between Orthogonal, Symplectic and Unitary Ensembles.}, Jour. Statist. Phys. \textbf {94}, 1999 347--363. \bibitem{TW02} C. Tracy and H. Widom, {\em Distribution Functions for Largest Eigenvalues and Their Applications}, Proceedings of the International Congress of Mathematicians, Beijing 2002, Vol. I, ed. LI Tatsien, Higher Education Press, Beijing 2002, 587-596. \bibitem{zvon} A. Zvonkin, {\em Matrix integrals and map enumeration: an accessible introduction}, Mathl. Comput. Modelling, \textbf{26}, 1997, 281-304. \end{thebibliography} \end{document} .