2
$\begingroup$

Suppose the following matrix $A$ is given $$\begin{pmatrix} 0.500 & -0.333 & -0.167\\ -0.500 & 0.667 & -0.167\\ -0.500 & -0.333 & 0.833\end{pmatrix}$$ with its transpose $A^T$. The product $A^TA=G$ yields $$\begin{pmatrix} 0.750 & -0.334 & -0.417\\ -0.334 & 0.667 & -0.333\\ -0.417 & -0.333 & 0.750\end{pmatrix},$$

where $G$ is a Laplacian matrix. Note that matrices $A$ and $G$ are of rank 2, with the zero eigenvalue corresponding to eigenvector $1_n=[1~ 1 ~1]^T$.

I wonder what would be the way to obtain $A$ if only $G$ is given. I tried eigendecomposition $G=UEU^T$, and then set $A'=UE^{1/2}$, but obtained different result. I guess this has to do with rank deficiency. Could someone explain this? Clearly, the above example is for illustration; you could consider general Laplacian matrix decomposition of the above form.


Since, for instance, Cholesky decomposition could be used to find $G=LL^T$, the decomposition on $G$ could yield many solution. I'm interested in the solution that could be expressed as $$A=(I-1_nw),$$ where $I$ is a $3\times 3$ identity matrix, $1_n=[1~ 1~ 1]$, and $w$ being some vector satisfying $w^T1_n=1$. If it simplifies matters, you could assume that the entries of $w$ are non-negative.

  • 0
    The square root of a matrix is not unique, so why should your $A'$ be unique?2012-04-09
  • 1
    Wouldn't that imply that $A$ is symmetric (and, the above example shows that it is not)?2012-04-09
  • 0
    *Laplacian matrix*? Not what http://en.wikipedia.org/wiki/Laplacian_matrix says...2012-04-09
  • 1
    Laplacian is "an $n\times n$, symmetric positive-semidefinite matrix, characterized by having zero row and column sums". Add to this that only off diagonal entries are non-positive.2012-04-09
  • 0
    Cross post at [SciComp](http://scicomp.stackexchange.com/questions/1887/factorizing-the-matrix-to-get-the-starting-matrices).2012-04-09
  • 0
    Thanks for pointing that out. I guess it would a good idea to allow users to somehow link the posts with other stack sites. Because, the spread of "experts" is often not following "name stack" logic.2012-04-09
  • 0
    @user506901, thanks for that definition of Laplacian matrix. It does make sense though I haven't heard that term used before in this context.2012-04-09

1 Answers 1

1

One looks for $A=I-1_3w^T$ such that $G=A^TA$, with $1_3=[1\ 1\ 1]^T$ and $w=[w_1\ w_2\ w_3]^T$ such that $w^T1_3=1$. Using $1_3^T1_3=3$, this yields $$ G=(I-w1_3^T)(I-1_3w^T)=I-w1_3^T-1_3w^T+3ww^T, $$ that is, for every $i\ne j$, $$ G_{ii}=1-2w_i+3w_i^2,\quad G_{ij}=-w_i-w_j+3w_iw_j. $$ Introducing $v=3w-1_3$, one gets $v^T1_3=0$ and, for every $i\ne j$, $$ v_i^2=3G_{ii}-2,\quad v_iv_j=3G_{ij}+1.\tag{$\ast$} $$ One sees that, if a solution $A=I-1_3w^T$ exists, then $G_{ii}\geqslant\frac23$ for every $i$, and, for every $i\ne j$, $$ (G_{ij}+\tfrac13)^2=(G_{ii}-\tfrac23)(G_{jj}-\tfrac23). $$ In the present case, these conditions are met and the system of equations $(\ast)$ reduces to $v_1^2=v_3^2=\frac14$, $v_2=0$ and $v_1v_3=-\frac14$, hence $v_1=\pm\frac12$, $v_2=0$, $v_3=\mp\frac12$.

Since $w_i=\frac13(1+v_i)$ for every $i$, the solutions are $w=[\frac12\ \frac13\ \frac16]^T$ and $w=[\frac16\ \frac13\ \frac12]^T$.

In dimension $n$, the same technique applies, which yields the conditions $$ nG_{ii}\geqslant n-1,\qquad (nG_{ij}+1)^2=(nG_{ii}-n+1)(nG_{jj}-n+1), $$ and the solutions $$ w_i=\tfrac1n\left(1\pm\sqrt{nG_{ii}-n+1}\right). $$

  • 0
    And, fortunately, nearly none of the above is explained [there](http://scicomp.stackexchange.com/questions/1887/finding-the-square-root-of-a-laplacian-matrix).2012-04-15
  • 0
    That's nice. It's good that you've pointed out the conditions on the existence of solutions.2012-04-16