# Barrett–Johnson inequalities for totally nonnegative matrices

Mark Skandera  and  Daniel Soskin

###### Abstract.

Given a matrix $A$, let $A_{I,J}$ denote the submatrix of $A$ determined by
rows $I$ and columns $J$. Fischer’s 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 for sums of
products of principal minors whose orders are given by nonincreasing integer
sequences $(\lambda_{1},\dotsc,\lambda_{r})$, $(\mu_{1},\dotsc,\mu_{s})$
summing to $n$. Specifically, if
$\lambda_{1}+\cdots+\lambda_{i}\leq\mu_{1}+\cdots+\mu_{i}$ for all $i$, then

$\lambda_{1}!\cdots\lambda_{r}!\negthickspace\negthickspace\sum_{(I_{1},\dotsc,I_{r})}\negthickspace\negthickspace\det(A_{I_{1},I_{1}})\cdots\det(A_{I_{r},I_{r}})~{}\geq~{}\mu_{1}!\cdots\mu_{s}!\negthickspace\negthickspace\sum_{(J_{1},\dotsc,J_{s})}\negthickspace\negthickspace\det(A_{J_{1},J_{1}})\cdots\det(A_{J_{s},J_{s}}),$

where sums are over sequences of disjoint subsets of $\\{1,\dotsc,n\\}$
satisfying $|I_{k}|=\lambda_{k}$, $|J_{k}|=\mu_{k}$. We show that these
inequalities hold for totally nonnegative matrices as well.

##  1\. Introduction

A matrix $A\in\mathrm{Mat}_{n\times n}(\mathbb{C})$ is called _Hermitian_ if
it satisfies $A^{*}=A$ where $*$ denotes conjugate transpose. Such a matrix is
called _Hermitian positive semi-definite_ (HPSD) if we have $x^{*}Ax\geq 0$
for all $x\in\mathbb{C}^{n}.$ For $A\in\mathrm{Mat}_{n\times n}(\mathbb{R})$,
the Hermitian property reduces to symmetry
$A^{\negthickspace\top\negthickspace}=A$, and the positive semidefinite (PSD)
property reduces to $x^{\negthickspace\top\negthickspace}Ax\geq 0$ for all
$x\in\mathbb{R}^{n}$. Hermitian matrices are fundamental to quantum mechanics
since they describe operators with real eigenvalues. Positive definite (semi-
definite) matrices are one of the matrix analogs of positive (nonnegative)
numbers, and correspond to inner products (nonnegative quadratic forms). They
appear in many fields such as geometry, numerical analysis, optimization,
quantum physics, and statistics. See [2] and [26].

Another matrix analog of nonnegative numbers is the class of _totally
nonnegative_ (TNN) matrices, those matrices in $\mathrm{Mat}_{n\times
n}(\mathbb{R})$ in which each minor (determinant of a square submatrix) is
nonnegative. Initially, total nonnegativity arose in three different areas. It
was studied by Gantmacher and Krein in oscillations of vibrating systems, by
Schoenberg in applications to analysis of real roots of polynomials and spline
functions, and by Karlin in integral equations and statistics. TNN matrices
appear in many other areas of mathematics. (See, e.g., [8].)

Like TNN matrices, HPSD matrices have a well-known characterization in terms
of matrix minors. Given an $n\times n$ matrix $A=(a_{i,j})$ and subsets
$I,J\subseteq[n]:=\\{1,\dotsc,n\\}$, define the submatrix
$A_{I,J}=(a_{i,j})_{i\in I,j\in J}$, and define the set
$I^{c}:=[n]\smallsetminus I$. While TNN matrices are characterized by the
inequalities

(1.1) $\det(A_{I,J})\geq 0,\qquad\text{for all $I,J\subseteq[n]$ with
}|I|=|J|,$

HPSD matrices are characterized by the equalities

(1.2) $\displaystyle a_{j,i}^{*}$ $\displaystyle=a_{i,j},$
$\displaystyle\text{for all $i,j\in[n]$},$ $\displaystyle\det(A_{I,I})$
$\displaystyle\geq 0,$ $\displaystyle\text{for all $I\subseteq[n]$}.$

From the inequalities in (1.1) – (1.2), one can deduce many inequalities
satisfied by polynomials in the entries of $n\times n$ HPSD, PSD, and/or TNN
matrices. The following inequalities hold for HPSD matrices and TNN matrices.
Hadamard [13] showed that for $A$ HPSD we have

(1.3) $\det(A)\leq a_{1,1}\cdots a_{n,n},$

and Koteljanskii [16], [17] showed that this holds for $A$ TNN as well. Marcus
[21] proved a permanental analog

(1.4) $\mathrm{per}(A)\geq a_{1,1}\cdots a_{n,n}$

for $A$ HPSD, and this analog clearly holds for $A$ TNN as well. Fischer [11]
strengthened (1.3) by showing that for all $I\subseteq[n]$ we have

(1.5) $\det(A)\leq\det(A_{I,I})\det(A_{I^{c},I^{c}}),$

and Ky Fan showed that this holds for $A$ TNN as well (unpublished; see [5]).
Lieb [18] proved a permanental analog

(1.6)
$\mathrm{per}(A)\geq\mathrm{per}(A_{I,I})\;\mathrm{per}(A_{I^{c},I^{c}}),$

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 (1.6) also appears on the
left-hand side. Koteljanskii [16], [17] strengthened (1.5) further by proving
that for all $I,J\subseteq[n]$ we have

(1.7) $\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})$

for $A$ belonging to a class of matrices including HPSD and TNN matrices.
Strengthening (1.3) somewhat differently, Schur [27] proved that for each
$\mathfrak{S}_{n}$-character $\chi$, the inequality

(1.8) $\det(A)\leq\frac{\mathrm{Imm}_{\chi}(A)}{\chi(e)}$

holds for $A$ HPSD, where $\mathrm{Imm}_{\chi}$ is the corresponding immanant
(defined in §3). Stembridge [32, Cor. 3.4] showed that this holds for $A$ TNN
as well.

Other inequalities hold for TNN matrices, and are not known to hold for HPSD
matrices. For instance Charles Johnson showed that the permanental analog of
(1.8),

(1.9) $\mathrm{per}(A)\geq\frac{\mathrm{Imm}_{\chi}(A)}{\chi(e)},$

holds for TNN matrices (unpublished; see [33, p. 1088]). The validity of this
inequality for HPSD matrices was conjectured by Lieb [18], is still open, and
is known as the permanental dominance conjecture. Extending the results (1.5)
and (1.7), Fallat, Gekhtman, and Johnson [9] and the first author [28]
characterized all $8$-tuples
$(I,J,K,L,I^{\prime},J^{\prime},K^{\prime},L^{\prime})$ of subsets of $[n]$
for which we have the inequality

(1.10)
$\det(A_{I,I^{\prime}})\det(A_{J,J^{\prime}})\leq\det(A_{K,K^{\prime}})\det(A_{L,L^{\prime}})$

whenever $A$ is TNN. (See [29] for progress on products of three or more
minors.) Drake, Gerrish, and the first author [7] proved a similar result for
products of $n$ matrix entries. In particular, the inequality

(1.11) $a_{1,v_{1}}\negthinspace\cdots{a}_{n,v_{n}}\geq
a_{1,w_{1}}\negthinspace\cdots{a}_{n,w_{n}}$

holds for all TNN $A$ if and only if $v\leq w$ in the Bruhat order on
$\mathfrak{S}_{n}$. (See, e.g., [3].) Other linear combinations of the
monomials in (1.11) which produce valid inequalities for TNN matrices are
related to Lusztig’s work on canonical bases of quantum groups [20] and are
called _Kazhdan-Lusztig immanants_ in [25]. Writing these as
$\\{\mathrm{Imm}_{w}(A)\,|\,w\in\mathfrak{S}_{n}\\}$, we have

(1.12) $\mathrm{Imm}_{w}(A)\geq 0$

for all $w\in\mathfrak{S}_{n}$ and all TNN $A$. (See [25] for definitions.) We
will define and use special cases of these, called Temperley-Lieb immanants in
[24], in Section 4.

Still other inequalities hold for HPSD matrices and are not known to hold for
TNN matrices. Heyfron [14] extended (1.8) and proved special cases of the
permanental dominance conjecture (1.9) by considering irreducible
$\mathfrak{S}_{n}$-characters indexed by ”hook” shapes
$\lambda=(k,1,\dotsc,1)$. (See Sections 2 – 3 for definitions.) In particular,
we have

(1.13)
$\mathrm{per}(A)=\frac{\mathrm{Imm}_{\chi^{n}}(A)}{\chi^{n}(e)}\geq\frac{\mathrm{Imm}_{\chi^{n-1,1}}(A)}{\chi^{n-1,1}(e)}\geq\frac{\mathrm{Imm}_{\chi^{n-2,1,1}}(A)}{\chi^{n-2,1,1}(e)}\geq\cdots\geq\frac{\mathrm{Imm}_{\chi^{1,\cdots,1}}(A)}{\chi^{1,\cdots,1}(e)}=\det(A)$

for $A$ HPSD. (See [23] for more results of this form.) Borcea and Brändén
showed that averages of the products of pairs of minors appearing in (1.5)
satisfy the log-concavity inequalities [4, Cor. 3.1 (b)]

(1.14) $\left(\sum_{\begin{subarray}{c}I\subseteq[n]\\\
|I|=k\end{subarray}}\frac{\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k}}}\negthickspace\right)^{\negthickspace\negthickspace
2}\geq\left(\sum_{\begin{subarray}{c}I\subseteq[n]\\\
|I|=k+1\end{subarray}}\negthickspace\negthickspace\frac{\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k+1}}}\negthickspace\right)\negthickspace\left(\sum_{\begin{subarray}{c}I\subseteq[n]\\\
|I|=k-1\end{subarray}}\negthickspace\negthickspace\frac{\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k-1}}}\negthickspace\right)$

for all $A$ HPSD and $k=1,\dotsc,n-1$. They also showed that these averages
satisfy the Maclaurin-type inequalities [4, Cor. 3.1 (c)]

(1.15)
$\left(\frac{\displaystyle{\sum}_{|I|=k+1}\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k+1}}\det(A)}\right)^{\negthickspace
k}\negthinspace\geq\left(\frac{\displaystyle{\sum}_{|I|=k}\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k}}\det(A)}\right)^{k+1}$

for all nonsingular $A$ HPSD and $k=1,\dotsc,n-1$.

Nearly belonging to the HPSD list above are the Barrett–Johnson Inequalities
[1] for (real) PSD matrices. Given nonnegative integer sequences
$\lambda=(\lambda_{1},\dotsc,\lambda_{r})$, $\mu=(\mu_{1},\dotsc,\mu_{s})$
summing to $n$, we have

(1.16)
$\lambda_{1}!\cdots\lambda_{r}!\negthickspace\negthickspace\sum_{(I_{1},\dotsc,I_{r})}\negthickspace\negthickspace\det(A_{I_{1},I_{1}})\cdots\det(A_{I_{r},I_{r}})~{}\geq~{}\mu_{1}!\cdots\mu_{s}!\negthickspace\negthickspace\sum_{(J_{1},\dotsc,J_{s})}\negthickspace\negthickspace\det(A_{J_{1},J_{1}})\cdots\det(A_{J_{s},J_{s}}),$

if and only if $\lambda_{1}+\cdots+\lambda_{i}\leq\mu_{1}+\cdots+\mu_{i}$ for
all $i$, where the sums are over sequences of disjoint subsets of $[n]$ having
cardinalities $\lambda$, $\mu$, respectively. We will show that these
inequalities also hold for TNN matrices.

In Section 2, we review basic facts about the symmetric group, its traces
(class functions), and symmetric functions. In Section 3 we apply these ideas
to form certain polynomials called immanants in the entries of $n\times n$
matrices, and we discuss the evaluation of these at TNN matrices. In Section
4, we discuss the Temperley–Lieb algebra, related immanants, and their
relationship to products of matrix minors. In Section 5, we present our main
result that the Barrett–Johnson inequalities hold for all $n\times n$ TNN
matrices.

##  2\. The symmetric group, its traces, and symmetric functions

The symmetric group algebra $\mathbb{C}[\mathfrak{S}_{n}]$ is generated over
$\mathbb{C}$ by $s_{1},\dotsc,s_{n-1}$, subject to relations

$\displaystyle s_{i}^{2}$ $\displaystyle=e$ $\displaystyle\text{for
$i=1,\dotsc,n-1$},$ $\displaystyle s_{i}s_{j}s_{i}$
$\displaystyle=s_{j}s_{i}s_{j}$ $\displaystyle\text{for $|i-j|=1$},$
$\displaystyle s_{i}s_{j}$ $\displaystyle=s_{j}s_{i}$ $\displaystyle\text{for
$|i-j|\geq 2$}.$

We define the one-line notation $w_{1}\cdots w_{n}$ of $w\in\mathfrak{S}_{n}$
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\mathfrak{S}_{n}$, we call $\ell$ the length of $w$ and write
$\ell=\ell(w)$. It is known that $\ell(w)$ is equal to $\textsc{inv}(w)$, the
number of inversions in $w_{1}\cdots w_{n}$. It is also known that conjugacy
classes in $\mathfrak{S}_{n}$ 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 parts, and we let $|\lambda|=n$ and $\lambda\vdash n$
denote that $\lambda$ is a partition of $n$. Given $\lambda\vdash n$, we
define the transpose partition
$\lambda^{\negthickspace\top\negthickspace}=(\lambda^{\negthickspace\top\negthickspace}_{1},\dotsc,\lambda^{\negthickspace\top\negthickspace}_{\lambda_{1}})$
by

$\lambda^{\negthickspace\top\negthickspace}_{i}=\\#\\{j\,|\,\lambda_{j}\geq
i\\}.$

Sometimes it is convenient to name a partition with exponential notation,
omitting parentheses and commas, so that $4^{2}1^{6}:=(4,4,1,1,1,1,1,1)$.
Sometimes it is convenient to partially order partitions of $n$ by the
_majorization order_ ,

(2.1)
$\lambda\preceq\mu\quad\text{iff}\quad\lambda_{1}+\cdots+\lambda_{i}\leq\mu_{1}+\cdots+\mu_{i}$

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

(2.2) $\mu_{i}=\lambda_{i}+1,\qquad\mu_{j}=\lambda_{j}-1.$

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$. Five standard bases of
$\Lambda_{n}$ consist of the monomial $\\{m_{\lambda}\,|\,\lambda\vdash n\\}$,
elementary $\\{e_{\lambda}\,|\,\lambda\vdash n\\}$, (complete) homogenous
$\\{h_{\lambda}\,|\,\lambda\vdash n\\}$, power sum
$\\{p_{\lambda}\,|\,\lambda\vdash n\\}$, and Schur
$\\{s_{\lambda}\,|\,\lambda\vdash n\\}$ symmetric functions. (See, e.g., [30,
Ch. 7] for definitions.)

The change-of-basis matrix relating $\\{e_{\lambda}\,|\,\lambda\vdash n\\}$
and $\\{m_{\lambda}\,|\,\lambda\vdash n\\}$ is given by the equations

(2.3)
$e_{\lambda}=\sum_{\mu\preceq\lambda^{\negthickspace\top\negthickspace}}M_{\lambda,\mu}m_{\mu},$

where $M_{\lambda,\mu}$ equals the number of column-strict Young tableaux of
shape $\lambda^{\negthickspace\top\negthickspace}$ 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

$e_{221}=m_{32}+2m_{311}+5m_{221}+12m_{2111}+30m_{11111},$

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

${\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,\qquad\qquad\qquad{\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox
to0.0pt{\vss\hbox to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox
to0.0pt{\hss\vbox to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox
to0.4pt{\vrule width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,\quad{\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox
to0.0pt{\vss\hbox to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox
to0.0pt{\hss\vbox to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox
to0.4pt{\vrule width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,}}}}}}}}}}}}}}}$
${\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,\quad{\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox
to0.0pt{\vss\hbox to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox
to0.0pt{\hss\vbox to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox
to0.4pt{\vrule width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,\quad{\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox
to0.0pt{\vss\hbox to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox
to0.0pt{\hss\vbox to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox
to0.4pt{\vrule width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,\quad{\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox
to0.0pt{\vss\hbox to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox
to0.0pt{\hss\vbox to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox
to0.4pt{\vrule width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,,\quad{\hbox{=100$\vbox{\halign{&\mkcell{#}\cr\vbox
to0.0pt{\vss\hbox to0.0pt{\hss$3$\hss}\vss}\vbox to0.0pt{\vss\hbox
to0.0pt{\hss\vbox to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox
to0.4pt{\vrule width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt|\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$2$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt,\vbox to0.0pt{\vss\hbox
to0.0pt{\hss$1$\hss}\vss}\vbox to0.0pt{\vss\hbox to0.0pt{\hss\vbox
to0.4pt{\hrule depth=0.4pt,height=0.0pt\vss\hbox to0.4pt{\vrule
width=0.4pt,height=0.4pt\hss\vrule width=0.4pt}\vss\hrule
height=0.4pt,depth=0.0pt}\kern-0.2pt}\kern-0.2pt\crcr}}$}}\,.}}}}}}}}}}}}}}}}}}}}}}}}}$

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

Let $\mathcal{T}_{n}$ be the $\mathbb{Z}$-module of
$\mathbb{Z}[\mathfrak{S}_{n}]$-traces (equivalently, $\mathfrak{S}_{n}$-class
functions), linear functionals
$\theta:\mathbb{Z}[\mathfrak{S}_{n}]\rightarrow\mathbb{Z}$ satisfying
$\theta(gh)=\theta(hg)$ for all $g,h\in\mathbb{Z}[\mathfrak{S}_{n}]$. Like the
$\mathbb{Z}$-module $\Lambda_{n}$, the trace space $\mathcal{T}_{n}$ has
dimension equal to the number of integer partitions of $n$. The Frobenius
$\mathbb{Z}$-module isomorphism (2.4)

(2.4) $\displaystyle\mathrm{Frob}:\mathcal{T}_{n}$
$\displaystyle\rightarrow\Lambda_{n}$ $\displaystyle\theta$
$\displaystyle\mapsto\frac{1}{n!}\sum_{w\in\mathfrak{S}_{n}}\theta(w)p_{\mathrm{ctype}(w)}$

define bijections between standard bases of $\Lambda$, and $\mathcal{T}_{n}$.
Schur functions correspond to irreducible characters,

$s_{\lambda}\leftrightarrow\chi^{\lambda}$

while elementary and homogeneous symmetric functions correspond to induced
sign and trivial characters,

$\begin{gathered}e_{\lambda}\leftrightarrow\epsilon^{\lambda}=\mathrm{sgn}\big{\uparrow}\negthickspace\negthickspace\phantom{\uparrow}^{\mathfrak{S}_{n}}_{\mathfrak{S}_{\lambda}}\qquad
h_{\lambda}\leftrightarrow\eta^{\lambda}=\mathrm{triv}\big{\uparrow}\negthickspace\negthickspace\phantom{\uparrow}^{\mathfrak{S}_{n}}_{\mathfrak{S}_{\lambda}}\end{gathered}$

where $\mathfrak{S}_{\lambda}$ is the Young subgroup of $\mathfrak{S}_{n}$
indexed by $\lambda$. The power sum and monomial bases of $\Lambda_{n}$
correspond to bases of $\mathcal{T}_{n}$ which are not characters. We call
these the power sum $\\{\psi^{\lambda}\,|\,\lambda\vdash n\\}$ and monomial
$\\{\phi^{\lambda}\,|\,\lambda\vdash n\\}$ traces, respectively. These are the
bases related to the irreducible character bases by the same matrices of
character evaluations and inverse Koskta numbers that relate power sum and
monomial symmetric functions to Schur functions,

(2.5) $\displaystyle p_{\lambda}$
$\displaystyle=\sum_{\mu}\chi^{\mu}(\lambda)s_{\mu},$
$\displaystyle\qquad\psi^{\lambda}$
$\displaystyle=\sum_{\mu}\chi^{\mu}(\lambda)\chi^{\mu},$ $\displaystyle
m_{\lambda}$ $\displaystyle=\sum_{\mu}K_{\lambda,\mu}^{-1}s_{\mu},$
$\displaystyle\qquad\phi^{\lambda}$
$\displaystyle=\sum_{\mu}K_{\lambda,\mu}^{-1}\chi^{\mu},$

where $\chi^{\mu}(\lambda):=\chi^{\mu}(w)$ for any $w\in\mathfrak{S}_{n}$
having $\mathrm{ctype}(w)=\lambda$.

##  3\. Immanants and totally nonnegative polynomials

Each of the inequalities stated in Section 1 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
$p(x)\in\mathbb{C}[x]:=\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})$. While few
of the polynomial inequalities in Section 1 specifically mention the symmetric
group, all of them involve polynomials which are linear combinations of
monomials of the form
$\\{x_{1,w_{1}}\negthinspace\cdots{x}_{n,w_{n}}\,|\,w\in\mathfrak{S}_{n}\\}$.
Following [19], [31], we call such polynomials immanants. Specifically, given
$f:\mathfrak{S}_{n}\rightarrow\mathbb{C}$ define the _$f$ -immanant_ to be the
polynomial

(3.1)
$\mathrm{Imm}_{f}(x):=\sum_{w\in\mathfrak{S}_{n}}f(w)x_{1,w_{1}}\negthinspace\cdots{x}_{n,w_{n}}\in\mathbb{C}[x].$

The sign character ($w\mapsto(-1)^{\ell(w)}$) immanant and trivial character
($w\mapsto 1$) immanant are the determinant and permanent,

$\det(x)=\sum_{w\in\mathfrak{S}_{n}}(-1)^{\ell(w)}x_{1,w_{1}}\negthinspace\cdots{x}_{n,w_{n}},\qquad\mathrm{per}(x)=\sum_{w\in\mathfrak{S}_{n}}x_{1,w_{1}}\negthinspace\cdots{x}_{n,w_{n}}.$

Simple formulas for the induced sign and trivial character immanants are due
to Littlewood–Merris–Watkins [19], [22],

(3.2)
$\begin{gathered}\mathrm{Imm}_{\epsilon^{\lambda}}(x)=\negthickspace\negthickspace\negthickspace\sum_{(I_{1},\dotsc,I_{r})}\negthickspace\negthickspace\det(x_{I_{1},I_{1}})\cdots\det(x_{I_{r},I_{r}}),\\\
\mathrm{Imm}_{\eta^{\lambda}}(x)=\negthickspace\negthickspace\negthickspace\sum_{(I_{1},\dotsc,I_{r})}\negthickspace\negthickspace\mathrm{per}(x_{I_{1},I_{1}})\cdots\mathrm{per}(x_{I_{r},I_{r}}),\end{gathered}$

where $\lambda=(\lambda_{1},\dotsc,\lambda_{r})\vdash n$ and the sums are over
all sequences of pairwise disjoint subsets of $[n]$ satisfying
$|I_{j}|=\lambda_{j}$. Call such a sequence an ordered set partition of $[n]$
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.,
[20].) 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)$ 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.

The formula (3.2) makes it obvious that $\mathrm{Imm}_{\epsilon^{\lambda}}(x)$
and $\mathrm{Imm}_{\eta^{\lambda}}(x)$ are TNN polynomials for each partition
$\lambda\vdash n$. A stronger result [32, Cor. 3.3] asserts that irreducible
character immanants $\mathrm{Imm}_{\chi^{\lambda}}(x)$ are TNN as well. It is
clear that the $\mathfrak{S}_{n}$-trace immanants

$\\{\mathrm{Imm}_{\theta}(x)\,|\,\theta\in\mathcal{T}_{n},\mathrm{Imm}_{\theta}(x)\text{
is TNN }\\}$

form a cone, i.e., are closed under real nonnegative linear combinations.
Stembridge has conjectured [33, Conj. 2.1] that the extreme rays of this cone
are generated by the monomial trace immanants

(3.3) $\\{\mathrm{Imm}_{\phi^{\lambda}}(x)\,|\,\lambda\vdash n\\},$

and has shown [33, Prop. 2.3] that the cone of TNN $\mathfrak{S}_{n}$-trace
immanants lies inside of the cone generated by (3.3).

######  Proposition 3.1.

Each immanant of the form $\mathrm{Imm}_{\theta}(x)$ with
$\theta\in\mathcal{T}_{n}$ is a totally nonnegative polynomial only if it is
equal to a nonnegative linear combination of monomial trace immanants.

Thus it is conjectured that an $\mathfrak{S}_{n}$-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
extremal rays of the cone of TNN $\mathfrak{S}_{n}$-trace immanants [6,
Thm.1̇0.3]. (See Theorem 4.6.)

##  4\. The Temperley-Lieb algebra and 2-colorings

Given a complex number $\xi$, we define the 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

$\displaystyle t_{i}^{2}$ $\displaystyle=\xi t_{i},$ $\displaystyle\text{for
}i=1,\dotsc,n-1,$ $\displaystyle t_{i}t_{j}t_{i}$ $\displaystyle=t_{i},$
$\displaystyle\text{if }|i-j|=1,$ $\displaystyle t_{i}t_{j}$
$\displaystyle=t_{j}t_{i},$ $\displaystyle\text{if }|i-j|\geq 2.$

When $\xi=2$ we have the isomorphism
$T_{n}(2)\cong\mathbb{C}[\mathfrak{S}_{n}]/(1+s_{1}+s_{2}+s_{1}s_{2}+s_{2}s_{1}+s_{1}s_{2}s_{1})$.
(See e.g. [10], [12, Sec. 2.1, Sec. 2.11], [34, Sec. 7].) Specificallly, the
isomorphism is given by

(4.1) $\displaystyle\sigma:\mathbb{C}[\mathfrak{S}_{n}]$
$\displaystyle\rightarrow T_{n}(2),$ $\displaystyle s_{i}$
$\displaystyle\mapsto t_{i}-1.$

Let $\mathcal{B}_{n}$ be the multiplicative monoid generated by
$t_{1},\dotsc,t_{n-1}$ when $\xi=1$, also called the standard basis of
$T_{n}(\xi)$. It is known that $|\mathcal{B}_{n}|$ is the $n$th Catalan number
$C_{n}=\tfrac{1}{n+1}\tbinom{2n}{n}$. Diagrams of the basis elements of
$T_{n}(\xi)$, made popular by Kauffman [15, Sec. 4] are (undirected) graphs
with $2n$ vertices and $n$ edges. The identity and generators
$1,t_{1},\dotsc,t_{n-1}$ are represented by

, , , $\dotsc$, ,

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

, , , , , , , , , , , , , ,

and the equality $t_{3}t_{2}t_{3}t_{3}t_{1}=\xi t_{1}t_{3}$ in $T_{4}(\xi)$ is
represented by

(4.2) $\raisebox{-8.82036pt}{
\includegraphics[height=28.45274pt]{tl4_t1t2t1t1t3}}=\xi\raisebox{-8.82036pt}{
\includegraphics[height=28.45274pt]{tl4_t1t3},}$

with the ”bubble” becoming the scalar multiple $\xi$. We will identify each
element $\tau\in\mathcal{B}_{n}$ with its Kauffman diagram, and will label
vertices $v_{1},\dotsc,v_{n}$, clockwise from the lower left. We define the
height of a vertex by

$\mathrm{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}$

For instance, (4.4) shows the element
$t_{7}t_{6}t_{8}t_{5}t_{7}t_{4}t_{6}t_{5}t_{2}\in\mathcal{B}_{9}$ 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\mathcal{B}_{n}$, each edge
$(v_{i},v_{j})$ satisfies

(4.3)
$\mathrm{hgt}(v_{i})-\mathrm{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}$

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 (4.4) we have $\hat{\tau}$ to its right, and the decomposition of
this graph into four disjoint cycles.

(4.4) $\begin{gathered}\raisebox{-8.82036pt}{
{\includegraphics[height=170.71652pt]{tau.eps}}}\\\
\phantom{\sum}\tau\phantom{\sum}\end{gathered}\qquad\qquad\begin{gathered}\raisebox{-8.82036pt}{
\includegraphics[height=170.71652pt]{tauhat.eps}}\\\
\phantom{\sum}\hat{\tau}\phantom{\sum}\end{gathered}\qquad\qquad\begin{gathered}\raisebox{-8.82036pt}{
\includegraphics[height=170.71652pt]{tauhatcycles.eps}}\ .\\\
\phantom{\sum}\text{cycles of }\hat{\tau}\phantom{\sum}\end{gathered}$

The Temperley-Lieb algebra $T_{n}(2)$ sometimes arises in the $2$-coloring of
combinatorial objects. Define a principal coloring of $\tau\in\mathcal{B}_{n}$
to be a map
$\kappa:\mathrm{vertices}(\tau)\rightarrow\\{\mathrm{black},\mathrm{white}\\}$
which is a proper coloring of $\hat{\tau}$, i.e.,

$\displaystyle\text{color}(v_{i})$ $\displaystyle\neq\text{color}(v_{2n+1-i})$
$\displaystyle\text{for $i=1,\dotsc,n$},$ $\displaystyle\text{color}(v_{i})$
$\displaystyle\neq\text{color}(v_{j})$ $\displaystyle\text{if $v_{i}$ and
$v_{j}$ are adjacent in $\tau$}.$

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 (4.4),

$\raisebox{-8.82036pt}{
\includegraphics[height=85.35826pt]{tauhatonecycle.eps}}.$

######  Proposition 4.1.

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.

###### Proof.

This is clear if $n=1$. Assume that $n\geq 2$ 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 (4.3), for each such edge $(v_{j},v_{k})$ we have
that $\mathrm{hgt}(v_{j})-\mathrm{hgt}(v_{k})$ is even. Also by (4.3), since
$\mathrm{hgt}(v_{i+1})-\mathrm{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}$). ∎

It is easy to see that if $\kappa$ is a principal coloring of
$\tau\in\mathcal{B}_{n}$ and if $\hat{\tau}$ is a single cycle, then we have

(4.5) $|\\#(\text{white vertices on left of }(\tau,\kappa))-\\#(\text{white
vertices on right of }(\tau,\kappa))|=\begin{cases}0&\text{if $n$ even},\\\
1&\text{if $n$ odd}.\end{cases}$

In this situation we call $(\tau,\kappa)$ balanced if $n$ is even, and
unbalanced otherwise. More specifically, we call $(\tau,\kappa)$ left-
unbalanced (right-unbalanced) if it has more white vertices on the left
(right).

Now consider $\tau\in\mathcal{B}_{n}$ with $\hat{\tau}$ a disjoint union of
cycles $C_{1},\dotsc,C_{d}$, and $\kappa$ a principal coloring of $\tau$.
Define

(4.6) $\displaystyle\alpha$
$\displaystyle=\alpha(\tau,\kappa):=\\#\\{i\,|\,(\tau_{C_{i}},\kappa)\text{
right unbalanced}\\},$ $\displaystyle\beta$
$\displaystyle=\beta(\tau,\kappa):=\\#\\{i\,|\,(\tau_{C_{i}},\kappa)\text{
left unbalanced}\\}.$

For example, recall $\tau$ and $\hat{\tau}$ from (4.4). The proper
$2$-coloring $\kappa$ of $\hat{\tau}$,

$\raisebox{-8.82036pt}{
\includegraphics[height=170.71652pt]{tauhatcyclecolor.eps}},$

corresponds to a principal coloring of $\tau$ which 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$ (4.6) are
constant.

######  Lemma 4.2.

Let $(\tau,\kappa)$, $(\tau,\kappa^{\prime})$ be principal colorings with $j$
white vertices on the left, for some $j$, $0\leq
j\leq\lfloor\tfrac{n}{2}\rfloor$. Then we have

$\alpha(\tau,\kappa)=\alpha(\tau,\kappa^{\prime}),\qquad\beta(\tau,\kappa)=\beta(\tau,\kappa^{\prime}).$

###### Proof.

It is easy to see that the number of cycles of $\hat{\tau}$ of cardinality
$2~{}(\mathrm{mod}~{}4)$ is

(4.7)
$\alpha(\tau,\kappa)+\beta(\tau,\kappa)=\alpha(\tau,\kappa^{\prime})+\beta(\tau,\kappa^{\prime}).$

On the other hand, we have by assumption that the number of white vertices on
the right of $(\tau,\kappa)$ (or of $(\tau,\kappa^{\prime})$) minus the number
of white vertices on the left is

(4.8) $(n-j)-j=n-2j.$

Since each balanced subgraph $(\tau_{C_{i}},\kappa)$ (or
$(\tau_{C_{i}},\kappa^{\prime})$) 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 (4.5), we see that (4.8) equals

(4.9)
$\alpha(\tau,\kappa)-\beta(\tau,\kappa)=\alpha(\tau,\kappa^{\prime})-\beta(\tau,\kappa^{\prime}).$

Combining (4.7) and (4.9), we have the desired equalities. ∎

By this lemma, we may write

(4.10)
$\alpha(\tau,j):=\alpha(\tau,\kappa)\qquad(\beta(\tau,j):=\beta(\tau,\kappa))$

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

(4.11)
$\mathrm{span}_{\mathbb{R}}\\{\det(x_{I,I})\det(x_{I^{c},I^{c}})\,|\,I\subseteq[n]\\}$

of immanants. We define an immanant $\mathrm{Imm}_{\tau}(x)$ for each
$\tau\in\mathcal{B}_{n}$ in terms of the function

(4.12) $\displaystyle f_{\tau}:\mathbb{C}[\mathfrak{S}_{n}]$
$\displaystyle\rightarrow\mathbb{R}$ $\displaystyle w$
$\displaystyle\mapsto\text{ coefficient of $\tau$ in }\sigma(w),$

(extended linearly). To economize notation, we will write
$\mathrm{Imm}_{\tau}$ instead of $\mathrm{Imm}_{f_{\tau}}$,

$\mathrm{Imm}_{\tau}(x)=\sum_{w\in\mathfrak{S}_{n}}f_{\tau}(w)x_{1,w_{1}}\cdots
x_{n,w_{n}}.$

For example, consider the case $n=3$ and $\tau=t_{1}\in\mathcal{B}_{3}$.
Extracting the coefficients of $t_{1}$ in the expressions

$\begin{gathered}\sigma(e)=1,\qquad\sigma(s_{1})=t_{1}-1,\qquad\sigma(s_{2})=t_{2}-1,\\\
\sigma(s_{1}s_{2})=(t_{1}-1)(t_{2}-1)=t_{1}t_{2}-t_{1}-t_{2}+1,\\\
\sigma(s_{2}s_{1})=(t_{2}-1)(t_{1}-1)=t_{2}t_{1}-t_{1}-t_{2}+1,\\\
\sigma(s_{1}s_{2}s_{1})=(t_{1}-1)(t_{2}-1)(t_{1}-1)=t_{1}+t_{2}-t_{1}t_{2}-t_{2}t_{1}-1,\end{gathered}$

(where we have used $t_{1}t_{2}t_{1}=t_{1}$ and $t_{1}^{2}=2t_{1}$ to obtain
the last expression), we have $f_{t_{1}}(e)=0$, $f_{t_{1}}(s_{1})=1$,
$f_{t_{1}}(s_{2})=0$, $f_{t_{1}}(s_{1}s_{2})=-1$, $f_{t_{1}}(s_{2}s_{1})=-1$,
$f_{t_{1}}(s_{1}s_{2}s_{1})=1$, and

$\mathrm{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}.$

Note that in the special case $\tau=1$, the function $f_{\tau}$ maps a
permutation $w$ to $(-1)^{\textsc{inv}(w)}$. Thus the determinant is a
Temperley-Lieb immanant,

$\det(x)=\mathrm{Imm}_{1}(x).$

It was shown in [24] that Temperley-Lieb immanants are a basis of the space
(4.11), and that they are TNN. Furthermore, they are the extreme rays of the
cone of TNN immanants in this space [24, Thm. 10.3].

######  Proposition 4.3.

Each immanant of the form

(4.13) $\mathrm{Imm}_{f}(x)=\sum_{\begin{subarray}{c}I,J\subseteq[n]\\\
|I|=|J|\end{subarray}}c_{I,J}\det(x_{I,J})\det(x_{\overline{I},\overline{J}})$

is a totally nonnegative polynomial if and only if it is equal to a
nonnegative linear combination of Temperley-Lieb immanants.

In fact each complementary product of minors is a $0$-$1$ linear combination
of Temperley-Lieb immanants [24, Prop. 4.4].

######  Theorem 4.4.

For $I\subseteq[n]$ we have

(4.14)
$\det(x_{I,I})\det(x_{I^{c},I^{c}})=\sum_{\tau\in\mathcal{B}_{n}}b_{\tau}\mathrm{Imm}_{\tau}(x),$

where

(4.15) $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]\smallsetminus I\\}$ black},\\\
0&\text{otherwise.}\end{cases}$

By (3.2) we have that for each two-part partition $\lambda=(n-j,j)$ of $n$,
the corresponding induced sign character immanant belongs to (4.11).
Furthermore, we have the following explicit expansion of these in terms of the
Temperley-Lieb immanant basis.

######  Theorem 4.5.

For $j=0,\dotsc,\lfloor\tfrac{n}{2}\rfloor-1$, we have

$\mathrm{Imm}_{\epsilon^{n-j,j}}(x)=\sum_{\tau\in\mathcal{B}_{n}}d_{j,\tau}\mathrm{Imm}_{\tau}(x),$

where $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 (4.10).

###### Proof.

The combinatorial description follows immediately from Theorem 4.4. 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. ∎

Combining (2.3) and (3.2), we see that monomial immanants
$\mathrm{Imm}_{\phi^{\mu}}(x)$ indexed by partitions of the form
$\mu=2^{c}1^{d}\vdash n$ belong to the space (4.11) as well. To expand these
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\mathcal{B}_{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.

######  Theorem 4.6.

For $\mu=2^{c}1^{d}\vdash n$, we have that $\mathrm{Imm}_{\phi^{\mu}}(x)$ is a
totally nonnegative polynomial. In particular we have

$\mathrm{Imm}_{\phi^{\mu}}(x)=\sum_{\tau\in
P(\mu)}b_{\mu,\tau}\mathrm{Imm}_{\tau}(x),$

where $b_{\mu,\tau}=2^{\\#\text{cycles of }\hat{\tau}\text{ of cardinality
}0~{}(\text{mod }4)}$.

###### Proof.

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 [6, Thm. 10.3], the coefficient $b_{\mu,\tau}$ is the number
of path families covering $G$ which satisfy

  1. (1)

$c+d$ pairwise nonintersecting paths are colored white,

  2. (2)

$c$ pairwise nonintersecting paths are colored black,

assuming no path family covering $G$ can be colored so that $c+d+1$
nonintersecting paths are colored white. It is straightforward to show [28,
Prop. 2.1] 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^{\prime})$ 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^{\prime})$ 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 Theorem 4.5
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. ∎

##  5\. Main results

Fischer’s inequalities (1.5) naturally lead to the questions of how products

(5.1) $\det(A_{I,I})\det(A_{I^{c},I^{c}})$

of complementary pairs of minors compare to one another, and of whether a
greater cardinality difference $|I^{c}|-|I|$ tends to make the product (5.1)
greater or smaller. This second question led Barrett and Johnson [1] to
consider the average value of such products when cardinalities are fixed,

(5.2) $\frac{1}{\binom{n}{k}}\sum_{\begin{subarray}{c}I\subseteq[n]\\\
|I|=k\end{subarray}}\det(A_{I,I})\det(A_{I^{c},I^{c}}).$

They found that for PSD matrices, a smaller cardinality difference makes the
average product of minors greater [1, Thm. 1]. We give two proofs that the
same is true for TNN matrices.

######  Theorem 5.1.

For all TNN matrices A and for $k=0,\dotsc,\lfloor\tfrac{n}{2}\rfloor-1,$ we
have

(5.3)
$\frac{\displaystyle{\sum}_{|I|=k}\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k}}}\leq\frac{\displaystyle{\sum}_{|I|=k+1}\det(A_{I,I})\det(A_{I^{c},I^{c}})}{\displaystyle{\binom{n}{k+1}}}.$

###### First proof.

By (3.2) it is equivalent to show that the polynomial

(5.4)
$\frac{\mathrm{Imm}_{\epsilon^{n-k-1,k+1}}(x)}{\displaystyle{\binom{n}{k+1}}}-\frac{\mathrm{Imm}_{\epsilon^{n-k,k}}(x)}{\displaystyle{\binom{n}{k}}}$

is totally nonnegative. By Theorem 4.5, this difference belongs to the span of
the Temperley-Lieb immanants. In particular, we may multiply the difference by
$n!/(k!(n-k-1)!)$ to obtain

(5.5)
$(k+1)\mathrm{Imm}_{\epsilon^{n-k-1,k+1}}(x)-(n-k)\mathrm{Imm}_{\epsilon^{n-k,k}}(x)=\sum_{\tau\in\mathcal{B}_{n}}c_{\tau}\mathrm{Imm}_{\tau}(x),$

where

(5.6) $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 Theorem 4.5

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 4.10.

Let $d$ be the number of cycles defined as in Theorem 4.5. Then by Theorem 4.5
we have that (5.6) equals

(5.7) $\displaystyle(k+1)d_{k+1,\tau}-(n-k)d_{k,\tau}$
$\displaystyle=(k+1)2^{d-\alpha-\beta}\binom{\alpha+\beta}{\alpha-1}-(n-k)2^{d-\alpha-\beta}\binom{\alpha+\beta}{\alpha}$
$\displaystyle=2^{d-\alpha-\beta}\left((k+1)\binom{\alpha+\beta}{\alpha-1}-(n-k)\binom{\alpha+\beta}{\alpha}\right)$
$\displaystyle=2^{d-\alpha-\beta}\frac{(\alpha+\beta)!}{(\alpha-1)!\beta!}\left(\frac{k+1}{\beta+1}-\frac{n-k}{\alpha}\right).$

Then substituting $\alpha=n-2k+\beta$ (see formula 4.8), the final difference
of fractions (5.7) becomes

$\frac{(k+1)(n-2k+\beta)-(n-k)(\beta+1)}{(\beta+1)(n-2k+\beta)}.$

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$. ∎

###### Second proof.

Again we show that the polynomial (5.4) is TNN. Multiplying the polynomial by
$\tfrac{n!}{k!(n-k-1)!}$ and expanding it in the monomial immanant basis of
the trace immanant space, we have

(5.8)
$(n-k)\mathrm{Imm}_{\epsilon^{(k,n-k)}}(x)-(k+1)\mathrm{Imm}_{\epsilon^{(k+1,n-k-1)}}(x)=\sum_{\mu\vdash
n}c_{\mu}\mathrm{Imm}_{\phi^{\mu}}(x)$

where the integers $\\{c_{\mu}\,|\,\mu\vdash n\\}$ satisfy

(5.9) $(n-k)e_{(k,n-k)}-(k+1)e_{(k+1,n-k-1)}=\sum_{\mu\vdash
n}c_{\mu}m_{\mu}.$

We claim that $c_{\mu}\geq 0$ for all relevant partitions $\mu$. To see this,
consider the special case of (2.3) for two-part partitions,

$e_{(k,n-k)}=\sum_{a=0}^{n-k}M_{(k,n-k),2^{a}1^{n-2a}}m_{2^{a}1^{n-2a}}.$

It follows that each partition $\mu$ appearing with nonzero coefficient in
(5.8) has the form $\mu=2^{a}1^{n-2a}$.

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 (5.9), the coefficient of $m_{2^{a}1^{n-2a}}$
is

$c_{2^{a}1^{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}$

This last expression is equal to

$\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{)},$

which is positive, since $a<n-k\leq\lfloor\tfrac{n}{2}\rfloor\leq k\leq n$.

Now by Theorem 4.6 we have that (5.8) is a totally nonnegative polynomial, and
that (5.4) is as well. ∎

Consideration of the average value of products of two complentary minors (5.2)
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$,

(5.10)
$\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}}),$

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 [1, Thm. 2]. We show that the same is true for TNN
matrices.

######  Theorem 5.2.

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

(5.11)
$\lambda_{1}!\cdots\lambda_{r}!\negthickspace\negthickspace\sum_{(I_{1},\dotsc,I_{r})}\negthickspace\negthickspace\det(A_{I_{1},I_{1}})\cdots\det(A_{I_{r},I_{r}})~{}\geq~{}\mu_{1}!\cdots\mu_{s}!\negthickspace\negthickspace\sum_{(J_{1},\dotsc,J_{s})}\negthickspace\negthickspace\det(A_{J_{1},J_{1}})\cdots\det(A_{J_{s},J_{s}}),$

###### Proof.

By (2.2) it suffices to consider $\lambda$, $\mu$ having equal parts except

$\mu_{i}=\lambda_{i}+1,\qquad\mu_{j}=\lambda_{j}-1$

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 Theorem 5.1, we observe that each sum of products of
minors is an induced sign character immanant (3.2). Thus the inequality (5.11)
is equivalent to the total nonnegativity of the polynomial

(5.12)
$\lambda_{1}!\cdots\lambda_{r}!\;\mathrm{Imm}_{\epsilon^{\lambda}}(x)-\mu_{1}!\cdots\mu_{r}!\;\mathrm{Imm}_{\epsilon^{\mu}}(x).$

Dividing this by $\nu_{1}!\cdots\nu_{r-2}!\lambda_{i}!\mu_{j}!$ and collecting
terms, we obtain

$\begin{gathered}\lambda_{j}\negthickspace\sum_{\begin{subarray}{c}J\subseteq[n]\\\
|J|=|\nu|\end{subarray}}\negthickspace\mathrm{Imm}_{\epsilon^{\nu}}(x_{J,J})\mathrm{Imm}_{\epsilon^{(\lambda_{i},\lambda_{j})}}(x_{J^{c},J^{c}})-\mu_{i}\negthickspace\sum_{\begin{subarray}{c}J\subseteq[n]\\\
|J|=|\nu|\end{subarray}}\negthickspace\mathrm{Imm}_{\epsilon^{\nu}}(x_{J,J})\mathrm{Imm}_{\epsilon^{(\lambda_{i}+1,\lambda_{j}-1)}}(x_{J^{c},J^{c}})\\\
=\negthickspace\sum_{\begin{subarray}{c}J\subseteq[n]\\\
|J|=|\nu|\end{subarray}}\mathrm{Imm}_{\epsilon^{\nu}}(x_{J,J})\left(\lambda_{j}\mathrm{Imm}_{\epsilon^{(\lambda_{i},\lambda_{j})}}(x_{J^{c},J^{c}})-\mu_{i}\mathrm{Imm}_{\epsilon^{(\lambda_{i}+1,\lambda_{j}-1)}}(x_{J^{c},J^{c}})\right).\end{gathered}$

By Theorem 5.1, or more precisely (5.5), this polynomial is TNN and so is
(5.12). ∎

It would be interesting to extend the Barrett–Johnson inequalities (1.16) to
all HPSD matrices, and to state a permanental analog as originally suggested
in [1]. Using (3.2) we may state these problems as follows.

######  Problem 5.3.

Characterize the pairs $(\lambda,\mu)$ of partitions of $n$ for which we have

  1. (1)

$\lambda_{1}!\cdots\lambda_{r}!\;\mathrm{Imm}_{\epsilon^{\lambda}}(A)\leq\mu_{1}!\cdots\mu_{r}!\;\mathrm{Imm}_{\epsilon^{\mu}}(A)$
for all $A$ HPSD,

  2. (2)

$\lambda_{1}!\cdots\lambda_{r}!\;\mathrm{Imm}_{\eta^{\lambda}}(A)\geq\mu_{1}!\cdots\mu_{r}!\;\mathrm{Imm}_{\eta^{\mu}}(A)$
for all $A$ HPSD or PSD,

  3. (3)

$\lambda_{1}!\cdots\lambda_{r}!\;\mathrm{Imm}_{\eta^{\lambda}}(A)\geq\mu_{1}!\cdots\mu_{r}!\;\mathrm{Imm}_{\eta^{\mu}}(A)$
for all $A$ TNN.

##  6\. Acknowledgements

The authors are grateful to Shaun Fallat and Misha Gekhtman for helpful
conversations.

## References

  * [1] W. W. Barrett and C. R. Johnson.  Majorization monotonicity of symmetrized Fischer products.  Linear and Multilinear Algebra, 34, 1 (1993) pp. 67–74.
  * [2] R. Bhatia.  Positive definite matrices.  Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ (2007).
  * [3] A. Björner and F. Brenti.  Combinatorics of Coxeter groups, vol. 231 of Graduate Texts in Mathmatics.  Springer, New York (2005).
  * [4] J. Borcea and P. Brändén.  Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products.  Duke Math. J., 143, 2 (2008) pp. 205–223.
  * [5] D. Carlson.  Weakly sign-symmetric matrices and some determinantal inequalities.  In Colloquium Mathematicum, vol. 17. Institute of Mathematics Polish Academy of Sciences (1967), pp. 123–129.
  * [6] S. Clearman, M. Hyatt, B. Shelton, and M. Skandera.  Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements.  Electron. J. Combin., 23, 2 (2016).  Paper 2.7, 56 pages.
  * [7] B. Drake, S. Gerrish, and M. Skandera.  Two new criteria for comparison in the Bruhat order.  Electron. J. Combin., 11, 1 (2004).  Note 6, 4 pp. (electronic).
  * [8] S. Fallat and C. Johnson.  Totally Nonnegative Matrices.  Princeton Series in Applied Mathematics. Princeton University Press (2011).
  * [9] S. M. Fallat, M. I. Gekhtman, and C. R. Johnson.  Multiplicative principal-minor inequalities for totally nonnegative matrices.  Adv. Appl. Math., 30, 3 (2003) pp. 442–470.
  * [10] K. Fan and R. M. Green.  Monomials and Temperley-Lieb algebras.  J. Algebra, 190 (1997) pp. 498–517.
  * [11] E. Fischer.  Über den Hadamardschen Determinantensatz.  Arch. Math. (Basel), 13 (1908) pp. 32–40.
  * [12] F. M. Goodman, P. de la Harpe, and V. Jones.  Coxeter Graphs and Towers of Algebras.  Springer–Verlag, New York (1989).
  * [13] J. Hadamard.  Resolution d’une question relative aux determinants.  Bull. des sciences math., 2 (1893) pp. 240–246.
  * [14] P. Heyfron.  Immanant dominance orderings for hook partitions.  Linear and Multilinear Algebra, 24, 1 (1988) pp. 65–78.
  * [15] L. Kauffman.  State models and the Jones polynomial.  Topology, 26, 3 (1987) pp. 395–407.
  * [16] D. M. Koteljanskiĭ.  A property of sign-symmetric matrices.  Amer. Math. Soc. Transl. (2), 27 (1963) pp. 19–23.
  * [17] D. M. Kotelyanskiĭ.  On a property of sign-symmetric matrices.  Uspehi Matem. Nauk (N.S.), 8, 4(56) (1953) pp. 163–167.
  * [18] E. H. Lieb.  Proofs of some conjectures on permanents.  J. Math. Mech., 16 (1966) pp. 127–134.
  * [19] D. E. Littlewood.  The Theory of Group Characters and Matrix Representations of Groups.  Oxford University Press, New York (1940).
  * [20] G. Lusztig.  Total positivity and canonical bases.  In Algebraic groups and Lie groups, vol. 9 of Austral. Math. Soc. Lect. Ser. Cambridge Univ. Press, Cambridge (1997), pp. 281–295.
  * [21] M. Marcus.  The permanent analogue of the hadamard determinant theorem.  Bulletin of the American Mathematical Society, 69, 4 (1963) pp. 494–496.
  * [22] R. Merris and W. Watkins.  Inequalities and identities for generalized matrix functions.  Linear Algebra Appl., 64 (1985) pp. 223–242.
  * [23] T. H. Pate.  Tensor inequalities, $\xi$-functions and inequalities involving immanants.  Linear Algebra Appl., 295, 1-3 (1999) pp. 31–59.
  * [24] B. Rhoades and M. Skandera.  Temperley-Lieb immanants.  Ann. Comb., 9, 4 (2005) pp. 451–494.
  * [25] B. Rhoades and M. Skandera.  Kazhdan-Lusztig immanants and products of matrix minors.  J. Algebra, 304, 2 (2006) pp. 793–811.
  * [26] C. R. J. Roger A. Horn.  Matrix Analysis.  Cambridge University Press, 2nd ed. (2013).
  * [27] I. Schur.  Über endliche Gruppen und Hermitesche Formen.  Math. Z., 1, 2-3 (1918) pp. 184–207.
  * [28] M. Skandera.  Inequalities in products of minors of totally nonnegative matrices.  J. Algebraic Combin., 20, 2 (2004) pp. 195–211.
  * [29] D. Soskin and M. Gekhtman.  On bounded ratios of minors of totally positive matrices.  arXiv preprint arXiv:2204.11962 (2022).
  * [30] R. Stanley.  Enumerative Combinatorics, vol. 2.  Cambridge University Press, Cambridge (1999).
  * [31] R. Stanley.  Positivity problems and conjectures.  In Mathematics: Frontiers and Perspectives (V. Arnold, M. Atiyah, P. Lax, and B. Mazur, eds.). American Mathematical Society, Providence, RI (2000), pp. 295–319.
  * [32] J. Stembridge.  Immanants of totally positive matrices are nonnegative.  Bull. London Math. Soc., 23 (1991) pp. 422–428.
  * [33] J. Stembridge.  Some conjectures for immanants.  Canad. J. Math., 44, 5 (1992) pp. 1079–1099.
  * [34] B. W. Westbury.  The representation theory of the Temperley-Lieb algebras.  Math. Z., 219 (1995) pp. 539–565.


# FedLE: Federated Learning Client Selection with Lifespan Extension for Edge
IoT Networks

Jiajun Wu  Electrical and Software Engineering
University of Calgary
Calgary, Canada
<EMAIL_ADDRESS>Steve Drew  Electrical and Software Engineering
University of Calgary
Calgary, Canada
<EMAIL_ADDRESS>Jiayu Zhou  Computer Science and Engineering
Michigan State University
East Lansing, USA
<EMAIL_ADDRESS>
###### Abstract

Federated learning (FL) is a distributed and privacy-preserving learning
framework for predictive modeling with massive data generated at the edge by
Internet of Things (IoT) devices. One major challenge preventing the wide
adoption of FL in IoT is the pervasive power supply constraints of IoT devices
due to the intensive energy consumption of battery-powered clients for local
training and model updates. Low battery levels of clients eventually lead to
their early dropouts from edge networks, loss of training data jeopardizing
the performance of FL, and their availability to perform other designated
tasks. In this paper, we propose FedLE, an energy-efficient client selection
framework that enables lifespan extension of edge IoT networks. In FedLE, the
clients first run for a minimum epoch to generate their local model update.
The models are partially uploaded to the server for calculating similarities
between each pair of clients. Clustering is performed against these client
pairs to identify those with similar model distributions. In each round, low-
powered clients have a lower probability of being selected, delaying the
draining of their batteries. Empirical studies show that FedLE outperforms
baselines on benchmark datasets and lasts more training rounds than FedAvg
with battery power constraints.

###### Index Terms:

Federated Learning, Client Selection, Edge Computing, Internet of Things
(IoT), Energy Efficiency

##  I Introduction

The pervasive deployment of Internet of Things (IoT) devices has resulted in
large-scale personal data generated at the network edge [1]. The edge-based
IoT data cannot be uploaded to a centralized server for machine learning due
to privacy concerns and resource limitations. Federated learning (FL) allows
distributed clients to collaboratively learn a model without uploading their
local training data, providing an ideal solution for privacy-privacy
distributed learning in edge computing. In reality, challenges exist for
effective FL, as IoT networks are largely battery-powered and heterogeneous,
with diversified battery capacities and potentially short lifespans. What
makes the problem worse is that IoT devices consume a significant amount of
energy during the training process of FL. A portion of devices would deplete
their energy earlier than others and drop out of the network. These dropouts
reduce the number of available clients, which in turn limits access to the
training data. With the vanilla FedAvg [2] performing client selection
uniformly at random, the heterogeneous energy profile and status of clients
are not considered. A critical client with low remaining energy has an equal
probability of being selected compared to a non-critical client for a new
round of data aggregation. These facts may lead to early drops of critical
clients, overall lower network availability, and consequently, poor model
performance and longer convergence time.

Due to the potential loss of critical clients, client selection becomes a
major concern. Existing studies primarily focused on optimizing energy
efficiency with bandwidth allocation in wireless networks. Yu et al. [3]
investigated the tradeoffs between maximizing the number of selected clients
and minimizing total energy consumption, and selecting clients with an
optimized allocation of CPU resources for FL local training and transmission
power for model updates. The impact on learning performance with varying
temporal client selection patterns was discussed by [4]. A stochastic
optimization problem was then formulated for joint bandwidth allocation and
client selection with a long performance guarantee. FedMCCS [5] aimed to
maximize the number of clients selected each round while considering client
resource budgets and capabilities, such as CPU, memory, and energy. Although
the client selection rate and test accuracy have been improved in certain
scenarios, existing studies did not factor in an unreliable edge computing
environment to maximize the lifespan of the entire edge networks with more
available clients.

In this paper, we propose FedLE, a clustering-based client selection method
for FL that accelerates training for heterogeneous data. The intuition of
FedLE is from model similarity, where clients with similar data tend to
provide similar models during FL. Therefore, a sampling strategy that
prioritizes the selection of clients with very different models can be an
energy-efficient approximation to cut down potentially redundant model uploads
and thus accelerate the learning processing of FL. With that in mind, FedLE
forms clusters based on clients’ local model weights following the steps shown
in Fig. 1, where the server computes similarity matrices of client model
weights and clusters the clients. The probability of a client being selected
will depend on the size of its cluster. With this approach, we are not
compromising client privacy, directly accessing client data, or acquiring new
information from the clients. Compared to existing studies, FedLE has the
following contributions:

  * •

FedLE balances the energy consumption and makes all clients last longer. To
our knowledge, this is the first work considering edge network lifespan
extension for FL.

  * •

Our proposed method uses partial model layers to build the similarity matrix
for clustering, which proves to be far more energy-efficient than using full
models.

  * •

We demonstrate through empirical studies that in most cases, the creation of
similarity matrix and clustering only needs to be performed once, therefore
only adding a small overhead while still outperforming baseline methods.

Figure 1: Overview of the FedLE client selection framework. 1) Before the
initial training round, all clients run for a minimum epoch and upload partial
model weights to the server. 2) Server computes the similarity matrices. 3)
Represent every client by comparing each with the lowest similarity pair in
the weight space. 4) Cluster the clients based on their weights. 5)
Dynamically set chances of selection based on the cluster size.

##  II Related Work

FedAvg [2] demonstrated that random client selection is effective when all
clients are available and adequately trained. To improve the performance of FL
with heterogeneous data, FedProx was proposed [6], introducing a proximal term
to restrict the local updates to be closer to the global model.

_Energy-efficient client selection_ has become one of the popular topics in
FL. The power-of-choice [7] client selection framework prioritized
communication and computation efficiency. Nishio and Yonetani [8] proposed a
client selection protocol for FL called FedCS that accounts for both energy
resources and heterogeneous data in mobile edge computing (MEC) environments.
While existing methods have improved energy efficiency in certain scenarios,
they did not consider extending the lifespan of edge and IoT networks to
balance the energy consumption of the clients. In comparison, our proposed
FedLE framework takes into account the total number of rounds for FL in an
attempt to extend the effective lifespan of the entire edge network to retain
the data sources and to help perform the primary tasks of the IoT devices. In
FedSim [9], pairwise client similarity was used for clustering as well, but it
made full use of the local model parameters of the client and took clustering
as a post-FL processing technique. As part of our proposed method, we utilize
only partial local model parameters in a one-time manner for client selection.
Wang et al. [10] proposed an FL scheme that removed ineffective models using
cosine similarity that clusters devices by vectorizing local and global model
parameters. It also required the full model parameters and did not take energy
into account. Our proposed method simply computes similarity using local model
parameters and requires less computation and communication power.

##  III The FedLE Client Selection Framework

In this section, we introduce the FedLE client section framework with the
problem formulation.

###  III-A Constrained battery power

We first define an edge-based FL scenario with a set of battery-powered
clients $\mathbb{C}$, where $\left|\mathbb{C}\right|=K$. All clients
communicate with an aggregation server $S$. We use the communication rounds in
FL to represent the current time in the system. Specifically, for the $k$th
client $c_{k}\in\mathbb{C}$, define its battery level as the remaining battery
power at Round $t$ for active use, denoted by $b_{t}^{k}\in[0,1]$, where $0$
stands for completely drained battery, and $1$ for a fully charged battery. As
long as a client is turned on, sitting idle will consume the device’s battery.
We define the standby battery discharge rate of $c_{k}$ as the amount of
$b_{t}^{k}$ dropped in each epoch of FL training time, denoted by $r_{t}^{k}$.
For the clients selected for model updates, transmission to the server will
result in additional consumption of the battery. We define the battery
discharge caused by each model update transmission to be $s_{t}^{k}$. For any
battery discharge resulting from other communications, we denote the amount as
$a_{t}^{k}$ for $c_{k}$. The total level at Round $t+1$ for $c_{k}$ will be:

$\displaystyle b_{t+1}^{k}=b_{t}^{k}-r_{t}^{k}-s_{t}^{k}-a_{t}^{k}.$

Edge devices typically have their primary tasks besides FL. Instead of
allowing the FL process to completely drain the device battery, we set a
critical battery level $\delta$. If the client battery level is lower than
$\delta$, the FL process will halt to allow the edge IoT device to complete
its primary tasks.

###  III-B Selecting statistically diverse clients

In FL, large numbers of clients can carry highly similar data in distribution.
Typical examples include IoT sensors in industrial environments with close
proximity, surveillance cameras on the same street, and smartphones of users
with matching preferences. It is necessary to avoid selecting such clients in
consecutive rounds during the FL process. When a majority of clients share
data with similar distributions, the training results would likely lead to
overfitting to the majority class. On the other hand, the energy constraints
of the clients limit their total rounds of training: the rounds of the clients
with limited remaining energy are numbered. Therefore, the opportunity to
participate in training is valuable. It is important to select clients with
diverse data distribution that boosts the convergence of the global model. We
plan to compare the local model weights of each client to form a similarity
matrix and cluster the clients based on their weight.

Algorithm 1 The Algorithm Building the Similarity Matrix

1:if initial round then

2: for each client $c_{k}\in\mathbb{C}$ do

3: locally train client $c_{k}$ for 1 epoch

4: $c_{k}$ sends model updates $w_{k}$ to the server

5: Server flattens partial $w_{k}$

6: end for

7: Server compares the dot products for each pair of the $K$ clients to build
a $K\times K$ similarity matrix

8: Server sums up the value for each row in the $K\times K$ matrix into a one-
dimension list of size $K$

9:end if

###  III-C Efficiently building the similarity matrix

The major challenges of building a similarity matrix in practice include the
overhead introduced by comparing every two of the $K$ clients for their
gradients. A total of $\binom{K}{2}/2$ comparisons of full model updates are
required for creating the similarity matrix. Although this process is
completed on the server side, it introduces significant computational cost and
latency. The problem worsens when $K$ and the model gradient matrix are large.
To address these challenges in building the similarity matrix, we partially
load model parameters to the server when updating the matrix. Based on our
observations, there is a significant difference between the local client
models in terms of model weights and bias, particularly in the first and last
layers of a convolutional neural network (CNN) model. Therefore, instead of
using the entire model to formulate the matrix, we only use the model
parameters of the first convolution layer and the last fully connected layer.
Suppose after trimming the model, for each gradient matrix of $c_{k}$, we have
a $D\times D$ gradient matrix.

To prove the effectiveness of using partial models, we design an experiment to
show the cosine similarity of each client using partial model parameters in
the FL process. In FedAvg setting, we train a CNN model with MNIST [11] for a
total of 30 rounds and CIFAR-10 [12] dataset for a total of 20 rounds, each
with 15 clients. Every round, each client computes the cosine similarity
between its local model weights and all other clients to get $k$ cosine
similarity values. We then formulate a $K\times K$ matrix where each cell
corresponds to the similarity scores of the two clients, calculated as below:

$sim(c_{i},c_{j})=\mathbf{w_{i}}\cdot\mathbf{w_{j}}=\sum_{d_{i}=1}^{D}\sum_{d_{j}=1}^{D}w_{i}^{d_{i}}w_{j}^{d_{j}},$
(1)

where $\mathbf{w_{i}}$ and $\mathbf{w_{j}}$ are the gradient matrices of
client $c_{i}$ and $c_{j}$, respectively. The variables $w_{i}^{d_{i}}$ and
$w_{j}^{d_{j}}$ represent the cell values in the gradients of $\mathbf{w_{i}}$
and $\mathbf{w_{j}}$. Applying Equation (1), we visualize the similarity
matrix in the format of heatmaps for all the matrices in each round with full
and partial weights. The results are shown in Fig. 2.

####  III-C1 The importance of the initial similarity matrix

By observing the heatmaps from Fig. 2, there is no significant change in the
pattern. We also learn that as the number of rounds increases, the pattern of
the similarity matrix remains relatively stable. There is no significant
difference between the consecutive matrices and even latter matrices. We
believe this is because the distribution of local data on each client is often
stable and not likely to change dramatically. It is evident from this
experiment that the use of the similarity matrix is valid and the matrix does
not need to be updated frequently.

Figure 2: The similarity matrix using full model weights. (Top row: CNN
model’s initial round and final round matrix. Bottom row: MLP model’s initial
round and final round matrix.)

####  III-C2 Robustness with different levels of non-IIDness and imbalanced
data

We design a simple experiment to test the robustness of the similarity matrix
using data with different levels of heterogeneity and imbalanced classes. For
the clarity of demonstration, we design two levels of heterogeneity. For MNIST
with CNN, MNIST with Multi-layer Perceptron (MLP), and CIFAR-10 with the CNN
models, we used 40 clients and assign each client only 2 and 3 classes with
50% clients sharing data from the same class. The weight-space graph in Fig. 3
shows that regardless of the level of data heterogeneity, their clustering
pattern is clear.

Figure 3: FedLE in different levels of heterogeneity using CNN and MLP. First
row: CNN model using CIFAR-10 with each client containing 2 and 3 classes of
data. Second row: CNN model using MNIST with each client containing 2 and 3
classes of data. Third row: MLP model using MNIST with each client containing
2 and 3 classes of data.

Given the information, we are convinced that the building process of the
similarity matrix can be a one-time procedure. Therefore, the communication
cost from the clients to the server in building the similarity matrix is
substantially reduced by the limited number of creating and updating the
matrix and by the reduced size of model parameters. With each round of
training, client selection is based on the matrix and its clusters. We can
select clients with more diverse data in a single round which contribute more
to the global model.

Depending on how frequently and how much the data on each client changes,
reconstruction of the matrix is likely necessary. If the client data is
dynamic and constantly changing then there is a need for updating the weight
matrix. However, this is not the focal point of this paper.

###  III-D Forming the clusters

The clustering operation takes place only once during the entire training
process in order to maximize energy efficiency. All clients will perform one
epoch of local training prior to uploading their local model updates. Each
client’s weight is compared with the weights of all other clients based on the
local model weights. After the similarity matrix is built, FedLE picks the
lowest $N_{s}$ similarity value from the matrix. The motivation behind picking
the clients with the lowest similarity for clustering is to locate the clients
with higher diversity and to avoid repeatedly selecting clients with lower
similarity. In our experiments, we pick the lowest similarity value for
analysis, which links to a pair of clients $c_{\alpha}$ and $c_{\beta}$. These
two clients are considered the farthest from each other. Every other client
would have a similarity score in between. To tackle the overfitting problem on
the majority of clients with similar data, we set different probabilities for
every cluster based on their size. For the cluster with the most clients, we
categorize that cluster as the majority cluster. The majority cluster has a
much lower chance of being selected. The rest of the clusters have an equal
probability of being selected. This way the clusters that carry statistically
similar data would have a lower chance of being selected. Clusters with fewer
clients will have a higher chance of being selected for training.

###  III-E Proposed FedLE Client Selection Method

In this section, we propose a novel client selection method based on gradient
similarity for FL to optimize training in an energy restraint scenario. We
introduce two baseline methods and one optimized method. Based on our
discussions in Section III-B, in FedLE, we only partially load model
parameters to the server when updating the matrix. There is a significant
difference between the local client models in terms of model weights and bias,
particularly in the first and last layers of the CNN model. Instead of using
the entire model to formulate the matrix, we only use the model parameters of
the first convolution layer and the last fully connected layer.

Algorithm 2 The FedLE algorithm. K is the number of participating clients. C
$\in$ (0,1] is a hyperparameter that indicates the fraction of clients
participating in each round of FL training.

1:Initialization: Server sends global model to all clients.

2:Constructing Similarity Matrix: See Algorithm 1.

3:K-means Clustering: Server uses K-means clustering to cluster every client
based on their pairwise similarity.

4:Client Selection: Server selects K$\times$C clients based on the cluster
size.

5:Distribution: Server distributes the newest global model to selected clients
this round.

6:Update and Upload: Selected clients update their local model parameter after
local training using the global model and local data.

7:Aggregation: Server averages uploaded parameters and aggregates into the new
global model for the next round.

8:All steps from Client Selection repeat until the model achieves the desired
result.

##  IV SIMULATION SETUP

In this section, we evaluate FedLE in a simulated energy-restraint environment
by comparing FedLE with two baseline methods FedBO and FedAvg-B, using MNIST
and CIFAR-10.

###  IV-A Baseline Methods

The first baseline approach is FedAvg with the consideration of battery
constraints, named FedAvg-B. In this baseline method, client selection follows
a uniformly random method, the same as FedAvg, but only adding the battery
level constraints to all clients. Clients with a battery level below the
critical power level $\delta$ will be dropped during training.

The second baseline approach is named Battery-Only (FedBO). In FedBO, the
client selection prioritizes clients with high battery levels. FedBO
calculates each client’s maximum training capacity based on their initial
battery level. The probability of selecting each client is then generated
based on its maximum capability. Essentially, low-powered clients have a lower
chance of being selected than high-powered clients.

For our Battery-Optimized approach, prior to training, all available clients
do local training for 1 epoch using their local data and upload part of the
local model parameters to the server. The central server computes the
similarity matrix and uses K-mean clustering. The new matrix will be used for
client selection. We select clients based on the following criteria:

  * •

FedLE gives a higher probability to clusters with fewer clients and a lower
probability to those with more clients.

  * •

In each cluster, clients with higher battery levels have higher probabilities
of being selected to optimize energy

###  IV-B Simulated Environment

Consider a typical FL scenario with $K$ clients and a central server. Each
client trains its local data based on the global model maintained by the
server. We simulate an energy-constrained FL environment with imbalanced
classes using the following variables. The training and communication costs
are reflected in the remaining battery levels of the clients. The battery
level b of each client determines when the client would be excluded from FL
training. Battery discharge r applies to all clients after each round even if
the client is not selected for training. Any other communication from clients
to the server has additional communication cost a.

Every client is initialized with battery level B. Low-power clients have
$b\in[0.245,0.265]$, and high-power clients have $b\in[0.895,0.905]$. We
initialize 50% of clients as low-powered clients and the other 50% of clients
as high-powered clients. When a client’s battery level $b\leq\delta$, where
$\delta=0.2$, it will be considered to have reached the critical level of the
battery and will be excluded from any further training. All clients have a
battery standby cost $r\in[0.1,0.15]$. We also set the additional battery
costs $s\in[0.4,0.5]$ and the additional communication costs
$a\in[0.24,0.25]$. In the simulated environment, we assume that all clients
have the same amount of data and computational power. There are 50% clients
assigned data points from the same class, creating an imbalanced class
scenario. We also establish an early-stopping point for the experiment. When
50% of the clients have their battery level below $\delta$, the entire FL
training process stops.

###  IV-C Non-IID & imbalanced data and Global models

We adopt both CNN and MLP models in the evaluation. The same setting is used
in the FL environment for all three methods for comparison. The FL settings
for MNIST and CIFAR-10 are listed below and are according to the definitions
in [2]. We use $K=40$ and $C=0.05$, which comes to exactly 2 clients per round
of training. To create a simulated environment for non-IID FL and imbalanced
classes, we divide the MNIST training set into 20 shards of size 3000 and the
CIFAR-10 training set into 80 shards of size 625. Then we assign the first 20
clients with one shard each and the other 20 clients to the same class.

##  V Performance Evaluation

In this section, we evaluate the performance of FedLE with two other baseline
methods from Section IV.

###  V-A Test Accuracy

As shown in Fig. 4, FedLE with a CNN model outperforms the other two baselines
in test accuracy by a wide margin (around 10%). A side-by-side comparison
shows that FedLE works well when clients have non-IID data and imbalanced
classes. The result shows that optimizing the client selection alone can have
a significant effect on accuracy. We can see that FedLE is able to extend the
training compared to FedAvg. We also tested our FedLE algorithm with another
model. Using an MLP model, FedLE converges faster in the earlier rounds but
only slightly outperforms the other two baselines toward the end of the
training. However, we believe it is due to the simplicity of the MLP model.
Under the extreme Non-IID and imbalanced class scenario, the simple MLP model
is difficult to converge, while the CNN model is much more resilient.

Figure 4: CNN and MLP on MNIST with FedLE, FedBO, and FedAvg-B. Figure 5: CNN
on CIFAR-10 with FedLE, FedBO, and FedAvg-B.

###  V-B Number of Clusters And Majority Class

We run another experiment to test how the number of clusters affects the
performance of FedLE. As shown in Fig. 6, increasing the number of clusters
does not have a significant effect on performance. We believe FedLE clusters
majority class data together regardless of the number of clusters. By
increasing the number of clusters, we would only further divide the clusters’
minority class data. Therefore, the impact on accuracy is low when increasing
the number of clusters. From the results, we can see that the optimal number
of clusters should be the sum of the number of the majority class data and the
number of training clients per round.

Figure 6: FedLE using different cluster size for MNIST and CIFAR-10.

The experiment runs using the same setting in Section IV (averaged results
with 5 different seeds). Our proposed method with varying numbers of clusters
in the MNIST experiment shows that when the cluster size is over the number of
training clients (2 in this case), the results are close regardless of the
number of clusters since the majority of class data are correctly categorized
by our method. FedLE with different numbers of clusters on CIFAR-10 shows
similar trends.

TABLE I: Rounds lasted before reaching critical battery level $\delta$ | FedLE | FedAvg-B | FedBO
---|---|---|---
_70% Low-Powered Clients_ |  |  |
MNIST CNN | 49 | 45 | 50
MNIST MLP | 48 | 44 | 50
CIFAR-10 CNN | 48 | 45 | 50
_50% Low-Powered Clients_ |  |  |
MNIST CNN | 48 | 43 | 50
MNIST MLP | 49 | 44 | 50
CIFAR-10 CNN | 48 | 43 | 50
_30% Low-Powered Clients_ |  |  |
MNIST CNN | 49 | 45 | 50
MNIST MLP | 48 | 44 | 50
CIFAR-10 CNN | 49 | 45 | 50

###  V-C Energy saving results

In Table I, we show the performance of energy preservation in terms of the
total number of rounds lasted for the edge IoT network. When 50% of the
clients become unavailable due to low power, we consider the network to be
unusable, and the FL training stops. We can see while FedLE does not
outperform FedBO which prioritizes solely on energy, it inches close with only
2 rounds short. Compared with the classic FedAvg-B, FedLE is able to extend
the training for about 5 more rounds, or 11.6%. Clustering the clients that
share similar data distributions, we protect the low-powered clients by
lowering the probability of selecting them and replacing them with high-
powered clients within the same cluster. As there are still small chances low-
powered clients are selected, we believe that is the reason why FedBO performs
slightly better since it prioritizes the high-powered clients much more.

##  VI Conclusions

In this paper, we proposed FedLE, a clustering method based on the similarity
matrix of client models to balance the energy consumption of battery-powered
edge IoT clients. Experimental results verified that FedLE outperforms
baseline methods while extending the lifespan of edge IoT networks by
protecting low-powered clients from draining batteries. Future work includes
studying the effect of other deep learning models, since the matrix is
calculated based on model parameters.

## Acknowledgement

This material is based in part upon work supported by University of Calgary
Start-up 10032260, National Science Foundation under Grant IIS-2212174,
IIS-1749940, Office of Naval Research N00014-20-1-2382, and National Institute
on Aging (NIA) RF1AG072449.

## References

  * Wu et al. [2023] J. Wu, S. Drew, F. Dong, Z. Zhu, and J. Zhou, “Topology-aware federated learning in edge computing: A comprehensive survey,” _arXiv preprint arXiv:2302.02573_ , 2023.
  * McMahan et al. [2017] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_ , 2017, pp. 1273–1282.
  * Yu et al. [2022] L. Yu, R. Albelaihi, X. Sun, N. Ansari, and M. Devetsikiotis, “Jointly optimizing client selection and resource management in wireless federated learning for internet of things,” _IEEE Internet of Things Journal_ , vol. 9, no. 6, pp. 4385–4395, 2022.
  * Xu and Wang [2021] J. Xu and H. Wang, “Client selection and bandwidth allocation in wireless federated learning networks: A long-term perspective,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 2, pp. 1188–1200, 2021\.
  * Abdulrahman et al. [2021] S. Abdulrahman, H. Tout, A. Mourad, and C. Talhi, “Fedmccs: Multicriteria client selection model for optimal iot federated learning,” _IEEE Internet of Things Journal_ , vol. 8, no. 6, pp. 4723–4735, 2021.
  * Li et al. [2020] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” _Proceedings of Machine Learning and Systems_ , vol. 2, pp. 429–450, 2020.
  * Jee Cho et al. [2022] Y. Jee Cho, J. Wang, and G. Joshi, “Towards understanding biased client selection in federated learning,” in _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , 2022.
  * Nishio and Yonetani [2019] T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” in _2019 IEEE International Conference on Communications (ICC)_. IEEE, 2019, pp. 1–7.
  * Palihawadana et al. [2022] C. Palihawadana, N. Wiratunga, A. Wijekoon, and H. Kalutarage, “FedSim: Similarity guided model aggregation for federated learning,” _Neurocomputing_ , vol. 483, pp. 432–445, 2022.
  * Wang et al. [2021] T. Wang, Y. Liu, X. Zheng, H.-N. Dai, W. Jia, and M. Xie, “Edge-based communication optimization for distributed federated learning,” _IEEE Transactions on Network Science and Engineering_ , 2021.
  * LeCun [1998] Y. LeCun, “The MNIST database of handwritten digits,” _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * Krizhevsky et al. [2009] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.