# Matrix optimization problem

This is (probably) an easy one:

Given a positive definite matrix $M$, find the positive definite matrix $X$, which minimizes $\textrm{tr}(X M)$ subject to $\det(X) = 1$.

Looking for how to find X, either a formula, an algorithm, or a reference to a paper.

-Thanks

-

If the eigenvalues of $M$ are $\lambda_1$, $\lambda_2$, ..., $\lambda_n$, then the minimum is $n (\lambda_1 \cdots \lambda_n)^{1/n}$.

Proof: Your problem is invariant under conjugating $X$ and $M$ by a unitary matrix. So we may assume that $M$ is diagonal, with diagonal entries $\lambda_1$, ..., $\lambda_n$. Once we have made this assumption, we have $\mathrm{Tr}(XM) = \sum x_{ii} \lambda_i$. In other words, this is a linear function of the diagonal of $X$.

We temporarily restrict ourselves to looking at those $X$ whose eigenvalues are $\mu_1$, $\mu_2$, ..., $\mu_n$. The space of positive definite matrices $X$ with eigenvalues $\mu_1$, $\mu_2$, ..., $\mu_n$ is a compact manifold. The Schur-Horn theorem states:

The subset of $\mathbb{R}^n$ which can occur as the diagonal of a positive definite matrix with eigenvalues $(\lambda_1, \ldots, \lambda_n)$ is a convex polytope; its vertices are the $n!$ permutations of $(\mu_1, \ldots, \mu_n)$.

A linear functional on a convex polytope is always minimized at a vertex. We conclude that

Given $(\mu_1, \ldots, \mu_n)$, as $X$ ranges over positive definite matrices with eigenvalues $\mu_i$, the minimal value of $\mathrm{Tr}(XM)$ is $\sum \lambda_i \mu_i$, where the $\lambda$'s and the $\mu$'s are sorted in opposite orders.

Now, we want to vary the $\mu$'s. So we want to find the minimal value of $\sum \lambda_i \mu_i$ where $\mu_i$ ranges over $n$-tuples obeying $\prod \mu_i = 1$, with $\mu_i$ sorted in the reverse order from $\lambda_i$. (In fact, removing this last condition will not effect the minimum.)

By the AM-GM inequality, $\sum \lambda_i \mu_i \geq n \prod \lambda_i^{1/n} \prod \mu_i^{1/n} = n \prod \lambda_i^{1/n}$. We get equality if $\mu_i = \left( \prod \lambda_i \right)^{1/n} / \lambda_i$, and we take $X$ to be diagonal in the same basis where $M$ is diagonal.

-
+1 for speed: I was at the AMGM too, but then i decided to refresh, and your solution was already there! – Suvrit Apr 28 '11 at 17:09
Thanks a lot for the excellent answer. As a minor point for anyone who reads this in the future, the final result implies $X=\det(M) M^{-1}$. – Jeremy Apr 29 '11 at 0:29