Skip to content
TheChatArchiveThe Chat Archive
Perplexitysonar-reasoning-pro-high· PerplexityHugging Face LMArena Search Arena 24K

what is the formula of laplacian matrix

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Perplexitysonar-reasoning-pro-high’s answer.
  1. User

    what is the formula of laplacian matrix

  2. Perplexity Assistant

    The Laplacian matrix of a graph, also known as the Kirchhoff matrix or admittance matrix, is a matrix representation that captures the structural properties of a graph. For a simple undirected graph G with n vertices, the standard formula for the Laplacian matrix L is:

    Standard Laplacian Matrix Formula

    L = D - A

    Where:

    • D is the degree matrix (a diagonal matrix where D[i,i] equals the degree of vertex i)
    • A is the adjacency matrix of the graph[1][6]

    The entries of the Laplacian matrix are defined element-wise as:

    • L[i,j] = -1 if vertices i and j are adjacent
    • L[i,j] = d(i) if i = j (where d(i) is the degree of vertex i)
    • L[i,j] = 0 otherwise[1][6]

    Alternative Formulations

    The Laplacian matrix can also be expressed as a product of the incidence matrix:

    L = BBᵀ

    Where B is the incidence matrix of the graph[3][6]. If we assign an orientation to the edges of the graph (which direction doesn't matter for the result), the incidence matrix B has entries:

    • B[i,e] = 1 if edge e starts at vertex i
    • B[i,e] = -1 if edge e ends at vertex i
    • B[i,e] = 0 otherwise[6]

    Quadratic Form Representation

    The Laplacian matrix can be characterized by its quadratic form:

    xᵀLx = ∑(i,j)∈E (xᵢ - xⱼ)²

    Where x is a vector, and the sum is taken over all pairs of adjacent vertices[3][7]. This form highlights the Laplacian's role as a discrete analog of the Laplace operator.

    Normalized Laplacian Matrices

    There are several normalized versions of the Laplacian matrix:

    1. Symmetrically Normalized Laplacian: Lₙ = D⁻¹/²LD⁻¹/² = I - D⁻¹/²AD⁻¹/² Where D⁻¹/² is the diagonal matrix with D⁻¹/²[i,i] = 1/√d(i)[6][7]

    2. Random Walk (Left) Normalized Laplacian: Lᵣ = D⁻¹L = I - D⁻¹A This is also called the random-walk normalized Laplacian as it relates to transition probabilities in random walks on graphs[6][7]

    For Weighted Graphs

    For a weighted graph, the formula extends to:

    • L[i,j] = -w(i,j) if vertices i and j are adjacent with weight w(i,j)
    • L[i,j] = ∑ₖ w(i,k) if i = j (sum of weights of edges incident to vertex i)
    • L[i,j] = 0 otherwise[7]

    The Laplacian matrix is fundamental in spectral graph theory and has numerous applications in graph partitioning, graph drawing, and network analysis. Its eigenvalues (called the spectrum of the graph) provide important insights into the graph's structural properties.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.