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
    @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
    That's nice. It's good that you've pointed out the conditions on the existence of solutions.2012-04-16