HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an incidence matrix is a
logical matrix A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix (mathematics), matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. ...
that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element of ''X'' and one column for each element of ''Y''. The entry in row ''x'' and column ''y'' is 1 if ''x'' and ''y'' are related (called ''incident'' in this context) and 0 if they are not. There are variations; see below.


Graph theory

Incidence matrix is a common graph representation in
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
. It is different to an
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
, which encodes the relation of vertex-vertex pairs.


Undirected and directed graphs

In graph theory an
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
has two kinds of incidence matrices: unoriented and oriented. The ''unoriented incidence matrix'' (or simply ''incidence matrix'') of an undirected graph is a n\times m
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
''B'', where ''n'' and ''m'' are the numbers of vertices and
edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed ...
s respectively, such that :B_=\left\{\begin{array}{rl}\,1 & \text{if vertex }v_i\text{ is incident with edge }e_j, \\ 0 & \text{otherwise.}\end{array}\right. For example, the incidence matrix of the undirected graph shown on the right is a matrix consisting of 4 rows (corresponding to the four vertices, 1–4) and 4 columns (corresponding to the four edges, e_{1},e_{2},e_{3},e_{4}): {, , {, align=left class=wikitable , - ! !! e1 !! e2 !! e3 !! e4 , - !1 , 1, , 1, , 1, , 0 , - !2 , 1, , 0, , 0, , 0 , - !3 , 0, , 1, , 0, , 1 , - !4 , 0, , 0, , 1, , 1 , = , \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ \end{bmatrix}. If we look at the incidence matrix, we see that the sum of each column is equal to 2. This is because each edge has a vertex connected to each end. The ''incidence matrix'' of a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
is a n\times m matrix ''B'' where ''n'' and ''m'' are the number of vertices and edges respectively, such that :B_{ij}=\left\{\begin{array}{rl} {-1} & \text{if edge }e_j\text{ leaves vertex }v_i, \\ \phantom{-}1 & \text{if edge }e_j\text{ enters vertex }v_i, \\ \phantom{-}0 & \text{otherwise.} \end{array}\right. (Many authors use the opposite sign convention.) The ''oriented incidence matrix'' of an undirected graph is the incidence matrix, in the sense of directed graphs, of any orientation of the graph. That is, in the column of edge ''e'', there is one 1 in the row corresponding to one vertex of ''e'' and one −1 in the row corresponding to the other vertex of ''e'', and all other rows have 0. The oriented incidence matrix is unique
up to Two mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R'' * if ''a'' and ''b'' are related by ''R'', that is, * if ''aRb'' holds, that is, * if the equivalence classes of ''a'' and ''b'' with respect to ''R'' ...
negation of any of the columns, since negating the entries of a column corresponds to reversing the orientation of an edge. The unoriented incidence matrix of a graph ''G'' is related to the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
of its
line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
''L''(''G'') by the following theorem: : A(L(G)) = B(G)^\textsf{T}B(G) - 2I_m. where ''A''(''L''(''G'')) is the adjacency matrix of the line graph of ''G'', ''B''(''G'') is the incidence matrix, and ''I''''m'' is the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
of dimension ''m''. The discrete
Laplacian In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...
(or Kirchhoff matrix) is obtained from the oriented incidence matrix ''B''(''G'') by the formula : B(G) B(G)^\textsf{T}. The integral cycle space of a graph is equal to the
null space In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kern ...
of its oriented incidence matrix, viewed as a matrix over the
integers An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
or
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
or
complex numbers In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
. The binary cycle space is the null space of its oriented or unoriented incidence matrix, viewed as a matrix over the two-element field.


Signed and bidirected graphs

The incidence matrix of a signed graph is a generalization of the oriented incidence matrix. It is the incidence matrix of any
bidirected graph In the mathematical domain of graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also ...
that orients the given signed graph. The column of a positive edge has a 1 in the row corresponding to one endpoint and a −1 in the row corresponding to the other endpoint, just like an edge in an ordinary (unsigned) graph. The column of a negative edge has either a 1 or a −1 in both rows. The line graph and Kirchhoff matrix properties generalize to signed graphs.


Multigraphs

The definitions of incidence matrix apply to graphs with loops and
multiple edges In graph theory, multiple edges (also called parallel edges or a multi-edge), are, in an undirected graph, two or more edges that are incident to the same two vertices, or in a directed graph, two or more edges with both the same tail vertex ...
. The column of an oriented incidence matrix that corresponds to a loop is all zero, unless the graph is signed and the loop is negative; then the column is all zero except for ±2 in the row of its incident vertex.


Weighted graphs

A weighted graph can be represented using the weight of the edge in place of a 1. For example, the incidence matrix of the graph to the right is: {, , {, align=left class=wikitable , - ! !! e1 !! e2 !! e3 !! e4 , - !1 , 2, , 1, , 5, , 0 , - !2 , 2, , 0, , 0, , 0 , - !3 , 0, , 1, , 0, , 6 , - !4 , 0, , 0, , 5, , 6 , = , \begin{bmatrix} 2 & 1 & 5 & 0 \\ 2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 6 \\ 0 & 0 & 5 & 6 \\ \end{bmatrix}.


Hypergraphs

Because the edges of ordinary graphs can only have two vertices (one at each end), the column of an incidence matrix for graphs can only have two non-zero entries. By contrast, a
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) w ...
can have multiple vertices assigned to one edge; thus, a general matrix of non-negative integers describes a hypergraph.


Incidence structures

The ''incidence matrix'' of an
incidence structure In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore al ...
''C'' is a matrix ''B'' (or its transpose), where ''p'' and ''q'' are the number of ''points'' and ''lines'' respectively, such that if the point ''p''i and line ''L''''j'' are incident and 0 otherwise. In this case, the incidence matrix is also a
biadjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...
of the Levi graph of the structure. As there is a
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) w ...
for every Levi graph, and ''vice versa'', the incidence matrix of an incidence structure describes a hypergraph.


Finite geometries

An important example is a finite geometry. For instance, in a finite plane, ''X'' is the set of points and ''Y'' is the set of lines. In a finite geometry of higher dimension, ''X'' could be the set of points and ''Y'' could be the set of subspaces of dimension one less than the dimension of the entire space (hyperplanes); or, more generally, ''X'' could be the set of all subspaces of one dimension ''d'' and ''Y'' the set of all subspaces of another dimension ''e'', with incidence defined as containment.


Polytopes

In a similar manner, the relationship between cells whose dimensions differ by one in a polytope, can be represented by an incidence matrix.


Block designs

Another example is a
block design In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as ''blocks'', chosen such that frequency of the elements satisfies certain conditions making the collection of bl ...
. Here ''X'' is a finite set of "points" and ''Y'' is a class of subsets of ''X'', called "blocks", subject to rules that depend on the type of design. The incidence matrix is an important tool in the theory of block designs. For instance, it can be used to prove Fisher's inequality, a fundamental theorem of balanced incomplete 2-designs (BIBDs), that the number of blocks is at least the number of points. Considering the blocks as a system of sets, the permanent of the incidence matrix is the number of systems of distinct representatives (SDRs).


See also

* Parry–Sullivan invariant


References


Further reading

* * Jonathan L Gross, Jay Yellen, ''Graph Theory and its applications'', second edition, 2006 (p 97, Incidence Matrices for undirected graphs; p 98, incidence matrices for digraphs)


External links

* {{Authority control Algebraic graph theory Combinatorics Matrices Graph data structures