Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
+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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.