## Friday, May 26, 2006

### It's A One-To-One Tie! Topic: Linear Algebra.

Note: Added my linear algebra book to the Math Books page.

--------------------

Definition: A function $f: A \to B$ is linear if $f(x+y) = f(x)+f(y)$ and $cf(x) = f(cx)$ for $x,y \in A$ and $c \in \mathbb{R}$ (or, rather, any field $\mathbb{F}$). Furthermore, it is one-to-one if and only if $f(x) = f(y) \Rightarrow x = y$.

--------------------

Problem: Let $V$ and $W$ be vector spaces, and let $T: V \to W$ be linear. Then $T$ is one-to-one if and only if $T$ carries linearly independent subsets of $V$ onto linearly independent subsets of $W$.

Solution: First we will show that if $T$ is one-to-one, then it carries linearly independent subsets of $V$ onto linearly independent subsets of $W$.

Let $S$ be a linearly independent subset of $V$. Suppose $S = \{x_1, x_2, \ldots, x_k\}$. We want to show that $R = \{T(x_1), T(x_2), \ldots, T(x_k)\}$ is also linearly independent. Suppose that $R$ is not. Then there exist $a_1, a_2, \ldots, a_k$ not all zero such that

$a_1T(x_1)+a_2T(x_2)+\cdots+a_kT(x_k) = 0$.

Since $T$ is linear, we can rewrite this as

$T(a_1x_1)+T(a_2x_2)+\cdots+T(a_kx_k) = T(a_1x_1+a_2x_2+\cdots+a_kx_k) = 0$.

Since $T(0) = 0$ and $T$ is one-to-one, we must have

$a_1x_1+a_2x_2+\cdots+a_kx_k = 0$.

But $S$ is linearly independent, so this is only possible if $a_1 = a_2 = \cdots = a_k = 0$, a contradiction. So $R$ is linearly independent.

Now, we will prove the converse - if $T$ takes linearly independent subsets of $V$ to linearly independent subsets of $W$ then $T$ is one-to-one. Let $x, y \in V$ be nonzero such that $T(x) = T(y)$. It suffices to show that $x = y$.

If $\{x, y\}$ is linearly dependent, then $x = cy$ for some $c \in \mathbb{R}$, so

$T(x) = T(y) = T(cx) = cT(x)$.

If $T(x) = T(y) \neq 0$, we have $c = 1 \Rightarrow x = y$. In the case that $T(x) = T(y) = 0$, the set $\{x\}$ is linearly independent but $T$ takes it onto $\{0\}$, which is linearly dependent, a contradiction.

If $\{x, y\}$ is linearly independent, then $\{T(x), T(y)\}$ is also linearly independent. But since $T(x) = T(y)$, the set is clearly linearly dependent, a contradiction.

Lastly, we have $T(0) = 0$. So $T$ must be a one-to-one function, as desired. QED.

--------------------

Comment: Basically, we made extensive use of the properties of a linear transformation to prove both directions. A nice corollary to this proof is that if $T$ is one-to-one, then $S$ is linearly independent if and only if $T(S)$ is linearly independent.

--------------------

Practice Problem: Let $V$ and $W$ be vector spaces, and let $T: V \to W$ be linear. Then $T$ is one-to-one if and only if $N(T) = \{0\}$ (here, $N(T)$ is the kernal of $T$, defined by $N(T) = \{x | T(x) = 0\}$).