Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The square root of a matrix is not unique, so why should your $A'$ be unique? –  Phira Apr 9 '12 at 9:04
1  
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
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. –  user506901 Apr 9 '12 at 11:28
    
Cross post at SciComp. –  Inquest Apr 9 '12 at 16:38

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.