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

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

\usepackage{tikz}
\usepackage{tabularx}
\usepackage{tabmac_avi}
\usetikzlibrary{arrows.meta}
\tikzset{>={Latex[width=1.2mm,length=1.7mm]}}
\newenvironment{proofidea}{\noindent \paragraph{\emph{Proof idea.}}}{\hfill $\Box$}
\newenvironment{proofomitted}{\noindent \paragraph{\emph{Proof omitted.}}}{\hfill $\Box$} 


\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}

\numberwithin{equation}{section}

\newcommand{\sn}{\mathfrak{S}_n}
\newcommand{\sr}{\mathfrak{S}_r}
\newcommand{\mfs}[1]{\mathfrak{S}_{#1}}
\newcommand{\mfsmin}[1]{\mathfrak{S}_-^{#1}}
\newcommand{\zsn}{\mathbb{Z}[\sn]}
\newcommand{\qsn}{\mathbb{Q}[\sn]}
\newcommand{\cx}{\mathbb{C}[x]}
\newcommand{\zx}{\mathbb{Z}[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{\qp}[2]{q^{\frac{#1}{#2}}}
\newcommand{\qm}[2]{q^{\negthinspace\Bar\,\frac{#1}{#2}}}
\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_u}
\newcommand{\qet}{q_t}
\newcommand{\qey}{q_y}
\newcommand{\qev}{q_v}
\newcommand{\qew}{\smash{\qp{\ell(w)}2}}
\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{\qiew}{\qm{\ell(w)}2}
\newcommand{\qiey}{q_y^{-1}}
\newcommand{\qiev}{q_v^{-1}}
\newcommand{\qieyp}{q_{y'}^{-1}}
\newcommand{\qiez}{q_{e,z}^{-1}}
\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{\hbnq}{H_n^B(q)}
\newcommand{\hrq}{H_r(q)}
\newcommand{\A}{\mathcal{A}}
\newcommand{\K}{\mathcal{B}}
\newcommand{\anq}{\mathcal{A}(n,q)}
\newcommand{\atwonq}{\mathcal{A}(2n,q)}
\newcommand{\arq}{\mathcal{A}(r;q)}
\newcommand{\arnq}{\mathcal{A}_r}
\newcommand{\annq}{\mathcal{A}_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{\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{\wtc}[2]{\widetilde{C}_{#1}(#2)}
\newcommand{\dksf}[2]{\tilde{F}_{#2}^{(#1)}}
\newcommand{\ksf}[2]{s_{#2}^{(#1)}}
\newcommand{\qdkst}[2]{\delta_q^{#2,(#1)}}
\newcommand{\dkst}[2]{\delta^{#2,(#1)}}
\newcommand{\qkst}[2]{\chi_q^{#2,(#1)}}
\newcommand{\kst}[2]{\chi^{#2,(#1)}}
\newcommand{\bolk}[3]{\mathbf{K}_{#2,#3}^{(#1)}}

\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{\cimm}[1]{\mathrm{Imm}_{#1}^C}

\newcommand{\sumsb}[1]{\sum_{\substack{#1}}} 
\newcommand{\stat}{\textsc{stat}}
\newcommand{\inv}{\textsc{inv}}
\newcommand{\pinv}{\textsc{inv}_{\ntnsp P}}
\newcommand{\rinv}{\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{\hgt}{\mathrm{hgt}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\triv}{\mathrm{triv}}
\newcommand{\wgt}{\mathrm{wgt}}
\newcommand{\type}{\mathrm{type}}
\newcommand{\sh}{\mathrm{sh}}
\newcommand{\rp}{\mathrm{rp}}
\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{\ktr}[1]{{{#1}\ntnsp\top \negthickspace}}
\newcommand{\ntnsp}{\negthinspace}
\newcommand{\ntksp}{\negthickspace}
\newcommand{\nTksp}{\negthickspace\negthickspace}
\newcommand{\nTknsp}{\negthickspace\negthickspace\negthinspace}
\newcommand{\nTtksp}{\negthickspace\negthickspace\negthickspace}
\newcommand{\nTTksp}{\negthickspace\negthickspace\negthickspace
	\negthickspace}
\newcommand{\nTTtksp}{\negthickspace\negthickspace\negthickspace
	\negthickspace\negthickspace}
\newcommand{\bp}{\begin{prob}}
\newcommand{\ep}{\end{prob}}


\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,\mathbb{C}))}
%\newcommand{\oqglnc}{{\mathcal O}_q(GL(n,\mathbb{C}))}
%\newcommand{\oslnc}{{\mathcal O}(SL(n,\mathbb{C}))}
%\newcommand{\oslthreec}{{\mathcal O}(SL(3,\mathbb{C}))}
%\newcommand{\oqslnc}{{\mathcal O}_q(SL(n,\mathbb{C}))}
\newcommand{\oglnc}{{\mathcal O}(\mathrm{GL}_n (\mathbb C))}
\newcommand{\oqglnc}{{\mathcal O}_q(\mathrm{GL}_n (\mathbb C))}
\newcommand{\oslnc}{{\mathcal O}(\mathrm{SL}_n) (\mathbb C)}
\newcommand{\oslthreec}{{\mathcal O}(\mathrm{SL}_3 (\mathbb C))}
\newcommand{\oqslnc}{{\mathcal O}_q(\mathrm{SL}_n (\mathbb C))}
\newcommand{\ospnc}{{\mathcal O}(\mathrm{SP}_{2n} (\mathbb C))}
\newcommand{\oqspnc}{{\mathcal O}_q(\mathrm{SP}_{2n} (\mathbb C))}
\newcommand{\uglnc}{U(\mathfrak{gl}(n,\mathbb{C}))}
\newcommand{\uqglnc}{U_q(\mathfrak{gl}(n,\mathbb{C}))}
\newcommand{\uslnc}{U(\mathfrak{sl}(n,\mathbb{C}))}
\newcommand{\uqslnc}{U_q(\mathfrak{sl}(n,\mathbb{C}))}
\newcommand{\uspnc}{U(\mathfrak{sp}_{2n}(\mathbb{C}))}
\newcommand{\uqspnc}{U_q(\mathfrak{sp}_{2n}(\mathbb{C}))}
\newcommand{\mat}[1]{\mathrm{Mat}_{#1 \times #1}}
\newcommand{\spc}[1]{\mathfrak{sp}_{#1}(\mathbb{C})}
\newcommand{\slc}[1]{\mathfrak{sl}_{#1}(\mathbb{C})}

\newcommand{\qdet}{\mathrm{det}_q}
\newcommand{\qper}{\mathrm{per}_q}
\newcommand{\perm}{\mathrm{per}}
%\newcommand{\exp}{\mathrm{exp}}
\newcommand{\ctype}{\mathrm{ctype}}
\newcommand{\frobch}{\mathrm{ch}}
\newcommand{\inc}{\mathrm{inc}}
\newcommand{\permmon}[2]{#1_{1,#2_1} \ntnsp\cdots {#1}_{n,#2_n}}
\newcommand{\sprod}[2]{s_{#1_1} \ntnsp\cdots s_{#1_#2}}
\newcommand{\sintprod}[3]{s_{[#1_1,#2_1]} \ntnsp\cdots s_{[#1_#3, #2_#3]}}
\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^{-}}
\newcommand{\core}[2]{\mathfrak{c}_{#1}(#2)}
\newcommand{\phmin}{\phantom{-}}
%\newcommand{\oglnc}{{\mathcal O}(GL(n,\mathbb{C}))}
%\newcommand{\oqglnc}{{\mathcal O}_q(GL(n,\mathbb{C}))}
%\newcommand{\oslnc}{{\mathcal O}(SL(n,\mathbb{C}))}
%\newcommand{\oqslnc}{{\mathcal O}_q(SL(n,\mathbb{C}))}
\newcommand{\sdot}{\left[ \begin{smallmatrix} 0 & -1 \\ 1 & \phantom{-}0 \end{smallmatrix}\right]}
\newcommand{\sddot}{\left[ \begin{smallmatrix} \phantom{-}0 & 1 \\ -1 & 0 \end{smallmatrix}\right]}
\newcommand{\sreg}{\left[ \begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right]}
\newcommand{\abdiag}[1]{\left[ \begin{smallmatrix} 1 & #1 \\ 0 & 1 \end{smallmatrix}\right]}
\newcommand{\bediag}[1]{\left[ \begin{smallmatrix} 1 & 0 \\ #1 & 1 \end{smallmatrix}\right]}
\newcommand{\circd}[1]{\raisebox{-9pt}{\textcircled{\raisebox{-.9pt}{#1}}}}
\newcommand{\trspace}[1]{\mathcal{T}_{#1}}
\newcommand{\upparrow}{\big \uparrow \nTksp \phantom{\uparrow}}
\newcommand{\upparrowa}{\big \uparrow \ntksp \phantom{\uparrow}}
\newcommand{\olj}{\ol{\phantom j} \nTksp\ntnsp J}
\newcommand{\phsum}{\phantom{\sum_A^Z}}
\newcommand{\phm}{\phantom M}
%\newcommand{\phmi}{\phantom{Mi}}
\newcommand{\phn}{\phantom{ni}}
\newcommand{\phj}{\phantom j}

\newcommand{\pexc}{\mathrm{exc}_P}
\newcommand{\paexc}{\mathrm{aexc}_P}
\newcommand{\pdes}{\mathrm{des}_P}
\newcommand{\pasc}{\mathrm{asc}_P}
\newcommand{\exc}{\mathrm{exc}}
\newcommand{\aexc}{\mathrm{aexc}}
\newcommand{\des}{\mathrm{des}}
\newcommand{\iDES}{\textsc{ides}}
\newcommand{\asc}{\mathrm{asc}}
\newcommand{\cp}{\mathrm{cp}}
\newcommand{\surj}{\mathrm{surj}}
\newcommand{\ist}{\mathcal{I}}

\newcommand{\tn}{T_n(\xi)}
\newcommand{\llt}[1]{\mathrm{LLT}_{#1,q}}
\newcommand{\sllt}[1]{\mathrm{LLT}_{#1,q+1}}
%\newcommand{\zllt}[1]{z_{\mathrm{LLT}}(\inc(#1))}
%\newcommand{\szllt}[1]{z'(\inc(#1))}

%\renewcommand{\st}{^{\text{st}}}
%\renewcommand{\nd}{^{\text{nd}}}
%\renewcommand{\rd}{^{\text{rd}}}
\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\hhhpsp{\def\baselinestretch{0.15}\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

\usepackage{lipsum}

%% define your title in the usual way
\title[Barrett--Johnson inequalities]{Barrett--Johnson inequalities for totally nonnegative matrices}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Mark Skandera\thanks{\href{mailto:mark.skandera@gmail.com}{mark.skandera@gmail.com}.}\addressmark{1} \and Daniel Soskin\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics,
Lehigh University \\ \addressmark{2}Department of Mathematics, The University of Notre Dame}

%% 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{Given a matrix $A$, let $A_{I,J}$ denote the submatrix of $A$ determined by
rows $I$ and columns $J$.  
%Fischer's 
The Barrett--Johnson Inequalities 
%state that for each $n \times n$ 
%Hermitian 
%positive semidefinite matrix $A$, 
%and each subset
%$I$ of $\{1,\dotsc,n\}$ and its complement $I^c$, we have
%$\det(A) \leq \det(A_{I,I})\det(A_{I^c,I^c})$. Barrett and Johnson (Linear Multilinear Algebra 34, 1993)
%extended these to state inequalities 
relate sums of products of principal minors of 
positive semidefinite (PSD) matrices, when orders of the minors
are given by integer partitions $\lambda = (\lambda_1,\dotsc,\lambda_r)$,
$\mu = (\mu_1,\dotsc,\mu_s)$ of $n$.  
Specifically, 
%if $\lambda_1+\cdots+\lambda_i\leq \mu_1+\cdots+\mu_i$ for all $i$, then
we have
$$
\lambda_1!\cdots\lambda_r!
\nTksp\sum_{(I_1,\dotsc,I_r)}\nTksp
\det(A_{I_1,I_1}) \cdots \det(A_{I_r,I_r}) ~\geq~
  \mu_1!\cdots\mu_s!
  \nTksp\sum_{(J_1,\dotsc,J_s)}\nTksp
  \det(A_{J_1,J_1}) \cdots \det(A_{J_s,J_s}),
$$
for all PSD $n \times n$ matrices $A$,
where sums are over ordered set partitions
%sequences of disjoint subsets
of $\{1,\dotsc,n\}$ satisfying $|I_k| = \lambda_k$,
$|J_k| = \mu_k$,
if and only if $\lambda$ is majorized by $\mu$.
We show that these inequalities hold for totally nonnegative matrices
as well.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% 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; i.e., [xx, yy] in the text

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

\begin{document}

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

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

A matrix $A \in \mat{n}(\mathbb C)$ %with complex entries 
is called \emph{Hermitian}
%or \emph{symmetric} if entries are real) 
if it satisfies $A^*=A$ where $*$ denotes conjugate transpose. 
%Thus $A \in \mat n(\mathbb R)$ is Hermitian if and only if it is symmetric. 
Such a matrix is called \emph{Hermitian positive semi-definite} (HPSD) if we have $x^* A x \geq 0$ for all $x \in \mathbb C^n.$ 
 For $A \in \mat n(\mathbb R)$, the Hermitian property reduces to symmetry $A^\tr = A$, and the positive semidefinite (PSD) property reduces to $x^\tr A x \geq 0$ for all $x \in \mathbb R^n$. A matrix $A \in \mat n(\mathbb R)$ is called \emph{totally nonnegative} (TNN) if each minor (determinant of a square submatrix) is
nonnegative. One can deduce that the entries of all $n \times n$ HPSD and/or TNN matrices satisfy certain polynomial inequalities. 
In some cases, inequalities for the two classes of matrices are precisely the same.
(See \cite[\S 1]{SkanSoskinBJArx}.)

Given an $n \times n$ matrix $A = (a_{i,j})$
and subsets $I,J \subseteq [n] \defeq \{1,\dotsc,n\}$,
define the submatrix $A_{I,J} = (a_{i,j})_{i \in I, j \in J}$, and define the set $I^c \defeq [n] \ssm I$.
Hadamard~\cite{hadamard1893} showed that for $A$ HPSD we have
\begin{equation}\label{eq:hadamard}
    \det(A)\leq a_{1,1} \cdots a_{n,n},
    \end{equation}
and     Koteljanskii~\cite{KotelProp}
%, \cite{KotelPropRuss} 
showed that this holds for $A$ TNN as well.
%    Marcus~\cite{marcus1963perm} proved a permanental analog
%    \begin{equation}\label{eq:marcus}
%    \perm(A)\geq a_{1,1} \cdots a_{n,n}
%    \end{equation}
%    for $A$ HPSD, and this analog clearly holds for $A$ TNN as well.
    Fischer~\cite{fischer1908} strengthened (\ref{eq:hadamard}) by showing that for all $I \subseteq [n]$ we have
    \begin{equation}\label{eq:fischer}
    \det(A)\leq \det(A_{I,I}) \det(A_{I^c,I^c}),
    \end{equation}
     and Ky Fan showed that this holds for $A$ TNN as well (unpublished; see \cite{carlson1967}).
%    Lieb~\cite{LiebPerm} proved a permanental analog
%    \begin{equation}\label{eq:lieb}
%    \perm(A)\geq \perm(A_{I,I}) \;\perm(A_{I^c,I^c}),
%    \end{equation}
%    for $A$ HPSD, and this analog holds for $A$ TNN because every term in the expansion of the product on the right-hand side of (\ref{eq:lieb}) also appears on the left-hand side.
%    Koteljanskii~\cite{KotelProp}, \cite{KotelPropRuss} strengthened (\ref{eq:fischer}) further by proving that for all $I, J \subseteq [n]$ we have
%    \begin{equation}\label{eq:koteljanskii}
%    \det(A_{I\cup J, I\cup J})\det(A_{I\cap J, I\cap J})\leq \det(A_{I,I}) \det(A_{J,J})
%    \end{equation}
%    for $A$ belonging to a class of matrices including HPSD and TNN matrices.  
    %No permanental analog of (\ref{eq:koteljanskii}) is known.
%\begin{enumerate}
    Barrett and Johnson~\cite{BJMajor} showed that for $A$ PSD, averages
    of the products of pairs of minors appearing in (\ref{eq:fischer}) increase as the cardinality difference between $I$ and $I^c$ decreases.  Furthermore, they proved a similar result for averages of products of many minors:
    %of all PSD matrices: 
    %In particular, 
    given
    integer partitions $\lambda = (\lambda_1,\dotsc,\lambda_r)$, $\mu = (\mu_1,\dotsc,\mu_s)$ of $n$, we have
\begin{equation}\label{eq:bj}
%j!(n-j)! 
%\lambda_1!\cdots\lambda_r!
%\nTksp
\sum_{(I_1,\dotsc,I_r)}\nTksp
\frac{\det(A_{I_1,I_1}) \cdots \det(A_{I_r,I_r})}{\binom{n}{\lambda_1,\dotsc,\lambda_r}} ~\geq~
    %(j+1)!(n-j-1)! 
%  \mu_1!\cdots\mu_s!
  \nTksp\sum_{(J_1,\dotsc,J_s)}\nTksp
  \frac{\det(A_{J_1,J_1}) \cdots \det(A_{J_s,J_s})}{\binom{n}{\mu_1,\dotsc,\mu_s}},
\end{equation}
if and only if $\lambda$ is majorized by $\mu$, where 
%$(\lambda_1,\dotsc,\lambda_r)$, $(\mu_1,\dotsc,\mu_s)$ are nonnegative sequences summing to $n$ and 
the sums are over {\em ordered set partitions} of $[n]$ of types $\lambda$ and $\mu$, i.e.,
sequences of subsets of $[n]$ satisfying 
having cardinalities %given by $\lambda$, $\mu$, i.e,
\begin{equation}\label{eq:orderedsetpartition}
    I_1 \uplus \cdots \uplus I_r = J_1 \uplus \cdots \uplus J_s = [n], \qquad 
|I_k| = \lambda_k, \quad |J_k| = \mu_k.
%    \end{equation*}
\end{equation}
%which hold for real positive semidefinite matrices, 
We will show that these inequalities also hold for TNN matrices.
%Specifically,
%($\star$ Mention right after TNN inequalities?)
%Call a polynomial $p(x)$ {\em totally nonnegative} if $p(A) \geq 0$
%whenever $A$ is a totally nonnegative matrix.
%For example, Lusztig has proved that the canonical bases of quantum groups consist of TNN polynomials \cite{LusztigTP}. 
%There is no standard name 
%for polynomials which
%evaluate nonnegatively on HPSD matrices.

%In Section~\ref{s:sn}, we review basic facts about the symmetric group, its traces (class functions), and symmetric functions. 
%In Section~\ref{s:imm} we apply these ideas to form certain polynomials called {\em immanants} in the entries of $n \times n$ matrices, and we discuss the evaluation of these at TNN matrices. 
%In Section~\ref{s:tl2c}, we discuss the Temperley--Lieb algebra, related immanants,
%and their relationship to products of matrix minors.
%In Section~\ref{s:mn}, we present our main result
%that the Barrett--Johnson inequalities hold for
%all $n \times n$ TNN matrices. 
%In Section~\ref{s:op} we summarize the open problems of proving the validity of inequalities which are conspicuously absent from the lists in Section~\ref{s:intro}.



\section{The symmetric group, its traces, and symmetric functions}\label{s:sn}

The {\em symmetric group algebra} $\csn$ is
generated over $\mathbb C$ by $s_1,\dotsc, s_{n-1}$, subject to relations
\begin{equation*}
\begin{alignedat}{2}
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*}
%($\star$ Define 1-line notation \textcolor{red}{what is it?}
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 = s_{[j,j+1]}$ acts on an $n$-letter word by
swapping the letters in positions $j$ and $j+1$, i.e.,
$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$. 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)$.  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$.
%\cite{Hum} 
%for definitions.) 
It is also known that conjugacy classes in $\sn$ are precisely the set of permutations that have the same cycle type. We name cycle type by integer
partitions of $n$, the
weakly decreasing positive integer sequences
$\lambda = (\lambda_1, \dotsc, \lambda_\ell)$ satisfying
$\lambda_1 + \cdots + \lambda_\ell = n$.
The $\ell = \ell(\lambda)$ components of $\lambda$ are called its {\em parts},
%(components) of $\lambda$.
and we let $|\lambda| = n$ and $\lambda \vdash n$ denote that
$\lambda$ is a partition of $n$.  
Given $\lambda \vdash n$,
we define the {\em transpose} partition
$\lambda^\tr = (\lambda^\tr_1, \dotsc, \lambda^\tr_{\lambda_1})$
by
\begin{equation*}
  \lambda^\tr_i = \# \{ j \,|\, \lambda_j \geq i \}.
\end{equation*}
Sometimes it is convenient to name a partition with exponential notation,
omitting parentheses and commas, so that
$4^21^6 \defeq (4, 4, 1, 1, 1, 1, 1, 1)$. Sometimes it is convenient to partially order partitions of $n$ by the \emph{majorization} (or \emph{dominance}) \emph{order}, \begin{equation}
    \lambda\preceq\mu \quad \text{iff} \quad \lambda_{1}+\cdots+\lambda_{i}\leq \mu_{1}+\cdots+\mu_{i} 
\end{equation} 
for all $i$. It is known that if $\lambda$ is covered by $\mu$ in this partial order then $\lambda$, $\mu$ have equal parts except in two positions $i < j$ where we have
\begin{equation}\label{eq:movebox}
    \mu_i=\lambda_i+1, \qquad \mu_j=\lambda_j-1.
\end{equation}

%The {\em symmetric group algebra} $\csn$
%and the 
%{\em (Iwahori-) Hecke algebra} $\hnq$
%have similar presentations as algebras over $\mathbb C$ and $\cqq$
%respectively, with 
%multiplicative identity elements $e$ and $T_e$,
%generators 
%$s_1,\dotsc, s_{n-1}$ and 
%$T_{s_1},\dotsc, T_{s_{n-1}}$, 
%and relations
%\begin{equation*}
%\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*}
%Analogous to the natural basis $\{ w \,|\, w \in \sn \}$ of $\csn$
%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 expression for $w$ in $\sn$.  We call $\ell$ the {\em length}
%of $w$ and write $\ell = \ell(w)$.  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 specialization of $\hnq$ at $\qp12 = 1$ is isomorphic to $\csn$.
%($\star$ Cut out the Hecke algebra?)

%Given a word $a = a_1 \cdots a_k$ in $\mfs k$,
%and a word $b = b_1 \cdostrictlyts b_k$ having $k$ distinct letters,
%we say that {\em $b$ matches the pattern $a$} if the letters of $b$ appear
%in the same relative order as those of $a$; that is, if we have
%$a_i < a_j$ if and only if $b_i < b_j$ for all $i,j \in [k]$.
%$Given $w \in \sn$
%$w = w_1\dotsc w_m$ having distinct letters,
%e.g., $w \in \mfs n$ or $w \in \bn$,
%we say that {\em $w$ avoids the pattern $a$} if no subword
%$w_{i_1} \cdots w_{i_k}$
%of the one-line notation
%of $w$ matches the pattern $a$.

%($\star$ Define the trace space $\trspace n$ and several bases of it.
%At least define $\{ \phi^\lambda \,|\, \lambda \vdash n\}$,
%$\{ \chi^\lambda \,|\, \lambda \vdash n\}$,
%$\{ \epsilon^\lambda \,|\, \lambda \vdash n\}$.)
%
%($\star$ Define the space $\Lambda_n$ of homogeneous degree-$n$ symmetric
%functions.  Define several bases, at least
%$\{ m_\lambda \,|\, \lambda \vdash n \}$,
%$\{ s_\lambda \,|\, \lambda \vdash n \}$,
%$\{ e_\lambda \,|\, \lambda \vdash n \}$.)

%\section{Symmetric functions and traces}

Let $\Lambda$ be the ring of symmetric functions in 
$x = (x_1, x_2, \dotsc)$ having integer coefficients, and
let $\Lambda_n$ be the $\mathbb Z$-submodule of homogeneous functions
of degree $n$.
This submodule has rank equal to the number of partitions of $n$.
%We define a {\em composition} of $n$ to be any rearrangement
%of a partition of $n$ and write $\alpha \vDash n$ to denote that $\alpha$
%is a composition of $n$.
Five standard bases of $\Lambda_n$ consist of the monomial $\{m_\lambda \,|\, \lambda \vdash n\}$,
elementary $\{e_\lambda \,|\, \lambda \vdash n\}$,
(complete) homogeneous $\{h_\lambda \,|\, \lambda \vdash n\}$,
power sum $\{p_\lambda \,|\, \lambda \vdash n\}$,
and Schur $\{s_\lambda \,|\, \lambda \vdash n\}$ 
%and forgotten $\{f_\lambda \,|\, \lambda \vdash n\}$ 
symmetric functions.
(See, e.g., \cite[Ch.\,7]{StanEC2} for definitions.)
The change-of-basis matrix relating
$\{ e_\lambda \,|\, \lambda \vdash n \}$ and
$\{ m_\lambda \,|\, \lambda \vdash n \}$ is given by the equations
\begin{equation}\label{eq:etom}
  e_\lambda = \sum_{\mu \preceq \lambda^\tr} M_{\lambda,\mu} m_\mu,
\end{equation}
where $M_{\lambda,\mu}$ equals the number of column-strict Young tableaux
of shape $\lambda^\tr$ and content $\mu$. That is, $M_{\lambda,\mu}$ is the number of histograms having $\lambda_{i}$ boxes in column $i$ for all $i$, filled with $\mu_1$ ones, $\mu_2$ twos, etc., with column entries strictly increasing from bottom to top.
%For example we have 
%\begin{equation*}
%e_{221}=m_{32}+2m_{311}+5m_{221}+12m_{2111}+30m_{11111},    
%\end{equation*}
%and the coefficients $M_{221,32}=1$ of $m_{32}$,
%$M_{221,311}=2$ of $m_{311}$,
%$M_{221,221}=5$ of $m_{221}$
%count the column-strict tableaux
%\begin{equation*}
%\tableau[scY]{2,2|1,1,1}\,,\qquad\qquad\qquad
%\tableau[scY]{2,3|1,1,1}\,,\quad
%\tableau[scY]{3,2|1,1,1}\,,
%\end{equation*}
%\begin{equation*}
%\tableau[scY]{2,2|1,1,3}\,,\quad
%\tableau[scY]{2,3|1,1,2}\,,\quad
%\tableau[scY]{3,2|1,1,2}\,,\quad
%\tableau[scY]{2,3|1,2,1}\,,\quad
%\tableau[scY]{3,2|2,1,1}\,.
%\end{equation*}
%Similar tableaux which are weakly increasing in rows combinatorially
%interpret the change-of-basis matrix relating
%$\{ h_\lambda \,|\, \lambda \vdash n\}$ and
%$\{ m_\lambda \,|\, \lambda \vdash n\}$.

%($\star$ Decide between $\mathbb Z$ and $\mathbb C$. \textcolor{red}{not sure what scalars are better})
Let $\trspace{n}$ be the $\mathbb Z$-module of
%$\mathbb Z$-module of
$\zsn$-{\em traces} (equivalently, $\sn$-class functions), 
%of $\hnq$,
%the symmetric group algebra $\zsn$,
%the
linear functionals
$\theta: \zsn \rightarrow \mathbb Z$ satisfying
$\theta(gh) = \theta(hg)$ for all $g, h \in \zsn$.
%For any trace $\theta: T_w \mapsto a(q)$ in $\trspace{n,q}$,
%the $\qp12 =1$ specialization $\theta: w \mapsto a(1)$
%\zsn \rightarrow \mathbb Z,
%belongs to the space $\trspace n \defeq \trspace{n,1}$ of $\zsn$-traces
%from $\zsn \rightarrow \mathbb Z$.
%$\theta: \zsn \rightarrow \mathbb Z$ satisfying
%$\theta(gh) = \theta(hg)$ for all $g, h \in \zsn$.
Like the $\mathbb Z$-module $\Lambda_n$,
%of homogeneous degree-$n$ symmetric functions,
the trace space 
%$\trspace{n,q}$ and 
$\trspace n$ has dimension equal to the number of integer partitions of $n$.  
The Frobenius $\mathbb Z$-module isomorphism (\ref{eq:Frob})
%and its $q$-extension,
%$\mathrm{Frob}_q: \trspace {n,q} \rightarrow \Lambda_n$,
%$\theta_q \mapsto \mathrm{Frob}(\theta)$,
\begin{equation}\label{eq:Frob}
  \begin{aligned}
    \mathrm{Frob}: \trspace n &\rightarrow \Lambda_n \\
%    &\qquad
%    \mathrm{Frob}_q: \trspace {n,q} &\rightarrow \Lambda_n\\
    \theta &\mapsto \frac 1{n!} \sum_{w \in \sn} \theta(w) p_{\ctype(w)}
 %   &\qquad
 %   \theta_q &\mapsto \mathrm{Frob}(\theta),
  \end{aligned}
\end{equation}
    %\frac 1{n!} \sum_{w \in \sn} \theta(w) p_{\ctype(w)},
%  \end{aligned}
%\end{equation}
defines bijections
between standard
%symmetric function
bases of $\Lambda$, 
%three character bases of
and $\trspace n$.
Schur functions correspond to irreducible characters,
%\begin{equation*}
  % \leftrightarrow \chi_q^\lambda,
%\end{equation*}
while elementary 
and homogeneous 
symmetric functions
%, and Schur functions
correspond to induced sign 
and trivial
characters,
%, and irreducible characters,
\begin{equation*}%\label{eq:threecharbases}
%  \begin{gathered}
  s_\lambda \leftrightarrow \chi^\lambda, \qquad
  e_\lambda \leftrightarrow \epsilon^\lambda = \sgn \upparrow^{\sn}_{\mfs \lambda},
  %\leftrightarrow \epsilon_q^\lambda = \sgn_q \upparrow^{\hnq}_{H_\lambda(q)},\\
 \qquad
  h_\lambda \leftrightarrow \eta^\lambda = \triv \upparrow^{\sn}_{\mfs \lambda},
 % \leftrightarrow \eta_q^\lambda = \triv_q \upparrow^{\hnq}_{H_\lambda(q)},
%  \qquad
  %  s_\lambda \leftrightarrow \chi^\lambda,
 % \end{gathered}
\end{equation*}
where $\mfs \lambda$ is the Young subgroup of $\sn$ indexed by $\lambda$.
The power sum and monomial bases of $\Lambda_n$ correspond to
%a natural basis
bases of $\trspace n$
which are not characters.
We call these the
{\em power sum}
$\{\psi^\lambda \,|\, \lambda \vdash n \}$
%$\{\psi^\lambda \,|\, \lambda \vdash n \}$ of $\trspace n$
%\begin{equation}\label{eq:psidef}
%  \psi^\lambda(w) \defeq \begin{cases}
%    z_\lambda &\text{if $\ctype(w) = \lambda$},\\
%    0 &\text{otherwise},
%  \end{cases}
%\end{equation}
%where $z_\lambda = \lambda_1 \cdots \lambda_\ell \alpha_1! \cdots \alpha_n!$
%and $\alpha_i$ is the number of parts of $\lambda$ equal to $i$.
%Two less natural bases of the trace space,
%the
and {\em monomial}
$\{ \phi^\lambda \,|\, \lambda \vdash n \}$
traces, respectively.
%Less natural than the character bases,
These are
%defined to be those
the bases related to the irreducible character bases
by the same matrices of character evaluations and
%of
inverse Kostka numbers that relate
power sum and monomial symmetric functions to Schur functions,
%basis of $\Lambda_n$,
\begin{equation}\label{eq:mforgotten}
%  \begin{alignedat}{2}
%    s_\lambda &= \sum_\mu K_{\lambda,\mu} m_\mu, &\qquad
%    s_\lambda &= \sum_\mu K_{\lambda^\tr,\mu} f_\mu,\\
%    \chi^\lambda &= \sum_\mu K_{\lambda,\mu} \phi^\mu, &\qquad
%    \chi^\lambda &= \sum_\mu K_{\lambda^\tr,\mu} \gamma^\mu.
%  \end{alignedat}
  \begin{alignedat}{2}
    p_\lambda &= \sum_\mu \chi^\mu(\lambda) s_\mu, &\qquad
    \psi^\lambda &= \sum_\mu \chi^\mu(\lambda) \chi^\mu, 
    %&\qquad
    %\psi_q^\lambda &= \sum_\mu \chi^\mu(\lambda) \chi_q^\mu,
    \\
    m_\lambda &= \sum_\mu K_{\lambda,\mu}^{-1} s_\mu, &\qquad
    \phi^\lambda &= \sum_\mu K_{\lambda,\mu}^{-1} \chi^\mu, 
    %&\qquad
    %\phi_q^\lambda &= \sum_\mu K_{\lambda,\mu}^{-1} \chi_q^\mu,\\
    %f_\lambda &= \sum_\mu K_{\lambda,\mu^\tr\;}^{-1} s_\mu, &\qquad
    %\gamma^\lambda &= \sum_\mu K_{\lambda,\mu^\tr}^{-1} \chi^\mu, &\qquad
    %\gamma_q^\lambda &= \sum_\mu K_{\lambda,\mu^\tr}^{-1} \chi_q^\mu,
  \end{alignedat}
\end{equation}
where $\chi^\mu(\lambda) \defeq \chi^\mu(w)$
for any $w \in \sn$ having $\ctype(w) = \lambda$.
%$ is the evaluation of the $\sn$-character $\chi^\mu$
%at any element $w \in \sn$ having cycle type $\lambda$.
%Just as the power sum symmetric functions form a
%$\mathbb Q$-basis of $\Lambda_n$, the power sum traces form
%$\mathbb Q$-bases of $\trspace n$ and $\trspace {n,q}$.
%The power sum traces of $\trspace n$
%which form a $\mathbb Q$-basis of $\trspace n$,
%also have the natural definition
%\begin{equation}\label{eq:psidef}
%  \psi^\lambda(w) \defeq \begin{cases}
%    z_\lambda &\text{if $\ctype(w) = %\lambda$},\\
%    0 &\text{otherwise},
%  \end{cases}
%\end{equation}
%where $z_\lambda = \lambda_1 \cdots \lambda_\ell \alpha_1! \cdots \alpha_n!$
%and $\alpha_i$ is the number of parts of $\lambda$ equal to $i$.

%\section{Totally nonnegative polynomials}

%Let $x = (x_{i,j})_{i,j \in [n]}$ be a matrix of $n^2$ indeterminates.
%Define $\cx = \mathbb C[x_{1,1}, x_{1,2}, \dotsc, x_{n,n}]$.
%For $p(x) \in \cx$ and $A = (a_{i,j})$ an $n \times n$ matrix, define
%$p(A) = p(a_{1,1}, a_{1,2} , \dotsc, a_{n,n})$.
%Call a polynomial $p(x)$ {\em totally nonnegative} if $p(A) \geq 0$
%whenever $A$ is a totally nonnegative matrix.

\section{Immanants and totally nonnegative polynomials}\label{s:imm}

Each of the inequalities stated in Section~\ref{s:intro} may
be stated in terms of a polynomial in matrix entries. 
In particular, let $x = (x_{i,j})_{i,j \in [n]}$ be a matrix of $n^2$ indeterminates, and for 
%For subsets $I,J \subseteq [n]$, define the submatrix $x_{I,J}=(x_{i,j})_{i \in I, j \in J}$ and the subset $I^c = [n] \ssm I$.  
%For 
$p(x) \in \cx \defeq \mathbb C[x_{i,j}]_{i,j \in [n]}$ and $A = (a_{i,j})$ an $n \times n$ matrix, define $p(A) = p(a_{1,1}, a_{1,2} , \dotsc, a_{n,n})$.
%($\star$ Introduce polynomials in $x_{i,j}$ here?) 
While few of the polynomial inequalities in Section~\ref{s:intro} specifically mention the symmetric group, all of them involve polynomials which are linear combinations of monomials of the form $\{ \permmon xw \,|\, w \in \sn \}$.  Following \cite{LittlewoodTGC}, \cite{StanPos}, we call such polynomials {\em immanants}.  Specifically, given $f: \sn \rightarrow \mathbb C$ define the \emph{$f$-immanant} to be the polynomial
\begin{equation}\label{eq:immdef}
  \imm f(x) \defeq \sum_{w \in \sn} f(w) \permmon xw \in \mathbb C[x].
\end{equation}
The sign character 
%($\sgn: w \mapsto (-1)^{\ell(w)}$)
($w \mapsto (-1)^{\ell(w)}$)
immanant and trivial character 
%($\triv: w \mapsto 1$)
($w \mapsto 1$)
immanant are the determinant and permanent,
\begin{equation*}
\det(x) = \sum_{w \in \sn} (-1)^{\ell(w)} \permmon xw,
\qquad
\perm(x) = \sum_{w \in \sn} \permmon xw.
\end{equation*}
Simple formulas for the induced sign 
and trivial 
character immanants 
%$\epsilon^\lambda$-immanants 
%and $\eta^\lambda$-immanants 
%employ
%determinants and permanents of square submatrices $x_{I,J}$ of $x$,
%\begin{equation*}
%x_{I,J} \defeq (x_{i,j})_{i \in I, j \in J},
%\qquad 
%I,J \subset [n] \defeq \{1,\dotsc, n\},
%\qquad 
%|I| = |J|.
%\qquad |I| = |J|.
%\end{gathered}
%\end{equation*}
%of $x$.  %(See \cite{MerWatIneq}.)
%(where these results are attributed to Littlewood?)
% or other paper by those authors.)
are due to Little\-wood--Merris--Watkins~\cite{LittlewoodTGC},
\cite{MerWatIneq}: for $\lambda = (\lambda_1,\dotsc,\lambda_r) \vdash n$, we have
%showed that for
%and 
%In particular, Littlewood~\cite{LittlewoodTGC} and 
%Merris and Watkins~\cite{MerWatIneq} showed that for
%$\lambda = (\lambda_1, \dotsc, \lambda_r) \vdash n$, we have
\begin{equation}\label{eq:lmw}
  \begin{gathered}
    \imm{\epsilon^\lambda}(x) = 
\nTtksp
\sum_{(I_1, \dotsc, I_r)} 
\nTksp
\det(x_{I_1, I_1}) \cdots \det(x_{I_r, I_r}), 
\\
\imm{\eta^\lambda}(x) = 
\nTtksp
\sum_{(I_1, \dotsc, I_r)} 
\nTksp
\perm(x_{I_1, I_1}) \cdots \perm(x_{I_r, I_r}),
\end{gathered}
\end{equation}
where 
%$\lambda = (\lambda_1, \dotsc, \lambda_r) \vdash n$ and
the sums are over all ordered set partitions of $[n]$ of type $\lambda$ (\ref{eq:orderedsetpartition}).
%sequences of pairwise disjoint subsets of $[n]$ satisfying $|I_j| = \lambda_j$.
%\end{thm}
%Call such a sequence an {\em ordered set partition} of $[n]$ 
%{\em of type $\lambda$.} 

Some current interest in immanants and their connection to TNN matrices was inspired by Lusztig's work with canonical bases of quantum groups. (See, e.g., \cite{LusztigTPCB}.) In particular, one quantum group has an interesting basis whose elements can be described in terms of immanants which evaluate nonnegatively on TNN matrices. 
Call a polynomial $p(x)$ {\em totally nonnegative} (TNN) if $p(A) \geq 0$
whenever $A$ is a totally nonnegative matrix.  There is no known procedure to decide if a given polynomial is TNN.
%For example, Lusztig has proved that the canonical bases of quantum groups consist of TNN polynomials \cite{LusztigTP}. 
%There is no standard name 
%for polynomials which
%evaluate nonnegatively on HPSD matrices.

The formula (\ref{eq:lmw}) makes it obvious that $\imm{\epsilon^\lambda}(x)$
%and $\imm{\eta^\lambda}(x)$ 
is a TNN polynomial for each partition
$\lambda \vdash n$.
A stronger result~\cite[Cor.\,3.3]{StemImm} asserts that irreducible character
immanants $\imm{\chi^\lambda}(x)$ are TNN as well.
It is clear that the $\sn$-trace immanants
\begin{equation*}
  \{ \imm{\theta}(x) \,|\,
  \theta \in \trspace n, \imm{\theta}(x) \text{ is TNN } \}
\end{equation*}
form a cone, i.e., are closed under real nonnegative linear combinations.
Stembridge has conjectured~\cite[Conj.\,2.1]{StemConj}
that the extreme rays of this cone are generated by the
monomial trace immanants
\begin{equation}\label{eq:monimm}
  \{ \imm{\phi^\lambda}(x) \,|\, \lambda \vdash n \},
\end{equation}
and has shown~\cite[Prop.\,2.3]{StemConj} that the cone of TNN $\sn$-trace immanants
lies inside of the cone generated by (\ref{eq:monimm}).
%  It would be interesting to decribe the extreme rays of this cone.
%Stembridge has conjectured the following~\cite[Conj.\,2.1, Prop.\,2.3]{StemConj}.
%Monomial trace immanants are conjectured to be the most basic TNN immanants. One part of this conjecture is known~\cite[Prop.~2.3]{StemConj}.
\begin{prop}
  Each immanant of the form $\imm{\theta}(x)$ with $\theta \in \trspace n$
  is a totally nonnegative polynomial only if it is equal to
  a nonnegative linear combination of monomial trace immanants.
\end{prop}
%(The ``if'' part of this proposition is open, and was conjectured by
%Stembridge.~\cite[Conj.~2.1]{StemConj})
Thus it is conjectured that an $\sn$-trace immanant is TNN if and only if it is equal to a nonnegative linear combination of monomial trace immanants. Indeed it is known that some monomial trace immanants generate
%known to be 
extremal
rays of the cone of TNN $\sn$-trace immanants~\cite[Thm.\.10.3]{CHSSkanEKL}.
(See \cref{t:monimmtnn}.)




\section{The Temperley-Lieb algebra and 2-colorings}\label{s:tl2c}

%($\star$ State the presentation of $TL_n(\xi)$ in terms of generators
%$t_1, \dotsc, t_{n-1}$ and show the Kaufman diagrams as well.)

Given a complex number $\xi$, we define the 
{\em Temperley-Lieb algebra} $T_n(\xi)$
to be the $\mathbb{C}$-algebra generated by elements
$t_1,\dotsc,t_{n-1}$ subject to the relations
\begin{alignat*}{2}
t_i^2 &= \xi t_i, &\qquad &\text{for } i=1,\dotsc,n-1, \\
t_i t_j t_i &= t_i,   &\qquad &\text{if }  |i-j|=1,\\
t_i t_j &= t_j t_i,   &\qquad &\text{if }  |i-j| \geq 2.
\end{alignat*}
When $\xi = 2$ we have the isomorphism $T_n(2) \cong \csn/(1 + s_1 + s_2 + s_1s_2 + s_2s_1 + s_1s_2s_1)$.
(See e.g.~\cite{FanMon}, \cite[Sec.\,2.1, Sec.\,2.11]{GHJ},
\cite[Sec.\,7]{WestburyTL}.) 
%Equivalently, 
%we may say that
%the ideal $(z_{[1,3]})$ is the kernel of the homomorphism 
%algebra homomorphism from $\zsn$ to 
%embedding of the symmetric group $S_n$ into
%$\tn$ given by the map
Specifically, the isomorphism is given by
\begin{equation}\label{eq:sntotn}
\begin{aligned}
\sigma : \csn &\rightarrow T_n(2),\\
s_i &\mapsto t_i - 1. 
%\quad \text{ for all } i.
\end{aligned}
\end{equation}
%For example, ($\star$ where did the example go?)
%$T_n(\xi)$ is isomorphic to the quotient
%$H(\xi-1)/(z_{[1,3]})$ of the Hecke algebra $H(\xi-1)$ and thus
%$\tn$ is isomorphic to the quotient 
%$\zsn/(z_{1,3})$.
%(where
%$I$ is 
%the ideal generated by
%$z_{1,3}$ necessarily contains
%$z_{2,4},\dotsc, z_{n-2,n}$ and 
%all similar expressions obtained
%by summing over subgroups of $S_n$ which are isomorphic to 
%$S_3,\dotsc,S_n$.  Do I need to mention this?)

Let $\K_n$ be the multiplicative monoid generated
by $t_1,\dotsc,t_{n-1}$ when $\xi = 1$, also called the standard basis of $\tn$.
It is known that $|\K_n|$ is
%the dimension of $\tn$ (and of $T_n(\xi)$) as a complex vector space
%$\mathbb{Z}$-module 
%is well known to be
the $n$th Catalan number $C_n = \tfrac{1}{n+1}\tbinom{2n}{n}$.
%A natural bijection between basis elements of $\tn$ and
%$321$-avoiding permutations in $S_n$ is given by the correspondence
%of generators $s_i \leftrightarrow t_i$.
%For $\tau = t_{i_1} \cdots t_{i_\ell}$ a basis element of $\tn$,
%define $v(\tau) \in \sn$ by
%\begin{equation}\label{eq:vtau}
%  v(\tau) = s_{i_1} \cdots s_{i_\ell}.
%\end{equation}
Diagrams of the
%Pictorial representations of the 
basis elements of $T_n(\xi)$, made popular by 
Kauffman~\cite[Sec.\,4]{KauffState} are (undirected) graphs with $2n$ vertices and $n$ edges. 
The identity and generators $1, t_1, \dotsc, t_{n-1}$ are represented by
\begin{equation*}
  \raisebox{-6.25mm}{
    {\includegraphics[height=16mm]{tln_idnew.eps}}, ~
    {\includegraphics[height=16mm]{tln_t1new}}, ~
    {\includegraphics[height=16mm]{tln_t2new}}, $\dotsc$, ~
    {\includegraphics[height=16mm]{tln_tn-1new}},}
\end{equation*}
%\begin{figure}[h]
%\centerline{
%%\subfigure[Planar networks for the generators of $S_n$.]
%\psfig{figure=kauff.eps,width=.5\textwidth}}
%\caption{}
%\label{f:kauff}
%\end{figure}
%Figure~\ref{f:kauff}(a) shows the generators of $T_4(2)$
%(and the basis elements?)
and multiplication of these elements corresponds to concatenation
of diagrams, with cycles contributing a factor of $\xi$.
For instance, 
the fourteen basis elements of $T_4(\xi)$ are
\begin{equation*}
\raisebox{-3.1mm}{
  \includegraphics[height=10mm]{tl4_id}, ~
  \includegraphics[height=10mm]{tl4_t1}, ~
  \includegraphics[height=10mm]{tl4_t2}, ~
  \includegraphics[height=10mm]{tl4_t3}, ~
  \includegraphics[height=10mm]{tl4_t1t3}, ~
  \includegraphics[height=10mm]{tl4_t1t2}, ~
  \includegraphics[height=10mm]{tl4_t2t1}, ~
  \includegraphics[height=10mm]{tl4_t2t3}, ~
  \includegraphics[height=10mm]{tl4_t3t2}, ~
  \includegraphics[height=10mm]{tl4_t1t2t3}, ~
  \includegraphics[height=10mm]{tl4_t3t2t1}, ~
  \includegraphics[height=10mm]{tl4_t1t3t2}, ~
  \includegraphics[height=10mm]{tl4_t2t1t3}, ~
  \includegraphics[height=10mm]{tl4_t2t1t3t2},}\\
\end{equation*}
%\begin{figure}[h]
%\centerline{
%\psfig{figure=kauffbasis.eps,width=.80\textwidth}}
%\caption{}
%\label{f:kauffbasis}
%\end{figure}
and the equality 
$t_3t_2t_3t_3t_1 = \xi t_1t_3$ in $T_4(\xi)$
is represented by
\begin{equation}\label{eq:kauffex}
  \raisebox{-3.1mm}{
\includegraphics[height=10mm]{tl4_t1t2t1t1t3}}
 = 
\xi
\raisebox{-3.1mm}{
  \includegraphics[height=10mm]{tl4_t1t3},}
\end{equation}
with the "bubble" becoming the scalar multiple $\xi$.
%\begin{figure}[h]
%\centerline{
%\psfig{figure=kauffex.eps,width=.45\textwidth}}
%\caption{}
%\label{f:kauffex}
%\end{figure}
We will identify each element $\tau \in\K_n$ with its Kauffman diagram, and will 
%treat it as an undirected graph. We will 
label vertices $v_1, \dotsc, v_{2n}$, clockwise from the lower left.  We define the height of a vertex by
\begin{equation*}
    \hgt(v_i) = \begin{cases}
      i &\text{if $1 \leq i \leq n$},\\
      2n+1-i &\text{if $n+1 \leq i \leq 2n$}.
      \end{cases}
\end{equation*}
For instance, (\ref{eq:tauhat}) shows the element $t_7t_6t_8t_5t_7t_4t_6t_5t_2 \in \K_9$ 
%$T_9(\xi)$ 
on the left, with vertex labels.
Vertices have heights $1,\dotsc,9$, from bottom to top.
It is easy to see that for all $\tau \in\K_n$, each edge $(v_i,v_j)$ satisfies
\begin{equation}\label{eq:heightdiff}
\hgt(v_i) - \hgt(v_j) = \begin{cases}
 1 ~(\mathrm{mod}~ 2) &\text{if $i,j \leq n$ or $i,j \geq n+1$},\\
 0 ~(\mathrm{mod}~ 2) &\text{otherwise}.
\end{cases}
\end{equation}

Define $\hat \tau$ to be the graph obtained from $\tau$ by adding edges $(i, 2n+1-i)$ for all $i$ (even if such an edge already exists).  Since each vertex in $\hat \tau$ has degree $2$, it is clear that this graph is a disjoint union of cycles.  For example, corresponding to the element $\tau$ on the left of (\ref{eq:tauhat}) we have $\hat \tau$ to its right, the decomposition of this graph into four disjoint cycles, and a proper $2$-coloring of this graph.
\begin{equation}\label{eq:tauhat}
  \begin{gathered}
 \raisebox{-3.1mm}{
{\includegraphics[height=40mm]{tau.eps}}} \\
\phantom \sum \tau \phantom \sum
\end{gathered}
\qquad\quad
\begin{gathered}
\raisebox{-3.1mm}{
\includegraphics[height=40mm]{tauhat.eps}}\\
\phantom\sum \hat \tau \phantom \sum\end{gathered}
\qquad\quad
\begin{gathered}
\raisebox{-3.1mm}{
\includegraphics[height=40mm]{tauhatcycles.eps}}\\ 
\phantom\sum
\text{cycles of } \hat\tau\phantom\sum
\end{gathered}
\quad\quad
\begin{gathered}
    \raisebox{-3.1mm}{
\includegraphics[height=40mm]{tauhatcyclecolor.eps}}\ .\\
\phantom\sum
\text{$2$-coloring of } \hat\tau\phantom\sum
\end{gathered}
\end{equation}

The Temperley-Lieb algebra $T_n(2)$ sometimes arises in the $2$-coloring
of combinatorial objects.
Define a {\em principal coloring} of $\tau \in \K_n$ to be a map $\kappa: \mathrm{vertices}(\tau) \rightarrow \{ \mathrm{black}, \mathrm{white} \}$ which is a {\em proper} coloring of $\hat \tau$, i.e., 
\begin{equation*}
\begin{alignedat}{2} 
\text{color}(v_i) &\neq \text{color}(v_{2n+1-i}) &\qquad  &\text{for $i=1,\dotsc,n$},\\
\text{color}(v_i) &\neq \text{color}(v_j) &\qquad &\text{if $v_i$ and $v_j$ are adjacent in $\tau$}.  
\end{alignedat}
\end{equation*}
Let $(\tau, \kappa)$ denote the graph $\tau$ with its vertices colored by $\kappa$.

Principal colorings of $\tau$ are closely related to cycles in $\hat\tau$.  It is clear that colors must alternate along any one cycle of $\hat\tau$.  It is also true that vertex colors alternate as one views the vertices in clockwise order, ignoring the edges of that cycle.
For example, consider a $2$-coloring of the cycle $(v_4, v_{11}, v_8, v_7, v_{12}, v_{15})$ of $\hat\tau$ in (\ref{eq:tauhat}),
\begin{equation*}
    \raisebox{-3.1mm}{
\includegraphics[height=20mm]{tauhatonecycle.eps}}.
\end{equation*}
\begin{prop}
If $\hat\tau$ is a single cycle, then there are two principal colorings of $\tau$. In each, vertices of odd index and of even index have opposite colors. 
\end{prop}
\begin{proof}
Omitted.
%This is clear if $n=1$. Assume that $n\geq2$ and suppose we have a principal coloring of $\tau$. It suffices to show that color($v_i$)$~\neq~$color($v_{i+1}$) for $i=1,\dotsc,n-1.$ Consider a subpath of the cycle of $\hat\tau$ from $v_i$ to $v_{i+1}$. Since $v_{i}$, $v_{i+1}$ belong to the left column, there are an even number of edges on the path that switch columns. By (\ref{eq:heightdiff}), for each such edge $(v_{j},v_{k})$ we have that $\hgt(v_j)-\hgt(v_k)$ is even. Also by (\ref{eq:heightdiff}), since $\hgt(v_{i+1})-\hgt(v_i)=1$ there are an odd number of edges that do not switch columns. Thus the path consists of an odd number of edges and color($v_i$)$~\neq~$color($v_{i+1}$).
\end{proof}

%It is easy to see that 
Clearly if $\kappa$ is a principal coloring of $\tau \in \K_n$ and if $\hat \tau$ is a single cycle, then we have
\begin{equation}\label{eq:lrdiff}
    \left| \# \left(\substack{\text{\normalsize white vertices on}\\[2pt] \text{\normalsize left of $(\tau,\kappa)$}}\right) - 
    \#  \left(\substack{\text{\normalsize white vertices on}\\[2pt] \text{\normalsize right of $(\tau,\kappa)$}}\right) \right| = 
    \begin{cases}
      0 & \text{if $n$ even},\\
      1 & \text{if $n$ odd}.
      \end{cases}
      \end{equation}
In this situation we call $(\tau,\kappa)$ {\em balanced} if $n$ is even, and
{\em unbalanced} otherwise.
More specifically, we call $(\tau,\kappa)$ {\em left-unbalanced} ({\em right-unbalanced}) if it has more white vertices on the left (right).
Now consider $\tau \in \K_n$
with $\hat \tau$ a disjoint union of cycles $C_1,\dotsc, C_d$, and $\kappa$ a principal coloring of $\tau$.
Define
\begin{equation}\label{eq:alphabeta}
\begin{aligned}
\alpha &= \alpha(\tau,\kappa) \defeq \# \{ i \,|\, (\tau_{C_i}, \kappa) \text{ right unbalanced} \},\\   \beta &= \beta(\tau,\kappa) \defeq \# \{ i \,|\, (\tau_{C_i}, \kappa) \text{ left unbalanced} \}.
\end{aligned}
\end{equation}
For example, in
%recall $\tau$ and $\hat\tau$ from 
(\ref{eq:tauhat}), the proper $2$-coloring $\kappa$ of $\hat\tau$
%\begin{equation*}
%\raisebox{-3.1mm}{
%\includegraphics[height=40mm]{tauhatcyclecolor.eps}},
%\end{equation*}
  corresponds to a principal coloring of $\tau$ with %satisfies 
  $\alpha(\tau,\kappa) = 1$, $\beta(\tau,\kappa) = 2$, and $d=4$. Also note that there is one balanced cycle.

It is easy to characterize the colorings $\kappa$ of a given Temperley-Lieb basis element $\tau$ for which the numbers $\alpha$, $\beta$ (\ref{eq:alphabeta}) are constant.
\begin{lem}
Let $(\tau, \kappa)$, $(\tau,\kappa')$ be principal colorings with $j$ white vertices on the left, for some $j$, $0 \leq j \leq \lfloor \tfrac n2 \rfloor$.
Then we have
%\begin{equation*}
    $\alpha(\tau,\kappa) = \alpha(\tau,\kappa')$
%    \qquad
 and
 $\beta(\tau,\kappa) = \beta(\tau,\kappa')$.
%\end{equation*}
\end{lem}
\begin{proof} Omitted.
%  It is easy to see that the number of cycles of $\hat \tau$ of cardinality $2~ (\mathrm{mod}~4)$ is
%  \begin{equation}\label{eq:absum}
%      \alpha(\tau,\kappa) + \beta(\tau,\kappa) = %
%      \alpha(\tau,\kappa') + \beta(\tau,\kappa').
%  \end{equation}
%  On the other hand, we have by assumption that the number of white vertices on the right of $(\tau,\kappa)$ (or of $(\tau,\kappa')$) minus the number of white vertices on the left is \begin{equation}\label{eq:njdiff}
%  (n-j)-j = n - 2j.
%  \end{equation}
%  Since each balanced subgraph $(\tau_{C_i},\kappa)$ (or $(\tau_{C_i},\kappa')$) contributes the same number of white vertices to both sides 
%  and each unbalanced subgraph contributes one more white vertex to one side than to the other (\ref{eq:lrdiff}),
%  we see that (\ref{eq:njdiff}) equals
%  \begin{equation}\label{eq:abdiff}
%  \alpha(\tau,\kappa) - \beta(\tau,\kappa) = \alpha(\tau,\kappa') - \beta(\tau,\kappa').
%  \end{equation}
%  Combining (\ref{eq:absum}) and (\ref{eq:abdiff}), we have the desired equalities.
\end{proof}
\noindent
By this lemma, we may write
\begin{equation}\label{eq:newalpha}
\alpha(\tau,j) \defeq \alpha(\tau,\kappa),
\qquad 
(\beta(\tau,j) \defeq \beta(\tau,\kappa))
\end{equation}
if there exists a principal coloring of $\tau$ in which $j$ vertices on the left are white.

Just as $T_n(2)$ is related to $2$-coloring, it is related to total
nonnegativity of polynomials in the subspace
\begin{equation}\label{eq:tlspace}
  \spn_{\mathbb R} \{ \det(x_{I,I}) \det(x_{I^c,I^c}) \,|\, I \subseteq [n] \}
  \end{equation}
of immanants. We define an immanant $\imm{\tau}(x)$ for each
$\tau \in \K_n$ in terms of the function
%.
%For each basis element
%$\tau$ of $\tn$ we define the function
\begin{equation}\label{eq:ftau}
\begin{aligned}
  f_\tau: \csn &\rightarrow \mathbb{R}\\
  w &\mapsto \text{ coefficient of $\tau$ in } \sigma(w),
    \end{aligned}
\end{equation}
(extended linearly).
%($\star$ or should $\alpha$ be extended linearly?)
%$w = s_{i_1} \cdots s_{i_\ell}$ to the coefficient of
%$\tau$ in $(t_{i_1}-1) \cdots (t_{i_\ell}-1)$.
To economize notation, we will write $\imm{\tau}$  instead of $\imm{f_\tau}$,
\begin{equation*}
\imm{\tau}(x) 
%\underset{\text{def}}= \imm{f_\tau}(x) 
= \sum_{w \in \sn} f_\tau(w)x_{1,w_1} \cdots x_{n,w_n}.
\end{equation*}
For example, consider the case $n=3$ and $\tau = t_1 \in \K_3$.
Extracting the coefficients 
%$\imm{t_1}(x)$ by using the coefficients
of $t_1$ in the expressions
\begin{equation*}
  \begin{gathered}
    \sigma(e) = 1, \qquad \sigma(s_1) = t_1 - 1, \qquad \sigma(s_2) = t_2 - 1,\\
    \sigma(s_1s_2) = (t_1 - 1)(t_2 - 1) = t_1t_2 - t_1 - t_2 + 1, \\
    \sigma(s_2s_1) = (t_2 - 1)(t_1 - 1) = t_2t_1 - t_1 - t_2 + 1, \\
    \sigma(s_1s_2s_1) = (t_1-1)(t_2-1)(t_1-1) = t_1 + t_2 - t_1t_2 - t_2t_1 - 1,
  \end{gathered}
\end{equation*}
(where we have used $t_1t_2t_1 = t_1$ and $t_1^2 = 2t_1$
to obtain the last expression), we have
%\begin{equation*}
%  \begin{gathered}
$f_{t_1}(e) = 0$,
$f_{t_1}(s_1) = 1$,
$f_{t_1}(s_2) = 0$,
$f_{t_1}(s_1s_2) = -1$,
$f_{t_1}(s_2s_1) = -1$,
$f_{t_1}(s_1s_2s_1) = 1$,
and
\begin{equation*}
  \imm{t_1}(x) = x_{1,2}x_{2,1}x_{3,3}
  - x_{1,3}x_{2,1}x_{3,2}
  - x_{1,2}x_{2,3}x_{3,1}
  + x_{1,3}x_{2,2}x_{3,1}.
  \end{equation*}
Note that in the special case $\tau = 1$, the function $f_\tau$ 
maps a permutation $w$ to $(-1)^{\inv(w)}$.  Thus 
the determinant is a Temperley-Lieb immanant,
\begin{equation*}
\det(x) = \imm{1}(x).
\end{equation*}

It was shown in \cite{RSkanTLImmp} that Temperley-Lieb immanants
are a basis of the space (\ref{eq:tlspace}), and that they are TNN.
Furthermore, they are the extreme rays of the cone of TNN immanants in this
space~\cite[Thm.\,10.3]{RSkanTLImmp}.
%\begin{prop}\label{t:tlimm}
%For any basis element $\tau$ of $\tn$, 
%the function $f_\tau : S_n \rightarrow \tn$ as before.
% by
%\begin{equation*}
%f_\tau(\pi) = [r]\theta(\pi).
%\end{equation*}
%the $f_\tau$-immanant 
%$\imm{\tau}(x)$ is totally nonnegative.
%\end{prop}
%($\star$ Cite.)
%The following was stated in 
\begin{prop}
  Each immanant of the form
  \begin{equation}\label{eq:sumofprodsof2minors}
    \imm f(x) = \sumsb{I,J \subseteq [n]\\ |I|=|J|} c_{I,J}
    \det(x_{I,J}) \det(x_{I^c, J^c})
  \end{equation}
  is a totally nonnegative polynomial if and only if it is equal to
  a nonnegative linear combination of Temperley-Lieb immanants.
\end{prop}
In fact each complementary product of minors is a $0$-$1$ linear
combination of Temper\-ley-Lieb immanants~\cite[Prop.\,4.4]{RSkanTLImmp}.
\begin{thm}\label{t:oneprod}
  %Each product of complementary minors of an $n\times n$ matrix belongs to $\spn \{ \imm{\tau}(x)\,|\,\tau\in\K_n\}$. In particular,
For $I \subseteq [n]$ we have 
\begin{equation}
\det(x_{I,I})\det(x_{I^c,I^c})=\sum_{\tau \in \K_n}b_{\tau}\imm{\tau}(x),    
\end{equation}
where 
\begin{equation}
    b_{\tau}=\begin{cases}
      1 & \text{if there is a principal coloring of $\tau$ with $\{v_i\,|\,i \in I\}$ white, $\{v_i\,|\,i \in [n]\ssm I\}$ black}, \\
      0&\text{otherwise.}
    \end{cases}
\end{equation}
\end{thm}
By (\ref{eq:lmw}) we have that for each two-part partition
$\lambda = (n-j,j)$ of $n$, the corresponding induced sign character immanant
belongs to (\ref{eq:tlspace}).
Furthermore, we have the following explicit expansion of these in terms of the
Temperley-Lieb immanant basis.
%Furthermore, we have an explicit
\begin{thm}\label{t:epsilontau}
For $j = 0,\dotsc,\lfloor \tfrac n2 \rfloor - 1$, we have
\begin{equation*}
    \imm{\epsilon^{n-j,j}}(x) = \sum_{\tau \in \K_n} d_{j,\tau} \imm{\tau}(x),
    \end{equation*}
    where $d_{j,\tau}$
    %= |D_{j}(\tau)|$, 
    is the number of principal colorings of $\tau$ having $j$ white vertices on the left. Explicitly, assuming such a coloring exists, this is $2^{d-\alpha-\beta}\binom{\alpha+\beta}{\alpha}$, where
    $d=$ the number of cycles of $\hat\tau$, and
    $\alpha=\alpha(\tau,j)$, $\beta=\beta(\tau,j)$
    are defined as in (\ref{eq:newalpha}).
    \begin{proof} Omitted.
%    The combinatorial description follows immediately from \cref{t:oneprod}. Now suppose $\hat\tau$ consists of cycles $C_1,\dotsc,C_d$ and consider the proper 2-coloring of these cycles that combine to form a principal coloring of $\tau$ having $j$ white vertices on the left. For each of the $d-\alpha-\beta$ balanced induced subgraphs $\tau_{C_i}$, both of the two possible colorings contribute $\frac{|C_i|}{2}$ white vertices to the left column of $\tau$. There are $2^{d-\alpha-\beta}$ colorings of the corresponding vertices. Besides these, each unbalanced subgraph $\tau_{C_i}$ must be colored so that it contributes more white vertices to the left or to the right. We choose $\alpha$ of these $\alpha+\beta$ unbalanced subgraphs to be right unbalanced in $\binom{\alpha+\beta}{\alpha}$ ways.
    \end{proof}
\end{thm}

Combining (\ref{eq:etom}) and (\ref{eq:lmw}), we see that
monomial immanants $\imm{\phi^\mu}(x)$ indexed by
partitions of the form $\mu = 2^c 1^d \vdash n$ belong to the space
(\ref{eq:tlspace}) as well.
To expand these
%monomial immanants
in the Temperley--Lieb immanant basis,
we define for each $\mu = 2^c 1^d \vdash n$ the set $P(\mu)$
of all $\tau \in \K_n$ such that there exists a principal coloring of $\tau$
with $c+d$ white vertices on the left and
no principal coloring of $\tau$ with $c+d+1$ white vertices on the left.
\begin{thm}\label{t:monimmtnn}
  For $\mu = 2^c 1^d \vdash n$, we have
  that $\imm{\phi^\mu}(x)$ is a totally nonnegative polynomial. In particular we  have 
\begin{equation*}
    \imm{\phi^\mu}(x) = \sum_{\tau \in P(\mu)} b_{\mu,\tau} \imm\tau(x), 
\end{equation*}
where $b_{\mu,\tau}=2^{\# \text{cycles of } \hat\tau \text{ of cardinality } 0~(\text{mod }4)}$.
\end{thm}
\begin{proof}
Omitted.
%Let $t_{i_1}\cdots t_{i_\ell}$ be an expression for $\tau$ which is as short as possible, and let $G$ be the wiring diagram of $s_{i_1}\cdots s_{i_\ell}$. By \cite[Thm.\,10.3]{CHSSkanEKL}, the coefficient $b_{\mu,\tau}$ is the number of path families covering $G$ which satisfy 
%\begin{enumerate}
%    \item $c+d$ pairwise nonintersecting paths are colored white, 
%    \item $c$ pairwise nonintersecting paths are colored black, 
%    \end{enumerate} 
%assuming no path family covering $G$ can be colored
%so that $c+d+1$ nonintersecting paths are colored white.
%It is straightforward to show \cite[Prop.\,2.1]{SkanIneq} that
%such path families correspond bijectively to principal colorings
%of $\tau$ with $c+d$ white and $c$ black vertices on the left,
%assuming that no principal coloring of $\tau$ has $c+d+1$
%white vertices on the left.
%    Let $(\tau,\kappa)$ be a principal coloring with $\alpha(\tau,\kappa)>0$. Let $(\tau,\kappa')$ be a coloring obtained from $(\tau,\kappa)$ by switching the color of each vertex in one right unbalanced subgraph of $(\tau,\kappa)$. In $(\tau,\kappa')$ the total number of white vertices on the left is one bigger than in $(\tau,\kappa)$. Thus, for principal colorings described above $\alpha(\tau,\kappa)=0$ and by \cref{t:epsilontau} we have $b_{\mu,\tau}=2^{d- \beta}$. Since $\alpha=0$, we have that $d-\beta=\# \text{cycles of } \hat\tau \text{ of cardinality } 0~(\text{mod }4)$, as desired.
\end{proof}

\section{Main results}\label{s:mn}

%($\star$Introduce inequalities for products of pairs of minors.)
Fischer's inequalities (\ref{eq:fischer}) naturally lead to the questions of how products
\begin{equation}\label{eq:prodminors}
\det(A_{I,I})\det(A_{I^c,I^c})
\end{equation}
of complementary pairs of minors compare to one another, and of whether a greater cardinality difference $|I^c| - |I|$ tends to make the product (\ref{eq:prodminors}) greater or smaller.
This second question led Barrett and Johnson~\cite{BJMajor} to consider the average value of such products when cardinalities are fixed,
\begin{equation}\label{eq:avg2}
    \frac 1{\binom nk} \sumsb{I \subseteq [n]\\|I| = k}
    \det(A_{I,I})\det(A_{I^c,I^c}).
    \end{equation}
    They found that for PSD matrices, a smaller cardinality difference makes the average product of minors greater~\cite[Thm.\,1]{BJMajor}.
    %Borcea--Branden proved inequalities between symmetrized Fischer's products for PSD matrices \cite{BBApps}. 
    We give two proofs that the same is true for TNN matrices.

\begin{thm}\label{t:fischer} For all TNN matrices A and for $k = 0,\dotsc, \lfloor \tfrac n2 \rfloor - 1,$ we have
\begin{equation}\label{eq:fisher}
    \frac1{\tbinom nk} \displaystyle{\sum_{|I|=k}} \det(A_{I,I}) \det(A_{I^c,I^c})
    %{\displaystyle{\binom nk}}
    \leq
    \frac1{\tbinom{n}{k+1}}\displaystyle{\sum_{|I|=k+1}} \det(A_{I,I}) \det(A_{I^c,I^c}).
    %}{\displaystyle{\binom n{k+1}}}.
    \end{equation}
\end{thm}
\begin{proof}[First proof (idea)]
By (\ref{eq:lmw}) it is equivalent to show that the polynomial
\begin{equation}\label{eq:ediff}
    \frac{\imm{\epsilon^{n-k-1,k+1}}(x)}{\displaystyle{\tbinom n{k+1}}} - 
    \frac{\imm{\epsilon^{n-k,k}}(x)}{\displaystyle{\tbinom nk}}
\end{equation}
is totally nonnegative.  By \cref{t:epsilontau}, this difference belongs to the span of the Temperley-Lieb immanants.  Multiplying 
%the difference 
by $n!/(k!(n-k-1)!)$ we obtain
\begin{equation}\label{eq:fishertlnofrac}
    (k+1)\imm{\epsilon^{n-k-1,k+1}}(x) - 
    (n-k)\imm{\epsilon^{n-k,k}}(x) 
    = \sum_{\tau \in \K_n} c_\tau \imm \tau (x),
\end{equation}
where 
%\begin{equation}\label{eq:ddc}
$c_\tau = (k+1)d_{k+1,\tau} - (n-k)d_{k,\tau}$,
and $d_{k+1,\tau}$, $d_{k,\tau}$ are defined in terms of proper colorings of $\tau$ as in \cref{t:epsilontau}.
Straightforward computations show that $c_\tau \geq 0$.
%
%We claim that $c_\tau \geq 0$.
%Suppose we have a proper coloring of $\tau$ in which $k$ vertices on the left are white. Let $\alpha = \alpha(\tau,k)$ and $\beta = \beta(\tau,k)$ be the numbers of right-unbalanced and left-unbalanced subgraphs of $\tau$ respectively, as in \ref{eq:newalpha}.
%
%Let $d$ be the number of cycles defined as in \cref{t:epsilontau}. Then by \cref{t:epsilontau} we have that (\ref{eq:ddc}) equals
%\begin{equation}\label{eq:abgamma}
%    \begin{aligned}
%    (k+1)d_{k+1,\tau} - (n-k)d_{k,\tau} &=
%    (k+1)2^{d-\alpha-\beta}\binom{\alpha+\beta}{\alpha-1}
%    -(n-k)2^{d-\alpha-\beta}\binom{\alpha+\beta}{\alpha} \\
%    &= 2^{d-\alpha-\beta}\left( (k+1)\binom{\alpha+\beta}{\alpha-1} - (n-k) \binom{\alpha+\beta}{\alpha} \right)\\
 %   &= 2^{d-\alpha-\beta}\frac{(\alpha+\beta)!}{(\alpha-1)!\beta!} \left( \frac{k+1}{\beta+1} - \frac{n-k}{\alpha} \right).
%    \end{aligned}
%\end{equation}
%Then substituting $\alpha = n - 2k + \beta$ (see formula \ref{eq:njdiff}), the final difference of fractions (\ref{eq:abgamma}) becomes
%\begin{equation*}
%    \frac{(k+1)(n-2k+\beta) - (n-k)(\beta+1)} %{(\beta+1)(n-2k+\beta)}.
%\end{equation*}
%This denominator is clearly positive.  The numerator is $(n-2k - 1)(k-\beta)$,
%which is nonnegative because of the bounds on $k$ and the definition of $\beta$.
\end{proof}



%The Fisher inequalities assert that for any $n \times n$
%positive definite (?) matrix $A$ and for 
%$k = \lceil \frac n2 \rceil, \dotsc n$, we have
%\begin{equation}\label{eq:fisherimmineq}
%  \frac{\imm{\epsilon^{(k,n-k)}}(A)}{\binom nk} \geq
%    \frac{\imm{\epsilon^{(k+1,n-k-1)}}(A)}{\binom n{k+1}}.
%\end{equation}
%These inequalities also hold for totally nonnegative matrices.
%Equivalently, we have the following.
%\begin{thm}
%  Fix $n > 0$.  For $k = \lceil \frac n2 \rceil, \dotsc n-1$,
%  the polynomial
%  \begin{equation}\label{eq:fisherpoly}
%    \frac{\imm{\epsilon^{(k,n-k)}}(x)}{\binom nk} -
%    \frac{\imm{\epsilon^{(k+1,n-k-1)}}(x)}{\binom n{k+1}}.
%  \end{equation}
%  in $\mathbb R[x]$ is totally nonnegative.
%\end{thm}

\begin{proof}[Second proof (idea)]
Again we multiply the polynomial (\ref{eq:ediff})
%  Multiplying the polynomial 
by
  ${n!}/({k!(n-k-1)!})$. Expanding in the monomial immanant
  basis of the trace immanant space, we have
  \begin{equation}\label{eq:fisherpoly2}
    (n-k)\imm{\epsilon^{(k,n-k)}}(x) -
    (k+1)\imm{\epsilon^{(k+1,n-k-1)}}(x) = \sum_{\mu \vdash n} c_{\mu}\imm{\phi^\mu}(x)
  \end{equation}
  where the integers $\{ c_{\mu} \,|\, \mu \vdash n \}$ satisfy
%  \begin{equation}\label{eq:efisher}
    $(n-k)e_{(k,n-k)} - (k+1)e_{(k+1,n-k-1)} = \sum_{\mu \vdash n} c_{\mu}m_\mu$.
%  \end{equation}
%  We claim that $c_{\mu} \geq 0$ for all relevant partitions $\mu$.
%  To see this, consider 
The special case of (\ref{eq:etom}) 
  for two-part partitions,
%  \begin{equation*}
%    e_{(k,n-k)} = \sum_{a=0}^{n-k} M_{(k,n-k),2^a1^{n-2a}} %m_{2^a1^{n-2a}}.
%  \end{equation*}
%  It follows 
implies that each partition $\mu$ appearing with nonzero coefficient in (\ref{eq:fisherpoly2})
  has the form $\mu = 2^a1^{n-2a}$.
Straightforward computations
show that we have $c_\mu \geq 0$, and
thus \cref{t:monimmtnn} completes the proof.
%and 
%  Since each column-strict Young tableaux of shape $(k,n-k)$ and content
%  $2^a 1^{n-2a}$ contains the letters $1, 1, 2, 2, \dotsc, a, a$ in rows
%  $1, \dotsc, a$, it is completely determined by the subset of the
%  letters $\{a+1, \dotsc, n-a\}$
%  appearing in rows $a+1,\dotsc,n-k$ of column $2$.
%  Thus there are $\tbinom{n-2a}{n-k-a} = \tbinom{n-2a}{k-a}$ such tableaux.
%  It follows that in the right-hand side of (\ref{eq:efisher}),
%  %  for $a = 0,\dotsc,n-k$,
%  the coefficient of $m_{2^a1^{n-2a}}$ is
%  \begin{equation*}
%    c_{2^a1^{n-2a}} = \begin{cases}
%      (n-k)\binom{n-2a}{k-a} 
%      &\text{if $a = n-k$,}\\
 %     (n-k)\binom{n-2a}{k-a} - (k+1)\binom{n-2a}{k-a+1}
 %     &\text{if $0 \leq a \leq n-k-1$.}
%    \end{cases}
%  \end{equation*}
%This last expression is equal to
%  \begin{multline*}
%    \frac{(n-2a)!}{(k-a)!(n-k-a-1)!}
%      \bigg( \frac{n-k}{n-k-a} - \frac{k+1}{k-a+1} \bigg)\\% 
%      = \frac{(n-2a)!}{(k-a)!(n-k-a-1)!}
%      \bigg( \frac{2k+1-n}{(n-k-a)(k-a+1)} \bigg),
%  \end{multline*}
%  which is positive, since
%  $a < n-k \leq \lfloor \tfrac n2 \rfloor \leq k \leq n$.
%
%  Now by \cref{t:monimmtnn}
%  we have that
%  (\ref{eq:fisherpoly2})
%  is a totally nonnegative polynomial, and that
%  (\ref{eq:ediff}) is as well.
\end{proof}
Now we may state and prove our main theorem.  
%Consideration of the average value of products of two complentary minors (\ref{eq:avg2}) naturally led Barrett and Johnson to consider average values of products of arbitrarily many minors having fixed cardinality sequences $\lambda = (\lambda_1,\dotsc,\lambda_r) \vdash n$, 
%\begin{equation}\label{eq:avgr}
%\frac{1}{\binom{n}{\lambda_1,\dotsc,\lambda_r}}
%\sum_{(I_1,\dotsc,I_r)}\det(A_{I_1,I_1}) \cdots %\det(A_{I_r,I_r}),
%\end{equation}
%where the sum is over ordered set partitions of $[n]$ of type $\lambda$ and the multinomial coefficient $\binom{n}{\lambda_1,\dotsc,\lambda_r} = \tfrac{n!}{\lambda_1! \cdots \lambda_r!}$ is the number of such ordered set partitions.  They found that for PSD matrices, partitions which appear lower in the majorization order lead to greater average products~\cite[Thm.\,2]{BJMajor}.  We show that the same is true for TNN matrices.  
%which are greater.
%inequalities hold for TNN matrices, follows easily from \cref{t:fischer}.  
  
\begin{thm}\label{t:main}
Fix $n > 0$ and partitions $\lambda = (\lambda_1,\dotsc,\lambda_r) \vdash n$,
$\mu = (\mu_1 \dotsc, \mu_s) \vdash n$ with $\lambda \preceq \mu$.
For all TNN matrices we have
  \begin{equation}\label{eq:majorfischerpoly}
%j!(n-j)! 
\lambda_1!\cdots\lambda_r!
\nTksp\sum_{(I_1,\dotsc,I_r)}\nTksp
\det(A_{I_1,I_1}) \cdots \det(A_{I_r,I_r}) ~\geq~
  \mu_1!\cdots\mu_s!
  \nTksp\sum_{(J_1,\dotsc,J_s)}\nTksp
  \det(A_{J_1,J_1}) \cdots \det(A_{J_s,J_s}),
%  \frac{\imm{\epsilon^\lambda}(x)}{\binom n{\lambda_1,\dotsc,\lambda_r}} -
  %  \frac{\imm{\epsilon^\mu}(x)}{\binom n{\mu_1,\dotsc,\mu_s}}
  \end{equation}
  %in $\mathbb R[x]$ is totally nonnegative.  %Furthermore, it evaluates nonnegatively on positive definite matrices.
\end{thm}
\begin{proof}
  By (\ref{eq:movebox}) it suffices to consider $\lambda$, $\mu$ having equal parts except
  %\begin{equation*}
  $\mu_i = \lambda_i + 1$ and $\mu_j = \lambda_j - 1$
%  \end{equation*}
  for some $i < j$. (Thus we may assume $s = r$ and will allow $\mu_s = 0$.)
  Let $\nu = (\nu_1,\dotsc,\nu_{r-2})$ be the partition of $n - \lambda_i - \lambda_j$ consisting of all other parts.
  
As in the proofs of \cref{t:fischer}, we observe that each sum of products of minors is an induced sign character immanant (\ref{eq:lmw}). Thus the inequality (\ref{eq:majorfischerpoly}) is equivalent to the total nonnegativity of the polynomial
      \begin{equation}\label{eq:thediff}
      \lambda_1! \cdots \lambda_r!\; \imm{\epsilon^\lambda}(x) - 
      \mu_1! \cdots \mu_r!\;
      \imm{\epsilon^\mu}(x).
      \end{equation}
      %By (\ref{eq:lmw}) we may
      Dividing this by $\nu_1! \cdots \nu_{r-2}! \lambda_i! \mu_j!$ and collecting terms, we obtain
%      \end{aligned}
  %\end{equation*}
  \begin{equation*}
  \begin{gathered}
      \lambda_j 
      \ntksp \sumsb{J \subseteq [n]\\|J| = |\nu|} \ntksp \imm{\epsilon^\nu}(x_{J,J}) \imm{\epsilon^{(\lambda_i,\lambda_j)}}(x_{J^c,J^c}) - 
      \mu_i 
      \ntksp \sumsb{J \subseteq [n]\\|J| = |\nu|}\ntksp \imm{\epsilon^\nu}(x_{J,J}) \imm{\epsilon^{(\lambda_i+1,\lambda_j-1)}}(x_{J^c,J^c}) \\
      = \ntksp \sumsb{J \subseteq [n]\\|J| = |\nu|} \imm{\epsilon^\nu}(x_{J,J})
      \left(\lambda_j \imm{\epsilon^{(\lambda_i,\lambda_j)}}(x_{J^c,J^c})
      -
      \mu_i 
      \imm{\epsilon^{(\lambda_i+1,\lambda_j-1)}}(x_{J^c,J^c}) \right).
      \end{gathered}
  \end{equation*}
  By \cref{t:fischer}, or more precisely (\ref{eq:fishertlnofrac}),
  this polynomial is TNN and so is (\ref{eq:thediff}).
  %by \cite[Thm.\,2]{BJMajor}
  %it evaluates nonnegatively on positive definite matrices.
\end{proof}

%Further consideration of averages suggests 
It would be interesting to extend the Barrett--Johnson inequalities (\ref{eq:bj}) %\cref{t:main} 
to all HPSD matrices, and to state a permanental analog as 
%This problem was 
originally suggested in \cite{BJMajor}.
Using (\ref{eq:lmw})
we may state these problems 
%of
%have the following possibilities of 
%extending (\ref{eq:bj})
as follows.
\begin{prob}\label{p:bj}
Characterize the pairs $(\lambda,\mu)$
of partitions of $n$ for which we have
\begin{enumerate}
    \item $\lambda_1! \cdots \lambda_r! \;\imm{\epsilon^\lambda}(A) \leq 
    \mu_1! \cdots \mu_r! \;\imm{\epsilon^\mu}(A)$ for all $A$ HPSD,
    \item $\lambda_1! \cdots \lambda_r! \;\imm{\eta^\lambda}(A) \geq
    \mu_1! \cdots \mu_r! \;\imm{\eta^\mu}(A)$ for all $A$ HPSD or PSD,
    \item $\lambda_1! \cdots \lambda_r! \;\imm{\eta^\lambda}(A) \geq
    \mu_1! \cdots \mu_r! \;\imm{\eta^\mu}(A)$ for all $A$ TNN.
\end{enumerate}
%\begin{equation*} 
%\lambda_1!\cdots\lambda_r!
%\nTksp\sum_{(I_1,\dotsc,I_r)}\nTksp
%\perm(A_{I_1,I_1}) \cdots %\perm(A_{I_r,I_r}) ~\geq~
%  \mu_1!\cdots\mu_s!
%  \nTksp\sum_{(J_1,\dotsc,J_s)}\nTksp
%  \perm(A_{J_1,J_1}) \cdots %\perm(A_{J_s,J_s}),
%\end{equation*}
%where $(\lambda_1,\dotsc,\lambda_r)$, $(\mu_1,\dotsc,\mu_s)$ are nonnegative sequences summing to $n$ and the sums are over
%sequences of disjoint subsets of $[n]$ having these cardinalities?
\end{prob}

%\section{Acknowledgements} The authors are grateful to Shaun Fallat
%and Misha Gekhtman for
%suggesting the problem and
%helpful conversations.  

\printbibliography
\end{document}

.
