eigenvalue. The smallest non-zero eigenvalue of L is called the spectral gap. The second smallest eigenvalue of L (could be zero) is the algebraic connectivity (or Fiedler value) of G and approximates the sparsest cut of a graph. The Laplacian is an operator on the n-dimensional vector space of functions , where is the vertex set of G, and . When G is k-regular, the normalized Laplacian is: , where A is the adjacency matrix and I is an identity matrix. For a graph with multiple connected components, L is a block diagonal matrix, where each block is the respective Laplacian matrix for each component, possibly after reordering the vertices (i.e. L is permutation-similar to a block diagonal matrix). The trace of the Laplacian matrix L is equal to where is the number of edges of the considered graph. Now consider an eigendecomposition of , with unit-norm eigenvectors and corresponding eigenvalues : Because can be written as the inner product of the vector with itself, this shows that and so the eigenvalues of are all non-negative. All eigenvalues of the normalized symmetric Laplacian satisfy 0 = μ0 ≤ … ≤ μn−1 ≤ 2. These eigenvalues (known as the spectrum of the normalized Laplacian) relate well to other graph invariants for general graphs. One can check that: , i.e., is similar to the normalized Laplacian . For this reason, even if is in general not symmetric, it has real eigenvalues — exactly the same as the eigenvalues of the normalized symmetric Laplacian . Interpretation as the discrete Laplace operator approximating the continuous Laplacian The graph Laplacian matrix can be further viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian operator obtained by the finite difference method. (See Discrete Poisson equation) In this interpretation, every graph vertex is treated as a grid point; the local connectivity of the vertex determines the finite difference approximation stencil at this grid point, the grid size is always one for every edge, and there are no constraints on any grid points, which corresponds to the case of the homogeneous Neumann boundary condition, i.e., free boundary. Such an interpretation allows one, e.g., generalizing the Laplacian matrix to the case of graphs with an infinite number of vertices and edges, leading to a Laplacian matrix of an infinite size. Generalizations and extensions of the Laplacian matrix Generalized Laplacian