3
$\begingroup$

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

  • 0
    Also posted (and currently on the verge of closure) at MO, http://mathoverflow.net/questions/89813/is-there-a-closed-form-solution-to-this-linear-algebra-problem2012-02-29

1 Answers 1

2

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