Is the following fact for laplace matrix true? And how to prove it?

Question

$A$ is a matrix with $0$ or $1$ element. $L$ is the lapace matrix of $A$. $S$ is a real vector, we define $\mathbb{sign}(S) = [\mathbb{sign}(s_1),...,\mathbb{sign}(s_n)]^T$. I find the following fact that $S^TL\mathbb{sign}(S)>0$ is always true through a large simulation. Is the fact necessary for the matrix metioned above and how can I prove it?

Answer 1

Depending on convention, the sign of zero may be zero or one.

When $\operatorname{sign}(0)=1$, let $D=\operatorname{diag}(\operatorname{sign}(S))$. Then $S=Dv$ for some $v\ge0$ and $\operatorname{sign}(S)=D\mathbf1$. Hence $S^TL\operatorname{sign}(S)=v^TDLD\mathbf1$. Since $L$ is Laplacian and $D$ is a diagonal matrix whose diagonal entries are equal to $\pm1$, $L\le DLD$ entrywise. It follows that $0=L\mathbf1\le DLD\mathbf1$ and in turn, $0\le v^TDLD\mathbf1$.

When $\operatorname{sign}(0)=0$, we have $S^TL\operatorname{sign}(S)=u^TM\operatorname{sign}(u)$ where $u$ is the subvector containing all nonzero entries of $S$ and $M$ is the corresponding principal submatrix of $L$. Let $D=\operatorname{diag}(\operatorname{sign}(u))$. Then $u=Dv$ for some $v>0$ and $u^TM\operatorname{sign}(u)=v^TDMD\mathbf1$. Similar to the previous paragraph, we have $M\le DMD$ entrywise and hence $M\mathbf1\le DMD\mathbf1$. Note that, as $M$ is a principal submatrix of $L$ and all off-diagonal entries of $L$ are non-positive, every row sum in $M$ is $\ge$ the corresponding row sum in $L$, because there are potentially fewer negative entries. It follows from $0=L\mathbf1$ that $0\le M\mathbf1$. Therefore $0\le M\mathbf1\le DMD\mathbf1$ and in turn, $0\le v^TDLD\mathbf1$.