Problem Set 7: Injective, Surjective, and Invertible

For each matrix $A$ below, decide whether $T_A$ is injective, surjective, and/or bijective. Justify your answers. You may use the Row Reducer to help you calculate.

1. $A = \begin{bmatrix} 1 & 1 \\ 2 & 3 \\ 3 & 4 \end{bmatrix}$

   Solution

   We row reduce $A$ to row echelon form.

   \[ \begin{aligned} &\left[\begin{array}{cc} 1 & 1 \\ 2 & 3 \\ 3 & 4 \end{array}\right] \xrightarrow{R_{2} \to R_{2} - 2\,R_{1}} \left[\begin{array}{cc} 1 & 1 \\ 0 & 1 \\ 3 & 4 \end{array}\right] \xrightarrow{R_{3} \to R_{3} - 3\,R_{1}} \left[\begin{array}{cc} 1 & 1 \\ 0 & 1 \\ 0 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - R_{2}} \left[\begin{array}{cc} 1 & 1 \\ 0 & 1 \\ 0 & 0 \end{array}\right] \end{aligned} \]

   Every column has a pivot, so $Ax = 0$ has only the trivial solution and $T_A$ is injective. The third row has no pivot, so $\rank(A) = 2 < 3$ and $\col(A)$ is not all of $\RR^3$. So $T_A$ is not surjective, and therefore not bijective.

2. $A = \begin{bmatrix} 1 & 2 & 1 \\ 2 & 1 & 1 \end{bmatrix}$

   Solution

   We row reduce $A$ to row echelon form.

   \[ \begin{aligned} &\left[\begin{array}{ccc} 1 & 2 & 1 \\ 2 & 1 & 1 \end{array}\right] \xrightarrow{R_{2} \to R_{2} - 2\,R_{1}} \left[\begin{array}{ccc} 1 & 2 & 1 \\ 0 & \llap{$-$}3 & \llap{$-$}1 \end{array}\right] \end{aligned} \]

   Every row has a pivot, so $\rank(A) = 2$, $\col(A) = \RR^2$, and $T_A$ is surjective. The third column has no pivot, so $x_3$ is a free variable and $Ax = 0$ has nonzero solutions. So $T_A$ is not injective, and therefore not bijective.

3. $A = \begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 & 3 \\ 3 & 2 & 5 \end{bmatrix}$

   Solution

   We row reduce $A$ to row echelon form.

   \[ \begin{aligned} &\left[\begin{array}{ccc} 1 & 1 & 2 \\ 2 & 1 & 3 \\ 3 & 2 & 5 \end{array}\right] \xrightarrow{R_{2} \to R_{2} - 2\,R_{1}} \left[\begin{array}{ccc} 1 & 1 & 2 \\ 0 & \llap{$-$}1 & \llap{$-$}1 \\ 3 & 2 & 5 \end{array}\right] \xrightarrow{R_{3} \to R_{3} - 3\,R_{1}} \left[\begin{array}{ccc} 1 & 1 & 2 \\ 0 & \llap{$-$}1 & \llap{$-$}1 \\ 0 & \llap{$-$}1 & \llap{$-$}1 \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - R_{2}} \left[\begin{array}{ccc} 1 & 1 & 2 \\ 0 & \llap{$-$}1 & \llap{$-$}1 \\ 0 & 0 & 0 \end{array}\right] \end{aligned} \]

   There are only two pivots. The third column has no pivot, so $Ax = 0$ has nonzero solutions and $T_A$ is not injective. The third row has no pivot, so $\rank(A) = 2 < 3$ and $T_A$ is not surjective. So $T_A$ is neither injective nor surjective, and not bijective.

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

   Solution

   We row reduce $A$ to row echelon form.

   \[ \begin{aligned} &\left[\begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{array}\right] \xrightarrow{R_{3} \to R_{3} - R_{1}} \left[\begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & \llap{$-$}1 & 1 \end{array}\right] \xrightarrow{R_{3} \to R_{3} + R_{2}} \left[\begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{array}\right] \end{aligned} \]

   There is a pivot in every column, so $T_A$ is injective, and a pivot in every row, so $T_A$ is surjective. So $T_A$ is bijective, and $A$ is invertible.

A tiny camera takes black-and-white photos that are a single row of four pixels, with brightness values $x_1, x_2, x_3, x_4$. The photographer's hands shake, so instead of the sharp image $x = (x_1, x_2, x_3, x_4)$ the camera records a blurred image $b = (b_1, b_2, b_3)$ in which each pixel is the average of two neighboring sharp pixels: \[ b_1 = \tfrac{1}{2}(x_1 + x_2),\qquad b_2 = \tfrac{1}{2}(x_2 + x_3),\qquad b_3 = \tfrac{1}{2}(x_3 + x_4). \] In other words, $b = Bx$ where \[ B = \frac{1}{2} \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}. \]

1. Explain why $T_B$ is not injective by finding a sharp image other than $(4, 4, 4, 4)$ that blurs to $b = (4, 4, 4)$.

   Solution

   The equation $Bx = (4, 4, 4)$ says \[ x_1 + x_2 = 8,\qquad x_2 + x_3 = 8,\qquad x_3 + x_4 = 8. \] Subtracting the second equation from the first gives $x_1 = x_3$, and subtracting the third from the second gives $x_2 = x_4$. So the solutions are the images $(s, 8 - s, s, 8 - s)$, and the solution set is \[ x = \begin{bmatrix} 4 \\ 4 \\ 4 \\ 4 \end{bmatrix} + t \begin{bmatrix*}[r] 1 \\ -1 \\ 1 \\ -1 \end{bmatrix*}. \] For example, the sharp image $(5, 3, 5, 3)$ also blurs to $(4, 4, 4)$. Two different sharp images have the same blurred image, so $T_B$ is not injective. No unblurring procedure can exist, since it would have to send $(4, 4, 4)$ back to both $(4, 4, 4, 4)$ and $(5, 3, 5, 3)$.

2. Is every vector $b$ in $\RR^3$ the blurred image of some sharp image? Explain.

   Solution

   Yes. The matrix $B$ is already in row echelon form, with a pivot in each of its three rows. So $\rank(B) = 3$, $\col(B) = \RR^3$, and $T_B$ is surjective. Every $b$ in $\RR^3$ is the blurred image of some sharp image, and by part (a) in fact of infinitely many.

3. The camera is upgraded so that it also records the first pixel $x_1$ sharply. The recorded data is now $y = (x_1, b_1, b_2, b_3) = Cx$, where \[ C = \frac{1}{2} \begin{bmatrix} 2 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}. \] Explain why $C$ is invertible.

   Solution

   We row reduce $C$ to row echelon form.

   \[ \begin{aligned} &\left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \xrightarrow{R_{2} \to R_{2} - \frac{1}{2}\,R_{1}} \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - R_{2}} \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{array}\right] \xrightarrow{R_{4} \to R_{4} - R_{3}} \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \end{array}\right] \end{aligned} \]

   There is a pivot in every row and every column, so $T_C$ is both surjective and injective. A square matrix whose transformation is bijective is invertible, so $C$ is invertible.

4. Find $C^{-1}$.

   Solution

   The matrix $C^{-1}$ sends the recorded data $y = Cx$ back to the sharp image $x$, so we solve the equations \[ y_1 = x_1,\qquad y_2 = \tfrac{1}{2}(x_1 + x_2),\qquad y_3 = \tfrac{1}{2}(x_2 + x_3),\qquad y_4 = \tfrac{1}{2}(x_3 + x_4) \] for the $x_i$ in terms of the $y_i$, one pixel at a time:

   \[\begin{aligned} x_1 &= y_1, \\ x_2 &= 2y_2 - x_1 = -y_1 + 2y_2, \\ x_3 &= 2y_3 - x_2 = y_1 - 2y_2 + 2y_3, \\ x_4 &= 2y_4 - x_3 = -y_1 + 2y_2 - 2y_3 + 2y_4. \end{aligned}\]

   Reading off the coefficients, \[ C^{-1} = \begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ -1 & 2 & 0 & 0 \\ 1 & -2 & 2 & 0 \\ -1 & 2 & -2 & 2 \end{bmatrix*}. \] Row reducing $[\,C \mid I_4\,]$ gives the same answer.

5. The upgraded camera records $y = (2, 3, 4, 5)$. Recover the sharp image.

   Solution

   The sharp image is

   As a check, the first pixel is $2$ and the averages of neighboring pixels are $3$, $4$, and $5$, as recorded.

For each statement below, decide whether it is true or false. If it is true, explain why. If it is false, give an example of a matrix $A$ for which it fails.

1. If $A$ is a $3 \times 5$ matrix, then $T_A$ is not injective.

   Solution

   True. A row echelon form of $A$ has at most $3$ pivots, one per row, but $A$ has $5$ columns. So at least $2$ columns have no pivot, which means $Ax = 0$ has free variables and therefore nonzero solutions. So $T_A$ is not injective.

2. If $A$ is a $3 \times 5$ matrix and $T_A$ is surjective, then the solution set of $Ax = 0$ is a plane through the origin.

   Solution

   True. Since $T_A$ is surjective, $\col(A) = \RR^3$ and $\rank(A) = 3$. By the Rank-Nullity Theorem, $\nullity(A) = 5 - 3 = 2$. So the solution set of $Ax = 0$ is the $2$-dimensional subspace $\Nul(A)$ of $\RR^5$, which is a plane through the origin.

3. If $A$ is a $2 \times 3$ matrix, then $T_A$ is surjective.

   Solution

   False. For example, if \[ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \] then $\rank(A) = 1$, so $\col(A)$ is the line spanned by $(1, 1)$ rather than all of $\RR^2$. The vector $(1, 0)$ is not in the image of $T_A$.

4. If $A$ is a $2 \times 2$ matrix with $A^{-1} = A$, then $A = I_2$ or $A = -I_2$.

   Solution

   False. The condition $A^{-1} = A$ says that $A A = I_2$. For example, if \[ A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \] then \[ AA = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \] so $A^{-1} = A$, but $A$ is neither $I$ nor $-I$. Geometrically, $T_A$ is the reflection across the line $y = x$, and reflecting twice returns every point to where it started.

5. If $A$ is a $4 \times 4$ matrix and there are two different vectors $x \neq y$ in $\RR^4$ with $Ax = Ay$, then $T_A$ is not surjective.

   Solution

   True. Since $Ax = Ay$, we have $A(x - y) = 0$, and $x - y \neq 0$. So $\Nul(A)$ contains a nonzero vector and $\nullity(A) \geq 1$. By the Rank-Nullity Theorem, $\rank(A) = 4 - \nullity(A) \leq 3$, so $\col(A)$ is not all of $\RR^4$ and $T_A$ is not surjective.

6. If the columns of $A$ are linearly independent, then $A$ is invertible.

   Solution

   False. Only square matrices can be invertible. For example, the columns of the $3 \times 2$ matrix \[ A = \begin{bmatrix} 1 & 1 \\ 2 & 3 \\ 3 & 4 \end{bmatrix} \] from Problem 1(a) are linearly independent, but $T_A$ is not surjective, so $T_A$ is not bijective and $A$ is not invertible.

Let \[ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 3 & 6 \end{bmatrix}. \] You may use the Row Reducer to help you calculate.

1. Find $A^{-1}$.

   Solution

   We row reduce $[\,A \mid I\,]$ to reduced row echelon form.

   \[ \begin{aligned} &\left[\begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 2 & 3 & 0 & 1 & 0 \\ 1 & 3 & 6 & 0 & 0 & 1 \end{array}\right] \xrightarrow{R_{2} \to R_{2} - R_{1}} \left[\begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & \llap{$-$}1 & 1 & 0 \\ 1 & 3 & 6 & 0 & 0 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - R_{1}} \left[\begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & \llap{$-$}1 & 1 & 0 \\ 0 & 2 & 5 & \llap{$-$}1 & 0 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - 2\,R_{2}} \left[\begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & \llap{$-$}1 & 1 & 0 \\ 0 & 0 & 1 & 1 & \llap{$-$}2 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{1} \to R_{1} - R_{3}} \left[\begin{array}{ccc|ccc} 1 & 1 & 0 & 0 & 2 & \llap{$-$}1 \\ 0 & 1 & 2 & \llap{$-$}1 & 1 & 0 \\ 0 & 0 & 1 & 1 & \llap{$-$}2 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{2} \to R_{2} - 2\,R_{3}} \left[\begin{array}{ccc|ccc} 1 & 1 & 0 & 0 & 2 & \llap{$-$}1 \\ 0 & 1 & 0 & \llap{$-$}3 & 5 & \llap{$-$}2 \\ 0 & 0 & 1 & 1 & \llap{$-$}2 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{1} \to R_{1} - R_{2}} \left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 3 & \llap{$-$}3 & 1 \\ 0 & 1 & 0 & \llap{$-$}3 & 5 & \llap{$-$}2 \\ 0 & 0 & 1 & 1 & \llap{$-$}2 & 1 \end{array}\right] \end{aligned} \]

   The left half is now the identity, so the right half is the inverse: \[ A^{-1} = \begin{bmatrix*}[r] 3 & -3 & 1 \\ -3 & 5 & -2 \\ 1 & -2 & 1 \end{bmatrix*}. \] As a check,

2. Use $A^{-1}$ to solve $Ax = b$ for \[ b = \begin{bmatrix} 2 \\ 3 \\ 5 \end{bmatrix} \qquad\text{and for}\qquad b = \begin{bmatrix} 3 \\ 6 \\ 10 \end{bmatrix}. \]

   Solution

   Since $A$ is invertible, $Ax = b$ has the unique solution $x = A^{-1} b$. For the first vector,

   and for the second,

   As a check, the second answer says that the sum of the columns of $A$ is $(3, 6, 10)$, which is true.

3. Explain why the matrix \[ B = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 5 & 7 \\ 3 & 7 & 10 \end{bmatrix} \] is not invertible.

   Solution

   We row reduce $[\,B \mid I\,]$.

   \[ \begin{aligned} &\left[\begin{array}{ccc|ccc} 1 & 2 & 3 & 1 & 0 & 0 \\ 2 & 5 & 7 & 0 & 1 & 0 \\ 3 & 7 & 10 & 0 & 0 & 1 \end{array}\right] \xrightarrow{R_{2} \to R_{2} - 2\,R_{1}} \left[\begin{array}{ccc|ccc} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 1 & \llap{$-$}2 & 1 & 0 \\ 3 & 7 & 10 & 0 & 0 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - 3\,R_{1}} \left[\begin{array}{ccc|ccc} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 1 & \llap{$-$}2 & 1 & 0 \\ 0 & 1 & 1 & \llap{$-$}3 & 0 & 1 \end{array}\right] \\[4pt] &\xrightarrow{R_{3} \to R_{3} - R_{2}} \left[\begin{array}{ccc|ccc} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 1 & \llap{$-$}2 & 1 & 0 \\ 0 & 0 & 0 & \llap{$-$}1 & \llap{$-$}1 & 1 \end{array}\right] \end{aligned} \]

   The left half has only two pivots, so no further row operations can turn it into the identity matrix, and the algorithm for computing $B^{-1}$ fails. Put another way, $\rank(B) = 2 < 3$, so $T_B$ is not surjective. Since $B$ is invertible exactly when $T_B$ is bijective, $B$ is not invertible.

The face on the left sits on the parallelogram with corners at the origin, $u_1 = (2, 1)$, $u_2 = (1, 2)$, and $u_1 + u_2 = (3, 3)$. We want to find the matrix $A$ such that $T_A$ maps the face on the left to the face on the right. Let $w_1 = T_A(u_1)$ and $w_2 = T_A(u_2)$.

1. Define $U = \begin{bmatrix} u_1 & u_2 \end{bmatrix}$ and $W = \begin{bmatrix} w_1 & w_2 \end{bmatrix}$ be the $2 \times 2$ matrices with these vectors as columns. Explain why $AU = W$.

   Solution

   The columns of a product $AU$ are $A$ times the columns of $U$, so \[ AU = \begin{bmatrix} Au_1 & Au_2 \end{bmatrix} = \begin{bmatrix} T_A(u_1) & T_A(u_2) \end{bmatrix} = \begin{bmatrix} w_1 & w_2 \end{bmatrix} = W. \]

2. Use the equation $AU = W$ to calculate $A$.
   Hint: the $2\times 2$ inverse formula.

   Solution

   Multiplying both sides of $AU = W$ on the right by $U^{-1}$ gives $A = AUU^{-1} = WU^{-1}$. So

   As a check, $A(2, 1) = (1, 1)$ and $A(1, 2) = (-1, 2)$, and the top corner goes to $A(3, 3) = (0, 3)$, as in the picture.