The whole point is that the matrix in question is not singular, it is symmetric positive definite. As is common in this sort of paper, many ordinary mathematical comments are left unsaid. Just before equation (1), we find out that $W$ is a real symmetric matrix of strictly positive numbers, called "weights." It need not be positive definite itself. Just before equation (3), we find out that $D$ is the diagonal matrix with $ d_{ii} = \sum_{j=1}^n \; w_{ij}.$ Next, we find $ \Delta = D - W. $ Now, as an $n$ by $n$ matrix, $\Delta$ is symmetric and singular, by construction the vector with every entry equal to $1$ is a null vector.
However, they then go on to take submatrices, starting with formula (4). By the time we get to formula (5), we find that your $ L = D_{uu} - W_{uu} $ is invertible, the reason for this being, in fact, that it is positive definite. This requires proof, and I will put that in when I have time. For now, note these examples: if $n=2$ and $ W \; = \; \left( \begin{array}{cc} a & b \\ b & c \end{array} \right) , $ then $ D -W \; = \; \left( \begin{array}{cc} b & -b \\ -b & b \end{array} \right) , $ and the only possible submatrix is 1 by 1, $ L = (b). $
If $n=3$ and $ W \; = \; \left( \begin{array}{ccc} a & f & e \\ f & b & d \\ e & d & c \end{array} \right) , $ then $ D - W \; = \; \left( \begin{array}{ccc} e + f & -f & -e \\ -f & f + d & -d \\ -e & -d & d + e \end{array} \right) , $ and the possible lower right corners are either 1 by 1 $ L = (d + e) $ or two by two $ L \; = \; \left( \begin{array}{cc} f + d & -d \\ -d & d + e \end{array} \right) . $ Because we required $a,b,c,d,e,f$ to be strictly positive, the possible matrix $L$s depicted are positive definite.
Still looking for a simple proof, but this is what is going on: Let $U$ be a symmetric real matrix of strictly positive elements. Let $T$ be the diagonal matrix such that $T_{ii} = \sum_{j} U_{ij}.$ Then let $S = T - U,$ so that $S$ is symmetric with row-sums all vanishing. The theorem is that $S$ is positive semidefinite. When we then increase the diagonal elements of $S$ by positive reals to arrive at the original $L$ above, the result is positive definite.