%% 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} .