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

Motivated by network resource allocation needs, 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. Graph-theoretic characterizations of the optimal subset design are obtained: in particular, the design is connected to the structure of a reduced effective graph defined from the essentially-nonnegative matrix. Also, the change in the optimum is studied when additional diagonal entries are constrained to be undesignable, from both an algebraic and graph-theoretic perspective. These results are developed in part using properties of the Perron complement of nonnegative matrices, and the concept of line-sum symmetry. Some results apply to general essentially-nonnegative matrices, while others are specialized for sub-classes (e.g., diagonally-symmetrizable, or having a single node cut). (C) 2017 Elsevier Ltd. All rights reserved.