Prove that grounded Laplacian/reduced conductance matrix is non-singular

Question

Consider a simple, connected graph $G = (V,E)$ with $|V| = n $. The Laplacian matrix $L$ is defined as $L = D - A$, where $D$ is the diagonal matrix with $D_{ii} = \text{degree of node $i$}$, and $A$ is the adjacency matrix with $A_{ij} = 1$ if $(i, j) \in E$ and zero otherwise.

Prove that the reduced $(n-1) \times (n-1) $ matrix $\tilde{L}$, obtained by deleting the $k^{th}$ row and $k^{th}$ column from $L$ is non-singular ($k \in \{1,\dots,n\}$). The matrix $\tilde{L}$ has been called grounded Laplacian matrix, reduced Laplacian matrix, or reduced conductance matrix.

I have found many research papers (e.g. see references below) quoting this fact, but I was unable to find a proof.

Yuan, Y.; Stan, G.-B.; Shi, L.; Barahona, M.; Goncalves, J., Decentralised minimum-time consensus, Automatica 49, No. 5, 1227-1235 (2013). ZBL1334.68231.

Ghosh, Arpita; Boyd, Stephen; Saberi, Amin, Minimizing effective resistance of a graph, SIAM Rev. 50, No. 1, 37-66 (2008). ZBL1134.05057.

Answer 1

If $G$ is connected, then it has got at least one spanning tree, and by Kirchhoff’s Theorem, any cofactor of $L$ is positive; namely, $\det(\tilde L)>0$.

Answer 2

We know that $L = B B^T$, where $B$ is the edge incidence matrix. Therefore, the grounded Laplacian $\tilde{L}$ is equal to $ \tilde{B} \tilde{B}^T$ where $\tilde{B}$ is the matrix obtained by deleting the $k$th row from $B$. We know from this that $\tilde{L}$ is positive-semidefinite.

To show that $\tilde{L}$ is positive definite, we need to show that $\tilde{B}x = 0$ iff $x$ is the zero vector. The converse direction is trivial. If $\tilde{B}x = 0$, then for any edge $e=(i, j)$, we have

\begin{equation} (\tilde{B}x)_e = \begin{cases} \pm(x_i - x_j) &\quad \text{if $i,j \neq k$,}\\ \pm x_i, &\quad \text{if $i=k$,}\\ \pm x_j &\quad \text{if $j=k$.} \end{cases} \end{equation}

Therefore, for any neighbour $j$ of node $k$, $x_j = 0$. Furthermore, $x_i$ must be the same for all nodes $i$ in the same connected component in the subgraph induced by $\{1,\dots,n\} \setminus \{k\} $. Since $G$ is connected, each connected component has a node that connected to $k$, so that $x_i = 0$ for all $i$, as required.