\documentclass[ALCO,ThmDefs,Unicode]{cedram}

\DeclareMathOperator{\tab}{tab}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Tr}{Trace}
\DeclareMathOperator{\ind}{ind}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\D}{D}



\newcommand{\cB}{\mathcal{B}}
\newcommand{\cb}{\mathcal{b}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cbP}{\ol{\mathcal{P}}}
\newcommand{\cbY}{\ol{\mathcal{Y}}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cY}{\mathcal{Y}}

\newcommand*{\upto}{up to}

\renewcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}


\newcommand{\noi}{\noindent}
\newcommand{\rar}{\rightarrow}
\newcommand{\ds}{}%\displaystyle}
\newcommand{\ol}{\overline}
\newcommand{\seq}{\subseteq}


% author defined ends











%%%%%%%%% a placer avant \begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}


\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur


\author{\firstname{Murali} \middlename{K.} \lastname{Srinivasan}}

\address{Department of Mathematics\\ 
Indian Institute of Technology Bombay\\
Powai, Mumbai 400076, India}


\email{murali.k.srinivasan@gmail.com}


%%%%% Sujet

\keywords{perfect matching association scheme, 
content evaluation of symmetric functions, Gelfand--Tsetlin vectors.}
  

\subjclass{05E10, 05E05, 05E30}


%%%%% Gestion

\DOI{10.5802/alco.104}
\datereceived{2018-08-13}
\daterevised{2019-11-28}
%\daterevised{2019-06-20}
%\datererevised{2019-11-28}
\dateaccepted{2019-11-29}


%%%%% Titre et résumé

\title{The perfect matching association scheme}

\begin{abstract}
We revisit the Bose--Mesner algebra of the perfect matching association
scheme. Our main results are 
\begin{itemize}
\item An inductive algorithm, based on solving linear
equations, to compute the eigenvalues of the
orbital basis elements given the 
central characters of the symmetric groups.

\item Universal formulas,
as content evaluations of symmetric functions, for the eigenvalues of fixed
orbitals. 

\item An inductive construction of an eigenvector (the so called
first Gelfand--Tsetlin vector) in each eigenspace leading to a different
inductive algorithm (not using central characters) 
for the eigenvalues of the orbital basis elements. 
\end{itemize}
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}


\dedicatory{To the memory of Angel, Gandhi, Shadow, and beloved Lucky}
\maketitle


\section{Introduction}\label{Sect1}

In this paper we revisit the Bose--Mesner algebra of the perfect matching
association scheme.
The symmetric group $S_{2n}$ has a natural substitution action on the set
$\cM_{2n}$ of all perfect matchings in the complete graph
$K_{2n}$. The corresponding permutation representation of $S_{2n}$ on
$\C[\cM_{2n}]$ (the complex vector space with $\cM_{2n}$ as basis)   
is multiplicity free
and the (commutative) algebra
$\cB_{2n} = \End_{S_{2n}}(\C[\cM_{2n}])$
is called the Bose--Mesner algebra of the perfect matching
association scheme. The eigenspaces of $\cB_{2n}$, in its left action on
$\C[\cM_{2n}]$, are indexed by even Young diagrams with $2n$ boxes 
(\ie  Young diagrams with $2n$ boxes
having an even number of boxes in every row)
and the orbital basis 
of $\cB_{2n}$ is indexed by even partitions of $2n$ (\ie  partitions of
$2n$ with all parts even). The present work is motivated by the following
two results.

Diaconis and Holmes~\cite{dh} determined all the eigenvalues
of the orbital basis element of $\cB_{2n}$ indexed by the even partition
$(4,2^{n-2})$ of $2n$ (here $(4,2^{n-2})$
denotes the even partition with one part equal to 4 and $n-2$ parts
equal to $2$). 
We generalize this result to all fixed orbitals in Theorem
\ref{mks} below. 

Godsil and Meagher~\cite{gm,gm1} and Lindzey~\cite{l}
write down an eigenvector (using a
quotient argument) belonging to the eigenspace indexed by the even Young
diagram $(2n-2,2)$ with $2n$ boxes, yielding the eigenvalues 
of all orbital basis elements on this eigenspace. 
We generalize this result by giving an inductive procedure to write down an
eigenvector in every eigenspace in Theorem~\ref{mt1} below. This yields a
practical algorithm to compute the eigenvalues 
that we have implemented in Maple, see~\cite{sr}. 
The program computes, reasonably 
efficiently, any given eigenvalue \upto{} $\cB_{40}$. We were able to determine
the entire spectrum of the perfect matching derangement matrix in
$\cB_{2n}$, \upto{} $2n=40$ (see Problem 16.10.1 in~\cite{gm}).

The rest of the introduction gives a more
detailed, although still informal, description of our results.


A partition (or a Young diagram) $\lambda$ is called \emph{even} 
if all parts (or all row lengths) of $\lambda$ are even. 
Clearly, $\lambda=(\lambda_1,\ldots
,\lambda_k) \mapsto 2\lambda=(2\lambda_1,\ldots ,2\lambda_k)$ is a bijection
between the set of all partitions of $n$ (or Young diagrams with $n$ boxes)
and the set of all even partitions of $2n$ (or even
Young diagrams with $2n$ boxes).
Let $\cP$ denote the set of all partitions
and $\cY$ denote the set of all Young diagrams (there is a unique partition
of $0$ and there is a unique Young diagram with $0$ boxes, both denoted
$(0)$).
Let $\cP_n$ denote the set of all partitions of $n$
and let $\cY_n$ denote the set of all Young diagrams with $n$ boxes.
If $\lambda$ is
a partition of $n$ or if $\lambda$ is a Young diagram with $n$ boxes
we write $\lambda\vdash n$ and $|\lambda|=n$ (it will be clear from the
context whether a partition or a Young diagram is meant).

Given a Young
diagram $\lambda$ with $n$ boxes, denote the (complex) irreducible
representation of $S_n$ parametrized by $\lambda$ by $V^{\lambda}$ and
denote the character of $V^{\lambda}$ by $\chi^{\lambda}$.
For $\mu\vdash n$, denote the conjugacy class
of permutations in $S_n$ of cycle type $\mu$
by $C_{\mu}$ and set $\chi^{\lambda}_{\mu}=\chi^{\lambda}(\pi)$, for (any)
$\pi\in C_{\mu}$. We let $k_{\mu}\in \C[S_n]$ (= the group algebra of $S_n$)
denote the sum of elements in $C_{\mu}$.

Let $Z[\C[S_n]]$ denote the center of the group algebra of $S_n$.
Then $Z[\C[S_n]]$ is a semisimple commutative
algebra of dimension $p(n)$, the number of
partitions of $n$, with $\{k_\mu\mid \mu\vdash n\}$ as a basis.
The eigenspaces of this algebra, in its left action on $\C[S_n]$,
are the isotypical
components of $V^\lambda,\;\lambda\vdash n$ in $\C[S_n]$. Let
$\hat{\phi}^{\lambda}_\mu$ denote the eigenvalue of $k_\mu$ on the isotypical
component of $V^\lambda$.
By taking traces we see that
%
\begin{equation} \label{equ}
\hat{\phi}^{\lambda}_{\mu} =
\frac{|C_{\mu}|\chi^{\lambda}_{\mu}}{\dim(V^{\lambda})}.
\end{equation}
%
We call $\hat{\phi}^{\lambda}_{\mu}$ a \emph{central character}.
It can be easily shown to be an integer.
As there are well known explicit formulas for $|C_\mu|$ and
$\dim(V^\lambda)$ we may regard
$\hat{\phi}^\lambda_\mu$ and $\chi^\lambda_\mu$ as being equivalent from the
point of view of computing them.
There are very efficient
practical algorithms, based on the Murnaghan--Nakayama rule, to compute
$\chi^\lambda_\mu$ for fairly large values of $n$ and these algorithms can
be used to calculate $\hat{\phi}^\lambda_\mu$.


We now define an analog of $Z[\C[S_n]]$.
We have the following basic result (see 
\cite{bu,jk,m,s,st}): there is a $S_{2n}$-linear isomorphism
\begin{equation} \label{fr}
\C[\cM_{2n}]  \cong  \oplus_{\lambda\vdash n} V^{2\lambda}.
\end{equation}


Let $\cB_{2n} = \End_{S_{2n}}(\C[\cM_{2n}])$. Since $\C[\cM_{2n}]$ is
multiplicity free, $\cB_{2n}$ is a semisimple commutative 
algebra called the \emph{Bose--Mesner algebra of the perfect 
matching association scheme}. Its
dimension is also $p(n)$. 

From~\eqref{fr} above we have that the common eigenspaces of $\cB_{2n}$, in its
left action on $\C[\cM_{2n}]$, are ($S_{2n}$-isomorphic to)
$V^{2\lambda},\;\lambda\vdash n$.
The orbits of the diagonal action of
$S_{2n}$ on $\cM_{2n}\times \cM_{2n}$, and thus the orbital basis of
$\cB_{2n}$, can be shown to be indexed by even partitions of $2n$ (see
Section~\ref{Sect2}). Given $\mu\vdash n$, let $N_{2\mu}$ denote the orbital basis
element of $\cB_{2n}$ indexed by the even partition $2\mu$ and let
$\hat{\theta}_{2\mu}^{2\lambda},\;\lambda,\mu\vdash n$, 
denote the eigenvalue (which can be shown to be an integer, see Section~\ref{Sect2})
of $N_{2\mu}$ on 
$V^{2\lambda}$. We refer to the $\hat{\theta}_{2\mu}^{2\lambda}$ 
as the \emph{eigenvalues} of $\cB_{2n}$. 
We think of $\hat{\theta}^{2\lambda}_{2\mu}$ as an analog of
$\hat{\phi}^{\lambda}_{\mu}$.

We are interested in combinatorial algorithms (recursive or
direct) that compute $\hat{\theta}^{2\lambda}_{2\mu}$. 
In this paper we give two such
algorithms. The first algorithm, given in Section~\ref{Sect3}, is quite involved
and is not
really suitable for implementation. It however has an important theoretical
consequence which we present in Section~\ref{Sect4}. The second algorithm, given in  
Section~\ref{Sect5}, is extremely simple and is much easier to implement. 
Moreover, there is a parallel and virtually identical algorithm that
calculates the central characters (not using~\eqref{equ} above).
We now discuss these results. 



In Section~\ref{Sect3} we address the following question:
assuming the central characters of $S_n$ as given, how can we
calculate the eigenvalues of the Bose--Mesner algebra.  
We give a recursive combinatorial algorithm for this task.
We show that we can inductively compute the eigenvalues   
of $\cB_2,\cB_4,\ldots ,\cB_{2n}$ from the central characters of
$S_2,S_4,\ldots ,S_{2n}$ by solving systems of linear equations.

Let $\hat{\Theta}(2n)$ denote the eigenvalue table of $\cB_{2n}$, \ie 
$\hat{\Theta}(2n)$ is the $\cY_n\times \cP_n$ matrix with entry in row 
$\lambda$, column $\mu$ given by $\hat{\theta}^{2\lambda}_{2\mu}$.     

\begin{theo} \label{mt} Assume given the central characters of
$S_2, S_4, \ldots , S_{2n}$ and the eigenvalues of $\cB_2, \cB_4, \ldots
,\cB_{2n-2}$. There is an algorithm that determines the eigenvalues of  
$\cB_{2n}$ by solving nonsingular systems of linear equations with
coefficient matrices  
$\hat{\Theta}(2), \hat{\Theta}(4), \ldots , \hat{\Theta}(2n-2)$ and with
right hand sides determined by the central characters of $S_4, S_6, \ldots
,S_{2n}$. 

Thus we can inductively compute the eigenvalues of the Bose--Mesner algebra
from the central characters of the symmetric groups 
by solving linear equations.
\end{theo}
   
Theorem~\ref{mt}, when combined with the work of Corteel, Goupil, and
Schaeffer~\cite{cgs} and Garsia~\cite{g} expressing central
characters (at fixed conjugacy classes) as content evaluations of symmetric
functions, yields similar formulas for the eigenvalues of fixed orbital basis
elements. Let us explain this. First we introduce notation concerning fixed  
classes and symmetric functions.


Let $\cP(2)$ denote the set of
partitions with all parts $\geq 2$. Note that
the unique partition of $0$ belongs to $\cP(2)$.
For $\mu\in \cP(2)$, let
$\ol{\mu}$ be the partition of $|\mu|-\ell(\mu)$ ($\ell(\mu)$ = number of
parts of $\mu$) obtained by subtracting $1$
from every part of $\mu$. The map $\cP(2) \rar \cP$ given by $\mu \mapsto
\ol{\mu}$ is clearly a bijection. Let $\cP(2,n)$ denote the set of all   
$\mu\in\cP(2)$ with $|\mu|\leq n$.

By a nontrivial cycle of a permutation we mean a cycle of length $\geq 2$.
Given $\mu\in \cP(2)$ and $n\geq 1$, define $c_{\mu}(n)$ to be 
element of 
$Z[\C[S_n]]$ given by the sum of all permutations $\pi$ in $S_n$
that have $\mu$ as the
partition determined by the lengths of the nontrivial cycles of $\pi$. Thus,
$c_\mu(n)$ is $0$ if $n<|\mu|$ and is equal to 
$k_{(\mu,1^{n-|\mu|})}$ if $n\geq |\mu|$ (here $(\mu,1^{n-|\mu|})$
denotes the partition of $n$ obtained by adding, to $\mu$, $n-|\mu|$ parts
equal to 1). 
In this notation, $c_{(3)}(n)$ denotes the conjugacy class sum of 3-cycles
in $\C[S_n]$ (which is automatically zero if $n=1,2$), $c_{(0)}(n)$
denotes the identity element of $\C[S_n]$, and 
$\{c_\mu(n)\mid \mu\in\cP(2,n)\}$ is a basis of $Z[\C[S_n]]$.

Given $\mu\in \cP(2)$ and $\lambda\in \cY$, define $\phi^\lambda_\mu$ to be
the eigenvalue of $c_\mu(|\lambda|)$ on $V^\lambda$. That is, if
$\lambda$ has $n$ boxes, $\phi^\lambda_\mu$ is equal to
$\hat{\phi}^\lambda_{(\mu,1^{n-|\mu|})}$ if $n\geq |\mu|$ and is equal to
$0$ if $n<|\mu|$.


Similarly, given $\mu\in \cP(2)$ and $n\geq 1$, define $M_{2\mu}(2n)$ to be the element of
$\cB_{2n}$ given as follows: it is equal to  the orbital basis element
$N_{2(\mu,1^{n-|\mu|})}$ if $n\geq |\mu|$ and it is $0$ if $n<|\mu|$. 
For instance, if $\mu = (3,2,1,1)\vdash 7$ and $\tau =(3,2)$ we can write
the element $N_{2\mu}$ of $\cB_{14}$ as $M_{2\tau}(14)$. The orbital basis
of $\cB_{2n}$ can be written as $\{M_{2\tau}(2n)\mid \tau\in\cP(2,n)\}$.  


Given $\mu\in \cP(2)$ and $\lambda\in \cY$, define $\theta^{2\lambda}_{2\mu}$ to be
the eigenvalue of $M_{2\mu}(2|\lambda|)$ on $V^{2\lambda}$. That is, if
$\lambda$ has $n$ boxes, $\theta^{2\lambda}_{2\mu}$ is equal to
$\hat{\theta}^{2\lambda}_{2(\mu,1^{n-|\mu|})}$ if $n\geq |\mu|$ and is equal to
$0$ if $n<|\mu|$.

We think of $\hat{\phi}^\lambda_\mu$
and $\hat{\theta}^{2\lambda}_{2\mu}$ as
functions of $\lambda, \mu\vdash n$, for fixed $n$ . While considering
$\phi^{\lambda}_{\mu}$ and $\theta^{2\lambda}_{2\mu}$, we regard $\mu$ as
fixed, and think of $\phi^\lambda_\mu$, $\theta^{2\lambda}_{2\mu}$ 
as functions on $\cY$.


The \emph{content}
$c(b)$ of a box $b$ of a Young diagram $\lambda$ is its
$y$-coordinate minus its $x$-coordinate (our convention for drawing Young
diagrams is akin to writing down matrices with $x$-axis running downwards
and $y$ axis running to the right). Thus the content of the boxes in the 
first row (from left to right) are $0,1,2,\ldots $, in the second row are
$-1,0,1, \ldots$, and so on. We denote by 
$c(\lambda)$ the multiset of contents     
of all the boxes of $\lambda$. 
So $c(\lambda)$ has (multiset) cardinality $|\lambda|$.





Let $\Lambda[t]$ denote the algebra, over $\Q[t]$, of symmetric functions in
$\{x_1,x_2,x_3,\ldots \}$. Define $p_0=1$ and
$p_n=\sum_{i}x_i^n,\;n\geq 1$. For $\lambda\in\cP$ the \emph{power sum
symmetric function} $p_{\lambda}$ is defined as follows:
\[
p_{\lambda} = p_{\lambda_1}p_{\lambda_2}\cdots\quad\mbox{if
}\lambda=(\lambda_1,\lambda_2,\ldots ).
\] 
%
The set $\{p_{\lambda}\mid \lambda\in\cP\}$ is a $\Q[t]$-module basis of
$\Lambda[t]$ (\cite{cst2,m,p,sa,st}).

Given $f\in \Lambda[t]$ and $\lambda\in\cY$ with $n$ boxes we
define the \emph{content evaluation} $f(c(\lambda))$ to be the
rational number obtained from $f$ by
setting $t=n,\;x_i=0\mbox{ for }i>n$, and
\[
\{x_1,x_2,\ldots ,x_n\}={}\mbox{(the multiset) }c(\lambda).
\]
Note that this definition makes sense as $f$ is symmetric.

Frobenius proved that the central character at the conjugacy class of
transpositions is given by content evaluation of the symmetric function
$p_1\in \Lambda[t]$ and Ingram proved that the central character at the
conjugacy class of 3-cycles is given by content evaluation of the
symmetric function $p_2-\frac{t(t-1)}{2} \in \Lambda[t]$ (see~\cite{cgs}).
These are \emph{universal formulas} (\ie  independent of 
$\lambda$) made precise as
follows:
\begin{align*}   
\phi^{\lambda}_{(2)} &= p_1(c(\lambda)) = {}\mbox{Sum of contents of all boxes of $\lambda$ },\;\;\lambda\in \cY,\\
\phi^{\lambda}_{(3)} 
&= \left(p_2-\frac{t(t-1)}{2}\right)(c(\lambda))\\
&={}\mbox{Sum of squares of contents of all boxes of $\lambda$}
- \frac{|\lambda|(|\lambda|-1)}{2},\;\;\lambda\in \cY.
\end{align*}
Note that $\phi^\lambda_{(3)}$ is 0 when
$|\lambda|=1,2$. 
These formulas can be generalized to all fixed conjugacy classes.



For each $\mu\in\cP(2)$, it is shown in~\cite{cgs} that
there is a symmetric
function $W_{\mu}\in \Lambda[t]$ such that
$\{W_{\mu}\mid \mu\in\cP(2)\}$ is a $\Q[t]$-module basis of $\Lambda[t]$ and,
for all $\mu\in \cP(2),\;\lambda\in \cY$,
\[
\phi^{\lambda}_{\mu} = W_\mu(c(\lambda)).
\]
%
An algorithm to compute $W_\mu$ is given in~\cite{g}.
We motivate and discuss this result in Section~\ref{Sect4}. 

Diaconis and Holmes~\cite{dh} observed, using Frobenius' result,
that the eigenvalues of the
orbital basis element of $\cB_{2n}$
corresponding to 4-cycles (\ie  the even partition $(4,2^{n-2})$) are given by content
evaluation of the symmetric function $\frac{p_1}{2}- \frac{t}{4}\in
\Lambda[t]$, \ie 
\begin{align*}
\theta^{2\lambda}_{2(2)} &= \left(\frac{p_1}{2}-
\frac{t}{4}\right)(c(2\lambda))\\ 
 &= \frac{\mbox{% 
Sum of contents of all boxes
of $2\lambda$}}{2} - \frac{2|\lambda|}{4},\quad\lambda\in \cY.
\end{align*}
Note that $\theta^{2\lambda}_{2(2)}=0$ when $|\lambda|=1$.
This can be generalized to all fixed orbital basis elements.

In Section~\ref{Sect4}, we show that the algorithm of Theorem~\ref{mt}
converts the basis $\{W_\mu\}$ of $\Lambda[t]$ into another basis $\{E_\mu\}$ of
$\Lambda[t]$ with the following property.

\begin{theo} \label{mks}
For each $\mu\in\cP(2)$ there is a symmetric
function $E_{\mu}\in \Lambda[t]$ such that  
\begin{enumerate}[(\roman*)]
\item\label{theo1.2_i} %\noi (i) 
$\{E_{\mu}\mid \mu\in\cP(2)\}$ is a $\Q[t]$-module basis of
$\Lambda[t]$.


\item\label{theo1.2_ii} %\noi (ii) 
For all $\mu\in\cP(2)$ and $\lambda\in\cY$, we have
\[
\theta^{2\lambda}_{2\mu} = E_{\mu}(c(2\lambda)).
\]
\end{enumerate}
\end{theo}  
%    
Information about the coefficients in the expansion of $W_\mu$ and
$E_\mu$ in the power sum basis is given in Section~\ref{Sect4}. Example~\ref{wep} in
Section~\ref{Sect4} lists these symmetric functions for $|\mu|\leq 4$. 


One method for computing the eigenvalues $\{\theta_i\}$ of a real symmetric
matrix $N$ is to write down eigenvectors $\{v_i\}$, one in each eigenspace,
and then to solve for $\theta_i$ in the equation $Nv_i=\theta_iv_i$. 
In Section~\ref{Sect5} we use this method to give a different  
inductive algorithm (not using the characters or central characters of
$S_n$) for computing the
eigenvalues $\hat{\theta}^{2\lambda}_{2\mu}$ of $\cB_{2n}$.

Every $S_n$-irreducible $V^\lambda$ has a canonically
defined basis, determined \upto{} scalars, and called the Gelfand--Tsetlin (GZ) basis. We
systematically choose one of these basis vectors  and call it the first GZ
vector (see Sections~\ref{Sect4} and~\ref{Sect5} for definitions). 
Let
$v_{2\lambda}$ denote the first GZ vector of the eigenspace $V^{2\lambda}$
of $\cB_{2n}$. 
Let $\lambda'\in \cY_{n+1}$ with $\lambda =
\lambda' - \{\mbox{last box in the last row of $\lambda'$}\}$.
Then there is a simple expression for $v_{2\lambda'}$ in terms  
of $v_{2\lambda}$ (see Section~\ref{Sect5}). 
The simplest nontrivial case of this occurs when
$\lambda'=(n,1)$. Here $\lambda=(n)$ and $V^{2(n)}$ is the trivial
representation giving $v_{2\lambda}=\sum_{A\in \cM_{2n}} A$. In this case
the eigenvector $v_{2\lambda'}$ coincides with that written down by
Godsil and Meagher~\cite{gm,gm1} and Lindzey~\cite{l} (using a
quotient argument).

Of course, explicitly writing down these
vectors is inefficient since $v_{2\lambda}$ lives in a space
of dimension $(2n-1)!!=1\cdot 3\cdot 5 \cdots \cdot (2n-1)$.
However, we use this expression implicitly to
give an algorithm that works with only the rows of $\hat{\Theta}(2n)$.
Note that a row of $\hat{\Theta}(2n)$ has only $p(n)$ components, which is
subexponential and is only moderately large for small values of $n$ 
(for example, compare $p(13)=101$ with $25!!=7905853580625$).
%
\begin{theo} \label{mt1}
Let $\lambda'\in \cY_{n+1}$ with $\lambda =
\lambda' - \{\mbox{last box in the last row of $\lambda'$}\}$.
Assume that
the row of $\hat{\Theta}(2n)$ indexed by $\lambda$, \ie  the vector
$(\hat{\theta}^{2\lambda}_{2\mu})_{\mu\vdash n}$, is known.

There is an algorithm to determine
$(\hat{\theta}^{2\lambda'}_{2\mu'})_{\mu'\vdash n+1}$, \ie 
the row of $\hat{\Theta}(2n+2)$ indexed by $\lambda'$.

\end{theo}
%  
The statement of Theorem~\ref{mt1} hides some details. Strictly
speaking, we need to work not with row vectors of length $p(n)$ but of length
$pp(n)$, the number of pointed partitions of $n$ (see Section~\ref{Sect5} for the
definition). The main point is that $pp(n)$ is also subexponential and is
only moderately large for small values of $n$. For instance, $pp(13)=272$.

The eigenvector approach also applies to the central characters and in
Section~\ref{Sect5} we give a very similar
inductive algorithm (not using irreducible characters) to compute
$\hat{\phi}^\lambda_\mu$. Although this method of computing the central
characters is not as efficient as the one based on~\eqref{equ} (since the
irreducible characters can be very efficiently calculated), 
it further brings out the
essential analogy between $\hat{\theta}^{2\lambda}_{2\mu}$
and $\hat{\phi}^\lambda_\mu$. A simple recursive implementation of these
algorithms in Maple is given in~\cite{sr}. 


Finally, we would like to add a terminological remark. The Bose--Mesner
algebra $\cB_{2n}$ is isomorphic to the Hecke algebra (also called the
double coset algebra) of the Gelfand pair
$(S_{2n},H_n)$, where $H_n$ is the hyperoctahedral group (see Example 5
of Chapter~VII.2 of~\cite{m}), and the two settings are equivalent. Except
in the last section, in
this paper we adopt the perfect matching point of view.



\section{The \texorpdfstring{$S_n$}{SN}-module \texorpdfstring{$\C[\cM_n]$}{C[Mn]}}\label{Sect2}


The regular modules $\C[S_n]$ have the following recursive
structure
\begin{equation} \label{rrs}
\ind_{S_n}^{S_{n+1}}(\C[S_n])\cong  \C[S_{n+1}].
\end{equation}
%
The modules $\C[\cM_{2n}]$ have a similar recursive structure. Informally,
we can say that
the induction happens at every other step and we do nothing in between (see
items~\ref{lemma2.1_v} and~\ref{lemma2.1_vi} of Lemma~\ref{mfree} below). This
is best brought out by
simultaneously considering the odd case, \ie  the action of $S_{2n+1}$ on
near perfect matchings (= matchings with $n$ edges) of $K_{2n+1}$. This idea
is implicit in the detailed proof of~\eqref{fr} given in Chapter 43 of
Bump's book~\cite{bu} (also see~\cite{jk,s}) but it is
useful to make it explicit as it simplifies certain technicalities and
also suggests an approach to writing down the
eigenvectors of $\cB_{2n}$ in
Section~\ref{Sect5}. We adopt a uniform notation for both the even and odd cases.






Let $\cbP_n$ denote the set of all even partitions of
$n$, if $n$ is even, 
or the set of all near even partitions of $n$ (\ie  exactly 
one part odd), if $n$ is odd. 
Let $\cbY_n$ denote the set 
of all even Young diagrams with
$n$ boxes, if $n$ is even, 
or the set of all near even Young diagrams with $n$ boxes (\ie  exactly 
one row length odd), if $n$ is odd. 




Let $\cM_n$ denote the set of all maximum matchings in $K_n$ (\ie  perfect
matchings if $n$ is even and near perfect matchings if $n$ is odd).
Given $A,B \in \cM_n$, let $d(A,B)$ be the partition whose parts
are the number of vertices in the connected components of
the spanning subgraph of $K_n$ with edge set
$A\cup B$. It is easily seen that $d(A,B)\in \cbP_n$.

For $\mu \in \cbP_n,\;A\in \cM_n$ define
\[
\cM(A,\mu) = \{ B\in \cM_n\mid  d(A,B)=\mu\},
\]
and define a linear operator
\[
N_\mu: \C[\cM_n]\rar \C[\cM_n]
\]
%
by setting, for $A\in \cM_n$,
\[
N_\mu(A)=\sum_{B\in \cM(A,\mu)}\;B.
\]


The symmetric group $S_n$ has a natural action on $\cM_n$ and this gives
rise to the $S_n$-module $\C[\cM_n]$. We have the diagonal action of $S_n$
on $\cM_n\times \cM_n$. Set $\cB_n = \End_{S_n}(\C[\cM_n])$.

For $n$ odd, given $A\in \cM_n$ we denote by $v(A)$ the unique vertex of
$K_n$ that is not the endpoint of any edge in $A$. An edge connecting
vertices $i$ and $j$ will be denoted $[i,j]$ (or $[j,i]$). The following result
collects together basic properties of the $S_n$-action on $\cM_n$.

\begin{lemm} \label{mfree} Let $n$ be a positive integer.
\begin{enumerate}[(\roman*)]
\item\label{lemma2.1_i} %\noi (i) 
$(A,B),\;(C,D)\in \cM_n\times \cM_n$ are in the same $S_n$-orbit if
and only if $d(A,B)=d(C,D)$.

\item\label{lemma2.1_ii} %\noi (ii) 
The set $\{ N_\mu\mid  \mu\in \cbP_n\}$ is a basis of
$\cB_n$.

\item\label{lemma2.1_iii} %\noi (iii) 
$(A,B),\,(B,A)$ are in the same $S_n$-orbit, for all $(A,B)\in
\cM_n\times \cM_n$.

\item\label{lemma2.1_iv} %\noi (iv) 
The $S_n$-module $\C[\cM_n]$ is multiplicity free.

\item\label{lemma2.1_v} %\noi (v) 
Assume $n$ is odd. We have an $S_n$-module isomorphism
(treating $S_n$ as the subgroup of $S_{n+1}$ fixing $n+1$) 
\[
\C[\cM_n] \cong \res_{\;S_n}^{\;S_{n+1}}(\C[\cM_{n+1}])
\]
given by $A\mapsto A \cup \{[v(A),n+1]\},\;A\in \cM_n$. 

\item\label{lemma2.1_vi} %\noi (vi) 
Assume $n$ is even. We have an $S_{n+1}$-module isomorphism
\[
\ind_{\;S_n}^{\;S_{n+1}}(\C[\cM_n])\cong  \C[\cM_{n+1}].
\]
\end{enumerate}
\end{lemm}  

\begin{proof} 
\ref{lemma2.1_i} %(i) 
This is clear.

\ref{lemma2.1_ii} %\noi (ii) 
This follows from part~\ref{lemma2.1_i} by a standard result (see~\cite{cst2,
gm}). 

\ref{lemma2.1_iii} %\noi (iii) 
Follows from part~\ref{lemma2.1_i}. %(i).


\ref{lemma2.1_iv} %\noi (iv) 
This follows from part~\ref{lemma2.1_iii}  by a standard result (see
\cite{cst2,gm}). 


\ref{lemma2.1_v} %\noi (v) 
This is clear.

\ref{lemma2.1_vi} %\noi (vi) 
Consider the disjoint union given by coset decomposition 
\[
S_{n+1} = S_n \cup (1\; n+1)S_n \cup \cdots \cup (n\;n+1)S_n.
\]
%
We think of $\ind_{\;S_n}^{\;S_{n+1}}(\C[\cM_n])$ as the (left)
$\C[S_{n+1}]$-module $\C[S_{n+1}] \otimes_{\C[S_n]} \C[\cM_n]$ with
basis $\{(i\;n+1)\otimes A\;:\;1\leq i \leq n+1,\;A\in \cM_n\}$ (here
$(n+1\;n+1) = \epsilon$, the identity permutation).

Define a bijective linear map
$f:\ind_{\;S_n}^{\;S_{n+1}}(\C[\cM_n])\rar \C[\cM_{n+1}]$ by
\[
f((i\;n+1)\otimes A) = (i\;n+1)\cdot A,\quad 1\leq i \leq n+1,\;A\in \cM_n.
\]
%
Fix $1\leq i \leq n+1$ and $A\in \cM_n$. Let $\tau \in S_{n+1}$. Set
$j=\tau(i)$ and write
$\tau (i\;n+1)=(j\;n+1)\tau'$ where $\tau'=(j\;n+1)\tau (i\;n+1)$. Note that
$\tau'(n+1)=(n+1)$. Then
\begin{align*}
f(\tau\cdot((i\;n+1)\otimes A))&=f((j\;n+1)\otimes (j\;n+1)\tau(i\;n+1)\cdot
A) \\
&= (j\;n+1)\cdot ((j\;n+1)\tau(i\;n+1)\cdot A)\\
&=\tau\cdot f((i\;n+1)\otimes A).
\end{align*}
Thus, $f$ is an $S_{n+1}$-module isomorphism. \end{proof}




We call $\{ N_\mu\mid  \mu\in \cbP_n\}$ 
the \emph{orbital basis} of $\cB_n$.
Parts~\ref{lemma2.1_ii} and~\ref{lemma2.1_iv} of Lemma~\ref{mfree} show that the eigenvalues of
$N_\mu$ are integers using the following standard argument (and the
fact that the irreducible characters of $S_n$ are integer valued).


\begin{lemm} \label{inteig}
Let a finite group $G$ act on a finite set $X$ and for, $g\in G$, let
$\rho(g)$ denote the $X\times X$ permutation matrix corresponding to the
action of $g$ on $X$. Let $A$ be a $X\times X$
matrix with integer entries that commutes with the action of $G$ on $X$,
\ie  $A\rho(g)=\rho(g)A$ for all $g\in G$. 
Assume that 

\begin{enumerate}[(\roman*)]
\item\label{lemma2.2_i} %\noi (i) 
The permutation representation of $G$ on $\C[X]$ is multiplicity free.  

\item\label{lemma2.2_io} %\noi (ii) 
The character of every $G$-irreducible appearing in $\C[X]$ is
integer valued.
\end{enumerate}

\noi 
Then the eigenvalues of $A$ are integral.
\end{lemm}


\begin{proof} Write 
\[
\C[X] = V_1 \oplus \cdots \oplus V_t,
\]
where $V_1,\ldots ,V_t$ are nonisomorphic irreducible $G$-submodules of
$\C[X]$. Let $\chi_i$ be the character of $V_i$.


Let $\lambda$ be an eigenvalue of $A$. 
By Schur's lemma, every $V_j$ is contained in an eigenspace of $A$. 
Thus the eigenspace of $\lambda$ is a direct sum of some of the $V_j$'s. 
Say $V_i$ is contained in the eigenspace of $\lambda$.

The
$G$-linear projection $\C[X] \rar \C[X]$ onto $V_i$ is given by
\[
 v\mapsto \frac{\dim V_i}{|G|} \sum_{g\in G} \ol{\chi_i(g)}\;g\cdot v.
\]
%
Since $\chi_i$ is integer valued the matrix of the projection above (in the
standard basis $X$) has rational entries and thus there is an eigenvector
for $\lambda$ with rational entries. Since $A$ is integral it follows that
$\lambda$ is a rational number and since it is also an algebraic integer
(being an eigenvalue of an integer matrix) it follows that $\lambda$ is an
integer. 
\end{proof}


The recursive structure of the modules $\C[\cM_n]$ given by parts~\ref{lemma2.1_v} and~\ref{lemma2.1_vi}
 of Lemma~\ref{mfree}, together with the branching rule, yields
a proof of~\eqref{fr}. This part of the proof, which we include for
completeness, is essentially the same as in~\cite{bu}. 
Let us first recall the branching rule.


A fundamental
result (see~\cite{cst2,jk,ov, p, sa}) in the representation theory of the
symmetric groups states that there is a unique assignment,
denoted $\lambda
\mapsto V^{\lambda}$, which associates to each Young diagram $\lambda$ an
equivalence class $V^{\lambda}$ of irreducible $S_{|\lambda|}$-modules
(we also let $V^{\lambda}$ 
denote an irreducible $S_n$-module in the corresponding equivalence
class)
such
that properties~\ref{sect2_a} and~\ref{sect2_b} below are satisfied:


\begin{enumerate}[(\roman*)]
\item\label{sect2_a} %(a) 
\emph{Initialization:}  $V^{(2)}$ is the trivial
representation of $S_2$ 
and $V^{(1,1)}$ is the sign representation of $S_2$
(here $(2)$, respectively $(1,1)$, denotes the Young diagram with a single
row of two boxes, respectively a single column of two boxes). 


\item\label{sect2_b} %(b) 
\emph{Branching rule:}
Given $\mu\in \cY$, we denote by
$\mu^-$ the set of all Young diagrams obtained from $\mu$ by
removing a box corresponding to 
one of the inner corners in the Young diagram $\mu$.
For $n\geq 2$, given $\lambda\in \cY_n$, consider the irreducible
$S_n$-module $V^{\lambda}$.
Viewing $S_{n-1}$ as the subgroup
of $S_n$ fixing $n$
we have an $S_{n-1}$-module isomorphism
\begin{equation} \label{brres}
\res^{S_n}_{S_{n-1}}(V^{\lambda})\cong  \bigoplus_{\mu\in\lambda^-}
V^{\mu}.
\end{equation}
\end{enumerate}


It is a consequence of properties~\ref{sect2_a} and~\ref{sect2_b} above that
$\{V^{\lambda}\mid \lambda\in \cY_n\}$ is a complete set of pairwise
inequivalent irreducible representations of $S_n$. Another consequence is
that, for any $n$, the Young diagram consisting of a single row of $n$ boxes
(respectively, a single column of $n$ boxes)    
corresponds to the trivial representation of $S_n$ (respectively, the sign
representation of $S_n$). 

Given $\mu\in \cY$, we denote by
$\mu^+$ the set of all Young diagrams obtained from $\mu$ by
adding a box corresponding to one of the outer 
corners in the Young diagram $\mu$.
For $n\geq 1$, given $\lambda\in \cY_n$, consider 
the irreducible $S_{n}$-module $V^{\lambda}$. 
By Frobenius reciprocity, the branching rule
can be equivalently stated as
%
\begin{equation} \label{brind}
\ind_{S_n}^{S_{n+1}}(V^{\lambda})\cong  \bigoplus_{\mu\in\lambda^+}
V^{\mu}.
\end{equation}


%
\begin{theo} \label{ep} Let $n$ be a positive integer. There is a $S_n$-linear
isomorphism
\[
\C[\cM_n] \cong \bigoplus_{\lambda\in \cbY_n} V^{\lambda}.
\]
\end{theo} 


\begin{proof} The proof is by induction on $n$, the cases $n=1,2$ being clear. Let
$n\geq 3$ and consider the following two cases.
\begin{enumerate}[(\roman*)]
\item\label{proof_theo2.3_i} %\noi (i) 
$n$ is odd: This easily follows from the induction hypothesis, 
Lemma~\ref{mfree}~\ref{lemma2.1_iv}, \ref{lemma2.1_vi}, and the branching rule.

\item\label{proof_theo2.3_ii} %\noi (ii) 
$n$ is even: Let $V^{\lambda}$, $\lambda\in \cY_n$ occur in
$\C[\cM_n]$ and assume that $\ell(\lambda)\geq 3$. Suppose that not 
all rows of
$\lambda$ are of even length. Then, since $n$ is even, we can find an
inner corner of $\lambda$ such that deleting the corresponding box leaves a
Young diagram with at least two rows of odd length. By Lemma~\ref{mfree}~\ref{lemma2.1_v}
and the branching rule,
this contradicts the induction hypothesis (for $n-1$). Thus,
$V^{\lambda}$ cannot occur in $\C[\cM_n]$.
\end{enumerate}

Define Young diagrams $\lambda_k=(n-k,k),\;0\leq k \leq n/2$. Note that
$\lambda_0,\ldots ,\lambda_{n/2}$ are all the Young diagrams with at most
two rows. We shall show, by induction on $k$, that $V^{\lambda_k},\;0\leq k\leq
n/2$ occurs in $\C[\cM_n]$ if and only if $k$ is even. Now $V^{\lambda_0}$ is
the trivial representation and thus occurs in permutation representation
$\C[\cM_n]$. Assume, inductively, that our claim has been proven for
$V^{\lambda_0},\ldots ,V^{\lambda_{t-1}}$ and consider $V^{\lambda_t}$.
Suppose $t$ is even. By the main induction hypothesis on $n$,
$V^{(n-t,t-1)}$ occurs in $\C[\cM_{n-1}]$. By Lemma~\ref{mfree}~\ref{lemma2.1_v} and the
branching rule, one of $V^{(n-t,t-1,1)},\;V^{(n-t+1,t-1)},\;V^{(n-t,t)}$
must occur in $\C[\cM_n]$. The first cannot occur by the paragraph above,
the second cannot occur by the secondary induction hypothesis on $k$, and so
the third must occur. Now suppose that $t$ is odd and that $V^{(n-t,t)}$
occurs in $\C[\cM_n]$. Then, since $V^{(n-t+1,t-1)}$ occurs in $\C[\cM_n]$
(by the secondary  induction hypothesis on $k$), $V^{(n-t,t-1)}$ will occur
at least twice in $\C[\cM_{n-1}]$ contradicting its multiplicity freeness.
Thus the claim on $V^{\lambda_k},\;0\leq k \leq n/2$ is established.

What we have shown so far implies that if $V^{\lambda},\;\lambda\in \cY_n$
occurs in $\C[\cM_n]$ then all rows of $\lambda$ must have even length. Since,
by the branching rule,  
$\res^{\;S_n}_{\;S_{n-1}}(V^{\lambda})$ and
$\res^{\;S_n}_{\;S_{n-1}}(V^{\mu})$, for $\lambda,\;\mu\in \cbP_n,
\mu\not=\lambda$ can have no irreducibles in common, the result follows from
the induction hypothesis and Lemma~\ref{mfree}~\ref{lemma2.1_v}. 
\end{proof}




\section{Eigenvalues and (class-coset) intersection numbers}\label{Sect3}


Assuming the
central characters of $S_2, S_4, \ldots , S_{2n}$ as given, we
show in this section that we can compute
the eigenvalues of $\cB_{2n}$ by solving linear equations.

We begin by recalling, without proof, the following classical formula for the
eigenvalues of $\cB_{2n}$ that appears in Bannai and Ito~\cite{bi} 
(see page 179), Hanlon, Stanley, and Stembridge
\cite{hss} (see equation (3.3) of Lemma 3.3)  and in
Godsil and Meagher~\cite{gm} (see Lemma 13.8.3). It is proved by
writing down the primitive idempotents of $\cB_{2n}$ and then 
expanding the orbital basis in terms of these. Another paper, using Jack
symmetric functions, on the
eigenvalues of $\cB_{2n}$ is Muzychuk~\cite{muz}.


Denote by $I$ the perfect matching $\{[1,n+1],[2,n+2],\ldots ,[n,2n]\}$
of $K_{2n}$. If $\mu$ is a
partition with $m_i$ parts equal to $i$ we set
$z_{\mu}=1^{m_1}m_1!\;2^{m_2}m_2!\;3^{m_3}m_3!\cdots$. 


% 
\begin{theo}[{\cite{bi,hss,gm}}] 
Let $\lambda, \mu \vdash n$. Fix $A\in \cM_{2n}$ with
$d(I,A)=2\mu$. 
Then
\[
\hat{\theta}^{2\lambda}_{2\mu} =
\frac{1}{2^{\ell(\mu)}z_{\mu}}\left\{\sum_{\pi\in S_{2n},\;\pi\cdot I = A}
\chi^{2\lambda}(\pi)\right\}. %\;\;\;\Box
\]
%
\end{theo}

The formula above has $2^nn!$ terms on the right hand side. 
We can group terms by cycle type to
reduce this number.

Let $\mu \vdash n$. Fix $A\in \cM_{2n}$ with $d(I,A)=2\mu$.
For $\tau\vdash 2n$, define 
\[
m(\tau,2\mu) = |C_{\tau} \cap \{\pi\in S_{2n}\mid  \pi\cdot I = A\}|,
\]
\ie  $m(\tau, 2\mu)$ is the number of permutations in $S_{2n}$ 
of cycle type $\tau$ taking $I$
to $A$ (this number is clearly independent of $A$ as long as $d(I,A)=2\mu$). 
We refer to the $m(\tau,2\mu)$ as the \emph{(class-coset) intersection
numbers} of $\cB_{2n}$ (being the cardinality of the 
intersection of a conjugacy class with a coset of the subgroup fixing $I$).
 
We thus have the following formula which has only $p(2n)$ terms
\begin{equation} \label{hssf}
\hat{\theta}^{2\lambda}_{2\mu} =
\frac{1}{2^{\ell(\mu)}z_{\mu}}\left\{\sum_{\tau\vdash
2n}m(\tau,2\mu)\chi^{2\lambda}_{\tau}\right\}.
\end{equation}
%
There is, however, no simple formula for $m(\tau,2\mu)$. 
Thus, in the identity~\eqref{hssf} above, the characters of $S_{2n}$ 
are known but we have two sets of unknowns: eigenvalues of $\cB_{2n}$ 
and the intersection numbers of $\cB_{2n}$.
The idea 
of the present approach is the following bootstrap procedure: 

\begin{enumerate}[(\roman*)]
\item\label{Sect3_i} % (i) 
Given the central characters, we shall simultaneously inductively calculate the eigenvalues and
intersection numbers of $\cB_{2n}$.

\item\label{Sect3_ii} %(ii)  
In Theorems~\ref{ev1} and~\ref{ev2} below we show that 
the eigenvalues of $\cB_{2n}$ can be found from the central characters of
$S_{2n}$ and the intersection numbers of $\cB_{2},\ldots ,\cB_{2n-2}$.


\item\label{Sect3_iii} %(iii) 
In Lemma~\ref{mtrick} below we show that we  
can find the intersection numbers of $\cB_{2n}$ 
from the central characters of $S_{2n}$ and the eigenvalues of
$\cB_{2n}$ by solving linear equations. 
\end{enumerate}

For $\tau\vdash n, \mu\vdash 2n$ define column vectors of length $p(n)$
\[
 \hat{\phi}_{\mu} = (\hat{\phi}^{2\lambda}_{\mu})_{\lambda\vdash n} 
\mbox{ and }
\hat{\theta}_{\tau} = (\hat{\theta}^{2\lambda}_{2\tau})_{\lambda\vdash n}.
\]
Note that $\hat{\theta}_\tau$ is the
column of $\hat{\Theta}(2n)$ indexed by $\tau$. We have
%
\begin{lemm} \label{mtrick}
Let $\mu\vdash 2n$. Then
\[
\hat{\phi}_{\mu} = \sum_{\tau\vdash n} m(\mu,2\tau)\hat{\theta}_{\tau},
\]
%
\ie defining the column vector $m(\mu)=(m(\mu,2\tau))_{\tau\vdash n}$ we have
\[
\hat{\phi}_\mu = \hat{\Theta}(2n)m(\mu).
\]
\end{lemm}
%
\begin{proof} Consider the element $k_{\mu}\in Z[\C[S_{2n}]]$. Then
\[ 
k_\mu \cdot I = \sum_{\tau\vdash n} m(\mu,2\tau) N_{2\tau}(I). 
\]
%
It follows that the actions of $k_\mu$ and 
$\sum_{\tau\vdash n} m(\mu,2\tau) N_{2\tau}$
on $\C[\cM_{2n}]$ are identical. The eigenvalue of $k_\mu$ on
$V^{2\lambda}$ is $\hat{\phi}^{2\lambda}_\mu$ and that of $N_{2\tau}$
on $V^{2\lambda}$ is $\hat{\theta}^{2\lambda}_{2\tau}$. 
The result follows. \end{proof}  

The matrix $\hat{\Theta}(2n)$ of eigenvalues of $\cB_{2n}$ 
is clearly nonsingular. Thus, 
Lemma~\ref{mtrick} above shows that, given the central characters of
$S_{2n}$ and the eigenvalues of $\cB_{2n}$, and given $\mu\vdash 2n$,
we can find all the $m(\mu,2\tau), \tau\vdash n$
by solving a single system of nonsingular linear 
equations of size $p(n)\times p(n)$. 
We shall now use this
result to inductively compute the eigenvalues of 
$\cB_2,\cB_4,\ldots ,\cB_{2n}$ from the central characters 
of $S_2,S_4,\ldots ,S_{2n}$.


For $\pi\in S_{2n}$ define
\[
\supp(\pi) = \{ i\in \{1,2,\ldots ,n\}\mid  \pi(i)\not= i \mbox{ or }
                \pi(n+i)\not= n+i\;(\mbox{or both}) \}.
\]
%
That is, $\supp(\pi) \cup (n + \supp(\pi))$ (here, $n + \supp(\pi) =
\{n+i\mid i\in \supp(\pi)\}$) is the set of end points of all
the edges of $I$ that are \emph{touched} by the nontrivial 
cycles of $\pi$ (\ie by cycles of length $\geq 2$).


Let $\mu\in \cP(2)$. For $n\geq 1$, define
\begin{equation} \label{deff}
f(\mu,2n): \C[\cM_{2n}] \rar \C[\cM_{2n}],
\end{equation}
by $x\mapsto c_{\mu}(2n)\cdot x$. Note that $2n < |\mu|$ implies that
$f(\mu,2n)=0$.

Clearly $f(\mu,2n)\in \cB_{2n}$. Write
\begin{equation} \label{expf}
f(\mu,2n) = \sum_{\tau\in \cP(2,n)}
d^\tau_\mu(2n)M_{2\tau}(2n).
\end{equation} 

The nonnegative integers $d^\tau_\mu(2n)$ defined above can be calculated as
follows, for $n\geq |\mu|$. Below $a \vee b$ denotes the maximum 
of two nonnegative integers $a,b$. 

%
\begin{theo}\ \\*[-1em]
%\begin{theoc} 
\label{ev1}
\begin{enumerate}[(\roman*)]
\item\label{theo3.3_i} %(i) 
Let $\mu\in \cP(2)$ with $|\mu|=k$ and let $n\geq k$. 
For $\tau\in\cP(2,n)$ 
we have
\[
d^\tau_\mu(2n) = %\left\{ \ba{cl}  
\begin{cases}
0 & \mbox{if }|\tau| > k \\
0 & \mbox{if }|\tau| = k \mbox{ and } \tau \not= \mu \\
2^{\ell(\mu)} & \mbox{if }\tau=\mu 
%\ea \right.
\end{cases}
\]
and, for $|\tau|=j<k$, $d^\tau_\mu(2n)$ equals
\begin{equation} \label{if}
\ds{\sum_{r=j\vee \lfloor \frac{k+1}{2} \rfloor}^{k-1}}\left\{
\ds{\sum_{s=j\vee \lfloor \frac{k+1}{2} \rfloor}^{r}}\;
(-1)^{r-s}\;\binom{r-j}{s-j}\;m((\mu,1^{2s-k}),2(\tau,1^{s-j}))\right\}
\binom{n-j}{r-j}.
\end{equation}

\item\label{theo3.3_ii} %(ii) 
The set $\{ f(\mu,2n)\mid  \mu\in \cP(2,n)\}$ is
a basis of $\cB_{2n}$.
\end{enumerate}
%\end{theoc}
\end{theo}


\begin{proof} 
\ref{theo3.3_i}~The result is clearly true if $k=0$ (in which case $f(\mu,2n)$ is the
identity map). So we may assume that $k\geq 2$. 
Let $\pi\in C_{(\mu,1^{2n-k})}$. A nontrivial $r$-cycle of $\pi$ can
touch at most $r$ edges of $I$ and thus $|\supp(\pi)|\leq k$. Moreover, if
$|\supp(\pi)|=k$ then each nontrivial $r$-cycle of $\pi$ touches exactly $r$
edges of $I$ and no edge of $I$ is touched by two distinct nontrivial
cycles. It follows that $|\supp(\pi)|=k$ implies 
$d(I, \pi\cdot I)=2(\mu, 1^{n-|\mu|})$ and
$|\supp(\pi)|\leq k-1$ implies 
$d(I,\pi\cdot I)=2(\lambda,1^{n-|\lambda|})$, 
where $\lambda\in \cP(2)$ satisfies
$|\lambda| \leq k-1$. 
Thus $d^\tau_\mu(2n)=0$ if $|\tau|>k$ or $|\tau|=k$ and $\tau\not=\mu$.

We now determine $d^\mu_\mu(2n)$. Consider the nontrivial
$r$-cycle $\sigma =(1\;2 \cdots r)\in S_{2n},\;2\leq r \leq n$. 
Then $\supp(\sigma)=\{1,2,\ldots ,r\}$ and 
$d(I,\sigma\cdot I)=2(r,1^{n-r})$. It can be checked that the only other
$r$-cycle $\pi$ with $\pi\cdot I = \sigma\cdot I$ is $\pi = (n+1\;n+r\;n+r-1
\cdots n+2)$. Since any element of $C_{(\mu,1^{2n-k})}$ has $\ell(\mu)$
nontrivial cycles it now follows from the paragraph above that
$d^\mu_\mu(2n)=2^{\ell(\mu)}$.



Now let $\tau\in\cP(2)$ with $|\tau|=j<k$. We now calculate $d^\tau_\mu(2n)$.

Fix $A\in \cM_{2n}$ with $d(I,A)=2(\tau, 1^{n-j})$ and with $I\cap A$, the intersection
of the set of edges of $I$ and $A$, given by 
\[
I\cap A = \{[j+1,n+j+1], [j+2,n+j+2],\ldots ,[n,2n]\}.
\]
%
We have
\begin{equation} \label{f1}
d^\tau_\mu(2n)= |\{ \pi\in C_{(\mu,1^{2n-k})}\mid  \pi\cdot I =A\}|.
\end{equation}
%
Let $\pi\in C_{(\mu,1^{2n-k})}$ with $\pi\cdot I =A$. 
Then we clearly have
\begin{equation} \label{f2}
\{1,2,\ldots ,j\}\seq \supp(\pi), \left\lfloor \frac{k+1}{2}\right\rfloor \leq
|\supp(\pi)|, \mbox{ and }|\supp(\pi)|\leq k-1,
\end{equation} 
where the last inequality follows from
the first paragraph of the proof.

Let $\cS(j,k,n)$ denote the set of all subsets $X$ of $\{1,2,\ldots ,n\}$
satisfying $\{1,2,\ldots ,j\}\seq X$ and 
$\lfloor \frac{k+1}{2}\rfloor \leq |X| \leq k-1$, \ie  $\cS(j,k,n)$
consists of all subsets of $\{1,2,\ldots ,n\}$ containing the elements
$\{1,2,\ldots ,j\}$ and with cardinality between $j \vee \lfloor
\frac{k+1}{2} \rfloor$ and $k-1$ (inclusive).
Partially order
$\cS(j,k,n)$ by set inclusion.

For $X\in \cS(j,k,n)$ define
\begin{align*}
\alpha(X) &= |\{ \pi \in C_{(\mu,1^{2n-k})}\mid  \supp(\pi)\seq X, \;\pi\cdot
I = A\}|,\\
\beta(X) &= |\{ \pi \in C_{(\mu,1^{2n-k})}\mid  \supp(\pi)=X, \;\pi\cdot
I = A\}|.
\end{align*}
%
Note that, from~\eqref{f1} and~\eqref{f2}, we have
\begin{equation} \label{abeta}
d^\tau_\mu(2n)= \sum_{X\in \cS(j,k,n)}\beta(X).
\end{equation}
We have
\[ 
\alpha(X) = \sum_{Y\seq X,\;Y\in \cS(j,k,n)}\beta(Y),\;\;\;X\in
\cS(j,k,n),
\]
and by the principle of inclusion-exclusion
\begin{equation} \label{pie1}
\beta(X) = \sum_{Y\seq X,\;Y\in
\cS(j,k,n)}\;(-1)^{|X-Y|}\alpha(Y),\;\;\;X\in \cS(j,k,n).
\end{equation}
%
If $X\in \cS(j,k,n)$ with $|X|=s$, then a little reflection shows that
\[
\alpha(X)=m((\mu,1^{2s-k}), 2(\tau,1^{s-j})).
\]

If $X\in \cS(j,k,n)$ with $|X|=r$, then we have (from~\eqref{pie1} above)
\begin{equation} \label{pie2}
\beta(X) = \sum_{s=j\vee \left\lfloor \frac{k+1}{2}
\right\rfloor}^r(-1)^{r-s}\binom{r-j}{s-j}\;m((\mu,1^{2s-k}),2(\tau,1^{s-j})).
\end{equation}
%
Thus, from~\eqref{abeta} above, we have
\begin{align*}
d^\tau_\mu(2n) &= \sum_{X\in \cS(j,k,n)}\;\beta(X)\\ 
            &= \sum_{r=j\vee \lfloor\frac{k+1}{2}\rfloor}^{k-1}\;\sum_{X\in
\cS(j,k,n), |X|=r}\;\beta(X).
\end{align*}
%
Since the number of sets $X\in \cS(j,k,n)$ with $|X|=r$ is clearly
$\binom{n-j}{r-j}$ the result follows from~\eqref{pie2} above. 

\ref{theo3.3_ii}~This follows from the triangularity of the coefficients $d^\tau_\mu(2n)$
established in part~\ref{theo3.3_i} above. 
\end{proof}


Choose a linear ordering of $\cP_n$ in which the partitions are listed in
weakly increasing order of the sum of their nontrivial parts (\ie parts
$\geq 2$). List the columns of the $\cY_n \times \cP_n$ matrix
$\hat{\Theta}(2n)$ in this order.
%
\begin{theo} \label{ev2}
\looseness-1
The first column of $\hat{\Theta}(2n)$, indexed by $(1^n)$, is 
the all 1's vector.
Let $\mu\in\cP(2,n)$ with $|\mu|>0$. 
Then the column of $\hat{\Theta}(2n)$, indexed by
$(\mu,1^{n-|\mu|})$, is given by
\[
\left(\hat{\theta}^{2\lambda}_{2(\mu,1^{n-|\mu|})}\right)_{\lambda\vdash n}
 =
\frac{1}{2^{\ell(\mu)}}
\left\{\Mk \left(\hat{\phi}^{2\lambda}_{(\mu,1^{2n-|\mu|})}\right)_{\lambda\vdash n} - 
\ds{\sum_{\tau\in \cP(2,|\mu|-1)}} 
d^\tau_\mu(2n)\;\left(\hat{\theta}^{2\lambda}_{2(\tau,1^{n-|\tau|})}\right)_{\lambda\vdash
n}\Mk \right\}\Mk . 
\]
\end{theo}
%
\begin{proof} This follows by taking the eigenvalues on $V^{2\lambda}$ on both sides
of~\eqref{expf} and using Theorem~\ref{ev1}. 
\end{proof}

\begin{proof}[Proof of Theorem~\ref{mt}]
Assume the central characters of $S_2,S_4,\ldots ,S_{2n}$ and
the eigenvalues of $\cB_2, \cB_4,\ldots ,\cB_{2n-2}$ as given. 


Let $\mu\in \cP(2,n)$ with $|\mu|=k$.
For $\lfloor \frac{k+1}{2}\rfloor \leq s \leq k-1$, we can, by Lemma
\ref{mtrick}, find all the nonnegative integers $m((\mu,1^{2s-k}),
2(\tau,1^{s-|\tau|}))$, $\tau\in\cP(2,s)$ by solving a single system of
linear equations of size $p(s)\times p(s)$ (this requires the central
characters of $S_{2s}$ and the eigenvalues of $\cB_{2s}$ but since $s\leq
k-1\leq n-1$ the latter are known).

Thus the numbers $d^\tau_\mu(2n)$, for $\mu\in\cP(2,n),\;|\tau|<|\mu|$ can
computed from~\eqref{if}.
We can now calculate the eigenvalues of $\cB_{2n}$ using the recurrence in
Theorem \ref{ev2}. 
\end{proof}
%
\begin{exam} To illustrate, we calculate the eigenvalue tables $\hat{\Theta}(4)$ and
$\hat{\Theta}(6)$ starting from $\hat{\Theta}(2)$.
The
central characters of $S_4, S_6$ can be calculated from the character tables of
$S_4, S_6$ given in~\cite{jk}. 

We rewrite Lemma~\ref{mtrick} as follows: for $\mu\vdash 2n$
%
\begin{equation} \label{rev}
(m(\mu,2\tau))_{\tau\vdash n} =
\hat{\Theta}(2n)^{-1}(\hat{\phi}^{2\lambda}_{\mu})_{\lambda\vdash n}.
\end{equation}
%

$\hat{\Theta}(2)$ is the $\cY_1\times \cP_1$ matrix $[1]$. Thus, from
\eqref{rev} above we have
%
\[
 m((2),2(1)) =  \hat{\phi}^{2(1)}_{(2)} = 1.
\]
%
We list the elements of $\cY_2$ as $\{(2), (1,1)\}$ and the
elements of $\cP_2$ as $\{(1,1), (2)\}$. The first column of
$\hat{\Theta}(4)$ is $%\left( \ba {r}
\begin{pmatrix}
1\\1 
%\ea\right)
\end{pmatrix}$.
From Theorem~\ref{ev2}, the second column is 
\[
\begin{pmatrix}
%\left( \ba{l}
\hat{\theta}^{2(2)}_{2(2)} \\  \hat{\theta}^{2(1,1)}_{2(2)} 
%\ea \right) 
\end{pmatrix}
= 
\frac{1}{2} \left\{ %\left( \ba{l}
\begin{pmatrix}
\hat{\phi}^{2(2)}_{(2,1^2)} \\ \hat{\phi}^{2(1,1)}_{(2,1^2)} 
\end{pmatrix}
%\ea \right)
- d^{(0)}_{(2)}(4)
%\left( \ba{r} 
\begin{pmatrix}
1\\ 1 
\end{pmatrix}
%\ea\right)
\right\}. 
\]
%
From Theorem~\ref{ev1} we have
\[
d^{(0)}_{(2)}(4) = 2m((2), 2(1)) = 2,
\]
%
and hence the second column is $
%\left( \begin{array}{r} 
\begin{pmatrix}
2\\-1 
%\end{array}\right)
\end{pmatrix}
$. 
%
Thus we get
\[
\hat{\Theta}(4) = %\left[ %\ba {rr} 
\begin{bmatrix}
1 & 2 \\ 1 & -1 %\ea %\right]
\end{bmatrix}
,\;\;\;
\hat{\Theta}(4)^{-1} =  %\left[ \ba {rr} 
\begin{bmatrix}
1/3 & 2/3 \\ 1/3 & -1/3 
\end{bmatrix}.
%\ea \right].
\]
%
From~\eqref{rev} above we get
\[
\begin{pmatrix}
%\left( \ba{l} 
m((3,1), 2(1,1)) \\ m((3,1), 2(2)) 
\end{pmatrix}
%\ea \right) 
=
%\left[ \ba{rr} 
\begin{bmatrix}
1/3 & 2/3 \\ 1/3 & -1/3 
%\ea \right]
\end{bmatrix}
%\left( \ba{l} 
\begin{pmatrix}
\hat{\phi}^{2(2)}_{(3,1)}
\\ \hat{\phi}^{2(1,1)}_{(3,1)}
\end{pmatrix}
%\ea\right) 
= %\left( \ba{r} 
\begin{pmatrix}
0 \\ 4 
\end{pmatrix}.
%\ea \right).
\]

We list the elements of $\cY_3$ as $\{(3), (2,1), (1^3)\}$ and the elements
of $\cP_3$ as $\{(1^3), (2,1), (3)\}$. The first column of $\hat{\Theta}(6)$
is the all 1's vector. 
From Theorem~\ref{ev2}, the second column is
%
\[
%\left( \ba{r}
\begin{pmatrix}
\hat{\theta}^{2(3)}_{2(2,1)} \\  \hat{\theta}^{2(2,1)}_{2(2,1)}
\\  \hat{\theta}^{2(1^3)}_{2(2,1)}
%\ea \right) 
\end{pmatrix}
= 
\frac{1}{2} \left\{ 
\begin{pmatrix}
%\left( \ba{r}
\hat{\phi}^{2(3)}_{(2,1^4)} \\ \hat{\phi}^{2(2,1)}_{(2,1^4)} 
\\ \hat{\phi}^{2(1^3)}_{(2,1^4)} 
%\ea \right)
\end{pmatrix}
- d^{(0)}_{(2)}(6)
%\left( \ba{r} 
\begin{pmatrix}
1\\ 1\\1 
%\ea\right)
\end{pmatrix}
\right\}. 
\]
%
From Theorem~\ref{ev1} we have
\[
d^{(0)}_{(2)}(6) = 3m((2), 2(1)) = 3,
\]
%
and hence the second column is 
$\begin{pmatrix}
%\left( \ba{r} 
6\\1\\-3 
%\ea \right)
\end{pmatrix}
$.


From Theorem~\ref{ev2}, the third  column of $\hat{\Theta}(6)$ is
%
\[
%\left( \ba{l}
\begin{pmatrix}
\hat{\theta}^{2(3)}_{2(3)} \\  \hat{\theta}^{2(2,1)}_{2(3)}
\\  \hat{\theta}^{2(1^3)}_{2(3)}
%\ea \right) 
\end{pmatrix}
= 
\frac{1}{2} \left\{ 
\begin{pmatrix}
%\left( \ba{l}
\hat{\phi}^{2(3)}_{(3,1^3)} \\ \hat{\phi}^{2(2,1)}_{(3,1^3)} 
\\ \hat{\phi}^{2(1^3)}_{(3,1^3)} 
%\ea \right)
\end{pmatrix}
- d^{(2)}_{(3)}(6)
%\left( \ba{r}
\begin{pmatrix}
6\\ 1 
\\ -3 
%\ea \right)
\end{pmatrix}
- d^{(0)}_{(3)}(6)
%\left( \ba{r} 
\begin{pmatrix}
1\\ 1\\1 
%\ea\right)
\end{pmatrix}
\right\}. 
\]
%
From Theorem~\ref{ev1} we have
\[
d^{(0)}_{(3)}(6) = 3m((3,1), 2(1^2)) = 0,\;\;
d^{(2)}_{(3)}(6) = m((3,1), 2(2)) = 4,
\]
%
and hence
\[
\hat{\Theta}(6) = %\left[ \ba{rrr} 
\begin{bmatrix}
1&6&8\\1&1&-2\\1&-3&2 
%\ea\right]
\end{bmatrix}
.
\]

\end{exam}

We now refine the triangularity of the coefficients $d^\tau_\mu(2n)$ shown
in part~\ref{theo3.3_i} of Theorem~\ref{ev1} above.
Define a partial order on $\cP$ as follows: $\mu\leq\lambda$ provided
$|\mu|<|\lambda|$ or $|\mu|=|\lambda|$ and $\mu$ can be obtained from
$\lambda$ by partitioning the parts of $\lambda$ into disjoint blocks and
then summing the parts in each block.
For instance,
$(5,3,2)\leq (4,2,2,1,1)$ but $(3,1,1)\not\leq (2,2,1)$ and $(2,2,1)\not\leq
(3,1,1)$.


\begin{lemm} \label{pol2}
Let $\mu \in \cP(2)$ with $|\mu|=k$ and let $n\geq k$. Let $\tau\in \cP(2,n)$ 
be such that 
the coefficient $d^\tau_\mu(2n)$ defined in~\eqref{expf} above is nonzero.
Then 
\begin{enumerate}[(\roman*)]
\item\label{lemma3.6_i} %\noi (i) 
$|\tau|\leq |\mu|$.

\item\label{lemma3.6_ii} %\noi (ii) 
$|\tau|=|\mu|$ implies $\tau = \mu$.

\item\label{lemma3.6_iii} %\noi (iii) 
$\ol{\tau} \leq \ol{\mu}$.
\end{enumerate}
\end{lemm} 

\begin{proof} Parts~\ref{lemma3.6_i},~\ref{lemma3.6_ii} follow from part~\ref{theo3.3_i} of Theorem~\ref{ev1}.

\ref{lemma3.6_iii} Let $\pi\in C_{(\mu,1^{2n-k})}$ with $d(I,\pi\cdot I)=2(\tau,
1^{n -|\tau|})$.
Let $\cD(I,\pi\cdot I)$ denote the (set) partition of $[2n]=\{1,2,\ldots ,2n\}$ 
whose blocks are the vertex sets
of the connected components of the spanning subgraph of $K_{2n}$
with edge set $I\cup \pi\cdot I$ (note that each block has an even number of
elements). 
Define a graph on the vertex set $[2n]$ by declaring vertices 
$i\not= j$ to be connected by an edge
provided $i=n+j$ or $j=n+i$ or $i$ and $j$ are in the same
nontrivial cycle of $\pi$ and define $p_{\pi}$ to be the set partition of
$[2n]$ whose blocks are the vertex sets of the connected components
of this graph.
Note that each block of $p_{\pi}$ has an even
number of elements. Clearly, as set partitions, we have
%
\begin{equation} \label{e1}
\cD(I,\pi\cdot I) \leq p_{\pi}.
\end{equation}
%
Define $\mu_{\pi}$ to be the partition in $\cP(2)$ obtained from $p_{\pi}$ by taking
half the sizes of all blocks of $p_{\pi}$ of cardinality $\geq 4$. It is
easy to see, using~\eqref{e1}, that
%
\begin{gather} \label{e2}
|\tau|\leq |\mu_{\pi}| \leq |\mu|, \\ 
\label{e3}
|\tau|=|\mu| \mbox{ implies } \tau=\mu_{\pi}=\mu.
\end{gather}
%
Write the parts of $\mu$ as $\{\mu_1,\ldots ,\mu_t\}$ so that the parts of
$\ol{\mu}$ are $\{\mu_1 - 1,\ldots ,\mu_t - 1\}$. 
Let $B$ be a block of $p_{\pi}$ of size $\geq 4$. Suppose this block
contains $m$ nontrivial cycles of $\pi$ whose sizes (we may assume without
loss of generality) to be $\mu_1,\ldots ,\mu_m$. Consider the hypergraph
with vertex set $B$ and edge set  the nontrivial cycles of $\pi$ contained
in $B$ together with the edges of $I$ contained in $B$. This hypergraph is
connected (since $B$ is a block of $p_\pi$) and so we have
\[
\frac{|B|}{2} \leq  \mu_1 + (\mu_2 -1) + (\mu_3 - 1) +\cdots +(\mu_m - 1),
\]
%
or, equivalently, $\frac{|B|}{2} - 1 \leq (\mu_1 -1)+\cdots + (\mu_m - 1).$

Writing the above inequality for every block of $p_{\pi}$ of size $\geq 4$
and summing we see that
%
\begin{equation} \label{e4}
|\ol{\mu_{\pi}}| \leq  |\ol{\mu}|.
\end{equation}
%
If $|\ol{\mu_{\pi}}|=|\ol{\mu}|$ then 
the argument above also shows that $\ol{\mu_{\pi}}\leq\ol{\mu}$
and if $|\ol{\mu_{\pi}}|<|\ol{\mu}|$ then 
$\ol{\mu_{\pi}}\leq\ol{\mu}$ by definition. So we have
% 
\begin{equation} \label{e5}
%|\ol{\mu_{\pi}}|=|\ol{\mu}|&\mbox{ implies }&
\ol{\mu_{\pi}}\leq\ol{\mu}.
\end{equation}
%
We now show that $ \ol{\tau} \leq \ol{\mu}$. This is clear from~\eqref{e3} if
$|\tau|=|\mu|$. Otherwise, by~\eqref{e2}, $|\tau| < |\mu|$. We consider two
cases.
\begin{enumerate}[(\alph*)]
\item\label{proof_lemma3.6_a} %(a) 
$\cD(I,\pi\cdot I) \not= p_{\pi}$: By~\eqref{e1} and~\eqref{e4} we
have $|\ol{\tau}| < |\ol{\mu_{\pi}}| \leq |\ol{\mu}|$ and so $\ol{\tau} \leq
\ol{\mu}$.

\item\label{proof_lemma3.6_b} %(b) 
$\cD(I,\pi\cdot I) = p_{\pi}$: We have $\tau=\mu_{\pi}$.
The result follows from~\eqref{e5}.\qedhere 
\end{enumerate}
\end{proof} 

We now define a polynomial in $\Q[t]$ using~\eqref{if}. In Theorem~\ref{eln}
below we shall evaluate this polynomial at values not covered by Theorem
\ref{ev1}. 

Given $\tau,\mu\in\cP(2)$ with $j=|\tau|\leq |\mu|=k$, define a polynomial
$\zeta^\tau_\mu(t)\in\Q[t]$ as follows:
\[
\zeta^\tau_\mu(t) = %\left\{ \ba{cl}  
\begin{cases}
0 & \mbox{if } j = k \mbox{ and } \tau \not= \mu \\
2^{\ell(\mu)} & \mbox{if }\tau=\mu 
%\ea \right.
\end{cases}
\]
and, for $j<k$, $\zeta^\tau_\mu(t)$ equals
\[
%&\ds
{\sum_{r=j\vee \lfloor \frac{k+1}{2} \rfloor}^{k-1}}\left\{
\ds{\sum_{s=j\vee \lfloor \frac{k+1}{2} \rfloor}^{r}}\;
(-1)^{r-s}\;\binom{r-j}{s-j}\;m((\mu,1^{2s-k}),2(\tau,1^{s-j}))\right\}
\;\binom{\frac{t}{2}- j}{r-j}. 
\]

\begin{lemm} \label{pol1} Fix $\tau, \mu\in \cP(2)$ with $|\tau|\leq |\mu|$. Then 
\begin{enumerate}[(\roman*)]
\item\label{lemma3.7_i} %\noi (i) 
$\zeta^{\mu}_{\mu}(t)=2^{\ell(\mu)}$.

\item\label{lemma3.7_ii} %\noi (ii) 
$\zeta^{\tau}_{\mu}(t)$ 
is a polynomial in $\Q[t]$ with degree $\leq |\mu|-|\tau|$. 

\item\label{lemma3.7_iii} %\noi (iii) 
$\zeta^\tau_\mu(t)=0$ 
unless $\ol{\tau}\leq \ol{\mu}$.

\item\label{lemma3.7_iv} %\noi (iv) 
$|\ol{\tau}|=|\ol{\mu}|$ implies that $\zeta^\tau_\mu(t)$ does
not depend on $t$, \ie  is a constant.
\end{enumerate}
\end{lemm}
\begin{proof} Parts~\ref{lemma3.7_i} and~\ref{lemma3.7_ii} follow from the definition of $\zeta^\tau_\mu(t)$.

\ref{lemma3.7_iii}~The result is true if $|\tau|=|\mu|$ and so we may assume
$|\tau|<|\mu|$. 
Part~\ref{lemma3.7_iii} of Lemma~\ref{pol2} and~\eqref{if} show that if
$\ol{\tau}\not\leq \ol{\mu}$ then 
$\zeta^\tau_\mu(2n)=0$ for all $n\geq |\mu|$. The result follows. 

\ref{lemma3.7_iv}~The result is true if $|\tau|=|\mu|$ and so we may assume
$|\tau|<|\mu|$. Let $|\ol{\tau}|=|\ol{\mu}|$ and let $n\geq |\mu|$.
Let $\pi,\sigma \in C_{(\mu,1^{2n-k})}$
satisfy $d(I,\pi\cdot I)= 2(\tau, 1^{n-|\tau|})$ 
and $\sigma\cdot I = \pi\cdot I$. Then  
\begin{enumerate}[(\alph*)]
\item\label{lemma3.7_iv_a} %(a) 
By~\eqref{e1} and by case~\ref{proof_lemma3.6_a}  in
the proof of part~\ref{lemma3.6_iii}  in Lemma~\ref{pol2} above
we have $p_{\sigma}=\cD(I,\sigma\cdot I)= \cD(I,\pi\cdot I) = p_{\pi}$.

\item\label{lemma3.7_iv_b} %By case (b) in
the proof of part~\ref{lemma3.6_iii} in Lemma~\ref{pol2} above
$|\ol{\mu_{\pi}}|=|\ol{\mu_{\sigma}}|= |\ol{\mu}|$. This implies that
$\pi$ and $\sigma$ have no transpositions of the form $(i\;n+i)$.
\end{enumerate}
It follows from~\ref{lemma3.7_iv_a} and~\ref{lemma3.7_iv_b} above 
that $\zeta^\tau_\mu(2n)$ does not depend on $n$. The result follows. \qedhere
\end{proof}


\begin{theo} \label{eln} Let $\mu\in\cP(2)$ with $|\mu|=k$.
\begin{enumerate}[(\roman*)]
\item\label{theo3.8_i} %\noi (i) 
For $k\leq n$ we have
\[
f(\mu,2n) = 2^{\ell(\mu)}M_{2\mu}(2n) + 
\sum_{\tau\in\cP(2,k-1)}\;\zeta^\tau_\mu(2n)M_{2\tau}(2n).
\]

\item\label{theo3.8_ii} %\noi (ii) 
For $n < k \leq 2n$ we have
\[
f(\mu,2n) = \sum_{\tau\in\cP(2,k-1)}\;\zeta^\tau_\mu(2n)M_{2\tau}(2n).
\]

\item\label{theo3.8_iii} %\noi (iii) 
For $2n < k$ and $\tau\in\cP(2),\;|\tau|\leq n$,
we have $\zeta^\tau_\mu(2n)=0$.
\end{enumerate}
\end{theo}

\begin{proof} \ref{theo3.8_i}~This follows from Theorem~\ref{ev1}.

%\noi 
Before proving parts~\ref{theo3.8_ii} and~\ref{theo3.8_iii} we make the following observation.

Let $2n\geq k$ so that $c_\mu(2n)\not= 0$. Then, from~\eqref{expf} and the
statement of Theorem~\ref{ev1}\ref{theo3.3_i} we have
\begin{equation} \label{ex}
f(\mu,2n)= d^\mu_\mu(2n)M_{2\mu}(2n) +
\sum_{\tau\in\cP(2,k-1)}d^\tau_\mu(2n)M_{2\tau}(2n).
\end{equation}
%
Fix $\tau\in\cP(2,k-1)$ with $|\tau|=j<k$. Define $\gamma_\tau$ to be the
number of perfect matchings $A$ in $\cM_{2j}$ with 
$d(\{[1, j+1], [2, j+2], \ldots ,[j, 2j]\}, A)=2\tau$. Thus the number
of perfect matchings $A$ in $\cM_{2n}$ with $d(I,A) = 2(\tau, 1^{n-j})$ is
$\gamma_\tau \binom{n}{j}$.

For $j\vee \lfloor \frac{k+1}{2} \rfloor \leq r \leq k$ define
\[
\alpha(r,\tau)=
|\{\pi\in C_{(\mu, 1^{2n-k})}\mid \supp(\pi)=\{1,2,\ldots
,r\},\;d(I,\pi\cdot I)=2(\tau,1^{n-j})\}|.
\]
%
Note that $\alpha(r,\tau)$ is defined and is independent of $n$ whenever
$n\geq \max\{r,k/2\}$.

A little reflection shows that
\begin{equation} %\nonumber
\begin{aligned}
d^{\tau}_{\mu}(2n) &= 
\frac{
{\ds{\sum_{r=j\vee \lfloor \frac{k+1}{2} \rfloor}^k}} \alpha(r,\tau){\binom{n}{r}}
}
{
\gamma_\tau{\binom{n}{j}}
}\\ \label{ex1}
&=
{\ds{\sum_{r=j\vee \lfloor \frac{k+1}{2} \rfloor}^k}} 
\;\frac{j!}{r!}\;\frac{\alpha(r,\tau)}{\gamma_\tau}\;(n-j)(n-j-1)\cdots
(n-r+1).
\end{aligned}
\end{equation}
%
The expression in~\eqref{ex1} above is valid for all $n\geq k/2$ and thus it
follows that
\begin{equation} \label{ex2}
\zeta^\tau_\mu(t)=
{\ds{\sum_{r=j\vee \left\lfloor \frac{k+1}{2} \right\rfloor}^k}} 
\;\frac{j!}{r!}\;\frac{\alpha(r,\tau)}{\gamma_\tau}\;\left(\frac{t}{2}-j\right)
\left(\frac{t}{2}-j-1\right)\cdots \left(\frac{t}{2}-r+1\right).
\end{equation}

\ref{theo3.8_ii}~Since $n<k$ we have $M_{2\mu}(2n)=0$ 
(and $d^\mu_\mu(2n)=0$ is undefined). The result now follows
from~\eqref{ex}, \eqref{ex1}, and~\eqref{ex2}  above.

\ref{theo3.8_iii}~This follows from~\eqref{ex2} on noting that, for $2n<k$ and
$|\tau|=j\leq n$ we have $n\in \{j,j+1,\ldots , 
\lfloor \frac{k+1}{2} \rfloor - 1\}$.
\end{proof}




\section{Content evaluation of symmetric functions}\label{Sect4}


We now consider algorithms for expressing
$\phi^\lambda_{\mu}$ and 
$\theta^{2\lambda}_{2\mu}$, for fixed $\mu\in \cP(2)$ and 
varying $\lambda\in \cY$, as content evaluations of symmetric functions.
The motivation comes from certain basic
results in the representation theory of symmetric groups~\cite{cst2,g,ov}.
We now recall these in items~\ref{Sect4_I}--\ref{Sect4_III} below (this will also be used
in the next section on eigenvectors).


\begin{enumerate}[(\roman*)]
\item\label{Sect4_I} %[(I)] 
Consider an irreducible $S_n$-module $V^{\lambda}$, for
$\lambda\in \cY_n$.
Since the branching is multiplicity free, the decomposition into irreducible
$S_{n-1}$-modules of $V^{\lambda}$ is
canonical.
Each of these modules, in turn, decompose canonically into
irreducible $S_{n-2}$-modules. Iterating this construction, we get a
canonical decomposition of $V^{\lambda}$ into irreducible $S_1$-modules,
\ie  one
dimensional subspaces. Thus, there is a canonical basis of $V^{\lambda}$,
determined
up to scalars, and  called the
\emph{Gelfand--Tsetlin (or GZ-) basis} of $V^{\lambda}$. 
Since $V^{\lambda}$ is irreducible an $S_n$-invariant inner product on 
$V^{\lambda}$ is unique \upto{} scalars and we note that the
GZ-basis is orthogonal with respect to this inner product.

\item\label{Sect4_II} %[(II)] 
For $i=1,2,\ldots ,n$ define $X_i = (1, i) + (2, i) + \cdots +
(i-1, i) \in \C[S_n]$. The $X_i$'s are called the
\emph{Young--Jucys--Murphy elements (YJM-elements)}. Note that $X_1=0$.


Consider
the Fourier transform, \ie  the algebra isomorphism
\begin{equation}\label{iso}
\C[S_n]\cong\bigoplus_{\lambda\in \cY_n} \End(V^{\lambda}),
\end{equation}
given by
\[
\pi \mapsto ( V^{\lambda} \buildrel {\pi}\over \rightarrow
V^{\lambda} \;:\;
\lambda
\in \cY_n),\;\;\pi\in S_n.
\]
We have identified a canonical basis, the GZ-basis, in each
$S_n$-irreducible. Let
$\D(V^{\lambda})$ consist of all operators on $V^{\lambda}$
diagonal in the GZ-basis of $V^{\lambda}$. It is known that the image of
$\bigoplus_{\lambda\in \cY_n} \D(V^{\lambda})$ (a maximal commutative
subalgebra of the right hand side of~\eqref{iso}) under the inverse  
Fourier transform is the subalgebra of $\C[S_n]$ generated by $X_1,\ldots
,X_n$, which is thus a maximal commutative subalgebra of $\C[S_n]$. 
It follows that the only common eigenvectors of $X_1,\ldots ,X_n$ in
an irreducible module $V^{\lambda}$ are (up to scalars) 
the elements of the GZ-basis of
$V^{\lambda}$. Moreover, the eigenvalues of the YJM elements    
on the GZ-basis vectors
in each irreducible module can also be written down once we parametrize the
GZ-basis by standard Young tableaux. We recall this in the next item below.

\item\label{Sect4_III} %\item[(III)] 
Let $\mu\in \cY$. A \emph{Young tableau of shape $\mu$}
is obtained by taking the Young diagram $\mu$ and filling its
$|\mu|$ boxes 
(bijectively) with the numbers $1,2,\ldots ,| \mu |$.
A Young tableau  is said to be \emph{standard} if the numbers in
the boxes strictly increase along each row and each column of the Young
diagram of $\mu$. Let $\tab(n,\mu)$, where $\mu \in
\cY_n$,
denote the set of all
standard Young tableaux of shape $\mu$ and let $\tab(n)=\cup_{\mu\in
\cY_n}\tab(n,\mu)$. There is a well known bijection between
$\tab(n,\lambda)$ and sequences $(\lambda_1,\lambda_2,\ldots ,\lambda_n)$
of Young diagrams with $\lambda_n = \lambda$ and $\lambda_{i}\in
\lambda_{i+1}^-$, for $1\leq
i \leq n-1$ (given $T\in \tab(n,\lambda)$, define $\lambda_i$ to be the 
diagram obtained by considering the boxes of $T$ containing the numbers 
$1,\ldots ,i$). It now easily follows from the branching rule that 
the GZ-basis of $V^{\lambda}$ can be parametrized by $\tab(n,\lambda)$.
Given $T\in \tab(n,\lambda)$, we write $v_T$ for the corresponding GZ-basis
vector of $V^{\lambda}$.

Given $T\in \tab(n,\lambda)$, the
eigenvalue of $X_i$ on $v_T$ is $c(b_T(i))$, the content of 
the box $b_T(i)$ of $T$ containing $i$. 

\end{enumerate}


Let $f=f(X_1,\ldots ,X_n)$ be a symmetric polynomial 
in $X_1,\ldots ,X_n$ (with complex coefficients).
By considering the $GZ$-basis of $V^{\lambda}$ we see that the action of $f$
on $V^{\lambda}$ is multiplication by the scalar $f(c(\lambda))$. Using the
Fourier transform, it now follows that any symmetric polynomial in
$X_1,\ldots ,X_n$ is in $Z[\C[S_n]]$. The converse
of this assertion is also true.

 
Given $n$ variables $x_1,\ldots ,x_n$ and $1\leq k \leq n$, we let
$e_k(x_1,\ldots ,x_n)$ denote the elementary symmetric polynomials. Suppose
$a=\{a_1,\ldots , a_n\}$ and $b=\{b_1,\ldots ,b_n\}$ are two multisets of
(complex) numbers of cardinality $n$. By considering the polynomials
$(x-a_1)\cdots (x-a_n)$ and $(x-b_1)\cdots (x-b_n)$ we see that $a=b$ as
multisets if and only if $e_k(a_1,\ldots ,a_n)=e_k(b_1,\ldots ,b_n)$, for
$1\leq k \leq n$.

Let $\lambda,\mu \in\cY_n$. The number of 0's
in $c(\lambda)$ is the number of boxes in the main diagonal of $\lambda$,
the number of 1's is the number of boxes in the first superdiagonal, the
number of -1's is the number of boxes in the first subdiagonal and so on. It
follows that $\mu = \lambda$ if and only if $c(\mu)=c(\lambda)$ if and only
if $e_k(c(\lambda))=e_k(c(\mu))$ for $1\leq k \leq n$.



Fix $\lambda \in \cY_n$. For $1\leq k \leq n$, define the following
symmetric polynomials in $X_1,\ldots ,X_n$:
\[
f_k(X_1,\ldots ,X_n) = \prod_{\mu} (e_k(X_1,\ldots ,X_n) -
e_k(c(\mu)),
\]
where the product is over all $\mu\in \cY_n$ with
$e_k(c(\mu))\not=e_k(c(\lambda))$.



Let $\mu\in \cY_n$. If $\mu\not= \lambda$ then, by the observation above,
$e_k(c(\mu))\not=e_k(c(\lambda))$ for some $1\leq k \leq n$. It follows that
\[
\left(\prod_{k=1}^nf_k(X_1,\ldots , X_n)\right)\cdot V^{\mu} =
%\left\{ \ba{ll}  
\begin{cases}
0 & \mbox{if }\mu\in \cY_n,\;\mu\not=\lambda, \\
\mbox{nonzero scalar} & \mbox{if }\mu=\lambda.
%                 \ea\right.
\end{cases}
\]
%
Using the Fourier transform we now see that 
every element in $Z[\C[S_n]]$ is a
symmetric polynomial in $X_1,\ldots ,X_n$. 

Thus $Z[\C[S_n]]$ consists of all symmetric polynomials 
in $X_1,\ldots ,X_n$. This is Jucys' fundamental 
theorem given, with a different proof, in~\cite{j}. Constructive proofs 
of this result are given in 
Murphy~\cite{mur1}, Moran~\cite{mo}, 
Diaconis and Greene~\cite{dg}, and Garsia~\cite{g}. A good
reference for this material is the book of
Cecchereni-Silberstein, Scarabotti, and Tolli~\cite{cst2}.


For instance, the symmetric polynomial $X_1+X_2+\cdots +X_n$ is the sum of
transpositions $c_{(2)}(n)$. The eigenvalue of $c_{(2)}(n)$ on $V^\lambda$
is $\phi^\lambda_{(2)}$. By considering any element of the GZ-basis of
$V^\lambda$ we see, from item (III) above, that the eigenvalue of
$X_1+\cdots +X_n$ on $V^\lambda$ is $p_1(c(\lambda))$. Thus we get
Frobenius' formula from the introduction. Similarly (letting $\epsilon$
denote the identity permutation),
\[
X_n^2 = \left(\sum_{i=1}^{n-1} (i\;n)\right) \left(\sum_{j=1}^{n-1}
(j\;n)\right) 
= \sum_{1\leq i,j \leq n-1, i\not=j} (j\;i\;n) + (n-1)\epsilon,
\]
%
and thus we get
\[
 X_1^2 + \cdots +X_n^2 = c_{(3)}(n) + \frac{n(n-1)}{2}\epsilon. 
\]
%
By considering the action of both sides of the identity above on a GZ-basis
element of $V^\lambda$ we get Ingram's formula from the introduction.

We thus come to the following basic problem in the present context: for fixed
$\mu\in \cP(2)$, write the conjugacy class
sum $c_\mu(n)\in Z[\C[S_n]]$ as a linear combination of, say, the
power sum symmetric functions in $X_1,\ldots ,X_n$ and say something about
the dependence of the coefficients on $n$. This problem was solved in
\cite{cgs,g}.

Given $f\in \Lambda[t]$ and $n\geq 1$ we define the \emph{YJM
evaluation} $f(n,X)$ to be the element of $Z[\C[S_n]]$ obtained from $f$ by
setting $t=n,\;x_i=0\mbox{ for }i>n$, and $x_i=X_i,\;i=1,\ldots ,n$.


The following result was proved in~\cite{cgs}. An algorithm
for constructing the symmetric function $W_\mu$ was given in~\cite{g}.
See~\cite{cst2} for another proof (Part (iv) below is taken from
Theorem 5.4.7 of this reference).

\begin{theo} \label{garsia}
For each $\mu\in\cP(2)$ there is an algorithm to compute a symmetric
function $W_{\mu}\in \Lambda[t]$ such that
\begin{enumerate}[(\roman*)]
\item\label{theo4.1_i} %\noi (i) 
$\{W_{\mu}\;:\;\mu\in\cP(2)\}$ is a $\Q[t]$-module 
basis of $\Lambda[t]$.

\item\label{theo4.1_ii} %\noi (ii) 
For $\mu\in\cP(2)$ and  $n\geq 1$ we have
\[
W_{\mu}(n,X) = c_\mu(n).
\]

\item\label{theo4.1_iii} %\noi (iii) 
For $\mu\in\cP(2)$ and $\lambda\in \cP$ we have
\[
W_{\mu}(c(\lambda)) = \phi^{\lambda}_{\mu}.
\]


\item\label{theo4.1_iv} %\noi (iv) 
Let $\mu\in\cP(2)$ with multiplicity of $i$ equal to $m_i$, $i\geq 2$.
The expansion of $W_{\mu}$ in the power sum basis has the form
\[
W_{\mu} = \sum_{\lambda\;\leq\;\ol{\mu}}\;a^{\lambda}_{\mu}(t)\;p_{\lambda},
\]
where
\begin{enumerate}[(\alph*)]
\item\label{theo4.1_iv_a} %(a) 
$a^{\lambda}_{\mu}(t)\in \Q[t]$ with degree $\leq
\frac{|\ol{\mu}|-|\lambda|}{2} + \ell(\ol{\mu}) - \ell(\lambda)$.

\item\label{theo4.1_iv_b} %(b) 
$a_{\mu}^{\ol{\mu}}=\frac{1}{\prod_{i\geq 2} m_i!}$ and
$a_{\mu}^{\lambda}\in\Q$ (\ie  does not depend on $t$) for
$|\lambda|=|\ol{\mu}|$.

\item\label{theo4.1_iv_c} %(c) 
$a^\lambda_\mu(t)=0$ if $|\ol{\mu}|$ and $|\lambda|$ do not have the
same parity.\qedhere
\end{enumerate}
\end{enumerate}
\end{theo}

\begin{rema} Let $\mu,\tau\in\cP(2)$. Using Theorem~\ref{garsia}\ref{theo4.1_i},
we can write
\[
W_\mu W_\tau = \sum_\lambda \omega^\lambda_{\mu,\tau}(t) \;W_\lambda,
\]
where the sum is over finitely many $\lambda\in \cP(2)$ and
$\omega^\lambda_{\mu,\tau}(t) \in \Q[t]$. From Theorem
\ref{garsia}\ref{theo4.1_ii} we have
\[
c_\mu(n) c_\tau(n) = \sum_\lambda \omega^\lambda_{\mu,\tau}(n) \;
c_\lambda(n),\;\;n\geq 1.
\]
In other words, the structure constants of the algebra of fixed conjugacy
classes (the so-called \emph{Farahat--Higman algebra})
are integer valued rational polynomials. See~\cite{cgs,cst2} for more
details.
\end{rema}

We now consider a perfect matching analog of Theorem~\ref{garsia} above. We
begin with a simple example. The symmetric polynomial $X_1+\cdots +X_{2n}$
is the conjugacy class sum $c_{(2)}(2n)$. It is easy to see (in the notation
of~\eqref{deff} above) that
\[
f((2),2n) = n\epsilon + 2M_{2(2)}(2n).
\]
%
Taking the eigenvalue of both sides on $V^{2\lambda}$ and using Frobenius'
result we get the formula (\cite{dh})
\[
\theta^{2\lambda}_{2(2)} = \left(\frac{p_1}{2} - \frac{t}{4}\right)(c(2\lambda)).
\]
%
The example above can be generalized to all fixed orbitals.
\begin{theo} \label{mks1}
For each $\mu\in\cP(2)$ there is an algorithm to compute a symmetric
function $E_{\mu}\in \Lambda[t]$ such that
\begin{enumerate}[(\roman*)]
\item\label{theo4.3_i} %\noi (i) 
$\{E_{\mu}\;:\;\mu\in\cP(2)\}$ is a $\Q[t]$-module basis of
$\Lambda[t]$.


\item\label{theo4.3_ii} %\noi (ii) 
For $\mu\in\cP(2)$ and $\lambda\in \cP$ we have
\[
E_{\mu}(c(2\lambda)) = \theta^{2\lambda}_{2\mu}.
\]


\item\label{theo4.3_iii} %\noi (iii) 
Let $\mu\in\cP(2)$ with multiplicity of $i$ equal to $m_i$,
$i\geq 2$.
The expansion of $E_{\mu}$ in the power sum basis has the form
\[
E_{\mu} = \sum_{\lambda\;\leq\;\ol{\mu}}\;b^{\lambda}_{\mu}(t)\;p_{\lambda},
\]
where
\begin{enumerate}[(\alph*)]
\item\label{theo4.3_iii_a} %(a) 
$b^{\lambda}_{\mu}(t)\in \Q[t]$ with degree $\leq
|\ol{\mu}|-|\lambda| + \ell(\ol{\mu}) - \ell(\lambda)$.

\item\label{theo4.3_iii_b} %(b) 
$b_{\mu}^{\ol{\mu}}=\frac{1}{2^{\ell(\mu)}\prod_{i\geq 2} m_i!}$ and
$b_{\mu}^{\lambda}\in\Q$ (\ie  does not depend on $t$) for
$|\lambda|=|\ol{\mu}|$.\qedhere
\end{enumerate}
\end{enumerate}
\end{theo}

\begin{rema} Let $\mu,\tau\in\cP(2)$. Using Theorem~\ref{mks1}\ref{theo4.3_i} %,
we can write
\[
E_\mu E_\tau = \sum_\lambda \beta^\lambda_{\mu,\tau}(t) \;E_\lambda,
\]
where the sum is over finitely many $\lambda\in \cP(2)$ and
$\beta^\lambda_{\mu,\tau}(t) \in \Q[t]$. From Theorem
\ref{mks1}\ref{theo4.3_ii}  we have
\[
M_{2\mu}(2n) M_{2\tau}(2n) = \sum_\lambda \beta^\lambda_{\mu,\tau}(2n) \;
M_{2\lambda}(2n),\;\;n\geq 1.
\]
In other words, the structure constants of the algebra of fixed orbitals
are integer valued rational polynomials. For a direct study of these
structure constants
in much more detail see the two recent papers~\cite{ac,co,t} (our focus 
in this paper is more on
the eigenvalues and eigenvectors of $\cB_{2n}$).
These papers work in
the context of the Hecke algebra of the Gelfand pair $(S_{2n},H_n)$ (which
explains the extra factor $2^n n!$ in their structure constants). 
\end{rema}

\begin{proof} We proceed by induction on $|\mu|$. 
Set $E_{(0)}=1$ and
assume that, for some $k\geq 1$, we have defined $E_{\mu} \in \Lambda[t]$, 
for all $\mu\in \cP(2)$
with $|\mu|\leq k-1$, such that 
items~\ref{theo4.3_ii}  and~\ref{theo4.3_iii} 
in the statement of the theorem are satisfied.

Now let $\mu\in \cP(2)$ with $|\mu|=k$ and with multiplicity of $i$ equal to
$m_i,\;i\geq 2$. 
Define
\[
E_{\mu} = \frac{1}{2^{\ell(\mu)}}\;\left\{W_{\mu} -
\sum_{\tau\in\cP(2,k-1)}
\zeta^{\tau}_{\mu}(t)\;E_{\tau}\right\}.
\]
We shall now verify items~\ref{theo4.3_ii}  and~\ref{theo4.3_iii}\ref{theo4.3_iii_a}, \ref{theo4.3_iii}\ref{theo4.3_iii_b}  
in the statement for $E_{\mu}$. 
We begin with item~\ref{theo4.3_iii}.


By Theorem~\ref{garsia}\ref{theo4.1_iv}  we can write 
\begin{equation} \label{t1}
W_{\mu} = \sum_{\lambda\;\leq\;\ol{\mu}}\;a^{\lambda}_{\mu}(t)\;p_{\lambda},
\end{equation}
%
where degree of $a^{\lambda}_{\mu}(t) 
\leq
\frac{|\ol{\mu}|-|\lambda|}{2} + \ell(\ol{\mu}) - \ell(\lambda)
\leq
|\ol{\mu}|-|\lambda| + \ell(\ol{\mu}) - \ell(\lambda)$.

Let $\tau\in \cP(2)$ with $|\tau|\leq k-1$. 
By the induction hypothesis we can write
\begin{equation}  \label{t2}
E_{\tau} = \sum_{\lambda\;\leq\;\ol{\tau}}\;b^{\lambda}_{\tau}(t)
\;p_{\lambda},
\end{equation}
where degree of $b^{\lambda}_{\tau}(t) \leq
|\ol{\tau}|-|\lambda| + \ell(\ol{\tau}) - \ell(\lambda)$.


Now, degree of $\zeta^\tau_\mu(t) \leq |\mu| - |\tau| =
|\mu|-|\ol{\tau}| - \ell(\ol{\tau})$ (by Lemma~\ref{pol1}\ref{lemma3.7_ii}) 
and thus degree of
$\zeta^\tau_\mu(t)b^\lambda_\tau(t) \leq |\mu| - |\lambda| - \ell(\lambda)
= |\ol{\mu}|-|\lambda|+\ell(\ol{\mu})-\ell(\lambda)$.

By Lemma~\ref{pol1}\ref{lemma3.7_iii} we have that $\zeta^\tau_\mu(t)\not= 0$ implies 
$\ol{\tau}\leq \ol{\mu}$. Item~\ref{theo4.3_iii}\ref{theo4.3_iii_a}
now follows from~\eqref{t1} and~\eqref{t2}. 

Item~\ref{theo4.3_iii}\ref{theo4.3_iii_b} also
follows from~\eqref{t1} and~\eqref{t2} by using the induction hypothesis,
Theorem~\ref{garsia}~\ref{theo4.1_iv}\ref{theo4.1_iv_b}  and
Lemma~\ref{pol1}\ref{lemma3.7_iii},~\ref{lemma3.7_iv}. 


We now verify item~\ref{theo4.3_ii}. Let $\lambda\in \cY_m$ and consider the following
three cases:
\begin{enumerate}[(\roman*)]
\item\label{proof_theo4.3_a} %\noi (a) 
$k\leq m$: This follows from Theorems~\ref{garsia}\ref{theo4.1_iii}, Theorem
\ref{eln}\ref{theo3.8_i},
and the induction hypothesis.

\item\label{proof_theo4.3_b}  %\noi (b) 
$m < k \leq 2m$: 
We need to show that $E_\mu(c(2\lambda))=0$.
This follows from
Theorem~\ref{garsia}\ref{theo4.1_iii}, Theorem~\ref{eln}\ref{theo3.8_ii}, and the induction
hypothesis.

\item\label{proof_theo4.3_c}  %\noi (c) 
$k>2m$: We need to show that $E_\mu(c(2\lambda))=0$.
By Theorem~\ref{garsia}\ref{theo4.1_iii} we have $W_\mu(c(2\lambda))=0$. By
the induction hypothesis $E_\tau(c(2\lambda))=0$ for $m<|\tau|$ and by 
Lemma~\ref{eln}\ref{theo3.8_iii} $\zeta^\tau_\mu(2m)=0$ for $|\tau|\leq m$. The result
follows.
\end{enumerate}

That completes the proof of items~\ref{theo4.3_ii} and~\ref{theo4.3_iii}. Item~\ref{theo4.3_i}  now follows from
Theorem~\ref{garsia}\ref{theo4.1_i} and the triangular definition of the $E_\mu$. \qedhere
\end{proof} 


It is easily seen that property~\ref{theo4.3_ii} of Theorem~\ref{mks1} characterizes the
symmetric function $E_\mu$.


\begin{coro} Let $f,g\in \Lambda[t]$. Suppose that there exists $n_0$ 
such that $f(c(2\lambda))=g(c(2\lambda))$ for all
$\lambda\in \cY,\;|\lambda|\geq n_0$. Then $f=g$. 
\end{coro}

\begin{proof} Suppose $f\not= g$. Write
\begin{equation} \label{k1}
f-g = a_{\mu_1}(t)E_{\mu_1}+ a_{\mu_2}(t)E_{\mu_2}+\cdots +
a_{\mu_k}(t)E_{\mu_k},
\end{equation}
%
where $\mu_i\in \cP(2)$ for all $i$ and $a_{\mu_i}(t)\not= 0$ for all $i$.

Choose a positive integer $m$ such that $m\geq n_0$, $|\mu_i|\leq m$ for
$1\leq i \leq k$, and $a_{\mu_i}(2m)\not= 0$ for $1\leq i \leq k$.
We can now rewrite~\eqref{k1} (by adding terms with zero coefficients) as
\begin{equation} \label{k2}
f-g  =  \sum_{\mu\in\cP(2,m)}\;a_{\mu}(t)E_{\mu},
\end{equation}
%
where not all $a_{\mu}(2m)$ are zero.

Evaluate both sides of~\eqref{k2} on the contents of $2\lambda$, for every
$\lambda\vdash m$. By assumption we get
\begin{equation} \label{k3}
0  =  \sum_{\mu\in\cP(2,m)}
a_{\mu}(2m)\hat{\theta}^{2\lambda}_{2(\mu,1^{m-|\mu|})},\quad\lambda\vdash m.
\end{equation}
%
From~\eqref{k3} we get that a nontrivial linear combination of
the columns of (the nonsingular matrix) $\hat{\Theta}(2m)$ is zero, 
a contradiction. \end{proof}

\begin{exam}\label{wep}  
Below we give tables of $W_{\mu}$ and $E_{\mu}$ polynomials for $|\mu|\leq
4$. The $W_{\mu}$ polynomials are from~\cite{cgs,g} while the $E_{\mu}$
polynomials were calculated using the definition given 
in the proof of Theorem~\ref{mks1}.
\begin{align*} 
W_{(0)} &= 1, &
E_{(0)} &= 1 \\
W_{(2)} &= p_1,&
E_{(2)} &= \frac{p_1}{2}- \frac{t}{4}\\
W_{(3)} &= p_2 -\frac{t(t-1)}{2}, &
E_{(3)} &= \frac{p_2}{2} - p_1 + \frac{3t-t^2}{4}\\
W_{(2,2)} &= \frac{p_1^2}{2} - \frac{3p_2}{2} + \frac{t(t-1)}{2},&
E_{(2,2)} &= \frac{p_1^2}{8} - \frac{3p_2}{4} + \frac{(10-t)p_1}{8} +
\frac{9t^2-24t}{32}\\
W_{(4)}&= p_3 - (2t-3)p_1, & 
E_{(4)} &= \frac{p_3}{2} -\frac{9p_2}{4} 
+ \frac{(11-2t)p_1}{2} + \frac{8t^2 - 23t}{8}
\end{align*}

We can calculate the eigenvalue table $\hat{\Theta}(8)$ of $\cB_8$ using the
list above. We list the elements of $\cP_4$ in the order $\{(1^4), (2,1^2),
(2,2), (3,1), (4)\}$ and the elements of $\cY_4$ in the order $\{(4), (3,1),
(2,2), (2,1^2), (1^4)\}$. We have
\[ 
\hat{\Theta}(8) = %\left[ \ba{rrrrr} 
\begin{bmatrix}
1&12&12&32&48\\
1&5&-2&4&-8\\
1&2&7&-8&-2\\
1&-1&-2&-2&4\\
1&-6&3&8&-6 
%\ea\right]
\end{bmatrix}
.
\]

\end{exam}


\section{Eigenvectors: similar algorithms for \texorpdfstring{$\hat{\phi}^\lambda_\mu$}{phi lambda mu} and \texorpdfstring{$\hat{\theta}^{2\lambda}_{2\mu}$}{theta 2lambda 2mu}}\label{Sect5}

In this section we shall give an inductive procedure to write down a specific 
eigenvector (a so called first GZ-vector) in each eigenspace of the (left)
actions of $Z[\C[S_n]]$ and $\cB_{2n}$ on $\C[S_n]$ and $\C[\cM_{2n}]$
respectively. This then yields simple inductive algorithms to calculate
$\hat{\phi}^\lambda_\mu$ and $\hat{\theta}^{2\lambda}_{2\mu}$ (that do not
depend on knowing the symmetric group characters).

To begin with, it will be useful to know (as suggested
by~\eqref{rrs} and Lemma~\ref{mfree}) how
GZ-vectors behave under restriction and induction.


The case of restriction follows from the following result.

\begin{lemm} \label{res} Let $\lambda\in \cY_n$ and consider the irreducible
$S_n$-module $V^\lambda$.

\begin{enumerate}[(\roman*)]
\item\label{lemma5.1_i} %(i) 
Let $v\in V^\lambda$ be an eigenvector for the action of $X_1,\ldots
,X_{n-1}$. Then $v$ is also an eigenvector for the action of $X_n$.

\item\label{lemma5.1_ii} %(ii)  
Suppose $T\in \tab(n,\lambda)$ and $v\in V^\lambda$ satisfy
\[
X_i\cdot v = c(b_T(i))v,\;1\leq i \leq n-1.
\]
Then $X_n\cdot v = c(b_T(n))v$. 


\item\label{lemma5.1_iii} %(iii) 
The GZ-basis of $V^{\lambda}$ is the union
of the GZ-bases of $V^{\mu}$, as $\mu$ varies over $\lambda^-$.
\end{enumerate}
\end{lemm}

\begin{proof} \ref{lemma5.1_i} %(i) 
Let $X$ be the sum of all transpositions in $S_n$. Note that
$X=X_1+\cdots +X_n$ and that $X$ is in the center of $\C[S_n]$. Thus, by
Schur's lemma, 
the action of $X$ on $V^\lambda$ is multiplication by a scalar. Thus
$v$ is an eigenvector for the action of $X_n = X - (X_1+\cdots + X_{n-1})$.

\ref{lemma5.1_ii} %(ii) 
The action of $X$ on $V^{\lambda}$ is multiplication by a scalar
$\alpha$. By considering a GZ-vector of $V^{\lambda}$ we see that $\alpha$
is equal to the 
sum of the contents of all boxes of the Young diagram $\lambda$.
The result follows.

\ref{lemma5.1_iii} %(iii) 
This follows from parts~\ref{lemma5.1_i} and~\ref{lemma5.1_ii} above using the branching rule
\eqref{brres}.
\end{proof}

Now we consider the case of induction. Since we will also be applying this
construction to the case of the regular module $\C[S_n]$, which is not
multiplicity free, we first extend the notion of a GZ-vector to a
$S_n$-module with a single isotypical component.

Let $V$ be a $S_n$-module with a single isotypical component, the
irreducibles occuring in $V$ all being isomorphic to $V^\lambda$, for some
$\lambda\in \cY_n$. Let $T\in \tab(n,\lambda)$ and define the following subspace of $V$:
%
\[
V_T = \{v\in V\mid X_i(v)=c(b_T(i))v,\;i=1,\ldots ,n\}.
\]
%
It is easy to see that we have the canonical decomposition:
%
\[
 V = \bigoplus_{T\in \tab(n,\lambda)} V_T.
\]
%
By a { \em GZ-vector of $V$ associated to $T$} we mean a
nonzero vector in $V_T$.


For a Young diagram $\lambda$ let 
$\cO(\lambda)$ be the set of boxes corresponding to the outer
corners of $\lambda$. Note that no two boxes in $\cO(\lambda)$ have the same
content. For $\lambda\in \cY_n$, we 
denote the isotypical component of $V^\lambda$ in a $S_n$-module $W$ by
$W^\lambda$.
 

%
\begin{lemm} \label{ind} Let $W$ be a $S_n$-module and let
\[
U = \C[S_{n+1}] \otimes_{\C[S_n]} W
=\ind_{\;S_n}^{\;S_{n+1}}(W).
\]
Let $T\in\tab(n,\lambda)$ and let $v\in W^\lambda$ be a GZ-vector associated
to $T$.
Let $\mu\in \lambda^+$ and let $b\in \cO(\lambda)$ be
the box added to $\lambda$ to get $\mu$. Let $S\in \tab(n+1,\mu)$ be the
standard tableau obtained from $T$ by adding $n+1$ in box $b$. 
%
Then 
%
\[
 \prod_{d\in \cO(\lambda)\setminus\{b\}}(X_{n+1} - c(d)\epsilon)\cdot
(\epsilon\otimes v)
\]
%
is a GZ-vector of $U^\mu$ associated to $S$.
\end{lemm}
\begin{proof} It suffices to prove the case $W=V^\lambda$. In this case $v=v_T$ (\upto{}
scalars) and, by the branching rule, $U=\oplus_{\tau\in \lambda^+} V^\tau$. 
Clearly, $\epsilon\otimes v_T \in U$ is $\not= 0$. Write 
$\epsilon\otimes v_T=\sum_{\tau\in \lambda^+} v_\tau$, where $v_\tau \in V^\tau$.

For $1\leq i \leq n$ we have $X_i\cdot (\epsilon\otimes v_T) = 
\epsilon\otimes (X_i\cdot v_T) = c(b_T(i))(\epsilon\otimes v_T)$. It follows that
$X_i \cdot v_\tau = c(b_T(i))v_\tau$, $1\leq i \leq n,\;\tau\in \lambda^+$. 
From part~\ref{lemma5.1_ii}
of Lemma~\ref{res} it now follows that $X_{n+1}\cdot v_\tau = c(d)
v_\tau,\;\tau\in \lambda^+$,
where $d$ is the box added to $\lambda$ to get $\tau$. 
The result follows. \end{proof}


Let $\lambda = (\lambda_1,\ldots ,\lambda_t)\vdash n$. Define the standard
tableau $R\in \tab(n,\lambda)$ by filling the boxes of $\lambda$ with the
integers $1,2,\ldots ,n$ in \emph{row major order}, \ie  the first row is
filled with the numbers $1,2,\ldots , \lambda_1$ (from left to right), the
second row with the numbers $\lambda_1+1,\lambda_1+2,\ldots ,
\lambda_1+\lambda_2$ and
so on. We call $R$ the \emph{first tableau} in $\tab(n,\lambda)$ and 
given a $S_n$-module $W$, a nonzero vector $v$ in 
$(W^\lambda)_R$ will be called  
\emph{a first Gelfand--Tsetlin vector} in $W^\lambda$.

We now give an example of a first GZ-vector and rederive a result from
\cite{gm1,l}. First, we make a definition. The \emph{perfect matching
derangement operator}
\[
D_{2n}:\C[\cM_{2n}] \rar \C[\cM_{2n}]
\]
%
is defined as follows: for $A\in \cM_{2n}$ set $D_{2n}(A) = \sum_B B$, where
the sum is over all $B\in \cM_{2n}$ with $d(A,B)$ having no part equal to 2.
In other words, $D_{2n}=\sum_\mu N_{2\mu}$, where the sum is over all
$\mu\in \cP(2)$ with $|\mu|=n$. For $\lambda\vdash n$, let
$m^{2\lambda}_{2n}$ denote the eigenvalue of $D_{2n}$ on $V^{2\lambda}$.


Fix a matching $A\in \cM_{2n}$. The number of $B\in \cM_{2n}$ with $d(A,B)$
having no part equal to 2 is easily seen (by inclusion-exclusion) to be
\[
d(2n)=\sum_{i=0}^{n}(-1)^i \binom{n}{i} (2n-2i-1)!!
\]
where we let $(-1)!!=1$.

We denote by $v_{2\lambda}$ the first GZ-vector in the subspace
$V^{2\lambda}$ of $\C[\cM_{2n}]$. For the rest of this section
fix $J=\{[1,2],[3,4],\ldots ,[2n-1,2n]\}\in \cM_{2n}$. 


%\begin{exam} 
\begin{enonce}[remark]{Examples}\label{glm} \ \\*[-1em]
\begin{enumerate}[(\roman*)]
\item\label{exam5.3_i} %(i) 
Clearly, $v_{2(n)} = \sum_{A\in \cM_{2n}} A$.
Let $\mu\in\cP_n$.
The coefficient of $J$ in $v_{2(n)}$ is $1$ while the coefficient of $J$ 
in $N_{2\mu}(v_{2(n)})$ (respectively, $D_{2n}(v_{2(n)})$) is 
$|\cM(J,2\mu)|$ (respectively, $d(2n)$). It follows that
\begin{align*}
\hat{\theta}^{2(n)}_{2\mu} &= |\cM(J,2\mu)|,\\
m^{2(n)}_{2n} &= d(2n).
\end{align*}
It is easy to see that
\[
|\cM(J,2\mu)| = \frac{2^n n!}{z_{\mu}2^{\ell(\mu)}}.
\]



\item\label{exam5.3_ii} %(ii) 
We now write down $v_{2(n-1,1)}$. Using the inductive structure of
$\C[\cM_{2n}]$ given in Lemma~\ref{mfree}~\ref{lemma2.1_v}, \ref{lemma2.1_vi} and applying 
Lemmas~\ref{res} and~\ref{ind}, we get from item~\ref{exam5.3_i} above,
\begin{center}
$\begin{aligned}
v_{2(n-1,1)} &= \left(X_{2n-1} - (2n-2)\epsilon\right)\cdot\left(
\sum_{A\in \cM_{2n-2}} (A\cup
\{[2n-1,2n]\})\right)\\
  &= \left( \sum_{i=1}^{2n-2} \sum_{A\in \cM_{2n}, [i,2n]\in A} A\right)
  - (2n-2)\left(\sum_{A\in \cM_{2n}, [2n-1,2n]\in A} A\right)\\
  &= \sum_{A\in \cM_{2n}} A - (2n-1)
                \left(\sum_{A\in \cM_{2n}, [2n-1,2n]\in A} A\right).
\end{aligned}
$%
\vspace*{\belowdisplayskip}
\end{center}
The coefficient of $J$ in $v_{2(n-1,1)}$ is $-(2n-2)$ and the coefficient of
$J$ in $D_{2n}(v_{2(n-1,1)})$ is $d(2n)$. We can easily
calculate the coefficient of $J$ in $N_{2\mu}(v_{2(n-1,1)})$. Two cases
arise:
\begin{enumerate}[(\alph*)]
\item\label{exam5.3_ii_a} %(a) 
$\mu$ has no part equal to $1$: 
The coefficient of $J$ in $N_{2\mu}(v_{2(n-1,1)})$ 
is $|\cM(J,2\mu)|$.

\item\label{exam5.3_ii_b} %(b) 
$\mu$ has a part equal to $1$: Let $\mu'\in \cP_{n-1}$ be obtained from
$\mu$ by deleting a $1$ from the parts of $\mu$ and let
$J'=\{[1,2],[3,4],\ldots ,[2n-3,2n-2]\}\in \cM_{2n-2}$. 
The coefficient of $J$ in $N_{2\mu}(v_{2(n-1,1)})$ is 
$|\cM(J,2\mu)|- (2n-1)|\cM(J',2\mu')|$.
\end{enumerate}
It follows that 
\begin{center}
\vspace*{\abovedisplayskip}
$\hat{\theta}^{2(n-1,1)}_{2\mu} = %\left\{ \ba{ll}
\begin{cases}
\frac{|\cM(J,2\mu)|}{-(2n-2)}, & \mbox{if 1 is not a part of }\mu,\\
%&\\
\frac{|\cM(J,2\mu)| - (2n-1)|\cM(J',2\mu')|}{-(2n-2)}, 
& \mbox{if 1 is a part of }\mu,
%\ea \right.
\end{cases}
$
\vspace*{\belowdisplayskip}
\end{center}
%
and that 
\begin{center}
\vspace*{\abovedisplayshortskip}
$
m^{2(n-1,1)}_{2n} = \frac{d(2n)}{-(2n-2)}.
$
\vspace*{\belowdisplayshortskip}
\end{center}
\end{enumerate}
\end{enonce}


In principle, it is possible to extend the method of Example~\ref{glm} to
certain other eigenspaces, such as $V^{2(n-2,2)}$ and $V^{2(n-2,1,1)}$, and
derive complicated explicit formulas for $m^{2(n-2,2)}_{2n}$ and
$m^{2(n-2,1,1)}_{2n}$. We do not pursue this here. 
Instead we shall show how Lemmas~\ref{res} and
\ref{ind} can be used to give a practical
recursive
algorithm for calculating $\hat{\theta}^{2\lambda}_{2\mu}$. 


Before developing our algorithm we shall show that the coefficient 
of $J$ in the first GZ-vector of $V^{2\lambda}$ is nonzero.

The construction of Lemma~\ref{ind} leads to the
following elements $p_T\in \C[S_n],\;T\in \tab(n)$ (originally
defined in~\cite{mur2} and further studied in  
\cite{g,cst2}):  

\begin{enumerate}[(\roman*)]
\item\label{Sect5_i} %(i) 
$p_T=\epsilon$ for $T$ the unique element of $\tab(1)$.

\item\label{Sect5_ii} %(ii) 
Let $T\in \tab(n+1,\mu)$, where $\mu\in \cY_{n+1}$. Let $b$ be the 
box corresponding to the inner corner of $\mu$ containing $n+1$. Drop this
box from $\mu$ to get $\lambda\in \cY_n$ and drop this box from $T$ to get
$S\in \tab(n,\lambda)$. Note that $b\in \cO(\lambda)$. Inductively define
\begin{center}
\vspace*{\abovedisplayshortskip}
$\displaystyle
p_T = p_S \left(
\prod_{d\in \cO(\lambda)\setminus\{b\}}
\frac{X_{n+1} - c(d)\epsilon}{c(b)-c(d)}\right).
$
\vspace*{\belowdisplayshortskip}
\end{center}
\end{enumerate}

We consider every $V^\lambda$ to be equipped with a (unique \upto{} scalars)
$S_n$-invariant inner product. The fundamental property of the 
elements $p_T$ is given in part~\ref{theo5.4_i} of the result below and 
parts~\ref{theo5.4_ii},~\ref{theo5.4_iii} are simple consequences of part~\ref{theo5.4_i}.

\goodbreak
\begin{theo} \label{md}\ \\*[-1em]
\begin{enumerate}[(\roman*)]
\item\label{theo5.4_i} %(i) 
Let $\lambda, \mu \in \cY_n$, $\lambda \not= \mu$ and let 
$T\in \tab(n,\mu)$. 
\begin{enumerate}[(\alph*)]
\item\label{theo5.4_i_a} %(a) 
The action of $p_T$ on $V^\lambda$ is the 
zero map, \ie  $p_T\cdot v = 0$ for all $v\in V^\lambda$.

\item\label{theo5.4_i_b} %(b) 
The action of 
$p_T$ on $V^\mu$ is orthogonal projection onto the one dimensional 
subspace spanned by the GZ-vector $v_T$.
\end{enumerate}

\item\label{theo5.4_ii} %(ii) 
We have the following identity in $\C[S_n]$:
\begin{equation} \label{proj}
\sum_{T\in \tab(n)}p_T = \epsilon.
\end{equation}

\item\label{theo5.4_iii} %(iii) 
For $T\in \tab(n,\mu)$ the coefficient of 
$\epsilon$ in $p_T$ is nonzero.
\end{enumerate}
\end{theo}

\begin{proof} 
\ref{theo5.4_i}\ref{theo5.4_i_a} Let $S\in \tab(n,\lambda)$ and let $v_S$ be the corresponding GZ-vector
in $V^\lambda$. It is enough to show that $p_T\cdot v_S=0$ (as the GZ-vectors
form a basis of $V^\lambda$).

The element 1 is in row 1, column 1 in both $T$ and $S$. 
Let $i\in\{2,\ldots ,n\}$ be the least integer whose coordinates differ 
in $T$ and $S$. Let $d$ be the box of $S$ containing $i$. Then 
$p_T$ contains the term $(X_i - c(d)\epsilon)$. Since $v_S$ is the GZ-vector 
corresponding to $S$ we have $X_i\cdot v_S=c(d)v_S$. It follows that 
$p_T\cdot v_S=0$.

\ref{theo5.4_i}\ref{theo5.4_i_b} Let $S\in \tab(n,\mu)$ with $T\not= S$ and with $v_S$ the 
corresponding GZ-vector. Then a similar argument as in the previous paragraph
shows that $p_T\cdot v_S=0$. From the definition of $p_T$ it follows that
$p_T\cdot v_T = v_T$. Since the GZ-basis is orthogonal with respect to the
$S_n$-invariant inner product on $V^\mu$ the result follows.

\ref{theo5.4_ii} Decompose $\C[S_n]$ into irreducibles and consider the basis of $\C[S_n]$
that is the union of the GZ-bases of each of the irreducibles. 
Part~\ref{theo5.4_i} shows that
the left hand side of~\eqref{proj} acts as the identity on each basis 
element. The result follows since the regular representation is faithful.

\ref{theo5.4_iii} Given an $S_n$-module $W$ and $a\in \C[S_n]$ by $\Tr_{W}(a)$ we mean
the trace of the action of $a$ on $W$. Let us first recall the Fourier
inversion formula. If $a=\sum_{\pi\in S_n} a_\pi \pi \in \C[S_n]$
then
\begin{equation} \label{fif}
a_\pi = \frac{1}{n!}\sum_{\lambda\in \cY_n} \dim(V^\lambda)
                                 \Tr_{V^\lambda}(\pi^{-1}a).
\end{equation}
%
The coefficient of $\epsilon$ in $p_T$ is thus
\[
\frac{1}{n!}\sum_{\lambda\in \cY_n} \dim(V^\lambda)
                                 \Tr_{V^\lambda}(p_T).
\]
By part~\ref{theo5.4_i}\ref{theo5.4_i_a} %(i)(a)
the sum above is equal to $\frac{1}{n!} \dim(V^\mu)\Tr_{V^\mu}(p_T)$ and by
part~\ref{theo5.4_i}\ref{theo5.4_i_b} %(i)(b) 
this is equal to $\frac{\dim(V^\mu)}{n!}$. \end{proof}


\begin{lemm} \label{md1}\ \\*[-1em]
\begin{enumerate}[(\roman*)]
\item\label{lemma5.5_i} Let $\lambda\in\cY_n$ and $T\in \tab(n,\lambda)$. Then 
$p_T\in \C[S_n]^\lambda$ and is itself a GZ-vector associated to $T$.

\item\label{lemma5.5_ii} %(ii) 
Let $S,T\in\tab(n)$. Then $p_Tp_S=\delta_{TS}\;p_S$.

\item\label{lemma5.5_iii} %(iii) 
Let $W$ be a $S_n$-module. Let $0\not=v\in W$, $\lambda\in\cY_n$, and
$T\in\tab(n,\lambda)$. Then $v\in W^\lambda$ and is a GZ-vector associated to
$T$ if and only if $p_T\cdot v=v$.
\end{enumerate}
\end{lemm}

\begin{proof} \ref{lemma5.5_i}~Consider the GZ-vector
$\epsilon$ of $V^{(1)}$. It follows from~\eqref{rrs} and Lemma~\ref{ind} that
\[
 p_T\cdot \epsilon = p_T
\]
is a GZ-vector of $\C[S_n]^\lambda$ associated to $T$.

\ref{lemma5.5_ii}~This follows from part~\ref{lemma5.5_i} and Theorem~\ref{md}\ref{theo5.4_i}.

\ref{lemma5.5_iii}~This follows by decomposing $W$ into irreducibles, writing $v$ as 
a linear combination of the basis of $W$ consisting of the 
union of the GZ-bases of the irreducibles in the decomposition and applying
Theorem~\ref{md}\ref{theo5.4_i}. 
\end{proof}

We now consider the coefficient of $J$ in GZ-vectors in $\C[\cM_{2n}]$.
Given $\lambda\in \cY_n$, call $T\in \tab(2n,2\lambda)$ \emph{good} if
$i+1$ is in the same row as $i$ (and therefore immediately 
following $i$) for all odd $i$. For instance, the first tableau is good.
It is easily seen that the number of good tableaux in $\tab(2n,2\lambda)$
is equal to $|\tab(n,\lambda)|$.

\begin{lemm} \label{nonz1}
Let $\lambda\in \cY_n$ and $T\in \tab(2n,2\lambda)$. Then 
\begin{enumerate}[(\roman*)]
\item\label{lemma5.6_i} %(i) 
$p_T\cdot J\not=0$ implies that the GZ-vector in $\C[\cM_{2n}]^{2\lambda}$
associated to $T$ is $p_T\cdot J$.

\item\label{lemma5.6_ii} %(ii) 
$p_T\cdot J\not=0$ if and only if $T$ is good.  
\end{enumerate}
\end{lemm}
%

\begin{proof}\ref{lemma5.6_i}~This follows from parts~\ref{lemma5.5_ii} and~\ref{lemma5.5_iii} of Lemma \ref{md1}.

\ref{lemma5.6_ii}~If the recursive definition of $p_T$ is expanded out it will be a
product of terms of the form $\frac{X_j - c(d)\epsilon}{c(b)-c(d)}$. Collect 
all the terms with $j$ even and call the product $p_T^e$ and collect
all the terms with $j$ odd and call the product $p_T^o$. 
Then $p_T=p_T^ep_T^o$. 

(if) It follows from Lemma \ref{mfree}\ref{lemma2.1_v},~\ref{lemma2.1_vi} and Lemma \ref{ind} that 
$v=p_T^o\cdot J \not= 0$ is the GZ-vector associated to $T$. 
We claim that $p_T^e \cdot v = v$. 
This will prove the result. Let $j$ be even and let it appear in box $b$
in $T$. Then $X_j\cdot v = c(b)v$. By definition every term involving $X_j$
in $p_T^e$ will be of the form $\frac{X_j - c(d)\epsilon}{c(b)-c(d)}$ where
$b\not=d$. The claim follows. 

(only if) Suppose $T$ is not good. Let $2j$ be the least even number not in
the same row as $2j-1$. Define a standard tableau $T'$ with $2j$ boxes 
as follows. Let $T_{2j-1}$ be the standard 
tableau obtained from $T$ by
considering the boxes containing the numbers $\{1,2,\ldots ,2j-1\}$. Now add
a box $b$ at the end of the row containing $2j-1$ and 
fill it with the number $2j$. 
Note that $T'\in \tab(2j,\lambda')$ (for some $\lambda'$) is good.

Set $q^o_T$ to be the product of all odd terms in $p_T$ involving
$\{X_1,X_3,\ldots ,X_{2j-1}\}$. It follows from Lemma \ref{mfree}\ref{lemma2.1_v},~\ref{lemma2.1_vi}
and Lemma \ref{ind} that $v=q^o_T\cdot J$ satisfies $X_{2j}\cdot v = c(b)v$.
Now $p_T$ has a term of the form $\frac{X_{2j} - c(b)\epsilon}{c(d)-c(b)}$,
where $d\not=b$, 
and thus it follows that $p_T\cdot J=0$.
\end{proof} 


It remains to show that the coefficient of $J$ in $p_T\cdot J$ is nonzero
whenever $T$ is good.
At this point it is convenient to switch to the Gelfand pair viewpoint and 
consider a realization of $\C[\cM_{2n}]$ as a submodule of $\C[S_{2n}]$ 
(see Sections~7.1 and~7.2 in~\cite{m}).

Let $H_n$ denote the subgroup of all permutations $\pi\in S_{2n}$ 
with $\pi\cdot J=J$. Then $|H_n|=2^n n!$ and we set
\[
e = \frac{1}{2^n n!} \sum_{\pi\in H_n}\;\pi \in \C[S_{2n}].
\]

We have $e^2=e$. The submodule $\C[S_{2n}]e$ of $\C[S_{2n}]$ is isomorphic to
the representation of $S_{2n}$ obtained by inducing from the trivial 
one dimensional representation of $H_n$.

For an arbitrary $v=\sum_{\pi\in S_{2n}} \alpha_\pi \pi \in \C[S_{2n}]$ the
coefficients of $ve$ are constant on the left cosets of $H_n$ (and 
are equal to the average
of the $\alpha$'s on the cosets). Thus $v\in \C[S_{2n}]$ is in 
$\C[S_{2n}]e$ if and only if the coefficients of $v$ are constant on the left
cosets of $H_n$. The number of left cosets of $H_n$ is equal
to $|\cM_{2n}|$ and every left coset of $H_n$ is the set of all 
$\pi\in S_{2n}$ with $\pi\cdot J=A$, for some $A\in \cM_{2n}$.


For $A\in \cM_{2n}$ define $e_A \in \C[S_{2n}]e$ by
\[ 
e_A = \frac{1}{2^n n!}\sum_\pi \pi,
\]
where the sum is over all $\pi\in S_{2n}$ with $\pi\cdot J=A$ (note that
$e_J=e$). It follows that $\{e_A\mid A\in \cM_{2n}\}$ is a basis of 
$\C[S_{2n}]e$ and the mapping
\[
\C[S_{2n}]e \rar \C[\cM_{2n}]
\]
sending $e_A \mapsto A,\;A\in \cM_{2n}$ is a $S_{2n}$-linear isomorphism.

Given $\lambda\in \cY_n$ consider the following central idempotent in
$\C[S_{2n}]$:
\[ 
\psi^{2\lambda}= \frac{\dim(V^{2\lambda})}{(2n)!} 
  \sum_{\pi\in S_{2n}} \chi^{2\lambda}(\pi) \pi.
\]
For any $S_{2n}$-module $W$ action of the element $\psi^{2\lambda}$ 
is projection onto $W^{2\lambda}$. 
We have 
\begin{equation} \label{r5} 
\psi^{2\lambda}\psi^{2\mu} =
\delta_{\lambda\mu}\psi^{2\lambda}.
\end{equation}
For $\lambda\in \cY_n$ set $e^{2\lambda}=\psi^{2\lambda}e$. Note that
$e^{2\lambda}\not =0$ as otherwise $V^{2\lambda}$ will not occur in
$\C[S_{2n}]e$.
We have
\begin{align}  \label{r1} 
e&= \sum_{\lambda\in \cY_n} e^{2\lambda}, \\
\label{r2} e^{2\lambda}e^{2\mu} &= \psi^{2\lambda}e\psi^{2\mu}e = 
\delta_{\lambda\mu}e^{2\lambda}.
\end{align}       

Similarly we can show that, for $\lambda\not=\mu$, we have
\begin{equation} \label{r3} 
e^{2\lambda}\C[S_{2n}]e^{2\mu}=0.
\end{equation}

The algebra $\cB_{2n}$ is isomorphic to the endomorphism
algebra $\End_{\C[S_{2n}]}(\C[S_{2n}]e)$ which, since it is
commutative and since $e$ is idempotent, is isomorphic to
$e\C[S_{2n}]e$, the isomorphism being given by $f\mapsto f(e)$.
We have, from~\eqref{r1}, \eqref{r3},
\begin{equation} \label{r4}
e\C[S_{2n}]e =\left(\sum_{\lambda\in\cY_n}e^{2\lambda}\right)\C[S_{2n}]
                \left(\sum_{\mu\in\cY_n}e^{2\mu}\right) =
\sum_{\lambda\in\cY_n}e^{2\lambda}\C[S_{2n}]e^{2\lambda}.
\end{equation}

It follows from~\eqref{r2} that the sum in~\eqref{r4} is direct. Now,
dimension of $e\C[S_{2n}]e$ is $p(n)$ and each summand on the right hand
side of~\eqref{r4} in nonzero (as it contains $e^{2\lambda}$) so each is
one dimensionsal. It follows that 
\begin{equation}
\label{r6}
e^{2\lambda}\C[S_{2n}]e^{2\lambda} = \C e^{2\lambda}.
\end{equation}

Now consider $\C[S_{2n}]$ with the standard inner product (\ie  the standard
basis $S_{2n}$ is orthonormal) which is $S_{2n}$-invariant. The matrix, in the 
standard basis, for 
the left action of $e$ is real and symmetric. Since $e^2=e$ this matrix is 
idempotent. 
It follows that the action of $e$ on $\C[S_{2n}]e$ is orthogonal
projection onto its image $e\C[S_{2n}]e$. 
It now follows from~\eqref{r1}, \eqref{r2}, \eqref{r3}, \eqref{r6} that the action of 
$e^{2\lambda}$ on $(\C[S_{2n}]e)^{2\lambda}$ is orthogonal
projection onto $\C e^{2\lambda}$ and thus its trace is 1. 

\begin{theo} \label{nonz}
Let $\lambda \in \cY_n$ and let $T\in \tab(2n,2\lambda)$ be good. Then the
coefficient of $J$ in $p_T\cdot J \not= 0$.
\end{theo}
\begin{proof} From Lemma \ref{nonz1} $p_T\cdot J\not=0$. By the 
$S_{2n}$-linear isomorphism between
$\C[S_{2n}]e$ and $\C[\cM_{2n}]$ we see that $p_Te\not=0$. Write
\[
p_Te = \sum_{A\in \cM_{2n}}\;\alpha_A e_A.
\]
%
We need to show that $\alpha_J\not=0$ or, equivalently, $|H_n|\alpha_J\not=0$.
Now, $|H_n|\alpha_J$ is the sum of the coefficients of elements of $H_n$ in
$p_Te$. By the Fourier inversion formula the sum of the coefficients of 
elements of $H_n$ in $p_Te$ is 
\[
\frac{2^n n!}{(2n)!}\left\{ \sum_{\mu\in \cY_{2n}} 
\dim(V^\mu) \Tr_{V^\mu}(ep_Te)\right\}.
\] 
%
By Theorem \ref{md}\ref{theo5.4_i}\ref{theo5.4_i_a} and~\eqref{r1}, \eqref{r3} this sum reduces to
\begin{equation} \label{nonz2}
\frac{2^n n!}{(2n)!}\dim(V^{2\lambda}) \Tr_{V^{2\lambda}}(ep_Te) =
\frac{2^n n!}{(2n)!}\dim(V^{2\lambda}) \Tr_{V^{2\lambda}}
(e^{2\lambda}p_Te^{2\lambda}).
\end{equation}
%
Let $S\in\tab(2n,2\lambda)$ and assume that $S$ is good. By Lemma \ref{nonz1}
and the $S_{2n}$-linear isomorphism between $\C[\cM_{2n}]$ and $\C[S_{2n}]e$
we see that $0\not=p_Se$ is the GZ-vector associated to $S$ in 
$(\C[S_{2n}]e)^{2\lambda}$. From~\eqref{r1} and Theorem \ref{md}\ref{theo5.4_i}\ref{theo5.4_i_a} we 
have $p_Se=p_Se^{2\lambda}$. 

By~\eqref{proj}, Theorem \ref{md}\ref{theo5.4_i}\ref{theo5.4_i_a},
and Lemma \ref{nonz1}\ref{lemma5.6_ii} we have
\begin{equation} 
\label{o} e^{2\lambda} = \sum_S p_S e^{2\lambda},
\end{equation}
where the sum is over all good $S\in \tab(2n,2\lambda)$.

The vectors on the right hand side of~\eqref{o} are nonzero
and orthogonal (being GZ-vectors associated to distinct
tableaux). It follows that the projection of $p_Te^{2\lambda}$
on $e^{2\lambda}$ is nonzero and thus 
$e^{2\lambda}p_Te^{2\lambda}=\beta e^{2\lambda}$, where $\beta$
is the square of the ratio of the lengths of $p_Te^{2\lambda}$ 
and $e^{2\lambda}$. 
Thus the expression in~\eqref{nonz2} is equal to
$\beta\frac{2^n n!}{(2n)!}\dim(V^{2\lambda})$. That completes the proof. \end{proof}


\begin{rema} Let $T\in \tab(2n,2\lambda)$ be not good. Let 
$a_Te^{2\lambda}$, where $a_T\in \C[S_{2n}]$ be the GZ-vector
in $\C[S_{2n}]^{2\lambda}$ associated with $T$. As the GZ-basis is orthogonal 
it follows from 
\eqref{o} that $a_Te^{2\lambda}$ is orthogonal to $e^{2\lambda}$ and thus
$e^{2\lambda}a_Te^{2\lambda}=0$.
\end{rema}

We shall now develop our algorithm for computing the 
eigenvalues of $\cB_{2n}$ by writing down the eigenvectors.
To be efficient
we shall not write down the eigenvectors explicitly 
but only keep track of the values of
these eigenvectors at a (subexponential) number of linear functionals on
$\C[\cM_{2n}]$.


For $\mu\in \cP_n$ define a linear functional
\[
f_{2\mu} : \C[\cM_{2n}] \rar \C
\]
%
as follows: given $v\in \C[\cM_{2n}]$ write
\[
v=\sum_{A\in \cM_{2n}} \alpha_A A,\;\;\alpha_A\in \C.
\]
%
Define $f_{2\mu}(v) = \sum_A \alpha_A,$ where  the sum is over all $A\in
\cM_{2n}$ with $d(J,A)=2\mu$. 
We call $(f_{2\mu}(v))_{\mu\vdash n}$ the {\em
orbital coefficients} of $v\in \C[\cM_{2n}]$. Note that the vector $v$,
living in a vector space of dimension $(2n-1)!!$, has
only $p(n)$ orbital coefficients.

Given $\lambda\in \cY_n$, 
let $v_{2\lambda}$ denote the first GZ-vector of
the submodule $\C[\cM_{2n}]^{2\lambda}$ of $\C[\cM_{2n}]$, normalized so that the
coefficient of $J$ in $v_{2\lambda}$ is $1$. Then it follows that
\[
\hat{\theta}^{2\lambda}_{2\mu} = f_{2\mu}(v_{2\lambda}).
\]

Thus, the eigenvalues can be determined once we know the orbital
coefficients of the first GZ-vectors. The basic idea of the algorithm is
to inductively compute the orbital
coefficients using Lemmas \ref{res} and \ref{ind}. This leads  to the following problem,
called the \emph{update problem}:

Given the orbital coefficients of $v\in \C[\cM_{2n}]$, determine the orbital
coefficients of $X_{2n-1}\cdot v$.

In order to solve the update problem we need to go slightly beyond orbital
coefficients to relative orbital coefficients.  

Let 
\[
\cP_n' = \{(\mu,i)\mid \mu\in \cP_n\mbox{ and $i$ is a part of $\mu$}\}.
\]
%
Elements of $\cP_n'$ are called \emph{pointed partitions} of $n$. 
Let $pp(n)$ denote
the number of pointed partitions of $n$. Clearly, $pp(n) = 1 +p(1)+\cdots
+p(n-1)$ (note that $pp(n)$ is also subexponential). 
Pointed partitions play an important role in Okounkov--Vershik
theory (see~\cite{ov,cst2})  as $pp(n)$ is the dimension of the relative
commutant $\{\pi\in \C[S_n]\mid \pi \C[S_{n-1}] = \C[S_{n-1}] \pi \}$.

For $(\mu,i)\in \cP_n'$ define a linear functional
\[
f_{(2\mu, 2i)} : \C[\cM_{2n}] \rar \C
\]
%
as follows: given $v\in \C[\cM_{2n}]$ write
\[
v=\sum_{A\in \cM_{2n}} \alpha_A A,\;\;\alpha_A\in \C.
\]
%
Define $f_{(2\mu,2i)}(v) = \sum_A \alpha_A,$ where the sum is over all $A\in
\cM_{2n}$ with $d(J,A)=2\mu$ and with the size of the component of $J\cup A$
containing the edge $[2n-1,2n]$ being $2i$. 
We call $(f_{(2\mu, 2i)}(v))_{(\mu,i)\in \cP_n'}$ the {\em
relative orbital coefficients} of $v\in \C[\cM_{2n}]$. 

For $\lambda\in \cY_n, \mu\in \cP_n$ we now have 
\[
\hat{\theta}^{2\lambda}_{2\mu} = \sum_i f_{(2\mu,2i)}(v_{2\lambda}),
\]
%
where the sum is over all parts $i$ of $\mu$.


The update problem for relative orbital coefficients can be easily  solved
using the following lemma.
\begin{lemm} \label{upl} 
Let $A\in\cM_{2n}$. 
Let $C_1,C_2,\ldots ,C_t$ be the components of the spanning
subgraph of $K_{2n}$ with edge set $J\cup A$, with $C_t$ containing the edge
$[2n-1,2n]$. Let $2\mu_i$ be the number of vertices of $C_i$, $i=1,\ldots
,t$. Thus $\{2\mu_1,\ldots ,2\mu_t\}$ is the multiset of parts of $d(J,A)$.

\begin{enumerate}[(\roman*)]
\item\label{lemma5.9_i} %(i) 
Let $s$ be a vertex of $C_j$, $j=1,\ldots , t-1$ and put $A'=
(s \; 2n-1)\cdot A$. Then the multiset of
parts of $d(A', J)$ is 
\[
(\{2\mu_1,\ldots ,2\mu_t\} - \{2\mu_j , 2\mu_t\}) \cup \{2(\mu_j + \mu_t)\},
\] 
with $2(\mu_j+\mu_t)$ as
the size of the component of $A' \cup J$ containing the edge
$[2n-1,2n]$.

\item\label{lemma5.9_ii} %(ii) 
Traverse the vertices of the alternating cycle $C_t$ in cyclic order,
beginning at the vertex $2n$ and going towards $2n-1$. List the
vertices encountered as $\{2n, 2n-1, i_1, i_2, \ldots ,i_{2k-1}, i_{2k}\}$,
where $k\geq 0$ and $2\mu_t = 2k+2$. Then

\begin{enumerate}[(\alph*)]
\item\label{lemma5.9_ii_a} %(a) 
Let $j\in \{1,2,\ldots ,k\}$ and put $A' = (i_{2j} \; 2n-1)\cdot A$.
The multiset of parts of $d(A', J)$ is 
$\{2\mu_1,\ldots ,2\mu_{t-1},2\mu_t -2j, 2j\}$, with
$2\mu_t - 2j$ as the size of the component of $A'\cup J$ containing the edge
$[2n-1, 2n]$.



\item\label{lemma5.9_ii_b} %(b) 
Let $j\in \{1,2,\ldots ,k\}$ and put $A' = (i_{2j-1} \; 2n-1)\cdot A$.
The multiset of parts of $d(A', J)$ is $\{2\mu_1,\ldots ,2\mu_t\}$, with
$2\mu_t$ as the size of the component of $A'\cup J$ containing the edge
$[2n-1, 2n]$.
\end{enumerate}
\end{enumerate}
\end{lemm}

\begin{proof} 
\ref{lemma5.9_i}~Let $[s,x], [2n-1,y]\in A$. Then $A' = (A\setminus \{[s,x],
[2n-1,y]\}) \cup \{[2n-1,x], [y,s]\}$. It follows that 
$C_k$, $k\in \{1,\ldots ,t-1\}\setminus \{j\}$, continue to remain
components of $J\cup A'$ and that $C_j$ and $C_t$ merge into a single
alternating cycle in $J\cup A'$.


\ref{lemma5.9_ii}\ref{lemma5.9_ii_a}~It is clear that $C_1,\ldots ,C_{t-1}$ continue to be components of
$J\cup A'$ and that $C_t$ splits into two alternating cycles with vertex
sets 
\[
\{i_{2j+1}, i_{2j+2}, \ldots ,i_{2k-1}, i_{2k}, 2n, 2n - 1\} \mbox{ and } 
\{i_1, i_2, \ldots ,i_{2j-1}, i_{2j}\}.
\]

\ref{lemma5.9_ii}\ref{lemma5.9_ii_b}~Similar to case~\ref{lemma5.9_ii}\ref{lemma5.9_ii_a} except that $C_t$ does not split. %$\Box$
\end{proof}

For $v\in \C[\cM_{2n}]$, define 
\[
 [v] = (f_{(2\mu,2i)}(v))_{(\mu,i)\in\cP_n'}
\]
to be the vector of the relative orbital coefficients of $v$. We denote
$f_{(2\mu,2i)}(v)$ by $v(2\mu,2i)$.

The following is the algorithm for updating the vector
of relative orbital coefficients. Its correctness directly follows from
Lemma \ref{upl}. 
%

\goodbreak
\bgroup
\setcounter{cdrthm}{0}
\def\thecdrthm{\arabic{cdrthm}}
\begin{enonce}[remark]{Algorithm}[\emph{Update for relative orbital coefficients}]\label{algo1}\ \\*[-1em]
%\begin{algo}%[\emph{Update for relative orbital coefficients}]
%\vskip 1ex
\begin{tabbing}
%{{ALGORITHM 1}} \emph{(Update for relative orbital coefficients)}\\
{{INPUT}} $[v]$, for some $v\in \C[\cM_{2n}]$, and an integer $a$.\\
{{OUTPUT}} $[u]$, where $u = (X_{2n-1} - a\epsilon )\cdot(v) 
\in \C[\cM_{2n}]$. \\
{{METHOD}} \\
1. For all $(\mu,i)\in \cP_n'$ do $\gamma(2\mu,2i) = 0$.\\
2. For \= all $(\mu,i)\in \cP_n'$ do\\
  \> 2a. Write the multiset of parts of $\mu$ as
$\{\mu_1,\mu_2,\ldots ,\mu_t\}$, where $\mu_t = i$. \\
   \> 2b. \= For $j = 1 \mbox{ to } t-1$ do \\
   \> \>  2b.1. $\mu' = (\{\mu_1, \mu_2,\ldots ,\mu_t\} \setminus \{\mu_j ,\mu_t\})
\cup \{\mu_j + \mu_t\},\;\;i'=\mu_j + \mu_t$. \\
 \> \> 2b.2. 
$\gamma(2\mu',2i') = 2\mu_j v(2\mu,2i) + \gamma(2\mu', 2i').$\\
    \> 2c. $k = \mu_t - 1$. \\
    \> 2d. For $j = 1 \mbox{ to } k$ do\\
   \> \> 2d.1. $\mu' = (\{\mu_1, \mu_2,\ldots ,\mu_{t-1},\mu_t -j, j\},
                  \;\;i'=\mu_t - j$.\\
\>\> 2d.2. $\gamma(2\mu',2i') = v(2\mu,2i) + \gamma(2\mu', 2i').$\\
\>\> 2d.3. $\gamma(2\mu,2i) = v(2\mu,2i) + \gamma(2\mu, 2i).$\\
3. For all $(\mu,i)\in \cP_n'$ do $u(2\mu,2i) = \gamma(2\mu,2i) - a v(2\mu,2i)$.\\
4. RETURN $(u(2\mu,2i))_{(\mu,i)\in \cP_n'}$.
\end{tabbing}
\end{enonce}

%\vskip 1ex   
We denote the output of Algorithm 1, on input $[v]$, by $F_{a}([v])$.

We now give the inductive algorithm for computing the rows of the eigenvalue
tables $\hat{\Theta}(2n)$. In Step 5 below we use the convention that,
for a proposition $P$, $[P]$ equals 1 if $P$ is true and
is equal to 0 if $P$ is false. 
%

%\vskip 1ex
\begin{enonce}[remark]{Algorithm}[\emph{Computing rows of the eigenvalue table inductively}]\label{algo2}\ \\*[-1em]
\begin{tabbing}
%{ALGORITHM 2} \emph{(Computing rows of the eigenvalue table inductively)}\\
{INPUT} (i) $\lambda'\in \cY_{n+1}$, 
with $\lambda = \lambda' -\mbox{\{last box in
last row of $\lambda$\}}\in \cY_n$.\\ 
(ii) The row of $\hat{\Theta}(2n)$ indexed by $\lambda$, \ie  
$(\hat{\theta}^{2\lambda}_{2\mu})_{\mu\in \cP_n}$.\\ 
{OUTPUT} The row of $\hat{\Theta}(2n+2)$ indexed by $\lambda'$, \ie 
$(\hat{\theta}^{2\lambda'}_{2\mu'})_{\mu'\in \cP_{n+1}}$.\\ 
{METHOD}\\ 
1. For all $(\mu',i)\in \cP_{n+1}'$ do $v(2\mu',2i) = 0$.\\ 
2. For all $\mu\in \cP_n$ do $v(2\mu\cup \{2\},2) = \hat{\theta}^{2\lambda}_{2\mu}$.\\ 
3. \= Let the Young diagram $2\lambda$ have $k+1$ outer corners. 
   Adding two boxes (in a row) \\
   \> in the place of one of these outer corners 
   yields $2\lambda'$. Denote the $k$ other outer \\
   \> boxes by $b_1,\ldots ,b_k$.\\ 
4. For $j = 1 \mbox{ to } k$ do $[v] = F_{c(b_j)}([v])$.\\  
5. For all $\mu'\in \cP_{n+1}$ do $\hat{\theta}^{2\lambda'}_{2\mu'} =
\frac{\ds{\sum_{i=1}^{n+1}}\;[i\mbox{ is a part of $\mu'$} ]
\;v(2\mu',2i)}{v(2(1^{n+1}),2)}$.\\  
6. RETURN $(\hat{\theta}^{2\lambda'}_{2\mu'})_{\mu'\in\cP_{n+1}}$.
\end{tabbing}
\end{enonce}
\setcounter{cdrthm}{9}
\egroup

%
\begin{theo} 
Algorithm~\ref{algo2} is correct.
\end{theo}

\begin{proof} Let $u\in \C[\cM_{2n}]$ be the first GZ-vector in $V^{2\lambda}$.
Normalize $u$ so that the coefficient of $J$ is 1. Let $v\in \C[\cM_{2n+2}]$ be
the vector corresponding to $1\otimes u \in
\ind^{S_{2n+1}}_{S_{2n}}(\C[\cM_{2n}])$, under the isomorphism between
$\ind^{S_{2n+1}}_{S_{2n}}(\C[\cM_{2n}])$ and
$\res^{S_{2n+2}}_{S_{2n+1}}(\C[\cM_{2n+2}])$ (Lemma \ref{mfree}(v,vi)).
Then it follows that steps 1 and 2 of Algorithm~\ref{algo2} correctly calculate $[v]$.


It now follows from Lemma \ref{ind} that steps 3, 4, 5, and 6 of Algorithm~\ref{algo2}
correctly compute the (normalized) 
orbital coefficients of the first GZ-vector of
$V^{2\lambda'}$. \end{proof}

It is clear that a similar algorithm exists for any good tableau and 
the use of the first tableau is only for convenience.
We have implemented Algorithms~\ref{algo1} and~\ref{algo2} in Maple. Both the program and its
binary file are available at~\cite{sr}. 
The program is able to compute
$\hat{\theta}^{2\lambda}_{2\mu}$ reasonably quickly for $|\lambda|=|\mu|\leq
20$. We were able to determine the entire spectrum of $D_{40}$.

\begin{exam} 
We give below the eigenvalue table $\hat{\Theta}(10)$ computed using this
program.
List the elements of $\cP_5$ in the order $\{(1^5), (2,1^3),
(2^2,1), (3,1^2), (3,2), (4,1), (5)\}$ and the elements of $\cY_5$ 
in the order $\{(5), (4,1), (3,2), (3,1^2),
(2^2,1), (2,1^3), (1^5)\}$. We have
\[
\hat{\Theta}(10) = %\left[ \ba{rrrrrrr} 
\begin{bmatrix}
1&20&60&80&160&240&384\\
1&11&6&26&-20&24&-48\\
1&6&11&-4&20&-26&-8\\
1&3&-10&2&-4&-8&16\\
1&0&5&-10&-10&10&4\\
1&-4&-3&2&10&6&-12\\
1&-10&15&20&-20&-30&24
%\ea\right]
\end{bmatrix}
.
\]
%
Summing the fifth and seventh columns of $\hat{\Theta}(10)$ we get the
spectrum  of $D_{10}$:
\begin{gather*}
m^{(10)}_{10} = 544, \ \ 
m^{(8,2)}_{10} = -68,\ \  
m^{(6,4)}_{10} = 12,\ \ 
m^{(6,2,2)}_{10} = 12,\\
m^{(4,4,2)}_{10} = -6,\ \ 
m^{(4,2,2,2)}_{10} = -2,\ \ 
m^{(2,2,2,2,2)}_{10} = 4.
\end{gather*}
%
Note the sole zero value in row 5, column 2. The eigenvalue table
$\hat{\Theta}(2n)$ tends to have far fewer zero values than the character
(or central character) table of $S_n$. For instance, $p(15)=176$ and of the
$176^2=30976$ entries in the character table of $S_{15}$ as many as $11216$
are zero while only $878$ of the entries in $\hat{\Theta}(30)$ are zero.
\end{exam}



Recently, Ku and Wong~\cite{kw} gave elegant explicit formulas for
$m^{2(1^n)}_{2n}$ and $m^{2(2^m,1^{n-2m})}_{2n}$. Namely, they showed that
\[
m^{2(1^n)}_{2n}=(-1)^{n-1}(n-1),\;\;m^{2(2^m,
1^{n-2m})}_{2n}=(-1)^{n-2}((m-1)n - m^2 + 2m +1).
\]
It would be interesting to see whether these formulas can be derived from the
algorithm presented here. This possibility arises as follows. The number $k$ 
of
times the for loop in Step 4 of Algorithm 2 is executed depends on the
number of outer boxes of the input Young diagram. In the case of the Young
diagrams $2(1^n)$ and $2(2^m,1^{n-2m})$ this number is 1 or 2 throughout
(\ie  at every level of recursion). This considerably simplifies the
recursion and it may be possible to use generating function techniques to
derive the formulas above. We hope to return to this later.   


We shall now give an almost identical algorithm for computing the central
characters of $S_n$, based on the inductive structure
\eqref{rrs} of the regular modules $\C[S_n]$.

For $\mu\in \cP_n$ define a linear functional
\[
g_{\mu} : \C[S_n] \rar \C
\]
%
as follows: given $v\in \C[S_n]$ write
\[
v=\sum_{\pi\in S_n} \alpha_\pi \pi,\;\;\alpha_\pi\in \C.
\]
%
Define $g_{\mu}(v) = \sum_\pi \alpha_\pi,$ where  the sum is over 
$\pi\in C_\mu$. 
We call $(g_{\mu}(v))_{\mu\vdash n}$ the {\em
class coefficients} of $v\in \C[S_n]$. Note that the vector $v$,
living in a vector space of dimension $n!$, has
only $p(n)$ class coefficients.

Given $\lambda\in \cY_n$, let $R\in \tab(n,\lambda)$ be the first tableau
and consider $p_R\in \C[S_n]^\lambda$, a GZ-vector associated to $R$.
Let $v_{\lambda}$ denote the vector obtained by normalizing $p_R$
so that the
coefficient of $\epsilon$ is $1$. 
Then it follows that
\[
\hat{\phi}^{\lambda}_{\mu} = g_{\mu}(v_{\lambda}).
\]

Thus, the eigenvalues can be determined once we know the class
coefficients of $v_{\lambda}$. The basic idea of the algorithm is
to inductively compute the class
coefficients using Lemma \ref{ind}. Like before, this leads  
to the \emph{update problem}:

Given the class coefficients of $v\in \C[S_n]$, determine the class
coefficients of $X_n\cdot v$.

To solve the update problem we define relative class coefficients.  
For $(\mu,i)\in \cP_n'$ define a linear functional
\[
g_{(\mu, i)} : \C[S_n] \rar \C
\]
%
as follows: given $v\in \C[S_n]$ write
\[
v=\sum_{\pi\in S_n} \alpha_\pi \pi,\;\;\alpha_\pi\in \C.
\]
%
Define $g_{(\mu,i)}(v) = \sum_\pi \alpha_\pi$, where
the sum is over all $\pi\in S_n$ 
with $\pi\in C_\mu$ and with the size of the cycle of $\pi$
containing $n$ being $i$. 
We call $(g_{(\mu, i)}(v))_{(\mu,i)\in \cP_n'}$ the {\em
relative class coefficients} of $v\in \C[S_n]$. 

For $\lambda\in \cY_n, \mu \in \cP_n$ we now have 
\[
\hat{\phi}^{\lambda}_{\mu} = \sum_i g_{(\mu,i)}(v_{\lambda}),
\]
%
where the sum is over all parts $i$ of $\mu$.


The update problem for relative class coefficients can be easily solved
using the following lemma.
%
\begin{lemm} \label{uplc} 
Let $\pi\in S_n$ with 
$C_1,C_2,\ldots ,C_t$ as its disjoint cycles and with
$C_t$ containing $n$. Let $\mu_i = |C_i|,\;i=1,\ldots ,t$, so that
$\{\mu_1,\ldots ,\mu_t\}$ is the multiset of cycle lengths of $\pi$.
\begin{enumerate}
\item\label{lemma5.12_i} %(i) 
Let $s$ be an element of $C_j$, $j=1,\ldots , t-1$ and put $\pi'=
(s \; n) \pi$. Then the multiset of cycle lengths of $\pi'$ is
%
\[
(\{\mu_1,\ldots ,\mu_t\} - \{\mu_j , \mu_t\}) \cup \{\mu_j + \mu_t\},
\] 
with $\mu_j+\mu_t$ as the length of the cycle containing $n$.

\item\label{lemma5.12_ii} %(ii) 
Write $C_t = (n\;i_k\;i_{k-1} \cdots i_1)$, where $k\geq 0$ and $\mu_t=k+1$. 
Let $j\in \{1,2,\ldots ,k\}$ and put $\pi' = (i_j \;  n) \pi$.
Then the  multiset of parts of $\pi'$ is 
$\{\mu_1,\ldots ,\mu_{t-1},\mu_t -j, j\}$, with
$\mu_t - j$ as the length of the cycle containing $n$.
\end{enumerate}
\end{lemm}

\begin{proof} 
This is similar to the proof of Lemma \ref{upl}. 
\end{proof}

For $v\in \C[S_n]$, define 
\[
[v] = (g_{(\mu,i)}(v))_{(\mu,i)\in\cP_n'}
\]
to be the vector of the relative class coefficients of $v$. We denote
$g_{(\mu,i)}(v)$ by $v(\mu,i)$.

The following is the algorithm for updating the vector
of relative class coefficients. Its correctness directly follows from
Lemma \ref{uplc}. 
%
%\vskip 1ex


\bgroup
\setcounter{cdrthm}{2}
\def\thecdrthm{\arabic{cdrthm}}
\begin{enonce}[remark]{Algorithm}[\emph{Update for relative class coefficients}]\label{algo3}\ \\*[-1em]
\begin{tabbing}
%{ALGORITHM 3} \emph{(Update for relative class coefficients)}\\
{INPUT} $[v]$, for some $v\in \C[S_n]$, and an integer $a$.\\
{OUTPUT}: $[u]$, where $u = (X_{n} - a\epsilon)\cdot(v) \in \C[S_n]$.\\
{METHOD}\\
1. For all $(\mu,i)\in \cP_n'$ do $\gamma(\mu,i) = 0$.\\
2. For \= all $(\mu,i)\in \cP_n'$ do\\
   \> 2a. Write the multiset of parts of $\mu$ as
$\{\mu_1,\mu_2,\ldots ,\mu_t\}$, where $\mu_t = i$.\\  
  \> 2b. \= For $j = 1 \mbox{ to } t-1$ do\\
   \> \> 2b.1. $\mu' = (\{\mu_1, \mu_2,\ldots ,\mu_t\} \setminus \{\mu_j ,\mu_t\})
\cup \{\mu_j + \mu_t\},\;\;i'=\mu_j + \mu_t$.\\
   \> \> 2b.2. $\gamma(\mu',i') = \mu_j v(\mu,i) + \gamma(\mu', i').$\\
   \> 2c. $k = \mu_t - 1$.\\
   \> 2d. \= For $j = 1 \mbox{ to } k$ do\\
   \> \> 2d.1. $\mu' = (\{\mu_1, \mu_2,\ldots ,\mu_{t-1},\mu_t -j, j\}, 
               \;\;i'=\mu_t - j$.\\
    \> \> 2d.2. $\gamma(\mu',i') = v(\mu,i) + \gamma(\mu', i').$\\
3. For all $(\mu,i)\in \cP_n'$ do $u(\mu,i) = \gamma(\mu,i) - a v(\mu,i)$.\\
4. RETURN $(u(\mu,i))_{(\mu,i)\in \cP_n'}$.
\end{tabbing}
\end{enonce}
%\vskip 1ex

We denote the output of Algorithm~\ref{algo3}, on input $[v]$, by $G_{a}([v])$.

We now give the inductive algorithm for computing the rows of the central
character tables of $S_n$. 
%
\begin{enonce}[remark]{Algorithm}[\emph{Computing rows of the central character table inductively}]\label{algo4}\ \\*[-1em]
%\vskip 1ex
\begin{tabbing}
%{ALGORITHM 4} \emph{(Computing rows of the central character table inductively)}\\
{INPUT} (i) $\lambda'\in \cY_{n+1}$, 
with $\lambda = \lambda' -\mbox{\{last box in
last row of $\lambda$\}}\in \cY_n$.\\ 
(ii) The row of the central character table of $S_n$ indexed by $\lambda$, \ie 
$(\hat{\phi}^{\lambda}_{\mu})_{\mu\in \cP_n}$.\\ 
{OUTPUT} Row of the central character table of $S_n$ 
indexed by $\lambda'$, \ie 
$(\hat{\phi}^{\lambda'}_{\mu'})_{\mu'\in \cP_{n+1}}$.\\ 
{METHOD}\\
1. For all $(\mu',i)\in \cP_{n+1}'$ do $v(\mu',i) = 0$.\\ 
2. For all $\mu\in \cP_n$ do $v(\mu\cup \{1\},1) = 
\hat{\phi}^{\lambda}_{\mu}$.\\ 
3. \= Let $\lambda$ have $k+1$ outer corners.
   One of these outer corners, when
   added to $\lambda$, \\
   \> yields $\lambda'$. Denote the $k$ other outer boxes by
   $b_1,\ldots ,b_k$. \\
4. For $j = 1 \mbox{ to } k$ do $[v] = G_{c(b_j)}([v])$.\\  
5. For all $\mu'\in \cP_{n+1}$ do
$\hat{\phi}^{\lambda'}_{\mu'} =
\frac{\ds{\sum_{i=1}^{n+1}}\;[i\mbox{ is a part of $\mu'$} ]\;v(\mu',i)}
{v(1^{n+1},1)}$.\\  
6. RETURN $(\hat{\phi}^{\lambda'}_{\mu'})_{\mu'\in\cP_{n+1}}$.
\end{tabbing}
\end{enonce}
\setcounter{cdrthm}{12}
\egroup
%
\begin{theo} 
Algorithm~\ref{algo4} is correct.
\end{theo} 
\begin{proof} Let $R\in\tab(n,\lambda)$ be the first tableau. Normalize 
$p_R\in\C[S_n]^\lambda$ to get a GZ-vector $u$ associated to $R$
so that the coefficient of $\epsilon$ is 1. 

Let $v$ correspond to $u$ under the embedding of $\C[S_n]$ into 
$\C[S_{n+1}]$ (adding $(n+1)$ 
as a singleton cycle to each permutation in $S_n$).
Then it follows that steps 1 and 2 of Algorithm 4 correctly calculate $[v]$.
It now follows from Lemma \ref{ind} that steps 3, 4, 5, and 6 of Algorithm 4
correctly compute the (normalized) class coefficients of $p_{R'}$ (where 
$R'\in\tab(n+1,\lambda')$ is the first tableau).
\end{proof}

It is clear that a similar algorithm exists for any tableau and 
the use of the first tableau is only for convenience.
This algorithm has also been implemented in~\cite{sr}. 


\longthanks{I thank the referees for their remarks. I am especially grateful to Reviewer C
for detailed suggestions that have considerably improved the exposition 
and, most importantly, for pointing out that the proof of validity 
of the algorithms in Section~\ref{Sect5} had a gap.}






%\nocite{*}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Srinivasan_218}
\end{document}
