Bounding the row sum arithmetic mean by Perron roots of row-permuted matrices

Abstract

$R_{+}^{n\times n}$ denotes the set of $n\times n$ non-negative matrices. For $A\in R_{+}^{n\times n}$ let $\Omega (A)$ be the set of all matrices that can be formed by permuting the elements within each row of $A$. Formally: $$\Omega (A)=\{B\in R_{+}^{n\times n}:\forall i\exists \text{ a permutation }{\varphi }_i\text{s.t.}{b}_{i,j}=a_{i,{\varphi }_i(j)}\forall j\}.$$ For $B\in \Omega (A)$ let $\rho (B)$ denote the spectral radius or largest non negative eigenvalue of $B$. We show that the arithmetic mean of the row sums of $A$ is bounded by the maximum and minimum spectral radius of the matrices in $\Omega (A)$ Formally, we are showing that $$\underset{B\in \Omega (A)}{\min }\rho (B)\le \frac{1}{n}\sum _{i=1}^n\sum _{j=1}^n{a}_{i,j}\le \underset{B\in \Omega (A)}{\max }\rho (B).$$ For positive $A$ we also obtain necessary and sufficient conditions for one of these inequalities (or, equivalently, both of them) to become an equality. We also give criteria which an irreducible matrix $C$ should satisfy to have $\rho (C)={\min }_{B\in \Omega (A)}\rho (B)$ or $\rho (C)={\max }_{B\in \Omega (A)}\rho (B)$. These criteria are used to derive algorithms for finding such $C$ when all the entries of $A$ are positive .

12 pages

References in corpus (1)

• On sets of eigenvalues of matrices with prescribed row sums and prescribed graph