Editing Laplacian matrix (section)

{{Use American English|date = March 2019}}
{{Short description|Matrix representation of a graph}}
In the [[mathematics|mathematical]] field of [[graph theory]], the '''Laplacian matrix''', also called the '''[[Discrete_Laplace_operator#Graph_Laplacians|graph Laplacian]]''', '''[[admittance matrix]]''', '''Kirchhoff matrix,''' or '''[[Discrete Laplace operator|discrete Laplacian]]''', is a [[matrix (mathematics)|matrix]] representation of a [[Graph (discrete mathematics)|graph]]. Named after [[Pierre-Simon Laplace]], the graph Laplacian matrix can be viewed as a matrix form of the negative [[discrete Laplace operator]] on a graph approximating the negative continuous [[Laplacian]] obtained by the [[finite difference method]].

The Laplacian matrix relates to many functional graph properties. [[Kirchhoff's theorem]] can be used to calculate the number of [[spanning tree (mathematics)|spanning tree]]s for a given graph. The [[cut (graph theory)#Sparsest cut|sparsest cut]] of a graph can be approximated through the [[Fiedler vector]] — the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian — as established by [[Cheeger constant (graph theory)#Cheeger Inequalities|Cheeger's inequality]]. The [[Eigendecomposition of a matrix|spectral decomposition]] of the Laplacian matrix allows the construction of [[nonlinear dimensionality reduction#Laplacian eigenmaps|low-dimensional embeddings]] that appear in many [[machine learning]] applications and determines a [[spectral layout]] in [[graph drawing]]. Graph-based [[signal processing]] is based on the [[graph Fourier transform]] that extends the traditional [[discrete Fourier transform]] by substituting the standard basis of [[complex number|complex]] [[Sine wave|sinusoid]]s for eigenvectors of the Laplacian matrix of a graph corresponding to the signal.

The Laplacian matrix is the easiest to define for a [[simple graph]] but more common in applications for an [[Glossary_of_graph_theory#weighted_graph|edge-weighted graph]], i.e., with weights on its edges — the entries of the graph [[adjacency matrix]]. [[Spectral graph theory]] relates properties of a graph to a spectrum, i.e., eigenvalues and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. Imbalanced weights may undesirably affect the matrix spectrum, leading to the need of normalization — a column/row scaling of the matrix entries — resulting in normalized adjacency and Laplacian matrices.