Another important symmetric matrix associated with a graph is the Laplacian matrix. This is the matrix [latex]L = A^TA[/latex], with [latex]A[/latex] as the arc-node incidence matrix. It can be shown that the [latex](i, j)[/latex] element of the Laplacian matrix is given by
[latex]\begin{align*} L_{i j} = \begin{cases} \# \operatorname{arcs} \text{ incident to node } i & \text{ if } i=j, \\ -1 & \text{ if there is an arc joining node } i \text{ to node } j, \\ 0 & \text{ otherwise. } \end{cases} \end{align*}[/latex]
See also:
