Exercise 2.5.8. State the dimensions of the four fundamental subspaces of the incidence matrix from exercise 2.5.6 (for the graph on page 113 with six edges and four nodes) and provide a set of basis vectors for each subspace.
Answer: The matrix in question is
From exercise 2.5.7 we know that Gaussian elimination on produces the following echelon matrix :
This matrix has three pivots, in columns 1, 2, and 3, and its rank is therefore 3. The rank is the dimension of the column space of . Since the column space of is the same as the dimension of is also 3. The first, second, and third columns of form a basis for :
Since the dimension of the column space is 3 and the number of columns is 4, the dimension of the nullspace is . Since the sum of the columns of is zero the vector
is a solution to and forms a basis for .
The dimension of the row space of is the same as the dimension of the column space, namely . The row space of is also the same as the row space of (since the process of elimination means that the rows of are linear combinations of the rows of ). The first, second, and fourth rows of
form a basis for the row space and therefore for the rowspace as well.
Since the dimension of the row space is 3 and the number of rows is 6, the dimension of the left nullspace is .
From exercise 2.5.6 we know that the vectors
are solutions to and are therefore in the left nullspace .
Note also that the vectors are linearly independent: Since the first two vectors have zero are their last entry and the third vector has 1, there is no way to form a linear combination of the first two vectors that is equal to the third. Similarly there is no way to form a linear combination of the second and third vectors that is equal to the first, or a linear combination of the first and third vectors that equals the second. (This can be seen by looking at the third and fifth entries of the vectors respectively.)
Since the three linearly independent vectors are in the left nullspace and the dimension of is 3, the three vectors form a basis for the space.
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.