## 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 .

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