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

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.

share|improve this question
    
unique for 2 by 2, assuming you mean all diagonal entries of $M$ are 0. Seems worth a good symbolic working over in the 3 by 3 case, at the same time a pretty full test with randomized entries. This kind of thing, fairly often, is either true or dies in dimension no larger than 4. –  Will Jagy Aug 27 '11 at 21:25
    
From a computational perspecive, I've run thousands of random examples on 10 by 10 matrices and all of them had a solution, although that doesn't say much about uniqueness clearly. –  Jeremy Aug 27 '11 at 22:16
    
Sorry; it seems that in my speed, all I proved was that $e^TX^{-1}e-1$ is convex, not its square as I claimed---so this idea gets deleted. Indeed, only for $e^TX^{-1}e \ge 1$ is the claimed function guaranteed to be convex. –  Suvrit Aug 28 '11 at 17:49
1  
It may be worth noting that you can write the condition that the diagonal elements of $X^{-1}$ are at most $1$ using semidefinite constraints. Suppose $X$ is positive definite and let $e_i$ be the $i^{\text{th}}$ unit column vector. Taking Schur complements, $\begin{bmatrix} 1 & e_i' \\ e_i & X\end{bmatrix}\succeq 0$ if and only if $e_i'X^{-1}e_i\leq 1$. Imposing these constraints for all $i$ gives the claimed condition. The question, then, is whether there is a suitable objective function which would encourage all of these Schur complement conditions to be tight simultaneously. –  Noah Stein Aug 28 '11 at 19:41

2 Answers 2

up vote 5 down vote accepted

(Edit: my original answer was perhaps not clear enough, let me try to improve it).

First some notation: for a matrix $x$, let me denote by $E(x)$ the diagonal matrix with the same diagonal as $x$: if $x=(x_{i,j})_{i,j\leq n}$, $E(x) = (x_{i,j}\delta_{i,j})_{i,j \leq n}$. Equivalently, $E$ is the orthogonal projection on the diagonal matrices when you consider the usual euclidean structure on $M_n$. If will also write $x>0$ to mean $x$ is symmetric positive definite.

You are asking whether the map $f:x \mapsto x^{-1} - E(x^{-1})$ is a bijection from its domain $D=\{x \in M_n(\mathbb R), x>0\textrm{ and }E(x)=1\}$ to its image $I=\{x \in M_n, x=x^*\textrm{ and }E(x)=0\}$. And the answer is yes. I prove first that $f$ is injective, and then that it is surjective.


f is injective

In fact let me prove the following fact, which is equivalent to the injectivity of $f$.

Let $x$ be a positive matrix. If $d$ is a diagonal matrix such that $x+d$ is positive and such that $x^{-1}$ and $(x+d)^{-1}$ have the same diagonals, then $d=0$.

Proof: Since $d$ is diagonal, the trace of $d\left(x^{-1} - (x+d)^{-1}\right)$ is zero. But one can write this expression as \[dx^{-1/2}\left(1- (1+x^{-1/2}dx^{-1/2})^{-1}\right)x^{-1/2},\] so that taking the trace and denoting by $a=x^{-1/2}dx^{-1/2}$, we get $0= Tr(a(1-(1+a)^{-1}))$.

If $\lambda_1,\dots,\lambda_n$ are the eigenvalues of $a$, the condition $x+d$ positive becomes $1+\lambda_i >0$, and the last equality becomes $0 = \sum \lambda_i(1-1/(1-\lambda_i)) = \sum \lambda_i^2/(1+\lambda_i)$, which is possible only if the $\lambda_i$ are all zero, i.e. $a=0$, i.e. $d=0$.


** f is surjective **

The surjectivity is true just for topological reasons. More precisely, to prove that $f$ is surjective, it is enough to prove that it is continuous, open and proper (because this would imply that the image is an open and closed subset of $I$, and hence everything since $I$ is connected). The continuity is obvious. $f$ is even differentiable, and the differential is explicitely computable and easily seen to be invertible at every point, so that $f$ is indeed open. It remains to check that it is proper.

The proof I have is not completely obvious, maybe I am missing something. Let me only sketch it. Take a sequence $x_k \in D$ that escapes every compact subset of $D$. Since $\|x\|\leq n$ for all $x \in D$, we have that $u_k=\|x_k^{-1}\|\to \infty$ (I consider the operator norm, and the inequality $\|x\|\leq n= Tr(x)$ is because the norm of $x>0$ is its largest eigenvalue, whereas its trace is the sum of its eigenvalues). We want to prove that $\|f(x_k)\|\to \infty$. Assume for contradiction that this is not the case, and that $\|f(x_k)\|\leq C$ for all $k$. We will get a contradiction through a careful study of the spectral decomposition of $x_k$.

Let $\xi_k$ be a sequence of unit eigenvectors of $x_k$ relative to the smallest eigenvalue of $x_k$, i.e. $x_k \xi_k = 1/u_k \xi_k$. Now the key observation: the assumption that $\|f(x_k)\|\leq C$ implies that, for all diagonal matrix $d$ with $1$ or $-1$ on the diagonal, the distance from $d \xi_k$ to the space $F_k$ spanned by the eigenvectors of $x_k^{-1}$ relative to the eigenvalues in an interval $[u_k/2,u_k]$ goes to zero. For a proof, consider the random diagonal matrix $d$ in which the diagonal entries are iid random variables uniform in $\{-1,1\}$, so that $E(x) = \mathbb E (d x d)$ (hoping there will be no confusion between $E$ and $\mathbb E$). Then $\langle f(x_k) \xi_k,\xi_k\rangle = \mathbb E ( u_k - \langle x_k d \xi_k, d \xi_k\rangle)$. The lhs of this equality is by assumption smaller than $C$. On the rhs, $u_k - \langle x_k d \xi_k, d \xi_k\rangle \geq 0$ because $d \xi_k$ is a unit vector. This implies that $u_k - \langle x_k d \xi_k, d \xi_k\rangle \leq 2^n C$ for any diagonal matrix with $\pm 1$ on the diagonal. But now use the fact that, for $x>0$ in $M_n$, if a unit vector $\xi$ in $\mathbb R^n$ satisfies $\langle x \xi,\xi\rangle \geq \|x\|-\delta$, then $\xi$ is at distance less than $\sqrt{2\delta/\|x\|}$ from the space spanned by the eigenvectors of $x$ relative to eigenvalues in the interval $[\|x\|/2,\|x\|]$ (hint for a proof: consider the decompostion of $\xi$ in an orthonormal basis of eigenvectors of $x$). Here if $\epsilon_k = \sqrt{2^{n+1} C/ u_k}$, we have indeed proved that $d \xi_k$ is at distance less than $\epsilon_k$ from $E_k$ for any diagonal matrix with $\pm 1$ on the diagonal.

I now claim that there is a vector $\eta_k$ in the canonical basis of $\mathbb R^n$ at distance less than $\sqrt n \epsilon_k$ from $E_k$. This will conclude the proof since it will in particular imply that $\langle x_k \eta_k,\eta_k\rangle \to 0$, whereas the assumption $E(x_k)=1$ implies that $\langle x_k \eta_k,\eta_k\rangle = 1$, a contradiction. To prove the claim, let $i$ be such that the $i$-th coordinate of $\xi_k$ is larger than $1/\sqrt n$ in absolute value. Observe that $\xi_k(i) e_i$ is the expected value of $d \xi$, where $d$ is the same random matrix as above, but conditionned to $d_i = 1$. This implies that $\xi_k(i) e_i$ is at distance at most $\epsilon_k$ from $E_k$, which proves the claim.

A remark I do not like this proof, since it really relies on finite-dimensional techniques. In particular, it does not extend to general von Neumann algebras (whereas the injectivity part does). I would prefer a more direct proof.

share|improve this answer
    
Of course, sorry. –  Jeremy Aug 30 '11 at 16:30
    
Looks great! It will take me a while to go through the proof in detail, but I think that you've got it. –  Jeremy Aug 30 '11 at 16:40
    
What does "conditional expectation on the algebra of diagonal matrices" mean? Apologies for my lack of familiarity with what must be standard terminology.... –  alex Aug 30 '11 at 21:13
    
Here it just means the map defined by the formula $(a_{i,j})_{i,j \leq n} \mapsto (\delta_{i,j} a_{i,j})_{i,j\leq n}$. More abstractly it is the only trace preserving linear map $E$ from $M_n(\mathbb C)$ to the space $diag_n$ of diagonal matrices that satisfies $E(1)=1$ and $E(dad') = d E(a) d'$ for all diagonal matrices $d_1,d_2$ and all matrices $a$. This terminology makes sense if you replace the couple $(diag_n,M_n(\mathbb C))$ by any couple of von Neumann algebras with one included in the other. In the case the algebras are commutative, you recover the classical notion from probability. –  Mikael de la Salle Aug 30 '11 at 22:10
    
Proof of unicity looks good, still going over the second bit. As a clarification, isn't the definition of $D$ missing a requirement of symmetry? Or is that not needed for some reason. –  Jeremy Aug 30 '11 at 23:43

Just a suggestion on emphasis. I really like Mark's last comment on Sunday. So I suggest the following: Let $U \subseteq \mathbb R^{(n^2 - n)/2}$ be the set of upper right triangles in any positive definite symmetric matrix $W$ with all 1's on the diagonal. I think $U$ is open and connected. Now, regard the matrix inverse of $W$ as mapping $U$ to $ \mathbb R^{(n^2 - n)/2},$ giving the upper triangle of some matrix, and of course ignoring the resulting diagonal.

My suggestion is that this may be a smooth bijection. Surjectivity is plausible as the determinant of $W$ may get arbitrarily close to 0, at the same time that several off-diagonal entries of $W$ are closer to $\pm 1$ than to 0. Useful ingredients could be the Cholesky decomposition. Meanwhile, as Brendan mentioned, if it is a bijection it at least must be a smooth diffeomorphism around every point.

Well, it works for $n=2,$ and looks very pretty for $n=3$ but i have not proved it yet.

share|improve this answer
    
Jeremy, no, the matrix IS symmetric, call it $W.$ All diagonal elements of $W$ are 1. By symmetry of $W,$ the upper triangle and lower triangle agree, so we need only keep track of the set $U.$ –  Will Jagy Aug 29 '11 at 21:51
    
Ah, sorry misunderstood, deleted former comment. –  Jeremy Aug 29 '11 at 21:53
    
Right. I suspect this property is stronger than what you originally asked about, but could well be true, and if true is quite pretty. –  Will Jagy Aug 29 '11 at 21:57
    
Actually, my intuition is that there is a smooth bijection as you describe, although that is based on some very sketchy application of information geometry for a machine learning problem (which in the context in which the question arose). –  Jeremy Aug 29 '11 at 22:05
1  
Do you mean for $\in$ to be $\subset$? –  Noah Stein Aug 30 '11 at 2:09

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.