Writing the Laplacian matrix of directed graphs as product?
I believe I have found a way to write the Laplacian as a product. First recall the definition in the directed-graph case: The Laplacian of $G=(V,E)$ is a matrix of size $|V|\times |V|$ such that $L_{ii}$ is the in-degree of $v_i$, and $L_{ij}$ for $i\ne j$ is minus the number of edges from $v_i$ to $v_j$.
Since the Laplacian needs not be symmetric in the directed case, it can't be written as $M^{T}M$. However, it can be written as $AB^T$ for two very similar matrices:
Define both A and B to be $n\times m$ matrices, where each row represents a vertex and each column represents an edge of $G$. Now, for each edge $e_k = v_i\to v_j$:
- $A_{ik} = 1, A_{jk} = -1$
- $B_{ik} = 0, B_{jk} = -1$
The rest of the entries are 0.
Unless I have some computational error, we have $L=AB^T$.