Admittance matrix

Encyclopedia : A : AD : ADM : Admittance matrix

In the mathematical field of graph theory the admittance matrix, Kirchhoff matrix, or Laplacian matrix is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph.

Definition

The admittance matrix of a graph G is defined as

[L := D - A]

with D the degree matrix of G and A the adjacency matrix of G.

More explicitly, given a graph G with n vertices the admittance matrix [L:=(l_)_] is defined as

[l_:=\left\ \deg(v_i) & \mbox\ i = j \\-1 & \mbox\ i \neq j\ \mbox\ v_i\ \mbox\ v_j \\0 & \mbox\end\right.]

In the case of directed graphs, either the indegree or the outdegree might be used, depending on the application.

For a graph G and its admittance matrix L with eigenvalues [\lambda_0 \le \lambda_1 \le \ldots \le \lambda_]:

L is always positive-semidefinite ([\forall i, \lambda_i \ge 0]).

The multiplicity of 0 as an eigenvalue of L is the number of connected components of G.

[\lambda_1] is called the algebraic connectivity.

The smallest non-trivial eigenvalue of L is called the spectral gap.