Editing Laplacian matrix (section)

=== Symmetric Laplacian via the incidence matrix ===
[[Image:elastic network model.png|thumb|A 2-dimensional spring system.]]
For graphs with weighted edges one can define a weighted incidence matrix ''B'' and use it to construct the corresponding symmetric Laplacian as <math>L = B B^\textsf{T}</math>. An alternative cleaner approach, described here, is to separate the weights from the connectivity: continue using the [[incidence matrix]] as for regular graphs and introduce a matrix just holding the values of the weights. A [[spring system]] is an example of this model used in [[mechanics]] to describe a system of springs of given stiffnesses and unit length, where the values of the stiffnesses play the role of the weights of the graph edges.

We thus reuse the definition of the weightless <math display="inline">|v| \times |e|</math> [[incidence matrix]] ''B'' with element ''B''<sub>''ve''</sub> for the vertex ''v'' and the edge ''e'' (connecting vertexes <math display="inline">v_i</math> and <math display="inline">v_j</math>, with ''i''&nbsp;>&nbsp;''j'') defined by
:<math>B_{ve} = \left\{\begin{array}{rl}
   1, & \text{if } v = v_i\\
  -1, & \text{if } v = v_j\\
   0, & \text{otherwise}.
\end{array}\right.</math>

We now also define a diagonal <math display="inline">|e| \times |e|</math> matrix ''W'' containing the edge weights. Even though the edges in the definition of ''B'' are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian <math display="inline">|v| \times |v|</math> matrix ''L'' defined as
:<math>L = B W B^\textsf{T}</math>
where <math display="inline">B^\textsf{T}</math> is the [[transpose|matrix transpose]] of ''B''.

The construction is illustrated in the following example, where every edge <math display="inline">e_i</math> is assigned the weight value ''i'', with <math display="inline">i=1, 2, 3, 4.</math>
{|class="wikitable"
! [[Undirected graph]]
! [[Incidence matrix]]
! Edge weights
! Laplacian matrix
|-
| [[image:Labeled_undirected_graph.svg|100px]]
| <math display="inline">\left(\begin{array}{rrrr}
   1 &  1 &  1 &  0\\
  -1 &  0 &  0 &  0\\
   0 & -1 &  0 &  1\\
   0 &  0 & -1 & -1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   1 &  0 &  0 &  0\\
   0 &  2 &  0 &  0\\
   0 &  0 &  3 &  0\\
   0 &  0 &  0 &  4\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   6 &  -1 &  -2 & -3\\
  -1 &   1 &   0 &  0\\
  -2 &   0 &   6 & -4\\
  -3 &   0 &   -4 & 7\\
\end{array}\right)</math>
|}