# Matrix factorization to get the right solution

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.

-
The square root of a matrix is not unique, so why should your $A'$ be unique? –  Phira Apr 9 '12 at 9:04
Wouldn't that imply that $A$ is symmetric (and, the above example shows that it is not)? –  user506901 Apr 9 '12 at 9:11
Laplacian matrix? Not what en.wikipedia.org/wiki/Laplacian_matrix says... –  lhf Apr 9 '12 at 11:05
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. –  user506901 Apr 9 '12 at 11:28
Cross post at SciComp. –  Inquest Apr 9 '12 at 16:38

## 1 Answer

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

-
And, fortunately, nearly none of the above is explained there. –  Did Apr 15 '12 at 11:11
That's nice. It's good that you've pointed out the conditions on the existence of solutions. –  user506901 Apr 16 '12 at 7:45