The Laplacian matrix of a nondirected graph can be written as $M^TM$ with $M$ being the incidence matrix of the graph. This makes the (otherwise tedious) proof of Kirkhoff's theorem into a beautiful application of the Cauchy-Binet formula (and indeed, this is one of the proofs in "Proofs from THE BOOK").
If the graph is directed, $M^TM$ does not work anymore; the diagonal of the resulting matrix contains the total degree of vertices, whereas for Kirkhoff's theorem to work, only the indegree should appear.
So my question is this: can this approach still be salvaged by a slightly different definition of $M$ that eludes me, or is the "tedious" proof necessary and Cauchy-Binet simply can't be used here?
Best Answer
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$:
The rest of the entries are 0.
Unless I have some computational error, we have $L=AB^T$.