Linear Algebra and Its Applications, Exercise 2.4.12

Exercise 2.4.12. Suppose that for a matrix A the system Ax = 0 has at least one nonzero solution. Show that there exists at least one vector f for which the system A^Ty = f has no solution. Show an example of such a matrix A and vector f.

Answer: Suppose A is an m by n matrix. If there exists a nonzero x = \begin{bmatrix} x_1&x_2&\cdots&x_n \end{bmatrix}^T for which Ax = 0 then the columns of A are linearly dependent. (If they were linearly independent then Ax = 0 would imply that x_i = 0 for all 1 \le i \le n.) We therefore have the rank r < n.

Since r < n and the dimension of the row space \mathcal R(A^T) is equal to r the dimension of \mathcal R(A^T) is less than n. In other words, the rows of A do not span all of \mathbf R^n.

But if that is the case then there exists at least one vector f in \mathbf R^n that is not in \mathcal R(A^T) and cannot be expressed as a linear combination of the rows of A. Therefore for the vector f there is no solution to the system A^Ty = f. (If there were such a solution then its coefficients y_1, y_2, \dotsc, y_m would define a linear combination of the rows of A equal to f.)

For example, suppose that we have the following 2 by 2 matrix

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

The system Ax = 0 is equivalent to

\begin{bmatrix} 1&-1 \\ 0&0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}

This system has rank r = 1 with x_1 as a basic variable and x_2 as a free variable.

From the first equation of the system we have x_1 - x_2 = 0 or x_1 = x_2. If we set the free variable x_2 to 1 we then have x_1 = 1 and x = \begin{bmatrix} 1 \\ 1 \end{bmatrix} as a (nonzero) solution to Ax = 0.

The vector \begin{bmatrix} 1 \\ -1 \end{bmatrix} is a basis for the row space \mathcal R(A^T), which consists of all vectors of the form \begin{bmatrix} c \\ -c \end{bmatrix}. Geometically this is a line through the origin and the point (1, -1).

Pick a point in the x-y plane not on this line, for example (1, 0), and consider the vector f = \begin{bmatrix} 1 \\ 0 \end{bmatrix} and the system

A^Ty = \begin{bmatrix} 1&0 \\ -1&0 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} = f

The first equation of the system produces y_1 = 1 while the second equation produces y_1 = -1, a contradiction. There is thus no solution to A^Ty = f for the example values of A and f.

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