Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and only if the graph is a tree (because then $B$ has $n-1$ columns and rank $n-1$). Is there a nice way to to factorize a connected graph with cycles?
I believe you are looking for a sparse Cholesky factorization (performed after column-row pivoting). In this sense, the view of the graph begins to intertwine with a sparse-matrix interpretation. The graph cycle appears as a "feedback loop", in the linear operator interpretation of Laplacian matrix, and is eliminated by Gaussian elimination.
It is worth noting that for a tree, the Cholesky factorization coincides with the oriented incidence matrix of the corresponding graph, assuming that factorization is performed in the correct order, from the leaves to the root (EDIT: corrected!). For graphs containing many cycles, e.g. the grid graph, the factorizations are fully dense, despite originating from a sparse matrix. For everything in-between, the density of the factorization is a good gauge to how interconnected the graph is.
I'm happy to provide refs / more info / detail if you can elaborate on exactly what you're looking for.
