\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<j}(x_i-x_j)^2\prod_{i=1}^{N}\alpha(x_i)dx_i \eeq defines
orthogonal polynomials of degree $N$ with weight function
$\alpha(x)$.

Combining \eqref{11:1} with \eqref{7:2} and \eqref{9:1} yields the
proof of the proposition.

\begin{remark} \label{rem:herm}
Hermite polynomials $H_n(x)$ are orthogonal with respect to
$e^{-x^2}$ and can be defined by

\beq \label{13:1}
 H_n(x)=(-1)^n e^{x^2}\frac{d^n}{dx^n}e^{-x^2}.
\eeq

Explicitly we have:
 \beq \label{13:2}
H_n(x)= \sum_{k=0}^{[n/2]}\frac{(-1)^k n!}{k!(n-2k)!} (2x)^{n-2k}.
\eeq

The first few Hermite polynomials are as follows:

$$
H_0(x)=1.
$$

$$
H_1(x)=2x.
$$

$$
H_2(x)=4 x^2-2.
$$

$$
H_3(x)=8x^3-12x.
$$

$$
H_4(x)=16x^4-48x^2+12.
$$



Normalized Hermite polynomials, $h_N(x)$ are defined by \beq
 \label{13:3}
  h_n(x)=2^{-\frac{n}{2}}H_n(\frac{x}{\sqrt{2}}),
  \eeq

or explicitly:

\beq \label{13:4}
 h_n(x)=\sum_{k=0}^{[n/2]}
 \frac{(-1)^k n!}{k!(n-2k)!} \frac{x^{n-2k}}{2^k}.
\eeq

The first few normalized Hermite polynomials are as follows:

$$h_0(x)=1.$$

$$h_1(x)=x.$$

$$h_2(x)=x^2-1.$$

$$h_3(x)=x^3-3x.$$

$$h_4(x)=x^4-6x^2+3.$$

The polynomials $\frac{1}{\sqrt{n!}}h_n(x)$ are orthonormal with
respect to the weight $\frac{1}{\sqrt{2 \pi}}e^{-\frac{x^2}{2}}$
and satisfy the following orthogonality relations: \beq
\label{12:3} \int_{-\infty}^{\infty}
h_n(x)h_m(x)e^{-\frac{x^2}{2}} = \sqrt{2 \pi}n! \delta_{nm} \eeq

\end{remark}


To bring out the combinatorial significance of Proposition
\ref{pr:9}, let us recall the following definition.

\begin{definition} \label{def:mp}
Given a graph $G$ with $n$ vertices and $m$ edges, let $p(G, k)$
denote the number of ways in which one can select $k$ independent
edges in $G$.  Let further $p(G, 0)=1$ for all $G$.  Then
\emph{the matching polynomial} $\alpha(G)$ of the graph $G$ is
given by \beq \alpha(G)=\alpha(G, x)=\sum_{0}^{m}(-1)^k p(G, k)
x^{n-2k}. \eeq
\end{definition}

Heilmann and Lieb \cite{HeLi72}  (see also  Godsil and Gutman
\cite{GG}) have proved that for a complete graph $K_n$ the
matching polynomial $\alpha(K_n, x) =h_n(x)$; this immediately
implies the following corollary.

\begin{corollary} \label{cor:mat}
Notation being as above, $\E_{\mu_N} |\Sc_j(M)|$ is equal to the
number of $j$-matchings in the complete graph $K_N$:
 %and to the
%number of involutions of $S_N$ having $j$ transpositions:
\beq \label{11:2} \E_{\mu_N} |\Sc_j(M)|=\frac{N!}{2^{j}j!(n-2j)!}.
\eeq
\end{corollary}


We can apply the known results about matching polynomials to
$\E_{\mu_N} |\Sc_j(M)|$.   For example, the asymptotic normality
of $\E_{\mu_N} |\Sc_j(M)|$, in the sense made precise below,  is
implied by the following result of Godsil:

\begin{utheorem} [Godsil~\cite{godsil1}] Let $G$ be a graph and let $p(G)$ be the total
number of matchings in $G$.  Let $X$ be the random variable whose
value is the number of edges in a randomly chosen matching; denote
by $m(G)$ its mean and by $\sigma(G)$ its standard deviation.
There exist numbers $K$ and $L$ such that for any graph $G$ where
$\sigma(G) > 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}

.
