Section ILT  Injective Linear Transformations

It is perhaps most instructive to examine a linear transformation that is not injective first.

Example  NIAQ
Not injective, Archetype Q
Archetype Q is the linear transformation

Notice that for

$\begin{array}{llllllll}\hfill x& =\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \\ \hfill -1\hfill \\ \hfill 2\hfill \\ \hfill 4\hfill \end{array}\right]& \hfill y& =\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 7\hfill \\ \hfill 0\hfill \\ \hfill 5\hfill \\ \hfill 7\hfill \end{array}\right]& \hfill & & \hfill & \\ \multicolumn{8}{c}{\text{ we have}}\\ \\ \hfill T\left(\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \\ \hfill -1\hfill \\ \hfill 2\hfill \\ \hfill 4\hfill \end{array}\right]\right)& =\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 55\hfill \\ \hfill 72\hfill \\ \hfill 77\hfill \\ \hfill 31\hfill \end{array}\right]& \hfill T\left(\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 7\hfill \\ \hfill 0\hfill \\ \hfill 5\hfill \\ \hfill 7\hfill \end{array}\right]\right)& =\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 55\hfill \\ \hfill 72\hfill \\ \hfill 77\hfill \\ \hfill 31\hfill \end{array}\right]& \hfill & & \hfill & \end{array}$

So we have two vectors from the domain, $x\ne y$ , yet $T\left(x\right)=T\left(y\right)$ , in violation of Definition ILT. This is another example where you should not concern yourself with how $x$ and $y$ were selected, as this will be explained shortly. However, do understand why these two vectors provide enough evidence to conclude that $T$ is not injective. $⊠$

Here’s a cartoon of a non-injective linear transformation. Notice that the central feature of this cartoon is that $T\left(u\right)=v=T\left(w\right)$ . Even though this happens again with some unnamed vectors, it only takes one occurrence to destroy the possibility of injectivity. Note also that the two vectors displayed in the bottom of $V$ have no bearing, either way, on the injectivity of $T$ .

To show that a linear transformation is not injective, it is enough to find a single pair of inputs that get sent to the identical output, as in Example NIAQ. However, to show that a linear transformation is injective we must establish that this coincidence of outputs never occurs. Here is an example that shows how to establish this.

Example  IAR
Injective, Archetype R
Archetype R is the linear transformation

To establish that $R$ is injective we must begin with the assumption that $T\left(x\right)=T\left(y\right)$ and somehow arrive from this at the conclusion that $x=y$ . Here we go,

$\begin{array}{cc}T\left(x\right)=T\left(y\right)& \\ T\left(\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \\ \hfill x_4\hfill \\ \hfill x_5\hfill \end{array}\right]\right)=T\left(\left[\begin{array}{c}\hfill y_1\hfill \\ \hfill y_2\hfill \\ \hfill y_3\hfill \\ \hfill y_4\hfill \\ \hfill y_5\hfill \end{array}\right]\right)& \\ \left[\begin{array}{c}\hfill -65x_1+128x_2+10x_3-262x_4+40x_5\hfill \\ \hfill 36x_1-73x_2-x_3+151x_4-16x_5\hfill \\ \hfill -44x_1+88x_2+5x_3-180x_4+24x_5\hfill \\ \hfill 34x_1-68x_2-3x_3+140x_4-18x_5\hfill \\ \hfill 12x_1-24x_2-x_3+49x_4-5x_5\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -65y_1+128y_2+10y_3-262y_4+40y_5\hfill \\ \hfill 36y_1-73y_2-y_3+151y_4-16y_5\hfill \\ \hfill -44y_1+88y_2+5y_3-180y_4+24y_5\hfill \\ \hfill 34y_1-68y_2-3y_3+140y_4-18y_5\hfill \\ \hfill 12y_1-24y_2-y_3+49y_4-5y_5\hfill \end{array}\right]& \\ \left[\begin{array}{c}\hfill -65x_1+128x_2+10x_3-262x_4+40x_5\hfill \\ \hfill 36x_1-73x_2-x_3+151x_4-16x_5\hfill \\ \hfill -44x_1+88x_2+5x_3-180x_4+24x_5\hfill \\ \hfill 34x_1-68x_2-3x_3+140x_4-18x_5\hfill \\ \hfill 12x_1-24x_2-x_3+49x_4-5x_5\hfill \end{array}\right]-\left[\begin{array}{c}\hfill -65y_1+128y_2+10y_3-262y_4+40y_5\hfill \\ \hfill 36y_1-73y_2-y_3+151y_4-16y_5\hfill \\ \hfill -44y_1+88y_2+5y_3-180y_4+24y_5\hfill \\ \hfill 34y_1-68y_2-3y_3+140y_4-18y_5\hfill \\ \hfill 12y_1-24y_2-y_3+49y_4-5y_5\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]& \\ \left[\begin{array}{c}\hfill -65\left(x_1-y_1\right)+128\left(x_2-y_2\right)+10\left(x_3-y_3\right)-262\left(x_4-y_4\right)+40\left(x_5-y_5\right)\hfill \\ \hfill 36\left(x_1-y_1\right)-73\left(x_2-y_2\right)-\left(x_3-y_3\right)+151\left(x_4-y_4\right)-16\left(x_5-y_5\right)\hfill \\ \hfill -44\left(x_1-y_1\right)+88\left(x_2-y_2\right)+5\left(x_3-y_3\right)-180\left(x_4-y_4\right)+24\left(x_5-y_5\right)\hfill \\ \hfill 34\left(x_1-y_1\right)-68\left(x_2-y_2\right)-3\left(x_3-y_3\right)+140\left(x_4-y_4\right)-18\left(x_5-y_5\right)\hfill \\ \hfill 12\left(x_1-y_1\right)-24\left(x_2-y_2\right)-\left(x_3-y_3\right)+49\left(x_4-y_4\right)-5\left(x_5-y_5\right)\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]& \\ \left[\begin{array}{ccccc}\hfill -65\hfill & \hfill 128\hfill & \hfill 10\hfill & \hfill -262\hfill & \hfill 40\hfill \\ \hfill 36\hfill & \hfill -73\hfill & \hfill -1\hfill & \hfill 151\hfill & \hfill -16\hfill \\ \hfill -44\hfill & \hfill 88\hfill & \hfill 5\hfill & \hfill -180\hfill & \hfill 24\hfill \\ \hfill 34\hfill & \hfill -68\hfill & \hfill -3\hfill & \hfill 140\hfill & \hfill -18\hfill \\ \hfill 12\hfill & \hfill -24\hfill & \hfill -1\hfill & \hfill 49\hfill & \hfill -5\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1-y_1\hfill \\ \hfill x_2-y_2\hfill \\ \hfill x_3-y_3\hfill \\ \hfill x_4-y_4\hfill \\ \hfill x_5-y_5\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]& \end{array}$

Now we recognize that we have a homogeneous system of 5 equations in 5 variables (the terms $x_i-y_i$ are the variables), so we row-reduce the coefficient matrix to

So the only solution is the trivial solution

$\begin{array}{llllllllllllllllllll}\hfill x_1-y_1& =0& \hfill x_2-y_2& =0& \hfill x_3-y_3& =0& \hfill x_4-y_4& =0& \hfill x_5-y_5& =0& \hfill & & \hfill & & \hfill & & \hfill & & \hfill & \end{array}$

and we conclude that indeed $x=y$ . By Definition ILT, $T$ is injective. $⊠$

Here’s the cartoon for an injective linear transformation. It is meant to suggest that we never have two inputs associated with a single output. Again, the two lonely vectors at the bottom of $V$ have no bearing either way on the injectivity of $T$ .

Let’s now examine an injective linear transformation between abstract vector spaces.

Example  IAV
Injective, Archetype V
Archetype V is defined by

To establish that the linear transformation is injective, begin by supposing that two polynomial inputs yield the same output matrix,

Then

$\begin{array}{llllll}\hfill \mathcal{O}& =\left[\begin{array}{cc}\hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill \end{array}\right]& \hfill & & \hfill & \\ \hfill & =T\left(a_1+b_{1}x+c_1{x}^2+d_1{x}^3\right)-T\left(a_2+b_{2}x+c_2{x}^2+d_2{x}^3\right)& \hfill & \text{ Hypothesis}& \hfill & & \hfill & \\ \hfill & =T\left(\left(a_1+b_{1}x+c_1{x}^2+d_1{x}^3\right)-\left(a_2+b_{2}x+c_2{x}^2+d_2{x}^3\right)\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =T\left(\left(a_1-a_2\right)+\left(b_1-b_2\right)x+\left(c_1-c_2\right)x^2+\left(d_1-d_2\right)x^3\right)& \hfill & \text{ Operations in }{P}_3& \hfill & & \hfill & \\ \hfill & =\left[\begin{array}{cc}\hfill \left(a_1-a_2\right)+\left(b_1-b_2\right)\hfill & \hfill \left(a_1-a_2\right)-2\left(c_1-c_2\right)\hfill \\ \hfill \left(d_1-d_2\right)\hfill & \hfill \left(b_1-b_2\right)-\left(d_1-d_2\right)\hfill \end{array}\right]& \hfill & \text{ Definition of }T& \hfill & & \hfill & \end{array}$

This single matrix equality translates to the homogeneous system of equations in the variables $a_i-b_i$ ,

$\begin{array}{llll}\hfill \left(a_1-a_2\right)+\left(b_1-b_2\right)& =0& \hfill & \\ \hfill \left(a_1-a_2\right)-2\left(c_1-c_2\right)& =0& \hfill & \\ \hfill \left(d_1-d_2\right)& =0& \hfill & \\ \hfill \left(b_1-b_2\right)-\left(d_1-d_2\right)& =0& \hfill & \end{array}$

This system of equations can be rewritten as the matrix equation

Since the coefficient matrix is nonsingular (check this) the only solution is trivial, i.e.

$\begin{array}{llllllllllllllll}\hfill a_1-a_2& =0& \hfill b_1-b_2& =0& \hfill c_1-c_2& =0& \hfill d_1-d_2& =0& \hfill & & \hfill & & \hfill & & \hfill & \\ \multicolumn{16}{c}{\text{ so that}}\\ \\ \hfill a_1& =a_2& \hfill b_1& =b_2& \hfill c_1& =c_2& \hfill d_1& =d_2& \hfill & & \hfill & & \hfill & & \hfill & \end{array}$

so the two inputs must be equal polynomials. By Definition ILT, $T$ is injective. $⊠$

For a linear transformation $T:U\to V$ , the kernel is a subset of the domain $U$ . Informally, it is the set of all inputs that the transformation sends to the zero vector of the codomain. It will have some natural connections with the null space of a matrix, so we will keep the same notation, and if you think about your objects, then there should be little confusion. Here’s the careful definition.

Definition  KLT
Kernel of a Linear Transformation
Suppose $T:U\to V$ is a linear transformation. Then the kernel of $T$ is the set

(This definition contains Notation KLT.) $△$

Notice that the kernel of $T$ is just the preimage of $0$ , $T^{-1}\left(0\right)$ (Definition PI). Here’s an example.

Example  NKAO
Nontrivial kernel, Archetype O
Archetype O is the linear transformation

To determine the elements of ${ℂ}^3$ in $\mathcal{K}\left(T\right)$ , find those vectors $u$ such that $T\left(u\right)=0$ , that is,

$\begin{array}{llll}\hfill T\left(u\right)& =0& \hfill & \\ \hfill \left[\begin{array}{c}\hfill -u_1+u_2-3u_3\hfill \\ \hfill -u_1+2u_2-4u_3\hfill \\ \hfill u_1+u_2+u_3\hfill \\ \hfill 2u_1+3u_2+u_3\hfill \\ \hfill u_1+2u_3\hfill \end{array}\right]& =\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]& \hfill & \end{array}$

Vector equality (Definition CVE) leads us to a homogeneous system of 5 equations in the variables $u_i$ ,

$\begin{array}{llll}\hfill -u_1+u_2-3u_3& =0& \hfill & \\ \hfill -u_1+2u_2-4u_3& =0& \hfill & \\ \hfill u_1+u_2+u_3& =0& \hfill & \\ \hfill 2u_1+3u_2+u_3& =0& \hfill & \\ \hfill u_1+2u_3& =0& \hfill & \end{array}$

Row-reducing the coefficient matrix gives

The kernel of $T$ is the set of solutions to this homogeneous system of equations, which by Theorem BNS can be expressed as

$⊠$

We know that the span of a set of vectors is always a subspace (Theorem SSS), so the kernel computed in Example NKAO is also a subspace. This is no accident, the kernel of a linear transformation is always a subspace.

Theorem  KLTS
Kernel of a Linear Transformation is a Subspace
Suppose that $T:U\to V$ is a linear transformation. Then the kernel of $T$ , $\mathcal{K}\left(T\right)$ , is a subspace of $U$ . $\square$

Proof   We can apply the three-part test of Theorem TSS. First $T\left(0_U\right)=0_V$ by Theorem LTTZZ, so $0_U\in \mathcal{K}\left(T\right)$ and we know that the kernel is non-empty.

Suppose we assume that $x,y\in \mathcal{K}\left(T\right)$ . Is $x+y\in \mathcal{K}\left(T\right)$ ?

$\begin{array}{llllllll}\hfill T\left(x+y\right)& =T\left(x\right)+T\left(y\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =0+0& \hfill & x,y\in \mathcal{K}\left(T\right)& \hfill & & \hfill & \\ \hfill & =0& \hfill & \text{Property Z}& \hfill & & \hfill & \end{array}$

This qualifies $x+y$ for membership in $\mathcal{K}\left(T\right)$ . So we have additive closure.

Suppose we assume that $\alpha \in {ℂ}^{}$ and $x\in \mathcal{K}\left(T\right)$ . Is $\alpha x\in \mathcal{K}\left(T\right)$ ?

$\begin{array}{llllllll}\hfill T\left(\alpha x\right)& =\alpha T\left(x\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =\alpha 0& \hfill & x\in \mathcal{K}\left(T\right)& \hfill & & \hfill & \\ \hfill & =0& \hfill & \text{Theorem ZVSM}& \hfill & & \hfill & \end{array}$

This qualifies $\alpha x$ for membership in $\mathcal{K}\left(T\right)$ . So we have scalar closure and Theorem TSS tells us that $\mathcal{K}\left(T\right)$ is a subspace of $U$ . $■$

Let’s compute another kernel, now that we know in advance that it will be a subspace.

Example  TKAP
Trivial kernel, Archetype P
Archetype P is the linear transformation

To determine the elements of ${ℂ}^3$ in $\mathcal{K}\left(T\right)$ , find those vectors $u$ such that $T\left(u\right)=0$ , that is,

$\begin{array}{llll}\hfill T\left(u\right)& =0& \hfill & \\ \hfill \left[\begin{array}{c}\hfill -u_1+u_2+u_3\hfill \\ \hfill -u_1+2u_2+2u_3\hfill \\ \hfill u_1+u_2+3u_3\hfill \\ \hfill 2u_1+3u_2+u_3\hfill \\ \hfill -2u_1+u_2+3u_3\hfill \end{array}\right]& =\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]& \hfill & \end{array}$

Vector equality (Definition CVE) leads us to a homogeneous system of 5 equations in the variables $u_i$ ,

$\begin{array}{llll}\hfill -u_1+u_2+u_3& =0& \hfill & \\ \hfill -u_1+2u_2+2u_3& =0& \hfill & \\ \hfill u_1+u_2+3u_3& =0& \hfill & \\ \hfill 2u_1+3u_2+u_3& =0& \hfill & \\ \hfill -2u_1+u_2+3u_3& =0& \hfill & \end{array}$

Row-reducing the coefficient matrix gives

The kernel of $T$ is the set of solutions to this homogeneous system of equations, which is simply the trivial solution $u=0$ , so

$⊠$

Our next theorem says that if a preimage is a non-empty set then we can construct it by picking any one element and adding on elements of the kernel.

Theorem  KPI
Kernel and Pre-Image
Suppose $T:U\to V$ is a linear transformation and $v\in V$ . If the preimage $T^{-1}\left(v\right)$ is non-empty, and $u\in T^{-1}\left(v\right)$ then

$\square$

Proof   Let $M=\left\{\left.u+z\right|z\in \mathcal{K}\left(T\right)\right\}$ . First, we show that $M\subseteq T^{-1}\left(v\right)$ . Suppose that $w\in M$ , so $w$ has the form $w=u+z$ , where $z\in \mathcal{K}\left(T\right)$ . Then

$\begin{array}{llllll}\hfill T\left(w\right)& =T\left(u+z\right)& \hfill & & \hfill & \\ \hfill & =T\left(u\right)+T\left(z\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =v+0& \hfill & u\in T^{-1}\left(v\right),z\in \mathcal{K}\left(T\right)& \hfill & & \hfill & \\ \hfill & =v& \hfill & \text{Property Z}& \hfill & & \hfill & \end{array}$

which qualifies $w$ for membership in the preimage of $v$ , $w\in T^{-1}\left(v\right)$ .

For the opposite inclusion, suppose $x\in T^{-1}\left(v\right)$ . Then,

$\begin{array}{llllllll}\hfill T\left(x-u\right)& =T\left(x\right)-T\left(u\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =v-v& \hfill & x,u\in T^{-1}\left(v\right)& \hfill & & \hfill & \\ \hfill & =0& \hfill & & \hfill & \end{array}$

This qualifies $x-u$ for membership in the kernel of $T$ , $\mathcal{K}\left(T\right)$ . So there is a vector $z\in \mathcal{K}\left(T\right)$ such that $x-u=z$ . Rearranging this equation gives $x=u+z$ and so $x\in M$ . So $T^{-1}\left(v\right)\subseteq M$ and we see that $M=T^{-1}\left(v\right)$ , as desired. $■$

This theorem, and its proof, should remind you very much of Theorem PSPHS. Additionally, you might go back and review Example SPIAS. Can you tell now which is the only preimage to be a subspace?

The next theorem is one we will cite frequently, as it characterizes injections by the size of the kernel.

Theorem  KILT
Kernel of an Injective Linear Transformation
Suppose that $T:U\to V$ is a linear transformation. Then $T$ is injective if and only if the kernel of $T$ is trivial, $\mathcal{K}\left(T\right)=\left\{0\right\}$ . $\square$

Proof   ( $\Rightarrow$ ) We assume $T$ is injective and we need to establish that two sets are equal ( Definition SE). Since the kernel is a subspace ( Theorem KLTS), $\left\{0\right\}\subseteq \mathcal{K}\left(T\right)$ . To establish the opposite inclusion, suppose $x\in \mathcal{K}\left(T\right)$ .

$\begin{array}{llllllll}\hfill T\left(x\right)& =0& \hfill & \text{Definition KLT}& \hfill & & \hfill & \\ \hfill & =T\left(0\right)& \hfill & \text{Theorem LTTZZ}& \hfill & & \hfill & \end{array}$

We can apply Definition ILT to conclude that $x=0$ . Therefore $\mathcal{K}\left(T\right)\subseteq \left\{0\right\}$ and by Definition SE, $\mathcal{K}\left(T\right)=\left\{0\right\}$ .

( $\Leftarrow$ ) To establish that $T$ is injective, appeal to Definition ILT and begin with the assumption that $T\left(x\right)=T\left(y\right)$ . Then

$\begin{array}{llllllll}\hfill T\left(x-y\right)& =T\left(x\right)-T\left(y\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =0& \hfill & \text{ Hypothesis}& \hfill & & \hfill & \end{array}$

So $x-y\in \mathcal{K}\left(T\right)$ by Definition KLT and with the hypothesis that the kernel is trivial we conclude that $x-y=0$ . Then

$\begin{array}{lll}\hfill y=y+0=y+\left(x-y\right)=x& & \hfill \end{array}$

thus establishing that $T$ is injective by Definition ILT. $■$

Example  NIAQR
Not injective, Archetype Q, revisited
We are now in a position to revisit our first example in this section, Example NIAQ. In that example, we showed that Archetype Q is not injective by constructing two vectors, which when used to evaluate the linear transformation provided the same output, thus violating Definition ILT. Just where did those two vectors come from?

The key is the vector

which you can check is an element of $\mathcal{K}\left(T\right)$ for Archetype Q. Choose a vector $x$ at random, and then compute $y=x+z$ (verify this computation back in Example NIAQ). Then

$\begin{array}{llllll}\hfill T\left(y\right)& =T\left(x+z\right)& \hfill & & \hfill & \\ \hfill & =T\left(x\right)+T\left(z\right)& \hfill & \text{Definition LT}& \hfill & & \hfill & \\ \hfill & =T\left(x\right)+0& \hfill & z\in \mathcal{K}\left(T\right)& \hfill & & \hfill & \\ \hfill & =T\left(x\right)& \hfill & \text{Property Z}& \hfill & & \hfill & \end{array}$

Whenever the kernel of a linear transformation is non-trivial, we can employ this device and conclude that the linear transformation is not injective. This is another way of viewing Theorem KILT. For an injective linear transformation, the kernel is trivial and our only choice for $z$ is the zero vector, which will not help us create two different inputs for $T$ that yield identical outputs. For every one of the archetypes that is not injective, there is an example presented of exactly this form. $⊠$

Example  NIAO
Not injective, Archetype O
In Example NKAO the kernel of Archetype O was determined to be

a subspace of ${ℂ}^3$ with dimension 1. Since the kernel is not trivial, Theorem KILT tells us that $T$ is not injective. $⊠$

Example  IAP
Injective, Archetype P
In Example TKAP it was shown that the linear transformation in Archetype P has a trivial kernel. So by Theorem KILT, $T$ is injective. $⊠$

There is a connection between injective linear transformations and linearly independent sets that we will make precise in the next two theorems. However, more informally, we can get a feel for this connection when we think about how each property is defined. A set of vectors is linearly independent if the only relation of linear dependence is the trivial one. A linear transformation is injective if the only way two input vectors can produce the same output is in the trivial way, when both input vectors are equal.

Theorem  ILTLI
Injective Linear Transformations and Linear Independence
Suppose that $T:U\to V$ is an injective linear transformation and $S=\left\{u_1,u_2,u_3,\dots ,u_t\right\}$ is a linearly independent subset of $U$ . Then $R=\left\{T\left(u_1\right),T\left(u_2\right),T\left(u_3\right),\dots ,T\left(u_t\right)\right\}$ is a linearly independent subset of $V$ . $\square$

Proof   Begin with a relation of linear dependence on $R$ (Definition RLD, Definition LI),

$\begin{array}{llllll}\hfill a_{1}T\left(u_1\right)+a_{2}T\left(u_2\right)+a_{3}T\left(u_3\right)+\dots +a_{t}T\left(u_t\right)& =0& \hfill & & \hfill & \\ \hfill T\left(a_1{u}_1+a_2{u}_2+a_3{u}_3+\cdots +a_t{u}_t\right)& =0& \hfill & \text{Theorem LTLC}& \hfill & & \hfill & \\ \hfill a_1{u}_1+a_2{u}_2+a_3{u}_3+\cdots +a_t{u}_t& \in \mathcal{K}\left(T\right)& \hfill & \text{Definition KLT}& \hfill & & \hfill & \\ \hfill a_1{u}_1+a_2{u}_2+a_3{u}_3+\cdots +a_t{u}_t& \in \left\{0\right\}& \hfill & \text{Theorem KILT}& \hfill & & \hfill & \\ \hfill a_1{u}_1+a_2{u}_2+a_3{u}_3+\cdots +a_t{u}_t& =0& \hfill & \text{Definition SET}& \hfill & & \hfill & \\ \hfill & & \hfill & & \hfill \end{array}$

Since this is a relation of linear dependence on the linearly independent set $S$ , we can conclude that

$\begin{array}{llllllllllllllllllll}\hfill a_1& =0& \hfill a_2& =0& \hfill a_3& =0& \hfill \dots & & \hfill a_t& =0& \hfill & & \hfill & & \hfill & & \hfill & & \hfill & \end{array}$

and this establishes that $R$ is a linearly independent set. $■$

Theorem  ILTB
Injective Linear Transformations and Bases
Suppose that $T:U\to V$ is a linear transformation and $B=\left\{u_1,u_2,u_3,\dots ,u_m\right\}$ is a basis of $U$ . Then $T$ is injective if and only if $C=\left\{T\left(u_1\right),T\left(u_2\right),T\left(u_3\right),\dots ,T\left(u_m\right)\right\}$ is a linearly independent subset of $V$ . $\square$

Proof   ( $\Rightarrow$ ) Assume $T$ is injective. Since $B$ is a basis, we know $B$ is linearly independent (Definition B). Then Theorem ILTLI says that $C$ is a linearly independent subset of $V$ .

( $\Leftarrow$ ) Assume that $C$ is linearly independent. To establish that $T$ is injective, we will show that the kernel of $T$ is trivial ( Theorem KILT). Suppose that $u\in \mathcal{K}\left(T\right)$ . As an element of $U$ , we can write $u$ as a linear combination of the basis vectors in $B$ (uniquely). So there are are scalars, $a_1,a_2,a_3,\dots ,a_m$ , such that

Then,

$\begin{array}{llllllll}\hfill 0& =T\left(u\right)& \hfill & \text{Definition KLT}& \hfill & & \hfill & \\ \hfill & =T\left(a_1{u}_1+a_2{u}_2+a_3{u}_3+\cdots +a_m{u}_m\right)& \hfill & \text{Definition TSVS}& \hfill & & \hfill & \\ \hfill & =a_{1}T\left(u_1\right)+a_{2}T\left(u_2\right)+a_{3}T\left(u_3\right)+\cdots +a_{m}T\left(u_m\right)& \hfill & \text{Theorem LTLC}& \hfill & & \hfill & \end{array}$

This is a relation of linear dependence (Definition RLD) on the linearly independent set $C$ , so the scalars are all zero: $a_1=a_2=a_3=\cdots =a_m=0$ . Then

$\begin{array}{llllll}\hfill u& =a_1{u}_1+a_2{u}_2+a_3{u}_3+\cdots +a_m{u}_m& \hfill & & \hfill & \\ \hfill & =0u_1+0u_2+0u_3+\cdots +0u_m& \hfill & \text{Theorem ZSSM}& \hfill & & \hfill & \\ \hfill & =0+0+0+\cdots +0& \hfill & \text{Theorem ZSSM}& \hfill & & \hfill & \\ \hfill & =0& \hfill & \text{Property Z}& \hfill & & \hfill & \end{array}$

Since $u$ was chosen as an arbitrary vector from $\mathcal{K}\left(T\right)$ , we have $\mathcal{K}\left(T\right)=\left\{0\right\}$ and Theorem KILT tells us that $T$ is injective. $■$

Theorem  ILTD
Injective Linear Transformations and Dimension
Suppose that $T:U\to V$ is an injective linear transformation. Then $dim\left(U\right)\le dim\left(V\right)$ . $\square$

Proof   Suppose to the contrary that $m=dim\left(U\right)>dim\left(V\right)=t$ . Let $B$ be a basis of $U$ , which will then contain $m$ vectors. Apply $T$ to each element of $B$ to form a set $C$ that is a subset of $V$ . By Theorem ILTB, $C$ is linearly independent and therefore must contain $m$ distinct vectors. So we have found a set of $m$ linearly independent vectors in $V$ , a vector space of dimension $t$ , with $m>t$ . However, this contradicts Theorem G, so our assumption is false and $dim\left(U\right)\le dim\left(V\right)$ . $■$

Example  NIDAU
Not injective by dimension, Archetype U
The linear transformation in Archetype U is

Since $dim\left(M_{23}\right)=6>4=dim\left({ℂ}^4\right)$ , $T$ cannot be injective for then $T$ would violate Theorem ILTD. $⊠$

Notice that the previous example made no use of the actual formula defining the function. Merely a comparison of the dimensions of the domain and codomain are enough to conclude that the linear transformation is not injective. Archetype M and Archetype N are two more examples of linear transformations that have “big” domains and “small” codomains, resulting in “collisions” of outputs and thus are non-injective linear transformations.

In Subsection LT.NLTFO we saw how to combine linear transformations to build new linear transformations, specifically, how to build the composition of two linear transformations (Definition LTC). It will be useful later to know that the composition of injective linear transformations is again injective, so we prove that here.

Theorem  CILTI
Composition of Injective Linear Transformations is Injective
Suppose that $T:U\to V$ and $S:V\to W$ are injective linear transformations. Then $\left(S\circ T\right):U\to W$ is an injective linear transformation. $\square$

Proof   That the composition is a linear transformation was established in Theorem CLTLT, so we need only establish that the composition is injective. Applying Definition ILT, choose $x$ , $y$ from $U$ . Then if $\left(S\circ T\right)\left(x\right)=\left(S\circ T\right)\left(y\right)$ ,

$\begin{array}{llllllllllll}\hfill & \Rightarrow & \hfill S\left(T\left(x\right)\right)& =S\left(T\left(y\right)\right)& \hfill & \text{Definition LTC}& \hfill & & \hfill & & \hfill & \\ \hfill & \Rightarrow & \hfill T\left(x\right)& =T\left(y\right)& \hfill & \text{Definition ILT}\text{ for }S& \hfill & & \hfill & & \hfill & \\ \hfill & \Rightarrow & \hfill x& =y& \hfill & \text{Definition ILT}\text{ for }T& \hfill & & \hfill & & \hfill & \end{array}$

$■$