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
    Depends on what you call a closed-form solution.2012-02-29
  • 0
    SVD & the like are fine2012-02-29
  • 0
    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$.2012-02-29
  • 0
    Note that $B$ has the same row sums as $A$, so you actually know $D$.2012-02-29
  • 0
    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?2012-02-29
  • 0
    The question reminded me of [this one](http://math.stackexchange.com/questions/67282/is-there-a-way-to-solve-the-following-tensor-equation), but that has $A^{-1}$ instead of $A$ as the last factor.2012-02-29
  • 0
    If you write $C=D^{1/2}A$, then $C^\top C=B$. This is solved by $C=OB^{1/2}$, where $O$ is any orthogonal matrix. Thus $A$ is of the form $D^{-1/2}OB^{1/2}$, but I don't see how to choose $O$ such that this is symmetric. Demanding symmetry yields $N(N-1)/2$ linear relationships between the entries of $O$, and together with the $N(N+1)/2$ quadratic orthonormality constraints this should determine $O$, but the mixture of linear and quadratic constraints doesn't seem any easier than the original problem.2012-02-29
  • 0
    Thanks for the help. Any other ideas? I'm stumped2012-02-29
  • 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'$.