Onto Means Every Output Can Be Reached
For a transformation \(T:\mathbb{R}^n\to\mathbb{R}^m\), being onto means that every vector in the output space is the image of at least one input. In symbols, for each \(\mathbf{b}\in\mathbb{R}^m\), there must be some \(\mathbf{x}\in\mathbb{R}^n\) such that \(T(\mathbf{x})=\mathbf{b}\). When \(T\) is given by a matrix, this question can be translated into a statement about its columns.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). For an input \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\), matrix multiplication gives \(T(\mathbf{x})=\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\). Thus every possible output is a linear combination of the columns. The question is whether these combinations include every vector in \(\mathbb{R}^m\).
Proof. Suppose \(T\) is onto. Take any \(\mathbf{b}\in\mathbb{R}^m\). By the definition of onto, there is an \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\in\mathbb{R}^n\) such that \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Expanding the matrix product gives \(\mathbf{b}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\), so \(\mathbf{b}\in\operatorname{Col}\mathbf{A}\). This holds for every \(\mathbf{b}\), and therefore \(\operatorname{Col}\mathbf{A}=\mathbb{R}^m\). Conversely, suppose \(\operatorname{Col}\mathbf{A}=\mathbb{R}^m\). For any \(\mathbf{b}\in\mathbb{R}^m\), this equality means that \(\mathbf{b}\) is a linear combination of the columns: \(\mathbf{b}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\) for some scalars \(x_1,\dots,x_n\). Set \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). Then \(\mathbf{A}\mathbf{x}=\mathbf{b}\), so every \(\mathbf{b}\) has an input mapping to it. Hence \(T\) is onto. \(\square\)
Testing the Column-Span Condition
The theorem turns surjectivity into a spanning question. A useful finite test comes from the standard basis \(\mathbf{e}_1,\dots,\mathbf{e}_m\) of \(\mathbb{R}^m\). Each vector \(\mathbf{b}\in\mathbb{R}^m\) has the form \(b_1\mathbf{e}_1+\cdots+b_m\mathbf{e}_m\). Consequently, if every standard basis vector can be written as a combination of the columns of \(\mathbf{A}\), then every \(\mathbf{b}\) can be written as one too.
Proof. If \(T\) is onto, every \(\mathbf{e}_i\in\mathbb{R}^m\) has a preimage, so each system \(\mathbf{A}\mathbf{x}=\mathbf{e}_i\) has a solution. Conversely, suppose every one of these systems has a solution. For any \(\mathbf{b}=(b_1,\dots,b_m)^{\top}\), choose \(\mathbf{x}_i\) satisfying \(\mathbf{A}\mathbf{x}_i=\mathbf{e}_i\). Define \(\mathbf{x}=b_1\mathbf{x}_1+\cdots+b_m\mathbf{x}_m\). Matrix multiplication distributes over addition and scalar multiplication, so \(\mathbf{A}\mathbf{x}=b_1\mathbf{A}\mathbf{x}_1+\cdots+b_m\mathbf{A}\mathbf{x}_m=b_1\mathbf{e}_1+\cdots+b_m\mathbf{e}_m=\mathbf{b}\). Thus every output has a preimage, and \(T\) is onto. \(\square\)
Why does row reduction help? A row operation on an augmented system replaces its equations with an equivalent system: it does not change which inputs solve the system. Therefore, a row-reduced augmented matrix can show whether a target \(\mathbf{b}\) is attainable. The coefficient block alone is not the full system: the right-hand side must undergo the same row operations as the coefficient block.
Worked Example: An Onto Map from R³ to R²
Let \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\). Test whether \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\) is onto \(\mathbb{R}^2\) by checking both standard basis targets at once.
Append \(\mathbf{I}_2\) and use \(R_1\to R_1-2R_2\):
The first right-hand side column is the transformed version of \(\mathbf{e}_1\), and the second is the transformed version of \(\mathbf{e}_2\). To read solutions, set the free variable \(x_3=0\). For \(\mathbf{e}_1\), the reduced equations give \(x_1=1\), \(x_2=0\), so one input is \((1,0,0)^{\top}\). For \(\mathbf{e}_2\), they give \(x_1=-2\), \(x_2=1\), so one input is \((-2,1,0)^{\top}\). Both basis targets are attainable, and the test shows that \(T\) is onto.
Check: \(\mathbf{A}(1,0,0)^{\top}=(1,0)^{\top}=\mathbf{e}_1\), while \(\mathbf{A}(-2,1,0)^{\top}=(-2+2,1)^{\top}=(0,1)^{\top}=\mathbf{e}_2\). Since every vector \((b_1,b_2)^{\top}\) equals \(b_1\mathbf{e}_1+b_2\mathbf{e}_2\), a corresponding input is \(b_1(1,0,0)^{\top}+b_2(-2,1,0)^{\top}=(b_1-2b_2,b_2,0)^{\top}\).
Worked Example: A Map That Is Not Onto R³
Consider the map from \(\mathbb{R}^2\) to \(\mathbb{R}^3\) with matrix \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\). It is enough to find one output that cannot be reached. Test the standard basis vector \(\mathbf{e}_3\) by row-reducing \(\begin{bmatrix}\mathbf{A}&\mathbf{e}_3\end{bmatrix}\).
First subtract \(R_1\) from \(R_3\), then subtract \(R_2\) from the new \(R_3\):
The last row represents \(0x_1+0x_2=1\), which is impossible. Thus \(\mathbf{A}\mathbf{x}=\mathbf{e}_3\) has no solution, so \(\mathbf{e}_3\notin\operatorname{Col}\mathbf{A}\). The columns do not span \(\mathbb{R}^3\), and the transformation is not onto.
Check: For any \((x_1,x_2)^{\top}\), the output is \((x_1,x_2,x_1+x_2)^{\top}\). Its third coordinate must equal the sum of its first two, but \(\mathbf{e}_3=(0,0,1)^{\top}\) does not satisfy that condition.
Solving for a General Output
When a map is onto, it is often useful to describe how an input can be built from a given output. The columns provide the direct interpretation: if \(\mathbf{b}=c_1\mathbf{a}_1+\cdots+c_n\mathbf{a}_n\), then \(\mathbf{x}=(c_1,\dots,c_n)^{\top}\) satisfies \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Row reduction can find such coefficients for a target. If there are free variables, setting them to convenient values gives one solution; the onto question asks whether a solution exists, not whether it is unique.
Worked Example: Constructing an Input for Any Output
Let \(\mathbf{A}=\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}\). Given an arbitrary output \(\mathbf{b}=(r,s)^{\top}\in\mathbb{R}^2\), find an input that maps to it. The system is \(x_1+x_2=r\) and \(x_2+x_3=s\). Choose \(x_2=0\). Then \(x_1=r\) and \(x_3=s\), so take \(\mathbf{x}=(r,0,s)^{\top}\).
Check: \(\mathbf{A}\begin{bmatrix}r\\0\\s\end{bmatrix} =\begin{bmatrix}r+0\\0+s\end{bmatrix} =\begin{bmatrix}r\\s\end{bmatrix} =\mathbf{b}\). This works for every pair \(r,s\in\mathbb{R}\), so every output is attainable and the map is onto. The same fact is visible from the columns: \(\mathbf{e}_1\) and \(\mathbf{e}_2\) are the first two columns, so the columns span \(\mathbb{R}^2\).
Common Pitfall: Row Operations Do Not Preserve Column Space
A row operation changes the columns as vectors, so it generally changes the column space. For instance, the matrix \(\mathbf{A}=\begin{bmatrix}1\\1\end{bmatrix}\) has column space \(\operatorname{span}\{(1,1)^{\top}\}\), which does not contain \((1,0)^{\top}\). If we subtract \(R_1\) from \(R_2\), we obtain \(\begin{bmatrix}1\\0\end{bmatrix}\), whose column space does contain \((1,0)^{\top}\). It would therefore be wrong to claim that row reduction preserves the original column space.
The correction is to use row operations on the augmented system, applying each operation to both the coefficient block and the right-hand side. For a fixed target \(\mathbf{b}\), this preserves whether \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has a solution. To test whether the map is onto, check all standard basis targets, or show directly that an arbitrary output has a preimage. A single successful target does not establish that every output is attainable.
Keep the distinctions straight: \(\operatorname{Col}\mathbf{A}\) is a subspace of the codomain \(\mathbb{R}^m\); the input \(\mathbf{x}\) lies in \(\mathbb{R}^n\); and the equation \(\mathbf{A}\mathbf{x}=\mathbf{b}\) asks whether a particular output \(\mathbf{b}\) can be reached. The column space test answers the universal version of that question: the map is onto exactly when every vector in the codomain lies in the column space.
Check Your Understanding
For each question, connect the matrix equation to the output space and verify any proposed input by multiplication.
- State the column space test for whether \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\), with \(\mathbf{A}\in\mathbb{R}^{m\times n}\), is onto \(\mathbb{R}^m\).
- Why is it enough to check whether each standard basis vector of \(\mathbb{R}^m\) is in \(\operatorname{Col}\mathbf{A}\)?
- For \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&-1\end{bmatrix}\), test whether \(\mathbf{e}_3\) is in \(\operatorname{Col}\mathbf{A}\) by solving the corresponding system.
- For \(\mathbf{A}=\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}\), give an input that maps to an arbitrary output \((r,s)^{\top}\).
- Explain why row-reducing \(\mathbf{A}\) alone does not preserve its original column space, and state how the right-hand side must be handled when testing a target.
