## Linear Algebra and Its Applications, Exercise 2.5.6

Exercise 2.5.6. Determine the incidence matrix $A$ for the graph on page 113 with six edges and four nodes, as follows: Edge 1 from node 1 to node 2, edge 2 from node 1 to node 3, edge 3 from node 2 to node 3, edge 4 from node 2 to node 4, edge 5 from node 1 to node 4, and edge 6 from node 3 to node 4.

Find three independent vectors $y$ that satisfy $A^Ty = 0$. How do these vectors relate to the loops in the graph?

Answer: Since there are six edges in the graph the incidence matrix $A$ has six rows, and since there are four nodes $A$ has four columns; $A$ is therefore a 6 by 4 matrix.

The first row of $A$ corresponds to edge 1. Since edge 1 goes from node 1 to node 2 the entry in the (1, 1) position is -1 (representing “flow” out of node 1) and the entry in the (1, 2) position is 1 (representing flow into node 2). Since edge 2 goes from node 1 to node 3 the entry in the (2, 1) position is -1 (representing flow out of node 1) and the entry in the (2, 3) position is 1 (representing flow into node 3). The values of the entries for the other rows (edges) can be similarly determined, and the final incidence matrix is $A = \begin{bmatrix} -1&1&0&0 \\ -1&0&1&0 \\ 0&-1&1&0 \\ 0&-1&0&1 \\ -1&0&0&1 \\ 0&0&-1&1 \end{bmatrix}$

We now try to find a solution to $A^Ty = 0$ or $\begin{bmatrix} -1&-1&0&0&-1&0 \\ 1&0&-1&-1&0&0 \\ 0&1&1&0&0&-1 \\ 0&0&0&1&1&1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \\ y_6 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$

by doing Gaussian elimination on $A^T$.

We first subtract -1 times the first row from the second row: $\begin{bmatrix} -1&-1&0&0&-1&0 \\ 1&0&-1&-1&0&0 \\ 0&1&1&0&0&-1 \\ 0&0&0&1&1&1 \end{bmatrix} \Rightarrow \begin{bmatrix} -1&-1&0&0&-1&0 \\ 0&-1&-1&-1&-1&0 \\ 0&1&1&0&0&-1 \\ 0&0&0&1&1&1 \end{bmatrix}$

We then subtract -1 times the second row from the third row: $\begin{bmatrix} -1&-1&0&0&-1&0 \\ 0&-1&-1&-1&-1&0 \\ 0&1&1&0&0&-1 \\ 0&0&0&1&1&1 \end{bmatrix} \Rightarrow \begin{bmatrix} -1&-1&0&0&-1&0 \\ 0&-1&-1&-1&-1&0 \\ 0&0&0&-1&-1&-1 \\ 0&0&0&1&1&1 \end{bmatrix}$

Finally, we subtract -1 times the third row from the fourth row: $\begin{bmatrix} -1&-1&0&0&-1&0 \\ 0&-1&-1&-1&-1&0 \\ 0&0&0&-1&-1&-1 \\ 0&0&0&1&1&1 \end{bmatrix} \Rightarrow \begin{bmatrix} -1&-1&0&0&-1&0 \\ 0&-1&-1&-1&-1&0 \\ 0&0&0&-1&-1&-1 \\ 0&0&0&0&0&0 \end{bmatrix}$

The resulting echelon matrix has pivots in columns one, two, and four, so $y_1$, $y_2$, and $y_4$ are basic variables and $y_3$, $y_5$, and $y_6$ are free variables.

We first set $y_3 = 1$ and $y_5 = y_6 = 0$. From the third row of the echelon matrix we have $-y_4 - y_5 - y_6 = 0 \rightarrow y_4 - 0 - 0 = 0$ $\rightarrow y_4 = 0$

From the second row of the echelon matrix we have $-y_2 - y_3 - y_4 - y_5 = 0 \rightarrow -y_2 - 1 - 0 - 0 = 0$ $\rightarrow y_2 = -1$

and from the first row we then have $-y_1 - y_2 - y_5 = 0 \rightarrow -y_1 - (-1) = 0$ $\rightarrow y_1 = 1$

So one solution to $A^Ty = 0$ is $\begin{bmatrix} 1&-1&1&0&0&0 \end{bmatrix}^T$.

We next set $y_5 = 1$ and $y_3 = y_6 = 0$. From the third row of the echelon matrix we have $-y_4 - y_5 - y_6 = 0 \rightarrow -y_4 - 1 - 0 = 0$ $\rightarrow y_4 = -1$

From the second row of the echelon matrix we have $-y_2 - y_3 - y_4 - y_5 = 0 \rightarrow -y_2 - 0 - (-1) - 1 = 0$ $\rightarrow y_2 = 0$

and from the first row we then have $-y_1 - y_2 - y_5 = 0 \rightarrow -y_1 - 0 - 1 = 0$ $\rightarrow y_1 = -1$

So a second solution to $A^Ty = 0$ is $\begin{bmatrix} -1&0&0&-1&1&0 \end{bmatrix}^T$.

Finally we set $y_6 = 1$ and $y_3 = y_5 = 0$. From the third row of the echelon matrix we have $-y_4 - y_5 - y_6 = 0 \rightarrow -y_4 - 0 - 1 = 0$ $\rightarrow y_4 = -1$

From the second row of the echelon matrix we have $-y_2 - y_3 - y_4 - y_5 = 0 \rightarrow -y_2 - 0 - (-1) - 0 = 0$ $\rightarrow y_2 = 1$

and from the first row we then have $-y_1 - y_2 - y_5 = 0 \rightarrow -y_1 - 1 - 0 = 0$ $\rightarrow y_1 = -1$

So a third solution to $A^Ty = 0$ is $\begin{bmatrix} -1&1&0&-1&0&1 \end{bmatrix}^T$.

The following set of three vectors $u$, $v$, and $w$ are thus solutions to $A^Ty = 0$. The vectors are independent (as you can verify by inspecting them): $u = \begin{bmatrix} 1 \\ -1 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \qquad v = \begin{bmatrix} -1 \\ 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \qquad w = \begin{bmatrix} -1 \\ 1 \\ 0 \\ -1 \\ 0 \\ 1 \end{bmatrix}$

Since $A^Ty = y^TA$ the vectors are in the left nullspace of $A$. (In fact they form a basis for the left nullspace.)

The vectors also correspond to independent loops in the graph used to create the incidence matrix $A$:

The first vector $u$ is a loop around the outside of the graph, and includes edge 1, edge 2, and edge 3. Note that edge 2 runs in a different direction than the other two, and hence its corresponding entry is reversed in sign from the other two.

The second vector $v$ is a loop around an interior triangle of the graph (in the upper left), and includes edge 1, edge 4, and edge 5, with edge 5 running in a different direction than the other two.

The third vector $w$ includes edges 1, 2, 4, and 6, with edges 2 and 6 running in different directions than the other two.

Note that if we add $u$ and $w$ $u + w = \begin{bmatrix} 1 \\ -1 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \begin{bmatrix} -1 \\ 1 \\ 0 \\ -1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 0 \\ 1 \end{bmatrix}$

we get a vector representing a loop around the bottom interior triangle of the graph, comprising edges 3, 4, and 6.

Similarly, if we subtract $v$ from $w$ $w - v = \begin{bmatrix} -1 \\ 1 \\ 0 \\ -1 \\ 0 \\ 1 \end{bmatrix} - \begin{bmatrix} -1 \\ 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ -1 \\ 1 \end{bmatrix}$

we get a vector representing the loop around the upper right interior triangle, comprising edges 2, 5, and 6.

These two vectors together with $v$ thus represent independent loops associated with the three interior triangles of the graph.

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.