  This paper studies the problem of selecting a submatrix of a positive
definite matrix in order to achieve a desired bound on the smallest eigenvalue
of the submatrix. Maximizing this smallest eigenvalue has applications to
selecting input nodes in order to guarantee consensus of networks with negative
edges as well as maximizing the convergence rate of distributed systems. We
develop a submodular optimization approach to maximizing the smallest
eigenvalue by first proving that positivity of the eigenvalues of a submatrix
can be characterized using the probability distribution of the quadratic form
induced by the submatrix. We then exploit that connection to prove that
positive-definiteness of a submatrix can be expressed as a constraint on a
submodular function. We prove that our approach results in polynomial-time
algorithms with provable bounds on the size of the submatrix. We also present
generalizations to non-symmetric matrices, alternative sufficient conditions
for the smallest eigenvalue to exceed a desired bound that are valid for
Laplacian matrices, and a numerical evaluation.
