Dominant eigenvalue minimization with trace preserving diagonal perturbation: Subset design problem

We study the problem of minimizing the dominant eigenvalue of an essentially-nonnegative matrix with respect to a trace-preserving or fixed-trace diagonal perturbation, in the case where only a subset of the diagonal entries can be perturbed. The spectrum of the perturbed matrix at the optimum is characterized. A constructive algorithm for computing the optimal diagonal trace-preserving perturbation is developed, using the spectral result together with line-sum-symmetrization arguments. A number of graph-theoretic results are developed on the optimal perturbation and how it changes if further entries are constrained, in part using properties of the Perron complement of nonnegative matrices.