Surjectivity Means Reaching Every Right-Hand Side
For a matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\), multiplication defines a linear transformation \(T:\mathbb{R}^n\to\mathbb{R}^m\) by \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\). To ask whether this transformation is onto is to ask whether every possible output in \(\mathbb{R}^m\) is reached by at least one input. Thus the question is not whether one particular system has a solution, but whether \(\mathbf{A}\mathbf{x}=\mathbf{b}\) is consistent for every right-hand side \(\mathbf{b}\in\mathbb{R}^m\).
Row reduction is useful because it gives an equivalent system with a simpler coefficient matrix. A pivot in every row will turn out to be the precise condition that guarantees consistency for all right-hand sides. A missing pivot row, on the other hand, becomes a zero row, which can impose a condition on the transformed right-hand side.
Why Row Operations Preserve Consistency
When row-reducing \(\mathbf{A}\mathbf{x}=\mathbf{b}\), each operation must be applied to both the coefficient matrix and the right-hand side. Swapping two equations, multiplying an equation by a nonzero scalar, or adding a multiple of one equation to another does not change which \(\mathbf{x}\) satisfy the system: each operation can be reversed. The next result records the fact needed in the proof.
Proof. A row swap simply changes the order of two equations, so it does not change which vectors satisfy all the equations. Multiplying one equation by a nonzero scalar preserves its solutions because the operation can be undone by multiplying by the reciprocal. Replacing one equation by itself plus a multiple of another also preserves the solutions: the new equation follows from the original pair, and subtracting that same multiple recovers the original equation. Each elementary row operation is therefore reversible and leaves the solution set unchanged. \(\square\)
The right-hand side matters during this process. If a row of the reduced coefficient matrix is zero, the corresponding transformed equation is either \(0=c\), which is inconsistent when \(c\ne0\), or \(0=0\), which imposes no condition. It is not enough to observe that a zero row exists; to disprove surjectivity, we must show that some original right-hand side produces a nonzero \(c\) in that row.
The Pivot-Row Criterion
Proof. Let \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\), obtained by a finite sequence of elementary row operations. Apply the same sequence to \(\mathbf{b}\), producing a transformed right-hand side \(\mathbf{d}\). By the lemma, \(\mathbf{A}\mathbf{x}=\mathbf{b}\) and \(\mathbf{R}\mathbf{x}=\mathbf{d}\) have the same solutions for each fixed \(\mathbf{b}\). Each operation on the right-hand side is reversible, so as \(\mathbf{b}\) ranges over \(\mathbb{R}^m\), \(\mathbf{d}\) also ranges over all of \(\mathbb{R}^m\).
First suppose \(\mathbf{R}\) has a pivot in every row. For an arbitrary \(\mathbf{b}\), take its transformed right-hand side \(\mathbf{d}\). Each row of \(\mathbf{R}\mathbf{x}=\mathbf{d}\) has a pivot variable. Set every free variable to \(0\); then assign each pivot variable the value in the corresponding entry of \(\mathbf{d}\). This satisfies every row, because in reduced row echelon form each pivot is the only nonzero entry in its column. Thus \(\mathbf{R}\mathbf{x}=\mathbf{d}\), and hence \(\mathbf{A}\mathbf{x}=\mathbf{b}\), is consistent. Since \(\mathbf{b}\) was arbitrary, \(T\) is onto.
Conversely, suppose \(\mathbf{R}\) does not have a pivot in every row. A nonzero row in reduced row echelon form has a pivot, so at least one row, say row \(i\), is entirely zero. Choose the transformed right-hand side \(\mathbf{d}\) to have entry \(1\) in row \(i\) and \(0\) in every other row. Reversibility of the row operations on the right-hand side guarantees that some original \(\mathbf{b}\in\mathbb{R}^m\) produces this \(\mathbf{d}\). Then row \(i\) of \(\mathbf{R}\mathbf{x}=\mathbf{d}\) says \(0=1\), so the system is inconsistent. Therefore \(T\) is not onto. The two implications prove the criterion. \(\square\)
The statement is about rows of the reduced coefficient matrix. A pivot in every row ensures that every output coordinate can be matched for every prescribed right-hand side. It does not require a pivot in every column: a column without a pivot corresponds to a free variable, which does not prevent the system from having a solution.
Worked Examples
Worked Example: A Transformation That Is Onto
Let \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\). Determine whether \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\) is onto \(\mathbb{R}^2\), and find an input for an arbitrary right-hand side \(\mathbf{b}=\begin{bmatrix}b_1\\b_2\end{bmatrix}\).
Clear the entry above the pivot in column 2 by applying \(R_1\to R_1-2R_2\):
There is a pivot in both rows, so the criterion says \(T\) is onto. To see a solution for every \(\mathbf{b}\), row-reduce the augmented system, applying the same row operation to its right-hand side:
Set the free variable \(x_3=t\). The rows give \(x_1=b_1-2b_2+2t\) and \(x_2=b_2-t\). In particular, taking \(t=0\) gives \(\mathbf{x}=\begin{bmatrix}b_1-2b_2\\b_2\\0\end{bmatrix}\).
Check: Multiplying back gives \(\mathbf{A}\mathbf{x}=\begin{bmatrix}b_1-2b_2+2b_2\\b_2+0\end{bmatrix}=\begin{bmatrix}b_1\\b_2\end{bmatrix}=\mathbf{b}\). This works for every real \(b_1,b_2\), as required for surjectivity.
Worked Example: A Zero Row That Prevents Surjectivity
Let \(\mathbf{A}=\begin{bmatrix}1&2\\2&4\\1&1\end{bmatrix}\). Find a right-hand side for which \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has no solution.
Row-reduce the coefficient matrix, using \(R_2\to R_2-2R_1\), \(R_3\to R_3-R_1\), then swapping rows 2 and 3, scaling row 2 by \(-1\), and applying \(R_1\to R_1-2R_2\):
The last row has no pivot. Track the same operations on the augmented system with \(\mathbf{b}=\begin{bmatrix}0\\1\\0\end{bmatrix}\):
The last row says \(0=1\), so the system is inconsistent and the transformation is not onto. The contradiction can also be checked in the original equations: the first equation would be \(x_1+2x_2=0\), while the second would be \(2x_1+4x_2=1\). Twice the first left-hand side is the second left-hand side, but twice the first right-hand side is \(0\), not \(1\).
Worked Example: A Parameter Changes the Pivot Rows
For the real parameter \(t\), let \(\mathbf{A}(t)=\begin{bmatrix}1&1&0\\2&2&t\end{bmatrix}\). Determine for which values of \(t\) the associated transformation from \(\mathbb{R}^3\) to \(\mathbb{R}^2\) is onto.
Apply \(R_2\to R_2-2R_1\):
If \(t\ne0\), scaling row 2 by \(1/t\) gives a pivot in the second row, as well as the pivot in the first row. Thus the transformation is onto. For an arbitrary \(\mathbf{b}=\begin{bmatrix}b_1\\b_2\end{bmatrix}\), choose \(\mathbf{x}=\begin{bmatrix}b_1\\0\\(b_2-2b_1)/t\end{bmatrix}\).
Check: \(\mathbf{A}(t)\mathbf{x}=\begin{bmatrix}b_1\\2b_1+t(b_2-2b_1)/t\end{bmatrix}=\begin{bmatrix}b_1\\b_2\end{bmatrix}\). If \(t=0\), the second row of the reduced coefficient matrix is zero. In particular, for \(\mathbf{b}=\begin{bmatrix}0\\1\end{bmatrix}\), the original equations require \(x_1+x_2=0\) and \(2x_1+2x_2=1\), which are incompatible. Therefore the transformation is onto exactly when \(t\ne0\).
Common Pitfall: Looking for a Pivot in Every Column
A common error is to require a pivot in every column when testing whether a transformation is onto. That is a different condition from the pivot-row criterion. For example, the first worked matrix has three columns but only two pivot columns; it is still onto \(\mathbb{R}^2\), because both rows have pivots and every right-hand side has a solution.
For that matrix, setting \(b_1=1\) and \(b_2=0\) gives the input \(\mathbf{x}=\begin{bmatrix}1\\0\\0\end{bmatrix}\), and multiplication gives \(\mathbf{A}\mathbf{x}=\begin{bmatrix}1\\0\end{bmatrix}\). More generally, the calculation in that example shows a preimage for every \(\begin{bmatrix}b_1\\b_2\end{bmatrix}\). Requiring a pivot in every column would wrongly reject this onto transformation. The correct procedure is to row-reduce the coefficient matrix and check whether every row has a pivot.
A second error is to conclude that a zero row alone proves a transformation is not onto without identifying an inconsistent right-hand side. The proof of the criterion supplies the missing reasoning: row operations can transform some right-hand side into one with a \(1\) in that zero row, producing \(0=1\). In practice, tracking a chosen \(\mathbf{b}\) through the row operations, as in the second worked example, makes the obstruction explicit.
Check Your Understanding
Use row reduction and the consistency criterion to answer each question.
- Does the matrix \(\begin{bmatrix}1&0&2\\0&1&-1\end{bmatrix}\) define an onto transformation from \(\mathbb{R}^3\) to \(\mathbb{R}^2\)? State the pivot rows and justify your conclusion.
- For the matrix \(\begin{bmatrix}1&2\\2&4\\0&1\end{bmatrix}\), find a right-hand side that makes the system inconsistent, or explain why every right-hand side is consistent.
- For which real values of \(s\) is the transformation associated with \(\begin{bmatrix}1&0\\0&s\\1&1\end{bmatrix}\) onto \(\mathbb{R}^3\)?
- Explain why a pivot in every column is not required for a transformation \(\mathbb{R}^n\to\mathbb{R}^m\) to be onto.
- In the pivot-row criterion proof, why can a chosen transformed right-hand side be obtained from some original right-hand side?
