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!