Editing Laplacian matrix (section)

== Properties ==
For an (undirected) graph ''G'' and its Laplacian matrix ''L'' with [[eigenvalues]] <math display="inline">\lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}</math>:

* ''L'' is [[symmetric matrix|symmetric]].
* ''L'' is [[positive-definite matrix|positive-semidefinite]] (that is <math display="inline">\lambda_i \ge 0</math> for all <math display="inline">i</math>). This can be seen from the fact that the Laplacian is symmetric and [[diagonally dominant matrix#Applications and properties|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, <math display="inline">\lambda_0 = 0</math>, because the vector <math display="inline">\mathbf{v}_0 = (1, 1, \dots, 1)</math> satisfies <math display="inline">L \mathbf{v}_0 = \mathbf{0} .</math> This also implies that the Laplacian matrix is singular.
* The number of [[Connected component (graph theory)|connected components]] in the graph is the dimension of the [[kernel (linear algebra)|nullspace]] of the Laplacian and the [[Eigenvalues and eigenvectors#Algebraic multiplicity|algebraic multiplicity]] of the 0 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 [[cut (graph_theory)#Sparsest cut|sparsest cut]] of a graph.
* The [[Laplacian]] is an operator on the n-dimensional vector space of functions <math display="inline">f : V \to \mathbb{R}</math>, where <math display="inline">V</math> is the vertex set of G, and <math display="inline">n = |V|</math>.
* When G is [[K-regular graph|k-regular]], the normalized Laplacian is: <math display="inline">\mathcal{L} = \tfrac{1}{k} L = I - \tfrac{1}{k} A</math>, where A is the adjacency matrix and I is an identity matrix.
* For a graph with multiple [[Connected component (graph theory)|connected components]], ''L'' is a [[Block matrix#Block diagonal matrices|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 <math display="inline">2m</math> where <math display="inline">m</math> is the number of edges of the considered graph.
* Now consider an eigendecomposition of <math display="inline">L</math>, with unit-norm eigenvectors <math display="inline">\mathbf{v}_i</math> and corresponding eigenvalues <math display="inline">\lambda_i</math>:
:<math>\begin{align}
  \lambda_i & = \mathbf{v}_i^\textsf{T} L \mathbf{v}_i \\
            & = \mathbf{v}_i^\textsf{T} M^\textsf{T} M \mathbf{v}_i \\
            & = \left(M \mathbf{v}_i\right)^\textsf{T} \left(M \mathbf{v}_i\right). \\
\end{align}</math>

Because <math display="inline">\lambda_i</math> can be written as the inner product of the vector <math display="inline">M \mathbf{v}_i</math> with itself, this shows that <math display="inline">\lambda_i \ge 0</math> and so the eigenvalues of <math display="inline">L</math> are all non-negative.
* All eigenvalues of the normalized symmetric Laplacian satisfy 0 = μ<sub>0</sub> ≤ … ≤ μ<sub>n−1</sub> ≤ 2. These eigenvalues (known as the spectrum of the normalized Laplacian) relate well to other graph invariants for general graphs.<ref name="Fan Chung" />

* One can check that:
: <math>L^\text{rw} = I-D^{-\frac{1}{2}}\left(I - L^\text{sym}\right) D^\frac{1}{2}</math>,

i.e., <math display="inline">L^\text{rw}</math> is [[Matrix_similarity | similar]] to the normalized Laplacian <math display="inline">L^\text{sym}</math>. For this reason, even if <math display="inline">L^\text{rw}</math> is in general not symmetric, it has real eigenvalues — exactly the same as the eigenvalues of the normalized symmetric Laplacian <math display="inline">L^\text{sym}</math>.