When Can Two Inputs Have the Same Output?
A transformation is one-to-one when it never sends two different inputs to the same output. For a matrix transformation, the question can be reduced to a homogeneous system: if two inputs have equal outputs, their difference is sent to the zero vector. This gives a practical test using the null space of the matrix, and it explains why row reduction can reveal whether a transformation loses information.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\). It defines the linear transformation \(T:\mathbb{R}^n\to\mathbb{R}^m\) by \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\). The transformation is one-to-one, or injective, if \(T(\mathbf{x})=T(\mathbf{z})\) implies \(\mathbf{x}=\mathbf{z}\) for every \(\mathbf{x},\mathbf{z}\in\mathbb{R}^n\). Its null space is the set of inputs mapped to the zero vector.
The zero vector always belongs to \(\operatorname{Nul}\mathbf{A}\), since \(\mathbf{A}\mathbf{0}=\mathbf{0}\). The crucial question is whether any nonzero vector belongs as well. A nonzero vector in the null space represents a change in input that leaves the output unchanged.
Proof. Suppose first that \(T\) is one-to-one. If \(\mathbf{x}\in\operatorname{Nul}\mathbf{A}\), then \(\mathbf{A}\mathbf{x}=\mathbf{0}=\mathbf{A}\mathbf{0}\). Thus \(T(\mathbf{x})=T(\mathbf{0})\). Since \(T\) is one-to-one, \(\mathbf{x}=\mathbf{0}\). So the null space contains no vector except \(\mathbf{0}\). Conversely, suppose \(\operatorname{Nul}\mathbf{A}=\{\mathbf{0}\}\), and take any \(\mathbf{x},\mathbf{z}\in\mathbb{R}^n\) with \(T(\mathbf{x})=T(\mathbf{z})\). Then \(\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{z}\), so linearity of matrix multiplication gives \(\mathbf{A}(\mathbf{x}-\mathbf{z})=\mathbf{0}\). Therefore \(\mathbf{x}-\mathbf{z}\in\operatorname{Nul}\mathbf{A}\), which forces \(\mathbf{x}-\mathbf{z}=\mathbf{0}\). Hence \(\mathbf{x}=\mathbf{z}\), and \(T\) is one-to-one. \(\square\)
Collisions and Differences of Inputs
The proof gives more than a yes-or-no test: it describes exactly how any collision is related to the null space. If two inputs \(\mathbf{x}\) and \(\mathbf{z}\) produce the same output, then their difference \(\mathbf{x}-\mathbf{z}\) is in the null space. Conversely, if a nonzero vector \(\mathbf{v}\) is in the null space, then \(\mathbf{v}\) and \(\mathbf{0}\) are distinct inputs with the same output.
Proof. If \(T(\mathbf{x})=T(\mathbf{z})\), then \(\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{z}\), so \(\mathbf{A}(\mathbf{x}-\mathbf{z})=\mathbf{0}\). By the definition of the null space, \(\mathbf{x}-\mathbf{z}\in\operatorname{Nul}\mathbf{A}\). In the other direction, if \(\mathbf{x}-\mathbf{z}\in\operatorname{Nul}\mathbf{A}\), then \(\mathbf{A}(\mathbf{x}-\mathbf{z})=\mathbf{0}\). Distributing the matrix product gives \(\mathbf{A}\mathbf{x}-\mathbf{A}\mathbf{z}=\mathbf{0}\), hence \(\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{z}\), or \(T(\mathbf{x})=T(\mathbf{z})\). If \(\mathbf{v}\ne\mathbf{0}\) is in the null space, set \(\mathbf{x}=\mathbf{v}\) and \(\mathbf{z}=\mathbf{0}\); these are distinct, and both map to \(\mathbf{0}\). \(\square\)
This difference viewpoint is useful when a problem gives two particular inputs and asks whether they collide. Instead of comparing outputs without a plan, calculate their difference and test whether it solves the homogeneous equation. When the question is whether the transformation is one-to-one for all inputs, solve the homogeneous equation generally and determine whether any nonzero solutions exist.
Using Row Reduction to Find the Null Space
To solve \(\mathbf{A}\mathbf{x}=\mathbf{0}\), row-reduce \(\mathbf{A}\). Elementary row operations preserve the solutions of a homogeneous system, so the reduced system has the same null space as the original one. A variable in a column without a pivot is a free variable. If there is a free variable, it can be chosen nonzero and the pivot variables can be determined from it, producing a nonzero solution. If every variable is a pivot variable, the homogeneous system has only the zero solution. The relation between pivots and injectivity is an application of the homogeneous-system pivot test established in the earlier material on linear independence.
There is also a direct connection to the columns. Write \(\mathbf{A}=\begin{bmatrix}\mathbf{a}_1&\cdots&\mathbf{a}_n\end{bmatrix}\) and \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). Then \(\mathbf{A}\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n\). Thus a nonzero solution to \(\mathbf{A}\mathbf{x}=\mathbf{0}\) is a nontrivial linear relation among the columns.
Proof. Suppose \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\ne\mathbf{0}\) and \(\mathbf{x}\in\operatorname{Nul}\mathbf{A}\). Then \(\mathbf{A}\mathbf{x}=\mathbf{0}\), which, by the definition of matrix multiplication in terms of columns, says \(x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0}\). Since \(\mathbf{x}\ne\mathbf{0}\), its coefficients are not all zero, so this is a dependence relation. Conversely, if the columns are dependent, there are coefficients \(x_1,\dots,x_n\), not all zero, with \(x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0}\). Form the nonzero vector \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). The same column formula gives \(\mathbf{A}\mathbf{x}=\mathbf{0}\), so \(\mathbf{x}\in\operatorname{Nul}\mathbf{A}\). \(\square\)
Worked Tests
Worked Example: A One-to-One Transformation
Determine whether \(T:\mathbb{R}^2\to\mathbb{R}^2\), defined by \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\) for \(\mathbf{A}=\begin{bmatrix}1&2\\3&5\end{bmatrix}\), is one-to-one.
We solve \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Row-reduce the coefficient matrix, first subtracting \(3R_1\) from \(R_2\), then multiplying \(R_2\) by \(-1\), and finally subtracting \(2R_2\) from \(R_1\):
The reduced homogeneous system is \(x_1=0\), \(x_2=0\), so \(\operatorname{Nul}\mathbf{A}=\{\mathbf{0}\}\). By the null space test, \(T\) is one-to-one.
Check: Multiplying the reduced matrix by the only solution gives \(\begin{bmatrix}1&0\\0&1\end{bmatrix}\begin{bmatrix}0\\0\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). Row operations preserve the homogeneous solution set, so this verifies the conclusion for the original system as well.
Worked Example: A Nonzero Null Vector Gives a Collision
Let \(T:\mathbb{R}^3\to\mathbb{R}^2\) be given by \(T(\mathbf{x})=\mathbf{A}\mathbf{x}\), where \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\). Find a nonzero null vector and use it to exhibit two inputs with the same output.
The homogeneous system has equations \(x_1+2x_2=0\) and \(x_2+x_3=0\). Its coefficient matrix reduces by \(R_1\to R_1-2R_2\) to
Column 3 has no pivot, so let \(x_3=t\). The equations give \(x_1=2t\) and \(x_2=-t\). Taking \(t=1\) gives \(\mathbf{v}=\begin{bmatrix}2\\-1\\1\end{bmatrix}\), which is nonzero.
Check: \(\mathbf{A}\mathbf{v}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\begin{bmatrix}2\\-1\\1\end{bmatrix}=\begin{bmatrix}2-2+0\\-1+1\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). Therefore \(T(\mathbf{v})=T(\mathbf{0})=\mathbf{0}\), even though \(\mathbf{v}\ne\mathbf{0}\). The transformation is not one-to-one.
Worked Example: Injectivity Depending on a Parameter
For which real values of \(t\) is the transformation defined by \(\mathbf{A}_t=\begin{bmatrix}1&t\\t&1\end{bmatrix}\) one-to-one?
Write the homogeneous equations as \(x_1+tx_2=0\) and \(tx_1+x_2=0\). The first equation gives \(x_1=-tx_2\). Substituting this into the second gives \((1-t^2)x_2=0\). If \(t\ne1\) and \(t\ne-1\), then \(1-t^2\ne0\), so \(x_2=0\), and then \(x_1=0\). The null space is trivial and the transformation is one-to-one.
If \(t=1\), the equations reduce to \(x_1+x_2=0\), so \(\begin{bmatrix}1\\-1\end{bmatrix}\) is a nonzero null vector. If \(t=-1\), they reduce to \(x_1-x_2=0\), so \(\begin{bmatrix}1\\1\end{bmatrix}\) is a nonzero null vector. Thus the transformation fails to be one-to-one at exactly these two parameter values.
Check: At \(t=1\), \(\mathbf{A}_t\begin{bmatrix}1\\-1\end{bmatrix}=\begin{bmatrix}1-1\\1-1\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). At \(t=-1\), \(\mathbf{A}_t\begin{bmatrix}1\\1\end{bmatrix}=\begin{bmatrix}1-1\\-1+1\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). Both exceptional cases have the claimed nonzero null vectors.
Common Mistake: Checking Only the Zero Input
A frequent error is to observe that \(T(\mathbf{0})=\mathbf{0}\) and conclude that no other input can have output \(\mathbf{0}\). But every linear transformation sends the zero vector to the zero vector; that fact alone says nothing about injectivity. For a concrete counterexample, take \(\mathbf{A}=\begin{bmatrix}1&2\\0&0\end{bmatrix}\). The incorrect check stops at \(\mathbf{A}\begin{bmatrix}0\\0\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). The corrected check tests a nonzero vector: \(\mathbf{A}\begin{bmatrix}-2\\1\end{bmatrix}=\begin{bmatrix}-2+2\\0\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). Thus \(\begin{bmatrix}-2\\1\end{bmatrix}\) and \(\begin{bmatrix}0\\0\end{bmatrix}\) are distinct inputs with the same output, so the transformation is not one-to-one.
When using row reduction, another important detail is that the pivot information concerns the columns of the original coefficient matrix: the variables correspond to those columns. A free variable signals a possible nonzero null vector, while a pivot variable is determined by the equations. For this test, do not confuse a transformation's inputs, which are vectors in \(\mathbb{R}^n\), with its outputs in \(\mathbb{R}^m\); the null space consists of inputs.
Check Your Understanding
For each question, use the homogeneous system or the difference of the inputs, and check any proposed null vector by multiplying by the matrix.
- Use the null space test to decide whether the transformation with matrix \(\begin{bmatrix}1&0\\2&1\end{bmatrix}\) is one-to-one.
- Find a nonzero vector in the null space of \(\begin{bmatrix}1&1&1\\0&1&2\end{bmatrix}\), or explain why none exists.
- For the matrix in question 2, give two distinct inputs with the same output.
- Explain why \(\mathbf{A}\mathbf{x}=\mathbf{A}\mathbf{z}\) implies \(\mathbf{x}-\mathbf{z}\in\operatorname{Nul}\mathbf{A}\).
- For which real values of \(t\) does the matrix \(\begin{bmatrix}1&t\\0&1\end{bmatrix}\) define a one-to-one transformation?
