Incidence matrix

Labeled undirected graph

Weighted undirected graph

Incidence matrix is a mathematical concept used in various fields such as graph theory, network analysis, and design theory. It is a matrix that shows the relationship between two classes of objects, typically between the vertices and edges of a graph or between the elements and blocks of a design.

Definition

In the context of graph theory, an incidence matrix of a graph G is a matrix B where rows represent the vertices of G, and columns represent the edges of G. The entry B[i,j] is non-zero if vertex i is incident with edge j; that is, if vertex i is one of the endpoints of edge j. The exact nature of the non-zero entries depends on the type of graph and the conventions being used. For an undirected graph, the entries are usually set to 1. For a directed graph, entries may be -1, 0, or 1, indicating the direction of the edge relative to the vertex.

Types of Incidence Matrices

There are two main types of incidence matrices: 1. Vertex-edge incidence matrix: This is the most common form, used in graph theory to represent which vertices are connected by which edges. 2. Block design incidence matrix: Used in combinatorial design and statistics, this matrix represents the incidence between elements and blocks (or sets) in a design.

Applications

Incidence matrices are used in various applications, including: - Analyzing the properties of graphs and networks, such as connectivity and flow. - Solving problems in electrical engineering, such as analyzing electrical circuits. - Designing and analyzing experiments in statistics. - In computer science, for representing and solving problems related to databases and relationships between entities.

Properties

Some important properties of incidence matrices include: - The sum of any column in a vertex-edge incidence matrix for an undirected graph is 2, reflecting the fact that each edge connects two vertices. - In a directed graph, the sum of the entries in any column of its incidence matrix is 0, as each edge has a direction from one vertex to another. - Incidence matrices are used to derive other important matrices in graph theory, such as the Laplacian matrix and the adjacency matrix.

Example

Consider a simple undirected graph G with vertices V = {1, 2, 3} and edges E = {a, b, c}, where edge a connects vertices 1 and 2, edge b connects vertices 2 and 3, and edge c connects vertices 1 and 3. The incidence matrix B for this graph is:

\[ B = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} \]

Here, the rows correspond to vertices 1, 2, and 3, and the columns correspond to edges a, b, and c, respectively.

See Also

- Graph theory - Adjacency matrix - Laplacian matrix - Combinatorial design