Rank of Laplacian matrix

Question

Let $ L $ be a Laplacian matrix of a balanced and strongly connected digraph having $n $ nodes. $ L[r]$ is a submatrix of $L$ which is obtained by deleting $rth$ row and $rth$ column of Laplacian matrix $L$. It is observed for any $r$ the rank of $ L[r]$ is full$(n-1)$. How can I prove this fact? Thanks in advance for your suggestions.

Answer 1

This is in fact true. What's more, the celebrated matrix-tree-theorem (or Kirchhoff theorem) states that the determinant of the reduced matrix $L[r]$ is precisely the number of spanning trees in the underlying graph (so surprisingly it's also the same number for any $1\leq r\leq n$). The number of spanning trees in a connected graph is a positive number, so $\det(L[r])\neq 0$. And hence, $L[r]$ is regular.

Answer 2

The proof can start with the acknowledgment that the rank of the incidence matrix for a graph G with a number of connected components c(G) is n-c(G), where n is the number of vertices in that graph.

Then, we can show that the rank of the Laplacian Matrix L is equal to the rank of the Incidence Matrix M for G, i.e.$rank(L)=rank(M)$.

It is because: $L = MM^{T}$ and for a given vector v, if $Lv=MM^{T}v=0$, we have $v^{T}MM^{T}v=0$, i.e. $||M^{T}v||=0$, hence $M^{T}v=0$; On the other hand, if $M^{T}v=0$, we have $MM^{T}v$ for sure. That is to say, $L$ and $M^T$ has same Kernel, given that they share the same number of columns, i.e. both equal to n, we know $rank(L)=rank(M)$ by Rank–nullity theorem