- Incidence Matrix Definition: An incidence matrix is defined as a matrix representing a graph, with rows for nodes and columns for branches.
- Matrix Entries: The entries in an incidence matrix are -1 for incoming branches, +1 for outgoing branches, and 0 for others.
- Construction Steps: To construct an incidence matrix, assign +1 to outgoing branches, -1 to incoming branches, and 0 to other branches.
- Reduced Incidence Matrix: A reduced incidence matrix is formed by deleting any row from the original incidence matrix.
- Correctness Check: To verify an incidence matrix, ensure the sum of each column is zero.
An incidence matrix records which nodes and branches are connected in a graph. In the convention used here, the matrix [AC] has one row for each node and one column for each branch.
If [AC] has n rows and m columns, the graph has n labelled nodes and m labelled branches. The signed entries also record the selected direction of each branch. Given the labels and orientation, [AC] contains the graph’s endpoint information.
The directed graph shown has four nodes and six branches, so its incidence matrix has four rows and six columns.
This page uses +1 where a branch leaves a node, -1 where it enters a node and 0 elsewhere. That sign convention is compatible with Kirchhoff’s Current Law (KCL). Some texts reverse both signs; either convention works when used consistently.
| Branch relationship to row node | Matrix entry |
| Outgoing branch from kth node | +1 |
| Incoming branch to kth node | -1 |
| Branch not incident on the node | 0 |
Steps to Construct an Incidence Matrix
Use these steps for the outgoing-positive convention:
- For each kth node, write +1 in every column whose branch leaves that node.
- Write -1 in every column whose branch enters the kth node.
- Write 0 for every branch that is not incident on that node.
Incidence Matrix Example
Write the incidence matrix for the graph shown above.
Reduced Incidence Matrix
Deleting one row from an incidence matrix [AC] gives a reduced incidence matrix, denoted [A]. For a graph with n nodes and b branches, this reduced matrix has n – 1 rows and b columns. If the graph is connected, any one row may be removed and the reduced matrix has full row rank.
For the graph above, one reduced incidence matrix is:
[NOTE :- In the above shown matrix row 4 is deleted.]
Now consider the second directed graph and construct its reduced incidence matrix.
Answer:- First construct the complete incidence matrix using the same branch orientation and sign convention.
Then remove the chosen reference-node row. In this example, the row for Node 2 is removed.
The displayed matrix is the required reduced incidence matrix.
Points to remember
- For an ordinary branch joining two distinct nodes, check that its column contains one +1, one -1 and zeros elsewhere.
- Every ordinary branch column sums to zero, but a zero sum alone does not prove that the column or full matrix is correct.
- An undirected graph can use a 0-1 incidence matrix or can be given an arbitrary orientation to form a signed incidence matrix.
- For a graph without self-loops, the number of nonzero entries in a node row equals its degree. For a directed graph, the total degree equals in-degree plus out-degree.
- The rank of a complete incidence matrix equals n – c, where n is the number of nodes and c is the number of connected components. A connected graph has c = 1 and rank n – 1.
- The order of the node-branch incidence matrix is n × b, where b is the number of branches.
- To reconstruct the complete incidence matrix from a reduced incidence matrix, calculate each missing-row entry as the negative sum of the remaining entries in that column. This makes every ordinary branch column sum to zero.
