## 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 .

This entry was posted in linear algebra. Bookmark the permalink.

### 1 Response to Linear Algebra and Its Applications, Exercise 2.5.10

1. Filipe says:

Very good!
Post these questions: 2.5.12, 2.5.16 and 2.6.4, 2.6.10, 2.6.16.
I didn’t get to do.