Fact-checked by Grok 2 weeks ago

Incidence matrix

In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, with rows corresponding to one class and columns to the other, where the entry is 1 if an element of the first class is incident to an element of the second class, and 0 otherwise.^[1] It generalizes to various incidence structures beyond graphs, such as in combinatorial designs and finite geometries. In graph theory, it is a (0,1)-matrix that encodes the incidences between the vertices and edges of a graph, with one row for each vertex and one column for each edge.^[1] This representation, first introduced by Gustav Kirchhoff in 1847 for analyzing electrical networks, provides a compact algebraic structure for studying properties of graphs and other structures.^[1] For undirected graphs, each column of the incidence matrix sums to 2, reflecting that every edge connects exactly two vertices, while self-loops would yield a column sum of 1 or adjusted entries.^[2] In directed graphs, the matrix is typically signed: entries are -1 for the initial vertex of an edge, +1 for the terminal vertex, and 0 otherwise, resulting in column sums of 0 (assuming no self-loops).^[2] An alternative convention, common in network flow and linear algebra contexts, transposes the matrix so that rows correspond to edges and columns to vertices, facilitating computations like Kirchhoff's laws where the matrix relates potentials across nodes to edge differences.^[3] Key properties include its sparsity (most entries are zero) and connections to other matrices: for instance, in graphs, the adjacency matrix of the line graph can be derived as L = C^T C - 2I, where C is the incidence matrix and I is the identity.^[1] The matrix also extends to higher-dimensional structures like polytopes, where it captures face-lattice incidences.^[1] Applications span electrical engineering (modeling currents and voltages via Kirchhoff's rules), network topology analysis for reliability and vulnerability in cyber-physical systems, and combinatorial designs such as projective planes.^[3]^[4]^[2]

Fundamentals

Definition

An incidence matrix is a combinatorial tool that encodes the incidence relation between two finite sets of objects, typically denoted as X and Y. Given sets X = \{x_1, \dots, x_m\} and Y = \{y_1, \dots, y_n\}, along with a binary relation I \subseteq X \times Y where (x_i, y_j) \in I signifies that element x_i is incident to element y_j, the incidence matrix M is defined as an m \times n matrix with entries in \{0,1\}, such that M_{i,j} = 1 if (x_i, y_j) \in I and M_{i,j} = 0 otherwise.^[5] This structure captures the relational data in a rectangular array, facilitating algebraic and combinatorial analysis.^[6] More generally, the entries of M may belong to the non-negative integers to account for multiplicities in the incidence relation, such as in multiset contexts or weighted structures.^[5] The incidence matrix can be interpreted as the biadjacency matrix of the bipartite graph G = (X \cup Y, E), where the partite sets are X and Y, and the edge set E consists of pairs \{x_i, y_j\} for each incidence (x_i, y_j) \in I.^[7] For a simple example, consider sets X = \{x_1, x_2\} and Y = \{y_1, y_2\} with incidences (x_1, y_1) and (x_2, y_2). The corresponding incidence matrix is

\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}.

^[5] Variations of the incidence matrix arise depending on the nature of the incidences. In unoriented settings, such as undirected relations, the matrix remains a (0,1)-matrix reflecting symmetric or neutral incidences.^[1] In oriented cases, like directed graphs or signed structures, entries may be signed integers (e.g., +1 for outgoing or positive direction, -1 for incoming or negative, and 0 otherwise) to encode directional information.^[8]

Historical development

The concept of the incidence matrix was first introduced by Gustav Kirchhoff in 1847 for analyzing electrical networks, where it encoded the connections between nodes (vertices) and branches (edges) in what is now recognized as graph theory.^[1] This application provided an early algebraic framework for studying network properties, particularly in physics and engineering. Subsequent developments in the late 19th century extended the idea to algebraic topology. Henri Poincaré introduced tabular representations—essentially incidence matrices—of simplicial complexes in his seminal papers on Analysis Situs (1895–1904), where he employed them to define boundary relations and compute topological invariants such as Betti numbers. These matrices, denoted as tables T_q with entries \varepsilon_q^{ij} (where +1 or -1 indicated oriented incidences and 0 otherwise), encoded the combinatorial structure of polyhedra, enabling the study of homology groups through linear relations like a_q^i \equiv \sum_j \varepsilon_q^{ij} a_{q-1}^j. Poincaré's approach laid the groundwork for using matrix-based methods to analyze the connectivity and holes in topological spaces, marking a systematic application in pure mathematics.^[9] In the early 20th century, incidence matrices found adoption in graph theory, particularly through Dénes Kőnig's comprehensive textbook Theorie der endlichen und unendlichen Graphen (1936). Kőnig utilized incidence matrices to represent bipartite graphs, applying them to problems in combinatorial optimization such as bipartite matching and vertex covers. His work demonstrated how these matrices could model edge-vertex incidences to prove key results like the equality of maximum matching size and minimum vertex cover in bipartite graphs, bridging graph theory with linear algebraic techniques. This application extended Poincaré's topological ideas to discrete structures, influencing subsequent developments in matching theory.^[10]^[11] Post-World War II advancements generalized incidence matrices to broader incidence structures in combinatorial design theory. In the 1940s and 1950s, R.C. Bose and collaborators developed these matrices for analyzing block designs and finite geometries, notably in Bose's 1947 paper on symmetrical factorial designs, which included constructions related to projective planes. These matrices captured point-block incidences, facilitating the study of balanced incomplete block designs and their symmetries, with applications to statistical experimentation and coding theory. Bose's contributions emphasized the matrices' role in verifying design properties like resolvability and orthogonality. From the 1960s onward, incidence matrices saw modern extensions in matroid theory, building on Hassler Whitney's earlier abstraction of linear dependence (1935) but gaining momentum through subsequent works linking them to linear algebra over GF(2). Whitney's framework treated graphic matroids via cycle spaces derived from incidence matrices modulo 2, unifying dependence in graphs and vector spaces. Later developments in the 1960s, including by researchers like W.T. Tutte, formalized binary matroids where incidence matrices over GF(2) represented circuit structures, enabling algorithmic and structural theorems in combinatorics. This era solidified incidence matrices as a versatile tool across topology, graphs, and designs.

Properties

Algebraic properties

The incidence matrix M of a graph G with n vertices and c connected components has rank n - c over the real numbers when using the oriented version, where each column corresponding to an edge has entries +1 and -1 at the incident vertices (with arbitrary orientation) and 0 elsewhere.^[3] For the unoriented (0,1)-incidence matrix, the rank over the reals is n - b, where b is the number of bipartite connected components; thus, for a connected non-bipartite graph, the rank is n, while for a connected bipartite graph, it is n - 1.^[12] Over the finite field GF(2, the rank of the (unoriented) incidence matrix is at most n - 1, with equality if and only if the graph is connected.^[13] The kernel of the incidence matrix M (viewed as a map from edge space to vertex space) consists of the cycle space of the graph over the reals, with nullity equal to the dimension of the cycle space, |E| - (n - c) for a graph with |E| edges.^[3] The image of M (or equivalently, the row space of M) spans the cut space, which has dimension equal to the rank of M. Over GF(2), the kernel corresponds to the binary cycle space, comprising even-degree subgraphs (Eulerian subgraphs mod 2), and is used in computations of mod-2 homology for graphs.^[14] For the oriented incidence matrix M, the product M M^T is the graph Laplacian matrix L, with diagonal entries equal to the vertex degrees and off-diagonal entries -1 if the vertices are adjacent and 0 otherwise. For the unoriented incidence matrix, M M^T has diagonal entries equal to the degrees of the vertices and off-diagonal entries equal to the number of shared incident edges between pairs of vertices (1 for adjacent vertices in simple graphs); thus, M M^T = D + A, where D is the degree matrix and A is the adjacency matrix. The eigenvalues of M M^T (or the Laplacian) are nonnegative and bounded above by twice the maximum degree of the graph.^[15] Over GF(2), the unoriented incidence matrix serves as the boundary operator in the chain complex for the graph, facilitating homology computations where the kernel captures mod-2 cycles and the image captures mod-2 cuts (bond space as the row space).^[14] As an example, consider the path graph on 3 vertices (with edges connecting vertices 1-2 and 2-3). The unoriented incidence matrix is

M = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{pmatrix},

which has rank 2 over the reals (full column rank, as expected for a tree, which is bipartite and connected). The kernel of M is trivial (dimension 0), consistent with the absence of cycles.^[3]

Comparison with other matrices

The incidence matrix of a graph is fundamentally distinct from the adjacency matrix in terms of structure and representational focus. The adjacency matrix is a square matrix of dimensions |V| \times |V|, where V is the vertex set, with entries indicating direct connections between vertex pairs (typically 1 for an edge, 0 otherwise in unweighted undirected graphs). In contrast, the incidence matrix is rectangular, with dimensions |V| \times |E|, where E is the edge set, and entries (0 or 1 for unoriented cases) specify which vertices are endpoints of each edge. This rectangular form allows the incidence matrix to explicitly encode edge-vertex relationships, whereas the adjacency matrix captures vertex-vertex neighborhoods without referencing edges as distinct entities.^[16]^[17] Sparsity patterns further highlight these differences: in simple undirected graphs without loops, each column of the incidence matrix contains exactly two 1's (one for each endpoint), reflecting the binary incidence per edge, while the adjacency matrix exhibits 1's symmetrically off the diagonal for adjacent vertices, with zeros on the diagonal. For example, in the cycle graph C_3 with vertices \{1,2,3\} and edges \{e_1=\{1,2\}, e_2=\{2,3\}, e_3=\{3,1\}\}, the unoriented incidence matrix is

\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix},

with precisely two 1's per column, whereas the adjacency matrix is the circulant

\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},

emphasizing pairwise adjacencies. The incidence matrix is preferred for analyzing edge-centric properties, such as cuts or flows, while the adjacency matrix suits vertex connectivity tasks, like path counting via powers.^[16]^[17] Compared to the biadjacency matrix, which is used for general bipartite graphs with an arbitrary bipartition of vertices into sets U and W, the incidence matrix represents a specialized case where one part is the vertices V and the other is the edges E, with entries indicating endpoint connections. This makes the incidence matrix the biadjacency matrix of the line graph's bipartite representation, but it differs from standard biadjacency matrices by treating edges as the second partite set rather than a vertex subset, enabling direct hypergraph-like encodings. General biadjacency matrices, sized |U| \times |W|, focus on inter-partite edges without elevating edges to partite status.^[18] The Laplacian matrix, a square |V| \times |V| construction, derives from the oriented incidence matrix B via L = B B^T (up to sign conventions for undirected graphs), but prioritizes vertex diffusion and spectral properties over direct incidence. While the incidence matrix emphasizes raw vertex-edge incidences for structural queries like spanning trees, the Laplacian encodes connectivity and harmonic functions, with its kernel dimension indicating connected components.^[19]^[20] Overall, the incidence matrix's consistent rectangular dimensionality |V| \times |E| and column-sparse structure (e.g., two nonzeros per column in simple graphs) contrast with the square, denser forms of adjacency and Laplacian matrices, guiding its use for edge-vertex relational analysis in combinatorics and optimization.^[16]^[17]

Graph Theory

Undirected and directed graphs

In graph theory, the incidence matrix of an undirected simple graph G = (V, E) with |V| = n vertices and |E| = m edges is an n \times m matrix B where the rows correspond to vertices and the columns to edges. The entry B_{v,e} is 1 if vertex v is an endpoint of edge e, and 0 otherwise; thus, each column contains exactly two 1's, reflecting the two endpoints of the undirected edge. This unoriented form is unique for a given graph labeling.^[15] For the complete graph K_2 on two vertices connected by a single edge, the incidence matrix is the $2 \times 1 matrix

\begin{pmatrix} 1 \\ 1 \end{pmatrix}.

^[15] To obtain a signed incidence matrix for an undirected graph, an arbitrary orientation is imposed on each edge, after which the matrix entries are adjusted accordingly; without such an orientation, the signed matrix is not uniquely defined.^[15] For a directed simple graph, where each edge has a designated tail and head, the oriented incidence matrix B is similarly an n \times m matrix, but with entries defined by the formula

B_{v,e} = \begin{cases} 1 & \text{if } v \text{ is the tail of } e, \\ -1 & \text{if } v \text{ is the head of } e, \\ 0 & \text{otherwise}. \end{cases}

Each column thus has one +1, one -1, and the rest 0's.^[15] An unsigned version for directed graphs can also be constructed by placing 1's at both the tail and head, analogous to the undirected case, though the signed form is more commonly used to capture directionality.^[15] In this setup, the matrix B fully encodes the graph's orientation. For the directed version of K_2 with the edge oriented from vertex 1 (tail) to vertex 2 (head), the incidence matrix is

\begin{pmatrix} 1 \\ -1 \end{pmatrix}.

^[15] These incidence matrices for both undirected and directed graphs form the basis for Kirchhoff's laws in electrical network analysis, where rows enforce current conservation at vertices and columns relate to voltage drops across edges.^[3]

Signed, bidirected, multigraphs

In signed graphs, edges are assigned signs, either positive or negative, to model relationships such as friendships or enmities in social network analysis. The incidence matrix of a signed graph \Sigma = (V, E, \sigma), where \sigma: E \to \{+, -\} assigns the sign to each edge e, is defined relative to an orientation \eta. The entry H(\Sigma)_{v,e} is \eta(v, e) if vertex v is incident to edge e, and 0 otherwise, with the two nonzero entries in each column being \pm 1 such that their product equals -\sigma(e). For a positive edge, the entries are +1 and -1; for a negative edge, they are both +1 or both -1.^[21] This construction captures the balance theory of signed graphs, where a cycle is balanced if the product of its edge signs is positive. For example, consider a 3-cycle with vertices v_1, v_2, v_3 and edges e_1: v_1 \to v_2 (positive), e_2: v_2 \to v_3 (positive), and e_3: v_3 \to v_1 (negative). The incidence matrix is

\begin{pmatrix} -1 & 0 & +1 \\ +1 & -1 & 0 \\ 0 & +1 & +1 \end{pmatrix},

where the signs reflect the orientation and edge signs, with the last column having equal signs due to the negative edge.^[21] Bidirected graphs extend directed graphs by allowing each endpoint of an edge to have an independent orientation, often represented by signing the ends as entering (+) or exiting (-). The incidence matrix of a bidirected graph has rows indexed by vertices and columns by edges, with the entry (v, e) equal to the number of incoming ends of e at v minus the number of outgoing ends at v, resulting in values of +1, -1, or $0. This differs from standard directed graphs, where orientations are uniform across the edge, as bidirected structures permit configurations like both ends entering or exiting the same vertex.^[22] For instance, in a bidirected edge between v and w with the end at v outgoing and at w incoming, the column entries are -1 at v and +1 at w. Bidirected incidence matrices are crucial in matroid theory.^[22] In multigraphs, multiple edges (possibly parallel) may connect the same pair of vertices, and the incidence matrix accommodates this by assigning a distinct column to each edge, regardless of parallelism. For undirected multigraphs, each such column contains exactly two +1 entries corresponding to the incident vertices; for directed versions, the entries are +1 at the head and -1 at the tail. This preserves the bipartite incidence structure while distinguishing parallel edges for applications like network flows with capacities on specific links. Signed and bidirected constructions extend naturally to multigraphs by applying the sign or bidirection rules to each parallel edge's column independently. For example, in a multigraph with two parallel edges between v_1 and v_2, one positive signed and one negative, the columns would feature \pm 1 pairs as per the signed graph rules, ensuring the matrix reflects the multiplicity and edge attributes.

Weighted graphs and hypergraphs

In weighted graphs, the incidence matrix extends the unoriented form by replacing binary entries with edge weights. For an undirected weighted graph, the entry M_{v,e} is the weight w_e > 0 if vertex v is incident to edge e, and 0 otherwise; thus, each column for edge e has w_e in the rows corresponding to its two endpoints. This construction preserves the structure used to derive the weighted Laplacian matrix L = B D B^T, where D is the diagonal matrix of edge weights and B is the incidence matrix.^[23] For directed weighted graphs, an orientation is imposed, with M_{v,e} = -w_e if v is the source (tail) of directed edge e, M_{v,e} = +w_e if v is the target (head), and 0 otherwise; this antisymmetric form facilitates analysis in network flows and consensus algorithms. As an illustrative example, consider an undirected path graph with vertices v_1, v_2, v_3 and edges e_1 = \{v_1, v_2\} of weight 2, e_2 = \{v_2, v_3\} of weight 3. The resulting $3 \times 2 incidence matrix is

\begin{pmatrix} 2 & 0 \\ 2 & 3 \\ 0 & 3 \end{pmatrix},

where the first column reflects the incidences of e_1 and the second those of e_2. The concept of incidence matrices generalizes to hypergraphs, which allow hyperedges connecting arbitrary subsets of vertices. For a hypergraph H = (V, E), the incidence matrix M is a |V| \times |E| matrix with rows indexed by vertices and columns by hyperedges, where M_{v,e} = 1 if v \in e and 0 otherwise.^[24] In this framework, each column may contain more than two nonzero entries, unlike graph incidence matrices where columns have at most two (corresponding to pairwise connections). Weighted hypergraphs further generalize this by setting M_{v,e} = w_{v,e} for some positive weight w_{v,e} if v \in e, and 0 otherwise, enabling models where vertex contributions to hyperedges vary, as in certain machine learning applications for multi-relational data. A special case is the k-uniform hypergraph, where every hyperedge has exactly k vertices, so each column sums to k in the unweighted case.

Incidence Structures

Finite geometries

In finite geometries, incidence matrices provide a combinatorial framework for representing the points and lines of structures such as projective and affine planes, capturing their incidence relations in a matrix form over finite fields.^[25] For a projective plane of order q, where q is a prime power, the incidence matrix is a square matrix of size (q^2 + q + 1) \times (q^2 + q + 1), with rows corresponding to the q^2 + q + 1 points and columns to the equally many lines; an entry is 1 if the point lies on the line and 0 otherwise. Each row and each column sums to q + 1, reflecting that every point lies on exactly q + 1 lines and every line contains exactly q + 1 points. This structure embodies the duality and symmetry of projective planes, where points and lines play interchangeable roles.^[25] A classic example is the Fano plane, the unique projective plane of order 2, with an incidence matrix of size $7 \times 7 where each row and column sums to 3. The matrix entries indicate the incidences among its 7 points and 7 lines, each line passing through 3 points, and it is the biadjacency matrix of the Heawood graph, the bipartite point-line incidence graph of the Fano plane.^[25] Affine planes of order n, also with n a prime power, have an incidence matrix of size n^2 \times n(n+1), with rows for the n^2 points and columns for the n(n+1) lines. Each row sums to n+1 (lines through a point), while each column sums to n (points on a line); the matrix encodes parallelism through disjoint supports for columns corresponding to parallel lines, which form n+1 classes of n parallel lines each.^[26] These matrices are square in the projective case, aligning with symmetric balanced incomplete block designs (BIBDs), and their determinants can be computed as \det(A) = \pm (q+1) q^{(q^2 + q)/2} for projective planes. In Desarguesian projective and affine planes, constructed from vector spaces over the finite field \mathbb{GF}(q), the rows of the incidence matrix span subspaces of the vector space, enabling linear algebraic analysis such as studying the matrix over \mathbb{GF}(q) to reveal geometric properties like coordinatization.^[25]^[25] The Bose-Mesner algebra, introduced in the context of association schemes arising from such geometries, forms a commutative subalgebra generated by the incidence matrices and their powers, facilitating eigenvalue computations and decompositions relevant to the symmetry of finite planes. This framework originated in the 1959 work of R. C. Bose and D. M. Mesner on linear associative algebras for partially balanced designs, with applications to the combinatorial algebra of projective geometries.^[27]^[28]

Polytopes and simplicial complexes

In the context of polytopes, the incidence matrix typically encodes the combinatorial structure relating vertices to facets (or more generally, to faces of any codimension). For a convex polytope P of dimension d, the vertex-facet incidence matrix M has rows indexed by the vertices of P and columns indexed by the facets (i.e., the (d-1)-dimensional faces); the entry M_{v,f} is 1 if vertex v lies on facet f, and 0 otherwise. This matrix captures the face lattice's bottom two levels and serves as a compact representation of the polytope's combinatorics, enabling computations such as determining the number of facets incident to a given vertex or reconstructing the full face lattice via algorithms that exploit its structure.00103-7) For simplicial complexes, incidence matrices generalize this idea to hierarchical relations across dimensions, forming the basis for algebraic topology. A simplicial complex \Delta is a collection of simplices closed under taking faces, and the incidence matrix between k-faces and (k-1)-faces has rows indexed by (k-1)-faces and columns by k-faces, with entries indicating inclusion (often unsigned as 1 or 0 for basic incidence, or signed \pm 1 based on orientation for boundary maps). The boundary operator \partial_k: C_k(\Delta) \to C_{k-1}(\Delta) in the associated chain complex is represented by a signed incidence matrix, where for an oriented k-simplex [v_0, \dots, v_k], \partial_k([v_0, \dots, v_k]) = \sum_{i=0}^k (-1)^i [v_0, \dots, \hat{v}_i, \dots, v_k], so the matrix entries are \pm 1 if the (k-1)-face is the i-th face of the k-face, and 0 otherwise.^[29] A concrete example is the 2-simplex (a triangle), which forms a simplicial complex with 3 vertices, 3 edges, and 1 face. The vertex-edge incidence matrix is a $3 \times 3 matrix where each column (edge) has exactly two 1's corresponding to its endpoints, such as

\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}

for vertices v_0, v_1, v_2 and oriented edges [v_0 v_1], [v_1 v_2], [v_0 v_2]. The full face lattice can be represented by a block-diagonal incidence matrix stacking these levels, but the edge-face incidence is a $3 \times 1 column vector of 1's (unsigned) or signed according to the boundary formula, yielding \partial_2 = [v_1 v_2] - [v_0 v_2] + [v_0 v_1].^[29] These incidence matrices underpin the chain complex of a simplicial complex, where the homology groups H_k(\Delta) = \ker \partial_k / \operatorname{im} \partial_{k+1} have ranks given by the Betti numbers \beta_k, measuring topological "holes" in dimension k. The Euler characteristic \chi(\Delta) is the alternating sum of these ranks, \chi(\Delta) = \sum_{k \geq 0} (-1)^k \beta_k, which equals the alternating sum of the ranks of the incidence matrices (or dimensions of the chain groups) due to the exactness properties of the complex: \chi(\Delta) = \sum_{k \geq 0} (-1)^k \operatorname{rank} C_k(\Delta).^[29] Henri Poincaré originally employed such incidence-based methods in his foundational work on analysis situs to compute Betti numbers via what would later be formalized as simplicial homology, linking combinatorial data to topological invariants without modern group theory.^[29]

Block designs

In combinatorial design theory, a balanced incomplete block design (BIBD) is defined by parameters (v, b, r, k, \lambda), where there are v points and b blocks such that each block contains k points, each point appears in r blocks, and every pair of distinct points is contained in exactly \lambda blocks. The incidence matrix A of a BIBD is a v \times b matrix with entries in \{0,1\}, where rows correspond to points, columns to blocks, and A_{i,j}=1 if point i belongs to block j. These designs satisfy the fundamental parameter relations bk = vr and \lambda(v-1) = r(k-1), which ensure the balance of pairwise incidences.^[30] A key algebraic property of the incidence matrix A is given by the relation

AA^T = (r - \lambda)I_v + \lambda J_v,

where I_v is the v \times v identity matrix and J_v is the v \times v all-ones matrix. This equation captures the replication and pairwise balance: the diagonal entries of AA^T are r, reflecting the number of blocks per point, while off-diagonal entries are \lambda. The eigenvalues of AA^T are r - \lambda with multiplicity v-1 (for eigenvectors orthogonal to the all-ones vector) and rk with multiplicity 1 (for the all-ones eigenvector), leading to the determinant

\det(AA^T) = kr(r - \lambda)^{v-1}.

Since r > \lambda in nontrivial BIBDs, AA^T is positive definite, confirming that the rows of A are linearly independent.^[30] An illustrative example is the affine plane of order q (where q is a prime power), which forms a BIBD with parameters v = q^2, b = q(q+1), r = q+1, k = q, and \lambda = 1. Here, points are elements of the vector space \mathbb{F}_q^2, and blocks are the cosets of 1-dimensional subspaces (lines), providing a concrete realization of the incidence structure. Extensions include symmetric BIBDs, where v = b and thus r = k, yielding a square incidence matrix A that satisfies A^2 = kI + (k - \lambda)(J - I). Signed variants, such as conference matrices, modify the (0,1)-entries of symmetric design incidence matrices by replacing some 1's with -1's to achieve orthogonality properties, as seen in balanced weighing matrices derived from symmetric BIBDs.^[31]^[30]^[32] In the broader framework of association schemes arising from BIBDs (particularly symmetric ones), the Bose-Mesner algebra is the commutative subalgebra of v \times v matrices generated by A, A^T, and J, closed under Schur (entrywise) and Hadamard (matrix) products. This algebra facilitates the study of eigenspaces and intersection numbers in design theory.^[33]

Other Applications

Matroids

Incidence matrices provide a key mechanism for representing certain matroids as linear matroids over finite fields, particularly GF(2). A matroid is representable over a field F if there exists a matrix A over F whose columns correspond to the ground set elements, such that a subset of columns is independent in the matroid if and only if those columns are linearly independent over F. For binary matroids, which are representable over GF(2), the incidence matrix of a structure like a graph or bipartite graph often serves as such a representing matrix.^[34] This linear representation aligns with Hassler Whitney's foundational 1935 characterization of matroids as abstract closure operators that generalize linear dependence in vector spaces, where the incidence matrix realizes the matroid concretely through column dependencies. Circuits in the matroid correspond to minimal linearly dependent sets of columns, enabling the detection of dependencies that define the matroid's structure.^[35] Graphic matroids, arising from the cycle structure of undirected graphs, are represented by the vertex-edge incidence matrix over GF(2), where each column has 1's in the rows corresponding to its incident vertices. In this representation, the independent sets are the forests of the graph, and the rank of the matroid equals the number of vertices minus the number of connected components in the underlying graph.^[34] Transversal matroids, derived from bipartite graphs and related to matching theory, use the incidence matrix with rows indexed by one partite set and columns by the other, with entries 1 if an edge connects them. Here, a set of columns is independent if it can be matched injectively to the row set, capturing the matroid's independence via the matrix's column linear independence over any field.^[36]^[37] For example, consider the cycle graph C_4 with vertices labeled 1 through 4 and edges e_1 = \{1,2\}, e_2 = \{2,3\}, e_3 = \{3,4\}, e_4 = \{4,1\}. The incidence matrix over GF(2) is

\begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{pmatrix},

where rows correspond to vertices and columns to edges. The independent sets are the acyclic subsets of edges (forests), such as any three edges forming a path, while the full set of four edges forms a circuit corresponding to the linear dependence of all columns. The matrix has rank 3, reflecting the graph's four vertices and one connected component.^[34]

Network analysis

In network analysis, the oriented incidence matrix B of a directed graph with n nodes and m edges encodes the topology for modeling flows and currents. The matrix B, of size n \times m, has entries B_{ij} = 1 if edge j originates at node i, B_{ij} = -1 if edge j terminates at node i, and 0 otherwise.^[3] This structure captures the connectivity and orientation essential for conservation principles.^[38] In network flows, conservation of flow at each node (except sources and sinks) is expressed by the equation B f = s, where f \in \mathbb{R}^m is the vector of flows along edges and s \in \mathbb{R}^n is the supply vector with positive entries for sources and negative for sinks.^[39] For electrical networks, Kirchhoff's current law enforces that the net current at each node is zero in a balanced circuit, given by B i = 0, where i \in \mathbb{R}^m is the vector of currents on edges.^[40] Node potentials \phi \in \mathbb{R}^n relate to voltage drops across edges via B^T \phi, where the j-th component equals the potential difference along edge j.^[40] A representative example is a three-node flow network with edges directed from node 1 to 2 (edge 1), node 2 to 3 (edge 2), and node 3 to 1 (edge 3), forming a cycle with a source at node 1 (s_1 = 2) and sink at node 3 (s_3 = -2, s_2 = 0). The incidence matrix is

B = \begin{pmatrix} 1 & 0 & -1 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix},

and solving B f = b (with b = (2, 0, -2)^T) yields feasible flows f satisfying conservation, such as f = (2, 2, 0)^T.^[3] In maximum flow problems, augmenting paths identified via the incidence structure allow incremental flow increases until saturation.^[39] The 1950s Ford–Fulkerson algorithm computes maximum flows by repeatedly finding augmenting paths in the residual graph, implicitly leveraging the incidence matrix's structure to enforce conservation and update flows.^[41] Computationally, systems like B f = s are solved efficiently using sparse LU decomposition, capitalizing on B's sparsity (exactly two nonzeros per column), with a time complexity of O(n m) for n nodes and m edges in typical implementations for network equations.^[42]

References

[1]
Incidence Matrix -- from Wolfram MathWorld
The incidence matrix of a graph gives the (0,1)-matrix which has a row for each vertex and column for each edge, and (v,e)=1 iff vertex v is incident upon edge ...
[2]
Incidence Matrix - an overview | ScienceDirect Topics
An incidence matrix is defined as a matrix that represents the relationships between edges and vertices in a graph, where the rows correspond to vertices ...
[3]
[PDF] Graphs, networks, incidence matrices - MIT OpenCourseWare
The incidence matrix of this directed graph has one column for each node of the. graph and one row for each edge of the graph: ⎤
[4]
https://www.sciencedirect.com/science/article/pii/S0378779618302086
[5]
[PDF] Smith Normal Forms of incidence matrices - People
An incidence matrix is a matrix A of zeros and ones which encodes a relation between two finite sets X and Y . Related elements are said to be incident. The ...
[6]
[PDF] Compositions and decompositions of binary relations - arXiv
Nov 11, 2021 · To every binary relation R on I we assign its incidence matrix MR = [aij] ∈ {0, 1}I×I as follows: aij := 1 if(i, j) ∈ R,. 0 otherwise. For I × I ...
[7]
Bipartite graphs in systems biology and medicine - PubMed Central
The adjacency matrices are symmetrical across the diagonal line. Bipartite graphs can be efficiently represented by biadjacency matrices (Figure 1C, D). The ...
[8]
[PDF] 4/2/2015 1.0.1 The Laplacian matrix and its spectrum
Apr 2, 2015 · The. (oriented) incidence matrix BD is an n × m matrix such that qij = −1 if the edge corresponding to column j leaves vertex i, 1 if it enters ...
[9]
[PDF] Papers on Topology - School of Mathematics
Jul 31, 2009 · Page 1. Papers on Topology. Analysis Situs and Its Five Supplements. Henri Poincaré. Translated by John Stillwell. July 31, 2009. Page 2. 2 ...
[10]
Theory of Finite and Infinite Graphs
Originally published as "Theorie der endlichen und unendlichen Graphen" ... Denes Konig's textbook in 1936. "From Konigsberg to Konig's book" sings the ...
[11]
https://books.google.com/books?id=XqYTk0sXmpoC
[12]
Which graphs have incidence matrices of full rank? - MathOverflow
Nov 14, 2009 · Theorem: The rows of the incidence matrix of a graph are linearly independent over the reals if and only if no connected component is bipartite.incidence matrix - linear algebra - MathOverflowRank adjacency matrix bipartite graph - MathOverflowMore results from mathoverflow.net
[13]
[PDF] 1 Graphs - Department of Mathematics | University of Toronto
1.1. 15 Show that the rank over GF(2) of the incidence matrix of a graph G is at most n − 1, with equality if and only if G is connected.
[14]
[PDF] Chapter 12. The Cycle Space and Bond Space of J. A. Bondy and ...
Dec 22, 2022 · In Exercise 2.6. 4(c) it is to be shown that the bond space of G is the row space of the incidence matrix M of G over GF(2), and the cycle ...
[15]
[PDF] Graphs and Matrices - Arizona Math
12.4 Incidence matrix games . ... the edge-Laplacian of a tree and obtain a combinatorial description of its inverse.
[16]
[PDF] Introduction to graphs and matrices
We start with an incidence matrix A, which has a row for each vertex, and a column for each edge of G. We let Ave = 1 if v ∈ e and Ave = 0 otherwise. A famous ...
[17]
[PDF] Graph Theory Fundamentals
Thus, the adjacency matrices corresponding to the two one-mode projections can be calculated directly from the incidence matrix, without having to construct the ...
[18]
None
### Summary: Incidence Matrix of Hypergraph and Biadjacency Matrix of Bipartite Graph
[19]
Laplacian Matrices | An Introduction to Algebraic Graph Theory
The Laplacian and Signless Laplacian Matrices. We first define the incidence matrix of a graph. Let G = ( V , E ) be a graph where V = { v 1 , v 2 , … , v n } ...
[20]
[PDF] Chapter 17 Graphs and Graph Laplacians - UPenn CIS
Unlike the case of directed graphs, the entries in the incidence matrix of a graph (undirected) are nonnegative. We usually write B instead of B(G). The notion ...<|control11|><|separator|>
[21]
[PDF] Matrices in the Theory of Signed Simple Graphs - People
Sep 17, 2010 · [19] Dénes König, Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft,. Leipzig, 1936. Repr. Chelsea, New York ...
[22]
[PDF] Glossary of Signed and Gain Graphs and Allied Areas
incidence matrix (of a bidirected graph). The matrix whose rows are indexed by the vertices and whose columns are indexed by the edges, in which the (v, e) ...
[23]
[PDF] Graph Theory and Its Applications
Each row in an incidence matrix represents a particular vertex in a graph. This is an example of an incidence matrix created based on a directed graph. A ...
[24]
[PDF] An Introduction to Finite Projective Planes - David Kurniadi Angdinata
An incidence matrix, defined below, is an explicit representation of a finite projective plane. Definition (Incidence matrix). An incidence matrix of a finite ...
[25]
[PDF] An Introduction to Finite Geometry
Sep 5, 2011 · 1.7 Affine planes. An affine plane is an incidence structure of points and lines with the following properties. (AP1) Every two points are ...
[26]
[PDF] Matrix techniques for strongly regular graphs and related geometries
This algebra was first studied by Bose &. Mesner [5] and is called the Bose-Mesner algebra of the association scheme. Since the matrices Ai commute, they can be ...
[27]
On Linear Associative Algebras Corresponding to ... - Project Euclid
March, 1959 On Linear Associative Algebras Corresponding to Association Schemes of Partially Balanced Designs. R. C. Bose, Dale M. Mesner · DOWNLOAD PDF + SAVE ...
[28]
None
Below is a merged summary of the sections from Allen Hatcher's "Algebraic Topology" based on the provided summaries, consolidating all information into a comprehensive response. To retain as much detail as possible, I will use a table format for clarity and density, followed by a narrative summary for additional context. The table will cover definitions, key details, and references across the topics: Simplicial Complexes, Chain Complexes, Incidence Matrices, Boundary Operators, Euler Characteristic, and Poincaré's Use for Betti Numbers. All unique information from the summaries is included, with page references and URLs where provided.
[29]
[PDF] Balanced Incomplete Block Designs and Other Combinatorial Objects
Theorem 1.3 For A, the incidence matrix of a given {v, k, λ} design, we have. AAT = (r − λ)I + λJ,. (5) where I is the v × v identity matrix and J is a v × v ...
[30]
[PDF] Theory Of Block Designs - Indian Statistical Institute, Bangalore
Incidence matrices are a convenient way of expressing BIBD's in a matrix form. Definition 1.3.1 Incidence Matrix. Let (X,A) be a design where X = {x1,...,xv} ...
[31]
Balanced generalized weighing matrices and conference matrices
A balanced weighing matrix is the incidence matrix of a symmetrical balanced incomplete block design (SBIBD) in which some of the ″ones″ are replaced by ...
[32]
[PDF] Chapter 7 Block Designs
chapter provides an introduction to association schemes, the Bose-Mesner algebra, and ... Let N be the incidence matrix (points versus blocks) of a partial design.
[33]
[PDF] Lecture 8: Matroids
Oct 8, 2009 · Definition 4 A binary matroid is a linear matroid that can be represented over GF(2). ... incidence matrix with a +1 and a −1 in each edge column.
[34]
[PDF] On the Abstract Properties of Linear Dependence - GRAAL
Author(s): Hassler Whitney. Source: American Journal of Mathematics, Vol. 57, No. 3 (Jul., 1935), pp. 509-533. Published by: The Johns Hopkins University ...Missing: paper | Show results with:paper
[35]
[PDF] Matroid Basics
Transversal Matroid. For the bipartite graph with partition A and B, form an incidence matrix AM as follows. Label the rows by vertices of B and the columns ...
[36]
[PDF] On the Complexity of Recovering Incidence Matrices - DROPS
Question: Decide whether M = L + S, where L is a binary matrix of weight at most r,. S is the incidence matrix of a graph in C and the sums are taken over GF(2) ...
[37]
[PDF] Graphs and Network Flows ISE 411 Lecture 2
– Which representation(s) could accommodate them? • Undirected Network. – What needs to change? ∗ Node-Arc Incidence Matrix. ∗ Node-Node Adjacency Matrix.
[38]
[PDF] Lecture 17 Network flow optimization
arc-node incidence matrix: m × n matrix A with entries. Aij =.. 1 if arc j starts at node i. −1 if arc j ends at node i. 0 otherwise. Network flow ...
[39]
[PDF] Chapter 10 Applications - MIT Mathematics
It is essential to connect the subspaces to the graph they come from. By specializing to incidence matrices, the laws of linear algebra become Kirchhoff's laws.
[40]
[PDF] maximal flow through a network - lr ford, jr. and dr fulkerson
Introduction. The problem discussed in this paper was formulated by. T. Harris as follows: "Consider a rail network connecting two cities by ...
[41]
[PDF] Direct Solutions of Sparse Network Equations by Optimally Ordered ...
The method consists of two parts : 1) a scheme of record- ing the operations of triangular decomposition of a matrix such that repeated direct solutions based ...