From Unit Interval Orders to Totally Nonnegative Matrices: Permanental Inequalities and Bruhat-Increasing Bijections

Abstract

Given an $n\times n$ matrix $A=(a_{i,j})$ and subsets $I,J$ of $[1,n]:=\{1,\dots ,n\}$, let $A_{I,J}=(a_{i,j}{)}_{i\in I,j\in J}$ denote the $(I,J)$-submatrix of $A$. We prove that, for every totally nonnegative matrix $A$ and every $h=1,\dots ,n-1$, \begin{equation} \operatorname{perm}(A_{[1,h],[1,h]}) \operatorname{perm}(A_{[h+1,n],[h+1,n]}) \;\geq\; \operatorname{perm}(A_{[1,n]\cap 2\mathbb Z,[1,n]\cap 2\mathbb Z}) \operatorname{perm}(A_{[1,n]\smallsetminus 2\mathbb Z,[1,n]\smallsetminus 2\mathbb Z}). \label{eq:absmain} \end{equation} In particular, these inequalities hold for the $0$-$1$ totally nonnegative matrices arising as antiadjacency matrices of unit interval orders. Our proof is based on explicit Bruhat-order comparisons between two distinguished families of permutations. Let ${\mathfrak{A}}_n$ be the Young subgroup ${\mathfrak{S}}_{1,\dots ,\lfloor \frac{n}{2}\rfloor }\times {\mathfrak{S}}_{\lfloor \frac{n}{2}\rfloor +1,\dots ,n}$ and let ${\mathfrak{B}}_n$ be the set of parity-alternating permutations \begin{equation*} \{w=w_1\cdots w_n\in\mathfrak{S}_n \mid i \text{ and } w_i \text{ have the same parity}\}. \end{equation*} For the balanced case $h=\lfloor \frac{n}{2}\rfloor$, we construct a bijection $f_n:{\mathfrak{A}}_n\to {\mathfrak{B}}_n$ satisfying $w\le f_n(w)$ in Bruhat order. We then extend this construction to arbitrary $h$ by means of maps $g_{n,h}$ satisfying the corresponding Bruhat-order comparison. These maps yield the inequalities for all totally nonnegative matrices.

56 pages. V2: 64 pages. Added Chapter 9 to include generalized results for TNN matrices. Updated title, abstract and introduction to reflect the change