Linear Algebra and Its Applications, Exercise 2.5.1

Exercise 2.5.1. Describe the incidence matrix $A$ 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 $Ax = 0$ . What vectors are in the nullspace $\mathcal N(A)$ ? Also find a solution to $A^Ty = 0$ . What vectors are in the left nullspace $\mathcal N(A^T)$ ?

Answer: Since the graph has three edges the incidence matrix $A$ has three rows, and since it has three nodes $A$ has three columns. The incidence matrix is

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

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 $r = 2$ and the dimensions of the nullspace and left nullspace are $n - r = 3 - 2 = 1$ and $m - r = 3 - 2 = 1$ respectively.

Since the entries in each row sum to zero, the vector $x = \begin{bmatrix} 1&1&1 \end{bmatrix}^T$ is a solution to $Ax = 0$ and a basis for the (1-dimensional) nullspace $\mathcal N(A)$ . The nullspace is then the set of all vectors $\begin{bmatrix} c&c&c \end{bmatrix}^T$ where $c$ is some scalar value.

Since $A^Ty = y^TA$ we can find a vector in the left nullspace by looking for a vector that can multiply each column of $A$ and produce zero. A little experimentation produces the vector $y = \begin{bmatrix} 1&1&-1 \end{bmatrix}^T$ as a solution to $y^TA = A^Ty$ and a basis for the (1-dimensional) left nullspace $\mathcal N(A^T)$ . The left nullspace is then the set of all vectors $\begin{bmatrix} c&c&-c \end{bmatrix}^T$ where $c$ is some scalar value.

UPDATE: Added a paragraph to clarify what the rows of $A$ 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.

Buy me a snack to sponsor more posts like this!

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

2 Responses to Linear Algebra and Its Applications, Exercise 2.5.1

James says:

September 17, 2012 at 8:19 pm

Keep up the good, fun work! Eventually your blog will be a repository for solutions to the Strang book. I’m working through the problems along with you. I haven’t answered every question, but I’ve attempted most that I’ve come across so far. I spend some time on OpenStudy in which they have a section devoted to people working through the Strang online text. Maybe I’ll see you there sometime. 🙂 Happy re (learning).

- hecker says:
  
  September 18, 2012 at 1:23 am
  
  Thanks for stopping by; I always enjoy hearing from folks who read this blog and find it useful. I haven’t had time to stop by OpenStudy, and in fact haven’t had time to schedule any more posts on this blog, but comments like yours motivate me to get back to work on this.