\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|=jk$ 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|=j0$. 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 $jn$, 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}