Submodular spectral functions of principal submatrices of a hermitian matrix, extensions and applications

We extend the multiplicative submodularity of the principal determinants of a nonnegative definite hermitian matrix to other spectral functions. We show that if f is the primitive of a function that is operator monotone on an interval containing the spectrum of a hermitian matrix A, then the function I bar right arrow trf(A[I]) is supermodular, meaning that trf(A[I]) + trf(A[J]) <= trf(A[I boolean OR J]) + trf(A[I boolean AND J]), where A[I] denotes the I x I principal submatrix of A. We discuss extensions to self-adjoint operators on infinite dimensional Hilbert space and to M-matrices. We also discuss an application to CUR approximation of nonnegative hermitian matrices. (C) 2011 Elsevier Inc. All rights reserved.