# Is there a closed-form solution to this linear algebra problem?

$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?

-
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

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'$.

-