Editing Laplacian matrix (section)

=== Laplacian matrix ===
Given a [[simple graph]] <math>G</math> with <math>n</math> vertices <math>v_1, \ldots, v_n</math>, its Laplacian matrix <math display="inline">L_{n \times n}</math> is 
defined element-wise as<ref name="Fan Chung">{{cite book
| last                  = Chung
| first                 = Fan
| author-link            = Fan Chung
| title                 = Spectral Graph Theory
| url                   = http://www.math.ucsd.edu/~fan/research/revised.html
| orig-year              = 1992
| year                  = 1997
| publisher             = American Mathematical Society
| isbn                  = 978-0821803158
}}</ref>
: <math>L_{i,j} := \begin{cases}
  \deg(v_i) & \mbox{if}\ i = j \\
         -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
          0 & \mbox{otherwise},
\end{cases}</math>
or equivalently by the matrix 
: <math>L = D - A, </math>

where ''D'' is the [[degree matrix]], and ''A'' is the graph's [[adjacency matrix]]. Since <math display="inline">G</math> is a simple graph, <math display="inline">A</math> only contains 1s or 0s and its diagonal elements are all 0s.

Here is a simple example of a labelled, undirected graph and its Laplacian matrix.

{|class="wikitable"
! [[Labelled graph]]
! [[Degree matrix]]
! [[Adjacency matrix]]
! Laplacian matrix
|-
| [[image:6n-graf.svg|175px]]
| <math display="inline">\left(\begin{array}{rrrrrr}
  2 &  0 &  0 &  0 &  0 &  0\\
  0 &  3 &  0 &  0 &  0 &  0\\
  0 &  0 &  2 &  0 &  0 &  0\\
  0 &  0 &  0 &  3 &  0 &  0\\
  0 &  0 &  0 &  0 &  3 &  0\\
  0 &  0 &  0 &  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrrrr}
  0 &  1 &  0 &  0 &  1 &  0\\
  1 &  0 &  1 &  0 &  1 &  0\\
  0 &  1 &  0 &  1 &  0 &  0\\
  0 &  0 &  1 &  0 &  1 &  1\\
  1 &  1 &  0 &  1 &  0 &  0\\
  0 &  0 &  0 &  1 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrrrr}
   2 & -1 &  0 &  0 & -1 &  0\\
  -1 &  3 & -1 &  0 & -1 &  0\\
   0 & -1 &  2 & -1 &  0 &  0\\
   0 &  0 & -1 &  3 & -1 & -1\\
  -1 & -1 &  0 & -1 &  3 &  0\\
   0 &  0 &  0 & -1 &  0 &  1\\
\end{array}\right)  </math>
|}
We observe for the undirected graph that both the [[adjacency matrix]] and the Laplacian matrix are symmetric and that the row- and column-sums of the Laplacian matrix are all zeros (which directly implies that the Laplacian matrix is singular).

For [[directed graph]]s, either the [[degree (graph theory)|indegree or outdegree]] might be used, depending on the application, as in the following example:
{|class="wikitable"
!Labelled graph
! [[Adjacency matrix]]
! Out-Degree matrix
! Out-Degree Laplacian
! In-Degree matrix
! In-Degree Laplacian
|-
|[[File:3 node Directed graph.png|center|100x100px]]
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  1\\
  0 &  0 &  1\\
  1 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  2 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   2 &  -1 &  -1\\
   0 &   1 &  -1\\
  -1 &   0 &   1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  2\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1 &  -1\\
   0 &   1 &  -1\\
  -1 &   0 &   2\\
\end{array}\right)</math>
|}
In the directed graph, the [[adjacency matrix]] and Laplacian matrix are asymmetric. In its Laplacian matrix, column-sums or row-sums are zero, depending on whether the [[degree (graph theory)|indegree or outdegree]] has been used.