Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all 1's. This problem looks vaguely like a semidefinite programming problem, except that both the matrix $(M+D)$ and it's inverse have linear constraints. Overall, the system has as many constraints as variables.

Based on small scale numerical testing, it strongly appears that there is always a unique solution. I've implemented an algorithm (which is $O(n^6)$, $n$ being the size of the matrix), that works by constructing a second matrix $X$, and minimizing $||(M+D) X - I||$ with respect to $D$ and then with respect to $X$ in an alternating fashion. Note that I am using the Frobenius norm here. Given the proper initialization, such the $(M+D)$ is positive definite, this usually appears to converge, and each step is simply a quadratic minimization.

That said, I have no proof that there is a unique solution for $D$, or that the algorithm above works in the general case, and moreover I have a strong intuition that there is an algorithm with is closer to $O(n^3)$.

What I seeks is proof or a theoretical justification that the solution to $D$ is unique (or of course a counterexample). Even better would be a provably polynomial time algorithm to find $D$.

My approach for a proof up till this point has been along the lines of finding some error function $f(X)$, $X = M + D$, such as $f(X) = \sum_i ((X^{-1})_{ii} - 1)^2$. This function (and lots of other variants) have a minimum at the desired solution. My hope was to then show that the function is convex over all positive definite matrices $X$. However I have not been able to accomplish this so far.

Edit: For the $f(X)$ given above I have found a number of counterexamples to it's convexity, although perhaps the overall method is still salvageable with a different error function.

Edit: Some additional facts I've been able to show (in part with help from the comments)

The set of all positive definite matrices $X = M + D$ is clearly a convex set (since it is the intersection of two convex sets, the positive definite matrices and the set of all matrices with non-diagonal elements $M$).

Moreover, the set of all $X$ above such that all the diagonals elements of $X^{-1}_{ii} \le 1$ is also a convex set. This follows from the convexity of $e^T X^{-1} e$, and the statement above. The solution in question is clearly on the boundary of this set.

asolution, although that doesn't say much about uniqueness clearly. – Jeremy Aug 27 '11 at 22:16