7
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.