\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_{i0$; } \\
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_{i0$.
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 $i1$. 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 $ia_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)*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)**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 $ik} \tau(k,j)
-\sum_{ik} \tau(k,j)+\sum_{j:\,jr$ 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 $iw_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_{iw_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 ia_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*