location of a random walker on the vertices of the graph, then is the probability distribution of the walker after steps. The random walk normalized Laplacian can also be called the left normalized Laplacian since the normalization is performed by multiplying the Laplacian by the normalization matrix on the left. It has each row summing to zero since is right stochastic, assuming all the weights are non-negative. In the less uncommonly used right normalized Laplacian each column sums to zero since is left stochastic. For a non-symmetric adjacency matrix of a directed graph, one also needs to choose indegree or outdegree for normalization: The left out-degree normalized Laplacian with row-sums all 0 relates to right stochastic , while the right in-degree normalized Laplacian with column-sums all 0 contains left stochastic . Negative weights Negative weights present several challenges for normalisation: The presence of negative weights may naturally result in zero row- and/or column-sums for non-isolated vertices. A vertex with a large row-sum of positive weights and equally negatively large row-sum of negative weights, together summing up to zero, could be considered a heavy node and both large values scaled, while the diagonal entry remains zero, like for a isolated vertex. Negative weights may also give negative row- and/or column-sums, so that the corresponding diagonal entry in the non-normalized Laplacian matrix would be negative and a positive square root needed for the symmetric normalization would not exist. Arguments can be made to take the absolute value of the row- and/or column-sums for the purpose of normalization, thus treating a possible value -1 as a legitimate unit entry of the main diagonal of the normalized Laplacian matrix. Properties For an (undirected) graph G and its Laplacian matrix L with eigenvalues : L is symmetric. L is positive-semidefinite (that is for all ). This can be seen from the fact that the Laplacian is symmetric and diagonally dominant. L is an M-matrix (its off-diagonal entries are nonpositive, yet the real parts of its eigenvalues are nonnegative). Every row sum and column sum of L is zero. Indeed, in the sum, the degree of the vertex is summed with a "−1" for each neighbor. In consequence, , because the vector satisfies This also implies that the Laplacian matrix is singular. The number of connected components in the graph is the dimension of the nullspace of the Laplacian and the algebraic multiplicity of the 0