%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

%\usepackage{lipsum}
\usepackage{ytableau}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\DeclareMathOperator{\fp}{fp}

%% define your title in the usual way
\title{Harmonic Polynomials on Perfect Matchings}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Y.~Filmus and N.~Lindzey]{Yuval Filmus\thanks{\href{mailto:yuvalfi@cs.technion.ac.il}{yuvalfi@cs.technion.ac.il}. Partially supported by the European Union's Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC.}\addressmark{1} \and Nathan Lindzey\thanks{\href{mailto:Nathan.Lindzey@colorado.edu}{Nathan.Lindzey@colorado.edu}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Computer Science, Technion, Israel\\ \addressmark{2}Department of Computer Science, University of Colorado, U.S.A.}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
We show that functions over perfect matchings of complete graphs admit unique presentations as harmonic polynomials annihilated by certain differential operators. Moreover, we give a concrete description of these harmonic polynomials by computing the unique harmonic presentation of the standard basis of \emph{Specht polynomials}. At the core of these results is a class of incidence matrices that we call the \emph{matching inclusion matrices}. The algebraic combinatorics of these matrices are related to \emph{Jack polynomials}, which leads us to some elegant formulas for particular weighted sums of Jack characters for arbitrary $\alpha$. Along the way, we prove a perhaps new combinatorial identity related to Jack characters that equates the product of the top row of $\alpha$-upper hook lengths of a shape $\lambda$ to a weighted sum of so-called \emph{tableau transversals} of $\lambda$.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{harmonic analysis, perfect matchings, Jack polynomials}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above



\section{Introduction}
The Boolean hypercube $\{0,1\}^n$ is the archetypal setting for discrete analysis. It has many desirable properties, such as the fact that every function on the hypercube admits a unique presentation as a multilinear polynomial of $\mathbb{R}[x_1,\ldots,x_n]$ with nice spectral properties, \textit{e.g.}, it adheres to the representation theory of the binary Hamming scheme (see~\cite{GodsilMeagher}, for example). According to the latter, the space $\mathbb{R}\{0,1\}^n$ decomposes into $n+1$ irreducible subspaces $V^0 \oplus V^1 \oplus \cdots \oplus V^n$. We can decompose each function $f \in \mathbb{R}\{0,1\}^n$ according to this decomposition as $f = f^{=0} + f^{=1} + \cdots + f^{=n}$, where $f^{=d}$ is the part belonging to $V^d$. It turns out that $f^{=d}$ is just the $d$th homogeneous part of the unique multilinear presentation of $f$. Furthermore, we know a simple basis for $V^d$, namely the degree-$d$ monomials. Fundamental duality principles such as these between the polynomial presentation and spectral representation (\textit{i.e.}, Fourier basis) have been invaluable in the analysis of Boolean functions and theoretical computer science~(see~\cite{O}). 

For other combinatorial domains it is not so clear that such duality principles hold, and a natural question is to what extent these principles extend to other domains. In this work we address these questions for \emph{perfect matchings} of graphs (pairwise-disjoint sets of edges that cover all of the vertices), in particular, those of the complete bipartite graph $K_{n,n} = ([n],[n],E)$ and the complete graph $K_{2n} = ([2n],E)$, which we denote as $\mathcal{M}_{n,n}$ and $\mathcal{M}_{2n}$. Let us single out the former, which can be identified with the symmetric group $S_n$. Let $\overline{x} := \{x_{i,j}\}_{i,j=1}^n$ be the set of indeterminants indicating whether the input permutation sends $i$ to $j$ or not, so that any function on $S_n$ can be presented as a polynomial of $\mathbb{R}[\overline{x}]$.

Does every function $f \in \mathbb{R}S_n$ admit a unique presentation as a multilinear polynomial of $\mathbb{R}[\overline{x}]$? Equivalently, does $0 \in \mathbb{R}S_n$ admit only $0 \in \mathbb{R}[\overline{x}]$ as its multilinear polynomial presentation? While this is true for the hypercube, it is easily seen to be false for $S_n$, and indeed many other combinatorial domains. For example, any monomial that is a multiple of $x_{i,j}x_{i,k}$ or $x_{i,k}x_{j,k}$ for any $i,j,k \in [n]$ must vanish on $S_n$. To avoid degeneracies such as this, we consider polynomial presentations modulo the ideal $\mathcal{I} = \{x_{i,j}^2 = x_{i,j},~x_{i,j}x_{i,k},~x_{i,k}x_{j,k} \text{ for all } i,j,k \in [n]\}$ to ensure multilinearity and that no monomial vanishes over all permutations. We call polynomials of $\mathbb{R}[\overline{x}]/(\mathcal{I})$ \emph{succinct}. It is clear that the degree-$d$ monomials of a succinct polynomial can be identified with $d$-matchings of $K_{n,n}$, and moreover, that any $f \in \mathbb{R}S_n$ admits a succinct presentation of degree at most $(n-1)$. Indeed, for any $\sigma \in S_n$, the degree-$n$ monomial corresponding to the $n$-matching $\sigma$ has a degree-$(n-1)$ presentation, as each $(n-1)$-matching extends to a unique perfect matching. However, we can still present the zero function $0 \in \mathbb{R}S_n$ as a succinct linear polynomial $z(\overline{x})$ of the following form: $
	z(\overline{x}) = \sum_{i=1}^n\sum_{j=1}^n c_{i,j}x_{i,j}$ where $c_{i,j} = l_i + r_j$ such that $\sum_{i=1}^n l_i + \sum_{j=1}^n r_j = 0$.
Indeed, we have $z(\sigma) = 0$ for all $\sigma \in S_n$ since $\sigma$ is a bijection, \textit{i.e.}, $\sum_j x_{i,j} = 1$ for all $i \in [n]$, and $\sum_i x_{i,j} = 1$ for all $j \in [n]$.
%Moreover, any linear polynomial of $\mathbb{R}[\overline{x}]$ that is identically zero on permutations is of the aforementioned form~\cite{Lovasz87}. We give a generalization of this result that provides a polynomial and spectral characterization of the degree-$d$ polynomials that are identically zero on perfect matchings (see Section~\ref{sec:orthogonal}).
This shows there is not a unique succinct presentation of any $f \in \mathbb{R}S_n$; therefore, we must further constrain the presentation if we are to obtain a uniqueness result. We show that if we also require the presentation to be \emph{harmonic} (see Section~\ref{sec:unique}), then this presentation is in fact unique, and moreover, that it adheres to the natural ``degree decomposition'' of $\mathbb{R}S_n$ and $\mathbb{R}\mathcal{M}_{2n}$:
\[
	\mathbb{R}S_n \cong \bigoplus_{d=0}^{n-1} V^d, \quad V^d := \!\!\!\! \!\!\!\! \bigoplus_{\substack{\lambda \vdash n : \lambda_1 = n-d}} \!\!\!\! \!\!\!\! V^\lambda 
\]
and
\[
	\quad \mathbb{R}\mathcal{M}_{2n} \cong \bigoplus_{d=0}^{n-1} V^d, \quad V^d :=\!\!\!\! \!\!\!\! \bigoplus_{\substack{\lambda \vdash n : \lambda_1 = n-d}} \!\!\!\! \!\!\!\! V^{2\lambda},
\]
where $2\lambda \vdash 2n$ is the shape obtained by doubling each part of $\lambda$ (see~\cite{Dafni} for more details).
\begin{theorem}\label{thm:unique}
Any real-valued function $f$ on perfect matchings of $\{K_{n,n},K_{2n}\}$ can be presented uniquely as a succinct harmonic polynomial $p$. Moreover, the unique succinct harmonic presentation of the $\perp$-projection $f^{=d}$ of $f$ onto $V^d$ equals the $d$th homogeneous part $p^{=d}$ of $p$. 
\end{theorem}
%\begin{theorem}\label{thm:unique2}
%	Any function on perfect matchings of $K_{2n}$ can be presented uniquely as a harmonic multilinear polynomial of $\mathbb{C}[\overline{x}]$.
%\end{theorem}
%\noindent But is this unique succinct harmonic presentation natural? That is, does it respect an underlying decomposition of $\mathbb{C}S_n$ into $n$ subspaces similar to the hypercube? This might seem nonsensical at first since the irreducibles of $S_n$ are indexed by integer partitions $\lambda = (\lambda_1,\lambda_2,\ldots,\lambda_\ell) \vdash n$ rather than non-negative integers, \textit{i.e.}, $\mathbb{C}S_n \cong \bigoplus_{\lambda \vdash n} V^\lambda$ where $V^\lambda$ is the $\lambda$-isotypic component; however, another natural decomposition is 
%$$\mathbb{C}S_n \cong V^0 \oplus V^1 \oplus \cdots \oplus V^{n-1} \quad \text{ where } \quad V^d := \bigoplus_{\substack{\lambda \vdash n ~:~ \lambda_1 = n-d}} V^\lambda,$$ 
%%where $V^0$ consists of all constant functions, and $V^{d+1}$ is the orthogonal complement of $U^d$ inside $U^{d+1}$, where $U^d$ is the span of all degree~$d$ monomials. The former decomposition refines the latter: $V^d = \bigoplus_{\substack{\lambda \vdash n \\ \lambda_1 = n-d}} V^\lambda$. 
%\textit{i.e.}, $f = f^{=0} + f^{=1} + \cdots + f^{=n-1}$ for any $f \in \mathbb{C}S_n$. We show the unique succinct harmonic presentation of $f \in \mathbb{C}S_n$ indeed respects the latter decomposition, that is, the function $f^{=d} \in \mathbb{C}S_n$ is the $d$th homogeneous part of the unique succinct harmonic presentation of $f$.  
%\begin{theorem}\label{thm:decomp}
%	Any complex-valued function on perfect matchings of $\{K_{n,n},K_{2n}\}$ can be presented uniquely as a succinct harmonic polynomial of $\mathbb{C}[\overline{x}]$.
%\end{theorem}
%\begin{theorem}\label{thm:decomp}
%	\[
%		\mathbb{C}S_n = V_0 \oplus V_1 \oplus \cdots \oplus V_n
%	\]
%\end{theorem}
%\begin{theorem}\label{thm:decomp2}
%	\[
%		\mathbb{C}\mathcal{M}_{2n} = V_0 \oplus V_1 \oplus \cdots \oplus V_n
%	\]
%\end{theorem}
We call $p$ the \emph{canonical presentation} of $f$. The \emph{Specht polynomials} $\{f_{s,t}\}_{s,t}$, where $s,t$ range over all standard $\lambda$-tableaux, form a well-known basis of degree-$n$ polynomials for the $\lambda$-isotypic component $V^\lambda$. We show the canonical presentation of this basis can be obtained by applying an appropriately defined differential operator $D_{\lambda_1}$ defined in Section~\ref{sec:jack}.

\begin{theorem}\label{thm:specht} For all standard $\lambda$-tableaux $s,t$, and standard $2\lambda$-tableaux $u$, the canonical presentations of $f_{s,t}$ and $f_u$ are $p_{s,t}(\overline{x}) = d_\lambda(1)^{-1} D_{\lambda_1} f_{s,t}$ and $p_{u}(\check{x}) = d_\lambda(2)^{-1} D_{\lambda_1} f_{u}$ respectively, where $d_\lambda(\alpha)$ is the product of the $\alpha$-upper hook lengths that compose the top row of $\lambda$.
\end{theorem}
%\noindent The proofs of these theorems use the representation theory of $S_n$ and the algebraic combinatorics of Jack polynomials. Central to these results is a class of incidence matrices, interesting in their own right, that we call \emph{the matching inclusion matrices} (see Section~\ref{sec:unique}), which are analogues of the well-studied and remarkable \emph{set incidence matrices} (see~\cite{Gottlieb}). 
%Along the way, we prove a perhaps new combinatorial identity related to Jack characters that equates the product of the top row of upper hook lengths to a weighted sum of so-called \emph{tableau transversals} defined in Section~\ref{sec:jack}. Finally, in places where the proofs for the domains $\mathcal{M}_{n,n}$ and $\mathcal{M}_{2n}$ are identical \emph{mutatis mutandis}, we prove only the $\mathcal{M}_{n,n}$ case.
%

%The paper is organized as follows. In Section~\ref{sec:unique} we give a unified proof of Theorem~\ref{thm:unique} and Theorem~\ref{thm:unique2} using \emph{Jack polynomials}, which we outline in Section~\ref{sec:jack}. In Section~\ref{sec:zero} we introduce some representation-theoretical results on partial matchings of $K_{n,n}$ and $K_{2n}$ to then deduce Theorem~\ref{thm:zero} and Theorem~\ref{thm:zero2} as corollaries of Theorem~\ref{thm:unique} and Theorem~\ref{thm:unique2} respectively. Finally, we prove Theorem~\ref{thm:decomp} using some combinatorial identities involving so-called \emph{tableau transversals} that we derive in Section~\ref{sec:transversals}. Central to these results is a class of incidence matrices, interesting in their own right, that we call \emph{the matching inclusion matrices} (see Section~\ref{sec:unique}), which are analogues of the well-studied and remarkable \emph{set incidence matrices} (see~\cite{Gottlieb}).
 
The paper is organized as follows. We first show in Section~\ref{sec:existence} that succinct harmonic presentations of functions exist. Next, we prove in Section~\ref{sec:unique} that such presentations are unique, proving Theorem~\ref{thm:unique}. Central to this result is a class of incidence matrices, interesting in their own right, that we call \emph{the matching inclusion matrices}, which are analogues of the well-studied and remarkable \emph{set incidence matrices} (see~\cite{Gottlieb}). In Section~\ref{sec:jack} we prove Theorem~\ref{thm:specht} using the representation theory of $S_n$ and the algebraic combinatorics of Jack polynomials. Along the way, we prove a perhaps new combinatorial identity related to Jack characters that equates the product of the top row of upper hook lengths to a weighted sum of so-called \emph{tableau transversals} defined in Section~\ref{sec:jack}. 

Finally, in places where the proofs for the domains $\mathcal{M}_{n,n}$ and $\mathcal{M}_{2n}$ are identical \emph{mutatis mutandis}, we prove only the $\mathcal{M}_{n,n}$ case.

\section{Existence}\label{sec:existence}

 Let $\mathcal{M}_{n,n} \cong S_n$ and $\mathcal{M}_{2n}$ be the collections of perfect matchings of $K_{n,n}$ and $K_{2n}$ respectively. For any $0 \leq k \leq n$, let $\mathcal{M}_{n,n}^k$ and $\mathcal{M}_{2n}^k$ be the collections of \emph{$k$-matchings} (sets of $k$ pairwise-disjoint edges) of $K_{n,n}$ and $K_{2n}$ respectively. For any set $X$, let $\mathbb{R}X$ be the space of real-valued functions on $X$. Let $n^{\underline{k}} := n!/(n-k)!$.

Recall that $\overline{x} = \{x_{i,j}\}_{i,j = 1}^n$ where each $x_{i,j}$ is an indeterminant for the edge $(i,j)$ of $K_{n,n}$. Let $\check{x} = \{x_{ij}\}_{ij \in E}$ be the set of indeterminants for the edges of $K_{2n} = (V,E)$.
We say $p \in \mathbb{C}[\overline{x}]$ is a \emph{presentation} of $f \in \mathbb{C}\mathcal{M}_{n,n}$ if $p(M) = f(M)$ for all $M \in \mathcal{M}_{n,n}$, and $p \in \mathbb{C}[\check{x}]$ is a \emph{presentation} of $f \in \mathbb{C}\mathcal{M}_{2n}$ if $p(M) = f(M)$ for all $M \in \mathcal{M}_{2n}$. If $p,q$ are presentations of $f$, we write $p \equiv q$.
Let $\mathcal{I} = \{x_{i,j}^2 = x_{i,j},~x_{i,j}x_{i,k},~x_{i,k}x_{j,k} \text{ for all } i,j,k \in [n]\}$. We say $p \in \mathbb{C}[\overline{x}]$ is \emph{succinct} if $p \in \mathbb{C}[\overline{x}]/\langle \mathcal{I}\rangle $.
	Let $\mathcal{J} = \{x_e^2 = x_e,~x_ex_f~\text{ for all } e,f \in E(K_{2n}) : |e \cap f| = 1\}$. We say $p \in \mathbb{C}[\check{x}]$ is \emph{succinct} if $p \in \mathbb{C}[\check{x}]/\langle \mathcal{J} \rangle$.
	 As mentioned in the introduction, we often identify degree-$d$ monomials of succinct polynomials by their corresponding $d$-matchings.
We say that a succinct polynomial $p \in \mathbb{C}[\overline{x}]$ is \emph{harmonic} if 
	$\Delta_{i,*}p := \sum_{j=1}^n \partial p/\partial x_{i,j} = 0$ for all $i \in [n]$ and $\Delta_{*,j}p := \sum_{i = 1}^n \partial p/\partial x_{i,j} = 0$ for all $j \in [n]$.
	A succinct polynomial $p \in \mathbb{C}[\check{x}]$ is \emph{harmonic} if $\Delta_vp := \sum_{u \neq v} \partial p/\partial x_{uv} = 0$ for all $v \in V(K_{2n})$.

 First, we show for any $f \in \mathbb{R}S_n$, that there exists a succinct harmonic presentation of $f$. For any $p \in \mathbb{R}[\overline{x}]$, let $p^{=d} \in \mathbb{R}[\overline{x}]$ be the homogeneous degree-$d$ polynomial that is the degree $d$ part of $p$. Let $\Phi_d(p)$ be the sum of squares of coefficients of $p^{=d}$.
\begin{theorem} \label{thm:sym-existence}
	Every $f \in \mathbb{R}S_n$ has a succinct harmonic presentation of degree at most $n-1$.
\end{theorem}
\begin{proof}
	Let $p$ be a succinct presentation of $f$ of degree at most $n-1$. Suppose $p$ is not harmonic, thus we may assume, without loss of generality, that $\Delta_{i,*} p \neq 0$, containing say the term $c m$ where $c > 0$ and $m$ is a degree-$d$ monomial. Let $J$ be the set of all $j \in [n]$ such that $m$ is not a multiple of $x_{k,j}$ for some $k \in [n]$. For any $j \in J$, let $c_j$ be the coefficient of $x_{i,j} m$. Thus $c = \sum_{j \in J} c_j$. Let $q := p - cm(\sum_{j \in J} x_{i,j} - 1)/|J|$. If $m = 1$ then $\sum_{j \in J} x_{i,j} = 1$. Thus $p \equiv q$. Moreover, we have
	\[
			\Phi_{d+1}(p) - \Phi_{d+1}(q) = \sum_{j \in J} \left(c_j^2 - \left(c_j - \frac{c}{|J|}\right)^2 \right) = \frac{2c}{|J|} \sum_{j \in J} c_j - \frac{c^2}{|J|} = \frac{c^2}{|J|} > 0.
	\]
	Using the expression above, we now prove by induction on $\deg p$ that for any succinct polynomial $p$ there is a harmonic succinct polynomial $q$ of degree at most $\deg p$ that is also a presentation of $f$. The base case $\deg p = 0$ holds vacuously, so suppose that $\deg p = d + 1$. Since the space of succinct polynomials that are a presentation of $f$ is compact, there exists a succinct presentation $q$ of $f$ of degree at most $\deg p$ that minimizes $\Phi_{d+1}$. By induction, there is a harmonic polynomial $r$ such that $r \equiv q - q^{=d+1}$. We also have that $q^{=d+1}$ is harmonic; otherwise, there exists a $q' \equiv q$ such that $\Phi(q)_{d+1} -\Phi(q')_{d+1} > 0$, a contradiction. This proves $q^{=d+1} + r$ is a succinct harmonic presentation of $f$ of degree at most $\deg p$, as desired.
\end{proof}
The same proof \emph{mutatis mutandis} shows the following.
\begin{theorem} \label{thm:pm-existence}
	Any $f \in \mathbb{R}\mathcal{M}_{2n}$ admits a succinct harmonic presentation of degree at most $n-1$.
\end{theorem}
Having showed that succinct harmonic presentations of functions over perfect matchings exist, it remains to show that such presentations are \emph{unique}, thus giving a canonical way of presenting a function over perfect matchings as a polynomial. 



\section{Uniqueness} \label{sec:unique}
In this section we prove Theorem~\ref{thm:unique}, that if $p$ is a succinct harmonic presentation of a nonzero function $f$ on perfect matchings, then $p$ is the \emph{unique} succinct harmonic presentation of $f$, and that $p^{=d}$ is the unique succinct harmonic presentation of $f^{=d}$.


Let $W_{\ell,k}$ be the binary $\mathcal{M}_{n,n}^\ell \times \mathcal{M}_{n,n}^{k}$ \emph{bipartite matching inclusion matrix} defined such that $W_{\ell,k}[M,m] = 1$ if $m \subseteq M$, 0 otherwise.
Let $A_{n,k}$ be the $\mathcal{M}_{n,n} \times \mathcal{M}_{n,n}$ matrix defined such that
$A_{n,k}[M,M'] = |\{ m \in \mathcal{M}^{k}_{n,n} : m \subseteq M \text{ and } m \subseteq M' \}| \text{ for all } M,M' \in \mathcal{M}_{n,n}.$
It is clear that $A_{n,k} = W_{n,k}W_{n,k}^\top$, thus $A_{n,k} \succeq 0$. 

Let $W_{\ell,k}'$ be the binary $\mathcal{M}_{2n}^\ell \times \mathcal{M}_{2n}^{k}$ \emph{non-bipartite matching inclusion matrix} defined such that $W_{\ell,k}'[M,m] = 1$ if $m \subseteq M$, 0 otherwise. 
Let $B_{n,k}$ be the $\mathcal{M}_{2n} \times \mathcal{M}_{2n}$ matrix defined such that $B_{n,k}[M,M'] = |\{ m \in \mathcal{M}^k_{2n} : m \subseteq M \text{ and } m \subseteq M' \}| \text{ for all } M,M' \in \mathcal{M}_{2n}.$ It is clear that $B_{n,k} = W_{n,k}'(W_{n,k}')^\top$, thus $B_{n,k} \succeq 0$. 

\begin{proposition}\label{prop:positive}
	We have $\sum_{k=0}^n  \alpha_k A_{n,k} \succ 0$ and $\sum_{k=0}^n  \beta_k B_{n,k} \succ 0$ if $\alpha_k,\beta_k > 0$ for all $k$.
\end{proposition}

\begin{theorem} \label{thm:sym-uniqueness}
	If $p$ is a succinct harmonic polynomial that vanishes on $\mathcal{M}_{n,n}$, then $p = 0$. Moreover, the unique succinct harmonic presentation of any $f \in V^d$ is homogeneous of degree~$d$.
\end{theorem}
\begin{proof}
	Let $p = \sum_m c(m) m$, where $m$ ranges over all matchings of $K_{n,n}$ and $m$ is identified as the monomial $\prod_{(i,j) \in m} x_{i,j}$. We prove by induction on $|m|$ that $c(m) = 0$ for all $m$.
	
	Let $m$ be a matching of size $d$, and consider the average $\overline{p}_m$ of $p$ over the set $\mathcal{M}_{n,n}(m)$ of perfect matchings $M \in \mathcal{M}_{n,n}$ that contain $m$. If $m' \subseteq M$ and $m \subseteq M$ for some perfect matching $M$, then we say $m'$ is \emph{compatible with} $m$. The probability of drawing from $\mathcal{M}_{n,n}(m)$ a perfect matching $M$ such that $m' \subseteq M$ is $1/(n-d)^{\underline{|m' \setminus m|}}$. Since $p(M) = 0$ for all $M \in \mathcal{M}_{n,n}(m)$, we have $\overline{p}_m = 0$, thus
	\[
		0 = \overline{p}_m = \sum_{m' \text{ compatible with } m} \frac{1}{(n-d)^{\underline{|m' \setminus m|}}} c(m').
	\]
	
	Let $A,B$ be the two subsets of the same size such that $m$ is a perfect matching between $\overline{A}$ and $\overline{B}$. Let $\mathcal{M}$ be the set of matchings between $A$ and $B$. Then we can rewrite $\overline{p}_m$ as
	\[
		0 = \overline{p}_m = \sum_{e=0}^{n-d} \frac{1}{(n-d)^{\underline{e}}} \sum_{w \subseteq m} \sum_{\substack{w' \in \mathcal{M} \\ |w'| = e}} c(w w'),
	\]
	where the notation $ww'$ denotes the matching $w \sqcup w'$. Let $(s_i,t_j)$ denote an edge of $K_{n,n}$.
	
	Fix $w \subseteq m$ and $e \geq 0$. Then the innermost summation on the RHS can be written as
	\[
		\sum_{\substack{w' \in \mathcal{M} \\ |w'| = e}} c(w w') =
		\frac{1}{e!}
		\sum_{\substack{s_1, \ldots, s_e \in A \\ s_i \neq s_j}} \sum_{\substack{t_1, \ldots, t_e \in B \\ t_i \neq t_j}} c(w(s_1,t_1) \cdots (s_e,t_e)).
	\]
	
	Fix distinct $s_1,\ldots,s_e \in A$. Then the innermost summation on the RHS equals
	\[
	\sum_{\substack{t_1, \ldots, t_e \in B \\ t_i \neq t_j}} c(w (s_1,t_1) \cdots (s_e,t_e)) =
	\sum_{t_1 \in B} \sum_{t_1 \neq t_2 \in B} \cdots \sum_{t_1,\ldots,t_{e-1} \neq t_e \in B} c(w (s_1,t_1) \cdots (s_e,t_e)).
	\]
	
	Let $A_w,B_w$ be the two subsets such that $w$ is a perfect matching between $\overline{A_w}$ and $\overline{B_w}$.
	Since $p$ is harmonic, we have $
	\sum_{t_1,\ldots,t_{e-1} \neq t_e \in B_w} c(w (s_1,t_1) \cdots (s_e,t_e)) = 0$,
	since the LHS is the coefficient of $w (s_1,t_1) \cdots (s_{e-1},t_{e-1})$ in $\Delta_{s_e,*} p$.
	Thus
	\[
	\sum_{t_1,\ldots,t_{e-1} \neq t_e \in B} c(w (s_1,t_1) \cdots (s_e,t_e)) =
	- \sum_{t_e \in B_w \setminus B} c(w (s_1,t_1) \cdots (s_e,t_e)).
	\]
	Exchanging summations and applying the same argument to $s_e \in A$ as well gives us
	\[
	\sum_{\substack{w' \in \mathcal{M} \\ |w'| = e}} c(w w') =
	\frac{1}{e!}
	\sum_{\substack{s_1, \ldots, s_{e-1} \in A \\ s_i \neq s_j}}
	\sum_{\substack{t_1, \ldots, t_{e-1} \in B \\ t_i \neq t_j}}
	\sum_{s_e \in A_w \setminus A}
	\sum_{t_e \in B_w \setminus B}
	c(w (s_1,t_1) \cdots (s_e,t_e)).
	\]
	Repeating this argument successively for $t_{e-1},s_{e-1},\ldots, t_1,s_1$ gives
	\[
	\sum_{\substack{w' \in \mathcal{M} \\ |w'| = e}} c(w w') =
	\frac{1}{e!}
	\sum_{\substack{s_1, \ldots, s_e \in A_w \setminus A \\ s_i \neq s_j}} \sum_{\substack{t_1, \ldots, t_e \in B_w \setminus B \\ t_i \neq t_j}} c(w (s_1,t_1) \cdots (s_e,t_e)).
	\]
	The double sum on the RHS vanishes unless $|A_w \setminus A| \geq e$. Note that $|A_w \setminus A| = d - |w|$, so the coefficients vanish by induction unless $|w| + e \geq d$, that is, unless $d - |w| \leq e$. It follows that the double sum vanishes unless $e = d - |w|$, in which case 
	after division by $e!$
	it is equal to
	$
	\sum_{w' \in \mathcal{M}(m \setminus w)} c(ww'),
	$
	where $\mathcal{M}(m \setminus w)$ is the set of all perfect matchings on the same vertices as $m \setminus w$. Let $\alpha_i := 1/(n-d)^{\underline{d-i}}$. We arrive at the following system:
	\[
	\sum_{w \subseteq m} \alpha_{|w|} \sum_{w' \in \mathcal{M}(m \setminus w)} c(ww') = 0 \quad \text{ 	for all $m \in \mathcal{M}_{n,n}^d$.}
	\]	
	
	Our goal is to show $c(m) = 0$ for all $m \in \mathcal{M}_{n,n}^d$ is the only solution. Let $A$ and $B$ be $d$-sets of vertices on the left and right of $V(K_{n,n})$, and consider all perfect matchings $m \in \mathcal{M}(A,B)$ between $A$ and $B$. Each choice of $A,B$, induces a subsystem of the above system of equations, and it suffices to show it has full rank. To this end, we show that the matrix associated to this subsystem of equations is positive definite.
	
	In the equation corresponding to $m \in \mathcal{M}(A,B)$, the coefficient corresponding to the perfect matching $m' \in \mathcal{M}(A,B)$ is $\sum_{w \subseteq (m \cap m')} \alpha_{|w|}$.
	Identifying $\mathcal{M}(A,B)$ with $\mathcal{M}_{d,d}$, for each $m \in \mathcal{M}_{d,d}$ we get an equation of the form 
	$
	\sum_{m' \in \mathcal{M}_{d,d}} \sum_{i=0}^d \alpha_i {A_{d,i}[m,m'] }c(m')  = 0.
	$
	The matrix of this system is $\sum_{i=0}^d \alpha_i {A_{d,i}}$, which by Proposition~\ref{prop:positive} is positive definite. 
	
By induction, we have $c(m) = 0$ for all matchings $m$, \textit{i.e.}, $p=0$, as desired. 

Finally, the second part of the theorem can be shown by a routine induction.
%Finally, for the second part of the theorem, we claim that the proof above in fact shows any degree-$d$ function $f \in V^d$ has a \emph{homogeneous} succinct harmonic presentation of degree~$d$. Indeed, we showed by induction that if a succinct harmonic polynomial is orthogonal to all monomials of degree at most $e < d$, then the coefficients of all monomials of degree up to $e$ vanish. Applying this for $e = d-1$ gives the result.
\end{proof}
%\ A similar proof using the $B_{n,k}$ matrices gives the following.
\begin{theorem}\label{thm:pm-uniqueness}
	If $p$ is a succinct harmonic polynomial that vanishes on $\mathcal{M}_{2n}$, then $p = 0$. Moreover, the unique succinct harmonic presentation of any $f \in V^d$ is homogeneous of degree~$d$.
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm:unique}]
For any $f \in \mathbb{R}S_n$, there is a $e$ such that $f \in V^{\leq e} := V^0 \oplus \cdots \oplus V^e$, so that $f = f^{=0} + \cdots + f^{=e}$ (similarly for $f \in \mathbb{R}\mathcal{M}_{2n}$). Applying Theorems~\ref{thm:sym-existence} and~\ref{thm:sym-uniqueness} for $\mathcal{M}_{n,n}$ and Theorems~\ref{thm:pm-existence} and~\ref{thm:pm-uniqueness} for $\mathcal{M}_{2n}$ gives the desired result.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Structure of Canonical Presentations}\label{sec:jack}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we give explicit descriptions of canonical presentations by determining the canonical presentations of the \emph{Specht bases} $\{ f_{s,t} \in \mathbb{R}[\overline{x}]: s,t \text{ standard $\lambda$-tableaux}, \lambda \vdash n  \}$ and $\{ f_u \in \mathbb{R}[\check{x}] : u \text{ standard $2\lambda$-tableau}, \lambda \vdash n\}$ of $\mathbb{R}S_n$ and $\mathbb{R}\mathcal{M}_{2n}$. Here, we define 
\[
f_{s,t}(\overline{x}) := \sum_{\tau \in R_s} \sum_{\sigma \in C_t} \text{sgn}(\sigma) x(\tau s,\sigma t) \quad \text{and} \quad f_{u}(\check{x}) := \frac{1}{\prod_i 2^{\lambda_i}\lambda_i!}\sum_{\tau \in R_u} \sum_{\sigma \in C_u} \text{sgn}(\sigma) x(\tau \sigma u)
\]
where $C_t$ ($R_t$) is the \emph{column (row) stabilizer} of $t$, $x(s, t) := \prod_{(i,j) \in \lambda} x_{ s_{i,j}, t_{i,j}}$, $x(u) := \prod_{ab} x_{ab}$ such that $ab$ ranges over all pairs of \emph{aligned} adjacent elements in the $2\lambda$-tableau $u$ (\textit{i.e.}, $a$ is in an odd column, and $b$ is the following entry on the same row). Computing the canonical presentation $p_{s,t}$ of $f_{s,t}$ will require us to introduce a few differential operators and compute the eigenvalues of $A_{n,k}$ and $B_{n,k}$, which we have already shown to be PSD. These eigenvalues are intimately related to a class of symmetric functions known as Jack polynomials, which we overview in the next section.

From the definition above, one can show that Specht polynomials can be expressed as a sum of $\lambda_1$-many products of determinants corresponding to the pairs of columns of $s,t$ (adjacent columns of $u$). Let $D_k := (\sum_{i,j=1}^n {\partial}/{\partial x_{i,j}})^{k}/k!$ and $D_k' := (\sum_{ij \in E(K_{2n})} {\partial}/{\partial x_{ij}})^{k}/k!$.
%We define $D'_k$ and $U'_k$ similarly for $\mathcal{M}_{2n}$ where the sum runs over $ij \in E(K_{2n})$. 
Let $D := D_1$, $D' := D_1'$. Let $I = i_1,\ldots,i_d \in [n]$ be distinct and $J = j_1,\ldots,j_d \in [n]$ be distinct. Let $X$ be the $d \times d$ matrix with $X_{a,b} = x_{i_a,j_b}$. Define the \emph{quasi-determinant} to be
\[
q(I, J)(\overline{x}) := \sum_{i \in I,j \in J} \frac{\partial}{\partial x_{i,j}} \det X = \sum_{i \in I,j \in J} \frac{\partial}{\partial x_{i,j}} \sum_{\pi \in S_d} \text{sgn}(\pi) \prod_{s \in [d]} x_{i_s,j_{\pi(s)}}.
\]
We define $q(I, J)(\check{x})$ similarly, replacing the ordered pair $i,j$ with the 2-set $ij$.
\begin{proposition} \label{prop:quasidet}
	$q(I,J)$ is harmonic.
\end{proposition}
\begin{proof}
	Without loss of generality, let $i_a = a$ and $j_b = b$ for any $a,b \in [d]$. We have $q([d],[d]) =
	\sum_{\pi \in S_d} \text{sgn}(\pi) \sum_{t \in [d]} \prod_{\substack{s \in [d] : s \neq t}} x_{s,\pi(s)}.
	$
	Now suppose that we sum the partial derivatives with respect to $x_{i,1},x_{i,2},\ldots,x_{i,n}$ for any $i \in [n]$. If $i \notin [d]$ then this is clearly 0; otherwise, 
	$
	\sum_{\pi \in S_d} \text{sgn}(\pi)  \sum_{\substack{t \in [d] : t \neq i}} \prod_{\substack{s \in [d] : s \neq t,i}} x_{s,\pi(s)}.
	$
	Each monomial appears exactly twice with different signs, as $\text{sgn}(\pi) = -\text{sgn}((i,t)\pi)$; therefore, the sum vanishes.
\end{proof}
 A similar proof shows $q(I, J)(\check{x})$ is harmonic.

Let $f_{s,t}'(\overline{x})$ and $f_{u}'(\check{x})$ be the \emph{quasi-Specht polynomials} defined by replacing determinants with $q(\cdot,\cdot)$, \textit{i.e.}, $f_{s,t}'(\overline{x}) :=  \sum_{\tau \in R_s} \prod_{i=1}^{\lambda_1} q((\tau s)_i, t_i)$ and $f_{u}'(\check{x}) :=  \sum_{\tau \in R_u} \prod_{i=1}^{\lambda_1} q((\tau u)_{2i-1}, u_{2i})$ 
where $t_i$ is the $i$th column of $t$. It is clear that quasi-Specht polynomials are harmonic.

The quasi-Specht and Specht polynomials are related by the formula $f'_{s,t} = D_{\lambda_1} f_{s,t}$. Indeed,
%The formula actually holds for every specific $\tau$, so let us fix $\tau$ to be the identity.	
by the product rule, applying $D$ to a product of quasideterminants is the same as summing over all ways to apply it to each factor. By Proposition~\ref{prop:quasidet}, if we apply $D$ twice to the same factor then we get zero, and so when applying $D^{\lambda_1}$, we must apply each $D$ to a different factor, and there are $\lambda_1 !$ ways to do this. Similarly, we have $f'_u = D'_{\lambda_1}f_u$.

Although $f'_{s,t}$ is harmonic, it is \emph{not} a presentation of $f_{s,t}$, \textit{i.e.}, $f_{s,t}' \not \equiv f_{s,t}$ (similarly, $f'_u \not \equiv f_u$). In the next section, we use Jack polynomials to compute two constants $d_\lambda(1), d_\lambda(2)$ such that $d_\lambda(1)^{-1}f_{s,t}'$, $d_\lambda(2)^{-1}f_{u}'$ are in fact the canonical presentations of $f_{s,t}$, $f_u$.


\subsection{Jack Polynomials}


We refer the reader to~\cite{M95,S89} for more details on symmetric functions and Jack polynomials.
Let $x := x_1,x_2, \ldots$ and $y := y_1,y_2,\ldots$ be disjoint sets of indeterminants. 
%Let $\Lambda = \oplus_n \Lambda_n$ be the ring of \emph{symmetric functions} graded by degree.
For any $\alpha \in \mathbb{R}$, let $\langle \cdot, \cdot \rangle_\alpha$ be the inner product on the ring $\Lambda = \oplus_n \Lambda_n$ of symmetric functions (graded by degree) defined such that $\langle p_\lambda , p_\mu \rangle_\alpha = \delta_{\lambda \mu } \alpha^{\ell(\lambda)}z_\lambda$ where $\ell(\lambda)$ denotes the number of parts of an integer partition $\lambda \vdash n$ and $z_\lambda$ is the order of the centralizer of a permutation of cycle-type $\lambda \vdash n$.
%The \emph{monomial symmetric functions} $\{m_\mu\}_{\mu \vdash n}$ form a vector space basis for $\Lambda_n$, and 
Recall that $\trianglelefteq$ denotes the \emph{dominance ordering} on $\lambda \vdash n$ (see~\cite{M95}). For a given $\alpha \in \mathbb{R}$, the \emph{Jack polynomials} $\{J_\lambda\}_{\lambda \vdash n}$ are the unique vector space basis of $\Lambda_n$ such that $\langle J_\lambda, J_\mu \rangle_\alpha = 0$ if $\lambda \neq \mu$, $J_\lambda = \sum_{\mu \trianglelefteq \lambda } c_{\lambda \mu}m_\mu$, and $[m_{1^n}]J_\lambda = n!$. A skew tableau on $r$ cells is a \emph{horizontal strip} (\emph{$r$-strip} for short) if no two of its cells lie in the same column. We write $\mu + r = \lambda$ if $|\lambda| \geq |\mu|$ and they differ by an $r$-strip. Let $J_r := J_{(r)}$.

Let $a_\lambda(i,j)$ and $l_\lambda(i,j)$ be the \emph{arm length} and \emph{leg length} of a cell $\Box = (i,j) \in \lambda$, \textit{i.e.}, the number of cells in row $i$ to the right of $(i,j)$, and the number of cells in column $j$ below $(i,j)$. Let $h^{*}_\lambda(\Box) :=  a_\lambda(\Box)\alpha + l_\lambda(\Box) + \alpha$ and $h_{*}^\lambda(\Box) :=  a_\lambda(\Box)\alpha + l_\lambda(\Box) + 1$
be the \emph{$\alpha$-lower hook length} and \emph{$\alpha$-upper hook length} of $\Box \in \lambda$. Let $H^{*}_\lambda :=  \prod_{\Box \in \lambda} h^{*}_\lambda(\Box)$ and 
$H_{*}^\lambda :=  \prod_{\Box \in \lambda} h_{*}^\lambda(\Box)$.
The coefficients $\theta_\mu^\lambda (\alpha)$ of the $J_\lambda$'s written in the power sum basis, \textit{i.e.}, $J_\lambda = \sum_{\mu \vdash n} \theta_\mu^\lambda (\alpha) p_\mu$, 
are sometimes called the \emph{Jack characters} (see~\cite{S89}). 

For all $\lambda \vdash n$, $k \leq n$, let $\eta^{\lambda}_{k}(\alpha) := \sum_{\mu \vdash n}\theta^{\lambda}_{\mu}(\alpha) \text{fp}(\mu)^{\underline{k}}$ where $\text{fp}(\mu)$ is the number of parts of $\mu$ equal to 1. We show $\eta^{\lambda}_{k}(\alpha)$ is the $\alpha$-\emph{Kostka number}~\cite[p. 327]{M95} $u_{\lambda \mu} =:  K_{\lambda, (n-k,1^k)}{(\alpha)}$ of shape $\lambda$ and content $(n-k,1^k)$ scaled by the upper hook product of $\lambda$.
\begin{theorem}\label{thm:eigs}
	$\eta^{\lambda}_{k}(\alpha) = H^{\lambda}_{*} K_{\lambda, (n-k,1^k)}{(\alpha)}$.
\end{theorem}
\begin{proof}
We have $\sum_{\lambda} {J_\lambda(x)J_\lambda(y)}/{H_{(\alpha)}^\lambda H^{(\alpha)}_\lambda } = \prod_{i,j} (1-x_iy_j)^{-1/\alpha} =  \prod_{r \geq 1} \exp {p_r(x)p_r(y)}/{\alpha r}$ by the Cauchy identity~\cite{S89}. Recall that $p_1 = J_1$ and $h_r = J_r$ for all $r$. Differentiating $k$ times with respect to $p_1(y)$ and then setting $p_r(y) = 1$ for all $r$ gives
\begin{align*}
	\sum_{\lambda} \frac{\eta^{\lambda}_{k}(\alpha)}{H_{(\alpha)}^\lambda H^{(\alpha)}_\lambda} J_\lambda(x) &= \alpha^{-k}p_1^{k}\prod_{r \geq 1} \exp \frac{p_r(x)}{\alpha r}\\
	 &= \alpha^{-k} \sum_{r} \frac{J_1^kJ_r}{\alpha^r r!} = k! \sum_{r} \frac{ \sum_{\mu \vdash k} J_rJ_\mu }{ \alpha^r r!~H_{(\alpha)}^\mu H^{(\alpha)}_\mu}.
\end{align*}
By Pieri's rule~\cite{S89}, we have $[J_\lambda]J_{r}J_\mu =  \prod_{\Box \in \mu} A_{\lambda \mu}(\Box) \prod_{\Box \in \lambda} B_{\lambda \mu}(\Box) \alpha^{r}r!/H^\lambda_* H^*_\lambda$ if $\lambda/ \mu$ is an $r$-strip, 0 otherwise, where 
\[
A_{\lambda \mu}(\Box) =
\begin{cases}
h^\mu_{*}(\Box) \quad &\text{if $\lambda / \mu$ does not contain a square in the same column as $\Box$;}\\
h_\mu^{*}(\Box)\quad &\text{otherwise,}
\end{cases}
\]
\[
B_{\lambda \mu}(\Box) =
\begin{cases}
h_\lambda^{*}(\Box) \quad &\text{if $\lambda / \mu$ does not contain a square in the same column as $\Box$;}\\
h^\lambda_{*}(\Box)\quad &\text{otherwise.}
\end{cases}
\]
Equating coefficients of $J_\lambda(x)$ gives $\eta_k^\lambda (\alpha) = k! \sum_\mu {\prod_{\Box \in \mu} A_{\lambda \mu}(\Box) \prod_{\Box \in \lambda} B_{\lambda \mu}(\Box)}/{H^\mu_* H^*_\mu}$ where $\mu$ ranges over all shapes such that $\lambda/\mu$ is a $(n-k)$-strip.  
Let $C_{\lambda \mu}$ ($R_{\lambda \mu}$) be the cells of $\lambda$ that belong to a column (row) that intersects $\lambda / \mu$. We have
\[
	\eta_k^\lambda (\alpha) = H^{\lambda}_{*} \!\!\!\! \!\!\!\!\sum_{\substack{\mu \vdash k \\ \mu + (n-k) = \lambda }} \!\!\!\! \frac{k!}{H_{*}^\mu } \prod_{\Box \not \in C_{\lambda \mu}} \frac{h_\lambda^{*}(\Box)h^\mu_{*}(\Box)}{h^\lambda_{*}(\Box)h_\mu^{*}(\Box)} = H^{\lambda}_{*} \!\!\!\! \!\!\!\! \sum_{\substack{\mu \vdash k \\ \mu + (n-k) = \lambda }} \!\!\!\! \frac{k!}{H_{*}^\mu } \prod_{\Box \in R_{\lambda \mu} \! \setminus C_{\lambda \mu}} \frac{h_\lambda^{*}(\Box)h^\mu_{*}(\Box)}{h^\lambda_{*}(\Box)h_\mu^{*}(\Box)},    
\]
where we have identified $\mu$ as a subshape of $\lambda$. The product over $\Box \in R_{\lambda \mu} \!\! \setminus \!\! C_{\lambda \mu}$ is $\psi^{(\alpha)}_{\lambda/\mu}$ as defined in~\cite[VI (10.11)]{M95}. Since $[m_{1^k}]P_\mu = k!/H^\mu_*$ where the $P_\mu$'s are the normalized Jack polynomials~\cite[VI Section~10]{M95}, the summation equals $K_{\lambda,(n-k,1^k)}{(\alpha)}$, as desired.
\end{proof}
 Let $d_\lambda(\alpha) =  \prod_{j=1}^{\lambda_1} h^{\lambda}_{*}(1,j)$. Stanley~\cite{S89} showed $[x_1^{\lambda_1}]J_\lambda(x) = d_\lambda(\alpha)J_{(\lambda_2,\ldots,\lambda_\ell)}(x_2,x_3,\ldots)$, so Theorem~\ref{thm:eigs} can be seen as a straightforward generalization of this result.

Let $\mathfrak{A}_{n,n}$ and $\mathfrak{A}_{2n}$ be the commutative \emph{Bose--Mesner algebras} generated by binary matrices $\{A_{\lambda}\}_{\lambda \vdash n}$ that are indexed by perfect matchings $M$ (of $K_{n,n}$ and $K_{2n}$ respectively) and defined such that $A_\lambda[M,M'] = 1$ if the multi-union $M \cup M'$ is isomorphic to a disjoint union of cycles $C_{2\lambda_1} \sqcup \cdots \sqcup C_{2\lambda_{\ell(\lambda)}}$ where $C_{2\lambda_i}$ denotes the cycle on $2\lambda_i$ edges (see~\cite{GodsilMeagher} for more details on the Bose--Mesner algebras of association schemes).
\begin{corollary}\label{cor:eigs}
	The eigenvalues of $A_{n,k}$ are $\{\eta_k^\lambda(1)\}_{\lambda \vdash n}$. 	The eigenvalues of $B_{n,k}$ are $\{\eta_k^\lambda(2)\}_{\lambda \vdash n}$. In particular, for any $\lambda \vdash n$, we have $\eta_{n-\lambda_1}^\lambda(1) = d_\lambda(1)$ and $\eta_{n-\lambda_1}^\lambda(2) = d_\lambda(2)$.
\end{corollary}
\begin{proof}
	The Jack character $\theta^\lambda_\mu(\alpha)$ for $\alpha = 1,2$ is the $\lambda$-eigenvalue of the basis element $A_\mu$  of $\mathfrak{A}_{n,n}$ and $\mathfrak{A}_{2n}$ respectively (see~\cite[VII Section 2 Example 5]{M95}). We may write $A_{n,k}$ and $B_{n,k}$ as
	\[
		A_{n,k} = \frac{1}{k!}\sum_{\mu \vdash n}\text{fp}(\mu)^{\underline{k}} A_{\mu}\quad (A_\mu \in \mathcal{A}_{n,n})\quad \text{ and } \quad B_{n,k} = \frac{1}{k!} \sum_{\mu \vdash n}\text{fp}(\mu)^{\underline{k}} A_{\mu} \quad (A_\mu \in \mathcal{A}_{2n}),
	\]
	which completes the first part of the proof. Finally, if $k = n-\lambda_1$, then there is a single $\mu = (\lambda_2,\ldots,\lambda_{\ell(\lambda)})$ such that $\lambda/\mu$ is a $\lambda_1$-strip, thus $K_{\lambda,(n-k,1^k)}{(\alpha)}$ is easily computed.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:specht}]
Note that $W_{n,k}^\top$, $(W_{n,k}')^\top$ are the functional analogues of $D_{n-k}$, $D_{n-k}'$, as $f_{s,t}' = D_{\lambda_1}f_{s,t}$ is $(n-\lambda_1)$-homogeneous and $[m]f_{s,t}' = \sum_{M \supseteq m} [M]f_{s,t}$ (similarly for $f_u'$). 
Let $E_\lambda \in \mathfrak{A}_{n,n}$, $E_\lambda \in \mathfrak{A}_{2n}$ be the $\perp$-projections onto $V^\lambda$, $V^{2\lambda}$. 
For all $f_{s,t} \in V^\lambda, f_u \in V^{2\lambda}$ and $\mu \neq \lambda$, we have $E_{\mu} f_{s,t} = 0$, $E_\mu f_u = 0$, thus
\[
	A_{n,n-\lambda_1}f_{s,t} = \sum_{\mu \vdash n} \eta_{n-\lambda_1}^\mu E_\mu f_{s,t} = d_\lambda(1) f_{s,t}, \quad  B_{n,n-\lambda_1}f_{u} = \sum_{\mu \vdash n} \eta_{n-\lambda_1}^\mu E_\mu f_{u} = d_\lambda(2) f_{u}.
\]
The foregoing shows that $f'_{s,t}(\sigma) = [D_{\lambda_1} f_{s,t}](\sigma) = (W_{n,n-\lambda_1}W_{n,n-\lambda_1}^\top f_{s,t})_{\sigma} = (A_{n,n-\lambda_1} f_{s,t})_{\sigma}$ for all $\sigma \in S_n$, and similarly, that $f'_u(M) = (B_{n,n-\lambda_1}f_u)_M$ for all $M \in \mathcal{M}_{2n}$. By Corollary~\ref{cor:eigs}, we have $p_{s,t} := d_\lambda(1)^{-1} f'_{s,t} \equiv f_{s,t}$ and $p_u := d_\lambda(2)^{-1}f_{u}' \equiv f_{u}$. Since $f'_{s,t},f'_u$ are harmonic, we deduce that $p_{s,t},p_u$ are canonical presentations, as desired.
\end{proof}

%	Since $A_{n,{\lambda_1}} = W_{n,k}W_{n,k}^\top \cong U_{\lambda_1}D_{\lambda_1}$, we have . By Proposition~\ref{prop:quasidet}, we have that $p_{s,t}$ is harmonic, thus it is the canonical presentation of $f_{s,t}$. A similar argument shows that $p_t := d_\lambda(2)^{-1}D_{\lambda_1}'f_{t} \equiv f_{t}$ is the canonical presentation of $f_{t}$. This completes the proof of Theorem~\ref{thm:specht}.


\subsection{A Combinatorial Identity for $d_\lambda(\alpha)$}

The main result of this section is Theorem~\ref{thm:combident} which gives a combinatorial formula for $d_\lambda(\alpha)$ in terms of \emph{tableau transversals}. The formula was inspired by the fact that $f_{s,t}$ and $f_u$ are eigenfunctions of $A_{n,k}$ and $B_{n,k}$, and that our combinatorial arguments in these cases readily generalized to arbitrary $\alpha$. Indeed, for $\alpha = 1,2$ it is well-known that there are combinatorial expressions for $\theta^\lambda_\mu(1),\theta^\lambda_\mu(2)$ in terms of perfect matchings by appealing to their representation theory (see~\cite[Ch. 11]{CST}, for example); however, such combinatorial expressions for general $\alpha$ are elusive~(see~\cite{Han88}, for example). Here, we are only considering particular weighted sums of Jack characters, nevertheless, this expression for $d_\lambda(\alpha)$ might shed some light on the combinatorics of $\theta^\lambda_\mu(\alpha)$.  

A \emph{transversal} $T$ of a tableau $\lambda$ is a set of cells which forms a transversal of the columns of $\lambda$. For example, $S = \{(2,1), (1,2),(2,3),(1,4)\}$ is a transversal of $(4,3,2,1) \vdash 10$. We define the \emph{$\alpha$-weight} of a transversal $T$ to be $w_\alpha (T) = H^T_*$. For example, $w_\alpha(S) = (\alpha + 1)^2$. 
% \prod_{k=1}^{\ell(\lambda)} |\{ (i,j) \in T : i = k \}|!_{(\alpha)}$.
Let $\mathcal{T}_\lambda$ be the collection of transversals of $\lambda$. 
%Define $\lambda! := \lambda_1 \lambda_2 \cdots \lambda_{\ell}$ and let $\lambda'$ is the transpose of $\lambda$. It is clear that $|\mathcal{T}_\lambda| = (\lambda')!$.  
Define $w_\alpha(\lambda) := \sum_{T \in \mathcal{T}_\lambda}w_\alpha(T)$.

For any $n \in \mathbb{R}$ and $k \in \mathbb{Z}$, recall that the binomial coefficient generalizes as a real-valued function $\binom{n}{k} := \prod_{i=1}^k (n-i+1) /k!$. The following can be shown via negative binomial coefficient identities and Vandermonde's identity for real-valued arguments.
\begin{theorem}\label{thm:convolution} For $a,b \in \mathbb{R}$ and $c \in \mathbb{N}$, we have
	$
	\binom{a+b+c-1}{c} = \sum_{d=0}^c \binom{a+c-d-1}{c-d} \binom{b+d-1}{d}. 
	$
\end{theorem}
%Let $(j+1)!_\alpha := (\alpha(j) + 1)(\alpha(j-1)+1)\cdots (\alpha + 1)(1)$
Let $N!_\alpha := N \cdot (N-\alpha)!_\alpha$ where $N!_\alpha = 1$ if $N < \alpha$. For any $k \leq N$, let $N^{\underline{k}_\alpha}$ be the product of the first $k$ factors of $N!_\alpha$. The following consequence of Theorem~\ref{thm:convolution} will be useful.
\begin{proposition}\label{prop:identity} 
	Let $\alpha \in \mathbb{R}$ and $i,k \in \mathbb{Z}$ such that $0 \leq i \leq k$. For all $N \geq k$, we have 
	$$N^{\underline{k}_\alpha} = \sum_{j=0}^{k} \binom{k}{j} (\alpha(j+i)-1)^{\underline{j}_\alpha}~(N-1-\alpha(j+i))^{\underline{k-j}_\alpha}.$$
\end{proposition}
\begin{proof} 
	Let $N = \alpha n + r$ such that $0 \leq r < \alpha$. It suffices to show that
	$$\frac{N^{\underline{k}_\alpha}}{\alpha^k k!} = \sum_{j=0}^{k} \frac{(\alpha (j+i)-(\alpha-1))^{\underline{j}_\alpha}}{\alpha^j j!}~\frac{(N-1-\alpha(j+i))^{\underline{k-j}_\alpha}}{\alpha^{k-j}(k-j))!}, \text{ equivalently,}$$
	\[
		\binom{n + r/\alpha }{k} = \sum_{j=0}^{k} \binom{j+i-(\alpha-1)/\alpha}{j}~\binom{n-(j+i)+ (r-1)/\alpha}{k-j}.
	\]
	Theorem~\ref{thm:convolution} with $a = n-k-i+(r-1)/\alpha$, $b = i + 1/\alpha$, $c = k$, $d=j$ gives the result.
\end{proof}

 An \emph{inner corner} of a shape $\lambda$ is a cell $\Box \in \lambda$ such that $h_\lambda(\Box) = 1$. The following relates $\alpha$-weighted sums of tableau transversals to upper hook products along the top row.
\begin{theorem}\label{thm:combident}
%For any shape $\lambda$ and $\alpha \in \mathbb{R}$, we have 
$d_\lambda(\alpha) = w_\alpha(\lambda)$
\end{theorem}
\begin{proof}
	We proceed by induction on $n = |\lambda|$. The claim is vacuously true for $|\lambda|=1$. Let $ (r,c) \in \lambda$ be the inner corner of $\lambda$ such that $r$ is maximum. Let $\lambda^- \vdash (n-1)$ be the shape obtained from $\lambda$ by removing $(r,c)$. By induction, we have
	\[
		\sum_{T \in \mathcal{T}_{\lambda^-} } w_\alpha(T) = \prod_{j=1}^{\lambda_1^-} h^{\lambda^-}_{*}(1,j) = (h^\lambda_{*}(1,c)-1)\prod_{j \neq c}^{\lambda_1} h^\lambda_{*}(1,j).
	\]
	Let $\mathcal{T}' := \mathcal{T}_\lambda \setminus \mathcal{T}_{\lambda^-}$ be the transversals of $\lambda$ that contain $(r,c)$. It suffices to show that
	\[
		\sum_{T \in \mathcal{T}'}w_\alpha (T) = \prod_{j \neq c}^{\lambda_1} h^\lambda_{*}(1,j).
	\]
	By our choice of $(r,c)$, the shape induced by the columns of $\lambda$ with index less than $c$ is $(r^{c-1}) \vdash r(c-1)$.
	Let $\mu$ be the shape obtained from $\lambda$ by deleting its $c$th column.
	There are $\binom{c-1}{j}$ ways a transversal $T \in \mathcal{T}'$ can choose $j$ columns from $\mu_r$. For every such choice, the $\alpha$-weight along the $r$th row is $(j+1)!_\alpha = (j+1)^{\underline{j}_\alpha}$.
	%$(\alpha j - 1)!_{(\alpha)}(\alpha (j + 1) - 1)=
	%$(\alpha (j + 1) - 1)!_{\alpha}$.
	%since we must also account for $(r,c) \in T$. 
	Let 
	$h := h^\lambda_{*}(1,1)$ and $X := \prod_{l=c+1}^{\lambda_1}h^\lambda_{*}(1,l)$. By induction, the remaining $\alpha$-weight on the rows $(\mu_1,\ldots,\mu_{r-1})$
	%applying the induction hypothesis to the shape $(\mu_1,\mu_2,\ldots,\mu_{r-1})$ 
	is $(h-1-(j+1))^{\underline{c-1-j}_\alpha} X$.
	Summing over all $j$ with $N = h$, $k = c-1$, and $i=1$ in Proposition~\ref{prop:identity} gives
	\[
		\sum_{T \in \mathcal{T}'}w_\alpha (T) = [h^{\underline{c-1}_\alpha }] X = \left[ \sum_{j=0}^{c-1}\binom{c-1}{j}(j+1)^{\underline{j}_\alpha} ~(h-1-(j+1))^{\underline{c-1-j}_\alpha} \right] X.
	\]
	This gives us $ \sum_{T \in \mathcal{T}'}w_\alpha (T) = h^{\underline{c-1}_\alpha } X = \prod_{j \neq c}^{\lambda_1} h^\lambda_*(1,j)$ as desired.
\end{proof}
%Our weight function $w$ can be generalized as follows:
%\[
%w_2(T) := \prod_{k=1}^{\ell(\lambda)} \left(2 \left |\left \{ (i,j) \in T : i = k \right \} \right|-1\right)!!.
%\]
%Define $w_2(\lambda) := \sum_{T \in \mathcal{T_\lambda}}w_2(T)$. Define the \emph{falling even double factorial} 
%$$(\!( 2n )\!)_k := 2^k(n)_k$$ 
%and the \emph{falling odd double factorial}  $(\!(2n+1)\!)_k := (2n+1)!!/(2(n-k)+1)!!.$
%\begin{proof}
%	By the binomial theorem and the well-known Vandermonde identity (which holds for complex arguments, see~\cite{WilfMaybe?}), we have
%	\begin{align*}
%	\sum_{d=0}^c \binom{a+c+d-1}{d-c} \binom{b+c-1}{d}
%	&=\sum_{d=0}^c(-1)^{c-d}\binom{-a}{c-d}(-1)^d\binom{-b}{d}\\
%	&=(-1)^c\sum_{d=0}^c\binom{-a}{c-d}\binom{-b}{d}\\
%	&=(-1)^c\binom{-a-b}{c}\\
%	&=\binom{a+b+c-1}{c},
%	\end{align*}
%	as desired.
%\end{proof}
%\begin{proposition}\label{prop:identity2} 
%	Let $i,k \in \mathbb{Z}$ such that $0 \leq i \leq k$. For all $n \geq k$, we have 
%	$$(\!(n)\!)_{k} = \sum_{j=0}^{k} \binom{k}{j} (\!(2(j+i)-1)\!)_j~(\!(n-1-2(j+i))\!)_{k-j}.$$
%\end{proposition}
%\begin{proof} 
%	Let $N \geq k$. It suffices to show
%	$$\frac{(\!(N)\!)_{k}}{(2k)!!} = \sum_{j=0}^{k} \frac{(\!(2(j+i)-1)\!)_j}{(2j)!!}~\frac{(\!(N-1-2(j+i))\!)_{k-j}}{(2(k-j))!!}$$
%	for all $N$ of the form $N = 2n$ and $N=2n-1$. For even $N$, we want to show
%	\begin{align}\label{eq:even}
%	\binom{n}{k} &= \sum_{j=0}^{k} \binom{j+i-1/2}{j}~\binom{n-(j+i)-1/2}{k-j}.
%	\end{align}
%	For odd $N$, we want to show
%	\begin{align}\label{eq:odd}
%	\binom{n-1/2}{k} &= \sum_{j=0}^{k} \binom{j+i-1/2}{j}~\binom{n-(j+i)}{k-j}.
%	\end{align}
%	Applying Theorem~\ref{thm:convolution} with $a=n-k-i+1/2$, $b=i+1/2$, $c=k$, $d=j$ proves (\ref{eq:even}). Applying Theorem~\ref{thm:convolution} with $a=n-k-i$, $b=i+1/2$, $c=k$, $d=j$ proves (\ref{eq:odd}), as desired.
%\end{proof}
%\begin{theorem}\label{thm:bijection22}
%	For any $\lambda \vdash n$, we have
%	\[
%	w_2(\lambda) := \sum_{T \in \mathcal{T}_{\lambda} } w_2(T) = \prod_{j=1}^{\lambda_1} h_\lambda^{(2)}(1,j).
%	\]
%\end{theorem}
%\begin{proof}
%	We proceed by induction on $|\lambda|$. The claim is vacuously true for $|\lambda|=1$. Let $(r,c) \in \lambda$ be the inner corner of $\lambda$ such that $r$ is maximum. Let $\lambda^- \vdash (n-1)$ be the shape obtained from $\lambda$ by removing $(r,c)$. 
%	%	\begin{center}
%	%	\ytableausetup{centertableaux}
%	%	\begin{ytableau}
%	%		~ & ~ &~ & ~ &~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ & ~\\
%	%		~ & ~ &~ & ~ &~ & ~ & ~ & ~ & ~ & ~ & ~ & ~ \\
%	%		~ & ~ &~ & ~ &~ & ~ & ~ & ~ & ~ & ~\\
%	%		~ & ~ &~ & ~ & ~ & ~ & \times & \times \\
%	%	\end{ytableau}
%	%	\end{center}
%	By induction, we have
%	\[
%	\sum_{T \in \mathcal{T}_{\lambda^-} } w_2(T) = \prod_{j=1}^{\lambda_1^-} h_{\lambda^-}^{(2)}(1,j) = (h_\lambda^{(2)}(1,c)-1)\prod_{j \neq c}^{\lambda_1} h_\lambda^{(2)}(1,j).
%	\]
%	Let $\mathcal{T}' := \mathcal{T}_\lambda \setminus \mathcal{T}_{\lambda^-}$ be the transversals of $\lambda$ that contain $(r,c)$. It suffices to show that
%	\[
%	\sum_{T \in \mathcal{T}'}w_2(T) = \prod_{j \neq c}^{\lambda_1} h_\lambda^{(2)}(1,j).
%	\]
%	By our choice of $(r,c)$, the shape induced by the columns of $\lambda$ with index less than $c$ is $(r^{c-1}) \vdash r(c-1)$.
%	Let $\mu$ be the shape obtained from $\lambda$ by deleting its $c$-th column.
%	There are $\binom{c-1}{j}$ ways that a transversal $T \in \mathcal{T}'$ can choose $j$ columns from the $r$-th row of $\mu$. For every such choice, the weight along the $r$-th row is $(2j-1)!!(2j+1)=(2(j+1)-1)!!$ since we must also account for $(r,c) \in T$. Let $h := h_\lambda^{(2)}(1,1)$ and $X := \prod_{l=c+1}^{\lambda_1}h_\lambda^{(2)}(1,l)$. By induction, the remaining weight on the rows $(\mu_1,\mu_2,\ldots,\mu_{r-1})$
%	%applying the induction hypothesis to the shape $(\mu_1,\mu_2,\ldots,\mu_{r-1})$ 
%	is $(\!(h-1-(j+1))\!)_{c-1-j} X$.
%	Summing over all $j$ with $i=1$ in Proposition~\ref{prop:identity2} gives
%	\[
%	(\!(h)\!)_{c-1}X = \sum_{j=0}^{c-1}\binom{c-1}{j}(2(j+1)-1)!~(\!(h-1-(j+1))\!)_{c-1-j}X.
%	\]
%	This gives us 
%	$$\sum_{T \in \mathcal{T}'}w_2(T) = (\!(h)\!)_{c-1} X = \prod_{j \neq c}^{\lambda_1} h_\lambda^{(2)}(1,j),$$ 
%	as desired.
%\end{proof}



%We can deduce an analog of \Cref{thm:sym-spherical}.
%
%\begin{definition} \label{def:abs-decomposition}
%	We denote the orthogonal complement of $V_{\leq d-1}$ inside $V_{\leq d}$ by $V^d$. \textcolor{blue}{Notation isn't optimal.}	
%\end{definition}
%
%\begin{theorem} \label{thm:abs-spherical}
%	If a standard domain is degree-orthogonal then the unique zero-flux representation of a function in $V^d$ is homogeneous of degree~$d$.	
%\end{theorem}
%\begin{proof}
%	By definition, a function in $V^d$ can be represented as a succinct polynomial of degree at most~$d$, and so as a zero-flux polynomial of degree at most~$d$, by \Cref{thm:abs-existence}. By definition, it is orthogonal to all monomials of degree at most~$d-1$, and so the zero-flux polynomial is homogeneous by \Cref{def:abs-degree-orthogonal}.
%\end{proof}
 In the full version of this work we also give bijective combinatorial proofs of $d_\lambda(1)$, $d_\lambda(2)$.

\section{Conclusion and Open Questions}
We determined the canonical presentation of the Specht basis; however, there are other bases that one might argue are better suited for discrete analysis. For example, the well-known \emph{Gelfand--Tsetlin (GZ) basis} is orthogonal whereas the Specht basis is not. The issue here is that the GZ basis is defined inductively, and it is not clear if a ``nice'' combinatorial expression (\textit{e.g.},~\cite{Filmus2016a}) for these vectors exists, which we leave as an open question. 
%
%In the forthcoming full version of this work we present our results in a bit more generality, but one such generalization of $S_n$ that has thwarted our best efforts is the so-called $\mu$-\emph{multislice}, \textit{i.e.}, the permutation module $M^\mu$ obtained by the natural action of $S_n$ on $\mu$-tabloids (note that $\mu = (1)^n$ recovers the left-regular representation of $S_n$). Their multiplicities are given by the Kostka numbers and they are typically not multiplicity-free, which introduces a whole new array of challenges that we leave for future work.

We believe that the matching inclusion matrices are interesting in their own right and may share some of the same desirable properties as the set incidence matrices (see~\cite{Wilson}). For example, computational results show for all $k \leq n = 6$ that the nonzero elementary divisors of $W_{n,k}$ and $W_{n,k}'$ are all equal to 1. Set incidence matrices have played a distinguished role in extremal combinatorics, and it would be interesting to see if the matching inclusion matrices can be leveraged to this avail.

Finally, we note that this work is part of a larger programme to broaden the horizons of discrete analysis to other domains beyond the hypercube and its variants~\cite{Dafni}. In the full version of this work we present our results in more generality to include other domains. Many open questions remain, and we hope these results smooth the way for doing discrete analysis over the space of perfect matchings and other related domains.

\acknowledgements{
%\subsection*{Acknowledgements}
We thank Ryan O’Donnell, Elchanan Mossel and Pavel Etingof for useful discussions.
}

%, \textit{i.e.}, any integral vector in the column (row) space of $W_{n,k}$,$W_{n,k}'$ is a $\mathbb{Z}$-linear combination of its columns (rows). 

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
