\documentclass[finalversion]{FPSAC2018}
\articlenumber{74}


\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{obs}[thm]{Observation}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definition}
\newtheorem{quest}[thm]{Question}
\newtheorem{prob}[thm]{Problem}
\newtheorem{example}[thm]{Example}


\usepackage{enumerate}
\usepackage{tikz}
\usepackage{tabularx}
\usepackage{tabmac_avi}


\numberwithin{equation}{section}

\newcommand{\sn}{\mathfrak{S}_n}
\newcommand{\sr}{\mathfrak{S}_r}
\newcommand{\mfs}[1]{\mathfrak{S}_{#1}}
\newcommand{\zsn}{\mathbb{Z}[\sn]}
\newcommand{\cx}{\mathbb{C}[x]}
\newcommand{\cxn}{\mathbb{C}[x_{1,1},\dotsc,x_{n,n}]}
\newcommand{\zxn}{\mathbb{Z}[x_{1,1},\dotsc,x_{n,n}]}
\newcommand{\cqq}{\mathbb{C}[\qp12, \qm12]}
\newcommand{\zqq}{\mathbb{Z}[\qp12, \qm12]}
\newcommand{\nqq}{\mathbb{N}[\qp12, \qm12]}
\newcommand{\czn}{\cqq \langle z_{1,1},\dotsc,z_{n,n} \rangle}
\newcommand{\cz}{\cqq \langle z \rangle}
\newcommand{\cyr}{\mathbb{C}[y_{1,1},\dotsc,x_{r,r}]}
\newcommand{\csn}{\mathbb{C}[\sn]}


\newcommand{\Ie}{{I, \emptyset}}
\newcommand{\eJ}{{\emptyset, J}}
\newcommand{\Je}{{J, \emptyset}}
\newcommand{\eI}{{\emptyset, I}}
\newcommand{\IIJJ}{{I, J}}

\newcommand{\wo}{w_0}
\newcommand{\woi}{w_0^I}
\newcommand{\woj}{w_0^J}
\newcommand{\wok}{w_0^K}
\newcommand{\wokp}{w_0^{K'}}

\newcommand{\etu}{\epsilon_{t,u}}
\newcommand{\etv}{\epsilon_{t,v}}
\newcommand{\etz}{\epsilon_{t,z}}
\newcommand{\eut}{\epsilon_{u,t}}
\newcommand{\euv}{\epsilon_{u,v}}
\newcommand{\euw}{\epsilon_{u,w}}
\newcommand{\euy}{\epsilon_{u,y}}
\newcommand{\euz}{\epsilon_{u,z}}
\newcommand{\evu}{\epsilon_{v,u}}
\newcommand{\evw}{\epsilon_{v,w}}
\newcommand{\evy}{\epsilon_{v,y}}
\newcommand{\evz}{\epsilon_{v,z}}
\newcommand{\ewy}{\epsilon_{w,y}}
\newcommand{\ewz}{\epsilon_{w,z}}
\newcommand{\eyz}{\epsilon_{y,z}}
\newcommand{\ezu}{\epsilon_{z,u}}
\newcommand{\ezw}{\epsilon_{z,w}}
\newcommand{\ezy}{\epsilon_{z,y}}
\newcommand{\eeu}{\epsilon_{e,u}}
\newcommand{\eev}{\epsilon_{e,v}}
\newcommand{\eew}{\epsilon_{e,w}}
\newcommand{\qtu}{q_{t,u}}
\newcommand{\qtv}{q_{t,v}}
\newcommand{\qtz}{q_{t,z}}
\newcommand{\quv}{q_{u,v}}
\newcommand{\quw}{q_{u,w}}
\newcommand{\quy}{q_{u,y}}
\newcommand{\qvu}{q_{v,u}}
\newcommand{\qvw}{q_{v,w}}
\newcommand{\qvy}{q_{v,y}}
\newcommand{\qvz}{q_{v,z}}
\newcommand{\qyw}{q_{y,w}}
\newcommand{\qwy}{q_{w,y}}
\newcommand{\qwz}{q_{w,z}}
\newcommand{\qzw}{q_{z,w}}
\newcommand{\qeu}{q_{e,u}}
\newcommand{\qet}{q_{e,t}}
\newcommand{\qev}{q_{e,v}}
\newcommand{\qew}{q_{e,w}}
\newcommand{\qitu}{q_{t,u}^{-1}}
\newcommand{\qitv}{q_{t,v}^{-1}}
\newcommand{\qitw}{q_{t,w}^{-1}}
\newcommand{\qity}{q_{t,y}^{-1}}
\newcommand{\qiut}{q_{u,t}^{-1}}
\newcommand{\qiuv}{q_{u,v}^{-1}}
\newcommand{\qiuy}{q_{u,y}^{-1}}
\newcommand{\qiuw}{q_{u,w}^{-1}}
\newcommand{\qiuz}{q_{u,z}^{-1}}
\newcommand{\qivu}{q_{v,u}^{-1}}
\newcommand{\qivw}{q_{v,w}^{-1}}
\newcommand{\qivy}{q_{v,y}^{-1}}
\newcommand{\qivz}{q_{v,z}^{-1}}
\newcommand{\qiyw}{q_{y,w}^{-1}}
\newcommand{\qiyz}{q_{y,z}^{-1}}
\newcommand{\qizw}{q_{z,w}^{-1}}
\newcommand{\qizy}{q_{z,y}^{-1}}
\newcommand{\qiet}{q_{e,t}^{-1}}
\newcommand{\qieu}{q_{e,u}^{-1}}
\newcommand{\qiev}{q_{e,v}^{-1}}
\newcommand{\qiew}{q_{e,w}^{-1}}
\newcommand{\qiey}{q_{e,y}^{-1}}
\newcommand{\qiez}{q_{e,z}^{-1}}
\newcommand{\qp}[2]{q^{\frac{#1}{#2}}}
\newcommand{\qm}[2]{q^{\negthinspace\Bar\,\frac{#1}{#2}}}
\newcommand{\qdiff}{\qp12 - \qm12}

\newcommand{\wT}{\widetilde T} 
\newcommand{\wTp}{\widetilde T'}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\wR}[1]{\widetilde R_{#1}}
\newcommand{\wS}[1]{\widetilde S_{#1}} 
\newcommand{\wSp}{\widetilde S'}

\newcommand{\hnq}{H_n(q)}
\newcommand{\hrq}{H_r(q)}
%\newcommand{\anq}{\mathcal{A}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\anq}{\mathcal{A}(n,q)}
\newcommand{\arq}{\mathcal{A}(r;q)}
%\newcommand{\arnq}{\mathcal{A}_r(n;q)}
\newcommand{\arnq}{\mathcal{A}_r}
\newcommand{\annq}{\mathcal{A}_n(n;q)}
%\newcommand{\annnq}{\mathcal{A}_{[n],[n]}(n;q)}
\newcommand{\Ann}{\mathcal{A}_{[n],[n]}}
\newcommand{\annnq}{\mathcal{A}_{[n],[n]}}
\newcommand{\anmnq}{\mathcal{A}_{[n],M}(n;q)}
\newcommand{\amnnq}{\mathcal{A}_{M,[n]}(n;q)}
\newcommand{\alnnq}{\mathcal{A}_{L,[n]}(n;q)}
%\newcommand{\almnq}{\mathcal{A}_{L,M}(n;q)}
\newcommand{\AnM}{\mathcal{A}_{[n],M}}
\newcommand{\ALM}{\mathcal{A}_{L,M}}
\newcommand{\amlnq}{\mathcal{A}_{M,L}(n;q)}
\newcommand{\arrrq}{\mathcal{A}_{[r],[r]}(r;q)}
\newcommand{\alrrq}{\mathcal{A}_{L,[r]}(r;q)}
\newcommand{\armrq}{\mathcal{A}_{[r],M}(r;q)}

\newcommand{\Hpie}{H'_{\smash{\Ie}}} 
\newcommand{\Hie}{H_\Ie} 
\newcommand{\Hpej}{H'_{\smash\eJ}} 
\newcommand{\Hej}{H_\eJ} 
\newcommand{\Hpje}{H'_\Je} 
\newcommand{\Hje}{H_\Je} 
\newcommand{\Hpei}{H'_\eI} 
\newcommand{\Hei}{H_\eI} 
\newcommand{\Hij}{H_{I,J}} 
\newcommand{\Hpij}{H'_{I,J}} 

\newcommand{\Wiep}{W^{I,\emptyset}_+}
\newcommand{\Wiem}{W^{I,\emptyset}_-}
\newcommand{\WIkpem}{(W_I)^{K',\emptyset}_-}
\newcommand{\WIekpm}{(W_I)^{\emptyset,K'}_-}
\newcommand{\WIekpp}{(W_I)^{\emptyset,K'}_+}
\newcommand{\WIenpm}{(W_I)^{\emptyset,N'}_-}
\newcommand{\WJiem}{(W_J)^{I,\emptyset}_-}
\newcommand{\WJkem}{(W_J)^{K,\emptyset}_-}
\newcommand{\WJkep}{(W_J)^{K,\emptyset}_+}
\newcommand{\WJnem}{(W_J)^{N,\emptyset}_-}
\newcommand{\Wjep}{W^{J,\emptyset}_+}
\newcommand{\Wjem}{W^{J,\emptyset}_-}
\newcommand{\Wkep}{W^{K,\emptyset}_+}
\newcommand{\Wkem}{W^{K,\emptyset}_-}
\newcommand{\Weip}{W^{\emptyset,I}_+}
\newcommand{\Weim}{W^{\emptyset,I}_-}
\newcommand{\WJeim}{(W_J)^{\emptyset,I}_-}
\newcommand{\WJekm}{(W_J)^{\emptyset,K}_-}
\newcommand{\WJenm}{(W_J)^{\emptyset,N}_-}
\newcommand{\Wejp}{W^{\emptyset,J}_+}
\newcommand{\Wejm}{W^{\emptyset,J}_-}
\newcommand{\Wekp}{W^{\emptyset,K}_+}
\newcommand{\Wekpp}{W^{\emptyset,K'}_+}
\newcommand{\Wekm}{W^{\emptyset,K}_-}
\newcommand{\Wekpm}{W^{\emptyset,K'}_-}
\newcommand{\Wijp}{W^{I,J}_+}
\newcommand{\Wijm}{W^{I,J}_-}

\newcommand{\Rie}[1]{R_{#1}^{I,\emptyset}}
\newcommand{\Rpie}[1]{R^{\prime\,I,\emptyset}_{#1}}
\newcommand{\Rej}[1]{R_{#1}^{\emptyset,J}}
\newcommand{\Rpej}[1]{R^{\prime\,\emptyset,J}_{#1}}
\newcommand{\Rij}[1]{R_{#1}^{I,J}}
\newcommand{\Rpij}[1]{R^{\prime\,I,J}_{#1}}
\newcommand{\wRie}[1]{\wR_{#1}^{I,\emptyset}}
\newcommand{\wRpie}[1]{\wR^{\prime\,I,\emptyset}_{#1}}
\newcommand{\wRej}[1]{\wR_{#1}^{\emptyset,J}}
\newcommand{\wRpej}[1]{\wR^{\prime\,\emptyset,J}_{#1}}
\newcommand{\wRij}[1]{\wR_{#1}^{I,J}}
\newcommand{\wRpij}[1]{\wR^{\prime\,I,J}_{#1}}
\newcommand{\Sie}[1]{S_{#1}^{I,\emptyset}}
\newcommand{\Spie}[1]{S^{\prime\,I,\emptyset}_{#1}}
\newcommand{\Sej}[1]{S_{#1}^{\emptyset,J}}
\newcommand{\Spej}[1]{S^{\prime\,\emptyset,J}_{#1}}
\newcommand{\Sij}[1]{S_{#1}^{I,J}}
\newcommand{\Spij}[1]{S^{\prime\,I,J}_{#1}}
\newcommand{\wSie}[1]{\wS_{#1}^{I,\emptyset}}
\newcommand{\wSpie}[1]{\wS^{\prime\,I,\emptyset}_{#1}}
\newcommand{\wSej}[1]{\wS_{#1}^{\emptyset,J}}
\newcommand{\wSpej}[1]{\wS^{\prime\,\emptyset,J}_{#1}}
\newcommand{\wSij}[1]{\wS_{#1}^{I,J}}
\newcommand{\wSpij}[1]{\wS^{\prime\,I,J}_{#1}}
\newcommand{\Qie}[1]{Q_{#1}^{I,\emptyset}}
\newcommand{\Qej}[1]{Q_{#1}^{\emptyset,J}}
\newcommand{\Qij}[1]{Q_{#1}^{I,J}}
\newcommand{\pie}[1]{p_{#1}^{I,\emptyset}}
\newcommand{\pje}[1]{p_{#1}^{J,\emptyset}}
\newcommand{\pei}[1]{p_{#1}^{\emptyset,I}}
\newcommand{\pej}[1]{p_{#1}^{\emptyset,J}}
\newcommand{\pij}[1]{p_{#1}^{I\ntnsp,J}}
\newcommand{\pji}[1]{p_{#1}^{J\ntnsp,I}}
\newcommand{\rie}[1]{r_{#1}^{I\ntnsp,\emptyset}}
\newcommand{\rje}[1]{r_{#1}^{J\ntnsp,\emptyset}}
\newcommand{\rei}[1]{r_{#1}^{\emptyset,I}}
\newcommand{\rej}[1]{r_{#1}^{\emptyset,J}}
\newcommand{\rij}[1]{r_{#1}^{I\ntnsp,J}}
\newcommand{\rji}[1]{r_{#1}^{J\ntnsp,I}}
\newcommand{\redexp}[2]{s_{i_{#1}} \ntnsp \cdots s_{i_{#2}}}

\newcommand{\imm}[1]{\mathrm{Imm}_{#1}}
\newcommand{\immlm}[1]{\mathrm{Imm}_{#1}^{L,M}}
\newcommand{\immln}[1]{\mathrm{Imm}_{#1}^{L,[n]}}
\newcommand{\immlr}[1]{\mathrm{Imm}_{#1}^{L,[r]}}
\newcommand{\immnm}[1]{\mathrm{Imm}_{#1}^{[n],M}}
\newcommand{\immrm}[1]{\mathrm{Imm}_{#1}^{[r],M}}

\newcommand{\sumsb}[1]{\sum_{\substack{#1}}}  %%%for multi-line sums
\newcommand{\inv}{\textsc{inv}}
\newcommand{\rinv}{\textsc{rinv}}
\newcommand{\rbinv}{\raisebox{1mm}{\textsc{rinv}}}

\newcommand{\defeq}{:=} 
\newcommand{\dfct}{\textsc{d}}
\newcommand{\dnc}{\textsc{dnc}}
\newcommand{\dc}{\textsc{dc}}
\newcommand{\pnc}{\textsc{pnc}}
\newcommand{\spn}{\mathrm{span}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\wgt}{\mathrm{wgt}}
\newcommand{\type}{\mathrm{type}}
\newcommand{\incross}{\textsc{invnc}}
\newcommand{\cdncross}{\textsc{cdnc}}
\newcommand{\cross}{\textsc{c}}
\newcommand{\pavoiding}{$3412$-avoiding, $4231$-avoiding }
\newcommand{\avoidsp}{avoids the patterns $3412$ and $4231${}}
\newcommand{\avoidp}{avoid the patterns $3412$ and $4231${}}
\newcommand{\avoidingp}{avoiding the patterns $3412$ and $4231${}}
\newcommand{\theps}{the patterns $3412$ and $4231${}}
\newcommand{\ul}[1]{\underline{#1}}  
\newcommand{\ssec}[1]{\subsection{#1}{$\negthinspace$}}

\newcommand{\tr}{{\negthickspace \top \negthickspace}}
\newcommand{\ntnsp}{\negthinspace}
\newcommand{\ntksp}{\negthickspace}
\newcommand{\nTksp}{\negthickspace\negthickspace}
\newcommand{\nTtksp}{\negthickspace\negthickspace\negthickspace}
\newcommand{\nTTksp}{\negthickspace\negthickspace\negthickspace
	\negthickspace}
\newcommand{\nTTtksp}{\negthickspace\negthickspace\negthickspace
	\negthickspace\negthickspace}
	
\newcommand{\kbar}[2]{\varphi_#1(#2)}

\newcommand{\hnqq}{H_n(q_2,q_4)}
\newcommand{\anqq}{\mathcal{A}(n;q_2,q_4)}
\newcommand{\arnqq}{\mathcal{A}_r(n;q_2,q_4)}
\newcommand{\almnqq}{\mathcal{A}_{L,M}(n;q_2,q_4)}
\newcommand{\annnqq}{\mathcal{A}_{[n],[n]}(n;q_2,q_4)}
\newcommand{\aT}{\widetilde{\mathcal{T}}}
\newcommand{\q}[3]{q_{#1,#2,#3}}
\newcommand{\qi}[3]{q^{-1}_{#1,#2,#3}}
\newcommand{\qsum}{q_2 + q_4}
\newcommand{\qprod}{-q_2q_4}
\newcommand{\qprodi}{(-q_2q_4)^{-1}}


\newcommand{\oglnc}{{\mathcal O}(GL_n)}
\newcommand{\oqglnc}{{\mathcal O}_q(GL_n (\mathbb C))}
\newcommand{\oslnc}{{\mathcal O}(SL_n)}
\newcommand{\oslthreec}{{\mathcal O}(SL_3)}
\newcommand{\oqslnc}{{\mathcal O}_q(SL_n (\mathbb C))}
\newcommand{\qdet}{\mathrm{det}_q}
\newcommand{\qper}{\mathrm{per}_q}
\newcommand{\permmon}[2]{#1_{1,#2_1} \cdots {#1}_{n,#2_n}}
\newcommand{\ssm}{\smallsetminus}
\newcommand{\multiu}{\Cup}
\newcommand{\bs}{\backslash}  
\newcommand{\wleq}{\leq_W}
\newcommand{\wless}{<_W}  
\newcommand{\slambda}{\mathfrak{S}_\lambda}
\newcommand{\slambdamin}{\mathfrak{S}_\lambda^{-}}
\renewcommand{\th}{^{\text{th}}}

\def\hsp{\def\baselinestretch{0.75}\large\normalsize}
\def\hhsp{\def\baselinestretch{0.25}\large\normalsize}
\def\hhhsp{\def\baselinestretch{0.125}\large\normalsize}
\def\hhhpsp{\def\baselinestretch{0.13}\large\normalsize}
\def\ssp{\def\baselinestretch{1.0}\large\normalsize}
\def\dsp{\def\baselinestretch{1.4}\large\normalsize}    % for pretty dsp
\def\tsp{\def\baselinestretch{2.0}\large\normalsize}    % for "real" dsp
\def\qsp{\def\baselinestretch{2.4}\large\normalsize}    % for bigger dsp





\title{Bases of the quantum matrix bialgebra and induced sign characters of the Hecke algebra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Ryan Kaliszewski\thanks{\href{mailto:ryk216@lehigh.edu}{ryk216@lehigh.edu}}\addressmark{1}, 
Justin Lambright\thanks{\href{mailto: jjlambright@anderson.edu}{jjlambright@anderson.edu}}\addressmark{2}, and 
Mark Skandera\thanks{\href{mailto:mas906@lehigh.edu}{mas906@lehigh.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Lehigh University, Bethlehem, PA \\ \addressmark{2}School of Science and Engineering, Anderson University, Anderson, IN}

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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We combinatorially describe the transition matrices which
  relate monomial bases of the zero-weight space of the quantum
  matrix bialgebra.  This description leads to a combinatorial rule
  for evaluating induced sign characters of the (type $A$) Hecke algebra $\hnq$
  %In particular, we evaluate the sign characters on 
  at all elements of 
  %the spanning set of $\hnq$ whose elements have
  the form $(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$,
  %where $s_{i_1} \cdots s_{i_m}$ an expression (not necessarily reduced)
  %for a permutation in the symmetric group.
  %These 
  including the Kazhdan--Lusztig basis elements indexed by
  $321$-hexagon-avoiding permutations.
  This result is the first subtraction-free rule for 
  evaluating any 
  %Hecke algebra trace 
  character at all elements of a basis of $\hnq$.}
  %spanning set of the Hecke algebra.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous d\'ecrivons les matrices de transition entre quelques bases de la 
  bialg\`ebre quantique des matrices. 
  Cette description donne une formule combinatoire pour l'\'evaluation
  des caract\`eres  induits sign\'es de l'alg\`ebre de Hecke (type $A$) $\hnq$
  sur chacque \'el\'ement de la forme
  $(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$.
  %where $s_{i_1} \cdots s_{i_m}$ an expression (not necessarily reduced)
  %for a permutation in the symmetric group.
  %These 
  Cet ensemble inclut les \'el\'ements de la base de Kazhdan--Lusztig 
  index\'es par les permutations qui \'evitent les motifs $321$-hexagonaux.
  %$321$-hexagon-avoiding permutations.
  Ce r\'esultat est la premi\`ere formule sans soustraction pour l'\'evaluation
  d'un caract\'ere dans tous les \'el\'ements d'une base de $\hnq$.}
  %ensemble des g\'en\'erateurs
  %de l'alg\`ebre de Hecke.}

%% put your keywords here, or comment this out if you don't have them yet
%%\keywords{math, maths, mathematics}

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

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

\begin{document}

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

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

The {\em symmetric group algebra} $\zsn$
%generated over $\mathbb C$ by $s_1,\dotsc, s_{n-1}$, 
and 
the 
{\em (Iwahori--) Hecke algebra (of type $A$)} $\hnq$
%(of type $A$)
have similar presentations as algebras over $\mathbb Z$ and $\zqq$
respectively, with 
multiplicative identity elements $e$ and $T_e$,
generators 
$s_1,\dotsc, s_{n-1}$ and 
%generated over $\cqq$ by 
$T_{s_1},\dotsc, T_{s_{n-1}}$, 
%are presented by similar 
and relations
\begin{equation}\label{eq:hnqdef}
\begin{alignedat}{3}
s_i^2 &= e &\qquad
T_{s_i}^2 &= (q-1) T_{s_i} + qT_e &\qquad
&\text{for $i = 1, \dotsc, n-1$},\\
s_is_js_i &= s_js_is_j &\qquad
T_{s_i}T_{s_j}T_{s_i} &= T_{s_j}T_{s_i}T_{s_j} &\qquad
&\text{for $|i - j| = 1$},\\
s_is_j &= s_js_i &\qquad
T_{s_i}T_{s_j} &= T_{s_j}T_{s_i} &\qquad
&\text{for $|i - j| \geq 2$}.
\end{alignedat}
\end{equation}
%where $e$ and $\wT_e$ are the respective multiplicative identity elements.
Analogous to the natural basis $\{ w \,|\, w \in \sn \}$ of $\zsn$
is the natural basis $\{ T_w \,|\, w \in \sn \}$ of $\hnq$,
where we define
$T_w = T_{s_{i_1}} \cdots T_{s_{i_\ell}}$ whenever $s_{i_1} \cdots s_{i_\ell}$
is a reduced (short as possible)
expression for $w$ in $\sn$.  We call $\ell$ the {\em length}
of $w$ and write $\ell = \ell(w)$.
%We define the {\em one-line notation} $w_1 \cdots w_n$ of $w \in \sn$ by
%letting any expression for $w$ act on the word $1 \cdots n$,
%where each generator $s_j$ acts on an $n$-letter word by
%swapping the letters in positions $j$ and $j+1$,
%\begin{equation*}
%  s_j \circ v_1 \cdots v_n = v_1 \cdots v_{j-1} v_{j+1} v_j v_{j+2} \cdots v_n.
%\end{equation*}
%It is known that $\ell(w)$ is equal to $\inv(w)$, the number of inversions 
%in the one-line notation $w_1 \cdots w_n$ of $w$.
%(See, e.g., \cite{BjBrentiBruhat}, \cite{Hum} for defintions.) 
%The ``longest'' element of $\sn$, written $w_0$, has one-line notation
%$n \cdots 1$ and length $n(n-1)/2$. 
The specialization of $\hnq$ at $\qp12 = 1$ is isomorphic to $\zsn$.
%Two partial orders arising in the study of $\sn$ are the 
The {\em Bruhat order} on $\sn$ is
%$\leq$ and the {\em weak order} $\wleq$ 
defined by $u \leq v$ if every reduced expression for $v$ contains a reduced expression for $u$.
%\begin{equation}\label{eq:bruweakdef}
%  \begin{alignedat}2
%    u &\leq v &\quad &\text{if every reduced expression for $v$ contains a reduced expression for $u$,}\\
%    u &\wleq v &\quad &\text{if some reduced expression for $v$ ends with a reduced expression for $u$.}
%  \end{alignedat}
%\end{equation}
In addition to the natural basis of 
%$\zsn$ and 
$\hnq$, we have the
(modified) {\em Kazhdan--Lusztig basis}
%$\{ C'_w(1) \,|\, w \in \sn \}$,
$\{ \qew C'_w(q) \,|\, w \in \sn \}$,
%defined in terms of certain {\em Kazhdan--Lusztig polynomials}
%$\{ P_{v,w}(q) \,|\, v,w \in \sn \}$ in $\mathbb N[q]$ by
%\begin{equation}\label{eq:KLbasis}
%C'_w(1) = \sum_{v \leq w} P_{v,w}(1) v, 
%\qquad
%%C'_w(q) = \qiew \sum_{v \leq w} P_{v,w}(q) T_v,
%C'_w(q) = \qiew \sum_{v \leq w} P_{v,w}(q) T_v,
%\end{equation}
where
%%$\leq$ denotes the Bruhat order and
we define $\qew \defeq \qp{\ell(w)}2$. (See \cite{KLRepCH} for definitions.)
%$\qew = \qp{\ell(w)}2$.
%(See, e.g., \cite{Hum}.)
%(See, e.g., \cite{BjBrentiBruhat}.) 
%(See \cite{KLRepCH}.)
%We will find it convenient to modify the second basis to obtain
%\begin{equation}\label{eq:modKLbasis}
%  \{ \qew C'_w(q) \,|\, w \in \sn \} \subseteq \spn_{\mathbb N[q]} \{ T_w \,|\, w \in \sn \}.
%\end{equation}
%Since $P_{w,w}(q) = 1$ for all $w$, this and the first basis in
%(\ref{eq:KLbasis}) 
%These are related to the natural bases of $\hnq$ and $\zsn$
%by unitriangular transition matrices.
%We have the identity $P_{v,w}(q) = 1$ when $w$ \avoidsp,
%i.e., when no subword $w_{i_1} w_{i_2} w_{i_3} w_{i_4}$ of $w_1 \cdots w_n$
%consists of letters which appear in the same relative order as 
%$3412$ or $4231$.
%%satisfies $w_{i_3} < w_{i_4} < w_{i_1} < w_{i_2}$
%%or $w_{i_4} < w_{i_2} < w_{i_3} < w_{i_1}$.  
%(See, e.g., \cite{BilleyLak}.)  ($\star$ Is this fact necessary or even
%useful in the current paper?)

Representations of $\hnq$ are often studied in terms of 
%$\mathbb C$- and $\cqq$-linear functions called
%$\mathbb Z$- and 
$\zqq$-linear functionals called {\em characters}.
The $\zqq$-span of these characters is called the space of
{\em $\hnq$-traces} and has
dimension equal to the number of integer partitions of $n$.  
%(See, e.g., \cite{Sag}, \cite{StanEC1}, \cite{StanEC2} for definitions.) 
Two well-studied bases 
are the irreducible characters $\{ \chi_q^\lambda \,|\, \lambda \vdash n \}$,
and induced sign characters $\{ \epsilon_q^\lambda \,|\, \lambda \vdash n \}$,
related to one another by the
%where $\lambda \vdash n$ denotes that $\lambda$ is a partition of $n$.
% has the same dimension and analogous character bases
%$\{ \chi_q^\lambda \,|\, \lambda \vdash n \}$,
%$\{ \epsilon_q^\lambda \,|\, \lambda \vdash n \}$, 
%specializing at $\smash{\qp12} = 1$ to the $\sn$-character bases.
%In each space, t
%The 
{\em Kostka numbers}, i.e.,
%$\{ K_{\lambda,\mu} \,|\, \lambda, \mu \vdash n \} \subseteq \mathbb N$
%relate these bases
%induced sign and irreducible characters 
%just as they relate the elementary and Schur functions
%in the ring of symmetric functions,
%\begin{equation*}
%  \epsilon^\lambda = \sum_{\mu \vdash n}K_{\mu^\tr,\lambda} \chi^\mu, \qquad
$\epsilon_q^\lambda = \sum_{\mu \vdash n}K_{\mu^\tr,\lambda} \chi_q^\mu$, 
%\qquad e_\lambda = \sum_{\mu \vdash n}K_{\mu^\tr,\lambda} s_\mu$,
%\end{equation*}  
where $\mu^\tr$ denotes the transpose or {\em conjugate}
of the partition $\mu$.
  
%The above characters $\theta \in \{ \chi^\lambda, \epsilon^\lambda \}$
%of $\sn$
%satisfy $\theta^\lambda(z) \in \mathbb Z$ for 
%all $z \in \zsn$ and $\lambda \vdash n$.
%An ideal combinatorial formula for such evaluations
%would define sets $R$, $S$
%so that we have
%$\theta(z) = (-1)^{|S|}|R|$,
%or simply $\theta(z) = |R|$ if $\theta(z) \in \mathbb N$.
%For $z$ in the natural or Kazhdan--Lusztig basis of $\zsn$ we have
%the following results and open problems.
%
%\vspace{2mm}
%%\hhhsp
%\hhhpsp
%\begin{center}
%\newcolumntype{R}{>{$}c<{$}}
%\begin{tabularx}{148.35mm}{|R|R|R|R|R|}%
%\hline
%& & & &\\
%& & & &\\
%\theta
%& \begin{matrix}
%    \mbox{Do we have $\phantom{w_{T_i}^{\hat T}}\nTksp\nTksp\nTksp$} \\ 
%    \mbox{$\theta(w)^{\phantom{\hat T}}\nTksp \in \mathbb N$} \\
%    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
%  \end{matrix} 
%& \begin{matrix}
%    \mbox{Can we interpret $\phantom{w^{\hat T}}\nTksp\nTksp\nTksp$} \\ 
%    \mbox{$\theta(w)^{\phantom{\hat T}}\nTksp$ as $(-1)^{|S|}|R|$} \\
%    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
%  \end{matrix}
%& \begin{matrix}
%    \mbox{Do we have $\phantom{w_{T_i}^{\hat T}}\nTksp\nTksp\nTksp$} \\ 
%    \mbox{$\theta(C'_w(1))^{\phantom{\hat T}}\nTksp \in \mathbb N$} \\
%    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
%  \end{matrix}
%& \begin{matrix}
%    \mbox{Can we interpret $\phantom{w^{\hat T}}\nTksp\nTksp\nTksp$} \\ 
%    \mbox{$\theta(C'_w(1))$ as $|R|^{\phantom{\hat T}}\nTksp$} \\
%    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
%  \end{matrix} \\
%& & & &\\
%& & & &\\
%\hline 
%& & & &\\
%& & & &\\
%\epsilon^\lambda & \mbox{no} & \mbox{yes} & \mbox{yes} & \mbox{open} \\
%& & & &\\
%& & & &\\
%\chi^\lambda & \mbox{no} & \mbox{open} & \mbox{yes} & \mbox{open}\\
%& & & &\\
%& & & &\\
%\hline
%\end{tabularx}
%\end{center}
%\vspace{2mm}
%\ssp
%
%Of the four combinatorial interpretations asked for in the above table,
%the only one which is known may be described as follows.
%Let $\lambda = (\lambda_1, \dotsc, \lambda_r)$.  Then we have
%\begin{equation*}
%  \epsilon^\lambda(w) = (-1)^{|S(w)|}|R(w,\lambda)|,
%\end{equation*}
%where $S(w)$ is the set of inversions in the one-line notation of $w$
%and $R(w,\lambda)$ is the set of labelings of the cycles of $w$ by
%$1, \dotsc, r$ such that exactly $\lambda_i$ letters
%are contained in the cycles labeled $i$
%(\emph{cf.} formula for $M(f,p)_{\lambda,\mu}$ in \cite[page 9]{RemTrans}).
%For instance, consider the partition
%$\lambda = (5,4) \vdash 9$ and permutation $w = 234167589 \in \mfs 9$
%with $\inv(w) = 5$.
%Writing $w$ in cycle notation as $(1,2,3,4)(5,6,7)(8)(9)$,
%we may label the cycles in three ways so that $\lambda_1 = 5$ letters
%belong to cycles labeled $1$ and $\lambda_2 = 4$ letters belong to
%cycles labeled $2$:
%\begin{equation*}
%  \begin{matrix}
%    \ul{(1,2,3,4)} & \ul{(5,6,7)} & \ul{(8)} & \ul{(9)} \\
%    1              & 2            & 1        & 2,   \\
%    1              & 2            & 2        & 1,   \\
%    2              & 1            & 1        & 1.
%  \end{matrix}
%\end{equation*}
%Thus we have
%  $\epsilon^{\lambda}(w) = (-1)^5 3 = -3$.
%The number $\chi^\lambda(w)$ may be computed by the well-known algorithm
%of Murnaghan and Nakayama 
%but has no conjectured expression 
%of the type stated above.
%(See, e.g., \cite{StanEC2}.)  
%Interpretations of
%$\epsilon^\lambda(C'_w(1))$ and
%$\chi^\lambda(C'_w(1))$
%are not known for general $w \in \sn$,
%but nonnegativity follows from work of 
%Haiman~\cite{HaimanHecke} and Stembridge~\cite{StemImm}.
%In the special case that $w$ \avoidsp,
%interpretations of these numbers
%are given in \cite[Theorem 4.7]{CHSSkanEhatKL}.

The characters $\theta_q \in \{ \chi_q^\lambda, \epsilon_q^\lambda \}$
%of $\hnq$
%It is known that irreducible $\sn$-characters 
%$\{ \chi^\lambda \,|\, \lambda \vdash n \}$
satisfy $\theta_q(z) \in \mathbb Z[q]$ for 
all $z \in \hnq$ and $\lambda \vdash n$.
%It is known that 
%irreducible $\hnq$-characters 
%$\{ \chi_q^\lambda \,|\, \lambda \vdash n \}$
%satisfy $\chi_q^\lambda(T_w) \in \mathbb Z[q]$ for all $w \in \sn$.
%Thus for any integer linear combination
%$\theta_q = \sum_\lambda c_\lambda \chi_q^\lambda$ of these
%the irreducibleany 
%$\hnq$-characters, 
%and any element 
%$z \in \spn_{\mathbb Z[q]} \{ T_w \,|\, w \in \sn \}$, we have
%$\theta_q(z) \in \mathbb Z[q]$ as well.
An ideal combinatorial formula for such evaluations
would define
sequences $(S_k)_{k \geq 0}$, $(R_k)_{k \geq 0}$ of sets
%sets $R$, $S$
so that we have
%In some cases, we may associate
%to the pair $(\theta_q, z)$
%to combinatorially interpret
%provide a combinatorial interpretation of the polynomial 
%$\theta_q(z)$ as
%\begin{equation*}
$\theta_q(z) = 
\sum_k (-1)^{|S_k|}|R_k| q^k$,
or simply $\theta_q(z) = 
\sum_k |R_k| q^k$ if $\theta_q(z) \in \mathbb N[q]$.
%\end{equation*}
%We summarize 
%known 
%results and open problems in the following table.
For $z$ in the natural basis
or modified Kazhdan--Lusztig basis of $\hnq$ we have
the following results and open problems.

\vspace{2mm}
\hhhpsp
\begin{center}
\newcolumntype{R}{>{$}c<{$}}
\begin{tabularx}{162mm}{|R|R|R|R|R|}%
%\begin{tabularx}{154.09mm}{|R|R|R|R|R|}%
%\begin{tabularx}{\linewidth}{|R|R|R|R|R|}%
\hline
& & & &\\
& & & &\\
\theta_q \ntnsp
& \begin{matrix}
    \mbox{Do we have $\phantom{w_{T_i}^{\hat T}}\nTksp\nTksp\nTksp$} \\ 
    \mbox{$\theta_q(T_w)^{\phantom{\hat T}}\nTksp \in \mathbb N[q]$}\\
    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
  \end{matrix}
& \begin{matrix}
%    \mbox{interpretation of}\\
    \mbox{Can we interpret $\phantom{w^{\hat T}}\nTksp\nTksp\nTksp$} \\
    \mbox{$\theta_q(T_w)^{\phantom{\hat T}}\nTksp$ as}\\
    \mbox{$\sum_k^{\phantom{\hat T}} (-1)^{|S_k|}|R_k|q^k$}\\
    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
  \end{matrix}\ntksp
& \begin{matrix}
    \mbox{Do we have $\phantom{w_{T_i}^{\hat T}}\nTksp\nTksp\nTksp$} \\
    \mbox{$\theta_q(\qew C'_w(q))^{\phantom{\hat T}}\nTksp \in \mathbb N[q]$}\\
    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
  \end{matrix}
& \begin{matrix}
%    \mbox{interpretation of}\\ 
    \mbox{Can we interpret $\phantom{w^{\hat T}}\nTksp\nTksp\nTksp$} \\
    \mbox{$\theta_q(\qew C'_w(q))^{\phantom{\hat T}}\nTksp$ as}\\
    \mbox{$\sum_k^{\phantom{\hat T}}\ntksp|R_k|q^k$}\\
    \mbox{for all $w \in \sn^{\phantom{\hat T}}\nTksp$ \,?}
%\mbox{$w$ avoiding $312^{\phantom{\hat T}}\nTksp$?}\end{matrix} \\
%\mbox{$w^{\phantom{\hat T}}\nTksp$ avoiding}\\ 
    %\mbox{$3412^{\phantom{\hat T}}\nTksp$ and $4231$?}
  \end{matrix} \\
& & & &\\
& & & &\\
\hline 
%& & & &\\
%& & & &\\
%\eta_q^\lambda & \mbox{no} & \mbox{open} & \mbox{yes} & \mbox{stated in Section 5}\\
& & & &\\
& & & &\\
%\vspace{1mm} 
\epsilon_q^\lambda & \mbox{no} & \mbox{open} & \mbox{yes} & \mbox{open}\\
& & & &\\
& & & &\\
%\vspace{1mm} 
\chi_q^\lambda \ntksp & \mbox{no} & \mbox{open} & \mbox{yes} & \mbox{open}\\
& & & &\\
& & & &\\
\hline
\end{tabularx}
\end{center}
\vspace{2mm}
\ssp

The polynomials $\chi_q^\lambda(T_w)$ and $\epsilon_q^\lambda(T_w)$
may be computed via a $q$-extension of the Murnaghan--Nakayama algorithm
%(e.g., \cite{RamFrob}),
%\cite{KerVerCFR}, \cite{KingWRepTr}, 
%However,
%Otherwise, $\theta_q^\lambda(T_w)$ 
but neither has a conjectured expression of the type asked for above.
Interpretations of
%$\theta_q(\qew C'_w(q))$
$\epsilon_q^\lambda(\qew C'_w(q))$ and
$\chi_q^\lambda(\qew C'_w(q))$ 
are not known for general $w \in \sn$,
but nonnegativity is due to
%but results concerning containment in $\mathbb N[q]$ 
%follow from work of 
Haiman~\cite{HaimanHecke}.
% and Stembridge~\cite{StemImm}.
%In both cases, coefficients of these polynomials
%are unimodal and
%symmetric about $\qew$~\cite[Lemma 1.1]{HaimanHecke}.
In the special case that $w$ \avoidsp,
interpretations %formulas for these polynomials
are given in
\cite[Thms.\ 6.4, 8.1]{CHSSkanEKL}.

To obtain ideal combinatorial interpretations analogous to those asked for
above, we will consider $\epsilon_q^\lambda$ and the infinite spanning set of $\hnq$ %which consists
of all elements of the form 
\begin{equation}\label{eq:wdelt}
(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}) = \qp m2 C'_{s_{i_1}}(q) \cdots C'_{s_{i_m}}(q), \end{equation}
where the index sequence $s_{i_1}\cdots s_{i_m}$ varies over
all products of generators of $\sn$.
%It is easy to see that if we arbitrarily choose exactly one reduced expression
%for each element of $\sn$, then the $n!$ corresponding products
%(\ref{eq:wdelt}) form a basis for $\hnq$.
%Different choices of reduced expressions yield different bases.
%For $z$ belonging to the above spanning set,
%we have the following results and open problems.
%\vspace{2mm}
%\hhhpsp
%\begin{center}
%\newcolumntype{R}{>{$}c<{$}}
%%\begin{tabularx}{163.9mm}{|R|R|R|R|R|}%
%\begin{tabularx}{132.5mm}{|R|R|R|}%
%%\begin{tabularx}{\linewidth}{|R|R|R|R|R|}%
%\hline
%& &\\
%& &\\
%\theta_q \ntnsp
%& \begin{matrix}
%    \mbox{Do we have $\phantom{w_{T_i}^{\hat T}}\nTksp\nTksp\nTksp$} \\ 
%    \mbox{$\theta_q((1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})) \in \mathbb N[q]$}\\
%    \mbox{for all $s_{i_1} \cdots s_{i_m}^{\phantom{\hat T}}\nTksp$ \,?}
%  \end{matrix}
%& \begin{matrix}
%    \mbox{Can we interpret $\phantom{w^{\hat T}}\nTksp\nTksp\nTksp$} \\
%    \mbox{$\theta_q((1+T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}))^{\phantom{\hat T}}\nTksp$ as}\\
%    \mbox{$\sum_k^{\phantom{\hat T}} |R_k|q^k$ for all $s_{i_1} \cdots s_{i_m}^{\phantom{\hat T}}\nTksp$ \,?}
%  \end{matrix} \\
%& &\\
%& &\\
%\hline 
%& &\\
%& &\\
%\epsilon_q^\lambda & \mbox{yes} & \mbox{Stated in Section 7}\\
%& &\\
%& &\\
%\chi_q^\lambda \ntksp & \mbox{yes} & \mbox{open}\\
%& &\\
%& &\\
%\hline
%\end{tabularx}
%\end{center}
%\vspace{2mm}
%\ssp
%Results concerning 
We have $\epsilon_q^\lambda((1+T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}) \in \mathbb N[q]$
%Containment in $\mathbb N[q]$ 
%is due to
%follow from work of 
%Haiman, 
since each product $\qeu C'_u(q) \qev C'_v(q)$ belongs
to $\spn_{\mathbb N[q]} \{ \qew C'_w(q) \,|\, w \in \sn \}$.
(See \cite[Appendix]{HaimanHecke}.)
Interpretation of these polynomials
%$\epsilon_q^\lambda((1 + T_{s_{i_1}}) \cdots ( 1 + T_{s_{i_m}}))$
is new, and is the first result of its kind to include evaluation
of an $\hnq$-character at all elements of a basis of $\hnq$.
%Its justification depends upon the transition matrices which
%relate natural bases of Drinfeld's quantum matrix bialgebra~\cite{DrinfeldQYBE},
%and an identity in this bialgebra 
%%which was stated by
%due to Konvalinka and the third author~\cite[Theorem 5.4]{KSkanQGJ}.

%($\star$ Rewrite this.)
%In Sections~\ref{s:prelim} -- \ref{s:qmb}
In Section~\ref{s:qmb} 
we introduce the quantum matrix bialgebra $\A$ % = \anq$ 
%and review important facts about $\sn$.
%In Section~\ref{s:mbases} we state 
and prove combinatorial
formulas for the entries of transition matrices that relate
%various 
monomial bases of the zero-weight space of $\A$.
%Using these formulas, we define 
In Sections~\ref{s:planar}--\ref{s:evalthm} 
we 
%use formulas from Section~\ref{s:qmb} and 
define a function $\sigma: \A \rightarrow \zqq$
which allows us to compute
%\begin{equation}\label{eq:thetadw}
$\theta_q((1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}))$
%\end{equation}
for any linear function $\theta_q: \hnq \rightarrow \zqq$
in terms of a generating function in $\A$ for $\theta_q$.
%Proofs rely upon formulas from Section~\ref{s:qmb}.
%Combinatorial interpretations from Section~\ref{s:qmb}
%then allow us to interpret (\ref{eq:thetadw}) in terms of
%a wiring diagram for the product $s_{i_1} \cdots s_{i_m}$.
%($\star$ Is that an exaggeration?)
Finally, in Section~\ref{s:eval} we use 
%results from Section~\ref{s:qmb} and 
the map $\sigma$
to combinatorially evaluate induced sign characters of $\hnq$
at all elements of the spanning set (\ref{eq:wdelt}).

%In Section~\ref{s:pathposet} we introduce a partial order on paths in
%zig-zag networks, and show how this poset and results in the literature lead 
%to combinatorial interpretations for the evaluations
%of $\sn$-class functions at the above Kazhdan--Lusztig basis elements
%of $\zsn$.
%For the remainder of the article,
%we concentrate on combinatorial interpretations of trace evaulations
%of the form $\theta_q(\qew C'_w(q))$ where $w$ \avoidsp.
%In Sections~\ref{s:hnqinterph} -- \ref{s:hnqinterpe} 
%we interpret
%$\eta_q^\lambda(\qew C'_w(q))$
%and $\epsilon_q^\lambda(\qew C'_w(q))$. 
%In Section~\ref{s:chromsf} we recall the relationship between
%$\sn$-class functions and Stanley's chromatic symmetric functions,
%and prove that $\hnq$-traces are similarly related to the
%Shareshian--Wachs chromatic quasisymmetric functions.
%In Sections~\ref{s:hnqinterps} -- \ref{s:hnqinterpp} 
%we use results of Shareshian--Wachs and Athanasiadis to
%interpret
%$\chi_q^\lambda(\qew C'_w(q))$
%and $\psi_q^\lambda(\qew C'_w(q))$. 
%One of our interpretations proves a formula conjectured by 
%Haiman~\cite[Conj.4.1]{HaimanHecke}.
%Finally, in Section~\ref{s:hnqinterpm} we state several results 
%concerning 
%$\phi_q^\lambda(\qew C'_w(q))$.


\section{The quantum matrix bialgebra}\label{s:qmb}
%\section{The quantum polynomial ring $\anq$}

%($\star$ Say something about why this bialgebra is important in general.)

The \emph{quantum matrix bialgebra} $\A = \anq$
%The \emph{quantum polynomial ring} $\anq$
is the associative algebra with unit $1$ generated over $\zqq$
%is generated as a noncommutative $\cqq$-algebra 
%generated
by $n^2$ variables $x=(x_{1,1},\dots,x_{n,n})$,
subject to the relations
\begin{equation}\label{eq:anqdef}
\begin{alignedat}{2}
x_{i,\ell}x_{i,k} &= \qp12x_{i,k} x_{i,\ell}, &\qquad 
x_{j,k} x_{i,\ell} &= x_{i,\ell}x_{j,k},\\
x_{j,k}x_{i,k} &= \qp12x_{i,k} x_{j,k}, &\qquad 
x_{j,\ell} x_{i,k} &= x_{i,k} x_{j,\ell} + (\qdiff) x_{i,\ell}x_{j,k},
\end{alignedat}
\end{equation}
for all 
%indices 
$1 \leq i < j \leq n$ and 
$1 \leq k < \ell \leq n$.
The counit and coproduct maps
%\begin{equation*}
%\varepsilon(x_{i,j}) = \delta_{i,j}, \qquad 
%\Delta(x_{i,j}) = \sum_{k=1}^n x_{i,k} \otimes x_{k,j}
%\end{equation*}
$\varepsilon(x_{i,j}) = \delta_{i,j}$, 
$\Delta(x_{i,j}) = \sum_{k=1}^n x_{i,k} \otimes x_{k,j}$
give $\A$ a bialgebra structure.  
Two closely related Hopf algebras 
%closely related to it
%Interest in $\A$ began when Drinfeld~\cite{DrinfeldQYBE}
%used it to express
are 
the quantum coordinate rings of $SL_n(\mathbb C)$ and $GL_n(\mathbb C)$,
%as the quotients
%Each of these is isomorphic to a quotient of $\A$,
\begin{equation*}
\oqslnc \cong \mathbb C \otimes \A/(\qdet(x)-1),
\qquad
\oqglnc \cong \mathbb C \otimes \A[t]/(\qdet(x)t-1),
\end{equation*}
where
%\begin{equation}\label{eq:qdetdef}
$\qdet(x) \defeq \sum_{v \in \sn} (-\qm 12)^{\ell(v)} \permmon xv$ 
%\quad \test
%= \sum_{v \in \sn} (-\qm 12)^{\ell(v)} x_{v_1,1} \cdots x_{v_n,n}
%\end{equation}
is the 
%($n \times n$) 
{\em quantum determinant} of the matrix $x = (x_{i,j})$.  
%(The second equality holds in $\A$ but not in the noncommutative ring
%$\zqq\langle x_{1,1}, \dotsc, x_{n,n} \rangle$.)
For $k$-element subsets $I, J \subset [n] \smash{\defeq} \{1,\dotsc,n\}$,
the submatrix $x_{I,J} = (x_{i,j})_{i \in I, j \in J}$ of $x$ and
the quantum minor $\qdet(x_{I,J})$ are defined in the obvious ways.
%The antipode maps of these Hopf algebras are 
%\begin{equation*}
%\mathcal S (x_{i,j}) = (-\qp12)^{j-i} \qdet(x_{[n]\ssm\{j\}, [n]\ssm \{i\}}),
%\qquad
%\mathcal S (x_{i,j}) = 
%\frac{(-\qp12)^{j-i}\qdet(x_{[n]\ssm\{j\}, [n]\ssm \{i\}})}{\qdet(x)},
%\end{equation*}
%respectively, where
%we define
%\begin{equation*}
%  [n] \defeq \{ 1, \dotsc, n \},
%\end{equation*}
%and where $x_{[n] \ssm \{j\}, [n] \ssm \{i\} }$ is the $(n-1) \times (n-1)$
%submatrix of $x$ obtained by deleting row $j$ and column $i$,
%and the $(n-1) \times (n-1)$ quantum determinant
%is defined analogously to (\ref{eq:qdetdef}).
%in the obvious way.  
%($\star$ Cite Manin? or Soibelman and Vaksman?)
%More generally, for any row subset $I$ and column subset $J$,
%we will denote the $I,J$ submatrix of $x$ by $x_{I,J}$.
Specializing $\A$ at $\qp12 = 1$, we obtain 
%Notice that $ \mathcal{A}(n;1) $ is
the commutative 
%polynomial 
ring $\mathbb{Z}[x_{1,1}, \dotsc, x_{n,n}]$.
%$\A$ has a natural $\zqq$-basis 
%$\{ x_{1,1}^{a_{1,1}} \cdots x_{n,n}^{a_{n,n}} \,|\, 
%a_{1,1}, \dotsc, a_{n,n} \in \mathbb{N} \}$
%of monomials in which variables 
%appear in lexicographic order, and 
%the relations (\ref{eq:anqdef})
%provide an algorithm for expressing any other
%monomial in terms of this basis.
%$\A$ has a natural grading by degree,
%\begin{equation}
%\A = \bigoplus_{r \geq 0} \A_r,
%\end{equation}
%where $\A_r$
%consists of polynomials which are homogeneous of degree $r$.
%We may further decompose each
%homogeneous component 
%$\arnq$ by considering pairs $(L,M)$ of multisets of $r$
%integers, written as weakly increasing words
%\begin{equation*}
%L = \ell_1 \cdots \ell_r, \quad M = m_1 \cdots m_r.
%\end{equation*}
%This leads to the multigrading
%\begin{equation}
%\A = \bigoplus_{r \geq 0} \bigoplus_{L,M} \ALM,
%\end{equation}
%For multisets $L$, $M$ of $[n]$, we let $\A_{L,M}$ 
%denote the $\zqq$-span of monomials whose row indices and
%column indices (with multiplicity) are equal to the multisets $L$
%and $M$, respectively. 
The submodule 
%$\Ann$
%Thus the multigraded component $\annnq$ is spanned by the monomials
\begin{equation}
\Ann = \spn_{\zqq} \{ x^{u,v} \defeq x_{u_1,v_1} \cdots x_{u_n,v_n} \mid u,v \in \sn \}
%\{x_{1,w_1} \cdots x_{n,w_n} \mid w \in \sn \}.
\end{equation}
is called the {\em zero weight space} of $\A$ and
%This component 
has the natural basis $\{ x^{e,w} \,|\, w \in \sn \}$.
%More generally, $\ALM$ is 
%spanned by the monomials
%\begin{equation}\label{eq:natspan}
%\{x_{\ell_{u_1},m_{v_1}} \cdots x_{\ell_{u_r},m_{w_r}} \mid u,v \in \sr \} 
%= \{(x_{L,M})^{u,v} \mid u,v \in \sr \},
%\end{equation}
%where $x_{L,M}$ denotes the {\em generalized submatrix}
%\begin{equation}\label{eq:gensubmatrix}
%x_{L,M} =
%\begin{bmatrix}
%x_{\ell_1,m_1} & x_{\ell_1,m_2} & \cdots & x_{\ell_1,m_r} \\
%x_{\ell_2,m_1} & x_{\ell_2,m_2} & \cdots & x_{\ell_2,m_r} \\
%\vdots & \vdots & & \vdots \\
%x_{\ell_r,m_1} & x_{\ell_r,m_2} & \cdots & x_{\ell_n,m_r}
%\end{bmatrix}
%\end{equation}
%of $x$ determined by the multisets $L$, $M$.
%
%\section{Monomial bases of the zero-weight space}\label{s:mbases}
Expanding other monomials in the basis, we have the following.
\begin{prop}\label{p:rpoly}
There are uniquely defined polynomials
$\{r_{u,v,w}(q_1)\mid w\in\sn\}$ in $\mathbb{N}[q_1]$
which satisfy
\begin{equation}\label{eq:rdefn}
x^{u,v} = \sum_{w \in \sn} r_{u,v,w}(\qp12 - \qm12)x^{e,w}.
%x^{u,v} = \sum_{w \geq u^{-1}v} r_{u,v,e,w}(\qp12 - \qm12)x^{e,w}
\end{equation}
Moreover, we have $r_{u,v,u^{-1}v}(q_1) = 1$ and
%\begin{enumerate}
%\item 
$r_{u,v,w}(q_1) = 0$ unless $w \geq u^{-1}v$.
%\item 
%\end{enumerate}
\end{prop}
\begin{proof}[Proof of Proposition \ref{p:rpoly}]
Omitted.
\end{proof}
%\begin{prop}\label{p:xuvbases} 
\begin{cor}\label{c:xuvbases} 
For each fixed $u \in \sn$, the set $\{ x^{u,v} \,|\, v \in \sn \}$
is a basis for $\annnq$.
\end{cor}
%\begin{proof}
%(Idea.)
%  Let $(w^{(1)}, \dotsc, w^{(n!)})$ be a linear extension of the Bruhat order,
%  and define the sequence $(v^{(1)}, \dotsc, v^{(n!)})$ by $v^{(i)} = uw^{(i)}$.
%  Expanding each monomial $x^{u,v^{(i)}}$ in the (ordered) natural basis
%  $(x^{e,w^{(1)}}, \dotsc, x^{e,w^{(n!)}})$ we obtain $n!$ equations of the form
%  \begin{equation*}
%    x^{u,v^{(i)}} =
%    r_{u,v^{(i)},e,w^{(1)}}(\qdiff) x^{e,w^{(1)}} + \cdots +
%    r_{u,v^{(i)},e,w^{(n!)}}(\qdiff) x^{e,w^{(n!)}}.
%  \end{equation*}
%  By Proposition~\ref{p:ruvtw} we have that
%  $r_{u,v^{(i)},e,w^{(j)}}(\qdiff) = 0$
%  when $w^{(j)} \not \geq u^{-1}v^{(i)} = w^{(i)}$, in particular when $j < i$.
%  We also have $r_{u,v^{(i)},e,w^{(i)}}(\qdiff) = 1$.
%  Thus our system of equations is unitriangular and therefore invertible.
%\end{proof}
%Let us first consider bases of the graded component $\Ann$,
%called the \emph{zero-weight space}
%of $\A$. 
%
%The relations (\ref{eq:anqdef}) imply 
%that the monomials $\{ x^{u,v} \,|\, u,v \in \sn \}$
%satisfy
%\begin{equation}\label{eq:switchsides}
%x^{u,v} = \begin{cases}
%x^{s_iu,s_iv} 
%&\text{if $s_iu < u$ and $s_iv > v$},\\ 
%x^{s_iu,s_iv} + (\qdiff) x^{s_iu,v} &\text{if $s_iu<u$ and $s_iv<v$}.
%\end{cases}
%\end{equation}
%It follows that for fixed $u, v \in \sn$, 
%%satisfying $t \wleq u$, 
%each monomial $x^{u,v}$ belongs to $\sum_w \mathbb N[\qdiff] x^{e,w}$.
%%In particular, since 
%Since nonnegative powers of $\qdiff$ are linearly independent,
%there are uniquely defined polynomials
%$\{r_{u,v,w}(q_1)\mid w\in\sn\}$ in $\mathbb{N}[q_1]$
%which satisfy
%\begin{equation}\label{eq:rdefn}
%x^{u,v} = \sum_{w \in \sn} r_{u,v,w}(\qp12 - \qm12)x^{e,w}.
%%x^{u,v} = \sum_{w \geq u^{-1}v} r_{u,v,e,w}(\qp12 - \qm12)x^{e,w}
%\end{equation}
%In order to state some properties of these polynomials and combinatorially
%interpret their coefficients, we recall a well-known property of the
%Bruhat order (See \cite[Theorem ?]{BBCoxeter}).
%\begin{prop}\label{p:midascent}
%Fix elements $u,v \in \sn$ and a transposition $s$.
%($\star$ Can it be any transposition, or must it be an adjacent transposition?)
%If $us < u$ and $sv < v$ then $uv < usv$.
%\end{prop}
%These polynomials relate 
%$\{x^{u,v} \mid v \in \sn \}$ to 
%%the basis
%$\{x^{e,w} \mid w \in \sn \}$ by a unitriangular matrix.
%\end{proof}
%Now we show that for fixed $u \in \sn$, the set $\{ x^{u,v} \,|\, v \in \sn \}$
%is a basis of $\Ann$.
%\begin{prop}\label{p:ruvtw}
%For fixed $t, u, v \in \sn$ with $t \wleq u$, the polynomials 
%$\{r_{u,v,t,w}(q_1)\mid w\in\sn\}$ in $\mathbb{N}[q_1]$
%satisfy
%$r_{u,v,t,w}(q_1) = 0$ unless $w \geq tu^{-1}v$,
%and $r_{u,v,t,tu^{-1}v}(q_1) = 1$.
%\end{prop}
%\begin{proof}
%(Omitted.)
%By definition we have $r_{t,v,t,w}(q_1) = \delta_{v,w}$.
%Thus the claim holds when $u = t$.
%Now fix $t$ and assume that the claim holds for $\ell(u) \leq \ell(t)+ k-1$,
%consider $u$ of length $\ell(t) + k \geq \ell(t) + 1$,
%and let $s$ be a left descent of $ut^{-1}$ and therefore of $u$.
%It follows that we have $t \wleq su$.
%
%By (\ref{eq:switchsides}) and the linear independence of powers of $\qdiff$,
%we have 
%\begin{equation}\label{eq:rrecur}
%r_{u,v,t,w}(q_1) = \begin{cases}
%r_{su,sv,t,w}(q_1) &\text{if $sv > v$,}\\
%r_{su,sv,t,w}(q_1) + (q_1) r_{su,v,t,w}(q_1) &\text{if $sv < v$}.
%\end{cases}
%\end{equation}
%Suppose that $w \not \geq tu^{-1}v$. Since
%$t(su)^{-1}sv = tu^{-1}v$ and $\ell(su) = \ell(t) + k-1$, we have
%by induction that
%$r_{su,sv,t,w}(q_1) = 0$
%in both cases of (\ref{eq:rrecur}).
%Furthermore since $tu^{-1}s < tu^{-1}$,
%we have by
%($\star$ Cite Bjorner and Brenti? $us < u$ and $sv < v$ imply $uv < usv$.)
%that $tu^{-1}sv > tu^{-1}v$ when $sv < v$.
%Thus in the second case above, the condition $w \ngeq tu^{-1}v$ also implies
%that $w \ngeq tu^{-1}sv$, which by induction implies that 
%$r_{su,v,t,w}(q_1) = 0$.
%Therefore we have $r_{u,v,t,w}(q_1) = 0$ unless $w \geq tu^{-1}v$.
%
%Setting $w = tu^{-1}v$ in (\ref{eq:rrecur}) we have
%$r_{su,sv,t,tu^{-1}v}(q_1) = 1$
%in both cases.
%When $sv < v$ we also have
%$r_{su,v,t,tu^{-1}v}(q_1) = 0$
%since $tu^{-1}v \ngeq tu^{-1}sv$.
%Therefore we have $r_{u,v,t,tu^{-1}v}(q_1) = 1$.
%\end{proof}

%\begin{cor}
%For fixed $t, u \in \sn$, not necessarily related in the weak order, 
%there are uniquely defined polynomials
%$\{r_{u,v,t,w}(q_1)\mid v,w\in\sn\}$ in $\mathbb{Z}[q_1]$
%which satisfy
%\begin{equation}\label{eq:rdefn2}
%x^{u,v} = \sum_{w \in \sn} r_{u,v,t,w}(\qp12 - \qm12)x^{t,w}.
%\end{equation}
%\end{cor}
%\begin{proof}
%(Omitted.)
%  The matrix of coefficients appearing in the proof of
%  Corollary~\ref{c:xuvbases} is invertible over $\mathbb{Z}[\qdiff]$.
%  \end{proof}
%($\star$ Mention that $x^{v,e} = x^{e,v^{-1}}$?)

%Now we
%turn to the problem of
To combinatorially interpret
coefficients of the polynomials
$\{ r_{u,v,w}(q_1) \,|\, u,v,w \in \sn \}$,
%when $t \wleq u$.
%To begin,
%let us turn to a seemingly unrelated question about
%walks in the weak order.
%(Is this the weak order?)
we consider a seemingly unrelated problem concerning sequences of permutations.
\begin{defn}\label{d:pdefn}
Fix permutations $u, v, w \in \sn$ 
%with $t \wleq u$,
% in the weak order,
and a reduced expression $s_{i_1} \ntnsp\cdots s_{i_k}$ 
%be any reduced expression 
for $u$. %$ut^{-1}$.
Define $C_{u,v,w}^b(s_{i_1} \cdots s_{i_k})$ to be the set of sequences
$\pi = (\pi^{(0)}, \dotsc, \pi^{(k)})$ satisfying
\begin{enumerate}
\item $\pi^{(0)} = v$, $\pi^{(k)} = w$,
\item $\pi^{(j)} \in \{ s_{i_j} \pi^{(j-1)}, \pi^{(j-1)} \}$ for $j = 1,\dotsc, k$,
\item $\pi^{(j)} = s_{i_j}\pi^{(j-1)}$ if $s_{i_j}\pi^{(j-1)} > \pi^{(j-1)}$ for $j = 1,\dotsc, k$,
\item $\pi^{(j)} = \pi^{(j-1)}$ for exactly $b$ values of $j$ 
for $j = 1,\dotsc, k$,
\end{enumerate}
and define 
%, fix $k \leq \ell$ and define
%$t = s_{i_k} \cdots s_{i_\ell}$.  
%Define 
the polynomial
%\begin{equation}\label{eq:pdefn}
%p_{u,v,t,w}(q_1) = 
%p_{u,v,t,w}(q_1; s_{i_1}\ntnsp \cdots s_{i_k}) 
$p_{u,v,w}(q_1; \redexp 1k) 
%= \sum_b c_b q_1^b \in \mathbb N[q_1]
= \sum_b |C_{u,v,w}^b(\redexp 1k )| q_1^b \in \mathbb N[q_1]$.
%\end{equation}
%by $c_b = |C_{u,v,t,w}^b(s_{i_1}\cdots s_{i_k})|$.
%declaring $c_b$ to be the number of sequences
\end{defn}
%\noindent
%Observe that we have $p_{t,v,t,w}(q_1;\emptyset) = \delta_{v,w}$. 
%We also have the following recursive formula.

%\begin{prop}\label{p:simplerecur}
%Fix $t,u,v,w \in \sn$ with $t <_W u$,
%and fix a reduced expression 
%$s_{i_1} \cdots s_{i_k}$ for $ut^{-1}$.
%Then we have
%\begin{equation}\label{eq:simplerecur}
%p_{u, v, t, w}(q_1;s_{i_1}\ntnsp \cdots s_{i_k}) = 
%\begin{cases}
%p_{s_{i_1}\ntnsp u, s_{i_1}\ntnsp v, t, w}(q_1; s_{i_2}\ntnsp \cdots s_{i_k}) 
%&\text{if $s_{i_1}\ntnsp v > v$},\\
%p_{s_{i_1}\ntnsp u, s_{i_1}\ntnsp v, t, w}(q_1; s_{i_2}\ntnsp \cdots s_{i_k}) 
%+ q_1 p_{s_{i_1}\ntnsp u, v, t , w}(q_1; s_{i_2}\ntnsp \cdots s_{i_k}) 
%&\text{if $s_{i_1}\ntnsp v < v$}.
%\end{cases}
%\end{equation}
%\end{prop}
%\begin{proof}
%(Omitted.)
%The coefficient of $q_1^b$ on the left-hand side of
%(\ref{eq:simplerecur}) is $|C_{u,v,t,w}^b(s_{i_1}\ntnsp \cdots s_{i_k})|$.
%Since $t <_W u$ and $s_{i_1}$ is a left descent for $ut^{-1}$,
%we have that $t \wleq s_{i_1}\ntnsp u$ and that $s_{i_2} \cdots s_{i_k}$ is
%a reduced expression for $s_{i_1}\ntnsp ut^{-1}$.
%Thus the coefficient of $q_1^b$ on the right-hand side of 
%(\ref{eq:simplerecur}) is equal to the cardinality of
%\begin{equation*}
%D \defeq 
%\begin{cases}
%C_{s_{i_1}\ntnsp u,s_{i_1}\ntnsp v,t,w}^b(s_{i_2}\ntnsp \cdots s_{i_k})
%&\text{if $s_{i_1}\ntnsp v > v$},\\
%C_{s_{i_1}\ntnsp u,s_{i_1}\ntnsp v,t ,w}^b(s_{i_2}\ntnsp \cdots s_{i_k}) 
%\cup C_{s_{i_1}\ntnsp u,v,t,w}^{b-1}(s_{i_2}\ntnsp \cdots s_{i_k})
%&\text{if $s_{i_1}\ntnsp v < v$}.
%\end{cases}
%\end{equation*}
%We claim that the 
%map
%\begin{equation}\label{eq:removepi0}
%\pi = (\pi^{(0)}, \pi^{(1)}, \dotsc, \pi^{(k)}) \mapsto 
%(\pi^{(1)}, \dotsc, \pi^{(k)})
%\end{equation}
%is a bijection from $C_{u,v,t,w}^b(s_{i_1}\ntnsp \cdots s_{i_k})$ to $D$.
%Clearly it is injective, since each element of 
%$C_{u,v,t,w}^b(s_{i_1}\ntnsp \cdots s_{i_k})$ satisfies $\pi^{(0)} = v$.
%
%To see that the map (\ref{eq:removepi0}) is well-defined and surjective,
%assume first that $s_{i_1}\ntnsp v > v$.  
%Then $\pi$ satisfies $\pi^{(1)} = s_{i_1}\ntnsp v$
%and we have $b \leq k-1$.  
%It follows that for $b = 0, \dotsc, k-1$, the sequence
%$(\pi^{(1)}, \dotsc, \pi^{(k)})$ satisfies the conditions
%\begin{enumerate}
%\item[($1'$)] $\pi^{(1)} = s_{i_1} \ntnsp v$, $\pi^{(k)} = w$,
%\item[($2'$)] $\pi^{(j)} \in \{ s_{i_j} \pi^{(j-1)}, \pi^{(j-1)} \}$ 
%for $j = 2,\dotsc, k$,
%\item[($3'$)] $\pi^{(j)} = s_{i_j}\pi^{(j-1)}$ if $s_{i_j}\pi^{(j-1)} > \pi^{(j-1)}$
%for $j = 2,\dotsc, k$,
%\item[($4'$)] $\pi^{(j)} = \pi^{(j-1)}$ for exactly $b$ values of $j$ 
%for $j = 2,\dotsc, k$.
%\end{enumerate}
%Thus $(\pi^{(1)}, \dotsc, \pi^{(k)})$ belongs 
%to $C_{s_{i_1}\ntnsp u,s_{i_1}\ntnsp v,t,w}^b(s_{i_2}\ntnsp \cdots s_{i_k})$.
%Moreover, since prepending $v$ to any sequence in 
%$C_{s_{i_1}\ntnsp u,s_{i_1}\ntnsp v,t,w}^b(s_{i_2}\ntnsp \cdots s_{i_k})$
%produces a sequence belonging to 
%$C_{u,v,t,w}^b(s_{i_1}\ntnsp \cdots s_{i_k})$, the map (\ref{eq:removepi0}) 
%is surjective as well.
%
%Now assume that $s_{i_1} \ntnsp v < v$.  Then $\pi$ satisfies 
%$\pi^{(1)} = s_{i_1} \ntnsp v$
%or $\pi^{(1)} = v$.
%If $\pi^{(1)} = s_{i_1} \ntnsp v$, 
%then the sequence $(\pi^{(1)}, \dotsc, \pi^{(k)})$
%satisfies conditions ($1'$) -- ($4'$) above.  Otherwise it satisfies
%conditions ($2'$) -- ($3'$) and
%\begin{enumerate}
%\item[($1''$)] $\pi^{(1)} = v$, $\pi^{(k)} = w$,
%\item[($4''$)] $\pi^{(j)} = \pi^{(j-1)}$ for exactly $b-1$ values of $j$ 
%for $j = 2,\dotsc, k$.
%\end{enumerate}
%Thus the sequence $(\pi^{(1)}, \dotsc, \pi^{(k)})$
%belongs to
%\begin{equation*}
%C_{s_{i_1}\ntnsp u,s_{i_1}\ntnsp v,t ,w}^b(s_{i_2}\ntnsp \cdots s_{i_k}) 
%\cup C_{s_{i_1}\ntnsp u,v,t,w}^{b-1}(s_{i_2}\ntnsp \cdots s_{i_k}).
%\end{equation*}
%Moreover, since prepending $v$ to any sequence in this union 
%produces a sequence belonging to 
%$C_{u,v,t,w}^b(s_{i_1}\ntnsp \cdots s_{i_k})$, we again have 
%surjectivity.
%\end{proof}

%For fixed $t, u, w$
%and reduced expression $s_{i_1}\ntnsp \cdots s_{i_k}$
%as in Definition~\ref{d:pdefn},
%the above
%initial conditions and 
%recursive formula allow one to compute
%$\{p_{u,v,t,w}(q_1; s_{i_1}\ntnsp \cdots s_{i_k}) \,|\, v \in \sn \}$ 
%by considering the sets
%\begin{equation*}
%\{ p_{s_{i_k}\ntnsp t, v, t, w}(q_1; s_{i_k}) \,|\, v \in \sn \}, \quad
%\{ p_{s_{i_{k-1}}\ntnsp s_{i_k}\ntnsp t, v, t, w}(q_1; s_{i_{k-1}}\ntnsp s_{i_k}) \,|\, v \in \sn \}, \dotsc,
%\end{equation*}
%in order.  
Surprisingly, these polynomials 
{\em do not} depend upon the choice of a reduced expression for %$ut^{-1}$,
$u$, although each set $C_{u,v,w}^b(s_{i_1} \cdots s_{i_k})$ 
does depend upon such a choice.
\begin{thm}\label{t:uexpanduprime}
For $u$ in $\sn$, 
%$ut^{-1}$ in $\sn$ 
%with $t \wleq u$,
the polynomials $\{ r_{u,v,w}(q_1) \,|\, v,w \in \sn \}$
defined in (\ref{eq:rdefn}) satisfy
$r_{u,v,w}(q_1) = p_{u,v,w}(q_1, s_{i_1} \ntnsp \cdots s_{i_k})$,
where $s_{i_1} \ntnsp \cdots s_{i_k}$ is any reduced expression for %$ut^{-1}$.
$u$.  
\end{thm}
\begin{proof}[Proof of Theorem \ref{t:uexpanduprime}]
%(Idea:) The polynomials $\{r_{u,v,w}(q_1)\}$
%$\{p_{u,v,w}(q_1)\}$ satisfy the same recurrence formula.
(Omitted.)
%Observe that the claimed equality holds when $t = u$,
%since 
%\begin{equation*}
%  r_{u,v,u,w}(q_1) = p_{u,v,u,w}(q_1; \emptyset) = \delta_{v,w}
%  \end{equation*}
%by (\ref{eq:rdefn2}) 
%and (\ref{eq:pdefn}).
%Now assume the equality
%to hold for $u$ and $t$ differing in length by at most $k - 1$,
%and consider the case that $u$ and $t$ differ in length by $k$.
%Let $s$ be a left descent of $ut^{-1}$, 
%and therefore a left descent of $u$.
%
%Expanding both sides of (\ref{eq:rdefn}) in terms of the basis
%$\{ x^{t,w} \,|\, w \in \sn \}$ and using induction we obtain
%\begin{equation}\label{eq:randp}
%r_{u,v,t,w}(q_1) = 
%\begin{cases}
%p_{su,sv,t,w}(q_1; s_{j_2} \cdots s_{j_k}) &\text{if $sv > v$},\\
%p_{su,sv,t,w}(q_1; s_{j_2} \cdots s_{j_k}) 
%+ q_1 p_{su,v,t,w}(q_1; s_{j_2} \cdots s_{j_k}) &\text{if $sv < v$},
%\end{cases}
%\end{equation}
%where $s_{j_2} \cdots s_{j_k}$ is an arbitrary reduced expression for $sut^{-1}$.
%Since $s$ is an arbitrarily chosen left descent of $ut^{-1}$, 
%we have the desired result.
\end{proof}

%\begin{cor}\label{c:unitri}
%  For any $u,v,t,w \in \sn$ with $t \wleq u$ we have 
%  \begin{equation*}
%  x^{u,w}
%= x^{t, tu^{-1}w} + 
%\ntksp\ntksp \sum_{v > tu^{-1}w} \ntksp\ntksp 
%r_{u,w,t,v}(\qdiff) x^{t,v}.
%\end{equation*} 
%\end{cor}

%Using Definition~\ref{d:pdefn} and Theorem~\ref{t:uexpanduprime}
%we compute some special cases of the polynomials $r_{u,v,t,w}(q_1)$.
%\begin{prop}
%Fix $w \in \sn$ and any generator $s$.  We have
%\begin{gather}
%r_{ws,w,e,s}(q_1) = r_{w,w,e,e}(q_1) = 1,\label{eq:strategicexample}\\ 
%r_{w,w,e,s}(q_1) = \begin{cases}
%q_1 &\text{if $ws < w$},\\
%0 &\text{if $ws > w$}. 
%\end{cases} \label{eq:strategicexample2}
%\end{gather}
%\end{prop}
%\begin{proof}
%(Omitted.)
%  (\ref{eq:strategicexample}) follows from Proposition~\ref{p:ruvtw}.
%
%  To see (\ref{eq:strategicexample2}),
%  consider the coefficient
%  of $q_1^b$ in $r_{w,w,e,s}(q_1)$ for $b \geq 0$, and let $\ell(w) = m$.
%  By Theorem~\ref{t:uexpanduprime}
%  this is equal to the number of $m$-step walks
%  \begin{equation*}
%    \pi = (\pi^{(0)} = w, \pi^{(1)}, \dotsc, \pi^{(m)} = s)
%  \end{equation*}
%  in the weak order satisfying conditions stated in Definition~\ref{d:pdefn}.
%  In particular, $b$ of the indices $j \in \{1, \dotsc, m-1\}$ satisfy
%  $\pi^{(j-1)} = \pi^{(j)}$, while the others satisfy $\pi^{(j-1)} > \pi^{(j)}$.
%  Since $\ell(w) - \ell(s) = m-1$, the coefficient must be $0$ unless $b = 1$.
%  Furthermore, the coefficient must be $0$ if $ws > w$, equivalently
%  $s \not \wless w$, because in this case the shortest walk in the weak order
%  from $w$ to $s$ consists of $m+1$ steps with no repetition.
%
%  Suppose therefore that we have $b = 1$ and $ws < w$,
%  equivalently $s \wless w$.
%  Then $w$ has a reduced expression of the form
%  $s_{i_1} \cdots s_{i_{m-1}} s$,
%  and the sequence
%  \begin{equation}\label{eq:onewalk}
%    (w, s_{i_1}w, s_{i_2}s_{i_1}w, \dotsc, s_{i_{m-1}} \cdots s_{i_1}w = s, s)
%  \end{equation}
%  is one walk satisfying the conditions of Definition~\ref{d:pdefn}
%  using the above reduced expression (which may be chosen arbitrarily
%  by Theorem~\ref{t:uexpanduprime}).
%  Assume that another such walk satisfies the conditions of the definition,
%  using the same reduced expression.
%  Then for some index $j < m-1$ this walk must have the form
%  \begin{equation*}
%    (w, s_{i_1}w, \dotsc, s_{i_j} \cdots s_{i_1}w, s_{i_j} \cdots s_{i_1}w,
%    s_{i_{j+2}}s_{i_j} \cdots s_{i_1}w, \dotsc,
%    ss_{i_{m-1}} \cdots s_{i_{j+2}} s_{i_j} \cdots s_{i_1}w = s ).
%  \end{equation*}
%  But the equation in the last component of this walk implies that we have
%  \begin{equation*}
%    w = s_{i_1} \cdots s_{i_j} s_{i_{j+2}} \cdots s_{i_{m-1}},
%  \end{equation*}
%  contradicting the fact that $\ell(w) = m$.
%  It follows that (\ref{eq:onewalk}) is the only walk satisfying
%  the conditions of Definition~\ref{d:pdefn} for the chosen reduced
%  expression, and that the coefficient of $q_1^1$ is $1$
%  when $ws < w$.
%\end{proof}  
%($\star$ Is there a shorter proof of (\ref{eq:strategicexample2})
%that uses a recursive formula like
%(\ref{eq:randp}), based on {\em right} multiplication by a generator?)


\section{Wiring diagrams and path matrices}\label{s:planar}
%($\star$ State the purpose of this section.)
To combinatorially evaluate
induced sign characters at elements $(1+T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$
of $\hnq$,
we will use standard $\sn$ wiring diagrams,
concatenations of
%associate to each such element
%a graph $G$ called a {\em wiring diagram},
%a related matrix $B$,
%and a map $\sigma_B: \Ann \rightarrow \zqq$.
%A generating function $\imm{\epsilon_q^\lambda}(x) \in \Ann$ for
%$\{\epsilon_q^\lambda(T_w) \,|\, w \in \sn \}$ will then allow us to compute
%\begin{equation}\label{eq:evalwithsigma}
%  \epsilon_q^\lambda((1+T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}))
%  = \sigma_B(\imm{\epsilon_q^\lambda}(x))
%\end{equation}
%and to combinatorially interpret the resulting polynomial.
%%\ssec{Wiring diagrams, path matrices, and path families}
%Call a directed planar graph $G$ a
%{\em planar network of order $n$} if it
%is acyclic and 
%may be embedded in a disc with $2n$ boundary vertices labeled
%clockwise as 
%{\em source $1, \dotsc,$ source $n$} 
%(with indegrees of $0$) and 
%{\em sink $n, \dotsc,$ sink $1$}
%(with outdegrees of $0$).
%In figures, we will draw 
%sources on the left and sinks on the right,
%implicitly labeled $1, \dotsc, n$ 
%from bottom to top. Edges will be implicitly oriented from left to right.
%Let $\pi = (\pi_1,\dotsc,\pi_n)$ be a sequence of source-to-sink paths
%in a planar network $G$ of order $n$.  We call $\pi$
%a (bijective) {\em path family} if there exists a permutation
%$w = w_1 \cdots w_n \in \sn$ such that 
%$\pi_i$ is a path from source $i$ to sink $w_i$.
%In this case, we say more specifically that $\pi$ has {\em type $w$}.
%We say that the path family {\em covers} $G$ if it contains every edge
%at least once.
%We will call a planar network of order $n$ a {\em wiring diagram}
%if it is a concatenation of any combination of the $n-1$ simple transposition
%elementary
the diagrams
%$G_{[1,2]}, G_{[2,3]}, G_{[3,4]}, \dotsc, G_{[n-1,n]}$, defined by
\begin{equation}\label{eq:elenets}
  G_{[1,2]} = 
\begin{tikzpicture}[scale=.4,baseline=-40]
  \draw[-] (0,0) -- (1,0);
  \draw[-] (0,-1) -- (1,-1);
  \draw[-] (.5,-1.6) circle (1pt); \draw[-] (.5,-1.9) circle (1pt); \draw[-] (.5,-2.2) circle (1pt); 
  \draw[-] (0,-3) -- (1,-3);
  \draw[-] (0,-4) -- (1,-4);
  \draw[-] (0,-5) -- (1,-6); 
  \draw[-] (0,-6) -- (1,-5);
\end{tikzpicture}
\;, \quad
  G_{[2,3]} = 
\begin{tikzpicture}[scale=.4,baseline=-40]
  \draw[-] (0,0) -- (1,0);
  \draw[-] (0,-1) -- (1,-1);
  \draw[-] (.5,-1.6) circle (1pt); \draw[-] (.5,-1.9) circle (1pt); \draw[-] (.5,-2.2) circle (1pt); 
  \draw[-] (0,-3) -- (1,-3);
  \draw[-] (0,-4) -- (1,-5);
  \draw[-] (0,-5) -- (1,-4);
  \draw[-] (0,-6) -- (1,-6);
\end{tikzpicture}
\;, \quad
  G_{[3,4]} = 
\begin{tikzpicture}[scale=.4,baseline=-40]
  \draw[-] (0,0) -- (1,0);
  \draw[-] (0,-1) -- (1,-1);
  \draw[-] (.5,-1.6) circle (1pt); \draw[-] (.5,-1.9) circle (1pt); \draw[-] (.5,-2.2) circle (1pt); 
  \draw[-] (0,-3) -- (1,-4);
  \draw[-] (0,-4) -- (1,-3);
  \draw[-] (0,-5) -- (1,-5);
  \draw[-] (0,-6) -- (1,-6);
\end{tikzpicture}
\;, \quad \dotsc, \quad
  G_{[n-1,n]} = 
\begin{tikzpicture}[scale=.4,baseline=-40]
  \draw[-] (0,0) -- (1,-1);
  \draw[-] (0,-1) -- (1,0);
  \draw[-] (.5,-1.6) circle (1pt); \draw[-] (.5,-1.9) circle (1pt); \draw[-] (.5,-2.2) circle (1pt); 
  \draw[-] (0,-3) -- (1,-3);
  \draw[-] (0,-4) -- (1,-4);
  \draw[-] (0,-5) -- (1,-5);
  \draw[-] (0,-6) -- (1,-6);
\end{tikzpicture}
\;, \quad
  G_{\emptyset} = 
\begin{tikzpicture}[scale=.4,baseline=-40]
  \draw[-] (0,0) -- (1,0);
  \draw[-] (0,-1) -- (1,-1);
  \draw[-] (.5,-1.6) circle (1pt); \draw[-] (.5,-1.9) circle (1pt); \draw[-] (.5,-2.2) circle (1pt); 
  \draw[-] (0,-3) -- (1,-3);
  \draw[-] (0,-4) -- (1,-4);
  \draw[-] (0,-5) -- (1,-5);
  \draw[-] (0,-6) -- (1,-6);
\end{tikzpicture}
\end{equation}
%  \raisebox{-9mm}{\includegraphics[height=19mm]{g12}}\ , \qquad
%  G_{[2,3]} =
%  \raisebox{-9mm}{\includegraphics[height=19mm]{g23}}\ , \qquad
%  G_{[3,4]} =
%  \raisebox{-9mm}{\includegraphics[height=19mm]{g34}}\ , 
%  \dotsc, \
%  G_{[n-1,n]} =
%  \raisebox{-9mm}{\includegraphics[height=19mm]{gnminusonen}}\ , \qquad
%\end{equation}
%including the empty concatenation
%\begin{equation*}
%    G_{\emptyset} \defeq \raisebox{-9mm}{\includegraphics[height=19mm]{gempty}}\ ,
representing the elements 
$s_1, s_2, s_3, \dotsc, s_{n-1}, e$ of $\sn$, respectively. 
Each wiring diagram has $n$ implicit vertices on the left and right,
labeled 
{\em source $1, \dotsc,$ source $n$} 
%(with indegrees of $0$) 
and 
{\em sink $1, \dotsc,$ sink $n$},
respectively, from bottom to top.
Edges are implicitly oriented from left to right.
Let $\pi = (\pi_1,\dotsc,\pi_n)$ be a sequence of source-to-sink paths
in an $\sn$ wiring diagram $G$.  We call $\pi$
a (bijective) {\em path family} if there exists a permutation
$w = w_1 \cdots w_n \in \sn$ such that 
$\pi_i$ is a path from source $i$ to sink $w_i$.
In this case, we say more specifically that $\pi$ has {\em type $w$}.
We say that the path family {\em covers} $G$ if it contains every edge
exactly once.

It is easy to see that 
the number of path families covering the wiring diagram
%a path family which covers a wiring diagram
\begin{equation}\label{eq:wdnetwork}
G = G_{[i_1,i_1+1]} \circ \cdots \circ G_{[i_m,i_m+1]}
\end{equation}
of $s_{i_1} \cdots s_{i_m}$
%includes every edge of $G$ exactly once.  Furthermore, $G$ 
is $2^m$: for $j = 1,\dotsc,m$, the two paths
intersecting at the central vertex of $G_{[i_j,i_j+1]}$ either cross or
do not cross at that vertex.  In these two cases, we call the index $j$
a {\em crossing} or {\em noncrossing}, respectively.
%Wiring diagrams appear frequently in the study of $\sn$, where
%the wiring diagram $G$ (\ref{eq:wdnetwork}) typically encodes the
%sequence $s_{i_1} \cdots s_{i_m}$ of generators in $\sn$.
%Whether or not this expression is reduced, we call $G$
%{\em the wiring diagram of} the expression $s_{i_1} \cdots s_{i_m}$.
%It is well known that if we have the equality
%$s_{i_1} \cdots s_{i_m} = w$ in $\sn$,
%then $w$ is the type of the unique path family covering $G$
%(\ref{eq:wdnetwork})
%in which all indices $1,\dotsc,m$ are crossings.

The diagram (\ref{eq:wdnetwork})
may be used to encode
%Alternatively, one may use the same diagram $G$ to encode the element
%$(1 + s_{i_1}) \cdots (1 + s_{i_m})$ of $\zsn$.
%The $2^m$ terms in the expansion of this product may be written
%and collected as
%\begin{equation*}
%  \sum_{\beta \in 2^{[m]}} s_{i_1}^{\beta_1} \cdots s_{i_m}^{\beta_m}
%  = \sum_{v \in \sn} d_v v,
%\end{equation*}
%where the $2^m$ binary words $\beta = \beta_1 \cdots \beta_m$
%correspond to path families covering $G$ by
%\begin{equation}\label{eq:mask}
%  \beta_j = \begin{cases}
%    1 &\text{if $j$ is a crossing},\\
%    0 &\text{otherwise},
%  \end{cases}
%\end{equation}
%and we define $s_{i_j}^0 = 1$.
%Thus each coefficient $d_v \in \mathbb N$ in the second sum
%counts the number of path families of type $v$ which cover $G$.
%Similar to the above
%$\zsn$
%encoding is the use of $G$
%to encode 
%the element
$(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}) = \sum_{v \in \sn}a_v T_v$ in $\hnq$.
%Expanding this product and collecting terms we have
%\begin{equation}\label{eq:hnqwire}
%  \sum_{\beta \in 2^{[m]}} (T_{s_{i_1}})^{\beta_1} \cdots (T_{s_{i_m}})^{\beta_m}
%  = \sum_{v \in \sn} a_v T_v,
%\end{equation}
%where binary words $\beta = \beta_1 \cdots \beta_m$
%correspond to path families covering $G$ by 
%\begin{equation}\label{eq:mask}
%  \beta_j = \begin{cases}
%    1 &\text{if $j$ is a crossing},\\
%    0 &\text{otherwise},
%  \end{cases}
%\end{equation}
%and the definition $T_{s_{i_j}}^0 = 1$.
%Now 
Specifically, each coefficient $a_v \in \mathbb N[q]$ 
%in the expansion 
%belong to $\mathbb N[q]$ and
may be interpreted in terms of a path family statistic called {\em defects}.
%crossings and noncrossings of paths in path families.
Call index $j$ a {\em defect} of path family $\pi$ if
the two paths containing the central vertex of $G_{[i_j,i_j+1]}$
have previously crossed an odd number of times.
%(Equivalently, a crossing or noncrossing is defective if
%the path entering the common vertex on top has a lower source index.)
We will call index $j$ a {\em proper} crossing or noncrossing if it
is not defective.
Letting
%$\cross$ and
$\dfct(\pi)$ denote the number of
%proper and crossings and defective noncrossings, respectively, in $\pi$,
%Then
defects in $\pi$ we have
%Now we have
%Now the coefficients $a_v$ in the expansion belong to $\mathbb Z[q]$ and
%are defined in terms of {\em noncrossings} of paths in path families,
%indices $j$ such that the two paths containing the central vertex of
%$G_{[i_j,i_j+1]}$ do not cross at that vertex.
%Call noncrossing $j$ {\em proper} if the two relevant paths
%cross an even number of times before $G_{[i_j,i_j+1]}$,
%and {\em defective} otherwise.
%Let $\pnc(\pi)$ ($\star$ necessary?)
%and $\dfct(\pi)$ denote the numbers of proper and
%defective noncrossings, respectively, in $\pi$.
%Now wehave 
%\begin{equation}\label{eq:defectdef}
%  a_v = \qp{m-\ell(v)}2 \sumsb{\pi\\\type(\pi) = v} \qp{\dfct(\pi)-\pnc(\pi)}2,
%\end{equation}
%or better, since $m = \ell(v) + \dfct(\pi) + \pnc(\pi)$,
%\begin{equation}\label{eq:defectdef2}
  $a_v =
%  \sumsb{\pi\\ \type(\pi) = v \\ \pi \text{ covers } G} q^{\dfct(\pi)}.
  \sum_\pi q^{\dfct(\pi)}$,
  %\qp{\cross(\pi)-\ell(v)}2,
%\end{equation}
where the sum is over path families of type $v$ 
which cover $G$~\cite[Proposition 3.5]{Deodhar90}.
Billey and Warrington~\cite[Theorem 1]{BWHex} showed that 
if $s_{i_1} \cdots s_{i_m}$ is a reduced expression for $w$ avoiding $321$ and the {\em hexagon} patterns
%and if $w$ avoids the patterns 
%$321$, 
$56781234$, $56718234$, $46781235$, $46718235$,
then 
%we have 
$\qew C'_w(q) = (1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$.
%sum (\ref{eq:hnqwire})
%wiring diagram of this expression encodes 
%equals $\qew C'_w(q)$.
%as in (\ref{eq:hnqwire}).
    
%\begin{equation*}
  %\label{eq:bwhex}
%  \qiew C'_w(q) =
  

%In order to use wiring diagrams for the evaluations of Hecke algebra
One often enhances a planar network by
associating to each edge
%we will place {\em weights} on their edges.
%To each edge of a planar network we associate
a {\em weight} belonging to some ring $R$, and by defining
the {\em weight of a path} to be the product of its edge weights.
If $R$ is noncommutative, then weights are multiplied
in the order that the corresponding edges appear in the path.
For a {\em family} $\pi = (\pi_1,\dotsc,\pi_n)$ of $n$
paths in a planar network,
one defines $\wgt(\pi) = \wgt(\pi_1) \cdots \wgt(\pi_n)$. 
%We will say that such a family {\em covers} the wiring diagram $G$
%if it contains every edge of $G$ exactly once.
%We will say that $\pi$ has {\em type $w \in \sn$} if
%$\pi_i$ is a path from source $i$ to sink $w_i$ for all $i$.
The {\em (weighted) path matrix} $B = B(G) = (b_{i,j})$ of $G$ is defined by
letting $b_{i,j}$ be the sum of weights of all paths in $G$ from source $i$
to sink $j$.
Thus the product $\permmon bw$ is equal to the sum of weights of all
path families of type $w$ in $G$.
%A result known as {\em Lindstr\"om's Lemma}~\cite{KMG}, \cite{LinVRep}
%asserts that for row and column sets $I$, $J$ with $|I| = |J|$,
%the minor $\det(B_{I,J})$ is equal to the sum of weights of all nonintersecting
%path families from sources indexed by $I$ to sinks indexed by $J$.
%It is easy to show that path matrices respect concatenation:
%$B(G_1 \circ G_2) = B(G_1)B(G_2)$.
%These families may or may not cover $G$.
%It is well known that the path matrix of the concatenation of
%planar networks is equal to the product of the corresponding path matrices. 
%($\star$ State/cite Lindstr\"om's Lemma?)

Assigning weights to the edges of $G$ (\ref{eq:wdnetwork}) can aid in
the evaluation of a linear function $\theta: \zsn \rightarrow \mathbb Z$
at $(1 + s_{i_1}) \cdots (1 + s_{i_m})$ by relating it to the
generating function
\begin{equation}\label{eq:imm}
  \imm{\theta}(x) \defeq \sum_{w \in \sn} \theta(w) \permmon xw
  \in \zxn,
\end{equation}
called the {\em $\theta$-immanant} in \cite[Section 3]{StanPos}.
In particular,
for $j = 1,\dotsc, m$, we assign weight $1$ to the
$n-2$ horizontal edges of $G_{[i_j,i_j+1]}$, and we assign (commuting)
indeterminate weights
$z_{i_j,j,1}$, $z_{i_j,j,2}$, $z_{i_j+1,j,1}$, $z_{i_j+1,j,2}$
to the remaining nonhorizontal edges $a, b, c, d$, respectively,
\begin{equation}\label{eq:onestar}
\begin{tikzpicture}[scale=.7,baseline=-25]
  \draw[-] (0,0) -- (1.2,-1) node[above right,midway,xshift=-1mm,yshift=-1mm] {c};
  \draw[-] (0,-2) -- (1.2,-1) node[below right,midway,xshift=-1mm,yshift=1mm] {a};
  \draw[-] (2.4,0) -- (1.2,-1) node[above left,midway,xshift=1mm,yshift=-1mm] {d};
  \draw[-] (2.4,-2) -- (1.2,-1) node[below left,midway,xshift=1mm,yshift=2mm] {b};
  \draw[-,fill] (0,0) circle (2pt);  \draw[-,fill] (0,-2) circle (2pt);
  \draw[-,fill] (2.4,0) circle (2pt);  \draw[-,fill] (2.4,-2) circle (2pt);
  \draw[-,fill] (1.2,-1) circle (2pt);
\end{tikzpicture}\;.
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{starabcd.eps}}
\end{equation} 
%labeled $a,b,c,d$, respectively.
%Edges $a,b,c,d$
%receive the indeterminate weights
%respectively, while horizontal edges receive the weight $1$.
Thus networks corresponding to expressions $s_{i_1} s_{i_2} s_{i_3} = s_1s_2s_1$
and $s_{i_4}s_{i_5}s_{i_6} = s_1s_2s_1$ are weighted differently
because of the different indexing of the generators.
Let $z_G$
%$\mathbf{z}$ 
be the product of all $4m$ indeterminates $z_{i,j,k}$,
and for $f \in \mathbb{Z}[z_{1,1,1} ,\dotsc, z_{i_m,m,2}]$, let $[z_G]f$ denote
the coefficient of $z_G$ in $f$.
Then we have the following.
%The following result was essentially observed by Stembridge in
%\cite[page 1081]{StemConj}.
\begin{prop}\label{p:stem}
Assign weights to the edges of $G$ (\ref{eq:wdnetwork}) as above
and let $B$ be the resulting path matrix.
Then for any linear function $\theta: \zsn \rightarrow \mathbb Z$ we have
\begin{equation*}
\theta((1 + s_{i_1}) \cdots (1 + s_{i_m})) = [z_G]\imm{\theta}(B).
\end{equation*}
\end{prop}
    
\begin{example}
%let $n = 3$ and 
Consider
%the element
%\begin{equation*}
$(1+s_1)(1+s_2)(1+s_1) = 2 + 2s_1 + s_2 + s_1s_2 + s_2s_1 + s_1s_2s_1$
%\end{equation*}
in $\zsn$ and its wiring diagram
%the network
%in (\ref{eq:wdnetwork}) be
%\begin{equation}\label{eq:Gbraid}
%  \begin{aligned}
$ G
= G_{[i_1,i_1+1]} \circ G_{[i_2,i_2+1]} \circ G_{[i_3,i_3+1]}
  = G_{[1,2]} \circ G_{[2,3]} \circ G_{[1,2]}$.
%\end{equation}
Assigning weights to the edges of $G$ we have
%i.e.,
\begin{equation}\label{eq:Gbraidfig}
%\[
%  G =
  \resizebox{6cm}{!}{
\raisebox{-2.2cm}{
    \begin{tikzpicture}
  \node at (-1,0) {\large $3$};
  \node at (-1,-2) {\large $2$};
  \node at (-1,-4) {\large $1$};
  \node at (7,0) {\large $3$};
  \node at (7,-2) {\large $2$};
  \node at (7,-4) {\large $1$};
  \draw[-] (0,0)  -- (2,0)
                  -- (3,-1) node[midway,left]  {\large $z_{3,2,1}$}
                  -- (4,0)  node[midway,right] {\large $z_{3,2,2}$}
                  -- (6,0);
  \draw[-] (0,-2) -- (1,-3) node[midway,left]  {\large $z_{2,1,1}$}
                  -- (2,-2) node[midway,right] {\large $z_{2,1,2}$}
                  -- (3,-1) node[midway,left]  {\large $z_{2,2,1}$}
                  -- (4,-2) node[midway,right] {\large $z_{2,2,2}$}
                  -- (5,-3) node[midway,left]  {\large $z_{2,3,1}$}
                  -- (6,-2) node[midway,right] {\large $z_{2,3,2}$};
  \draw[-] (0,-4) -- (1,-3) node[midway,left]  {\large $z_{1,1,1}$}
                  -- (2,-4) node[midway,right] {\large $z_{1,1,2}$}
                  -- (4,-4) 
                  -- (5,-3) node[midway,left]  {\large $z_{1,3,1}$}
                  -- (6,-4) node[midway,right] {\large $z_{1,3,2}$};
\filldraw (0,0) circle (.7mm);
\filldraw (2,0) circle (.7mm);
\filldraw (4,0) circle (.7mm);
\filldraw (6,0) circle (.7mm);
\filldraw (3,-1) circle (.7mm);
\filldraw (0,-2) circle (.7mm);
\filldraw (2,-2) circle (.7mm);
\filldraw (4,-2) circle (.7mm);
\filldraw (6,-2) circle (.7mm);
\filldraw (1,-3) circle (.7mm);
\filldraw (5,-3) circle (.7mm);
\filldraw (0,-4) circle (.7mm);
\filldraw (2,-4) circle (.7mm);
\filldraw (4,-4) circle (.7mm);
\filldraw (6,-4) circle (.7mm);
\end{tikzpicture}%.
}}
%\]
\end{equation}
and $z_G = z_{1,1,1} \cdots z_{3,2,2}$.
%By inspection, one sees that t
The weighted path matrix of $G$
is
%has four entries consisting of two terms,
%$(2,2)$-entry equal to
%\begin{equation}\label{eq:B1212}
%  \begin{gathered}
%  b_{1,1} = z_{1,1,1}z_{1,1,2}z_{1,3,1}z_{1,3,2}
%  + z_{1,1,1}z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}z_{1,3,2}, \\
%  b_{1,2} = z_{1,1,1}z_{1,1,2}z_{1,3,1}z_{2,3,2}
%  + z_{1,1,1}z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}z_{2,3,2}, \\
%  b_{2,1} = z_{2,1,1}z_{1,1,2}z_{1,3,1}z_{1,3,2}
%  + z_{2,1,1}z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}z_{1,3,2}, \\
%  b_{2,2} = z_{2,1,1}z_{1,1,2}z_{1,3,1}z_{2,3,2}
%  + z_{2,1,1}z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}z_{2,3,2},
%  \end{gathered}
%\end{equation}
\begin{equation}\label{eq:Bex}
%  \begin{aligned}
    B
%  =\begin{bmatrix}
%    z_{1,1,1}z_{1,1,2} & z_{1,1,1}z_{2,1,2} & 0 \\
%    z_{2,1,1}z_{1,1,2} & z_{2,1,1}z_{2,1,2} & 0 \\
%    0              & 0               & 1 
%  \end{bmatrix} \ntksp
%  \begin{bmatrix}
%    1 & 0              & 0               \\
%    0 & z_{2,2,1}z_{2,2,2} & z_{2,2,1}z_{3,2,2} \\
%    0 & z_{3,2,1}z_{2,2,2} & z_{3,2,1}z_{3,2,2} 
%  \end{bmatrix} \ntksp
%  \begin{bmatrix}
%    z_{1,3,1}z_{1,3,2} & z_{1,3,1}z_{2,3,2} & 0 \\
%    z_{2,3,1}z_{1,3,2} & z_{2,3,1}z_{2,3,2} & 0 \\
%    0              & 0               & 1 
%  \end{bmatrix}\\
  = \ntnsp \begin{bmatrix}
    z_{1,1,1}z_Uz_{1,3,2} + z_{1,1,1}z_Dz_{1,3,2}
    & z_{1,1,1}z_Uz_{2,3,2} + z_{1,1,1}z_Dz_{2,3,2}
    & z_{1,1,1}z_{2,1,2}z_{2,2,1}z_{3,2,2} \\
    z_{2,1,1}z_Uz_{1,3,2} + z_{2,1,1}z_Dz_{1,3,2}
    & z_{2,1,1}z_Uz_{2,3,2} + z_{2,1,1}z_Dz_{2,3,2}
    & z_{2,1,1}z_{2,1,2}z_{2,2,1}z_{3,2,2} \\
    z_{3,2,1}z_{2,2,2}z_{2,3,1}z_{1,3,2}
    & z_{3,2,1}z_{2,2,2}z_{2,3,1}z_{2,3,2}
    & z_{3,2,1}z_{3,2,2}
  \end{bmatrix}%\ntnsp,
%  \end{aligned}
\end{equation}
where $z_U = z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}$,
$z_D = z_{1,1,2}z_{1,3,1}$.
%We also have that $B$ is equal to the product of the weighted path matrices
%of the three factor networks,
%\begin{equation*}
%  B =
%  \begin{bmatrix}
%    z_{1,1,1}z_{1,1,2} & z_{1,1,1}z_{2,1,2} & 0 \\
%    z_{2,1,1}z_{1,1,2} & z_{2,1,1}z_{2,1,2} & 0 \\
%    0              & 0               & 1 
%  \end{bmatrix}
%  \begin{bmatrix}
%    1 & 0              & 0               \\
%    0 & z_{2,2,1}z_{2,2,2} & z_{2,2,1}z_{3,2,2} \\
%    0 & z_{3,2,1}z_{2,2,2} & z_{3,2,1}z_{3,2,2} 
%  \end{bmatrix}
%  \begin{bmatrix}
%    z_{1,3,1}z_{1,3,2} & z_{1,3,1}z_{2,3,2} & 0 \\
%    z_{2,3,1}z_{1,3,2} & z_{2,3,1}z_{2,3,2} & 0 \\
%    0              & 0               & 1 
%  \end{bmatrix}.
%\end{equation*}
Now define $\theta: \zsn \rightarrow \mathbb Z$ by
%let $\theta$ be the linear function defined by
$\theta(e) = 1$, $\theta(s_1s_2s_1) = -1$, $\theta(w) = 0$ otherwise.
%\begin{equation*}
%  \theta(w) = \begin{cases}
%    1 & \text{if $w = e$}\\
%    -1 & \text{if $w = s_1s_2s_1$}\\
%    0 &\text{otherwise}
%  \end{cases}
%\end{equation*}
%This function satisfies
We have
%\begin{equation*}
%  $\theta((1+s_1)(1+s_2)(1+s_1)) = 2 - 1 = 1$.
  $\theta((1+s_1)(1+s_2)(1+s_1)) = 1$.
%  \end{equation*}
Applying Lindstr\"om's Lemma 
%and inspection of the wiring diagram 
to the wiring diagram (\ref{eq:Gbraidfig}),
one sees that the corresponding immanant
%\begin{equation*}
  $\imm{\theta}(x) = x_{1,1}x_{2,2}x_{3,3} - x_{1,3}x_{2,2}x_{3,1} =
  \det(x_{13,13})x_{2,2}$
%\end{equation*}
satisfies
%\begin{equation*}
$[z_G]\imm{\theta}(B) = 1$,
since exactly one
family of paths $\pi = (\pi_1, \pi_2, \pi_3)$ from all sources
to the corresponding sinks covers $G$ (has weight $z_G$) and satisfies
$\pi_1 \cap \pi_3 = \emptyset$.  (See (\ref{eq:Gtableaux}).)
%\begin{enumerate}
%\item $\pi_1$ and $\pi_3$ do not intersect,
%\item $\pi$ covers $G$ and therefore has weight $z_G$.
%\end{enumerate}
\end{example}

It is natural to ask for a $q$-analog of Proposition~\ref{p:stem}
which applies to
%to aid in
the computation of
$\theta_q((1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}))$
for a linear function $\theta_q: \hnq \rightarrow \zqq$.
While the most naive approach will not suffice,
%$q$-extension will not suffice,
%however:
%while the immanant (\ref{eq:imm}) in $\zxn$ does have
%a natural $q$-analog in $\A$, the evaluation of this element
%at a matrix is not well-defined.
%unless the entries of that matrix
%satisfy the relations (\ref{eq:anqdef}).
%Nevertheless,
we will state and prove the desired $q$-analog in Section~\ref{s:evalthm}.

%relating this evaluation to the
%requires
%some care.
%\begin{equation*}
%\begin{aligned}
%{[z_G]}\imm{\theta}(B) &= [z_G](b_{1,1}b_{2,2}b_{3,3} - b_{1,3}b_{2,2}b_{3,1})\\
%&= [z_G](2z_Uz_Dz_{1,1,1}z_{1,3,2}z_{2,1,1}z_{2,3,2}z_{3,2,1}z_{3,2,2}\\
%&\qquad \qquad - z_{1,1,1}z_{2,1,2}z_{2,2,1}z_{3,2,2}z_{2,1,1}z_Dz_{2,3,2}z_{3,2,1}z_{2,2,2}z_{2,3,1}z_{1,3,2})\\
%&= [z_G](2z_G - z_G)\\
%&= 1.
%\end{aligned}
%\end{equation*}

\section{The $q$-immanant evaluation theorem for wiring diagrams}
\label{s:evalthm}

%Assigning weights to the edges of $G$ (\ref{eq:wdnetwork}) can similarly aid
%in the evaluation of
In order to evaluate a linear function $\theta_q: \hnq \rightarrow \mathbb Z$
at $(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$ by relating this evaluation to the
generating function
\begin{equation}\label{eq:qimm}
  \imm{\theta_q}(x) \defeq \sum_{w \in \sn} \theta_q(T_w) \qiew \permmon xw
  \in \A,
\end{equation}
we begin by assigning weights to the edges of the wiring diagram $G$
(\ref{eq:wdnetwork}) exactly as in (\ref{eq:onestar}).
But now
%For the purposes evaluating induced sign characters of $\hnq$,
%we will strategically weight edges of the wiring diagram (\ref{eq:wdnetwork})
%by $4m$ indeterminates which commute or quasicommute with one another.
%In particular,
%Let $\qp12$ be another indeterminate which commutes with all v
we define two indeterminates $z_{h,j,k}$, $z_{h',j',k'}$
to commute only if $j \neq j'$ or $k \neq k'$; otherwise we impose the relation
\begin{equation}\label{eq:zrelation}
z_{i_j+1,j,k} z_{i_j,j,k} 
= \qp12 z_{i_j,j,k} z_{i_j+1,j,k}.
\end{equation}
%for each of the $2m$ pairs $(j,k)$.
%\in [m] \times [2]$,
%where $q$ is the parameter
%of $\hnq$, which we define to commute with all indeterminates.
Let $Z_G$ be the quotient of 
%the noncommutative ring
%\begin{equation*}
    $\mathbb Z[\qp12, \qm12]
    \langle z_{i_j,j,1}, z_{i_j,j,2}, z_{i_j+1,j,1}, z_{i_j+1,j,2}
    \,|\, j=1,\dotsc, m, \rangle$
%    \end{equation*}
modulo the ideal generated by the above commuting and quasicommuting
relations, and assume that $\qp12$, $\qm12$
commute with all other indeterminates.
Let $z_G$
%$\mathbf{z}$ 
be the product of all $4m$ indeterminates $z_{i,j,k}$, in lexicographic order.

This
small change in the indeterminates $z_{1,1,1}, \dotsc, z_{i_m,m,2}$
does not imply that the most naive $q$-analog of Proposition~\ref{p:stem}
holds, however.  Indeed, the evaluation of an element of $\A$ at a matrix
is not well defined unless the entries of that matrix satisfy the
relations (\ref{eq:anqdef}).
We therefore define the $\zqq$-linear map
%{\em Lindstr\"om's Lemma}~\cite{LinVRep},
%originally due to Karlin and McGregor~\cite{KMG},
%states that for any
%In the classical case of an unweighted planar network $G$ of order $n$
%and its path matrix $B = (b_{i,j})$ defined by
%\begin{equation*}
%  b_{i,j} = \# \text{ paths from source $i$ to sink $j$},
%\end{equation*}
%one may evaluate any element $f(x) \in \zxn$
%at the matrix $B$ by substituting $x_{i,j} = b_{i_j}$ in $f$
%for all $i,j \in [n]$.
%\ssec{A map $\sigma_B$ which interprets elements of $\Ann$ in terms of
%  path families}
%In the example of (\ref{eq:Gbraid}) - (\ref{eq:Bex}),
%products such as $b_{1,1}b_{2,2}b_{3,3}$ include terms such as
%\begin{equation*}
%  (z_{1,1,1}z_{1,1,2}z_{1,3,1}z_{1,3,2})
%  (z_{2,1,1}z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}z_{2,3,2})
%  (z_{3,2,1}z_{3,2,2})
%\end{equation*}
%which are weights of path families which cover $G$, and terms such as
%\begin{equation*}
%  (z_{1,1,1}z_{1,1,2}z_{1,3,1}z_{1,3,2})
%  (z_{2,1,1}z_{1,1,2}z_{1,3,1}z_{2,3,2})
%  (z_{3,2,1}z_{3,2,2})
%\end{equation*}
%which are weights of path families which exclude some edges
%of $G$,
%while including others
%twice.
%We will be interested in those path families which {\em cover} a wiring diagram,
%and in the crossings of component paths within such a family.
%In order to extract only these path families from a product
%$b_{1,v_1} \cdots b_{n,v_n}$ of path matrix entries, we
%define the $\zqq$-linear map 
\begin{equation}\label{eq:sigmadef}
\begin{aligned}
%  \sigma_B: \anq_{[n],[n]} &\rightarrow \zqq\\
  \sigma_B: \annnq &\rightarrow \zqq\\
\permmon xv &\mapsto [z_G] \permmon bv,
\end{aligned}
\end{equation}
where $[z_G] \permmon bv$ is the coefficient of $z_G$ in $\permmon bv$,
%and this coefficient is
taken after $\permmon bv$ 
is expanded in the lexicographic basis of $Z_G$.
Note that the substitution $x_{i,j} \mapsto b_{i,j}$ is performed
only for monomials of the form $x^{e,v}$ in $\Ann$;
we define $\sigma_B(x^{u,w})$ by first expanding $x^{u,w}$
in the basis $\{ x^{e,v} \,|\, v \in \sn \}$, and {\em then} performing
the substitution.
% $x_{i,j} \mapsto b_{i,j}$.

%Let us continue with our
\begin{example}
%(\ref{eq:Gbraid}), let us and
Let us compute
%\begin{example}
%Let $n=3$ and let $G$ be the star network
%Consider evaluating
$\sigma_B(x_{2,2}x_{1,1}x_{3,3})$ for the path matrix $B$ (\ref{eq:Bex}) 
of the wiring diagram in (\ref{eq:Gbraidfig}).
%Since the map $\sigma_B$ is defined on elements of the natural basis
%$\{ x^{e,v} \,|\, v \in \sn \}$ of $\annnq$,
%Thus we expand $x_{2,2}x_{1,1}x_{3,3}$ as
%Thus
Using (\ref{eq:anqdef}) and linearity of $\sigma_B$, we write
%express $x_{2,2}x_{1,1}x_{3,3}$ in terms of these
%we have
\begin{equation}\label{eq:x22x11x33}
  \begin{aligned}
    \sigma_B(x_{2,2}x_{1,1}x_{3,3})
    &= \sigma_B(x_{1,1}x_{2,2}x_{3,3}) + (\qdiff)\sigma_B(x_{1,2}x_{2,1}x_{3,3})\\
    &= [z_G]b_{1,1}b_{2,2}b_{3,3} + (\qdiff)[z_G]b_{1,2}b_{2,1}b_{3,3}.
    \end{aligned}
\end{equation}
Expanding $b_{1,1}b_{2,2}b_{3,3}$
%(\ref{eq:Bex})
and
%expand $b_{1,1}b_{2,2}b_{3,3}$ while
%(\ref{eq:Bex}) and
omitting terms with repeated indeterminates,
%and sorting indeterminates into lexicographic order (\ref{eq:zrelation}),
we have
%\begin{equation*}
%  z_G + z_{1,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,2} z_{2,3,1} z_{1,3,2} z_{2,1,1} z_{1,1,2} z_{1,3,1} z_{2,3,2} z_{3,2,1} z_{3,2,2},
%\end{equation*}
%\begin{equation*}
%  \begin{align*}
%where the second term is a permutation of $z_G$.
%    \begin{multline*}
\begin{equation*}
  \begin{aligned}
    {[z_G]} b_{1,1}b_{2,2}b_{3,3} &=
  [z_G](z_{1,1,1} z_{1,1,2} z_{1,3,1} z_{1,3,2} z_{2,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,2} z_{2,3,1} z_{2,3,2} z_{3,2,1} z_{3,2,2} \\
  &\quad+ z_{1,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,2} z_{2,3,1} z_{1,3,2} z_{2,1,1} z_{1,1,2} z_{1,3,1} z_{2,3,2} z_{3,2,1} z_{3,2,2}).
% = z_G + qz_G. 
    %    \end{multline*}
  \end{aligned}
  \end{equation*}
%Observe that the first term in parentheses is $z_G$
%and the second is a permutation of $z_G$.
    %    \end{align*}
Sorting indeterminates into lexicographic order and using
(\ref{eq:zrelation}), we see that this is
\begin{equation*}
  [z_G] (z_G + q z_G) = 1+q.
  \end{equation*}
%see that this expression equals $z_G + qz_G$.
%Thus we have $\sigma_B(x_{1,1}x_{2,2}x_{3,3}) = 1+q$.
%Sorting the indeterminates in the second into lexicographical order and using
%(\ref{eq:zrelation}),
%we obtain $(1+q)z_G$.
%to sort the indeterminates 
%    and collecting terms, we have that
    %\[ \sigma_B(x_{1,1}x_{2,2}x_{3,3}) = (1+q). \]
%    \begin{equation*}
%      (1+q)
%z_{1,1,1}z_{1,1,2}z_{1,3,1}z_{1,3,2}z_{2,1,1}z_{2,1,2}z_{2,2,1}z_{2,2,2}z_{2,3,1}z_{2,3,2}z_{3,2,1}z_{3,2,2}
%    \end{equation*}
%Applying the same process to 
Similarly computing $[z_G] b_{1,2}b_{2,1}b_{3,3}$,
%from (\ref{eq:Bex}),
we obtain
%and using
%(\ref{eq:zrelation}), we obtain
%$(\qp12 + \qp32)z_G$.
%Thus we have $\sigma_B(x_{1,2}x_{2,1}x_{3,3}) = (\qp12 + \qp32)$.
$(\qp12 + \qp32)$.
%Through the same process we get that
%\[ \sigma_B(x_{1,2}x_{2,1}x_{3,3})=(\qp{1}{2}+\qp{3}{2}). \]
%Combining these two results with
Thus Equation \eqref{eq:x22x11x33} gives
%us that
\[\sigma_B(x_{2,2}x_{1,1}x_{3,3}) = (1+q) + (\qdiff)(\qp12 + \qp32) = q+q^2. \]

%and use
%Since, for example, 
%\begin{equation*}
%B_{1,1} = 
%z_{1,1,1} z_{1,1,2} z_{1,3,1} z_{1,3,2} + z_{1,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,%2} z_{2,3,1} z_{1,3,2},
%\end{equation*}
%we have that
%\begin{align*} \sigma_B(x_{1,1}x_{2,2}x_{3,3})\cdot z_G = &(z_{1,1,1} z_{1,1,2}% z_{1,3,1} z_{1,3,2} + z_{1,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,2} z_{2,3,1} z_{1,3%,2}) \\
% & \cdot (z_{2,1,1} z_{1,1,2} z_{1,3,1} z_{2,3,2} + z_{2,1,1} z_{2,1,2} z_{2,2,%1} z_{2,2,2} z_{2,3,1} z_{2,3,2}) \\
%  & \cdot (z_{3,2,1} z_{3,2,2}). \end{align*}
%By eliminating terms with repeated indeterminates, we get that
%\begin{align*} \sigma_B(x_{1,1}x_{2,2}x_{3,3})\cdot z_G =& z_{1,1,1} z_{1,1,2} %z_{1,3,1} z_{1,3,2} z_{2,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,2} z_{2,3,1} z_{2,3,2}% z_{3,2,1} z_{3,2,2} \\
% & + z_{1,1,1} z_{2,1,2} z_{2,2,1} z_{2,2,2} z_{2,3,1} z_{1,3,2} z_{2,1,1} z_{1%,1,2} z_{1,3,1} z_{2,3,2} z_{3,2,1} z_{3,2,2}. \end{align*}
%After sorting into lexicographical order and collecting terms, we have that
%\[ \sigma_B(x_{1,1}x_{2,2}x_{3,3}) = (1+q). \]
%Through the same process we get that
%\[ \sigma_B(x_{1,2}x_{2,1}x_{3,3})=(\qp{1}{2}+\qp{3}{2}). \]
%Combining these two results with Equation \eqref{eq:x22x11x33} gives us that
%\[\sigma_B(x_{2,2}x_{1,1}x_{3,3}) = q+q^2. \]
%\end{example}

%For example, let $n=2$ and let $G$ be the network in (\ref{eq:onestar}), with
%all horizontal edges removed.  Consider evaluating $\sigma_B(x_{2,2}x_{1,1})$.
%The map $\sigma_B$ is defined on elements of the natural basis of $\anq$.
%Expressing $x_{2,2}x_{1,1}$ in terms of these we have
%\begin{equation}\label{eq:x22x11}
%x_{2,2}x_{1,1} = x_{1,1}x_{2,2} + (\qdiff)x_{1,2}x_{2,1}.
%\end{equation}
%Since
%\begin{equation*}
%B = \begin{bmatrix}
%z_{1,1,1} z_{1,1,2} & z_{1,1,1} z_{2,1,2} \\
%z_{2,1,1} z_{1,1,2} & z_{2,1,1} z_{2,1,2}
%\end{bmatrix}, 
%\qquad
%\end{equation*}
%we have that $\sigma_B(x_{1,1}x_{2,2}) + (\qdiff)\sigma_B(x_{1,2}x_{2,1})$ 
%is equal to the coefficient of 
%\begin{equation*}
%z_G = z_{1,1,1}z_{1,1,2}z_{2,1,1}z_{2,1,2}
%\end{equation*}
%in
%\begin{equation*}
%\begin{aligned}
%\begin{gathered}
%z_{1,1,1}z_{1,1,2}z_{2,1,1}z_{2,1,2} + (\qdiff) z_{1,1,1}z_{2,1,2}z_{2,1,1}z_{1,1,2} \\
%= z_{1,1,1}z_{1,1,2}z_{2,1,1}z_{2,1,2} + (\qdiff) \qp12 z_{1,1,1}z_{1,1,2}z_{2,1,1}z_{2,1,2},
%\end{gathered}
%\end{aligned}
%\end{equation*}
%which is $1 + (q-1) = q$.

%($\star$ Redo this example with $n$ larger.)
%($\star$ Redo the next observation - proposition example with nonreduced expression too.)

%For some combinations of a wiring diagram $G$
%and two permutations $u,v$, 
%the expression for $\sigma_B(x^{u,v})$ is very simple.
%\begin{prop}\label{p:sigmareduced}
%  Fix $u, v, w \in \sn$, and an expression $s_{i_1} \cdots s_{i_\ell}$
%  (not necessarily reduced) for $w$.
%  Let $G$ be the corresponding wiring diagram
%  and let $B$ be the weighted path matrix of $G$.
%  Then we have the following.
%  \begin{enumerate}[(i)]
%  \item $\sigma_B(x^{u,v}) = 0$ unless $s_{i_1} \cdots s_{i_\ell}$ contains a subexpression for $u^{-1}v$.
%  \item If $s_{i_1} \cdots s_{i_\ell}$ is reduced, then
%    $\sigma_B(x^{e,w}) = \qp{\ell(w)}2$, and
%    $\sigma_B(x^{e,v}) = 0$ unless $v \leq w$.    
%  \end{enumerate}
%\end{prop}
%\begin{proof}
%(Omitted.)
%  (i) Suppose that $b_{u_1,v_1} \cdots b_{u_n,v_n} \neq 0$.
%  Then there is a path family $\pi$ of type $u^{-1}v$ which covers $G$.
%  Define the binary word $\beta = \beta_1 \cdots \beta_\ell$ by
%  \begin{equation*}
%    \beta_j = \begin{cases}
%      1 &\text{if two paths of $\pi$ cross at the central vertex of
%        $G_{[i_j,i_j+1]}$,}\\
%      0 &\text{otherwise.}
%    \end{cases}
%  \end{equation*}
%  Then we have $\type(\pi) = s_{i_1}^{\beta_1} \cdots s_{i_\ell}^{\beta_\ell}$ and
%  the factors with $\beta_j = 1$ form a subexpression of
%  $s_{i_1} \cdots s_{i_\ell}$ which is equal in $\sn$ to $\type(\pi)$.
%
%  \noindent
%  (ii) If $s_{i_1} \cdots s_{i_\ell}$ is reduced, then there is exactly
%  one path family $\pi$ which covers $G$ and has type $u^{-1}v$.
%  Its component paths cross at the central vertex of each
%  simple transposition graph $G_{[i_j,i_j+1]}$.
%  Each crossing causes the variables $z_{i_j,j,1}$, $z_{i_j+1,j,2}$
%  to appear earlier than the variables $z_{i_j+1,j,1}$, $z_{i_j,j,2}$,
%  contributing $\qp12$ to $\sigma_B(x^{e,w})$.
%  Now consider a permutation $v$ with $v \not \leq w$. By definition
%  of the Bruhat order (\ref{eq:bruweakdef})
%  there is no subexpression of $s_{i_1}\cdots s_{i_\ell}$ which
%  is an expression for $v$.  By (i.) we have $\sigma_B(x^{e,v}) = 0$.
%\end{proof}

%\begin{obs}\label{o:genshort}
%  Fix $u,v \in \sn$, let $G$ be a wiring diagram for the expression $s_i$,
%  and let $B$ be the weighted path matrix of $G$.  Then we have
%  $\sigma_B(x^{u,v}) = 0$ unless $u^{-1}v \in \{ e, s_i \}$.
%\end{obs}
%\begin{proof}
%  Omitted.
%  \end{proof}

%\noindent
%An important special case of Proposition~\ref{p:sigmareduced}
%concerns wiring diagrams for a single generator.
%\begin{cor}\label{c:sigmareduced}
%  Let $H$ be the wiring diagram corresponding to the reduced
%  expression $s_{i_1} = s_j$, and let $C$ be the weighted path matrix of $H$.
%  For $u,v \in \sn$ we have
%  \begin{equation*}
%    \sigma_C(x^{u,v}) = 
%    \begin{cases}
%      \qp12 &\text{if $u = vs_j$},\\
%      q &\text{if $u = v$ and $vs_j < v$},\\
%      1 &\text{if $u = v$ and $vs_j > v$},\\
%      0 &\text{if $u \not \in \{ v, vs_j \}$}.
%    \end{cases}
%  \end{equation*}
%  \end{cor}
%\begin{proof}
%(Idea.) Use the combinatorial interpretation in Theorem~\ref{t:uexpanduprime}
%and the relations (\ref{eq:zrelation}).
%The matrix $C$ is obtained from the $n \times n$ identity matrix by
%replacing its $[j,j+1]$, $[j,j+1]$ submatrix by
%\begin{equation*}
%\begin{bmatrix}
%z_{j,1,1} z_{j,1,2} & z_{j,1,1} z_{j+1,1,2} \\
%z_{j+1,1,1} z_{j,1,2} & z_{j+1,1,1} z_{j+1,1,2}
%\end{bmatrix},
%\end{equation*}
%and we have $z_H = z_{j,1,1}z_{j,1,2}z_{j+1,1,1}z_{j+1,1,2}$.
%Using Proposition~\ref{p:ruvtw} to expand $x^{u,v}$
%in the natural basis of $\annnq$ and recalling that
%Proposition~\ref{p:sigmareduced} (ii) implies $\sigma_C(x^{e,w})$
%to vanish unless
%$w \in \{ e, s_j \}$, we can write
%\begin{equation*}
%  \sigma_C(x^{u,v}) = \sigma_C(x^{e,u^{-1}v})
%  + \sumsb{w > u^{-1}v\\w \leq s_j} r_{u,v,e,w}(\qdiff)\sigma_C(x^{e,w}).
%\end{equation*}
%Now observe that the restrictions on $w$ imply this expression to vanish unless
%$u \in \{ v, vs_j \}$.
%When $u = vs_j$ we have
%\begin{equation}\label{eq:xvsjv}
%  \begin{aligned}
%  \sigma_C(x^{vs_j,v}) = \sigma_C(x^{e,s_j})
%  &= [z_H] z_{j,1,1}z_{j+1,1,2}z_{j+1,1,1}z_{j,1,2} \\
%  &= [z_H] \qp12 z_{j,1,1}z_{j,1,2}z_{j+1,1,2}z_{j+1,1,1} 
%  = \qp12,
%  \end{aligned}
%\end{equation}
%since $z_{j,1,2}$ commutes with $z_{j+1,1,1}$ and quasicommutes with $z_{j+1,1,2}$.
%On the other hand, when $u = v$, we may use (\ref{eq:strategicexample})
%and (\ref{eq:xvsjv}) to obtain
%\begin{equation}\label{eq:sigmagenerator}
%    \begin{aligned}
%      \sigma_C(x^{v,v}) &= \sigma_C(x^{e,e})
%      + r_{v,v,e,s_j}(\qdiff)\sigma_C(x^{e,s_j}) \\
%      &= [z_H] z_{j,1,1}z_{j,1,2}z_{j+1,1,1}z_{j+1,1,2}
%      + \qp12 \begin{cases}
%        \qdiff &\text{if $vs_j < v$}, \\
%        0      &\text{otherwise}
%      \end{cases}\\
%      &= \begin{cases}
%        q &\text{if $vs_j < v$},\\
%        1 &\text{otherwise}.
%      \end{cases}
%    \end{aligned}
%\end{equation}
%\end{proof}
\end{example}

The map $\sigma_B$ behaves well with respect to concatenation of star networks.
\begin{prop}\label{p:sigmacoprod}
Let $G$ and $H$ be wiring diagrams corresponding to expressions
$s_{i_1} \cdots s_{i_k}$ and $s_{i_{k+1}} \cdots s_{i_m}$,
with weighted path matrices $B$ and $C$ respectively, 
so that $G \circ H$ corresponds to expression $s_{i_1} \cdots s_{i_m}$ and 
has weighted path matrix $BC$. Then for all $u,w \in \sn$ we have
\begin{equation}\label{eq:sigmacoprod}
\sigma_{BC}(x^{u,w}) = \sum_{v \in \sn} \sigma_B(x^{u,v}) \sigma_C(x^{v,w}).
\end{equation}
\end{prop}
\begin{proof}[Proof of Proposition \ref{p:sigmacoprod}]
(Omitted.)
%Let $A = BC = (a_{i,j})$ and consider
%\begin{equation*} 
%\begin{aligned}
%  \sigma_{BC}(x^{u,w})
%  &= [z_{GH}]a_{u_1,w_1} \cdots a_{u_n,w_n}\\
%  &= [z_{GH}] \Big( \sum_{j_1=1}^n b_{u_1,j_1} c_{j_1,w_1} \Big)
%  \cdots \Big( \sum_{j_n=1}^n b_{u_1,j_n} c_{j_n,w_1} \Big).
%\end{aligned}
%\end{equation*}
%In all but $n!$ of the $n^n$ resulting terms,
%repeated indices among $j_1,\dotsc, j_n$ lead to
%repeated indeterminates or matrix entries equal to $0$, which cause
%the coefficient of $z_{GH}$ to be $0$.
%Thus we may consider only
%the $n!$ terms in which $j_1, \dotsc, j_n$ are all distinct,
%and the expression reduces to
%\begin{equation}\label{eq:zgh}
%  [z_{GH}] \sum_{v \in \sn} b_{u_1,v_1}c_{v_1,w_1} \cdots b_{u_n,v_n}c_{v_n,w_n}.
%\end{equation}
%Now observe that $b_{u_i,v_i}$ commutes with $c_{v_j,w_j}$ for all $i,j$,
%since our indexing of the expressions $s_{i_1} \cdots s_{i_k}$,
%$s_{i_{k+1}} \cdots s_{i_m}$ guarantees all edge weights 
%  $\{ z_{i_j, j,1}, z_{i_j,j,2}, z_{i_j+1,j,1}, z_{i_j+1,j,2} \,|\, 1 \leq j \leq k\}$
%of $G$ to
%commute with all edge weights 
%  $\{ z_{i_j, j,1}, z_{i_j,j,2}, z_{i_j+1,j,1}, z_{i_j+1,j,2} \,|\, k+1 \leq j \leq m\}$
%of $H$.
%Thus (\ref{eq:zgh}) is equal to
%\begin{equation*}
%  \begin{aligned}
%    \sum_{v \in \sn} [z_{GH}] b_{u_1,v_1} \cdots b_{u_n,v_n} c_{v_1,w_1} \cdots c_{v_n,w_n} 
%    &= \sum_{v \in \sn} [z_G] b_{u_1,v_1} \cdots b_{u_n,v_n} [z_H] c_{v_1,w_1} \cdots c_{v_n,w_n} \\
%    &= \sum_{v \in \sn} \sigma_B(x^{u,v}) \sigma_C(x^{v,w}).
%  \end{aligned}
%\end{equation*}
\end{proof}

The special case of Proposition~\ref{p:sigmacoprod} in which we have
%$u = e$ and
$m = k+1$ (so that $H$ is the wiring diagram of the single
generator $s_{i_{k + 1}}$) leads to a simple formula for
%$\sigma_{BC}(x^{e,w})$
$\sigma_{BC}(x^{u,w})$
in terms of
%$w$, $s_{i_{k+1}}$ and
%the matrix 
$B$.
\begin{cor}\label{c:sigmacoprod}
  Let wiring diagrams $G$, $H$
  %correspond to
  of expressions $s_{i_1}\cdots s_{i_k}$, $s_{i_{k+1}}$
  have weighted path matrices $B$, $C$, respectively.
%  so that $BC$ is the weighted path matrix of $G \circ H$.
  Then for all $w \in \sn$ we have
  \begin{equation*}
    \sigma_{BC}(x^{u,w}) =
    \qp12 \sigma_B(x^{u,ws_{i_{k+1}}}) +
    \begin{cases}
      q \sigma_B(x^{u,w}) &\text{if $ws_{i_{k+1}} < w$},\\
      \sigma_B(x^{u,w}) &\text{if $ws_{i_{k+1}} > w$}.
    \end{cases}  
%    \sigma_{BC}(x^{e,w}) =
%    \qp12 \sigma_B(x^{e,ws_{i_{k+1}}}) +
%    \begin{cases}
%      q \sigma_B(x^{e,w}) &\text{if $ws_{i_{k+1}} < w$},\\
%      \sigma_B(x^{e,w}) &\text{if $ws_{i_{k+1}} > w$}.
%    \end{cases}  
  \end{equation*}
\end{cor}
\begin{proof} [Proof of Corollary \ref{c:sigmacoprod}]
%  $BC$ is the weighted path matrix of $G \circ H$.
%  By Corollary~\ref{c:sigmareduced}, the expansion in 
%  Proposition~\ref{p:sigmacoprod} has only two nonzero terms:
%\begin{equation*}
%\sigma_{BC}(x^{u,w}) 
%= \sigma_B(x^{u,ws_{i_{k+1}}}) \sigma_C(x^{ws_{i_{k+1}},w}) 
%+ \sigma_B(x^{u,w}) \sigma_C(x^{w,w}).
%\end{equation*}
%Evaluating $\sigma_C$ as in Corollary~\ref{c:sigmareduced}
%we then have the desired expression.
%&= \sigma_B(x^{u,ws_{i_{k+1}}}) \qp12 
%   + \sigma_B(x^{e,w}) \sigma_C(r_{w,w,e,e}(\qdiff)x^{e,e} + r_{w,w,e,s_{i_{k+1}}}(\qdiff)x^{e,s_{i_{k+1}}}).
%\sigma_{BC}(x^{e,w}) 
%&= \sigma_B(x^{e,ws_{i_{k+1}}}) \sigma_C(x^{ws_{i_{k+1}},w}) 
%   + \sigma_B(x^{e,w}) \sigma_C(x^{w,w})\\
%&= \sigma_B(x^{e,ws_{i_{k+1}}}) \sigma_C(r_{ws_{i_{k+1}},w,e,s_{i_{k+1}}}(\qdiff) x^{e,s_{i_{k+1}}})\\
%   &\quad + \sigma_B(x^{e,w}) \sigma_C(r_{w,w,e,e}(\qdiff)x^{e,e} + r_{w,w,e,s_{i_{k+1}}}(\qdiff)x^{e,s_{i_{k+1}}}).
%\end{aligned}
%\end{equation*}
%By (\ref{eq:strategicexample}) and Corollary~\ref{c:sigmareduced}
%this is
%\begin{equation*}
%\begin{gathered} 
%  \sigma_B(x^{e,ws_{i_{k+1}}}) \sigma_C(x^{e,s_{i_{k+1}}})
%+ \sigma_B(x^{e,w}) \sigma_C(x^{e,e})
%+ \begin{cases}
%  \ntnsp (\qdiff) \sigma_B(x^{e,w}) \sigma_C(x^{e,s_{i_{k+1}}})
%  &\ntnsp \text{if $ws_{i_{k+1}} < w$},\\
%  \ntnsp 0
%  &\ntnsp \text{if $ws_{i_{k+1}} > w$}
%\end{cases}\\
%= \sigma_B(x^{e,ws_{i_{k+1}}}) \qp12
%+ \sigma_B(x^{e,w}) + \begin{cases}
%(q-1) \sigma_B(x^{e,w}) &\text{if $ws_{i_{k+1}} < w$},\\
%0 &\text{if $ws_{i_{k+1}} > w$}.
%\end{cases}\\
%\end{gathered}
%\end{equation*}
Use the combinatorial interpretation in Theorem~\ref{t:uexpanduprime}, and the relations (\ref{eq:zrelation}). 
\end{proof}
  
%Another 
An important property of the map $\sigma_B$ is that its
evaluation
at monomial basis elements of $\Ann$ is related to
coefficients in the 
%natural 
expansion of 
$(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$.
% in $\hnq$.  
\begin{prop}\label{p:qewcoeff}
Let $G$ be the wiring diagram in (\ref{eq:wdnetwork}) 
with weighted path matrix $B$, and fix $w \in \sn$.
Then 
$\sigma_B(x^{e,w})$ is equal to $\qew$ times the coefficient of $T_w$ in 
$(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$.
\end{prop}
\begin{proof} [Proof of Proposition \ref{p:qewcoeff}]
(Idea.) Use induction, Proposition~\ref{p:sigmacoprod}, 
Corollary~\ref{c:sigmacoprod}, 
and the relations (\ref{eq:hnqdef}).
%  Consider the wiring diagram $G = G_{[j,j+1]}$ of the simple transposition $s_j$
%  and its weighted path matrix $B$.
%  By Corollary~\ref{c:sigmareduced} we have
%  \begin{equation*}
%    \sigma_B(x^{e,w}) = \begin{cases}
%      \qp12 
%      &\text{if $w = s_j$},\\
%      1 
%      &\text{if $w = e$},\\
%      0 
%      &\text{otherwise}.
%    \end{cases}
%    \end{equation*}
%  Thus the result is true for any simple transposition 
%   wiring diagram
%  in (\ref{eq:elenets}).
% 
%  Now assume that the result holds for concatenations 
%  of $1,\dotsc, m-1$ simple transposition diagrams,
%  and let $\{ a_w \,|\, w \in \sn \}$ be the coefficients appearing in
%  \begin{equation*}
%    (1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_{m-1}}}) = \sum_{w \in \sn} a_w T_w.
%    \end{equation*}
%Consider the wiring diagram
%$G = G_{[i_1,i_1+1]} \circ \cdots \circ G_{[i_m,i_m+1]}$
%and decompose $G$ as $G' \circ H$, where
%$G' = G_{[i_1,i_1+1]} \circ \cdots \circ G_{[i_{m-1},i_{m-1}+1]}$
%has weighted path matrix $B'$ and
%$H = G_{[i_m,i_m+1]}$ has 
%weighted path matrix $C$.
%By Corollary~\ref{c:sigmacoprod}
%we have
%\begin{equation*}
%\begin{aligned} 
%\sigma_B(x^{e,w}) = \sigma_{B'C}(x^{e,w}) 
%&= \qp12 \sigma_{B'}(x^{e,ws_{i_m}})
%+ \begin{cases}
%q \sigma_{B'}(x^{e,w}) &\text{if $ws_{i_m} < w$},\\
%\sigma_{B'}(x^{e,w}) &\text{if $ws_{i_m} > w$}.
%\end{cases}\\
%\end{aligned}
%\end{equation*}
%By induction, this is
%\begin{equation*}
%    \qp12 q_{e,ws_{i_m}} a_{ws_{i_m}} 
%    + \begin{cases}
%q \qew a_w &\text{if $ws_{i_m} < w$},\\
%\qew a_w &\text{if $ws_{i_m} > w$}\
%\end{cases}
%= 
%\begin{cases}
%\qew (a_{ws_{i_m}} + q a_w) &\text{if $ws_{i_m} < w$},\\
%\qew (q a_{ws_{i_m}} + a_w) &\text{if $ws_{i_m} > w$}.
%\end{cases}
%\end{equation*}
%On the other hand,
%consider the element
%\begin{equation}\label{eq:element}
%  (1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})
%  = \Big( \sum_{v \in \sn} a_v T_v \Big) (1 + T_{s_{i_m}}).  
%\end{equation}
%By (\ref{eq:hnqdef}) we have
%\begin{equation*}
%  T_w T_{s_{i_m}} = \begin{cases}
%    (q-1)T_w + qT_{ws_{i_m}} &\text{if $ws_{i_m} < w$},\\
%    T_{ws_{i_m}} &\text{if $ws_{i_m} > w$}.
%  \end{cases}
%  \end{equation*}
%Thus $\qew$ times the coefficient of $T_w$ in (\ref{eq:element}) is  
%\begin{equation*}
%\qew \Bigg( a_w + \begin{cases} 
%a_{ws_{i_m}} + (q-1)a_w &\text{if $ws_{i_m} < w$,}\\
%qa_{ws_{i_m}} &\text{if $ws_{i_m} > w$}
%\end{cases} \Bigg)
%= \begin{cases} 
%\qew(a_{ws_{i_m}} + q a_w) &\text{if $ws_{i_m} < w$},\\
%\qew(qa_{ws_{i_m}} + a_w) &\text{if $ws_{i_m} > w$}.
%\end{cases}
%\end{equation*}
\end{proof}

As a consequence of Proposition~\ref{p:qewcoeff},
we now have a $q$-analog of Proposition~\ref{p:stem}.
%the evaluation
%$B \mapsto \imm{\theta}(B)$ 
%of immanants in $\zxn$ at $n \times n$ matrices. 
Namely, when $B$ is the path matrix
of a wiring diagram, and $\theta_q: \hnq \rightarrow \zqq$ is linear,
we may ``evaluate'' $\imm{\theta_q}(x)$ at $B$ by 
applying the map $\sigma_B$ to $\imm{\theta_q}(x)$.
%This provides
%a $q$-analog of Proposition~\ref{p:stem}.
%The function $\sigma_B$ can be quite useful 
%in the study of
%linear functions $\theta_q:\hnq \rightarrow \zqq$.
%This %when one is interested in
%value of working with the algebra $\A$ and the 
%$\hnq$
%and path matrices of wiring diagrams
%While sometimes we lack an explicit formula for
%evaluations $\theta_q(g)$, $g \in \hnq$,
%we may have a nice generating function in $\Ann$ for $\theta_q$,
%\begin{equation}\label{eq:immdef}
%  \imm{\theta_q}(x) \defeq \sum_{v \in \sn} \qiev \theta_q(T_v) x^{e,v},
%\end{equation}
%which allows us to perform the desired evaluations.  If so, then we can
%apply the following result.
%Specifically we have the following.
%Let us illustrate this first for $q=1$,
%i.e., for the rings $\mathbb Z[x_{1,1}, \dotsc, x_{n,n}]$ and $\zsn$.
%Weight the wiring diagram of an expression $s_{i_1} \cdots s_{i_m}$
%by $4m$ {\em commuting} indeterminates as in (\ref{eq:onestar})
%and letting $z_G$ be the product of these.
%For a linear function $\theta: \zsn \rightarrow \mathbb Z$, define
%the generating function
%\begin{equation*}
%  \imm{\theta}(x) = \sum_{v \in \sn} \theta(w) x^{e,w}
%\end{equation*}
%in $\mathbb Z[x_{1,1}, \dotsc, z_{n,n}]$.
%It is straightforward to show that
%\begin{equation*}
%  \theta((1 + s_{i_1}) \cdots (1 + s_{i_m})) = [z_G]\imm{\theta}(B).
%\end{equation*}
%More generally, we have the following.
\begin{thm}\label{t:immeval}
  Let $\theta_q: \hnq \rightarrow \zqq$ be linear, and let wiring diagram
  $G$ of $s_{i_1} \cdots s_{i_m}$ have weighted path matrix $B$.
Then we have
\begin{equation}\label{eq:immeval}
\theta_q((1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})) = 
\sigma_B(\imm{\theta_q}(x)).
\end{equation}
\end{thm}
%($\star$ Define $\imm{\theta_q}(x)$ here or earlier?)
\begin{proof}[Proof of Theorem \ref{t:immeval}]
%Define $\{ a_v \,|\, v \in \sn \}$ in $\mathbb Z[q]$ by
%\begin{equation*}
Write $(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}) = \sum_{v \in \sn} a_v T_v$.
%  = \theta_q((1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})).
%\end{equation*}
Then the right-hand side of
%Equation~
(\ref{eq:immeval}) is
\begin{equation*}
%\begin{aligned}
\sigma_B \Big( \sum_{v \in \sn} \theta_q(T_v) \qiev x^{e,v} \Big) 
= \sum_{v \in \sn} \theta_q(T_v) \qiev \sigma_B(x^{e,v})
= \sum_{v \in \sn} \theta_q(T_v) \qiev \qev a_v
%&= \sum_{v \in \sn} \theta_q(a_vT_v)\\
= \theta_q \Big( \sum_{v \in \sn} a_vT_v \Big),
%\end{aligned}
\end{equation*}
%where the second equality follows from 
by Proposition~\ref{p:qewcoeff}.
But this is precisely the left-hand side of
%Equation~
(\ref{eq:immeval}).
\end{proof}

Now observe that if one fixes a reduced expression $s_{i_1} \cdots s_{i_m}$ for
each $w \in \sn$ and uses each such expression to define an element
\begin{equation*}
  D_w \defeq (1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}) \in \hnq,
\end{equation*}
%in $\hnq$,
then %the set 
$\{ D_w \,|\, w \in \sn \}$ forms a basis of
$\hnq$: we have
%\begin{equation*}
$D_w \in T_w + \spn_{\mathbb Z[q]} \{ T_v \,|\, v < w \}$.
%\end{equation*}
(See also \cite[Corollary 3.6]{Deodhar90}.)  Thus we can evaluate
$\theta_q(g)$ for every $g \in \hnq$, provided that we can expand
$g$ in this basis.

\section{$G$-tableaux and the evaluation of induced sign characters}\label{s:eval}
%\section{$G$-tableaux and the combinatorics of the evaluation map}\label{s:tableaux}
%To combinatorially interpret the evaluation
Given a path family $\pi$ covering a wiring diagram $G$,
we will find it convenient to arrange the paths of $\pi$ into
a Young diagram.
We will call the resulting structure $U$ a {\em $G$-tableau},
or more specifically a {\em $\pi$-tableau}.
If $\type(\pi) = w$, we say that $U$ has type $w$.
We call $U$ {\em left column-strict} if $\pi_b$ appears above $\pi_a$
in a column only when $a < b$. We call $U$ {\em column-strict} 
it is left column-strict and no two paths in a column intersect.
We call $U$ {\em column-closed} if in each column, 
the sets of source and sink indices of paths there are equal.
We define $L(U)$ and $R(U)$ to be the Young tableaux in which paths are replaced by their source indices and sink indices, respectively.
%in each column have the
%same $\pi$-tableau

Let $U$ be a $\pi$-tableau of any shape $\lambda \vdash n$.
Define $\incross(U)$ to be the number of inverted noncrossings of $U$, i.e.,
the number of occurrences of
 \begin{equation}\label{eq:inc}
\begin{tikzpicture}[scale=.7,baseline=-25]
  \draw[dashed] (0,0) -- (1,-1) -- (2,0);
  \draw[-] (0,-2) -- (1,-1) -- (2,-2);
  \node at (-.5,0) {$\pi_b$};
  \node at (-.5,-2) {$\pi_a$};
\end{tikzpicture}\;,
% \raisebox{-7mm}
 %{\includegraphics[height=15mm]{incross.eps}}\ ,
 \end{equation}
where $\pi_b$ appears in an earlier column of $U$ than $\pi_a$
(whether or not $b > a$).  Thus inverted noncrossings may be proper or
defective.   
Define $\cross(U) = \cross(\pi)$ to be the number of crossings of $\pi$, i.e.,
the number of occurrences of
\begin{equation*}
\begin{tikzpicture}[scale=.7,baseline=-25]
  \draw[dashed] (0,0) -- (1,-1) -- (2,-2);
  \draw[-] (0,-2) -- (1,-1) -- (2,0);
  \node at (-.5,0) {$\pi_b$};
  \node at (-.5,-2) {$\pi_a$};
\end{tikzpicture}
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{cr1.eps}}\ 
\qquad
\mathrm{ or }
\qquad 
\begin{tikzpicture}[scale=.7,baseline=-25]
  \draw[-] (0,0) -- (1,-1) -- (2,-2);
  \draw[dashed] (0,-2) -- (1,-1) -- (2,0);
  \node at (-.5,0) {$\pi_a$};
  \node at (-.5,-2) {$\pi_b$};
\end{tikzpicture} \;.
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{cr2c.eps}}\ .
\end{equation*}
This depends only upon $\pi$; not upon the 
locations of $\pi_a$ and $\pi_b$ in $U$.
%($\star$ postpone $\cdncross$ definition until later? It is only used as a
%stepping stone.)
Define $\cdncross(U)$ to be the number of defective noncrossings of pairs of 
paths appearing in the same column of $U$, i.e.,
the number of occurrences of (\ref{eq:inc}) where $b < a$ and $\pi_b$, $\pi_a$ 
appear in the same column of $U$.

\begin{prop}\label{p:sigmastats}
  Let wiring diagram $G$ have weighted path matrix $B$.
For $u,w \in \sn$ we have 
\begin{equation}\label{eq:stats}
\sigma_B (x^{u,w}) = 
\sum_\pi \qp{\cross(\pi)}2
%\sum_U
q^{\incross(U)},
\end{equation}
where the sum is over path families $\pi$ of type $u^{-1}w$ covering $G$,
and $U = U(\pi,u,w)$ is the unique $\pi$-tableau of shape $(n)$
satisfying $L(U) = u$, $R(U) = w$.
\end{prop}
\begin{proof} [Proof of Proposition \ref{p:sigmastats}]
(Omitted.)
%  Let $G = G_{[i_1,i_1+1]} \circ \cdots \circ G_{[i_m,i_m+1]}$.
%  If $s_{i_1} \cdots s_{i_m}$ contains no reduced subexpression for $u^{-1}w$,
%  then there is no path family of type $u^{-1}w$ which covers $G$,
%  and the right-hand side of (\ref{eq:stats}) is $0$.
%  By Proposition~\ref{p:sigmareduced}, the left-hand side is $0$ as well.
%  Now suppose $m = \ell(u^{-1}w)$ and
%  let $s_{i_1} \cdots s_{i_m}$ be a reduced expression for $u^{-1}w$.
%  Then there is exactly one path family of type $u^{-1}w$ that covers $G$.
%  It has $\ell(u^{-1}w)$ crossings and no noncrossings.
%  Thus the right-hand side of (\ref{eq:stats}) is $q_{e,u^{-1}w}$.
%  By Corollary~\ref{c:unitri} and Proposition~\ref{p:sigmareduced},
%  the left-hand side is the same.
%  Thus the claim is true for wiring diagrams $G$ which are concatenations of
%  $0,\dotsc,\ell(u^{-1}w)$ simple transposition diagrams.
%    
%  Now suppose the claim is true for $G$ a concatenation of
%  $m \geq \ell(u^{-1}w)$ simple transposition networks
%  and consider $G = G' \circ H$ where
%  \begin{equation*}
%    G' = G_{[i_1,i_1+1]} \circ \cdots \circ G_{[i_m,i_m+1]},
%    \qquad H = G_{[i_{m+1},i_{m+1}+1]}.
%    \end{equation*}
%    Let $B'$, $C$ be the path matrices of $G'$, $H$, respectively
%    so that $B = B'C$ is the path matrix of $G$.
%    Then by Corollary~\ref{c:sigmacoprod} we have
%  \begin{equation}\label{eq:sigmatwosum}
%    \sigma_B(x^{u,v})
%    =
%    \qp12 \sigma_{B'}(x^{u,ws_{i_{m+1}}}) + \begin{cases}
%      q \sigma_{B'}(x^{u,w}) &\text{if $ws_{i_{m+1}} < w$},\\
%      \sigma_{B'}(x^{u,w}) &\text{if $ws_{i_{m+1}} > w$}.
%      \end{cases}
%  \end{equation}
%  By induction we may interpret $\sigma_{B'}(x^{u,ws_{i_{m+1}}})$
%  and $\sigma_{B'}(x^{u,w})$, respectively, as
%  \begin{equation}\label{eq:sigmainterp}
%    \sum_{\pi^{B'}} \qp{\cross(\pi^{B'})}2 q^{\incross(U(\pi^{B'},u,ws_{i_{m+1}}))}, \qquad
%    \sum_{\pi^{B'}} \qp{\cross(\pi^{B'})}2 q^{\incross(U(\pi^{B'},u,w))},
%  \end{equation}
%  where the sums are over path families of type $u^{-1}ws_{i_{m+1}}$ and $u^{-1}w$,
%  respectively, which cover the wiring diagram $G'$.
%  Substituting these two expressions into
%  the right-hand side of (\ref{eq:sigmatwosum}), we obtain
%  \begin{equation}\label{eq:sigmalong}
%    \sum_{\pi^{B'}} \qp{\cross(\pi^{B'})+1}2 q^{\incross(U(\pi^{B'},u,ws_{i_{m+1}}))} +
%    \begin{cases}
%      \displaystyle{\sum_{\pi^{B'}}} \qp{\cross(\pi^{B'})+2}2 q^{\incross(U(\pi^{B'},u,w))} &\text{if $ws_{i_{m+1}} < w$,}\\
%      \displaystyle{\sum_{\pi^{B'}}} \qp{\cross(\pi^{B'})}2 q^{\incross(U(\pi^{B'},u,w))} &\text{if $ws_{i_{m+1}} > w$,}\\
%    \end{cases}
%  \end{equation}
%where the sums are as in (\ref{eq:sigmainterp}).
%  
%Concatenating a path family $\pi^{B'}$
%which covers $G'$
%to a path family $\pi^C$
%which covers $H$
%we obtain a new path family $\pi^{{B'}C}$
%which covers $G$
%and satisfies
%$\type(\pi^{{B'}C}) = \type(\pi^{B'}) \type(\pi^C)$.
%Conversely, every path family which covers $G$
%decomposes this way.
%If
%$\type(\pi^{B'}) = u^{-1}ws_{i_{m+1}}$ and
%$\type(\pi^C) = s_{i_{m+1}}$ then we have
% \begin{equation}\label{eq:sigmasum}
%       \incross(U(\pi^{{B'}C},u,w)) = \incross(U(\pi^{B'},u,ws_{i_{m+1}})), \qquad
%       \cross(\pi^{{B'}C}) = \cross(\pi^{B'}) + 1.
% \end{equation}
% Otherwise, if $\type(\pi^{B'}) = u^{-1}w$ and $\type(\pi^C) = e$,
% then let $j$ and $k$ be the source indices of
%  the paths in $\pi^{{B'}}$ which terminate at sinks $i_{m+1}$ and $i_{m+1}+1$,
%  respectively. Then we have
%  \begin{equation}\label{eq:precedence}
%    \begin{gathered}
%    \incross(U(\pi^{{B'}C},u,w)) = \incross(U(\pi^{B'},u,w)) +
%    \begin{cases}
%      1 &\text{if $k$ precedes $j$ in $u$,
%     i.e., $u^{-1}_k < u^{-1}_j$},\\
%      0 &\text{otherwise},
%    \end{cases}\\
%    \cross(\pi^{{B'}C}) = \cross(\pi^{B'}). 
%    \end{gathered}
%\end{equation}
%  Since $\type(\pi^{B'}) = u^{-1}w$, the index $k$ is given by
%  $k = (u^{-1}w)^{-1}_{i_{m+1}+1} = (w^{-1}u)_{i_{m+1}+1}$.
%  Thus the first condition in (\ref{eq:precedence}) is equivalent to
%  \begin{equation*}
%    (u^{-1})_{(w^{-1}u)_{i_{m+1}+1}} < (u^{-1})_{(w^{-1}u)_{i_{m+1}}}.
%  \end{equation*}
%  Simplifying the two expressions in this inequality to
%$(w^{-1}uu^{-1})_{i_{m+1}+1} = (w^{-1})_{i_{m+1}+1}$ and
%$(w^{-1}uu^{-1})_{i_{m+1}} = (w^{-1})_{i_{m+1}}$, respectively,
%we obtain the equivalent inequality 
%$ws_{i_{m+1}} < w$.
%
%It follows that the expression in (\ref{eq:sigmalong})
%and therefore the right-hand side of (\ref{eq:sigmatwosum}) can be written as
%\begin{equation}\label{eq:stats2}
%\sum_{\pi^{{B'}C}} \qp{\cross(\pi^{{B'}C})}2
%q^{\incross(U(\pi^{{B'}C},u,w)},
%\end{equation}
%where the sum is over path families of type $u^{-1}w$ which cover $G$.
%Thus the claim is true by induction.
\end{proof}

%The special case $u = e$ of Proposition~\ref{p:sigmastats} yields another proof
%of the formula (\ref{eq:defectdef2}).
%\begin{cor}\label{c:sigmastats}
%  The coefficients in the expansion
%    $(1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}}) = \sum_w a_w T_w$
%are given by
%\begin{equation*}
%  a_w = \sum_\pi q^{\dfct(\pi)},
%\end{equation*}
%where the sum is over all path families of type $w$ which cover the wiring
%diagram of $s_{i_1} \cdots s_{i_m}$.
%\end{cor}
%\begin{proof} 
%  Substituting $u = e$ on the right-hand side of (\ref{eq:stats}),
%  we sum over path families $\pi$ of type $w$ and
%  find that each tableau $U = U(\pi,e,w)$ is simply
%  the sequence $\pi = (\pi_1,\dotsc,\pi_n)$.
%  An inverted noncrossing of $U$ then becomes a noncrossing (\ref{eq:inc})
%  in which the upper path has index less than that of the lower path.
%  This is simply a defective noncrossing.  To combine these with defective
%  crossings, let us temporarily define
%  \begin{equation*}
%    \begin{aligned}
%      \dnc(\pi) &= \text{ number of defective noncrossings of $\pi$},\\
%      \dc(\pi) &= \text{ number of defective crossings of $\pi$}.
%    \end{aligned}
%  \end{equation*}
%  Now observe that for any path familiy of type $w$ we have
%    \begin{equation*}
%    \cross(\pi) = \inv(w) + 2\dc(\pi)
%    \end{equation*}
%    because if paths $\pi_a$, $\pi_b$ cross $k$ times,
%    then at most one of those crossings contributes to $\inv(w)$,
%    while exactly half of the remaining crossings are defective.
%    Thus the right-hand side of (\ref{eq:stats}) becomes
%    \begin{equation}\label{eq:rhsstats}
%      \sum_\pi \qp{\inv(w) + 2\dc(\pi)}2 q^{\dnc(\pi)}
%      = \sum_\pi \qew q^{\dc(\pi)+\dnc(\pi)} = \qew \sum_\pi q^{\dfct(\pi)},
%    \end{equation}
%    where the sum is over all path families of type $w$ which cover the
%    wiring diagram of $s_{i_1} \cdots s_{i_m}$.
%
%    Substituting $u = e$ on the left-hand side of (\ref{eq:stats})
%  and applying Proposition \ref{p:qewcoeff} we have $\qew a_w$.
%  Combining this with (\ref{eq:rhsstats}), we have the desired result.
%\end{proof}

%\section{Evaluation of induced sign characters}\label{s:eval}

By Theorem~\ref{t:immeval}, the map $\sigma_B$ (\ref{eq:sigmadef})
can be used to evaluate $\epsilon_q^\lambda(D_w)$ when one has a simple
expression for the generating function
$\imm{\epsilon_q^\lambda}(x)$
%which allows us to evaluate
and can evaluate
$\sigma_B(\imm{\epsilon_q^\lambda}(x))$.
Such an expression was given by Konvalinka
and the third author in \cite[Theorem 5.4]{KSkanQGJ}:
\begin{equation}\label{eq:immepsilon}
  \imm{\epsilon_q^\lambda}(x) =
  \sum_{(I_1,\dotsc,I_r)} \qdet(x_{I_1,I_1}) \cdots \qdet(x_{I_r,I_r}),
\end{equation}
where $\lambda = (\lambda_1,\dotsc,\lambda_r)$,
$\qdet$, $(x_{I,I})$ are defined as in Section~\ref{s:qmb},
and the sum is over all ordered set partitions of $\{1,\dotsc,n\}$ satisfying
$|I_j| = \lambda_j$.  We will say that such an ordered set
partition has {\em type} $\lambda$.
To evaluate $\sigma_B(\imm{\epsilon_q^\lambda}(x))$, we will expand
the right-hand side of (\ref{eq:immepsilon}) and recognize the resulting
monomials as elements of bases $\{x^{u,v} \,|\, v \in \sn \}$ of $\Ann$.
%presented in Section~\ref{s:qmb}.  
%Section~\ref{s:mbases}.  
These bases are best described
in terms of the {\em Young subgroup} $\slambda$ of $\sn$,
%Define $\slambda$ to be 
the subgroup 
%of $\sn$ 
generated by
%\begin{equation*}
%\label{eq:youngsubgen}
%J \defeq 
$\{ s_1, \dotsc, s_{n-1} \} \ssm 
\{ s_{\lambda_1}, s_{\lambda_1 + \lambda_2}, 
s_{\lambda_1 + \lambda_2 + \lambda_3}, 
\dotsc, 
s_{n-\lambda_r} \}$.
%\end{equation*}
Let $\slambdamin$ be the set of Bruhat-minimal representatives of cosets
of the form $\slambda u$, i.e., the elements $u \in \sn$ for which each
of the subwords
\begin{equation}\label{eq:subwordsofu}
u_1 \cdots u_{\lambda_1}, \qquad 
u_{\lambda_1 +1} \cdots u_{\lambda_1 + \lambda_2}, \quad
\dotsc, \quad
u_{n-\lambda_r + 1} \cdots u_n
\end{equation}
is strictly increasing.
%It is clear that such
Such elements correspond bijectively to 
ordered set partitions $(I_1, \dotsc, I_r)$ of $[n]$ of type $\lambda$.
Specifically, the correspondence $u \mapsto I(u)$ is given by
%$I_1 = \{ u_1, \dotsc, u_{\lambda_1} \}$, 
\begin{equation}\label{eq:uI}
  I_j = \{ u_{\lambda_1 +\cdots+ \lambda_{j-1} + 1}, \dotsc, u_{\lambda_1 +\cdots+ \lambda_j} \}
  \text{ for } j = 1,\dotsc,r.
\end{equation}
We will let $u(I)$ denote the permutation in $\slambdamin$ which corresponds
to $I$.
%, i.e., the permutation whose one-line notation is the increasing
%rearrangement of $I_1$, followed by the increasing rearrangement of $I_2$, etc.
%If $u \in \slambdamin$ corresponds to $(I_1, \dotsc, I_r)$,
%then the path indices in row $j$ of $U(u,\pi,\lambda)$
%are simply the elements of $I_j$, in increasing order. 

%In order 
To interpret 
$\epsilon_q^\lambda((1+T_{s_{i_1}}) \cdots (1+T_{s_{i_m}}))
= \sigma_B(\imm{\epsilon_q^\lambda}(x))$,
we refer to the treatment of the formula (\ref{eq:immepsilon}) which appears in
%and to its dissection in 
\cite[Equation (6.1)]{CHSSkanEKL}: 
\begin{equation}\label{eq:lambepsilon}
%\begin{aligned}
%\epsilon_q^\lambda((1+T_{s_{i_1}}) \cdots (1+T_{s_{i_m}}))
%&= \sigma_B(\imm{\epsilon_q^\lambda}(x))\\
%&= 
\sum_{(I_1,\dotsc,I_r)} \sigma_B(\qdet(x_{I_1,I_1}) \cdots \qdet(x_{I_r,I_r})) 
= \sum_{u \in \slambdamin} \sum_{y \in \slambda}
%&= \sum_{u \in \slambdamin} \sum_{y \in u^{-1}\slambda u} 
%(-1)^{\ell(uy)-\ell(u)}q_{u,uy}^{-1} \sigma_B (x^{u,uy}),
(-1)^{\ell(y)}q_{e,y}^{-1} \sigma_B (x^{u,yu}),
%\end{aligned}
\end{equation}
where the first sum is over all ordered set partitions $(I_1,\dotsc, I_r)$
of $[n]$ of type $\lambda$.
%Let us therefore consider evaluations of the form 
%$\sigma_B (x^{u,v})$.
%(See, e.g., \cite{CurtisLIT}.)
%satisfying
%\begin{equation*}
%u_1 < \cdots < u_\lambda, \qquad u_{\lambda_1 +1} < \cdots < u_{\lambda_1 + \la%mbda+2}, 
%\dotsc, u_{n-\lambda_r + 1} < \cdots < u_n.
%\end{equation*}
%In order 
To interpret the final sum in (\ref{eq:lambepsilon})
we need to consider evaluations of the form
(\ref{eq:stats}) only for $u \in \slambdamin$ for some
partition $\lambda = (\lambda_1,\dotsc,\lambda_r) \vdash n$,
%and $v = uy$ for $y \in u^{-1}\slambdamin u$.
and $v = yu$ for $y \in \slambdamin$.
Since elements of $\slambdamin$ correspond bijectively to ordered set
partitions $I$ of $[n]$ of type $\lambda$, and $\sigma_B(x^{u,yu})$ has
the interpretation given in Proposition~\ref{p:sigmastats},
it will be convenient to define
\begin{equation*}
%  \begin{aligned}
    \mathcal U_I = \mathcal U_I(G)
%    =\{ U(\pi, u, uy ) \,|\, \pi \text{ covers } G, u = u(I),
    =\{ U(\pi, u, yu ) \,|\, \pi \text{ covers } G, u = u(I), 
    \type(\pi) = y \in \slambda \}.
%    \type(\pi) = y \in u^{-1}\slambda u \}.
%  \end{aligned}
\end{equation*}
Note that our restriction on $y$ forces the sink indices of paths located in
the $\lambda_j$ entries
%components
%\begin{equation*}
  $(\lambda_1 + \cdots + \lambda_{j-1}+1), \dotsc, (\lambda_1 + \cdots + \lambda_j)$
%\end{equation*}
%of $U(\pi,u,uy)$ to be a permutation of the source indices of the same paths.
of $U(\pi,u,yu)$ to be a permutation of the source indices of the same paths.

On the other hand, the final sum in (\ref{eq:lambepsilon}) has both
positive and negative signs.  We will obtain a subtraction-free expression
for this sum
%$\epsilon_q^\lambda((1+T_{s_{i_1}}) \cdots (1+T_{s_{i_m}}))$
by defining a sign-reversing involution $\zeta = \zeta_I$
for each ordered set partition $I$ of type 
$\lambda = (\lambda_1,\dotsc,\lambda_r)$.
%This will cancel all negative
%contributions from expressions of the form $\sigma_B(x^{u,uy})$
%with some positive contributions of the same form.
It will be convenient to define this involution on a second set of tableaux,
in obvious bijection with the first set.
%Fix a partition $\lambda = (\lambda_1, \dotsc, \lambda_r) \vdash n$,
%an ordered set partition $I$ of $[n]$ of type $\lambda$, 
%and a star 
%%descending star 
%network $G$,
%%and let $\mathcal T_\lambda = \mathcal T_\lambda(F)$ 
%and
For a wiring diagram $G$,
% of $s_{i_1} \cdots s_{i_m}$,
% representing $(1 + T_{s_{i_1}}) \cdots (1+ T_{s_{i_m}})$,
let $\mathcal T_I = \mathcal T_I(G)$ be 
the set of all column-closed, left column-strict $G$-tableaux 
$W$ of shape $\lambda^\tr$
such that $L(W^\tr)_j = I_j$ (as sets) for $j = 1,\dotsc,r$.
%Observe that all column-strict $G$-tableaux of type $e$ 
%satisfying $L(U^\tr)_j = I_j$ (as sets) for $j = 1,\dotsc,r$
%belong to $\mathcal T_I$.  ($\star$ Is this important?)
The bijection $\delta_I: \mathcal U_I \rightarrow \mathcal T_I$ 
%is given by
maps $U \in \mathcal U_I$ to the left column-strict tableau $W$ 
of shape $\lambda^\tr$ 
whose $j$th column consists of entries
%to be the one-rowed tableau consisting of components
$(\lambda_1 + \cdots + \lambda_{j-1}+1), \dotsc,
(\lambda_1 + \cdots + \lambda_j)$ of $U$.
%$U \in \mathcal U_I$,
%for $j = 1, \dotsc, r$,
%and by defining $\delta_I(U) = V^\tr$.

Since $U$ and $\delta_I(U)$ contain the same path family, it is easy to see
that $\delta_I$ does not affect the statistic $\cross$.
It changes the statistic $\incross$ in a very simple way.
\begin{lem}\label{l:TU}
Let $W = \delta_I(U)$. Then we have
%\begin{equation*}
$\incross(U) = \incross(W) + \cdncross(W)$.
%\end{equation*}
\end{lem}
\begin{proof} [Proof of Lemma \ref{l:TU}]
(Omitted.)
\end{proof}

Fixing a wiring diagram $G$ and ordered set partition $I$, 
we define a sign-reversing involution
%\begin{equation*}
%\label{eq:zeta}
%\zeta: \mathcal T_\lambda \rightarrow \mathcal T_\lambda
$\zeta: \mathcal T_I \rightarrow \mathcal T_I$
%\end{equation*}
as follows. 
%($\star$ or something like this).  
%($\star$ This definition isn't quite right.  Fix it.)  (Yes it is?)
\begin{enumerate}
\item If $W$ is a column-strict tableau of type $e$, then define $\zeta(W) = W$.
\item Otherwise, 
  \begin{enumerate}
  \item Let $t$ be the 
%least
greatest index such that column $t$ of $W$ is not column-strict.
\item Let $k$ be the greatest index such that
two paths $\pi_j$, $\pi_{j'}$ with $j, j' \in I_t$
both pass through the central vertex of the factor network $G_{[i_k, i_{k+1}]}$,
and let $\pi'_j$, $\pi'_{j'}$ be the paths obtained 
by swapping the terminal subpaths of $\pi_j$ and $\pi_{j'}$, beginning
at the central vertex of $G_{[i_k,i_{k+1}]}$.
%and let $\pi'_j$, $\pi'_{j'}$ be the paths which are equal to 
%$\pi_j$, $\pi_{j'}$, respectively, from sources $j$, $j'$ to the 
%central vertex of $G_{[i_k,i_{k+1}]}$, and which are equal to $\pi_{j'}$, $\pi_j$
%respectively from that point to their sinks.
%\item Let $(j,j')$ be the 
%%right-to-left 
%lexicographically greatest 
%%lexicographically least
%pair of indices in 
%%$L(U)_i$ 
%$I_t$ such that 
%$j < j'$, path $\pi_j$ appears to the left of path $\pi_{j'}$
%$\pi_j$ and $\pi_{j'}$ 
%%appear in $U_i$, and the two paths 
%intersect ($j < j'$).
%%Let $(j,j')$ be the lexicographically greatest pair of indices 
%%such that $j < j'$, path $\pi_j$ appears to the left of path $\pi_{j'}$
%%in $U_i$, and the two paths intersect.
%%  \item Let $(k,k')$ be the sink indices of paths $\pi_j$ and $\pi_{j'}$, respectively.
\item Using the above indices $j, j'$,
  define $\zeta(W)$ to be the tableau obtained from $W$ by replacing
$\pi_j$, $\pi_{j'}$ by $\pi'_j$, $\pi'_{j'}$, respectively. 
%the unique paths in $F$ from
%source $j$ to sink $k'$ and source $j'$ to sink $k$.
  \end{enumerate}
\end{enumerate}

%\begin{lem}\label{l:lengthdiff}
%Let $I = (I_1, \dotsc I_r)$ be an ordered set partition of type $\lambda$.
%  Let $U, V \in \mathcal U_I$ satisfy $\zeta(\delta_I(U)) = \delta_I(V)$.
%Then we have the following.
%\begin{enumerate}[(i)]
%\item $U = U(\pi, u, v)$, $V = U(\pi', u, v')$ 
%  for some path families $\pi$, $\pi'$ related as above,
%  and some $v, v' \in \slambda u$.
%\item The permutations $v$, $v'$ satisfy $|\ell(v) - \ell(v')| = 1$.
%\end{enumerate}
%\end{lem}
%\begin{proof}
%(i) For any tableau $W \in \mathcal U_I$, the tableau $\delta_I(W)$
%contains the same path family as $W$.  The definition of $\zeta_I$
%then implies that $\pi$, $\pi'$ are related as claimed.
%Since elements of $\mathcal T_I$ are column-closed, it follows that
%the set of sink indices of paths in each column 
%are equal to the source indices of paths in the same column.
%Thus the two sequences of sink indices,
%read bottom-to-top in columns $1, \dotsc, r$, belong to $\slambda u$.
%But these are precisely $v$ and $v'$.
%
%\noindent (ii) By the definition of $\zeta_I$, the permutations $v$ and $v'$
%differ from one another in exactly two positions: those holding the 
%letters $v_j = v'_{j'}$ and $v_{j'} = v'_j$.  Both letters 
%belong to the same block of the ordered set partition $I$.
%Since we used the rightmost vertex in $\pi_j \cap \pi_{j'}$
%to define $\pi'_j$ and $\pi'_{j'}$, the letters must appear
%consecutively in $v$ and in $v'$.
%It follows that $v' = sv$ for some adjacent transposition $s \in \slambda$.
%\end{proof}
 
\begin{prop}\label{p:zeta}
%  Fix $G$ representing $(1 + T_{s_{i_1}}) \cdots (1+ T_{s_{i_m}})$, and
  Fix $W \in \mathcal T_I$ containing path family $\pi = (\pi_1, \dotsc, \pi_n)$
  and satisfying $\zeta(W) \neq W$.
  Let $\pi'$ be the path family in $\zeta(W)$ 
%contain path family $\pi'$
%  ($= \pi$ with $\pi_j$, $\pi_{j'}$ replaced by $\pi'_j$, $\pi'_{j'}$
%  as in the definition of $\zeta$).
  and let $v = R(\delta_I^{-1}(W))$, $v' = R(\delta_I^{-1}(\zeta(W)))$.
Then we have
% involution $\zeta$ satisfies 
%\begin{equation}\label{eq:incrosseq}
$\incross(\zeta(W)) = \incross(W)$ and
%\end{equation}
%and
\begin{equation}\label{eq:cdncrosseq}
\cdncross(\zeta(W)) 
%+ \incross(\zeta(U)) 
%+ \cross(\zeta(U))/2
%+ \frac{\cross(\zeta(U))}2
+ \frac{\cross(\pi')}2
=
\begin{cases}
\cdncross(W) 
%+ \incross(U) 
+ \frac{\cross(\pi)+1}2  
%&\text{if $\type(\pi) < \type(\pi')$,}\\
&\text{if $v < v'$,}\\
\cdncross(W) 
%+ \incross(U) 
+ \frac{\cross(\pi)-1}2  
%&\text{otherwise.}
&\text{if $v > v'$.}
\end{cases}
\end{equation}
\end{prop}
\begin{proof} [Proof of Proposition \ref{p:zeta}]
(Omitted.)
%To verify (\ref{eq:incrosseq}), 
%let $j''$ be an index which does not belong to $I_t$.
%Then $\pi_{j''}$ is an entry of $W$ and $\zeta(W)$ which does not appear 
%in column $t$.
%Clearly, any point of intersection between 
%$\pi_{j''}$ and 
%$\pi_j$ or $\pi_{j'}$
%which occurs in $G$ to the left of the central vertex of $G_{[i_k, i_k+1]}$
%exactly matches an intersection between 
%$\pi_{j''}$ and 
%$\pi'_j$ or $\pi'_{j'}$.
%On the other hand, suppose that $\pi_{j''}$ and $\pi_j$ (or $\pi_{j'}$) 
%have a point of intersection in $G$ to the right of 
%the central vertex of $G_{[i_k, i_k+1]}$.
%Since $j$ and $j'$ both belong to $I_t$,
%this point is an inverted noncrossing of 
%$\pi_{j''}$ and $\pi_j$ (or $\pi_{j'}$) in $W$
%if and only if it is an inverted noncrossing of
%$\pi_{j''}$ and $\pi'_{j'}$ (or $\pi'_j$) in $\zeta(W)$.
%
%To verify (\ref{eq:cdncrosseq}), consider the intersection of 
%$\pi_j$ and $\pi_{j'}$ at the central vertex of $G_{[i_k, i_k+1]}$ and the
%tableaux $U = \delta_I^{-1}(W)$, $U' = \delta_I^{-1}(\zeta(W))$.
%We have $v = R(U)$, $v' = R(U')$.
%If $v > v'$
%then our choice of $(j,j')$ implies
%that this intersection is either a defective
%noncrossing or a crossing that sends $\pi_j$ above $\pi_{j'}$.
%In the first case, the map $\zeta$ 
%removes exactly one defective noncrossing and creates exactly one crossing, 
%changing the statistic sum $\cdncross + \cross/2$ by $-1 + 1/2 = -1/2$.
%In the second case, the map $\zeta$ 
%removes exactly one crossing and creates exactly one proper noncrossing, 
%changing the same sum by $-1/2 + 0 = -1/2$.
%Similarly, if
%$v < v'$
%then our choice of $(j,j')$ implies
%that the intersection is either a proper noncrossing or a crossing that 
%sends $\pi_{j'}$ above $\pi_j$.  In both cases, the statistic sum increases
%by $1/2$.
\end{proof}

Now we can state and prove our main result.
\begin{thm}\label{t:qepsilon}
Let $G$ be the wiring diagram of $s_{i_1} \cdots s_{i_m}$.
Then for $\lambda \vdash n$ 
we have
\begin{equation*}
%\label{eq:epsilonmain}
\epsilon_q^\lambda((1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})) 
= \sum_U q^{\incross(U)+\cross(U)/2},
\end{equation*}
where the sum is over all column-strict $G$-tableaux 
of type $e$ and shape $\lambda^\tr$.
\end{thm}
\begin{proof} [Proof of Theorem \ref{t:qepsilon}] (Idea.)
Apply Proposition~\ref{p:sigmastats} and Lemma~\ref{l:TU}
to all monomials in (\ref{eq:lambepsilon}) to obtain
\begin{equation}\label{eq:sumtocancel}
  \sum_{(y,\pi)} (-1)^{\ell(y)}  q_{e,y}^{-1}
  \qp{\cross(\pi)}2
  q^{\incross(W)+\cdncross(W)},
\end{equation}
where the sum is over pairs $(y,\pi)$ with
$y \in \slambda$ and $\pi$ a path family of type $u^{-1}yu$ which covers $G$.
$W = \delta_I(U(\pi,u,yu))$ is then uniquely determined by $(y,\pi)$ and
%By Lemma~\ref{l:TU} this in turn is equal to
%where $W = \delta_I(U)$.
%Thus as $y,\pi$ vary as above,
%we have that $W$
varies over all tableaux in $\mathcal T_I$. Contributions from
tableaux $W$, $\zeta(W) \neq W$
%\zeta(W)$ 
cancel one another, 
and by Proposition~\ref{p:zeta} the remaining tableaux contribute
the claimed powers of $q$.
%Let $B$ be the path matrix of $G$ and let $(I_1,\dotsc,I_r)$ be a set
%partition of $[n]$ of type $\lambda$.
%By (\ref{eq:lambepsilon}),
%there is a permutation $u \in \slambdamin$ 
%corresponding to $(I_1,\dotsc,I_r)$ such that we have
%\begin{equation*}
%\sigma_B(\qdet(x_{I_1,I_1}) \cdots \qdet(x_{I_r,I_r})) = 
%\sum_{y \in \slambda} (-1)^{\ell(y)}  q_{e,y}^{-1} \sigma_B ( x^{u, yu} ).
%\end{equation*}
%By Proposition~\ref{p:sigmastats} this is equal to
%\begin{equation}\label{eq:ypiinvuupi}
%  \sum_{(y,\pi)} (-1)^{\ell(y)} \qp{\cross(\pi)}2 q^{\incross(U)},
%\end{equation}
%where the sum is over pairs $(y,\pi)$ such that 
%$y \in \slambda$ and $\pi$ is a path family of type $u^{-1}yu$ which covers $G$.
%The tableau
%$U = U(\pi,u,yu) \in \mathcal U_I$ is then uniquely determined by $(y,\pi)$.
%By Lemma~\ref{l:TU} this in turn is equal to
%\begin{equation}\label{eq:sumtocancel}
%  \sum_{(y,\pi)} (-1)^{\ell(y)}  q_{e,y}^{-1}
%  \qp{\cross(\pi)}2
%  q^{\incross(W)+\cdncross(W)},
%\end{equation}
%where $W = \delta_I(U)$.
%Thus as $y,\pi$ vary as above, we have that $W$
%varies over all tableaux in $\mathcal T_I$. 
%
%Now consider a tableau $W \in \mathcal T_I$ which satisfies $\zeta(W) \neq W$.
%Let tableaux $W$ and $\zeta(W)$ contain path families $\pi$ of type $u^{-1}yu$
%and $\pi'$ of type $u^{-1}y'u$.  Assume without loss of generality that
%$\ell(y) < \ell(y') = \ell(y) + 1$.  Then the terms of (\ref{eq:sumtocancel})
%which correspond to $W$ and $\zeta(W)$ are
%\begin{equation}\label{eq:Wcont}
%  (-1)^{\ell(y)} \qm{\ell(y)}2 \qp{\cross(\pi)}2 q^{\incross(W) + \cdncross(W)}
%\end{equation}
%and by Proposition~\ref{p:zeta}
%\begin{equation*}
%  (-1)^{\ell(y')} \qm{\ell(y')}2 \qp{\cross(\pi')}2 q^{\incross(\zeta(W)) + \cdncross(\zeta(W))}
%  = (-1)^{\ell(y)+1} \qm{\ell(y)}2 \qm12 \qp{\cross(\pi)+1}2 q^{\incross(W) +\cdncross(W)}, 
%\end{equation*}
%which is the opposite of the expression in (\ref{eq:Wcont}).
%Thus the terms of (\ref{eq:sumtocancel}) indexed by
%$(y,\pi)$, $(y',\pi')$ corresponding to $W$, $\zeta(W)\neq W$
%cancel to contribute $0$.
%Thus it suffices to sum only the terms indexed by pairs $(y,\pi)$ corresponding
%to tableaux $W = \zeta(W)$.  By the definition of $\zeta$, these tableaux
%are column-strict and therefore satisfy $\cdncross(W) = 0$.
\end{proof}

\begin{cor} \label{lastcor}
Let $G$ be the wiring diagram of a reduced expression 
%$s_{i_1}\cdots s_{i_m}$
%is a reduced wiring diagram 
for a $321$-hexagon-avoiding permutation $w$. Then we have
\begin{equation*}
\epsilon_q^\lambda(\qew C'_w(q)) = \smash{\sum_U} q^{\incross(U)+\cross(U)/2},
\end{equation*}
where the sum is over all column-strict $G$-tableaux 
%$U$ 
of 
type $e$
and 
shape $\lambda^\tr$.
\end{cor}
\begin{proof} [Proof of Corollary \ref{lastcor} ]
Billey and Warrington~\cite[Theorem 1]{BWHex} showed that if this reduced expression is $s_{i_1} \cdots s_{i_m}$ then we have
%in this case we have
%if $s_{i_1} \cdots s_{i_m}$
%is a reduced expression for $w$ avoiding
%the patterns $321$, $56781234$, $56718234$, $46781235$, $46718235$,
%%and if $s_{i_1} \cdots s_{i_m}$ is a reduced expression for $w$, 
%then we have
$\qew C'_w(q) = (1 + T_{s_{i_1}}) \cdots (1 + T_{s_{i_m}})$.
(See page 5.)
%($\star$) Do I need $\qiew$ or $\qew$ next to each Kazhdan--Lusztig basis element?
\end{proof}
  
To illustrate the theorem, we compute 
$\smash{\epsilon_q^{21}}((1+T_{s_1})(1+T_{s_2})(1+T_{s_1}))$ 
using the wiring diagram
%consider the wiring diagram 
(\ref{eq:Gbraidfig}).
There are two path families of type $e$ which cover $G$, and one 
column-strict $G$-tableau of shape $21^\tr = 21$ for each:
\begin{equation}\label{eq:Gtableaux}
\begin{tikzpicture}[scale=.5,baseline=-15]
  \draw[dotted] (0,0) -- (1,0) -- (1.5,-.5) -- (2,0) -- (3,0);
  \draw[dashed] (0,-1) -- (.5,-1.5) -- (1.5,-.5) -- (2.5,-1.5) -- (3,-1);
  \draw[-,thick] (0,-2) -- (.5,-1.5) -- (1,-2) -- (2,-2) -- (2.5,-1.5) -- (3,-2);
  \node at (-.5,0) {$\pi_3$};
  \node at (-.5,-1) {$\pi_2$};
  \node at (-.5,-2) {$\pi_1$};
\end{tikzpicture} 
\;, \quad
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{braid1.eps}}\ , \quad
U_\pi = \tableau[scY]{\pi_3 | \pi_1,\pi_2}
\;; \qquad
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{tableaupi.eps}}\ , \qquad \qquad
\begin{tikzpicture}[scale=.5,baseline=-15]
  \draw[dotted] (0,0) -- (1,0) -- (1.5,-.5) -- (2,0) -- (3,0);
  \draw[dashed] (0,-1) -- (1,-2) -- (2,-2) -- (3,-1);
  \draw[-,thick] (0,-2) -- (1.5,-.5) -- (3,-2);
  \node at (-.5,0) {$\rho_3$};
  \node at (-.5,-1) {$\rho_2$};
  \node at (-.5,-2) {$\rho_1$};
\end{tikzpicture} 
\;, \quad
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{braid2.eps}}\ , \quad
U_\rho = \tableau[scY]{\rho_3 | \rho_2,\rho_1} \;.
%\raisebox{-7mm}
%{\includegraphics[height=15mm]{tableausig.eps}}\ .
%\ \begin{matrix}
%\pi_3 & \\
%\pi_1 & \pi_2 
%\end{matrix},
\end{equation}
%where $\pi = (\pi_1, \pi_2, \pi_3)$ is the unique noncrossing path family
%covering $G$.  
Tableau $U_\pi$ contributes 
$q^{\incross(U_\pi)}q^{\cross(U_\pi)/2} = q^1q^{0/2} = q$,
since $\pi$ has no crossings, 
and only one of its noncrossings is inverted in $U_\pi$:
$\pi_3$ intersects $\pi_2$ from above 
and appears in an earlier column of $U_\pi$.
Tableau $U_\rho$ contributes 
$q^{\incross(U_\rho)}q^{\cross(U_\rho)/2} = q^1q^{2/2} = q^2$,
since $\rho$ has two crossings, 
and its unique noncrossing is inverted in $U_\rho$:
$\rho_3$ intersects $\rho_1$ from above 
and appears in an earlier column of $U_\rho$.
Adding the two contributions together, we have
$\smash{\epsilon_q^{21}}((1+T_{s_1})(1+T_{s_2})(1+T_{s_1})) = q + q^2.$ 


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



\end{document}

