Projection of the degree vector on the kernel of digraph Laplacian

70 Views Asked by At

Let $g$ be a strongly connected directed graph, $A$ its adjacency matrix, $d$ its in-degree vector, $D$ its in-degree diagonal matrix and $L=D-A$ its Laplacian.

According to this excellent answer the kernel of $L$ is $1$-dimensional and the vector $w=(w_i)$, where $w_i$ is the number of directed trees that originate from the vertex $i$, spans the kernel of $L$.

For some reason that would take too long to explain, I'm interested in the projection $\text{proj}_wd$ of $d$ onto $w$. It seems that it is always true that $\|\text{proj}_wd\|_1\le\|d\|_1$, where $\|\cdot\|_1$, the $1$-norm on $\mathbb R^n$. I know it's a stretch, but are there any such results?

PS. Clearly this does not hold for arbitrary vectors $d$ and $w$, in which case the inequality $\|\text{proj}_wd\|_1\le\sqrt n \|d\|_1$ is correct.