From Injectivity to a Matrix Test
A linear transformation can send different inputs to the same output, or it can distinguish every input. For a transformation represented by a matrix, the latter property can be tested by row reduction. The key is to follow the input variables: a column without a pivot leaves one variable free, and that freedom produces a nonzero input that the matrix sends to zero.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and define \(T:\mathbb{R}^n\to\mathbb{R}^m\) by \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\). The \(n\) columns of \(\mathbf{A}\) are the vectors \(\mathbf{a}_1,\dots,\mathbf{a}_n\). The transformation is one-to-one, or injective, if \(T(\mathbf{x})=T(\mathbf{y})\) implies \(\mathbf{x}=\mathbf{y}\). The null space \(\operatorname{Nul}\mathbf{A}\) is the set of inputs \(\mathbf{x}\in\mathbb{R}^n\) satisfying \(\mathbf{A}\mathbf{x}=\mathbf{0}\).
This criterion concerns column positions in the RREF, not whether the original columns themselves remain unchanged during row reduction. Row operations change the entries of the matrix, but they preserve the solutions of its homogeneous system. We will use that fact to connect the pivot positions to injectivity.
Why the Null Space Is the Right Link
Proof. Suppose first that \(T\) is one-to-one and \(\mathbf{x}\in\operatorname{Nul}\mathbf{A}\). Then \(T(\mathbf{x})=\mathbf{A}\mathbf{x}=\mathbf{0}=T(\mathbf{0})\), so injectivity gives \(\mathbf{x}=\mathbf{0}\). Therefore the null space contains only \(\mathbf{0}\). Conversely, suppose \(\operatorname{Nul}\mathbf{A}=\{\mathbf{0}\}\), and suppose \(T(\mathbf{x})=T(\mathbf{y})\). Then \(\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{y}\), so \(\mathbf{A}(\mathbf{x}-\mathbf{y})=\mathbf{0}\). Thus \(\mathbf{x}-\mathbf{y}\) belongs to the null space and must be \(\mathbf{0}\). Hence \(\mathbf{x}=\mathbf{y}\), and \(T\) is one-to-one. \(\square\)
To use this test, we can replace \(\mathbf{A}\) with its RREF. Each elementary row operation is reversible: a row swap reverses itself, scaling a row by a nonzero scalar can be undone by scaling by its reciprocal, and adding a multiple of one row to another can be undone by subtracting that multiple. Therefore these operations preserve the solutions of \(\mathbf{A}\mathbf{x}=\mathbf{0}\).
Proof. The RREF is obtained from \(\mathbf{A}\) by a sequence of elementary row operations. For each operation, applying it to the left-hand side of a system changes its equations without changing their solution set, because the operation has an inverse of the same kind. After the entire sequence, the solution set is therefore unchanged. In particular, the homogeneous systems for \(\mathbf{A}\) and \(\mathbf{R}\) have exactly the same solutions. \(\square\)
In the RREF system, a variable in a pivot column is a pivot variable; a variable in a column without a pivot is a free variable. A pivot row expresses its pivot variable in terms of the free variables. If there are no free variables, each pivot variable must be zero in a homogeneous system. If there is a free variable, it can be chosen nonzero, and the pivot variables can then be set to satisfy the pivot-row equations.
The Pivot-Column Criterion
Proof. By the null space test, \(T\) is one-to-one if and only if \(\mathbf{A}\mathbf{x}=\mathbf{0}\) has only the solution \(\mathbf{x}=\mathbf{0}\). By the lemma, this is equivalent to \(\mathbf{R}\mathbf{x}=\mathbf{0}\) having only that solution, where \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). If every column is a pivot column, there are no free variables. In each nonzero row of \(\mathbf{R}\), the pivot variable equals zero because every other variable in that row is a pivot variable and the homogeneous equations force the pivot variables to be zero. Equivalently, solving the pivot equations from the last pivot row upwards gives every variable equal to zero. Thus the only solution is \(\mathbf{x}=\mathbf{0}\).
For the reverse direction, suppose some column has no pivot. Its variable is free. Set that free variable to \(1\), set any other free variables to \(0\), and use the pivot-row equations to determine the pivot variables. This gives a solution of \(\mathbf{R}\mathbf{x}=\mathbf{0}\) whose chosen free variable is \(1\), so it is nonzero. The same vector solves \(\mathbf{A}\mathbf{x}=\mathbf{0}\) by the lemma. The null space is not just \(\{\mathbf{0}\}\), so the null space test shows that \(T\) is not one-to-one. This proves both directions. \(\square\)
The theorem works for rectangular matrices as well as square ones. The number of columns is the number of input variables, so it is the columns—not the rows—that must all have pivots. A matrix with \(n\) columns can have at most \(m\) pivot columns, since it has \(m\) rows. Consequently, if \(n>m\), the criterion cannot be met. When \(n\le m\), this observation alone does not settle injectivity; row reduction still decides whether every column has a pivot.
Using the Criterion
Worked Example: An Injective Transformation with More Rows Than Columns
Let \(\mathbf{A}=\begin{bmatrix}1&2\\2&4\\1&1\end{bmatrix}\), and let \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\). Decide whether \(T:\mathbb{R}^2\to\mathbb{R}^3\) is one-to-one.
Reduce \(\mathbf{A}\). First use \(R_2\to R_2-2R_1\) and \(R_3\to R_3-R_1\); then swap rows 2 and 3, scale row 2 by \(-1\), and clear above its pivot:
Both columns have pivots, so the criterion says that \(T\) is one-to-one. The RREF system also shows this directly: \(x_1=0\) and \(x_2=0\) are the only values satisfying \(\mathbf{A}\mathbf{x}=\mathbf{0}\).
Check: the only possible null-space vector is \(\mathbf{x}=\begin{bmatrix}0\\0\end{bmatrix}\), and \(\mathbf{A}\begin{bmatrix}0\\0\end{bmatrix}=\begin{bmatrix}0\\0\\0\end{bmatrix}\). Thus the homogeneous equation has exactly the zero solution, as required.
Worked Example: A Free Variable Gives a Nonzero Input
Let \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\). Decide whether \(T:\mathbb{R}^3\to\mathbb{R}^2\), \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\), is one-to-one. If it is not, find a nonzero input sent to \(\mathbf{0}\).
Subtract twice row 2 from row 1:
There are pivots in columns 1 and 2, but not in column 3. Hence \(x_3\) is free, so \(T\) is not one-to-one. The reduced equations are \(x_1-2x_3=0\) and \(x_2+x_3=0\). Set \(x_3=1\); then \(x_1=2\) and \(x_2=-1\), giving \(\mathbf{x}=\begin{bmatrix}2\\-1\\1\end{bmatrix}\).
Check:
This nonzero input and the zero input have the same output, confirming that \(T\) is not one-to-one.
Worked Example: A Zero Column Is a Free-Variable Warning
Consider \(\mathbf{A}=\begin{bmatrix}0&1&2\\0&2&4\\0&1&1\end{bmatrix}\), defining \(T:\mathbb{R}^3\to\mathbb{R}^3\). Determine whether \(T\) is one-to-one.
Use \(R_2\to R_2-2R_1\) and \(R_3\to R_3-R_1\), swap rows 2 and 3, scale row 2 by \(-1\), and apply \(R_1\to R_1-2R_2\):
Columns 2 and 3 have pivots, while column 1 does not. Thus \(x_1\) is free and \(T\) is not one-to-one. The RREF equations give \(x_2=0\) and \(x_3=0\); choosing \(x_1=1\) gives \(\mathbf{x}=\begin{bmatrix}1\\0\\0\end{bmatrix}\).
Check: the first column of the original matrix is zero, so \(\mathbf{A}\begin{bmatrix}1\\0\\0\end{bmatrix}=\begin{bmatrix}0\\0\\0\end{bmatrix}\). This verifies the nonzero null-space vector.
Common Mistake: Counting Pivot Rows Instead of Pivot Columns
A common error is to count the pivots and compare that count with the number of rows. In the second example there are two pivot rows and two pivots, but there are three input variables. Concluding that the transformation is one-to-one because “every row has a pivot” is wrong: column 3 has no pivot, and the free variable \(x_3\) produces the nonzero null-space vector \(\begin{bmatrix}2\\-1\\1\end{bmatrix}\).
The correction is to match the criterion to the input side. The columns of \(\mathbf{A}\) correspond to the coordinates of \(\mathbf{x}\), so injectivity requires a pivot in every column. A pivot in every row is a different condition; it concerns whether outputs can be reached and belongs to the study of surjectivity. For injectivity, count the columns and inspect each column for a pivot.
What the Criterion Tells You
The pivot-column test is a practical form of the null space test. It does not merely report whether a transformation is one-to-one: when a column lacks a pivot, the free variable gives a direct route to a nonzero input that maps to zero. Conversely, when every column has a pivot, the homogeneous system has no free variables and no nonzero null-space vector. This is why row reduction turns a statement about all pairs of inputs into a finite check of pivot positions.
Check Your Understanding
For each question, connect the pivot pattern to the homogeneous system before deciding whether the transformation is one-to-one.
- A \(4\times3\) matrix has pivots in columns 1, 2, and 3. What does the criterion imply about its matrix transformation?
- A \(2\times3\) matrix has pivots in columns 1 and 3. Which variable is free, and what does that imply about injectivity?
- Explain why row operations preserve the solutions of \(\mathbf{A}\mathbf{x}=\mathbf{0}\).
- For the matrix \(\begin{bmatrix}1&0&-2\\0&1&1\end{bmatrix}\), find a nonzero vector in its null space and verify it by multiplication.
- In the pivot-column criterion, why is the number of columns—not the number of rows—the relevant count?
