A Pivot-Based Classification Workflow
For a matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\), the rule \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\) defines a linear map \(T:\mathbb{R}^n\to\mathbb{R}^m\). The number of columns \(n\) is the dimension of the input space; the number of rows \(m\) is the dimension of the output space. To classify this map, row-reduce \(\mathbf{A}\) and inspect two different features: whether every column has a pivot, and whether every row has one. These are separate tests. A map can pass either test, both, or neither.
Throughout, a pivot position means the leading \(1\) in a nonzero row of the reduced row echelon form (RREF). A pivot row is a row containing such a position, and a pivot column is a column containing one. The column numbers identify pivot columns in the original matrix as well; row operations do not change which column indices are pivot columns. The number of pivot rows is the number of nonzero rows in RREF.
Here, injective means that distinct inputs cannot have the same output: \(T(\mathbf{x}_1)=T(\mathbf{x}_2)\) implies \(\mathbf{x}_1=\mathbf{x}_2\). Onto means that every vector in the codomain is an output: for every \(\mathbf{y}\in\mathbb{R}^m\), there is some \(\mathbf{x}\in\mathbb{R}^n\) with \(T(\mathbf{x})=\mathbf{y}\). The matrix’s shape helps interpret the test, but does not by itself settle every case: a map from a larger space to a smaller one cannot have a pivot in every column, while one from a smaller space to a larger one cannot have a pivot in every row.
Why the Two Pivot Tests Work
The classification rule follows from what row reduction does to systems. Elementary row operations preserve the solutions of a homogeneous system \(\mathbf{A}\mathbf{x}=\mathbf{0}\). They also preserve whether the system with an arbitrary right-hand side can be solved for every possible output. More precisely, each row operation is reversible; applying a sequence of them changes \(\mathbf{A}\) to a row-equivalent matrix \(\mathbf{R}\) and changes a right-hand side \(\mathbf{y}\) to the corresponding transformed right-hand side. The proof below makes the consequences for injectivity and onto-ness explicit.
Proof. First consider injectivity. If \(T(\mathbf{x}_1)=T(\mathbf{x}_2)\), then \(\mathbf{A}(\mathbf{x}_1-\mathbf{x}_2)=\mathbf{0}\). Thus \(T\) is injective exactly when the only solution of \(\mathbf{A}\mathbf{x}=\mathbf{0}\) is \(\mathbf{x}=\mathbf{0}\). Row operations preserve the solution set of this homogeneous system, so it is enough to examine \(\mathbf{R}\mathbf{x}=\mathbf{0}\). If every column has a pivot, there are no free variables; every variable is a pivot variable, and the homogeneous equations force each one to be zero. If some column has no pivot, its variable is free. Set that free variable to \(1\), set any other free variables to \(0\), and solve for the pivot variables. This gives a nonzero solution. So injectivity holds exactly when every column has a pivot.
Now consider whether \(T\) is onto. Row reduction is a sequence of reversible row operations, so there is an invertible matrix \(\mathbf{E}\) such that \(\mathbf{R}=\mathbf{E}\mathbf{A}\). If \(\mathbf{A}\mathbf{x}=\mathbf{y}\), then \(\mathbf{R}\mathbf{x}=\mathbf{E}\mathbf{y}\). As \(\mathbf{y}\) ranges over \(\mathbb{R}^m\), so does \(\mathbf{E}\mathbf{y}\), because \(\mathbf{E}\) is invertible. Therefore \(\mathbf{A}\mathbf{x}=\mathbf{y}\) is solvable for every \(\mathbf{y}\) exactly when \(\mathbf{R}\mathbf{x}=\mathbf{z}\) is solvable for every \(\mathbf{z}\in\mathbb{R}^m\). If every row of \(\mathbf{R}\) has a pivot, then every equation has a pivot variable. For any right-hand side, set the free variables to zero and solve for the pivot variables. Conversely, if a row has no pivot, it is a zero row in RREF. Choose a right-hand side with a nonzero entry in that row; the corresponding equation reads \(0=c\), where \(c\ne0\), and is inconsistent. Hence the map is onto exactly when every row has a pivot. \(\square\)
This theorem gives a compact workflow: record the matrix’s shape, row-reduce, list the pivot row and column numbers, and apply the two tests separately. If both tests pass, the number of pivot positions must equal both \(m\) and \(n\), so \(m=n\). In particular, the rectangular examples below show why injectivity and onto-ness must not be treated as interchangeable.
Four Worked Classifications
Worked Example: Onto but Not Injective
Let \(\mathbf{A}\in\mathbb{R}^{2\times3}\) and \(T:\mathbb{R}^3\to\mathbb{R}^2\) be given by \(\mathbf{A}=\begin{bmatrix}1&2&0\\2&4&1\end{bmatrix}\). Find the pivots and classify \(T\).
Apply \(R_2\to R_2-2R_1\):
This is RREF, with pivot positions in row 1, column 1 and row 2, column 3. Thus the pivot rows are 1 and 2, and the pivot columns are 1 and 3. Every row has a pivot, so \(T\) is onto. Column 2 has no pivot, so \(T\) is not injective.
Checks: For an arbitrary output \(\mathbf{y}=(y_1,y_2)^\top\), the original equations are \(x_1+2x_2=y_1\) and \(2x_1+4x_2+x_3=y_2\). Set the free variable \(x_2=0\); then \(x_1=y_1\) and \(x_3=y_2-2y_1\). Substitution gives the output \((y_1,y_2)^\top\), confirming onto-ness. For injectivity, \(\mathbf{x}=(-2,1,0)^\top\ne\mathbf{0}\) satisfies \(\mathbf{A}\mathbf{x}=(0,0)^\top\), so distinct inputs \(\mathbf{x}\) and \(\mathbf{0}\) have the same output.
Worked Example: Injective but Not Onto
Consider \(T:\mathbb{R}^2\to\mathbb{R}^3\) with matrix \(\mathbf{A}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}\). Reduce and classify the map.
First apply \(R_3\to R_3-R_1\), then \(R_3\to R_3-R_2\):
The pivots are in rows 1 and 2 and columns 1 and 2. Every column has a pivot, so \(T\) is injective. Row 3 has no pivot, so \(T\) is not onto.
Check: Direct multiplication gives \(T(x_1,x_2)=(x_1,x_2,x_1+x_2)^\top\). The output \((0,0,1)^\top\) is impossible: its first two coordinates would require \(x_1=x_2=0\), which forces the third coordinate to be \(0\), not \(1\). Meanwhile, if \(T(x_1,x_2)=\mathbf{0}\), the first two coordinates give \(x_1=x_2=0\); the kernel is trivial, as the pivot test predicts.
Worked Example: Neither Injective nor Onto
Let \(T:\mathbb{R}^3\to\mathbb{R}^3\) have matrix \(\mathbf{A}=\begin{bmatrix}1&2&0\\2&4&0\\0&1&1\end{bmatrix}\). Locate the pivots and decide whether either property holds.
Apply \(R_2\to R_2-2R_1\), then interchange rows 2 and 3, then apply \(R_1\to R_1-2R_2\):
The pivot rows are 1 and 2, and the pivot columns are 1 and 2. Column 3 has no pivot, so \(T\) is not injective; row 3 has no pivot, so \(T\) is not onto.
Checks: The vector \(\mathbf{x}=(2,-1,1)^\top\) is nonzero and \(\mathbf{A}\mathbf{x}=(2-2,4-4,-1+1)^\top=\mathbf{0}\), confirming failure of injectivity. Also, for every input, the second output coordinate is twice the first, since \(2x_1+4x_2=2(x_1+2x_2)\). Thus the output \((0,1,0)^\top\), whose second coordinate is not twice its first, cannot occur. This confirms failure of onto-ness.
Worked Example: Both Injective and Onto
For \(T:\mathbb{R}^2\to\mathbb{R}^2\) with matrix \(\mathbf{A}=\begin{bmatrix}1&2\\3&5\end{bmatrix}\), find the pivots and classify \(T\).
Apply \(R_2\to R_2-3R_1\), \(R_2\to -R_2\), and \(R_1\to R_1-2R_2\), in that order:
Both rows and both columns have pivots. Therefore \(T\) is injective and onto.
Check: For output \((y_1,y_2)^\top\), the equations \(x_1+2x_2=y_1\) and \(3x_1+5x_2=y_2\) give \(x_2=3y_1-y_2\) and \(x_1=-5y_1+2y_2\). Substitution into the first equation gives \((-5y_1+2y_2)+2(3y_1-y_2)=y_1\); into the second it gives \(3(-5y_1+2y_2)+5(3y_1-y_2)=y_2\). This confirms that every output is reached. The only input giving output \(\mathbf{0}\) is \(\mathbf{0}\), also consistent with the pivots.
A Common Pivot Misreading
A common mistake is to conclude that a pivot in every row means a pivot in every column, and therefore the map is injective. Those are different claims. In the first example, the matrix has two pivot rows but only two pivot columns out of three. The map is onto but not injective.
For that matrix, a mistaken argument might say: “There are pivots in both rows, so there are no free variables.” The correction is that variables correspond to columns, not rows: column 2 is free. For onto-ness, the correct conclusion from a pivot in every row is that every equation has a pivot variable. Set the free variables to zero and solve for the pivot variables. For injectivity, check instead whether every column has a pivot.
Keep the two tests separate when recording a classification. A pivot in every column answers the injectivity question; a pivot in every row answers the onto question. The four examples show all possible outcomes, with the square matrix in the final example passing both tests.
Check Your Understanding
For each matrix, row-reduce and record pivot row and column numbers before classifying its map.
- Let \(\mathbf{A}=\begin{bmatrix}1&0\\2&0\\0&1\end{bmatrix}\). Is the map \(\mathbb{R}^2\to\mathbb{R}^3\) injective, onto, both, or neither?
- Let \(\mathbf{B}=\begin{bmatrix}1&2&1\\0&1&3\end{bmatrix}\). Is the map \(\mathbb{R}^3\to\mathbb{R}^2\) injective, onto, both, or neither?
- Give a nonzero vector in the null space of the matrix in question 2, or explain why none exists.
- For a matrix in \(\mathbb{R}^{m\times n}\), state the pivot condition for injectivity and the pivot condition for onto-ness.
- Explain why a zero row in RREF prevents the associated map from being onto.
