FACTOID # 3: South Carolina has the highest rate of violent crimes and aggravated assaults per capita among US states.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Incidence matrix

In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. 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. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... For the square matrix section, see square matrix. ...

## Contents

A diagram of a graph with 6 vertices and 7 edges. ...

### Ordinary and directed graphs

In graph theory, the incidence matrix of an undirected graph G is a p × q matrix [bij] where p and q are the number of vertices and edges respectively, such that bij = 1 if the vertex vi and edge xj are incident and 0 otherwise. This matrix is also called the unoriented incidence matrix. This article just presents the basic definitions. ... For the square matrix section, see square matrix. ... In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ... This article just presents the basic definitions. ...

The incidence matrix of a directed graph D is a p × q matrix [bij] where p and q are the number of vertices and edges respectively, such that bij = − 1 if the edge xj leaves vertex vi, 1 if it enters vertex vi and 0 otherwise. (Many authors use the opposite sign convention!) This article just presents the basic definitions. ... For the square matrix section, see square matrix. ... In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ... This article just presents the basic definitions. ...

An oriented incidence matrix of an undirected graph G is the incidence matrix, in the sense of directed graphs, of any orientation of G. That is, in the column of edge e, there is a +1 in the row corresponding to one vertex of e and a -1 in the row corresponding to the other vertex of e, and all other rows have 0. All oriented incidence matrices of G differ only by negating some set of columns. In many uses, this is an insignificant difference, so one can speak of the oriented incidence matrix, even though that is technically incorrect.

The oriented or unoriented incidence matrix of a graph G is related to the adjacency matrix of its line graph L(G) by the following theorem: In mathematics and computer science, the adjacency matrix for a finite graph on n vertices is an n × n matrix in which entry aij is the number of edges from vi to vj in . ... In graph theory, the line graph L(G) of a graph G is a graph such that each vertex of L(G) represents an edge of G; and any two vertices of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common...

A(L(G)) = B(G)TB(G) − 2Iq

where A(L(G)) is the adjacency matrix of the line graph of G, B(G) is the incidence matrix, and Iq is the identity matrix of dimension q. In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ...

The Kirchhoff matrix is obtained from the oriented incidence matrix M(G) by the formula

M(G)M(G)T.

The integral cycle space of a graph is equal to the null space of its oriented incidence matrix, viewed as a matrix over the integers or real or complex numbers. The binary cycle space is the null space of its oriented or unoriented incidence matrix, viewed as a matrix over the two-element field. In graph theory, certain vector spaces over the two-element field Z2 are associated with an undirected graph; this allows to use the tools of linear algebra to study graphs. ... The null space (also nullspace) of a matrix A is the set of all vectors v which solve the equation Av = 0. ... The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ... Please refer to Real vs. ... The complex numbers are an extension of the real numbers, in which all non-constant polynomials have roots. ... Look up field in Wiktionary, the free dictionary A green field or paddock Field may refer to: A field is an open land area, used for growing agricultural crops. ...

### 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 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. 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.

## Incidence structures

The incidence matrix of an incidence structure C is a p × q matrix [bij] where p and q are the number of points and lines respectively, such that bij = 1 if the point pi and line Lj are incident and 0 otherwise. In this case the incidence matrix is also a biadjacency matrix of the Levi graph of the structure. In mathematics, in particular in combinatorics, an incidence structure is a triple where is the set of points, is the set of lines and is the incidence relation. ... In mathematics and computer science, the biadjacency matrix for a finite bipartite graph with n black vertices and m white vertices is an n × m matrix where the entry aij is the number of edges joining black vertex and white vertex . ... Levi graph or incidence graph is a bipartite graph associated with an incidence structure. ...

### 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 dimention one less than the dimension of Y; or X could be the set of all subspaces of one dimension d and Y the set of all subspaces of another dimension e. A finite geometry is any geometric system that has only a finite number of points. ...

### Block designs

Another example is a block design. 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 existence theory of block designs. For instance, it is used to prove the fundamental theorem of symmetric 2-designs, that the number of blocks equals the number of points. You may be looking for block design test In combinatorial mathematics, a block design is a particular kind of set system, which has some long-standing applications to experimental design, as well as some pure combinatorial aspects. ...

Results from FactBites:

 Incidence matrix - Wikipedia, the free encyclopedia (721 words) The incidence matrix of a signed graph is a generalization of the oriented incidence matrix. 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. In this case the incidence matrix is also a biadjacency matrix of the Levi graph of the structure.
 Adjacency matrix - Wikipedia, the free encyclopedia (812 words) In the special case of a finite, simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. The relationship between a graph and its adjacency matrix is studied in spectral graph theory. The adjacency matrix of an undirected graph is symmetric, and therefore has a complete set of eigenvalues and orthogonal eigenvector basis.
More results at FactBites »

Share your thoughts, questions and commentary here