Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$A$ and $B$ are non-negative symmetric matrices, whose entries sum to 1.0.

Each of these matrices has $\frac{N^2-N}{2}+N-1$ degrees of freedom.

$D$ is the diagonal matrix defined as follows (in Matlab code):

$$D=\text{diag}(\text{diag}(A*\text{ones}(N)))^{-1}$$

We are given the matrix $B$. Does this problem have a closed-form solution to $A$ (assuming one exists), such that

$$ADA=B$$

If so, what is it? If not, what's the best method to find an approximate solution?

share|improve this question
    
Depends on what you call a closed-form solution. –  Alex Becker Feb 29 '12 at 0:02
    
SVD & the like are fine –  user25956 Feb 29 '12 at 0:04
    
It seems a bit "proprietary" to post in Matlab code when the question isn't about Matlab -- why not avail yourself of the universal mathematical notation we've been blessed with? Or you could just say in words that $D$ contains the reciprocals of the row sums on the diagonal. Or you could write that $A\hat{A}=B$, where $\hat A$ is $A$ with the rows normalized to sum to $1$. –  joriki Feb 29 '12 at 0:18
    
Note that $B$ has the same row sums as $A$, so you actually know $D$. –  joriki Feb 29 '12 at 0:29
    
BTW, $1.0$ is an unusual specification. Usually this notation indicates that you know the value only to one decimal place, but I presume you actually mean $1$ exactly? –  joriki Feb 29 '12 at 0:42

1 Answer 1

The diagonal entries of $D$ are the reciprocals of the row sums of $A$. The row sums of $B$ are those of $A$. Thus $D$ is known. Then $A$ can be obtained as

$$A=\frac1{\sqrt D}\sqrt{\sqrt DB\sqrt D}\frac1{\sqrt D}\;,$$

or, if you prefer,

$$A=D^{-1/2}\left(D^{1/2}BD^{1/2}\right)^{1/2}D^{-1/2}\;.$$

According to this post, this is the unique symmetric positive-definite solution of $ADA=B$.

The square root of $D$ is straightforward; the remaining square root can be computed by diagonalization or by various other methods.

To see that the solution is consistent in that the $A$ so obtained does indeed have the same row sums as $B$, note that

$$\left(D^{1/2}BD^{1/2}\right)\left(D^{-1/2}\mathbf 1\right)=D^{1/2}B\mathbf 1=D^{1/2}D^{-1}\mathbf 1=D^{-1/2}\mathbf 1\;,$$

where $\mathbf 1$ is the vector consisting entirely of $1$s. Thus $D^{-1/2}\mathbf 1$ is an eigenvector with eigenvalue $1$ of $D^{1/2}BD^{1/2}$, and thus also of

$$D^{1/2}AD^{1/2}=\left(D^{1/2}BD^{1/2}\right)^{1/2},$$

and thus

$$DA\mathbf1=D^{1/2}\left(D^{1/2}AD^{1/2}\right)\left(D^{-1/2}\mathbf1\right)=D^{1/2}D^{-1/2}\mathbf1=\mathbf1$$

as desired.

Perhaps a more concise way of saying all this is that we should apply a transform $x=D^{1/2}x'$ to get

$$x^\top Ax=x'^\top A'x'\quad\text{with}\quad A'=D^{1/2}AD^{1/2}\;,\\ x^\top Bx=x'^\top B'x'\quad\text{with}\quad B'=D^{1/2}BD^{1/2}\;,\\ \mathbf1'=D^{-1/2}\mathbf1\;,$$

and then the equation becomes $A'^2=B'$ and the row sum conditions become $A'\mathbf1'=B'\mathbf1'=\mathbf1'$.

share|improve this answer

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.