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

(*for correct formatting of formulae, please see Version of Record)

Rn×n denotes the set of n × n non-negative matrices.
+
For A ∈ Rn×n let Ω(A) be the set of all matrices that can be formed by permuting the elements within each row of A.
+
Formally:

Ω(A) = {B ∈ Rn×n : ∀i ∃ a permutation
+
φi s.t. bi,j = ai,φi (j) ∀j}.

For B ∈ Ω(A) let ρ(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 Ω(A). Formally, we show that

min ρ(B) ≤ 1
B∈Ω(A) n
n
n∑
i=1
n∑
j=1
ai,j ≤ max
B∈Ω(A) ρ(B).
For positive A we obtain necessary and sufficient conditions for these inequalities to become an equality. We also give
criteria which an irreducible matrix C should satisfy so that
ρ(C) = minB∈Ω(A) ρ(B) or ρ(C) = maxB∈Ω(A) ρ(B).
These criteria are used to derive algorithms for finding such C when all the entries of A are positive.