Conditions to preserve Laplacian matrix

160 Views Asked by At

Let $L$ be a Laplacian matrix $L=D-A$ where $D$ and $A$ are the degree and the adjacency matrices. It is known that $L$ has (among others) the properties: $L=L^T$, $L\geq 0$ and $L1_n=0$, where $1_n$ denotes the $n$-dimensional vector with all entries equal to $1$.

Now I have the transformation $\bar L=WLW^T$, where $W$ is an $r\times n$ matrix, and then $\bar L$ is an $r\times r$ matrix. We assume that $W$ is full rank.

Q: I would like to find (IF possible) necessary and sufficient conditions for $\bar L$ to be Laplacian. The difficult part is to check or find conditions on $\bar L 1=0$. We proceed as follows:

let us write $W=\begin{bmatrix} w_1\\ w_2\\ \vdots\\ w_r \end{bmatrix}$, $W^T=\begin{bmatrix} w_1^T & w_2^T & \cdots & w_r^T \end{bmatrix}$.

Then $\bar L=WLW^T=\begin{bmatrix} w_1Lw_1^T & w_1Lw_2^T & \cdots & w_1Lw_r^T\\ w_2Lw_1^T & w_2Lw_2^T & \cdots & w_2Lw_r^T\\ \vdots & & & \\ w_rLw_1^T & w_rLw_2^T & \cdots & w_rLw_r^T\\ \end{bmatrix}$.

Thus we have

$$ \bar L1_r=\begin{bmatrix} w_1L(w_1^T+\ldots +w_r^T)\\ \vdots\\ w_rL(w_1^T+\ldots +w_r^T)\\ \end{bmatrix}=\begin{bmatrix} 0\\ \vdots\\ 0\\ \end{bmatrix} $$

This means that we have to solve $w_iL\alpha=0$ for all $i=1,\ldots,r$ and $\alpha=w_1^T+\ldots +w_r^T$.

From the fact that $W$ is full rank, we know that $w_i$ and $\alpha^T$ are linearly dependent for all $i$. But I don't know how and where should I proceed. Do you think I can refine more the conditions on $W$?

1

There are 1 best solutions below

2
On

I'll demonstrate that a necessary and sufficient condition is $$LW^T1 = 0$$ when $r \leq n$.

$\bar L$ is self-adjoint

Since $\bar L = WLW^T$ we have $$(\bar L)^T = (WLW^T)^T = WL^TW^T = WLW^T$$

$\bar L$ is positive semi-definite

We know that for all $v$, $\langle Lv, v \rangle \geq 0$. We compute $$\langle \bar L v, v \rangle = \langle WLW^Tv, v \rangle = \langle L(W^Tv), W^Tv \rangle = \langle Lu, u \rangle \geq 0$$ where $u = W^Tv$.

$\bar L 1 = 0$ is equivalent to $LW^T1 = 0$

Consider $$\bar L1 = WLW^T1 = W(LW^T1) = 0$$ Since $W$ is full rank (and $r \leq n$), the only way for $WLW^T1 = 0$ is for $LW^T1 = 0$.

I am unable to produce a better condition for a general $W$ than the one at the end of your post: $$WLW^T1 = 0$$