# Minimizing the sum of the $k$ smallest elements of the diagonal of a matrix

I have a $N\times N$ symmetric positive semidefinite matrix $Q$, and am considering a class of symmetric positive definite matrices having all eigenvalues in a given bounded interval $[a, b]$.

Is it possible to find a matrix in this class such that the sum of the smallest $k$ elements of $\text{diag}(XQ)$ is minimized?

I am welcoming any suggestion, either in the form "not a trivial problem", or "here is the solution, or a pointer to it".

-

I don't know if there's a quick and easy solution (I doubt it), but if you want to approach the problem numerically, I'd suggest using the spectral decomposition of $X$. Then you could alternatingly solve the minimization problem for the eigenvalues alone and for the eigenvectors alone. For each of these minimization problems, you could keep the set of diagonal elements that are summed fixed in each step; then if it turns out that after the step different diagonal elements have become the smallest ones, the target value can only decrease when you switch to summing the right elements, so this shouldn't cause oscillations. With fixed diagonal elements being summed, the minimization problem for the eigenvalues would be a trivial linear problem with solution either $a$ or $b$ for each eigenvalue. (That seems a bit too easy -- am I making a mistake there?) Since all eigenvalues will be either $a$ or $b$ in the end, you could also consider doing $N+1$ separate eigenvector optimizations with all possible combinations of eigenvalues; then you don't have to worry about the eigenvalues at all -- that would probably be less efficient but easier to code. I wouldn't be surprised to find that one could show that they will all end up $a$ anyway -- there is clearly a bias towards $a$, and they can certainly not all be $b$.

Regarding the minimization problem for the eigenvectors, I've done that sort of thing before, using rotation matrices that reproduce the correct gradient to linear order; I could write more about the details of that but that will get a bit more involved so I'll stop here and wait to see if you think this is at all a promising approach.

P.S.: Note that if it's true that all the eigenvalues will be either $a$ or $b$, then you wouldn't in fact be optimizing a full set of eigenvectors, but just a decomposition into two orthogonal eigenspaces of given dimensions. This might also lead to ideas for an analytical solution after all.

P.P.S.: In fact I think it does :-). I just realized that for summation over fixed diagonal elements (say, with index set $I$) you can write the target function as the sum over a quadratic form evaluated at each of the eigenvectors and multiplied by the corresponding eigenvalue:

$$\sum_{i\in I}\mathrm{diag}(XQ)_i = \sum_{i\in I} \vec{e}_i^\mathrm{T}\left(\sum_{j=1}^N\lambda_j x_jx_j^\mathrm{T}\right)Q\vec{e}_i=\sum_{j=1}^N\lambda_jx_j^\mathrm{T} \left(\sum_{i\in I}Q\vec{e}_i\vec{e}_i^\mathrm{T}\right)x_j\;.$$

I'd be surprised if the solution for minimizing this weren't that the eigenvectors are the eigenvectors of that quadratic form and the eigenvalues are $a$ or $b$ according as the eigenvalues of the quadratic form are positive or negative.

If that's true, then you could find the global optimum by trying out all $\left(N\atop k\right)$ subsets of $k$ diagonal elements and diagonalizing the corresponding quadratic forms. But I still feel I may have made some gigantic mistake along the way -- it seems simpler than it should be now...

-