what is the formula of laplacian matrix
- User
what is the formula of laplacian matrix
Assistant
The Laplacian matrix of a graph G = (V, E) with n vertices can be defined in several equivalent ways:
Basic Definition
The standard definition of the Laplacian matrix L is:
L = D - A
Where:
- D is the diagonal degree matrix with D(i,i) = d(i), the degree of vertex i
- A is the adjacency matrix of the graph[1][6][8]
Element-wise, the Laplacian matrix entries are given by:
- L(i,i) = d(i) (degree of vertex i) on the diagonal
- L(i,j) = -1 if vertices i and j are adjacent
- L(i,j) = 0 otherwise[1][6]
Alternative Formulations
Incidence Matrix Form
The Laplacian can also be expressed using the incidence matrix B:
L = B·B^T
Where B is the incidence matrix of the graph. This formulation demonstrates that L is positive semi-definite[3][6].
Quadratic Form
The Laplacian can be understood through its quadratic form:
x^T·L·x = Σ(x_i - x_j)²
where the sum is over all pairs (i,j) where vertices i and j are adjacent. This formula directly shows that L is positive semi-definite[3][8].
Normalized Laplacian Variants
Symmetrically Normalized Laplacian
L_sym = D^(-1/2)·L·D^(-1/2) = I - D^(-1/2)·A·D^(-1/2)
Where D^(-1/2) is the diagonal matrix with entries 1/√d(i)[6][7].
Random-Walk Normalized Laplacian
L_rw = D^(-1)·L = I - D^(-1)·A
This variant is closely related to random walks on the graph[6][7].
Laplacian for Weighted Graphs
For a weighted graph where edge (i,j) has weight w_ij:
- L(i,i) = sum of weights of all edges incident to vertex i
- L(i,j) = -w_ij if vertices i and j are adjacent
- L(i,j) = 0 otherwise[7]
The corresponding quadratic form is:
x^T·L·x = (1/2)·Σ w_ij(x_i - x_j)²
Key Properties
- L is symmetric for undirected graphs
- L is positive semi-definite
- The smallest eigenvalue of L is always 0
- The multiplicity of the 0 eigenvalue equals the number of connected components in the graph
- For a connected graph, the second smallest eigenvalue (algebraic connectivity or Fiedler value) is related to how well-connected the graph is[1][3][6]
The Laplacian matrix is widely used in spectral graph theory and has applications in graph partitioning, spanning tree enumeration, and network analysis.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.