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

\usepackage{amscd,etoolbox,ytableau}
%\usepackage{dsfont}


\DeclareSymbolFont{bbold}{U}{bbold}{m}{n}
\DeclareSymbolFontAlphabet{\mathbbb}{bbold}

\newcommand{\matc}[3]{\left[\begin{array}{ccc}#1 \\ #2 \\ #3 \end{array}\right]}
\patchcmd{\bordermatrix}{8.75}{8.75}{}{}
\patchcmd{\bordermatrix}{\left(}{\left[}{}{}
\patchcmd{\bordermatrix}{\right)}{\right]}{}{}
\newcommand{\scprod}[2]{\langle #1,#2\rangle}
\newcommand{\imm}{\mathfrak{S}}
\newcommand{\dimm}{\mathfrak{S}^*}
\newcommand{\detd}{\det\!\downarrow\!}
\newcommand{\nh}{\mathbbb{h}}
\newcommand{\K}{\mathbf{K}}
\newcommand{\Ki}{\mathcal{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\TT}{\mathbb{TT}}
\newcommand{\sumred}{\scalebox{0.8}{$\sum$}}

\DeclareMathOperator{\charge}{charge}
\DeclareMathOperator{\Comp}{Comp}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\NSym}{NSym}
\DeclareMathOperator{\QSym}{QSym}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\wt}{wt}

\newlength{\cellsize}
\cellsize=2.5ex

\newcommand\tableau[1]{%
\vcenter{
\let\\=\cr
\baselineskip=-16000pt
\lineskiplimit=16000pt
\lineskip=0pt
\halign{&\tableaucell{##}\cr#1\crcr}}}

\newcommand{\tableaucell}[1]{{%
\def \arg{#1}\def \void{}%
\ifx \void \arg
\vbox to \cellsize{\vfil \hrule width \cellsize height 0pt}%
\else
\unitlength=\cellsize
\begin{picture}(1,1)
\put(0,0){\makebox(1,1){$#1$}}
\put(0,0){\line(1,0){1}}
\put(0,1){\line(1,0){1}}
\put(0,0){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\end{picture}%
\fi}}


%%%%%%%%%%%%%%%%%%%%%%
\let\oldcprime\cprime
\renewcommand\cprime{\oldcprime\!}

\begin{DefTralics}
\let\oldcprime\cprime
\def\cprime{\oldcprime\!}
\newcommand{\mathbbb}[1]{\textrm{#1}}
\end{DefTralics}
%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%% 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
%%%1
\author{\firstname{Nicholas} \middlename{A.} \lastname{Loehr}}

\address{Virginia Tech\\
Dept. of Mathematics \\
Blacksburg, VA 24061, USA}

\email{nloehr@vt.edu}

%%%2
\author{\firstname{Elizabeth} \lastname{Niese}}

\address{Marshall University\\
Dept. of Mathematics \\
Huntington, WV 25755, USA}

\email{niese@marshall.edu}

\thanks{This work was supported by a grant from the Simons Foundation/SFARI
(\#633564 to Nicholas Loehr).}

%%%%% Sujet

\keywords{Kostka matrix, quasisymmetric functions, noncommutative symmetric
 functions, dual immaculate tableaux, immaculate basis, special rim hook
 tableaux, tournaments}

\subjclass{05E05, 05A19}


%%%%% Gestion

%\DOI{10.5802/alco.193}
%\datereceived{2020-11-07}
%\daterevised{2021-08-10}
%\dateaccepted{2021-08-10}


%%%%% Titre et résumé
\title{Combinatorics of the immaculate inverse Kostka matrix}

\begin{abstract}
The classical Kostka matrix counts semistandard tableaux
and expands Schur symmetric functions in terms of monomial symmetric functions. 
The entries in the inverse Kostka matrix can be computed by various
algebraic and combinatorial formulas involving determinants, special rim
hook tableaux, raising operators, and tournaments. Our goal here is
to develop an analogous combinatorial theory for the inverse of the
immaculate Kostka matrix. The immaculate Kostka matrix enumerates
dual immaculate tableaux and gives a combinatorial definition of
the dual immaculate quasisymmetric functions $\mathfrak{S}^*_{\alpha}$.
We develop several formulas for the entries in the inverse of this matrix
based on suitably generalized raising operators, tournaments, and
special rim-hook tableaux. Our analysis reveals how the combinatorial 
conditions defining dual immaculate tableaux arise naturally from 
algebraic properties of raising operators. We also obtain an elementary
combinatorial proof that the definition of $\mathfrak{S}^*_{\alpha}$ via
dual immaculate tableaux is equivalent to the definition of the immaculate 
noncommutative symmetric functions $\mathfrak{S}_{\alpha}$ via noncommutative 
Jacobi--Trudi determinants. A factorization of raising operators leads
to bases of $\text{NSym}$ interpolating between 
the $\mathfrak{S}$-basis and the $\mathbbb{h}$-basis,
and bases of $\text{QSym}$ interpolating between the 
$\mathfrak{S}^*$-basis and the $M$-basis.
We also give $t$-analogues for most of these results using combinatorial
statistics defined on dual immaculate tableaux and tournaments. 
\end{abstract}


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



\begin{document}



\maketitle

\section{Introduction}
\label{sec:intro}

\subsection{The Kostka Matrix and its Inverse}
\label{subsec:kostka}

\looseness-1
The Kostka matrix and its inverse are central objects in the theory
of symmetric functions. For each positive integer $n$, the Kostka 
matrix $\K_n$ has rows and columns indexed by integer partitions of $n$.
The entry $\K_n(\lambda,\mu)$ in row $\lambda$, column $\mu$, counts
the number of semistandard Young tableaux (SSYT) of shape $\lambda$
and content $\mu$. These are fillings of the cells in the diagram
of $\lambda$ with $\mu_1$ copies of $1$, $\mu_2$ copies of $2$, etc.
such that every row is weakly increasing from left to right 
and every column is strictly increasing from bottom to top. 
Let $\Sym_n$ be the vector space (over any field $F$)
of symmetric functions of degree $n$. Three bases of $\Sym_n$
are the \emph{monomial basis} $(m_{\lambda})$,
the \emph{Schur basis} $(s_{\lambda})$, and
the \emph{complete basis} $(h_{\lambda})$. 
The Kostka matrix and its transpose connect these bases, as follows:
\begin{equation}\label{eq:Kostka-Sym}
s_{\lambda}=\sum_{\mu} \K_n(\lambda,\mu)m_{\mu}; \qquad
h_{\mu}=\sum_{\lambda} \K_n(\lambda,\mu)s_{\lambda}. 
\end{equation}
The sums here range over integer partitions of $n$; we omit
the subscript $n$ in $\K_n$ when it is clear from context.
Here and below, we assume familiarity with standard notation for
partitions and symmetric functions, which can be found in references 
such as~\cite{loehr-comb,macd,sagan}.

If we order integer partitions of $n$ lexicographically, then
the Kostka matrix is upper-triangular with diagonal entries equal to $1$.
Thus we have an \emph{inverse Kostka matrix} $\K^{-1}=\K_n^{-1}$
that provides inverse transition matrices to the ones above:
\begin{equation}\label{eq:invKostka-Sym}
m_{\lambda}=\sum_{\mu} \K^{-1}(\lambda,\mu)s_{\mu}; \qquad
s_{\mu}=\sum_{\lambda} \K^{-1}(\lambda,\mu)h_{\lambda}. 
\end{equation}

\begin{exam}
When $n=4$, there are five integer partitions of $4$, which we
write in abbreviated form as $4$, $31$, $22$, $211$, and $1111$.
The Kostka matrix $\K_4$ and its inverse $\K_4^{-1}$ are shown here:
\[ \K:\bordermatrix{
 ~ & 4 & 31 & 22 & 211 & 1111 \cr
 4 & 1 & 1 & 1 & 1 & 1 \cr
31 & 0 & 1 & 1 & 2 & 3 \cr
22 & 0 & 0 & 1 & 1 & 2 \cr
211& 0 & 0 & 0 & 1 & 3 \cr
1111&0 & 0 & 0 & 0 & 1 \cr}; \qquad
 \K^{-1}:\bordermatrix{
 ~ & 4 & 31 & 22 & 211 & 1111 \cr
 4 & 1 & -1 & 0 & 1 & -1 \cr
31 & 0 & 1 & -1 & -1 & 2 \cr
22 & 0 & 0 & 1 & -1 & 1 \cr
211& 0 & 0 & 0 & 1 & -3 \cr
1111&0 & 0 & 0 & 0 & 1 \cr}. \]
\end{exam}

There is a rich combinatorial theory for the inverse Kostka matrices
in $\Sym$. The following four methods (two algebraic formulas and 
two associated combinatorial models) are available for computing 
the entries $\K^{-1}(\lambda,\mu)$. 

\begin{enumerate}
\item\emph{Jacobi--Trudi Formula.} $\K^{-1}(\lambda,\mu)$ is
 the coefficient of $h_{\lambda}$ when we expand the determinant
 $s_{\mu}=\det[h_{\mu_i+j-i}]$ expressing the Schur function $s_{\mu}$
 as a signed sum of products of complete symmetric functions $h_k$.

\item\emph{Special Rim Hook Tableau Model.}
E\u{g}ecio\u{g}lu and Remmel~\cite{eg-rem} showed that
$\K^{-1}(\lambda,\mu)$ is the sum of the signs of all
special rim hook tableaux (SRHT) of shape $\mu$ and type $\lambda$
(see~\S\ref{subsec:SRHT} for definitions and more details).

\item\emph{Raising Operator Formula.} 
According to Macdonald~\cite[(3.4$''$), pg. 42]{macd},
$\K^{-1}(\lambda,\mu)$ is the coefficient of $h_{\lambda}$ when
we expand $s_{\mu}=\prod_{i<j} (I-R_{i,j})\bullet h_{\mu}$.
Here $I$ is the identity operator and $R_{i,j}$ acts on any
$h_{\beta}$ by incrementing $\beta_i$ and decrementing $\beta_j$,
but there are subtleties (see~\S \ref{subsec:act-on-int} for
a full explanation).

\item\emph{Tournament Model.}
The raising operator formula translates into a combinatorial
model for $\K^{-1}(\lambda,\mu)$ as a signed sum of certain tournaments.
Details appear in~\S \ref{subsec:tourn-invK}.
\end{enumerate}


\subsection{The Immaculate Kostka Matrix}
\label{subsec:immac-kostka}

Our goal in this paper is to extend the combinatorics of the inverse
Kostka matrix from the space $\Sym$ to the spaces $\NSym$ and $\QSym$.
Here $\Sym$ is the self-dual Hopf algebra of symmetric functions,
while $\NSym$ and $\QSym$ are the dual Hopf algebras of
noncommutative symmetric functions and quasisymmetric functions, respectively. 
We will only require the vector space structure of these Hopf algebras,
rather than the full machinery of the product, coproduct, and antipode map.
For more information on $\NSym$ and $\QSym$, see~\cite{GKLLRT, qschur-book}.

A variety of Schur-like bases have been studied in $\NSym$ and $\QSym$,
each of which leads to a possible version of the classical Kostka matrix~\cite{AHM, BBSSZ, GKLLRT,HLMvW}.
We focus on the version arising from the immaculate basis
$(\imm_{\alpha})$ of $\NSym$ and the dual immaculate basis
$(\dimm_{\alpha})$ of $\QSym$, first defined in~\cite{BBSSZ}. These bases, which are indexed by integer 
compositions $\alpha$, can be defined in two equivalent ways. There
is a combinatorial approach based on tableaux, as well as an algebraic 
approach based on the non\-commutative Jacobi--Trudi formula. 

The combinatorial approach needs the following definitions.
A \emph{(strict) composition of $n$ of length $k$} is a list 
$\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_k)$ of $k$ positive integers
with $n=\alpha_1+\alpha_2+\cdots+\alpha_k$. Note that $\alpha_i=0$
is not allowed in a composition. 
Let $\Comp_n$ be the set of all compositions of $n$.
Let $\Comp$ be the set of all compositions.
The \emph{diagram} of a composition
$\alpha$ is an array of boxes, where row $i$ consists of $\alpha_i$ 
left-justified boxes. Our convention is to number the rows from bottom
to top and number the columns from left to right. A \emph{dual immaculate
tableau of shape $\alpha$} is a filling $T$ of the diagram of $\alpha$
with positive integers such that every row is weakly increasing from
left to right, and column 1 (the leftmost column) is strictly increasing
from bottom to top. The
\emph{content of $T$} is the list $(f_1,f_2,\ldots)$ where $f_i$
is the number of times $i$ appears in the filling $T$. 
For each $n$, the \emph{immaculate Kostka matrix}
is the matrix $\Ki_n$ with rows and columns indexed by 
compositions of $n$, such that $\Ki_n(\alpha,\beta)$ is
the number of dual immaculate tableaux of shape $\alpha$ and content $\beta$.
As before, we omit the subscript $n$ when it is clear from context.
Ordering compositions lexicographically, one readily checks that
each matrix $\Ki_n$ is upper-triangular with $1$s on the diagonal,
so $\Ki_n$ is invertible over $\Z$. 

\begin{exam}
For $\alpha = (4,2,3)$ and $\beta = (2,3,2,2)$ the dual immaculate tableaux with shape $\alpha$ and content $\beta$ are:
\begin{equation*}
\tableau{3&4&4\\2&3\\1&1&2&2} \quad \tableau{3&3&4\\2&2\\1&1&2&4} \quad \tableau{3&3&4\\2&4\\1&1&2&2} \quad \tableau{3&4&4\\2&2\\1&1&2&3}\;.
\end{equation*} 
\end{exam}

\begin{exam}
When $n=4$, we compute: 
%{%\footnotesize
\[ 
\scalebox{0.755}{$\Ki:\bordermatrix{
 ~ & 4 & 31 & 22 & 211 & 13 & 121 & 112 & 1111 \cr
 4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \cr
31 & 0 & 1 & 1 & 2 & 1 & 2 & 2 & 3 \cr
22 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 3 \cr
211& 0 & 0 & 0 & 1 & 0 & 1 & 1 & 3 \cr
13 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \cr
121& 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 \cr
112& 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \cr
1111&0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 };\ \ 
\Ki^{-1}:\bordermatrix{
 ~ & 4 & 31 & 22 & 211 & 13 & 121 & 112 & 1111 \cr
 4 & 1 & -1 & 0 & 1 & 0 & 0 & 0 & -1 \cr
31 & 0 & 1 & -1 & -1 & 0 & 1 & 0 & 1 \cr
22 & 0 & 0 & 1 & -1 & -1 & 0 & 0 & 1 \cr
211& 0 & 0 & 0 & 1 & 0 & -1 & 0 & -1 \cr
13 & 0 & 0 & 0 & 0 & 1 & -1 & 0 & 1 \cr
121& 0 & 0 & 0 & 0 & 0 & 1 & -1 & -1 \cr
112& 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \cr
1111& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 }. 
$}\]
%}
\end{exam}

Now let $(M_{\alpha})$ be the monomial basis for $\QSym$,
and let $(\nh_{\alpha})$ be the non\-commutative complete basis for $\NSym$. 
By definition, $(M_{\alpha})$ and $(\nh_{\alpha})$ are dual bases
for $\NSym$ and $\QSym$. This means that there is a bilinear pairing
$\scprod{\cdot}{\cdot}:\QSym\times\NSym\rightarrow F$ (where $F$ is
the field of scalars) such that $\scprod{M_{\alpha}}{\nh_{\beta}}=
\chi(\alpha=\beta)$. Here and below, for any logical statement $P$,
$\chi(P)=1$ if $P$ is true, and $\chi(P)=0$ if $P$ is false.

By analogy with~\eqref{eq:Kostka-Sym}, we define:
\begin{equation}\label{eq:Kostka-QSym}
\dimm_{\alpha}=\sum_{\beta} \Ki(\alpha,\beta)M_{\beta}; \qquad
 \nh_{\beta} =\sum_{\alpha}\Ki(\alpha,\beta)\imm_{\alpha}. 
\end{equation}
These formulas explicitly define the \emph{dual immaculate functions}
$\dimm_{\alpha}$ in $\QSym$ and implicitly define the 
\emph{immaculate functions} $\imm_{\alpha}$ in $\NSym$.
Multiplying by the inverse immaculate Kostka matrix, 
this definition is equivalent to:
\begin{equation}\label{eq:invKostka-QSym}
M_{\alpha}=\sum_{\beta} \Ki^{-1}(\alpha,\beta)\dimm_{\beta}; \qquad
\imm_{\beta} =\sum_{\alpha}\Ki^{-1}(\alpha,\beta)\nh_{\alpha}. 
\end{equation}
Another equivalent version of these formulas is to define
$\dimm_{\alpha}$ by the $M$-expansion in~\eqref{eq:Kostka-QSym}
and then declare that $\imm_{\alpha}$ is the unique dual basis of $\NSym$, 
meaning that $\scprod{\dimm_{\alpha}}{\imm_{\beta}}=\chi(\alpha=\beta)$
for all compositions $\alpha,\beta$.

\goodbreak
\subsection{The NonCommutative Jacobi--Trudi Formula}
\label{subsec:nc-Jacobi-Trudi}

\looseness-1
The algebraic approach to defining $\imm_{\alpha}$ and $\dimm_{\alpha}$
goes in the opposite direction.
First we define $\imm_{\beta}$ by a non\-commutative version of the
Jacobi--Trudi formula. Given any $m\times m$ matrix $A$ with entries
in a (possibly noncommutative) ring, 
let the \emph{top-to-bottom determinant} of $A$ be 
\begin{equation}\label{eq:def-detd}
 \detd(A)=\sum_{w\in S_m} \sgn(w)A(1,w(1))A(2,w(2))\cdots A(m,w(m)). 
\end{equation}
Here $S_m$ is the set of permutations of $\{1,2,\ldots,m\}$, and we
multiply the chosen entries of $A$ in order working from row $1$
down to row $m$. For any composition
$\beta=(\beta_1,\ldots,\beta_m)$, we define
\begin{equation}\label{eq:imm-JT}
 \imm_{\beta}=\detd[\nh_{\beta_i+j-i}]_{m\times m}
 =\sum_{w\in S_m} \sgn(w)\nh_{(\beta_1+w(1)-1,\beta_2+w(2)-2,
 \ldots,\beta_m+w(m)-m)}, 
\end{equation}
where $\nh_0=1$ and $\nh_k=0$ for $k<0$.
Then we declare that $(\dimm_{\beta})$ is the unique basis 
of $\QSym$ dual to the basis $(\imm_{\beta})$ of $\NSym$.

\begin{exam}
For $\beta=(3,4,1)$, we compute
\[ \imm_{341} =\detd\left[\begin{array}{ccc}
 \nh_3 & \nh_4 & \nh_5 \\
 \nh_3 & \nh_4 & \nh_5 \\
 0 & \nh_0 & \nh_1 \end{array}\right]
 = \nh_{341}+\nh_{53}-\nh_{35}-\nh_{431}. \] 
Due to noncommutativity, the answer is not zero even though
the determinant has two equal rows.
\end{exam}

To see that this approach is equivalent to the combinatorial approach,
one must check that the $\nh$-expansion of $\imm_{\beta}$
(as given by the Jacobi--Trudi formula) really does agree with
the expansion in~\eqref{eq:Kostka-QSym} obtained by inverting
the matrix of dual immaculate tableau counts. 
The equivalence of the two definitions is known but non-trivial; 
we give a combinatorial proof of this fact later (Theorem~\ref{thm:Kinv-JT}).
We take the combinatorial formulas~\eqref{eq:Kostka-QSym} 
and~\eqref{eq:invKostka-QSym} as the definition of $(\imm_{\alpha})$ 
and $(\dimm_{\alpha})$ to be used here.

\subsection{Overview of Results}
\label{subsec:our-results}

Section~\ref{sec:inv-kostka-operators} defines raising operators
$R_{i,j}$ on various abstract vector spaces and examines algebraic properties
of the inverse Kostka operators $\prod_{i<j}(I-R_{i,j})$ on each space.
Section~\ref{sec:comb-invk} develops combinatorial algorithms for computing
these operators and their inverses based on manipulations of filled diagrams.
Analysis of these algorithms leads naturally to expressions involving
dual immaculate tableaux (Theorem~\ref{thm:Uinv}) and analogous fillings
of diagrams where rows of length zero may occur (Theorem~\ref{thm:Tinv}).
Applying raising operators in stages leads to bases of $\NSym$ interpolating
between the $\imm$-basis and the $\nh$-basis, and dual bases of $\QSym$
interpolating between the $\dimm$-basis and the $M$-basis
(\S \ref{subsec:interp-bases}).

Section~\ref{sec:tourn-etc} develops combinatorial models for the entries in
the inverse of the dual immaculate Kostka matrix. We provide formulas
involving tournaments (Theorem~\ref{thm:Kinv-tourn}), 
transitive tournaments (Theorem~\ref{thm:Kinv-trans}), 
noncommutative determinants (Theorem~\ref{thm:Kinv-JT}),
recursions (Theorem~\ref{thm:detd-rec}), and 
special rim hook tableaux (Theorem~\ref{thm:SRHT-QSym}).

Section~\ref{sec:t-analogue} defines $t$-analogues of inverse Kostka operators,
dual immaculate tableaux, tournaments, and the associated bases of $\NSym$ 
and $\QSym$. These $t$-analogues can be viewed as noncommutative and 
quasisymmetric versions of the Hall--Littlewood polynomials, of which there 
are several in the literature already~\cite{BBSSZ, HLMvW, Hivert}. 

\goodbreak

\section{Algebraic Development of Inverse Kostka Operators}
\label{sec:inv-kostka-operators}

In this section, we study the algebraic properties
of \emph{inverse Kostka operators} \hbox{$\prod_{i<j} (I-R_{i,j})$} acting
on various abstract vector spaces. Later we specialize these results to obtain
information about transition matrices in $\QSym$, $\NSym$, and $\Sym$.
Throughout this discussion we fix a positive integer $m$ and a field $F$.
All vector spaces use scalars coming from $F$ (the theory also
works for free $\Z$-modules). $I$ denotes the identity map
on the vector space currently being considered. We set $[m]=\{1,2,\ldots,m\}$.

\subsection{Action on Lists of Integers}
\label{subsec:act-on-int}

Let $\Z^m$ be the set of all ordered lists $[a_1,\ldots,a_m]$
with each $a_i\in\Z$. 
Let $V_0$ be the vector space having $\Z^m$ as a basis.
Thus, by definition, every $v\in V_0$ is a finite formal linear
combination of $m$-element lists of integers. For distinct $i,j\in [m]$,
define the \emph{raising operator} $R_{i,j}:V_0\rightarrow V_0$ to
be the linear map on $V_0$ that acts on basis vectors via
\[ R_{i,j}([a_1,\ldots,a_i,\ldots,a_j,\ldots,a_m])
 =[a_1,\ldots,a_i+1,\ldots,a_j-1,\ldots,a_m]. \]
For example, $R_{1,3}(-2[3,1,5]+5[2,-3,0])=-2[4,1,4]+5[3,-3,-1]$.

In the $F$-algebra of all linear operators on $V_0$,
all these raising operators commute and obey
the associative and distributive laws. We can now give
a rigorous explanation of the raising operator formula
stated in~\S \ref{subsec:kostka}.
Given a partition $\mu=[\mu_1,\ldots,\mu_m]$ with $m$ parts,
first apply the operator $\prod_{1\leq i<j\leq m} (I-R_{i,j})$
to $[\mu_1,\ldots,\mu_m]\in V_0$ to obtain some linear combination
of $m$-element lists. Then apply the evaluation map $E:V_0\rightarrow\Sym$
that sends each list $\alpha=[\alpha_1,\ldots,\alpha_m]$ to 
$h_{\alpha}=h_{\alpha_1}\cdots h_{\alpha_m}$ (where $h_0=1$ and $h_k=0$ 
for $k<0$, and the $h_k$'s commute). The resulting symmetric
function is known to be the Schur function $s_{\mu}$~\cite[pg. 42]{macd}.
 
Trying to analyze $\prod_{i<j} (I-R_{i,j})$ in $V_0$
is problematic, however, for the following reason.
Although each $R_{i,j}$ is invertible (clearly $R_{i,j}^{-1}=R_{j,i}$), 
the operators $I-R_{i,j}:V_0\rightarrow V_0$ are \emph{not} invertible.
For example, taking $m=2$, we claim that no $v\in V_0$ solves
$(I-R_{1,2})(v)=[0,0]$. Comparing coefficients of basis vectors
on both sides of this equation, we see that any solution $v$ 
must include all terms of the form
$\sum_{k=-\infty}^{-1} c[k,-k]+\sum_{k=0}^{\infty} (c+1)[k,-k]$
for some $c\in F$. But whatever we choose for $c$, this expression is not
a \emph{finite} linear combination of basis vectors. So there
is no solution in the space $V_0$.

\subsection{Action on Lists of Nonnegative Integers}
\label{subsec:act-on-nonneg}

To address the non-invertibility of $I-R_{i,j}$, we pass to
a smaller vector space. Let $\Z_{\geq 0}^m$ be the set of all ordered lists 
$[a_1,\ldots,a_m]$ where each $a_i$ is a nonnegative integer.
We sometimes omit commas from such a list if no confusion is likely. 
Let $V$ be the vector space with basis $\Z_{\geq 0}^m$.
For distinct $i,j\in [m]$, define the raising operator $R_{i,j}:V\rightarrow V$
to be the linear map acting on basis vectors via
\[ R_{i,j}([a_1,\ldots,a_i,\ldots,a_j,\ldots,a_m])
 =\begin{cases}
[a_1,\ldots,a_i+1,\ldots,a_j-1,\ldots,a_m] & \mbox{ if $a_j>0$; } \\
0 & \mbox{ if $a_j=0$. } \end{cases} \]
Intuitively, if the old raising operator produces a list with 
a negative entry, that list is discarded from the answer.
For example, $R_{1,3}(-2[3,1,5]+5[2,3,0])=-2[4,1,4]$.

These raising operators (like any linear maps on a vector space)
still obey the associative and distributive laws, but \emph{they
no longer commute} in general. For example,
\[ R_{1,2}\circ R_{2,3}([3,0,1])=R_{1,2}([3,1,0])=[4,0,0],\mbox{ but }
 R_{2,3}\circ R_{1,2}([3,0,1])=R_{2,3}(0)=0. \]
However, if $i,j,a,b$ are four distinct indices, then
$R_{i,j}$ does commute with $R_{a,b}$. Similarly, 
for a fixed index $j$, the operators $R_{1,j}$, $R_{2,j}$, $\ldots$,
$R_{j-1,j}$ all commute. This is because $R_{i,j}\circ R_{k,j}$
sends a basis vector $[a_1,\ldots,a_m]$ to zero iff $a_j\leq 1$
iff $R_{k,j}\circ R_{i,j}$ sends $[a_1,\ldots,a_m]$ to zero.
We also have the following restricted version of commutativity.
Suppose $R_{i_1,j_1},\ldots,R_{i_s,j_s}$ are given raising operators
and $[a_1,\ldots,a_m]$ is an input such that for all $j\in [m]$,
the number of occurrences of $j$ in $j_1,\ldots,j_s$ is at most $a_j$.
Then applying these raising operators to input $[a_1,\ldots,a_m]$,
in any order, produces the same output. This holds since the exceptional
case where a basis vector is sent to zero never applies. 
More specifically, the output here is $[b_1,\ldots,b_m]$, where 
$b_k=a_k+\sum_{r=1}^s \chi(i_r=k)-\sum_{r=1}^s \chi(j_r=k)$ for $k\in [m]$.
This formula is unchanged by reordering the given raising operators.

Due to noncommutativity, we must take care in defining 
what $\prod_{i<j} (I-R_{i,j})$ means. For each fixed $j$
between $2$ and $m$, define a linear map $T_j:V\rightarrow V$ by
\[ T_j=(I-R_{1,j})\circ (I-R_{2,j})\circ\cdots\circ (I-R_{j-1,j})
 =\prod_{i=1}^{j-1} (I-R_{i,j}). \]
For definiteness we compose the factors $I-R_{i,j}$ in the indicated 
order, although these factors do commute. Next, we define the
\emph{inverse Kostka operator on $V$} to be
\[ T=T_2\circ T_3\circ\cdots\circ T_m=\prod_{j=2}^m T_j. \]
So $T_m$ acts first on an input vector, then $T_{m-1}$, etc. ending with $T_2$.
We use this order to ensure that we get the expected answer for $\Sym$
when working in $V$ rather than $V_0$ (see the discussion
below~\eqref{eq:tourn-in-V} in~\S \ref{subsec:tourn-invK}).

Acting on $V$, it is no longer true that $R_{i,j}^{-1}=R_{j,i}$.
In fact, each $R_{i,j}$ is a \emph{locally nilpotent} linear operator on $V$.
This means that for each $v\in V$, there exists a positive integer $N$
(depending on $v$) such that $R_{i,j}^N(v)=0$. More specifically, starting
with the basis vector $[a_1,\ldots,a_j,\ldots,a_m]$ and applying $R_{i,j}$
repeatedly, we obtain zero after $N=a_j+1$ steps. 

The local nilpotence makes it easy to invert $I-R_{i,j}$ using the
formal geometric series formula. Specifically,
\[ (I-R_{i,j})^{-1}=I+R_{i,j}+R_{i,j}^2+\cdots+R_{i,j}^N+\cdots
 =\sum_{e=0}^{\infty} R_{i,j}^e. \]
The sum on the right side has only finitely many nonzero terms when
applied to any specific input vector $v$. We could also fix $n$ and restrict 
attention to the subspace spanned by lists $[a_1,\ldots,a_m]$ with
$a_1+\cdots+a_m=n$. On this subspace, $R_{i,j}$ is nilpotent of index 
$n+1$, and $(I-R_{i,j})^{-1}=\sum_{e=0}^{n} R_{i,j}^e$.
For example, 
\[ (I-R_{1,3})^{-1}([2,1,3])=[213]+[312]+[411]+[510]. \]

It is now routine to invert the full inverse Kostka operator on $V$.
For fixed $j$, we have
$T_j^{-1}=(I-R_{j-1,j})^{-1}\circ\cdots\circ (I-R_{1,j})^{-1}$.
Then $T^{-1}=T_m^{-1}\circ\cdots\circ T_3^{-1}\circ T_2^{-1}$.
Expanding this with the distributive law, we see that $T^{-1}$ is the
sum of all terms of the form
\[ R_{m-1,m}^{e_{m-1,m}}\cdots R_{1,m}^{e_{1,m}}R_{m-2,m-1}^{e_{m-2,m-1}}
 \cdots R_{1,m-1}^{e_{1,m-1}}\cdots
 R_{2,3}^{e_{2,3}} R_{1,3}^{e_{1,3}} R_{1,2}^{e_{1,2}}, \]
where each $e_{i,j}$ is a nonnegative integer.

\subsection{Action on Compositions}
\label{subsec:act-on-comp}
 
Let $W$ be the subspace of $V$ spanned by basis vectors 
$[a_1,a_2,\ldots,a_m]$ where all zero parts (if any) occur at the end.
More formally, this means that if $a_i=0$ then $a_{i+1},\ldots,a_m$
must also be zero. By dropping any zero parts at the end, 
these lists correspond to (strict) compositions with at most $m$ parts.
Later we will identify the abstract basis vectors $[a_1,\ldots,a_m]$
with particular basis elements of $\QSym$ and $\NSym$.

The operators $T$ and $T_j$ on $V$ do not always send inputs from $W$
to outputs in $W$. To resolve this difficulty, we introduce a linear
projection map $P:V\rightarrow W$ that acts on basis vectors by moving
any zero parts to the right end. For example, $P([2,0,3,0,1,0])=[2,3,1,0,0,0]$
and $P([2,4,1,3,0,0])=[2,4,1,3,0,0]$. We say that $P$ acts on a list by
\emph{packing} the nonzero parts of its input on the left end.
We now define our \emph{inverse Kostka operator on the space $W$} by letting 
$U=P\circ (T|_W)$, where $T|_W:W\rightarrow V$ is the restriction of
the operator $T$ to the domain $W$. We similarly define
$U_j=P\circ (T_j|_W)$ for $j=2,\ldots,m$ and
$U_{i,j}=P\circ (I-R_{i,j})|_W$ for distinct $i,j\in [m]$.

Since $T_j=\prod_{i=1}^{j-1} (I-R_{i,j})$, one might expect
 that $U_j=\prod_{i=1}^{j-1} U_{i,j}$. However, the following example
shows this is \emph{not} true in general. On one hand,
applying $U_3=P\circ (I-R_{1,3})\circ (I-R_{2,3})$ to $[1,1,1,1]$ gives
$P([1111]-[2101]-[1201]) =[1111]-[2110]-[1210]$.
On the other hand,
$U_{2,3}([1,1,1,1]) =P\circ (I-R_{2,3})([1111]) =[1111]-[1210]$, 
so
$U_{1,3}(U_{2,3}([1,1,1,1])) =[1111]-[2110]-[1210]+[2200]$. 
Thus, $U_3\neq U_{1,3}\circ U_{2,3}$.

The example shows that we cannot indiscriminately insert new $P$'s 
in the product of $I-R_{i,j}$'s defining $U$. But there are certain
locations where $P$'s may be inserted safely. Specifically, we show
later (Lemma~\ref{lem:U-facz}) that 
$P\circ\prod_{j=2}^m T_j=\prod_{j=2}^m P\circ T_j$
when acting on vectors in $W$, 
so that $U=U_2\circ U_3\circ\cdots \circ U_m$ holds. 
This fact allows us to invert $U$ in $m-1$ stages, writing
$U^{-1}=U_m^{-1}\circ\cdots\circ U_3^{-1}\circ U_2^{-1}$.
However, we no longer have simple formulas for $U_j^{-1}$ 
based on the geometric series, due to the presence
of the non-invertible projection map $P$. The next section shows
how to invert each $U_j$ and $U$ itself using combinatorial models
for these operators and their inverses.

\section{Combinatorics of Inverse Kostka Operators}
\label{sec:comb-invk}

This section gives combinatorial models for the action of the
operators $T_j$, $U_j$, $T_j^{-1}$, $U_j^{-1}$, $T^{-1}$, $U^{-1}$,
$T$, and $U$ on basis vectors of $V$ and $W$. We visualize
a basis vector $[a_1,\ldots,a_m]$ of $V$ by a \emph{generalized
composition diagram} that has $a_i$ left-justified boxes in
row $i$ from the bottom. Working in $V$, we allow some rows
to have zero boxes; but for basis vectors in $W$, all such
rows must occur at the top of the figure.

\subsection{Combinatorial Action of \texorpdfstring{$T_j$}{Tj} and \texorpdfstring{$U_j$}{Uj}}
\label{subsec:comb-Tj-Uj}

Fix $j$ between $2$ and $m$.
We begin with a model for $T_j=\prod_{i=1}^{j-1} (I-R_{i,j})$
acting on input $v=[a_1,\ldots,a_m]\in V$. We create a signed linear
combination of diagrams by making the following choices in all
possible ways and adding the results. Start with the diagram of $v$
with coefficient $+1$. First, to model $I-R_{j-1,j}$, either leave the 
diagram unchanged or move one box from row $j$ to row $j-1$ and change 
the sign. Second, either leave the diagram unchanged
or move one box from row $j$ to row $j-2$ with a sign change. Continue until 
the choice for $I-R_{1,j}$, where we either leave the diagram unchanged or
move one box from row $j$ to row $1$ and change the sign. During this 
process, if all boxes in row $j$ are moved,
then we must choose $I$ (leave the diagram unchanged)
from that point on. 

The algorithm for $T_j$ can be described more concisely, as follows.
Starting with the diagram of $v=[a_1,\ldots,a_m]$, decrease $a_j$
by some amount $d$ with $0\leq d\leq a_j$, and increment $d$ \emph{distinct}
entries in the first $j-1$ positions of $v$. Use the coefficient
$(-1)^d$ for this list, and add up all the lists that can be made 
from $v$ in this way.

\looseness-1
The action of $U_j=P\circ (T_j|_W)$ is similar, but there are two modifications.
First, $U_j$ is only allowed to act on (linear combinations of)
basis vectors in $W$. So any input $v=[a_1,\ldots,a_m]$ to $U_j$
must have all zero parts at the right end. Second, for any output list 
$w=\pm [b_1,\ldots,b_m]$ produced by the algorithm for $T_j$, we must replace 
this list by its packed version $P(w)$. Now $v$ is already packed, and
the choice process creating $w$ from $v$ can only create a new zero 
in position $j$. Therefore, we have 
$P(w)=\pm [b_1,\ldots,b_{j-1},b_{j+1},\ldots,b_m,0]$ 
when $b_j=0$ and $P(w)=w$ when $b_j>0$.
In terms of diagrams, when we make choices that move all $a_j$ cells
from row $j$ down to lower rows, the part of the diagram above row $j$
\emph{falls} into the empty row $j$ at the end.

\begin{exam}\label{ex:T3-U3}
Given $v=[1,4,2,3,1]$, we compute $T_3(v)$ and $U_3(v)$ by acting on diagrams.
We have $T_3(v)=[14231]-[24131]-[15131]+[25031]$ 
 and $U_3(v)=[14231]-[24131]-[15131]+[25310]$.
The diagrams for $v$ and $U_3(v)$ are shown below. We place a minus sign in
each cell moved by an $R_{i,j}$ operator to keep track of the sign.
\[
\tableau{ 
{} \\
{}&{}&{} \\
{}&{} \\
{}&{}&{}&{} \\
{} } 
\quad\stackrel{U_3}{\longrightarrow}\quad
\tableau{ 
{} \\
{}&{}&{} \\
{}&{} \\
{}&{}&{}&{} \\
{} } 
\quad
\tableau{ 
{} \\
{}&{}&{} \\
{} \\
{}&{}&{}&{} \\
{}& - } 
\quad
\tableau{ 
{} \\
{}&{}&{} \\
{} \\
{}&{}&{}&{}& - \\
{} } 
\quad
\tableau{ 
 \\
{} \\
{}&{}&{} \\
{}&{}&{}&{}& - \\
{}& - } 
\] 
\end{exam}

\subsection{Combinatorial Action of \texorpdfstring{$T_j^{-1}$}{Tj-1} and \texorpdfstring{$U_j^{-1}$}{Uj-1}}
\label{subsec:comb-Tjinv-Ujinv}

Recall that the inverse of $T_j=\prod_{i=1}^{j-1} (I-R_{i,j})$
is given algebraically by the geometric series formula
\begin{equation}\label{eq:invert-Tj}
 T_j^{-1}=\sum_{e_1\geq 0}\sum_{e_2\geq 0}\cdots\sum_{e_{j-1}\geq 0}
 R_{j-1,j}^{e_{j-1}}\circ \cdots\circ R_{2,j}^{e_2}\circ R_{1,j}^{e_1}. 
\end{equation}
Given a basis vector $v=[a_1,\ldots,a_m]\in V$, we can compute
$T_j^{-1}(v)$ by acting on diagrams as follows. Do the following
steps in all possible ways and add the results. Starting with
the diagram of $[a_1,\ldots,a_m]$, choose nonnegative integers 
$e_1,\ldots,e_{j-1}$ with sum at most $a_j$. For $i=1,2,\ldots,j-1$
in turn, move $e_i$ boxes from row $j$ to row $i$. We mark each
moved box with a $+$ symbol, noting that there are no negative signs
in the formula for $T_j^{-1}$. 

Now we introduce a combinatorial operator $U_j'$ on $W$ that will turn out
to be $U_j^{-1}$. Start with the diagram of a packed basis vector 
$v=[a_1,\ldots,a_m]\in W$. As before, choose $e_1,\ldots,e_{j-1}$ with
sum at most $a_j$ and move $e_i$ boxes from row $j$ to row $i$ for 
each $i<j$. If there are still boxes left in row $j$, then we stop
here and record the resulting object. However, for choices of $e_i$
where $e_1+\cdots+e_{j-1}=a_j$, row $j$ becomes empty and the higher
rows fall down (as happened with $U_j$). When this occurs, we continue
the process, choosing $e_1',\ldots,e_{j-1}'$ with sum at most $a_{j+1}$
(the number of boxes now in row $j$). We again move $e_i'$ boxes
from row $j$ to row $i$ for each $i<j$. If $e_1'+\cdots+e_{j-1}'<a_{j+1}$,
then we stop and record the resulting object. Otherwise, the rows above
row $j$ fall again and we continue recursively. This process
must terminate after finitely many steps, since eventually we run
out of boxes above row $j$.

\begin{exam}\label{ex:T3i-U2i}
We have $T_3^{-1}([3,1,2,1])=[3121]+[4111]+[3211]+[5101]+[3301]+[4201]$.
Using the following diagrams, we find
$U_2'([1,1,2,1])=[1121]+[2210]+[3110]+[4100]+[5000]$.
\[ 
\tableau{
{}\\
{}&{}\\
{}\\
{} } 
\quad\stackrel{U_2'}{\longrightarrow}\quad
\tableau{
{}\\
{}&{}\\
{}\\
{} } \quad
\tableau{
\\
{}\\
{}&{}\\
{}&{+} } \quad
\tableau{
\\
{}\\
{}\\
{}&{+}&{+} } \quad
\tableau{
\\
\\
{}\\
{}&{+}&{+}&{+} } \quad
\tableau{ 
\\
\\
\\
{}&{+}&{+}&{+}&{+} } \] 
\hrule height0pt width0pt
\end{exam}

\subsection{Proof of Inverse Property for \texorpdfstring{$U_j$}{Uj}}
\label{subsec:inverse-Uj}

\begin{theorem}\label{thm:invert-Uj}
\looseness-1
For $2\leq j\leq m$,
the operator $U_j':W\rightarrow W$ is the inverse of $U_j:W\rightarrow W$.
\end{theorem}
\begin{proof}
It suffices to prove that $U_j'\circ U_j=I$ (the identity map on $W$). 
The other identity $U_j\circ U_j'=I$ follows automatically
because for each $n$ and $m$, $U_j$ and $U_j'$ restrict to linear maps
on the \emph{finite-dimensional} subspaces of $W$ spanned by composition
diagrams with $n$ boxes and $m$ rows.

When we act on diagrams by a sequence of operators, it is helpful to
annotate the diagrams by filling each box with its row number in the
original input diagram. A box that moves down due to a $-R_{i,j}$ term
retains its number along with a minus sign (drawn above the number
to save space). Other boxes that move or fall down keep their number 
with no sign. The next example illustrates
this annotation process for the operator sequence $U_3'\circ U_3$.

\begin{exam}\label{ex:U3'U3}
We compute $U_3'(U_3([2311]))$ by drawing annotated diagrams.
First we find  $U_3([2311]) =[2311]-[3310]-[2410]$ as shown here:
\[
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
4\\
3\\
2 & 2 & 2 \\
1 & 1 
\end{ytableau}
\quad
\stackrel{U_3}{\longrightarrow}\quad
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
4\\
3\\
2 & 2 & 2 \\
1 & 1 
\end{ytableau}
 \quad
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
4\\
2 & 2 & 2 \\
1 & 1 & \overline{3} 
\end{ytableau}
 \quad
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
4\\
2 & 2 & 2 & \overline{3} \\
1 & 1
\end{ytableau} \;.
\]


To continue, we find $U_3'(U_3([2311]))=U_3'([2311])-U_3'([3310])
 -U_3'([2410])$ by applying $U_3'$ to each of the three intermediate
diagrams produced in the previous step. The seven positive diagrams for 
$U_3'([2311])$ are shown here: 
\[
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
4\\
3\\
2 & 2 & 2 \\
1 & 1 
\end{ytableau}
 \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
4\\
2 & 2 & 2 \\
1 & 1 & 3 
\end{ytableau}
 \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
\none\\
2 & 2 & 2 \\
1 & 1 & 3 & 4 
\end{ytableau}
 \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
\none\\
2 & 2 & 2 & 4\\
1 & 1 & 3 
\end{ytableau}
 \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
4\\
2 & 2 & 2 & 3 \\
1 & 1 
\end{ytableau}
 \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
\none\\
2 & 2 & 2 & 3 \\
1 & 1 & 4 
\end{ytableau}
 \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
\none\\
2 & 2 & 2 & 3 & 4 \\
1 & 1 
\end{ytableau}
 \;.
\] 
The six negative diagrams for $-U_3'([3310])-U_3'([2410])$ are 
shown here:
\[
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
4\\
2 & 2 & 2 \\
1 & 1 & \overline{3} 
\end{ytableau}
 \ \ \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
2 & 2 & 2 \\
1 & 1 & \overline{3} & 4
\end{ytableau}
 \ \ \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
2 & 2 & 2 & 4 \\
1 & 1 & \overline{3} 
\end{ytableau}
 \qquad\quad
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
4\\
2 & 2 & 2 & \overline{3} \\
1 & 1 
\end{ytableau}
 \ \ \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
2 & 2 & 2 & \overline{3} \\
1 & 1 & 4 
\end{ytableau}
 \ \ \ 
\ytableausetup{centertableaux,boxsize=1.2em}
\begin{ytableau}
\none\\
2 & 2 & 2 & \overline{3} & 4 \\
1 & 1 
\end{ytableau}
 \;.
\]
Noting the cancellation of terms with the same shape but opposite
signs, the final answer is $U_3'(U_3([2311]))=[2311]=I([2311])$. 
\end{exam}

We now prove that the cancellation seen in the example holds in general.
Fix $j>1$. To prove $U_j'\circ U_j=I$, it suffices to show that
$U_j'(U_j(w))=w$ for all basis vectors $w=[a_1,\ldots,a_m]$ of $W$.
We show this by introducing a sign-reversing,
shape-preserving involution on the set of annotated diagrams
that appear in the calculation of $U_j'(U_j(w))$.
Observe the following property of such diagrams: each row $i<j$
contains (among other things) at most one box labeled $-j$,
followed by zero or more boxes labeled $j$. 

Given such a diagram $z$, find the least row index $i<j$ such that
a box with $-j$ or $j$ occurs in that row. If there is no
such $i$, then neither $U_j$ nor $U_j'$ moved any boxes down,
so we must have $z=w$. This diagram (which is positive) is the unique 
fixed point of the involution, corresponding to the output term $w$.

When $i$ does exist, the involution acts as follows. If there is
a $-j$ in row $i$, change it to $j$. If there is no $-j$ in row $i$,
change the first $j$ in row $i$ to $-j$. One sees immediately
that the new object is another valid annotated diagram arising
in the computation of $U_j'(U_j(w))$ with opposite sign as $z$. 
It is also clear that performing this action twice restores 
the original object $z$, so we do have an involution. Thus all output
objects except $w$ itself cancel, as needed. The previous example
illustrates this involution. The first object in row $1$ is the fixed
point $[2311]$, and the remaining objects in row $1$ match (in order)
with the corresponding objects in row $2$. 
\end{proof}

The identity $T_j^{-1}\circ T_j=I$ can be given a similar combinatorial
proof (which we omit). Here the situation is simpler, since rows do not 
fall and there is no recursive continuation of the motion process 
in $T_j^{-1}$.

\subsection{Tableau Description of the Kostka Operator \texorpdfstring{$T^{-1}$}{T-1}}
\label{subsec:comb-Tinv}

Next we use annotated diagrams to give a combinatorial formula
for $T^{-1}$ (the \emph{Kostka operator} on $V$) 
in terms of tableau-like structures. 
For a filled generalized composition diagram $D$,
the \emph{shape} of $D$ (denoted $\sh(D)$) is the list
of $m$ row lengths of $D$. The \emph{content} of $D$ is the
list $(f_1,f_2,\ldots,f_m)$, where $f_i$ is the number of occurrences
of $i$ in $D$.
Recall $T=T_2T_3\cdots T_m$ and $T^{-1}=T_m^{-1}\cdots T_3^{-1}T_2^{-1}$.
Therefore, we can compute the action of $T^{-1}$ on a basis
vector $v=[a_1,\ldots,a_m]\in V$ as follows. Start with the annotated
diagram for $v$, which has $a_j$ boxes labeled $j$ in each row $j$
(rows of length zero may occur). 
Generate a collection of filled diagrams by executing the following loop
and making all possible box motions. For $j=2,3,\ldots,m$ in this order,
move any number of boxes down from row $j$ to the end of lower rows,
keeping the labels in each box. Then $T^{-1}(v)$ is the 
sum of the shapes of all filled diagrams generated in this way.

\begin{exam} 
Let $v=[2,1,2]$. 
Using the annotated diagrams shown below, we compute
\[
T^{-1}(v)= [212]+2[311]+[221]+2[410]+2[320]+[230]+[302]+[401]+[500].
\]
The first diagram arises by moving no boxes when $j=2$ and no boxes when
$j=3$. The second diagram (of shape $[311]$) arises by moving no boxes 
when $j=2$ and moving one box from row $3$ to row $1$ when $j=3$. 
We see this same shape in the ninth diagram, which arises by moving
a box from row $2$ to row $1$ when $j=2$ and moving a box from row $3$
to row $2$ when $j=3$. This explains why $[311]$ has coefficient $2$
in $T^{-1}(v)$.
\[
\tableau{3&3\\2\\1&1} \quad
\tableau{3\\2\\1&1&3} \quad
\tableau{3\\2&3\\1&1} \quad
\tableau{\\2\\1&1&3&3} \quad
\tableau{\\2&3\\1&1&3}\quad
\tableau{\\2&3&3\\1&1} \]
\[ \tableau{3&3\\\\1&1&2}\quad
\tableau{3\\\\1&1&2&3}\quad
\tableau{3\\3\\1&1&2} \quad
\tableau{\\\\1&1&2&3&3}\quad
\tableau{\\3\\1&1&2&3} \quad
\tableau{\\3&3\\1&1&2} \]
\end{exam}

The next theorem characterizes the filled diagrams that occur
when we compute $T^{-1}(v)$.

\begin{theorem}\label{thm:Tinv}
For any basis vector $v=[a_1,\ldots,a_m]$ of $V$,
$T^{-1}(v)=\sum_D \sh(D)$, where we sum over all filled diagrams $D$
with these properties:
\begin{enumerate}[label=(\alph*)]
%(a)
\item\label{theo3.6_a}~all rows of $D$ are weakly increasing;
%(b)
\item\label{theo3.6_b}~$D$ has content $v$;
%(c)
\item\label{theo3.6_c}~each copy of $j$ in $D$ appears in some row $i\leq j$. 
\end{enumerate}
\end{theorem}
\begin{proof}
First suppose $D$ is one of the filled diagrams generated by the algorithm
for computing $T^{-1}(v)$. The initial diagram for $v$ has content $v$, 
and the motion rules do not change the content, so~\ref{theo3.6_b}~holds. Since
occurrences of $j$ are moved to the end of lower rows in increasing
order of $j$, \ref{theo3.6_a}~holds. Since each copy of $j$ begins in row $j$
and optionally moves down to lower rows, \ref{theo3.6_c}~holds.

To finish the proof, we must show that any filled diagram $D$ with properties~\ref{theo3.6_a}, \ref{theo3.6_b}, \ref{theo3.6_c}~is produced in exactly one way by the algorithm
computing $T^{-1}(v)$. Given such a diagram $D$, we can produce $D$ from 
the original filled diagram for $v$ by the following choices.
For $j=2,3,\ldots,m$ in order,
move some of the $a_j$ copies of $j$ in row $j$
down to lower rows so that the frequency of $j$'s in rows $1$ through $j$
matches the frequency in $D$. This is possible, since $D$ has exactly
$a_j$ copies of $j$ that all occur in the first $j$ rows. The choices
made at each step are forced, so there is only one way to produce $D$.
\end{proof}

\subsection{Combinatorial Action of \texorpdfstring{$T$}{T} and \texorpdfstring{$U$}{U}}
\label{subsec:act-T-U}

We can give a similar combinatorial prescription for acting by 
$T=T_2\circ\cdots\circ T_m$ on a basis vector $v=[a_1,\ldots,a_m]\in V$.
Start with the diagram of $v$, consisting of $a_j$ boxes in each row $j$.
For $j=m,m-1,\ldots,2$ in this order, move some number $d\geq 0$
of the boxes currently in row $j$ into $d$ distinct rows
$i_1,\ldots,i_d<j$. Every box that moves causes a sign change in
the coefficient of the final object produced. In this case, even if
we fill each box with its original row number, there is not always
enough information in the final filled diagram to reconstruct
the choices that produced it. This is because a box might be moved to 
its final location in several steps as we proceed from $j=m$ down to $j=2$.
We remedy this defect in~\S \ref{subsec:tourn-invK} by giving a combinatorial
model for $T(v)$ based on tournaments. However, we can use the 
current model to prove the following technical fact mentioned 
at the end of~\S \ref{subsec:act-on-comp}.

\begin{lemma}\label{lem:U-facz}
The operator $U:W\rightarrow W$ factors as $U=U_2\circ U_3\cdots\circ U_m$.
\end{lemma}
\begin{proof}
Recalling that $U=P\circ (T|_W)$ and $U_j=P\circ (T_j|_W)$, 
it suffices to prove that $P\circ\prod_{j=2}^m T_j$
and $\prod_{j=2}^m (P\circ T_j)$ have the same effect on 
any packed basis vector $v=[a_1,\ldots,a_m]\in W$.
On one hand, to compute $[P\circ\prod_{j=2}^m T_j](v)$,
we act on the diagram of $v$ by using the procedure given for $T$,
but at the end we pack each output diagram by letting higher rows
fall into any zero-length rows that have been created.
On the other hand, to compute $[\prod_{j=2}^m P\circ T_j](v)$,
we pack the diagrams after every iteration of the loop over
$j=m,m-1,\ldots,2$. We claim that the extra packing steps do
not affect the signed objects that can be generated. Intuitively,
this holds since the packing step after $T_j$ does not affect
the choices that can be made by later operators $T_{j-1},\ldots,T_2$.
The formal proof follows.

\looseness-1
Since the input list $v$ is already packed, we can assume without loss
of generality that every $a_i$ is positive. This is because the operators
$T_j$ and $P\circ T_j$, corresponding to any zero parts $a_j=0$ at the
right end of $v$, act first and send $v$ to itself. Later operators
$T_i$ and $P\circ T_i$ neither affect nor are affected by these
trailing zero parts in $v$.

Now, we prove the following statement by backwards
induction on $j$ ranging from $m$ down to $1$:
``if $[\prod_{j<J\leq m} T_J](v)=\sum_i c_iL_i$ for certain scalars $c_i$
and lists $L_i$, then $[\prod_{j<J\leq m} P\circ T_J](v)=\sum_i c_iL_i'$,
where each $L_i'=P(L_i)$, the first $j$ components of $L_i'$ agree
with the corresponding components of $L_i$, and the first $j$
components of $L_i$ are positive.'' Here we interpret an
empty product of operators as the identity map. 
For the base case $j=m$, $\sum_i c_iL_i$ and $\sum_i c_iL_i'$ are both $v$,
and the needed conclusions hold by our assumption on $v$.

For the induction step, assume the quoted statement holds for a fixed $j$
between $2$ and $m$, and prove this statement also holds with $j$ replaced
by $j-1$. Here, $[\prod_{j-1<J\leq m} T_J](v)=\sum_i c_iT_j(L_i)$
and $[\prod_{j-1<J\leq m} P\circ T_J](v)=\sum_i c_iP(T_j(L_i'))$, 
where $L_i$ and $L_i'$ satisfy the conditions in the quoted statement.
Let us compare how $T_j$ acts on a particular list 
$L_i=[b_1,\ldots,b_j,b_{j+1},\ldots,b_m]$ with how $P\circ T_j$ acts
on the corresponding list $L_i'=[b_1,\ldots,b_j,b_{j+1}',\ldots,b_m']$.
Here, $b_1,\ldots,b_j$ are all positive, and $[b_{j+1}',\ldots,b_m']$
is the packed version of $[b_{j+1},\ldots,b_m]$. 
Doing $T_j$ to $L_i$ will produce a signed linear combination
of new lists $L_{i,1},\ldots,L_{i,s_i}$. Each list $L_{i,s}$ arises
from $L_i$ by decreasing $b_j$ by some amount (possibly zero)
and incrementing certain entries in $b_1,\ldots,b_{j-1}$.
We can perform exactly the same actions on $L_i'$ and then pack to get
new lists $L_{i,1}',\ldots,L_{i,s_i}'$ such that each $L_{i,s}'$
agrees with $L_{i,s}$ in the first $j-1$ positions, which all
contain positive entries. The only difference between $L_{i,s}'$
and $L_{i,s}$ is that if the new entry in position $j$ of $L_{i,s}$ is zero,
then $P$ moves that entry to the right end in $L_{i,s}'$. Thus, 
$L_{i,s}'=P(L_{i,s})$ for all $i$ and $s$, completing the induction step.

The quoted statement is now known to hold for $j=1$. 
This statement tells us (among other things) that we can obtain 
$[\prod_{j=2}^m P\circ T_j](v)=\sum_i c_iL_i'$ 
by applying $P$ to $[\prod_{j=2}^m T_j](v)=\sum_i c_iL_i$.
This is exactly what we set out to prove. 
\end{proof}


\subsection{Tableau Description of the Kostka Operator \texorpdfstring{$U^{-1}$}{U-1}}
\label{subsec:comb-Uinv}

Thanks to Lemma~\ref{lem:U-facz}, we know $U^{-1}=U_m^{-1}\cdots
U_3^{-1}U_2^{-1}$. So we can give a combinatorial model for $U^{-1}$
(the \emph{Kostka operator} on $W$) similar to what we did
in~\S \ref{subsec:comb-Tinv} for $T^{-1}$. Given a packed basis
vector $v=[a_1,\ldots,a_m]\in W$, compute $U^{-1}(v)$ as follows.
Start with the filled diagram of $v$ where row $j$ has $a_j$ boxes
labeled $j$. For $j=2,3,\ldots,m$ in this order, use the recursive
motion rule for $U_j^{-1}$ (see~\S \ref{subsec:comb-Tjinv-Ujinv}) to move 
filled boxes from row $j$ into lower rows. This includes the possibility that
higher rows fall into row $j$ and some of their boxes move down
recursively. Do this in all possible ways; the sum of the shapes
of the resulting filled diagrams is $U^{-1}(v)$.

\begin{exam}\label{ex:Uinv}
Given $v=[2,1,2]\in W$, let us find $U^{-1}(v)=U_3^{-1}(U_2^{-1}(v))$. First 
compute $U_2^{-1}(v)=[212]+[320]+[410]+[500]$ using the diagrams
shown below.
\[\tableau{3&3\\2\\1&1}\quad\tableau{\\3&3\\1&1&2}\quad
 \tableau{\\3\\1&1&2&3} \quad\tableau{\\ \\1&1&2&3&3}\] 
Now $U_3^{-1}$ acts as the identity on $[320]$, $[410]$, and $[500]$,
since the associated diagrams have no boxes in row $3$. Computing
$U_3^{-1}([212])$, we now move entries from row 3 down in all possible ways, 
obtaining the diagrams shown here.
\[\tableau{3&3\\2\\1&1}\quad \tableau{3\\2&3\\1&1} \quad 
\tableau{3\\2\\1&1&3} \quad \tableau{\\2&3&3\\1&1} \quad 
\tableau{\\2&3\\1&1&3} \quad \tableau{\\2\\1&1&3&3}\] 
Thus, $U^{-1}(v) = [212]+[221]+[311]+[230]+2[320]+2[410]+[500]$.
\end{exam}

When we characterize the filled diagrams appearing in the
computation of $U^{-1}(v)$, dual immaculate tableaux miraculously emerge.
Recall (\S \ref{subsec:immac-kostka}) that a dual immaculate tableau is a 
filling of a composition diagram so that rows weakly increase from left to 
right and the first (leftmost) column strictly increases from bottom to top.

\begin{theorem}\label{thm:Uinv}
For any basis vector $v=[a_1,\ldots,a_m]$ of $W$, 
$U^{-1}(v)=\sum_D \sh(D)$, where we sum over all dual immaculate
tableaux $D$ of content $v$.
\end{theorem}
\begin{proof}
\looseness-1
First suppose $D$ is one of the filled diagrams generated by the
algorithm for computing $U^{-1}(v)$. Note that the initial filled
diagram for $v$ is a dual immaculate tableau of content $v$. 
The action of each $U_j^{-1}$ preserves the content.
Also, a routine induction on $j$ shows that $U_j^{-1}$ 
acts only on diagrams such that all values below row $j$
are less than all values in rows $j$ and higher.
It follows that each $U_j^{-1}$ (hence $U$ itself)
preserves the property of having weakly increasing rows. 
Moreover, a value in column $1$ only changes
when a row becomes empty and higher rows fall down into the gap.
Since the initial values in column $1$ form a strictly increasing
sequence, this property is preserved throughout the algorithm.
Thus, $D$ is a dual immaculate tableau of content $v$.

Conversely, we now verify that every dual immaculate tableau $D$ of content 
$v$ arises in exactly one way during the computation of $U^{-1}(v)$.
Fix such a tableau $D$. Let the strictly increasing
sequence of values in column $1$ of $D$ be $a_1<a_2<\cdots<a_k$,
where $a_1=1$, and let $M$ be the maximum value in $D$.
Because rows of $D$ weakly increase, any occurrence
in $D$ of a value $i\leq a_j$ must occur in one of the first $j$ rows.
Consider how we could produce $D$ from the filled diagram of $v$
during the computation of $U^{-1}$. The first step (acting by $U_2^{-1}$)
must terminate with $a_2$ residing in row $2$, column 1, since
none of the later $U_j^{-1}$ steps can displace the first entry in row $2$.
Similarly, the action by $U_3^{-1}$ must terminate with $a_3$ residing
in row $3$, column $1$, and so on. This means that the box motions chosen
in the $U_2^{-1}$ step must be the following: for $i=2,3,\ldots,a_2$
in this order, move the $i$'s from row $2$ to their final locations 
in $D$. Next, in the $U_3^{-1}$ step, we must act as follows:
for $i=a_2+1,\ldots,a_3$, move all the $i$'s from row $3$ to
their final locations in $D$. Continue similarly with $U_4^{-1},
\ldots,U_k^{-1}$. If $M>a_k$, then we end with the following actions
during the $U_{k+1}^{-1}$ step: for $i=a_k+1,\ldots,M$, move all
the $i$'s from row $k+1$ to their final locations in $D$. This procedure
gives the unique sequence of choices leading from $v$ to $D$.
\end{proof}

\begin{exam}\label{ex:sequence}
Given the dual immaculate tableau
\[D=\tableau{5&5\\3&4&5\\2&3\\1&2&4}\]
of content $v=[12223]$,
Figure~\ref{fig:seq} shows the unique choice sequence that produces $D$ 
from the filled diagram for $v$. In Figure~\ref{fig:seq} the labels moving 
are in bold in each step.

\begin{figure}[htb]
\[\tableau{5&5&5\\4&4\\3&3\\2&\boldsymbol{2}\\1}
\stackrel{U_2^{-1}}\longrightarrow 
\tableau{5&5&5\\4&4&\\3&\boldsymbol{3}\\2\\1&2}
\stackrel{U_3^{-1}}\longrightarrow 
\tableau{5&5&5\\\boldsymbol{4}&\boldsymbol{4}\\3\\2&3\\1&2}
\stackrel{\text{begin }U_4^{-1}}\longrightarrow 
\tableau{\\5&5&\boldsymbol{5}\\3&4\\2&3\\1&2&4}
\stackrel{\text{finish }U_4^{-1}}\longrightarrow 
\tableau{\\5&5\\3&4&5\\2&3\\1&2&4}\]
\caption{Illustration of the sequence of choices leading from $v$ to $D$.}\label{fig:seq}
\end{figure} 
\end{exam}

\subsection{Interpolating Bases for \texorpdfstring{$\NSym$}{NSym} and \texorpdfstring{$\QSym$}{QSym}}
\label{subsec:interp-bases}

Given a composition $\alpha\in\Comp_m$ with $\ell$ nonzero parts,
let $[\alpha]$ denote the $m$-element list 
$[\alpha_1,\ldots,\alpha_{\ell},0,\ldots,0]$, which
is a basis element of $W$. Theorem~\ref{thm:Uinv}
translates into the following fact about the immaculate Kostka matrix.

\begin{theorem}\label{thm:Uinv-Ki}
For all compositions $\beta\in\Comp_m$,
$U^{-1}([\beta])=\sum_{\alpha\in\Comp_m} \Ki(\alpha,\beta)[\alpha]$. 
\end{theorem}

Let $\NSym_m$ (resp. $\QSym_m$) be the subspace of $\NSym$ (resp. $\QSym$)
consisting of homogeneous elements of degree $m$. Also let
$W_m$ be the subspace of $W$ spanned by the lists $[\alpha]$ with
$\alpha\in\Comp_m$. We can identify the vector space $W_m$
with $\NSym_m$ by identifying the list $[\alpha]$
with the immaculate basis element $\imm_{\alpha}$ for all $\alpha\in\Comp_m$.
Then $U$ and $U^{-1}$, which map $W_m$ into itself,
are identified with linear maps on $\NSym_m$.
Comparing Theorem~\ref{thm:Uinv-Ki} to the definition~\eqref{eq:Kostka-QSym},
we see that 
\begin{equation}\label{eq:Uinv-on-NSym}
 U^{-1}(\imm_{\beta})=\sum_{\alpha\in\Comp_m} \Ki(\alpha,\beta)\imm_{\alpha}
 =\nh_{\beta}\quad\mbox{ for all $\beta\in\Comp_m$.} 
\end{equation} 
Thus, the Kostka operator $U^{-1}$ maps the $\imm$-basis of 
$\NSym$ to the $\nh$-basis, and the inverse Kostka operator $U$ maps
the $\nh$-basis to the $\imm$-basis.

We have seen that the linear map $U^{-1}$ factors as 
$U^{-1}=U_m^{-1}\cdots U_3^{-1}U_2^{-1}$, where each $U_j^{-1}$
maps $W_m$ into itself.
Therefore, we obtain \emph{interpolating bases} between
the $\nh$-basis and the $\imm$-basis of $\NSym_m$ by defining
\[ \imm^{(i)}_{\beta}=[U_i^{-1}\cdots U_3^{-1}U_2^{-1}](\imm_{\beta})
\quad\mbox{ for all $\beta\in\Comp_m$ and $1\leq i\leq m$.} \]
Here $\imm^{(1)}_{\beta}=\imm_{\beta}$ and $\imm^{(m)}_{\beta}=\nh_{\beta}$.

So far we have always considered vector spaces $V$ and $W$
spanned by lists of a fixed length $m$ (including trailing zero parts). 
These spaces naturally embed in the corresponding spaces spanned by lists 
of length $m+1$ by appending a zero part to the end of each basis vector.
The maps $T_{m+1}$, $U_{m+1}$, and their inverses act as the identity
on a list of length $m+1$ ending with a zero part. In particular, the
value of quantities such as $U(v)$, $U^{-1}(v)$, $U_i^{-1}\cdots U_2^{-1}(v)$,
etc. remains stable if we append trailing zero parts to $v$. 
By taking a suitable algebraic limit as $m$ goes to infinity, we can 
extend our entire discussion to spaces spanned by lists of infinite length 
that have only finitely many nonzero parts. So for each positive integer $i$,
we obtain a basis $(\imm^{(i)}_{\beta})$ of the full space 
$\NSym=\bigoplus_{m\geq 0} \NSym_m$,
where $\beta$ ranges through all compositions. For all $\beta\in\Comp_m$
and all $N\geq m$, we have $\imm^{(N)}_{\beta}=\nh_{\beta}$.

Inverting~\eqref{eq:Uinv-on-NSym}, we see that
the matrix of the linear map $U:\NSym_m\rightarrow\NSym_m$ 
relative to the immaculate basis $(\imm_{\beta})$ of $\NSym_m$ 
is $\Ki^{-1}$, where $\Ki$ is the immaculate Kostka matrix.
Therefore, the matrix of the dual linear map 
$U^*:\QSym_m\rightarrow \QSym_m$ relative to the dual basis 
$(\dimm_{\beta})$ of $\QSym_m$ is the transpose of $\Ki^{-1}$.
In other words, recalling~\eqref{eq:invKostka-QSym},
\[ U^*(\dimm_{\alpha})=\sum_{\beta\in\Comp_m}
 \Ki^{-1}(\alpha,\beta)\dimm_{\beta}=M_{\alpha}
\quad\mbox{ for all $\alpha\in\Comp_m$}. \]
Thus the dual inverse Kostka operator $U^*$ maps the $\dimm$-basis
of $\QSym_m$ to the $M$-basis, while the dual of $U^{-1}$ maps the $M$-basis
to the $\dimm$-basis. By applying $U^*$ or its inverse in stages,
we obtain interpolating bases between these two bases of $\QSym_m$.
As above, we can take a formal limit to get bases for the full space $\QSym$,
which are dual to the bases $(\imm^{(i)}_{\beta})$.
Specifically, $\imm^{(i)*}_{\beta}=U_i^*\cdots U_3^*U_2^*(\dimm_{\beta})$
for all compositions $\beta$.

By adjusting the proof of Theorem~\ref{thm:Uinv} to stop the computation
of $U^{-1}$ after $U_i^{-1}$, we can obtain a combinatorial
expansion of $\imm^{(i)}_{\beta}$ in terms of the $\imm$-basis.
Given a composition $\alpha$, let $\ell(\alpha)=s$ be the number of 
positive parts of $\alpha$.
Given a composition $\beta=(\beta_1,\ldots,\beta_m)$ and $j\in [m]$, 
define $\beta_{\leq j}=(\beta_1,\ldots,\beta_j)$ and
$\beta_{>j}=(\beta_{j+1},\ldots, \beta_m)$.
Let $\Ki'(\alpha,\beta_{\leq j})$ be the set of dual immaculate tableaux
of shape $\alpha$ and content $\beta_{\leq j}$ such that every entry
in the top row is $j$. Let $\alpha\bullet\beta_{>j}$ be the composition
consisting of the parts of $\alpha$ followed by $(\beta_{j+1},\ldots,\beta_m)$.

\begin{theorem}\label{thm:interp-basis}
For all compositions $\beta$ with $m$ parts and all positive integers $i$,
\begin{equation}\label{eq:interp-basis}
 \imm^{(i)}_{\beta} = 
\sum_{\substack{\alpha\in\Comp: \\ \ell(\alpha)<i }} 
 \Ki(\alpha,\beta)\imm_{\alpha}
+\sum_{\substack{\alpha\in\Comp: \\ \ell(\alpha)=i }} 
 \sum_{j=i}^m \Ki'(\alpha,\beta_{\leq j})\imm_{\alpha\bullet\beta_{>j}}. 
\end{equation}
\end{theorem}
\begin{proof}
Consider a typical object $D$ generated 
when we start with the filled diagram of $[\beta]$, act by 
$U_2^{-1}$, $U_3^{-1}$, $\ldots$, $U_i^{-1}$ in this order, and then stop.
If $D$ has fewer than $i$ rows of positive length,
then (as in the proof of Theorem~\ref{thm:Uinv}) $D$ is a dual immaculate 
tableau of content $\beta$ and some shape $\alpha$ with $\ell(\alpha)<i$.
Moreover, all such tableaux arise exactly once in this computation.
This accounts for the first sum in~\eqref{eq:interp-basis}.

On the other hand, suppose $D$ has at least $i$ rows, and let $j$ be
the symbol in row $i$, column $1$ of $D$. Using the combinatorial description
of the operators $U_k^{-1}$, one readily sees that: $i\leq j\leq m$;
the first $i$ rows of $D$ form a dual immaculate tableau 
counted by $\Ki'(\alpha,\beta_{\leq j})$ for some $\alpha$ with
$\ell(\alpha)=i$; row $i+1$ of $D$ must contain $\beta_{j+1}$ copies of $j+1$; 
row $i+2$ of $D$ must contain $\beta_{j+2}$ copies of $j+2$; and so on. 
Thus the overall shape of $D$ is $\alpha\bullet\beta_{>j}$. Each diagram $D$ 
satisfying these conditions (for some such $\alpha$ and $j$) arises exactly 
once in the computation. 
This explains the second sum in~\eqref{eq:interp-basis}. 
\end{proof}

For instance, $\imm^{(2)}_{212}=\imm_{212}+\imm_{32}+\imm_{41}+\imm_{5}$
by Theorem~\ref{thm:interp-basis} or Example~\ref{ex:Uinv}.

\begin{rema} 
Theorem~\ref{thm:interp-basis} shows that each interpolating basis
$(\imm^{(i)}_{\beta})$ has a positive integral expansion in
the immaculate basis of $\NSym$. By duality, the dual immaculate basis
of $\QSym$ has a positive integral expansion in each basis
$(\imm^{(i)*}_{\beta})$. It would be interesting to find (signed) 
combinatorial formulas for the expansions of
$(\imm^{(i)*}_{\beta})$ in terms of other familiar bases of $\QSym$
such as the Young quasisymmetric Schur basis or the fundamental basis.
\end{rema}


\section{Tournaments, Determinants, Recursions, and Special Rim Hook Tableaux}
\label{sec:tourn-etc}

This section gives combinatorial models for the action of the
inverse Kostka operators $T$ and $U$ based on tournaments and
related structures. This leads to several formulas for
the entries in the inverse of the immaculate Kostka matrix.

An \emph{$m$-player tournament} is an $m\times m$ matrix $\tau$
with entries in $\{0,1\}$ such that for all $i$ in $[m]$, $\tau(i,i)=0$;
and for all $i<j$ in $[m]$, exactly one of $\tau(i,j)$ and $\tau(j,i)$ is $1$. 
Let $\T_m$ be the set of all $m$-player tournaments.
Note that $\tau\in \T_m$ is uniquely determined by the values
$\tau(i,j)$ with $1\leq i<j\leq m$.
The \emph{sign} of a tournament $\tau$ is
$\sgn(\tau)=\prod_{1\leq i<j\leq m} (-1)^{\tau(i,j)}$.
Thus, $\sgn(\tau)$ is $-1$ if $\tau$ has an odd number of $1$s above
the diagonal, and $+1$ otherwise.

\subsection{Tournament Models for Inverse Kostka Operators}
\label{subsec:tourn-invK}

\looseness-1
Let us first consider the action of the operator 
$T_0=\prod_{1\leq i<j\leq m} (I-R_{i,j})$
on the vector space $V_0$ with basis $\Z^m$.
We can expand this product of operators using the generalized distributive
law. For each factor $I-R_{i,j}$, we choose either $I$ or $-R_{i,j}$,
multiply together the chosen factors, and add all the results.
We can use a tournament $\tau\in \T_m$ to record all the choices made.
Specifically, for each $i<j$ in $[m]$, we let $\tau(i,j)=0$ if we pick
$I$ from the factor $I-R_{i,j}$, and we let $\tau(i,j)=1$ if we pick
$-R_{i,j}$ from this factor. We conclude that
\[ T_0=\prod_{i<j} (I-R_{i,j}) 
 =\sum_{\tau\in \T_m}\sgn(\tau)
 \prod_{\substack{i<j: \\ \tau(i,j)=1}} R_{i,j}. \]
For fixed $\tau\in \T_m$, the term in this sum indexed by $\tau$ sends
a list $[a_1,\ldots,a_m]$ in $\Z^m$ to $\sgn(\tau)[b_1,\ldots,b_m]$, where
\begin{equation}\label{eq:tourn-in-V0}
 b_k=a_k+\sum_{j=k+1}^m \tau(k,j)-\sum_{i=1}^{k-1} \tau(i,k)
 \quad\mbox{ for $1\leq k\leq m$.} 
\end{equation}
This holds since position $k$ initially contains $a_k$,
each $R_{i,j}$ with $i=k$ increments position $k$,
and each $R_{i,j}$ with $j=k$ decrements position $k$.
Identifying each list $[c_1,\ldots,c_m]$ with $h_{c_1}\cdots h_{c_m}\in\Sym$, 
we obtain the tournament model for the inverse Kostka matrix
mentioned at the end of~\S \ref{subsec:kostka}.

Turning to the space $V$, the inverse Kostka operator $T$ acts
on nonnegative lists $v=[a_1,\ldots,a_m]\in V$ by a similar formula.
Note first that
\begin{equation}\label{eq:tourn-in-V}
 T=\sum_{\tau\in \T_m}\prod_{j=2}^m\prod_{i=1}^{j-1} (-R_{i,j})^{\tau(i,j)}
 =\sum_{\tau\in \T_m}\sgn(\tau)\prod_{j=2}^m
\prod_{\substack{i<j:\\ \tau(i,j)=1}} R_{i,j}.
\end{equation}
We claim that we can find $T(v)$ in $V$ by computing $T_0(v)$ in $V_0$
(using formula~\eqref{eq:tourn-in-V0}) and then discarding any output
lists that have negative entries. This claim holds because of the order
in which we apply the $R_{i,j}$ operators in~\eqref{eq:tourn-in-V}.
The key point is that if a list entry becomes negative after applying
some of the operators encoded by~$\tau$, then that entry must remain negative 
after applying all the operators encoded by~$\tau$. Thus, a list that
is sent to zero at some intermediate stage (working in $V$) must also
be sent to zero if we work in $V_0$ and only discard lists with negative
entries at the very end. 

Finally, we can describe how the inverse Kostka operator $U=P\circ (T|_W)$
acts on the space $W$. We use the same formula~\eqref{eq:tourn-in-V}
given for $T$ (applied to basis vectors $[a_1,\ldots,a_m]\in W$), but at the
end we must apply $P$ by packing all the output lists.

\begin{exam}\label{ex:tourn}
The following table computes $T([3,1,3])$ using tournaments.
To visualize~\eqref{eq:tourn-in-V0}, we enter $a_1=3$, $a_2=1$, $a_3=3$
along the main diagonal of each tournament matrix $\tau\in \T_3$.
To find the output term $\pm [b_1,b_2,b_3]$ corresponding to $\tau$
via~\eqref{eq:tourn-in-V0}, we start with each diagonal entry $a_k$ and
compute $b_k$ by adding the $1$s to the right of $a_k$ in row $k$
and subtracting the $1$s above $a_k$ in column $k$.
\[
\begin{array}{cccccccc}
\matc{3&0&0}
 {1&1&0}
 {1&1&3} &
\matc{3&0&0}
 {1&1&1}
 {1&0&3} &
\matc{3&0&1}
 {1&1&0}
 {0&1&3} &
\matc{3&0&1}
 {1&1&1}
 {0&0&3} &
\matc{3&1&0}
 {0&1&0}
 {1&1&3} &
\matc{3&1&0}
 {0&1&1}
 {1&0&3} &
\matc{3&1&1}
 {0&1&0}
 {0&1&3} &
\matc{3&1&1}
 {0&1&1}
 {0&0&3} \\[5pt]
+[313] &
-[322] &
-[412] &
+[421] &
-[403] &
+[412] &
+[502] &
-[511]
\end{array} \]
Packing these outputs and noting the cancellation of $\pm[412]$, 
we get $U([3,1,3])=[313]-[322]+[421]-[430]+[520]-[511]$.
\end{exam}

Let the \emph{difference vector} of a tournament
$\tau\in \T_m$ be the list $\Delta(\tau)=[\delta_1(\tau),\ldots,
\delta_m(\tau)]$, where $\delta_k(\tau)=\sum_{j>k} \tau(k,j)
-\sum_{i<k} \tau(i,k)$. For each $k\in [m]$, the \emph{outdegree
of $k$ in $\tau$} is $d_k(\tau)=\sum_{j=1}^m \tau(k,j)$.
Since $\tau(i,k)=1-\tau(k,i)$ for all $i<k$ in $[m]$, we see that
\begin{equation}\label{eq:delta-tau}
 \delta_k(\tau)=\sum_{j:\,j>k} \tau(k,j)+\sum_{j:\,j<k} (-1+\tau(k,j))
 =d_k(\tau)-(k-1)\mbox{ for all $k\in [m]$.} 
\end{equation}
For lists of integers $v=[a_1,\ldots,a_m]$ and
$w=[b_1,\ldots,b_m]$, let $v\oplus w=[a_1+b_1,\ldots,a_m+b_m]$
(which is not the same as the formal linear combination $v+w$ in $V_0$).
Our results so far can be summarized as follows.

\begin{prop}
For all basis vectors $v\in V$ and $w\in W$,
\begin{equation}\label{eq:tourn-TU}
 T(v)=\sum_{\tau\in \T_m} \sgn(\tau)(v\oplus\Delta(\tau))\quad\mbox{ and }
 \quad U(w)=\sum_{\tau\in \T_m} \sgn(\tau)P(w\oplus\Delta(\tau)). 
\end{equation} 
\end{prop}

Now suppose $\beta$ is a (strict) composition of $n$ with $m$ parts.
We know from Theorem~\ref{thm:Uinv-Ki} that
$U([\beta])=\sum_{\alpha} \Ki^{-1}(\alpha,\beta)[\alpha]$. 
It suffices to sum over compositions $\alpha$ of $n$ with at most $m$ parts,
as is readily checked. For any such composition $\alpha$, let
$\T_m(\alpha,\beta)$ be the set of $\tau\in \T_m$ such that
$P([\beta]\oplus\Delta(\tau))=[\alpha]$.
We deduce the following combinatorial formula for the entries
of the inverse of the immaculate Kostka matrix.

\begin{theorem}\label{thm:Kinv-tourn}
For all compositions $\alpha$ and $\beta$ where $\beta$ has $m$ parts,
\[\displaystyle
{\Ki^{-1}(\alpha,\beta)=\sum_{\tau\in \T_m(\alpha,\beta)} 
\sgn(\tau)}.
\] 
\end{theorem}

For instance, Example~\ref{ex:tourn} provides the entire column of $\Ki^{-1}$ 
indexed by $\beta=[3,1,3]$. Specifically, the entries in rows $313$,
$421$, and $520$ of this column are $+1$, the entries in rows $322$,
$430$, and $511$ of this column are $-1$, and all other entries 
in this column are $0$. 


\subsection{Transitive Tournaments and the Jacobi--Trudi Formula}
\label{subsec:trans-tourn}

A tournament $\tau\in \T_m$ is called \emph{transitive} iff
for all $i,j,k\in [m]$, $\tau(i,j)=1$ and $\tau(j,k)=1$ imply
$\tau(i,k)=1$. It is well-known (see, for instance, 
Theorem~12.64 in~\cite{loehr-comb}) that 
$\tau$ is transitive iff the list of outdegrees
$d_1(\tau),\ldots,d_m(\tau)$ is a permutation of $0,1,\ldots,m-1$.
Let $\TT_m$ be the set of transitive tournaments in $\T_m$.

\begin{theorem}\label{thm:Kinv-trans}
Formula~\eqref{eq:tourn-TU} and Theorem~\ref{thm:Kinv-tourn} 
remain valid if we sum over \emph{transitive} tournaments
in $\T_m$ and $\T_m(\alpha,\beta)$, respectively.
\end{theorem}
\begin{proof}
It suffices to define an involution $I$ on $\T_m$ such that for all
transitive $\tau\in \T_m$, $I(\tau)=\tau$; and for all non-transitive
$\tau\in \T_m$, $\sgn(I(\tau))=-\sgn(\tau)$ and $\Delta(\tau)=\Delta(I(\tau))$.
Fix a non-transitive $\tau\in \T_m$, so that not all outdegrees in $\tau$
are distinct. Choose the minimum $r$ and then the minimum $s>r$ such
that $d_r(\tau)=d_s(\tau)$. Define $\tau'=I(\tau)$ by interchanging
the roles of $r$ and $s$ in $\tau$. In more detail, writing $r'=s$,
$s'=r$, and $k'=k$ for all $k\neq r,s$ in $[m]$, we define
$\tau'(i',j')=\tau(i,j)$ for all $i,j\in [m]$. Since $d_r(\tau)=d_s(\tau)$,
the list of outdegrees for $\tau'$ is the same as the list for $\tau$.
This implies that $\tau'$ is non-transitive and $I(\tau')=\tau$.
Moreover, $\Delta(\tau)=\Delta(\tau')$ follows from~\eqref{eq:delta-tau}.
It is routine to check that $\sgn(\tau')=-\sgn(\tau)$
(see~\cite[p. 548]{loehr-comb} for details). 
\end{proof}

\begin{exam}\label{ex:trans-cancel}
Cancellation may still occur in the formula
\[
\Ki^{-1}(\alpha,\beta)=\sum_{\tau\in\TT_m(\alpha,\beta)} \sgn(\tau).
\]
For example, $\Ki^{-1}(32,212)=0$ due to the cancellation of
the first two transitive tournaments shown below, while $\Ki^{-1}(41,212)=0$ 
due to the cancellation of the next two transitive tournaments
shown. These cancellations are possible because of the packing of output lists
when computing $U([212])=[212]-[221]$. To guarantee that the formula
for $\Ki^{-1}(\alpha,\beta)$ has no such cancellations, it is sufficient
that $\beta_j\geq j$ for $1\leq j\leq \ell(\beta)$. For in that case,
no zero parts occur in the lists appearing in $U([\beta])$.
\[ \begin{array}{ccccc}
\matc{2&1&0}
 {0&1&0}
 {1&1&2} &
\matc{2&0&1}
 {1&1&1}
 {0&0&2} & \hspace*{0.5in} &
\matc{2&1&1}
 {0&1&0}
 {0&1&2} &
\matc{2&1&1}
 {0&1&1}
 {0&0&2} \\[13pt]
-[302] &
+[320] & &
+[401] & 
-[410] 
\end{array} \]
\end{exam}

We now describe the close relation between transitive tournaments 
and permutations. Let $S_m$ be the set of permutations (bijections) 
$w:[m]\rightarrow [m]$. We identify $w\in S_m$ with the word 
$w_1,w_2,\ldots,w_m$, which is a rearrangement of $1,2,\ldots,m$. 
Recall that the \emph{inversion count} $\inv(w)$ is the number
of $i<j$ in $[m]$ with $w_i>w_j$, and $\sgn(w)=(-1)^{\inv(w)}$.

\begin{lemma}
There is a sign-preserving bijection $W:\TT_m\rightarrow S_m$ such that 
\[ W(\tau)=w_1(\tau),\ldots,w_m(\tau)=d_1(\tau)+1,\ldots,d_m(\tau)+1 \]
(the list of incremented outdegrees of $\tau$). The inverse bijection
$W':S_m\rightarrow \TT_m$ sends $w=w_1,\ldots,w_m\in S_m$
to $\tau$, where for all $i,j\in [m]$, $\tau(i,j)$ is $1$
if $w_i>w_j$ and $0$ otherwise.
\end{lemma}
\begin{proof}
We see that $W'$ does map $S_m$ into the claimed codomain $\TT_m$
by definition of transitive tournaments, while
$W$ does map $\TT_m$ into the codomain $S_m$ by the
characterization of transitive tournaments in terms of outdegrees.
Given $w\in S_m$, let $\tau=W'(w)\in \TT_m$. We check that $W(\tau)=w$. 
For each $i\in [m]$, $d_i(\tau)=\sum_{j=1}^m \tau(i,j)$
is the total number of symbols in $w$ that are less than $w_i$.
Since $w$ is a rearrangement of $1,2,\ldots,m$, the number
of such symbols must be $w_i-1$. Hence $d_i(\tau)+1=w_i$ 
for all $i$, so $W(\tau)=w$. As $w$ was arbitrary,
$W\circ W'$ is the identity map on $S_m$.
Since $S_m$ and $\TT_m$ are both finite sets of size $m!$,
we conclude that $W'$ is the two-sided inverse of $W$.
To finish, we check that $\sgn(\tau)=\sgn(w)$. We compute
\[ 
\sgn(\tau)=(-1)^{\sumred_{i<j} \tau(i,j)}=(-1)^{\sumred_{i<j} \chi(w_i>w_j)}
 =(-1)^{\inv(w)}=\sgn(w). \qedhere 
 \]
\end{proof}


We can now relate the tournament-based formulas for $\Ki^{-1}$ to
the noncommutative Jacobi--Trudi formula. The next theorem provides
the promised combinatorial proof of the equivalence of the two
definitions~\eqref{eq:invKostka-QSym} and~\eqref{eq:imm-JT}
for the immaculate basis $(\imm_{\beta})$ of $\NSym$.

\begin{theorem}\label{thm:Kinv-JT}
For all compositions $\alpha$, $\beta$ where $\beta$ has $m$ parts,
$\Ki^{-1}(\alpha,\beta)$ is the coefficient of $\nh_{\alpha}$ in 
$\detd[\nh_{\beta_i+j-i}]_{m\times m}$ 
(and hence this determinant does equal $\imm_{\beta}$ as defined
 in~\eqref{eq:invKostka-QSym}). 
\end{theorem}
\begin{proof}
Fix compositions $\alpha$, $\beta$ where $\beta$ has $m$ parts.
Theorem~\ref{thm:Kinv-trans} shows that
$\Ki^{-1}(\alpha,\beta)$ is the sum of $\sgn(\tau)$ over the
transitive tournaments $\tau\in \T_m(\alpha,\beta)$.
For any transitive $m$-player tournament $\tau$, 
the following conditions are equivalent:
\begin{itemize}
\item $\tau$ is in $\T_m(\alpha,\beta)$.
\item $P([\beta]\oplus \Delta(\tau))=[\alpha]$.
\item Packing the list $\beta_1+\delta_1(\tau),\beta_2+\delta_2(\tau),\ldots,
\beta_m+\delta_m(\tau)$ yields $[\alpha]$.
\item \looseness-1
Packing the list $\beta_1+d_1(\tau),\beta_2+d_2(\tau)-1,
\ldots,\beta_m(\tau)+d_m(\tau)-(m-1)$ yields $[\alpha]$.
\item Packing the list $\beta_1+w_1(\tau)-1,\beta_2+w_2(\tau)-2,
\ldots,\beta_m(\tau)+w_m(\tau)-m$ yields $[\alpha]$.
\item $W(\tau)$ is a permutation $w$ in $S_m$ such that
\[
\nh_{\beta_1+w(1)-1,\beta_2+w(2)-2,\ldots,\beta_m+w(m)-m}=\nh_{\alpha}.
\]
\end{itemize}
Using this and the definition of the determinant
in~\eqref{eq:imm-JT}, we see that the sum of $\sgn(\tau)$
over transitive $\tau\in \T_m(\alpha,\beta)$ equals 
the sum of $\sgn(w)$ over all $w\in S_m$ that yield a term
$\nh_{\alpha}$ when we expand $\detd[\nh_{\beta_i+j-i}]$.
Thus, $\Ki^{-1}(\alpha,\beta)$ is indeed the net coefficient
of $\nh_{\alpha}$ in this expansion. 
\end{proof}

\subsection{Recursive Computation of \texorpdfstring{$\Ki^{-1}$}{K-1}}
\label{subsec:invK-rec}

We can use Laplace expansions of the noncommutative
Jacobi--Trudi determinant to obtain recursions characterizing
the entries of $\Ki^{-1}$. For any $m\times m$ matrix $A$,
let $A[i|j]$ be the matrix obtained by deleting row $i$ and column $j$
of $A$. The most natural recursive expansions of a top-to-bottom
determinant proceed along row $1$ or row $m$:
\[ \detd[A] =\sum_{j=1}^m (-1)^{1+j}A(1,j)\detd[A[1|j]]
 =\sum_{j=1}^m (-1)^{m+j}\detd[A[m|j]]A(m,j). \] 
However, to ensure that the smaller subdeterminants are also
Jacobi--Trudi determinants, we need to consider an expansion
of $\detd[A]$ down column $m$, which is more awkward to formulate.

For any list $v\in\Z^m$, let $A(v)$ be the $m\times m$
matrix with entries $A(i,j)=\nh_{v_i+j-i}$ for $i,j\in [m]$.
In this discussion, we do not replace the symbols $\nh_0$ by
$1$ or $\nh_k$ by $0$ for $k<0$.
For any $i\in [m]$, let $v^{(i)}$ be the list obtained 
by deleting the $i$th entry of $v$ and decrementing all subsequent
entries. The key observation is that deleting row $i$, column $m$
of $A(v)$ produces the matrix $A(v^{(i)})$. 

\begin{exam}
For $v=(2,4,1,3)$,
\[ A(v)=\left[\begin{array}{cccc}
 \nh_2 & \nh_3 & \nh_4 & \nh_5 \\
 \nh_3 & \nh_4 & \nh_5 & \nh_6 \\
 \nh_{-1}& \nh_0 & \nh_1 & \nh_2 \\
 \nh_0 & \nh_1 & \nh_2 & \nh_3 
\end{array} \right]. \]
We have $v^{(1)}=(3,0,2)$, $v^{(2)}=(2,0,2)$,
$v^{(3)}=(2,4,2)$, and $v^{(4)}=(2,4,1)$.
We see by inspection that $A(v)[i|4]=A(v^{(i)})$ for $i=1,2,3,4$.
\end{exam}

Consider the defining formula~\eqref{eq:def-detd} for $\detd[A(v)]$.
For fixed $i\in [m]$, we can obtain the terms indexed by $f\in S_m$
with $f(i)=m$ as follows. 
First compute $\detd[A(v)[i|m]] =\detd[A(v^{(i)})]$ to
obtain a sum of terms $\pm\nh_w$, where $w\in\Z^{m-1}$ is a list of $m-1$ 
integers. Adjust each such term by inserting $v_i+m-i$ into position $i$
of list $w$, and multiplying the sign by $(-1)^{i+m}$. Summing all
the adjusted terms arising from all $i\in [m]$, we obtain $\detd[A(v)]$. 
These ideas lead to the following recursive technique for
computing entries of $\Ki^{-1}$.

\begin{theorem}\label{thm:detd-rec}
For $v,w\in\Z^m$, let $D(w,v)$ be the coefficient of $\nh_w$ when we expand
$\detd[A(v)]$. 
Define $v^{(i)}$ as above, and let $w^{[i]}$ be the list $w$
with its $i$th entry deleted. 
\begin{enumerate}[label=(\alph*)]
%(a) 
\item\label{theo4.9_a}
$D(w,v)=\chi(w=v)$ for $m=1$, and 
\begin{equation}\label{eq:detd-rec}
 D(w,v)=\sum_{i=1}^m (-1)^{i+m}D(w^{[i]},v^{(i)})\chi(w_i=v_i+m-i)
\quad\mbox{ for $m>1$.}
\end{equation}

%(b) 
\item\label{theo4.9_b}
For all compositions $\alpha,\beta$ where $\beta$ has $m$ parts,
\begin{equation}\label{eq:Kinv-rec}
 \Ki^{-1}(\alpha,\beta)=\sum_{\substack{w\in\Z^m:\\
 P(w)=[\alpha]}} D(w,[\beta]). 
\end{equation}
\end{enumerate}
\end{theorem}
\begin{proof}
%(a) 
\ref{theo4.9_a}~The formula for $D(w,v)$ is true when $m=1$, since $\detd[A(v)]=\nh_{v_1}$
in that case. For $m>1$, we obtain~\eqref{eq:detd-rec}
by expanding $\detd[A(v)]$ along column $m$, as described above. 
A term involving $\nh_w$ arises in this expansion precisely
when there is an $i$ such that $\detd[A(v^{(i)})]$ produces a term
involving $\nh_{w^{[i]}}$ and we insert $w_i$ into $w^{[i]}$
as the new $i$th entry, modifying the sign coefficient by $(-1)^{i+m}$.
Since the actual value inserted is $v_i+m-i$, we only
get a contribution to $D(w,v)$ for those $i$ such that $w_i=v_i+m-i$.

\ref{theo4.9_b}~For compositions $\alpha,\beta$ where $\beta$ has $m$ parts,
Theorem~\ref{thm:Kinv-JT} states
that $\Ki^{-1}(\alpha,\beta)$ is the coefficient of $\nh_{\alpha}$
in ${\detd[A([\beta])]}$, where now we do substitute $\nh_0=1$
and $\nh_k=0$ for $k<0$. For lists $w\in\Z^m$ without negative entries,
this has the effect of replacing each $\nh_w$ by $\nh_{P(w)}$. 
The net coefficient of $\nh_{\alpha}$ is the sum of the
coefficients of $\nh_w$ over all $w$ with $P(w)=[\alpha]$.
So formula~\eqref{eq:Kinv-rec} holds.
\end{proof}

\subsection{Special Rim Hook Tableaux}
\label{subsec:SRHT}

In the particular case where $\beta$ is a partition 
(meaning that the parts of $\beta$ are weakly decreasing),
we can give a formula for $\Ki^{-1}(\alpha,\beta)$ involving 
special rim hook tableaux. We first review the analogous formula, 
due to E\u{g}ecio\u{g}lu and Remmel~\cite{eg-rem},
for the inverse of the original Kostka matrix.

Recall that we draw the Ferrers diagram of an integer partition $\mu$
with the longest row at the bottom. A \emph{special rim hook} 
of length $\ell$ in the diagram of $\mu$ is a sequence of $\ell$ cells
that starts in the leftmost column and moves right or down at each step. 
The \emph{sign} of a rim hook is $+1$ (resp. $-1$) if the rim hook
occupies an odd (resp. even) number of rows.
Given partitions $\lambda$ and $\mu$,
a \emph{special rim hook tableau} (SRHT) of \emph{shape} $\mu$
and \emph{type} $\lambda$ is a decomposition of the diagram of $\mu$
into a disjoint union of special rim hooks such that the weakly decreasing 
rearrangement of the list of rim hook lengths is $\lambda$. 
The \emph{sign} of a SRHT is the product of the signs of its rim hooks.
E\u{g}ecio\u{g}lu and Remmel~\cite{eg-rem} proved that
$\K^{-1}(\lambda,\mu)$ is the sum of the signs of all SRHT
of shape $\mu$ and type $\lambda$. For more details and an abacus-based
proof of this formula, see~\cite[\S 10.16]{loehr-comb}. 

\begin{exam}\label{ex:SRHT}
The diagram below shows all SRHT of shape $\mu=(4,3,3)$.
\begin{center}
%\epsfig{file=srht.pdf,scale=0.7}
\includegraphics[scale=0.7]{Figures/srht.pdf}
\end{center} 
The first three tableaux have sign $+1$ and 
types $433$, $541$, and $622$, respectively.
The next three tableaux have sign $-1$ and 
types $442$, $532$, and $631$, respectively.
We therefore obtain the six nonzero entries in column $\mu$ of $\K^{-1}$. 
The same information can be found by taking the coefficients
of $h_{\lambda}$ in the (commutative) Jacobi--Trudi
expansion of the Schur function $s_{433}$:
\begin{align*}
 s_{433} =\det\left[\begin{array}{ccc}
 h_4 & h_5 & h_6 \\
 h_2 & h_3 & h_4 \\
 h_1 & h_2 & h_3 \end{array}\right] 
 & = h_4h_3h_3+h_5h_4h_1+h_6h_2h_2-h_4h_4h_2-h_5h_2h_3-h_6h_3h_1
\\ &= h_{433}+h_{541}+h_{622}-h_{442}-h_{532}-h_{631}.
\end{align*}
\end{exam}


To state our formula for $\Ki^{-1}(\alpha,\mu)$ where
$\mu$ is a partition and $\alpha$ is a composition, 
we introduce the notions of \emph{total content} and \emph{content}
for special rim hook tableaux. 
Let $S$ be a SRHT of partition shape $\mu=(\mu_1,\ldots,\mu_m)$, 
where some parts at the end might be zero. For $1\leq i\leq m$,
let the special rim hook starting in row $i$ have length $a_i$
and end in row $r_i$; if no rim hook starts in row $i$, let
$a_i=0$ and $r_i=i$. The \emph{total content} of $S$ is the
rearrangement of the rim hook lengths $a_1,\ldots,a_m$ 
produced as follows. Start with the empty list;
for $i=1,2,\ldots,m$, insert $a_i$ into position $r_i$ of the current list.
The \emph{content} of $S$ is the strict composition 
obtained by deleting all zero parts from the total content of $S$.

\begin{exam}
The following diagram shows four SRHT of shape $\mu=[3,3,3,3,2]$.
\begin{center}
%\epsfig{file=srht2.pdf,scale=0.7}
\includegraphics[scale=0.7]{Figures/srht2.pdf}
\end{center} 
From left to right, these SRHT have total content
$[42530]$, $[45302]$, $[34511]$, and $[75200]$.
In more detail, the first SRHT has $(a_1,\ldots,a_5)=(2,4,0,3,5)$ and
$(r_1,\ldots,r_5)=(1,1,3,3,3)$. The total content algorithm builds
the lists $[2]$, $[4,2]$, $[4,2,0]$, $[4,2,3,0]$, and $[4,2,5,3,0]$. 
The examples show that we \emph{cannot} compute the content of an SRHT
by scanning the boxes in the diagram in a predetermined order
and recording the lengths of the rim hooks as they are encountered.

Each SRHT shown above corresponds to a term in
the noncommutative Jacobi--Trudi determinant
{\small
\[
 \imm_{33332}= \detd\left[\begin{array}{ccccc}
\nh_3 & \nh_4 & \nh_5 & \nh_6 & \nh_7 \\
\nh_2 & \nh_3 & \nh_4 & \nh_5 & \nh_6 \\
\nh_1 & \nh_2 & \nh_3 & \nh_4 & \nh_5 \\
\nh_0 & \nh_1 & \nh_2 & \nh_3 & \nh_4 \\
 0 & 0 & \nh_0 & \nh_1 & \nh_2 
\end{array}\right]. \]
}
For example, the first SRHT corresponds to choosing 
$\nh_4$ from row $1$, $\nh_2$ from row~$2$, $\nh_5$ from row $3$,
$\nh_3$ from row $4$, and $\nh_0=1$ from row $5$. As we prove
in the next theorem, the total content of the SRHT agrees with the 
sequence of $\nh_k$'s multiplied together in top-to-bottom order.
We remark in passing that using a left-to-right determinant
expansion would have led to a simpler content rule where
we simply read the rim hook lengths from bottom to top, but
this alternate determinant does not equal $\imm_{\mu}$ in general.
\end{exam}


\begin{theorem}\label{thm:SRHT-QSym}
For all compositions $\alpha$ and partitions $\mu$,
$\Ki^{-1}(\alpha,\mu)$ is the sum of the signs of
all special rim hook tableaux of shape $\mu$ and content $\alpha$.
\end{theorem}
\begin{proof}
For all lists $v,w\in\Z^m$ such that $v$ is weakly decreasing,
let $C(w,v)$ be the sum of the signs of all SRHT
of shape $v$ and total content $w$. (This is zero if $v$ or $w$
has a negative entry.) We first prove that $C(w,v)=D(w,v)$
for all such lists $v,w$. It suffices to check that the quantities
$C(w,v)$ satisfy the recursion and initial condition
in Theorem~\ref{thm:detd-rec}\ref{theo4.9_a}. Note here that if $v\in\Z^m$ is
weakly decreasing, then all the related lists $v^{(i)}$
appearing in~\eqref{eq:detd-rec} are also weakly decreasing.

When $m=1$, the initial condition $C(w,v)=\chi(w=v)$ holds because
there is exactly one SRHT of shape $(v_1)$, which consists of a
single positive rim hook of length $v_1$. Now suppose $m>1$,
and fix $v,w\in\Z^m$ with $v$ weakly decreasing.
Consider a particular SRHT $S$ counted by $C(w,v)$.
Let the special rim hook starting in row $m$ of $S$ 
end in row $i$. This rim hook has sign $(-1)^{m-i}=(-1)^{i+m}$.
Deleting this rim hook and the cells it occupies, we
obtain a smaller SRHT $S'$ such that $\sgn(S)=(-1)^{i+m}\sgn(S')$.
One readily checks that since $S$ has shape $v$, $S'$ has shape $v^{(i)}$.
Also since $S$ has total content $w$, $S'$ has total content $w^{[i]}$.
Finally, $w_i$ is the length of the deleted rim hook, which is
$v_i+m-i$ since this rim hook starts in column $1$ of row $m$
and ends in column $v_i$ of row $i$. Conversely, by adding a rim
hook of this form above a smaller SRHT, we see that every $S$ counted 
by $C(w,v)$ arises in this way from a unique choice of $i$ with $w_i=v_i+m-i$ 
and a unique $S'$ counted by $C(w^{[i]},v^{(i)})$.
Thus, recursion~\eqref{eq:detd-rec} holds with $D$ replaced by $C$.
It follows by induction that $C(w,v)=D(w,v)$ for all $v,w\in\Z^m$
such that $v$ is weakly decreasing.

Now for all compositions $\alpha$ and partitions $\mu$ where
$\mu$ has $m$ parts, Theorem~\ref{thm:detd-rec}\ref{theo4.9_b} says
\[
 \Ki^{-1}(\alpha,\mu)=\sum_{\substack{w\in\Z^m:\\
 P(w)=[\alpha]}} C(w,[\mu]). 
 \]
Each SRHT of total content $w$ has content $P(w)$ (with trailing zeros
deleted). So this expression for $\Ki^{-1}(\alpha,\mu)$ reduces
to the sum of the signs of all SRHT of shape $\mu$ and content $\alpha$,
as needed.
\end{proof}

\begin{rema}
In contrast to the situation for partition diagrams,
we have found no satisfactory way of decomposing composition
diagrams into rim hooks to give combinatorial objects satisfying
the recursion in Theorem~\ref{thm:detd-rec}. Starting with
the diagram of $\beta\in\Comp_m$, one would have to remove $\beta_i+m-i$ cells
(for some $i$) in a way that leaves the diagram of $\beta^{(i)}$.
Various methods for drawing the diagram or removing these cells
all seem to produce substructures consisting of diagrams and/or
rim hooks that are disconnected. 
\end{rema}

\section{\texorpdfstring{$t$}{t}-Analogues}
\label{sec:t-analogue}

The original Kostka matrix (\S \ref{subsec:kostka}) has
a $t$-analogue that gives the expansion of Schur symmetric
functions in terms of the Hall--Littlewood symmetric polynomials
$P_{\mu}$~\cite[Ch. III]{macd}. Lascoux and Sch\"utzenberger~\cite{LS-charge}
found a combinatorial formula for the entries of this
matrix based on the \emph{charge} statistic. Specifically,
the $t$-analogue of the Kostka number $\K(\lambda,\mu)$ is
the sum of $t^{\charge(S)}$ over all semistandard tableaux $S$ 
of shape $\lambda$ and content $\mu$. For more details on charge,
see~\cite[III.6]{macd} or~\cite[\S 3.3]{LSW-trans}.
Carbonara~\cite{carbonara} found a combinatorial formula for
the inverse of the $t$-Kostka matrix as a sum over certain 
tournaments weighted by an appropriate power of $t$. 
See~\cite[\S 3.4]{LSW-trans} for a brief summary of this formula.

In this section, we develop $t$-analogues of the inverse Kostka 
operators, the immaculate Kostka matrix, the inverse of the immaculate Kostka 
matrix, and related concepts. The basic idea is to replace each raising
operator $R_{i,j}$ by $tR_{i,j}$, where $t$ is a formal variable,
and trace the powers of $t$ through all the combinatorial constructions.

\subsection{\texorpdfstring{$t$}{t}-Analogues of Inverse Kostka Operators}
\label{subsec:t-operators}

Fix a positive integer $m$. We use the vector space $V$ and its
subspace $W$ from~\S \ref{sec:inv-kostka-operators}. For $2\leq j\leq m$,
define $[T_j]_t:V\rightarrow V$ by $[T_j]_t=\prod_{i=1}^{j-1} (I-tR_{i,j})$.
Define $[U_j]_t:W\rightarrow W$ by $[U_j]_t=P\circ [T_j]_t|_W$.
Define the \emph{$t$-inverse Kostka operators} 
$[T]_t=\prod_{j=2}^m [T_j]_t$ and $[U]_t=P\circ [T]_t|_W$. 
The rules for how these operators act
on generalized composition diagrams are the same as before. The only
new ingredient is that whenever a box moves into a lower row due
to the application of a raising operator, the coefficient of the
resulting object is multiplied by $t$. However, when boxes fall
into a row due to application of $P$, no new $t$-factors are introduced.

The inverse of $[T_j]_t$ is given by formula~\eqref{eq:invert-Tj}
with the power $t^{e_{j-1}+\cdots+e_2+e_1}$ inserted inside the sums
on the right side. Theorem~\ref{thm:invert-Uj} holds for the
$t$-analogues of $U_j$ and $U_j'$, with the same proof. We need only
observe that the involution preserves the $t$-power (since changing
the sign of a moved $j$ does not affect how many boxes are moved by a 
raising operator), and the fixed point $w$ is not multiplied by any $t$'s.
Similarly, Lemma~\ref{lem:U-facz} is still true for the $t$-analogues,
so that $[U]_t=\prod_{j=2}^m [U_j]_t$. 

\begin{exam}
In Example~\ref{ex:T3-U3}, 
$[U_3]_t([14231])= [14231]-t[24131]-t[15131]+t^2[25310]$.
In Example~\ref{ex:T3i-U2i}, 
$[U_2]_t^{-1}([1121])=[1121]+t[2210]+t^2[3110]+t^3[4100]+t^4[5000]$. 
In Example~\ref{ex:U3'U3}, the seven positive diagrams shown have
$t$-weights $1$, $t$, $t^2$, $t^2$, $t$, $t^2$, $t^2$ (respectively).
The six negative diagrams have the same $t$-weights as their 
matches under the involution. 
\end{exam}

\begin{rema}
In important recent work~\cite{BMPS19,BMPS20}, Blasiak, Morse, Pun, and
Summers obtain detailed information about the $k$-Schur symmetric functions
by applying certain products of $t$-raising operators to Schur functions, 
creation operators, etc. These products are indexed by root ideals (or 
their complements) in the poset $\{(i,j):1\leq i<j\leq m\}$. 
It would be interesting to see if their ideas carry over to give new bases
or other combinatorial information about $\NSym$ and $\QSym$.
\end{rema}

\subsection{\texorpdfstring{$t$}{t}-Analogue of the Immaculate Kostka Matrix}
\label{subsec:t-immac}

The tableau description of the Kostka operator $T^{-1}:V\rightarrow V$
(\S \ref{subsec:comb-Tinv})
has the following $t$-analogue. Given a basis vector 
$v=[a_1,\ldots,a_m]\in V$, $[T]_t^{-1}(v)$ is a 
$t$-weighted sum of all filled diagrams $D$ satisfying conditions~\ref{theo3.6_a}, \ref{theo3.6_b}, 
\ref{theo3.6_c}~in Theorem~\ref{thm:Tinv}. The power of $t$ for a given diagram $D$
is the number of times an entry $j$ in $D$ appears below row $j$.
This holds since the only way a $j$ initially in row $j$ can move
to a lower row is when it is moved there by a raising operator $tR_{i,j}$.

The $t$-analogue of the Kostka operator $U^{-1}:W\rightarrow W$ is more
interesting since the action of $P$ (the falling operation) does not
introduce new $t$'s. In this case, we know (\S \ref{subsec:comb-Uinv}) that 
$U^{-1}(v)$ is the formal sum of the shapes of all dual immaculate tableaux 
with content $v$. Given such a tableau $D$ with values $a_1<a_2<\cdots<a_k$
in column $1$, we find the $t$-power of $D$ as follows.
For $1\leq i\leq k$, count the number of occurrences of $a_i$ in $D$
below row $i$. Add to these counts the number of occurrences of symbols $j$
in $D$ such that there is no $j$ in column $1$ of $D$. 
Denote the total count by $\wt(D)$. 

\begin{exam} We compute the weight of the tableau $D$ 
shown here:
\[
D=\tableau{5&5\\3&4&\boldsymbol{5}\\2&\boldsymbol{3}\\1&\boldsymbol{2}&4}\;.
\]
Note that the first column 
contains $1<2<3<5$, so the labels in bold in the diagram 
each contribute to the weight of $D$. Additionally, since there is 
no 4 in the first column of $D$, the two 4's in the diagram each 
contribute to the weight of $D$. Thus, $\wt(D)=5$. 
This corresponds to the $5$ raising operators used in 
Figure~\ref{fig:seq} to convert the filled diagram of
$v=[1,2,2,2,3]$ to $D$.
\end{exam}

\begin{theorem}
For all basis vectors $v$ of $W$, $[U]_t^{-1}(v)=\sum_D t^{\wt(D)}\sh(D)$,
where we sum over all dual immaculate tableaux $D$ of content $v$.
\end{theorem}
\begin{proof}
Let $D$ be a dual immaculate tableau with content $v$, maximum entry $M$,
and first column $a_1<a_2<\cdots<a_k$. It suffices to show that $\wt(D)$
is the number of times a raising operator was applied in the passage 
from the initial filled diagram of $v$ to $D$. This process was described
in the proof of Theorem~\ref{thm:Uinv} in~\S \ref{subsec:comb-Uinv}.
First, $a_1=1$, and all occurrences of $1$ in $D$ are in row $1$,
so the $1$s in $D$ contribute nothing to $\wt(D)$.
Second, when the $t$-version of $U_2^{-1}$ acts,
every occurrence of every symbol in $\{2,3,\ldots,a_2-1\}$ is moved
by a raising operator from row $2$ to row $1$. Also, any occurrences
of $a_2$ below row $2$ must arrive there by a raising operator.
Third, when the $t$-version of $U_3^{-1}$ acts,
every occurrence of every symbol in $\{a_2+1,\ldots,a_3-1\}$ is moved
by a raising operator from row $3$ to lower rows. Also, any occurrences
of $a_3$ below row $3$ must arrive there by a raising operator.
We continue similarly. If $M>a_k$, then at the end the
$t$-version of $U_{k+1}^{-1}$ moves all occurrences of
$a_k+1$, then $a_k+2,\ldots,M$ from row $k+1$ to lower rows 
via raising operators. We see from this description that $\wt(D)$ does
indeed count the total number of raising operators applied to reach $D$. 
\end{proof}

\begin{exam} 
The tableaux arising from the computation of $U^{-1}([2,1,2])$ 
in Example~\ref{ex:Uinv} are shown below, along with their $t$-weights. 
\[\renewcommand{\arraycolsep}{2pt}\begin{array}{@{}ccccccccc@{}} 
\tableau{3&3\\2\\1&1}\ & 
\tableau{\\3&3\\1&1&2}\ &
\tableau{\\2&3\\1&1&3}\ & 
\tableau{\\3\\1&1&2&3}\ &
\tableau{\\2\\1&1&3&3}\ &
\tableau{3\\2&3\\1&1}\ &
\tableau{3\\2\\1&1&3}\ &
\tableau{\\2&3&3\\1&1}\ & 
\tableau{\\\\1&1&2&3&3}\\[12pt]
t^0 & t^1 & t^2 & t^2 & t^2 &
t^1 & t^1 & t^2 &t^3 
\end{array}\]
Thus,
$[U]_t^{-1}([2,1,2])=
 [212]+(t^2+t)[320]+2t^2[410]+t[221]+t[311]+t^2[230]+t^3[500]$.
\end{exam}

We now define a \emph{$t$-analogue of the immaculate Kostka matrix}.
For any compositions $\alpha,\beta$,
let $\Ki(\alpha,\beta;t)=\sum_D t^{\wt(D)}$, where we sum
over all dual immaculate tableaux of shape $\alpha$ and content $\beta$.
Using this matrix and its inverse in~\eqref{eq:Kostka-QSym} 
and~\eqref{eq:invKostka-QSym},
we obtain $t$-analogues of the immaculate basis of
$\NSym$ and the dual immaculate basis of $\QSym$:
\[ \imm_{\beta}(t) =\sum_{\alpha}\Ki^{-1}(\alpha,\beta;t)\nh_{\alpha}; 
\qquad \dimm_{\alpha}(t)=\sum_{\beta} \Ki(\alpha,\beta;t)M_{\beta}. \]
We can also define $t$-analogues of the interpolating bases
from~\S \ref{subsec:interp-bases}. In fact, by using a different
formal variable $t_j$ for each operator $U_j$, we could obtain
multivariate analogues for these bases and the associated transition matrices.


\subsection{\texorpdfstring{$t$}{t}-Analogue of the Inverse Immaculate Kostka Matrix}
\label{subsec:t-immac-inv}

Formula~\eqref{eq:tourn-in-V} expresses the operator $T$ as a sum
over tournaments $\tau\in \T_m$ of certain products of raising operators.
We obtain the analogous formula for $[T]_t$ by replacing each
$R_{i,j}$ in~\eqref{eq:tourn-in-V} by $tR_{i,j}$. The total power
of $t$ in the term indexed by $\tau\in \T_m$ is then 
$\wt(\tau)=\sum_{1\leq i<j\leq m} \tau(i,j)$. We obtain $t$-analogues
of other formulas in~\S \ref{subsec:tourn-invK} by replacing $\sgn(\tau)$
by $\sgn(\tau)\wt(\tau)$. In particular, we deduce from
Theorem~\ref{thm:Kinv-tourn} the following
combinatorial formula for the entries in the inverse of the immaculate
$t$-Kostka matrix.

\begin{theorem}\label{thm:tKinv-tourn}
For all compositions $\alpha,\beta$ where $\beta$ has $m$ parts, 
\[
\Ki^{-1}(\alpha,\beta;t) 
=\sum_{\tau\in \T_m(\alpha,\beta)} \sgn(\tau)\wt(\tau).
\] 
\end{theorem}

However, unlike the $t=1$ case, we \emph{cannot} replace the sum
in Theorem~\ref{thm:tKinv-tourn} by a sum over transitive tournaments.
This is because the involution in the proof of Theorem~\ref{thm:Kinv-trans}
does not preserve the $t$-power, in general, as seen in the
example below. Consequently, there is no $t$-analogue of 
the noncommutative determinant formula from Theorem~\ref{thm:Kinv-JT}
or the special rim hook tableau formula from Theorem~\ref{thm:SRHT-QSym}.
Although the tournament model involves more objects than
these other models, we need tournaments to make the $t$-analogue work.

\begin{exam}
From the tournaments in Example~\ref{ex:tourn}, we compute all
entries in column $[3,1,3]$ of the $t$-analogue of $\Ki^{-1}$:
row $313$ has $1$,
row $322$ has $-t$,
row $412$ has $t^2-t$,
row $421$ has $t^2$,
row $43$ has $-t$,
row $52$ has $t^2$,
row $511$ has $-t^3$,
and all other entries in this column are zero. 
The tournaments contributing to $\Ki^{-1}(412,313;t)$
are the two non-transitive tournaments in $\T_3$,
and we see that the $t$-powers of these two tournaments are unequal. 
\end{exam}


 
\longthanks{The authors thank the two anonymous referees for 
their helpful comments.}

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