Linear Algebra and Its Applications, Exercise 2.5.10

Exercise 2.5.10. Given the incidence matrix

$A = \begin{bmatrix} -1&1&0&0 \\ -1&0&1&0 \\ 0&1&0&-1 \\ 0&0&-1&1 \end{bmatrix}$

draw the graph corresponding to the matrix, and state whether or not it is a tree and the rows are linearly independent. Demonstrate that removing a row produces a spanning tree, and describe the subspace of which the remaining rows form a basis.

Answer: The incidence matrix has four nodes, corresponding to the columns, and four edges, corresponding to the rows. The nodes can be arranged in the form of a square. Put node 1 in the upper left corner of the square. Edge 1 runs from node 1 to node 2; put node 2 in the lower left corner of the square, so that edge 2 forms the left side of the square. Edge 2 runs from node 1 to node 3; put node 3 in the upper right corner of the square, so that edge 2 forms the top side of the square.

Put the remaining node 4 in the lower right corner of the square. Edge 3 runs from node 4 to node 2, and thus forms the bottom side of the square. Edge 4 runs from node 3 to node 4, and thus forms the right side of the square.

Since the four edges form a loop (in the shape of a square) the graph is not a tree. Also, the rows are not linearly independent, since the first row minus the sum of the second and third rows equals the fourth row:

$\begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix} - \left( \begin{bmatrix} -1 \\ 0 \\ 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \\ 0 \\ -1 \end{bmatrix} \right)$

$= \begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix} - \begin{bmatrix} -1 \\ 1 \\ 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \end{bmatrix}$

If we remove the fourth row and the corresponding edge (i.e., the bottom side of the square) then the resulting three edges form a spanning tree, since they touch all four nodes and have no loops. The remaining three rows are linearly independent and form a basis for the row space $\mathcal R(A^T)$ .

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.

Buy me a snack to sponsor more posts like this!