Editing Laplacian matrix (section)

==== Left (random-walk) and right normalized Laplacians ====

The left (random-walk) normalized Laplacian matrix is defined as:
: <math>L^\text{rw} := D^+L = I - D^+A,</math>
where <math>D^+</math> is the [[Moore–Penrose inverse]].
The elements of <math display="inline">L^\text{rw}</math> are given by
:<math>L^\text{rw}_{i,j} := \begin{cases}
                     1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
  -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
                     0 & \mbox{otherwise}.
\end{cases}</math>

Similarly, the right normalized Laplacian matrix is defined as 
: <math>L D^+ = I - A D^+</math>.

The left or right normalized Laplacian matrix is not symmetric if the adjacency matrix is symmetric, except for the trivial case of all isolated vertices. For example, 
{|class="wikitable"
! [[Adjacency matrix]]
! Degree matrix
! Left normalized Laplacian
! Right normalized Laplacian
|-
| <math display="inline">\left(\begin{array}{rrr}
  0 &  1 &  0\\
  1 &  0 &  1\\
  0 &  1 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
  1 &  0 &  0\\
  0 &  2 &  0\\
  0 &  0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1 &  0\\
   -1/2 &   1 &  -1/2\\
  0&   -1 &   1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
   1 &  -1/2 &  0\\
   -1 &   1 &  -1\\
  0&   -1/2 &   1\\
\end{array}\right)</math>
|}
The example also demonstrates that if <math>G</math> has no isolated vertices, then <math>D^+A</math> [[Stochastic matrix|right stochastic]] and hence is the matrix of a [[random walk]], so that the left normalized Laplacian <math>L^\text{rw} := D^+L = I - D^+A</math> has each row summing to zero. Thus we sometimes alternatively call <math>L^\text{rw}</math> the [[random walk|random-walk]] normalized Laplacian. In the less uncommonly used right normalized Laplacian <math>L D^+ = I - A D^+</math> each column sums to zero since <math>A D^+</math> is [[Stochastic matrix|left stochastic]]. 

For a non-symmetric adjacency matrix of a directed graph, one also needs to choose [[degree (graph theory)|indegree or outdegree]] for normalization:
{|class="wikitable"
! [[Adjacency matrix]]
! Out-Degree matrix
! Out-Degree left normalized Laplacian
! In-Degree matrix
! In-Degree right normalized Laplacian
|-
| <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}
   1 &  -1/2 &  -1/2\\
   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/2\\
   0 &   1 &  -1/2\\
  -1 &   0 &   1\\
\end{array}\right)</math>
|}
The left out-degree normalized Laplacian with row-sums all 0 relates to [[Stochastic matrix|right stochastic]] <math>D_{\text{out}}^+A</math> , while the right in-degree normalized Laplacian  with column-sums all 0 contains [[Stochastic matrix|left stochastic]]  <math>AD_{\text{in}}^+</math>.