title: Matriz laplaciana
text: # Matriz laplaciana
  
  En teoría de grafos la matriz laplaciana — también denominada matriz de admitancia o matriz de Kirchhoff — es una representación matricial de un grafo. Otro tipo de representación matricial la proporciona la matriz de adyacencia, pero la matriz laplaciana es ideal para realizar la teoría espectral de grafos.
  
  ## Definición
  
  Dado un grafo G con n nodos, la matriz laplaciana $L:=(\ell _{i,j})_{n\times n}$ se define como:
  
      $\ell _{i,j}:={\begin{cases}\kappa _{i}&{\mbox{si}}\ i=j\\-1&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ n_{i}{\mbox{ es adyacente a }}n_{j}\\0&{\mbox{otro caso}}.\end{cases}}$
  
  siendo $\kappa _{i}$ el grado del nodo i-ésimo $n_{i}$. La matriz laplaciana normalizada ${\mathcal {L}}:=({\hat {\ell }}_{i,j})_{n\times n}$ se define como:
  
      ${\hat {\ell }}_{i,j}:={\begin{cases}1&{\mbox{si}}\ i=j\ {\mbox{y}}\ \kappa _{i}\neq 0\\-{\frac {1}{\sqrt {\kappa _{i}\kappa _{j}}}}&{\mbox{si}}\ i\neq j\ {\mbox{y}}\ n_{i}{\mbox{ es adyacente a }}n_{j}\\0&{\mbox{otro caso}}.\end{cases}}$
  
  Tomando ${\hat {T}}$ como la matriz diagonal de elementos $(i,i)$ de entrada $\kappa _{i}$, se tiene que:
  
      ${\hat {\mathcal {L}}}={\hat {T}}^{-1/2}{\hat {L}}{\hat {T}}^{-1/2}$
  
  con la convención $({\hat {T}}^{-1})_{v,v}=0$ para $\kappa _{v}=0$.
  
  ## Propiedades
  
  ### Relación con la matriz de adyacencias
  
  Cuando el grafo $\Gamma$ es k-regular se puede observar que:
  
      ${\hat {\mathcal {L}}}={\hat {\mathbb {I} }}-{\frac {1}{k}}{\hat {A}}$
  
  donde $A$ es la matriz de adyacencias y ${\hat {\mathbb {I} }}$ es la identidad. Para un grafo sin vértices aislados, tenemos entonces que:
  
      ${\hat {\mathcal {L}}}={\hat {T}}^{-1/2}{\hat {L}}{\hat {T}}^{-1/2}={\hat {\mathbb {I} }}-{\hat {T}}^{-1/2}{\hat {A}}{\hat {T}}^{-1/2}$.
  
  ### Ejemplo
  
  Ejemplo de la representación en forma de grafo de una red y su representación matricial laplaciana:
  
  | grafo | matriz laplaciana |
  | - | - |
  | | $\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)$ |
  
  ### Espectro de ${\hat {\mathcal {L}}}$
  
  Para un grafo $\Gamma$ y matriz laplaciana $L(\Gamma )$, con los autovalores ordenados (el espectro de $L$) $\lambda _{0}\leqslant \lambda _{1}\leqslant \dotsc \leqslant \lambda _{n-1}$:
  
  * La matriz laplaciana es siempre definida positiva.
  * El primer autovalor $\lambda _{0}=0$ es siempre nulo; existe un autovector que es siempre $[1,1,\dots ,1]$. La multiplicidad de $\lambda _{0}$ indica el número de subgrafos inconexos que hay.
  * El segundo autovalor no nulo $\lambda _{2}$ se denomina conectividad algebraica. Es una medida de la conectividad del grafo. A medida que $\lambda _{2}$ se hace más pequeño el grafo adquiere una estructura más modular. A través de la percolación a través de un grafo, la sincronización máxima se da para el valor más alto posible de $\lambda _{2}$. También se denomina salto espectral, gap o parámetro de Fiedler.
  