Exercise 2.5.1. Describe the incidence matrix for the following graph:
The graph has three nodes and three edges, with edge 1 going from node 2 to node 1, edge 2 going from node 3 to node 2, and edge 3 going from node 3 to node 1.
Find a solution to . What vectors are in the nullspace ? Also find a solution to . What vectors are in the left nullspace ?
Answer: Since the graph has three edges the incidence matrix has three rows, and since it has three nodes has three columns. The incidence matrix is
The first row represents edge 1 from node 2 to node 1 (i.e., leaving node 2 and entering node 1). The second row represents edge 2 from node 3 to node 2. The third row represents edge 3 from node 3 to node 1.
The sum of the first and second rows equals the third row, so the rank and the dimensions of the nullspace and left nullspace are and respectively.
Since the entries in each row sum to zero, the vector is a solution to and a basis for the (1-dimensional) nullspace . The nullspace is then the set of all vectors where is some scalar value.
Since we can find a vector in the left nullspace by looking for a vector that can multiply each column of and produce zero. A little experimentation produces the vector as a solution to and a basis for the (1-dimensional) left nullspace . The left nullspace is then the set of all vectors where is some scalar value.
UPDATE: Added a paragraph to clarify what the rows of represent.
NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.
If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.