Linear Algebra and Its Applications, Exercise 2.5.8

Exercise 2.5.8. State the dimensions of the four fundamental subspaces of the incidence matrix A 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

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}

From exercise 2.5.7 we know that Gaussian elimination on A produces the following echelon matrix U:

U = \begin{bmatrix} -1&1&0&0 \\ 0&-1&1&0 \\ 0&0&0&0 \\ 0&0&-1&1 \\ 0&0&0&0 \\ 0&0&0&0 \end{bmatrix}

This matrix has three pivots, in columns 1, 2, and 3, and its rank r is therefore 3. The rank is the dimension of the column space of U. Since the column space of A is the same as \mathcal R(U) the dimension of \mathcal R(A) is also 3. The first, second, and third columns of A form a basis for \mathcal R(A):

\begin{bmatrix} -1 \\ -1 \\ 0 \\ 0 \\ -1 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 1 \\ 0 \\ -1 \\ -1 \\ 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ -1 \end{bmatrix}

Since the dimension r of the column space \mathcal R(A) is 3 and the number of columns n is 4, the dimension of the nullspace \mathcal N(A) is n - r = 4 - 3 = 1. Since the sum of the columns of A is zero the vector

\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}

is a solution to Ax = 0 and forms a basis for \mathcal N(A).

The dimension of the row space of A is the same as the dimension of the column space, namely r = 3. The row space of A is also the same as the row space of U (since the process of elimination means that the rows of U are linear combinations of the rows of U). The first, second, and fourth rows of U

\begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 0 \\ -1 \\ 1 \end{bmatrix}

form a basis for the row space \mathcal R(U^T) and therefore for the rowspace \mathcal R(A^T) as well.

Since the dimension r of the row space \mathcal R(A^T) is 3 and the number of rows m is 6, the dimension of the left nullspace \mathcal N(A^T) is m - r = 6 - 3 = 3.

From exercise 2.5.6 we know that the vectors

\begin{bmatrix} 1 \\ -1 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} -1 \\ 0 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} -1 \\ 1 \\ 0 \\ -1 \\ 0 \\ 1 \end{bmatrix}

are solutions to y^TA = 0 and are therefore in the left nullspace \mathcal N(A^T).

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 \mathcal N(A^T) and the dimension of \mathcal N(A^T) 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.

 Buy me a snack to sponsor more posts like this!

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s