Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A textbook example asks you to prove that for the linear transformation $T\colon V \to W$ that it is one-to one if and only if $T$ carries linearly independent subsets of $V$ onto linearly independent subsets of $W$.

The answer key gives the following solution:

Suppose $T$ is one-to-one. Then let $S$ be a linearly independent subset of $V$, and let $S' = \{T(s)\mid s \in S\}$. (Notice that we’re not assuming that $S$ is finite.) Suppose there are some elements of $S’$ $T(s_1), T(s_2), \ldots , T(s_n)$ and scalars $a_1, \ldots, a_n$ such that $a_1T(s_1)+ \cdots + a_nT(s_n) = 0$. Then by the linearity of $T$,

$a_1T(s_1) + . . . + a_nT(s_n) = 0$

$T(a_1s_1) + . . . + T(a_ns_n) = 0$

$T(a_1s_1 + . . . + a_ns_n) = 0$

But $T$ is one-to-one, so $a_1s_1 + \cdots + a_ns_n = 0$, and thus $a_1 = \cdots = a_n = 0$ because $S$ is linearly independent. Thus $S’$ is linearly independent.

I don't understand this solution. Why does $(a_1s_1+...a_ns_n)$ need to equal 0 just because $T(\text{stuff}) = 0$? A one-to-one function doesn't mean that $T(1) = 1$ and $T(2) = 2$ etc... It simply means all numbers in the codomain must appear in the range.

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

A one-to-one (or injective) function doesn't mean that the codomain must appear in the range. Those are called onto or surjective functions. One-to-one means that for any output, there is exactly one input that maps to it (one output - to - one input).

$$L(\mathbf{x}) = L(\mathbf{y}) \implies \mathbf{x} = \mathbf{y}$$

You may want to contrast the two types:

  1. One-to-one functions have at most one input for each vector in the codomain.
  2. Onto or surjective functions have at least one input for each vector in the codomain.

If you combine the two, you have exactly one input for each vector in the codomain. That's precisely the definition of a bijection mapping.

As for the above theorem, the more fundamental result is perhaps that a linear mapping is one-to-one if and only if it has a trivial kernel. The proof of this is rather simple.

If $L$ is a linear mapping with a trivial kernel, then $$L(\mathbf{x}) = L(\mathbf{y}) \implies L(\mathbf{x}-\mathbf{y}) = \mathbf{0}$$ since the kernel is trivial we must have $\mathbf{x}-\mathbf{y} = \mathbf{0}$ so that the mapping is injective.

If conversely $L$ is injective, then since $L(\mathbf{0}) = \mathbf{0}$ this automatically implies $$L(\mathbf{x}) = \mathbf{0} = L(\mathbf{0})\implies \mathbf{x} = \mathbf{0}$$

Applying the above result should yield what you need.

share|improve this answer
    
Thank you for clearing this up for me. –  Imray Oct 5 '12 at 15:43
add comment

No, incorrect. Being one-to-one means that whenever $T(x) = T(y)$ for some $x$ and $y$ we must have that $x = y$. (The property you referr to is being 'onto').

Now, in your case, we have (as $T$ is linear and hence $T(0) = 0$, that $$ T \left(\sum_{i=1}^n a_is_i\right) = 0 = T(0) \Rightarrow \sum_{i=1}^n a_i s_i = 0 . $$

share|improve this answer
add comment

Suppose $T$ is not one-to-one (I prefer "injective") so that there exist $v_1\neq v_2$ with $T(v_1)=T(v_2)$. Then by linearity $T(v_1-v_2)=0$, so that $\{v_1-v_2\}$ is a linearly independent subset whose image $\{0_W\}$ is linearly dependent. This proves the "if" part.

Now suppose $T$ is injective, $v_1,\ldots,v_k$ a linearly independent, and $c_iT(v_1)+\cdots+c_kT(v_k)=0$ a relation between their images. Then by linearity $T(c_iv_1+\cdots+c_kv_k)=c_iT(v_1)+\cdots+c_kT(v_k)=0_W=T(0_V)$ (the last equality is what you missed), so by injectivity $c_iv_1+\cdots+c_kv_k=0_v$ and by linear independence of the $v_i$ all coefficients $c_i$ have to be $0$; this shows that $T(v_1),\ldots,T(v_k)$ are linearly independent. This proves the "f" part.

I did write the proof so that the independent set was finite, but your proposed answer shows how that can be avoided.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.