Editing Laplacian matrix (section)

== Generalizations and extensions of the Laplacian matrix ==
 
=== Generalized Laplacian ===
The generalized Laplacian <math>Q</math> is defined as:<ref>{{cite book |last1= Godsil |first1=C. |last2= Royle |first2=G. |date=2001 |title=Algebraic Graph Theory, Graduate Texts in Mathematics |publisher= Springer-Verlag}}</ref>
: <math>\begin{cases}
        Q_{i,j} < 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\
        Q_{i,j} = 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\
  \mbox{any number} & \mbox{otherwise}.
\end{cases}</math>

Notice the ordinary Laplacian is a generalized Laplacian.

===Admittance matrix of an AC circuit===
The Laplacian of a graph was first introduced to model electrical networks.
In an alternating current (AC) electrical network, real-valued resistances are replaced by complex-valued impedances.
The weight of edge (''i'', ''j'') is, by convention, ''minus'' the reciprocal of the impedance directly between ''i'' and ''j''.
In models of such networks, the entries of the [[adjacency matrix]] are complex, but the Kirchhoff matrix remains symmetric, rather than being [[Hermitian]].
Such a matrix is usually called an "[[admittance matrix]]", denoted <math>Y</math>, rather than a "Laplacian".
This is one of the rare applications that give rise to [[Symmetric_matrix#Complex|complex symmetric matrices]].

{|class="wikitable"
! [[Adjacency matrix]]
! Weighted degree matrix
! Admittance matrix
|-
| <math display="inline">\left(\begin{array}{rrrr}
   0 &  i &  0 &  0\\
   i &  0 &  1-2i &  0\\
   0 &  1-2i &  0 &  1\\
   0 &  0 &  1 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   i &  0 &  0 &  0\\
   0 &  1-i &  0 &  0\\
   0 &  0 &  2-2i &  0\\
   0 &  0 & 0 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   -i &  i &  0 &  0\\
   i &  -1+i &  1-2i &  0\\
   0 &  1-2i &  -2+2i & 1\\
   0 &  0 &  1 &  -1\\
\end{array}\right)</math>
|}

=== Magnetic Laplacian ===
There are other situations in which entries of the adjacency matrix are complex-valued, and the Laplacian does become a [[Hermitian matrix]]. The Magnetic Laplacian for a directed graph with real weights <math>w_{ij}</math>  is constructed  as the [[Hadamard product (matrices)|Hadamard product]] of the [[Symmetric_matrix#Real_symmetric_matrices|real symmetric matrix]] of the symmetrized Laplacian and the Hermitian phase matrix with the [[complex number|complex]] entries
:<math>\gamma_q(i, j) = e^{i2 \pi q(w_{ij}-w_{ji})}</math>
which encode the edge direction into the phase in the complex plane.
In the context of quantum physics, the magnetic Laplacian can be interpreted as the operator that describes the phenomenology of a free charged particle on a graph, which is subject to the action of a magnetic field and the parameter <math>q</math>  is called electric charge.<ref>{{cite conference|title=Graph Signal Processing for Directed Graphs based on the Hermitian Laplacian | conference=ECML PKDD 2019: Machine Learning and Knowledge Discovery in Databases |pages=447–463 |year=2020|doi= 10.1007/978-3-030-46150-8_27|url=https://ecmlpkdd2019.org/downloads/paper/499.pdf |author1=Satoshi Furutani |author2=Toshiki Shibahara|author3= Mitsuaki Akiyama|author4= Kunio Hato|author5=Masaki Aida }}</ref>
In the following example <math>q=1/4</math>:
{|class="wikitable"
! [[Adjacency matrix]]
! Symmetrized Laplacian
! Phase matrix
! Magnetic Laplacian
|-
| <math display="inline">\left(\begin{array}{rrrr}
   0 &  1 &  0 &  0\\
   1 &  0 &  1 &  0\\
   0 &  0 &  0 &  0\\
   0 &  0 &  1 &  0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   2 &  -2 &  0 &  0\\
   -2 &  3 &  -1 &  0\\
   0 &  -1 &  2 &  -1\\
   0 &  0 &  -1 &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   1 &  1 &  1 &  1\\
   1 &  1 &  i &  1\\
   1 &  -i &  1 & -i\\
   1 &  1 &  i &  1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
   2 & -2  &  0 & 0\\
   -2 & 3  & -i  &  0\\
  0 &   i &   2 & i\\
  0 &   0 &   -i & 1\\
\end{array}\right)</math>
|}

=== Deformed Laplacian ===

The '''deformed Laplacian''' is commonly defined as

:<math>\Delta(s) = I - sA + s^2(D - I)</math>

where ''I'' is the identity matrix, ''A'' is the adjacency matrix, ''D'' is the degree matrix, and ''s'' is a (complex-valued) number. <ref>{{cite journal |title=The Deformed Consensus Protocol |first=F. |last=Morbidi |journal=Automatica |volume=49 |number=10 |pages=3049–3055 |year=2013 |doi=10.1016/j.automatica.2013.07.006|s2cid=205767404 |url=http://hal.archives-ouvertes.fr/docs/00/96/14/91/PDF/Morbidi_AUTO13_ExtVer.pdf }}</ref><br /> The standard Laplacian is just <math display="inline">\Delta(1)</math> and <math display="inline">\Delta(-1) = D + A</math> is the signless Laplacian.

=== Signless Laplacian ===
The '''signless Laplacian''' is defined as
:<math>Q = D + A</math>
where  <math>D</math> is the degree matrix, and <math>A</math> is the adjacency matrix.<ref>{{Cite journal|last1=Cvetković|first1=Dragoš|last2=Simić|first2=Slobodan K.|date=2010|journal=Applicable Analysis and Discrete Mathematics|volume=4|issue=1|pages=156–166|issn=1452-8630|jstor=43671298|title=Towards a Spectral Theory of Graphs Based on the Signless Laplacian, III|doi=10.2298/AADM1000001C|doi-access=free}}</ref> Like the signed Laplacian <math>L</math>, the signless Laplacian <math>Q</math> also is positive semi-definite as it can be factored as
:<math>Q = RR^\textsf{T}</math>
where <math display="inline">R</math> is the incidence matrix. <math>Q</math> has a 0-eigenvector if and only if it has a bipartite connected component (isolated vertices being bipartite connected components). This can be shown as
:<math>\mathbf{x}^\textsf{T} Q \mathbf{x} = \mathbf{x}^\textsf{T} R R^\textsf{T} \mathbf{x} \implies R^\textsf{T} \mathbf{x} = \mathbf{0}.</math>
This has a solution where <math>\mathbf{x} \neq \mathbf{0}</math> if and only if the graph has a bipartite connected component.

=== Directed multigraphs ===
An analogue of the Laplacian matrix can be defined for directed multigraphs.<ref name="Chaiken1978">{{cite journal
 | title = Matrix Tree Theorems 
 | author1=Chaiken, S. | author2=Kleitman, D. | author-link2=Daniel Kleitman
 | journal = Journal of Combinatorial Theory, Series A 
 | volume = 24
 | number = 3
 | pages = 377–381
 | year = 1978
 | issn = 0097-3165
 | doi=10.1016/0097-3165(78)90067-5
| doi-access = free
 }}</ref> In this case the Laplacian matrix ''L'' is defined as
:<math>L = D - A</math>

where ''D'' is a diagonal matrix with ''D''<sub>''i'',''i''</sub> equal to the outdegree of vertex ''i'' and ''A'' is a matrix with ''A''<sub>''i'',''j''</sub> equal to the number of edges from ''i'' to ''j'' (including loops).