Editing Laplacian matrix (section)

==== Symmetrically normalized Laplacian ====

The '''symmetrically normalized Laplacian''' is defined as
: <math>L^\text{sym} := (D^+)^{1/2} L (D^+)^{1/2} = I - (D^+)^{1/2} A (D^+)^{1/2},</math>

where ''L'' is the unnormalized Laplacian, ''A'' is the adjacency matrix, ''D'' is the degree matrix, and <math>D^+</math> is the [[Moore–Penrose inverse]]. Since the degree matrix ''D'' is diagonal, its reciprocal square root <math display="inline">(D^+)^{1/2}</math> is just the diagonal matrix whose diagonal entries are the reciprocals of the square roots of the diagonal entries of ''D''. If all the edge weights are nonnegative then all the degree values are automatically also nonnegative and so every degree value has a unique positive square root. To avoid the division by zero, vertices with zero degrees are excluded from the process of the normalization, as in the following example:
{|class="wikitable"
! [[Adjacency matrix]]
! In-Degree matrix
! In-Degree normalized Laplacian
! Out-Degree matrix
! Out-Degree normalized Laplacian
|-
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  0\\
  4 &  0 &  0\\
  0 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  4 &  0\\
  0 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1/2 &  0\\
  -2 &  1 &  0\\
   0 &  0 &  0\\\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  4 &  0 &  0\\
  0 &  1 &  0\\
  0 &  0 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1/2 &  0\\
  -2 &  1 &  0\\
   0 &  0 &  0\\
\end{array}\right)</math>
|}

The symmetrically normalized Laplacian is a symmetric matrix if and only if the adjacency matrix ''A'' is symmetric and the diagonal entries of ''D'' are nonnegative, in which case we can use the term the '''''symmetric normalized Laplacian'''''.

The symmetric normalized Laplacian matrix can be also written as 
: <math>L^\text{sym} := (D^+)^{1/2} L (D^+)^{1/2} = (D^+)^{1/2}B W B^\textsf{T} (D^+)^{1/2} = S S^T</math>
using the weightless <math display="inline">|v| \times |e|</math> [[incidence matrix]] ''B'' and the diagonal <math display="inline">|e| \times |e|</math> matrix ''W'' containing the edge weights and defining the new <math display="inline">|v| \times |e|</math> weighted incidence matrix <math display="inline">S=(D^+)^{1/2}B W^{{1}/{2}}</math> whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edge ''e = {u, v}'' has an entry <math display="inline">\frac{1}{\sqrt{d_u}}</math> in the row corresponding to ''u'', an entry <math display="inline">-\frac{1}{\sqrt{d_v}}</math> in the row corresponding to ''v'', and has 0 entries elsewhere.