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.

OK, I am working on proofs of the rank-nullity (otherwise in my class known as the dimension theorem).

Here's a proof that my professor gave in the class. I want to be sure I understand the reasoning. So I will lay out what he had here with a less-precise layman's wording, as I want to be sure I know what I am doing. It makes the proof easier to memorize for me.

So:

Let V and V be vector spaces.

T:V→W is linear and V is finite-dimensional and

function $f \in Hom_K (V,W)$

Let dim(V) = n for some n$\in \mathbb N$ and dim(ker($f$) = $r$

dim(V) = nullity(T) + rank(T) = dim(ker($ f$ ) + dim(Im($ f$ ))

in some notations (like the one in our text) this wold look like dim(V) = nullity(T) + rank(T) = dim(N(T)) + dim(R(T))

on to the proof:

$ker(f) \subseteq V$. And it is a subspace.

Why a subspace? Because, since the kernel of any function is the set of vectors that goes to zero, adding to those vectors another vector in V will still be in V, a will multiplying them (since they go to zero).

since we let dim(V)=n all the bases (basis-es?) of V will have n elements.

therefore $ \exists$ a basis {$x_1 , x_2 , ... , x_r$} of $ ker(f)$ where r≤n.

(The reason is that any basis will have an equal or lesser number of dimensions than the space it describes. ker(f) is a subspace).

by the exchange lemma, which says that given any linearly independent subset $ \exists {y_1 , y_2 , ... y_s } \in V $ such that {$y_1 , y_2 , ... y_n $}$ \cap $ {$x_1 , x_2 ,... ,x_r$}$ = \varnothing $
the next step says that {$y_1 , y_2 , ... y_n$}$ \cup ${$x_1 , x_2 ,... ,x_r$} is a basis of V.

Now, my question is if that is because the intersection of the two sets is the empty set and they are linearly independent?

After that, we get to saying that {$ f(y_1), f(y_2),... f(y_n)$ } is a basis of Im($ f$ ).

But I am not sure why that is.

He then says we can claim the following: $ λ_1 f(y_1) + λ_2 f(y_2)+... +λ_s f(y_s)= 0 $

for some $λ_1, λ_2, ..., λ_s $ \in $ K

so taking $$f \Big( \sum_{i=1}^s x_i y_i \Big) = 0 $$ we can make that into $$ \Big[ \Big( \sum_{i=1}^s \lambda_i f(y_i) \Big) \Big] = \sum_{i=1}^s \lambda_i y_i \in ker(f)$$

That step I am a bit fuzzy on the reasoning. IIUC, it's just saying that taking the sum of f using the union of x an y sets equals zero (its just f(x,y) ) and the summation of the product of λ and all the f(y) terms is the same as the sum of all the λy terms and they are all in the kernel of f. But I wanted to be sure.

He then said that the above implies that there exists some set of scalars, $α_1, α_2, ... α_s \in$ K s.t.

$$ \sum_{i=1}^s \lambda_i y_i = \sum_{j=1}^r y_i x_j$$ and that further implies

$$\sum_{j=1}^r \alpha_j x_j - \sum_{i=1}^s \alpha_i x_i = 0 $$

which implies $α_j, λi = 0$ for all 1≤j≤r and 1≤i≤s.

and that further implies that the set {$f(y_1), f(y_2), ... ,f(y_s )$} is linearly independent.

Then he says: for all z in the Im(f) there exists x$ \in V$ s.t. $z=f(x)$ (this seems obvious at one level but I felt like it was just sleight of hand).

then

$z = f \Big(\sum_{j=1}^r \alpha_j x_j - \sum_{i=1}^s \lambda_i y_i \Big) = \sum_{j=1}^r \alpha_j f(x_i) + \sum_{i=1}^s x_i f(y_i)= 0 + \sum_{i=1}^s x_i f(y_i)$

and then he says dim(V) = r + s = dim(ker(f)) + dim(Im(f))

its the last few steps I can't seem to justify in my head. Any help would be appreciated (and seeing if I copied this wrong from the board).

share|improve this question
    
one word in your post concerns me greatly: "memorize". Judging from the intent of your post, I think what you really want is to understand the proof so you don't have to just recall it from rigid memory. –  James S. Cook Jun 23 '13 at 19:58
    
i do want to understand it more than I do; my prof said that we're going to be memorizing a lot tho. –  Jesse Jun 23 '13 at 22:00

2 Answers 2

up vote 2 down vote accepted

Perhaps modifying your notation just a bit? $T: V \rightarrow W$ where $dim(V)=n$ and $dim(W)=m$ our goal is to prove that $dim(V) = dim(Null(T))+dim(range(T))$ where $dim(Null(T)) = r$ and $dim(range(T))= rank(T)=s$. To prove this dimension theorem we need to exhibit bases (yes, that's it) which serve to form minimal spanning sets for the null-space and range of $T$.

One approach, pick a basis for $V$, study the matrix for $T$ and steal this theorem from the corresponding theorem for rank and nullity of a matrix. That theorem comes from the nuts and bolts of Gaussian elimination. I don't think that is what your professor intends, so back to the linear algebraic argument.

Note $ker(T) \leq V$ hence $ker(T)$ is a vector space and as it is a subspace of a finite-dimensional vector space it has a finite dimension as well, let's say $r$. Moreover, following your notation, $\beta_o=\{ x_1, x_2, \dots , x_r \}$. I assume at this point you have already proved in your class that if a vector space has a basis with finitely many elements then any such basis has the same number of vectors. We call this number the dimension of the vector space(or subspace).

It is also a simple exercise to show $T(V) \leq W$ hence there exists a basis $\beta_z=\{ z_1,z_2, \dots z_s \}$ for the range. To prove the theorem, we must show $r+s=n$.

If $z_j \in T(V)$ then there exists $y_j \in V$ such that $T(y_j)=z_j$. We show $\{y_1,y_2, \dots, y_s\}$ is linearly independent by supposing otherwise towards a contradiction: suppose $c_1y_1+c_2y_2+ \cdots + c_sy_s=0$ with at least one $c_j \neq 0$ then since $T(0)=0$ and the image of a linear combination is the linear combination of the images: $$ c_1T(y_1)+c_2T(y_2)+ \cdots + c_sT(y_s)=0 $$ Hence $c_1z_1+c_2z_2 + \cdots + c_sz_s=0$ with at least one $c_j \neq 0$ hence $\beta_z$ is linearly dependent. This contradicts our assumption that $\beta_z$ serves as a basis for the image of $T$. Therefore, $\{y_1,y_2, \dots , y_s \} = T^{-1}(\beta_z)$ is a linearly independent subset of $V$.

At this point, I would like to claim $\beta=\beta_o \cup T^{-1}(\beta_z)=\{x_1,x_2, \dots , x_r \} \cup \{y_1,y_2, \dots , y_s \}$ forms a LI subset of $V$. Notice $\beta_o \cap T^{-1}(\beta_z) = \emptyset$ (can you prove this?) Suppose $$c_1x_1+\cdots + c_rx_r+b_1y_1+ \cdots b_sy_s =0. $$ We know $\beta$ contains nonzero vectors hence any nontrivial solution must stem from at least two nonzero coefficients in the above sum. If those two or more coefficients appear in the $c_j$-terms then that cannot happen by LI of $\beta_o$. Likewise, within the $b_j$-coefficients we cannot find a linear dependence by LI of $T^{-1}(\beta_z)$. The only remaining possibility is that both $c_j$ and $b_j$ combine to give linear dependence, however, this is impossible since it contradicts the fact that the bases $\beta_o$ and $T^{-1}(\beta_z)$ are disjoint.

Next, ignoring the fact you may have other theorems to use, we must show $\beta$ spans $V$. Let $v \in V$ and suppose $T(v)=w$. There exist $\alpha_1,\alpha_2, \dots , \alpha_s$ such that $w = \alpha_1z_1+ \cdots \alpha_sz_s$ since $\beta_z$ forms basis of $T(V)$. Furthermore, $T(v-\alpha_1y_1- \cdots -\alpha_sy_s) = T(v)-w=0$ hence $v-\alpha_1y_1- \cdots -\alpha_sy_s \in ker(T)$. Thus, there exist $\beta_1, \dots , \beta_r$ such that $v-\alpha_1y_1- \cdots -\alpha_sy_s = \beta_1x_1+ \cdots +\beta_rx_r$. Consequently, $$ v=\alpha_1y_1+ \cdots \alpha_sy_s +\beta_1x_1+ \cdots +\beta_rx_r $$ which shows $v \in span(\beta)$ and as $v$ was arbitrary we find $span(\beta)=V$.

Therefore, $\beta$ forms a basis for $V$ and so (by that other theorem I'm not proving here) it has $n$-elements. But, $\beta$ also clearly has $r+s$ elements by its construction. Hence $r+s=n$ and the proof is complete.

share|improve this answer
    
See Julian's answer for more about what was wrong with your steps, I thought an easier approach was to just start from scratch. I hope it helps. –  James S. Cook Jun 23 '13 at 19:50
    
yes it does. And I get it about the notation -- our prof uses a certain notation that, of course, doesn't match the text so I have to constantly keep track of things like that and it's making things harder. FFS I wish people could be sort of consistent in classes for those of us without math PhDs. –  Jesse Jun 23 '13 at 21:09

Your "laymen's terms" are sometimes difficult to understand because they lack precision.

Some comments:

  1. On your "why a subspace?" You have to show that for two vectors $v,w\in \operatorname{ker}f$ their sum $v+w$ is also in $\operatorname{ker} f$. And the same for scalar multiplication. That $v+w\in V$ is by definition since $V$ is a vector space.
  2. Now for the part with the exchange theorem. I think you mixed something up. It should probably be $\langle,\rangle$-brackets and $\{0\}$ instead of $\emptyset$. Otherwise you can't conclude that the union of the $x$'s and the $y$'s will be a basis. The reasoning should probably be as follows: take a basis of kernel of $f$, i.e. the $x$'s, and complete it to a basis of $V$ (the part that you add are the $y$'s).
  3. I assume that the $f(y_i)$ form a basis is proven in the remainder. Once you have that you can conclude that the number of $x$'s plus the number of $y$'s is the dimension of $V$ (since all bases have the same cardinality). But the number of $x$'s is the dimension of $\operatorname{ker} f$ while the number of $y$'s is the same as the number of $f(y)$'s of which we will prove that they form a basis of the image of $f$. Hence we will have proven the theorem.
  4. Now let's try to prove that: The first part is to prove that they are linearly independent. So what you do is assuming that there are $\lambda_i$ with $\sum\lambda_i f(y_i)=0$. Then you rewrite that using linearity of $f$ into $f(\sum\lambda_iy_i)=0$. (There seems to be a typo in your question, where it is $x_i$ instead of $\lambda_i$. Now this means that $\sum\lambda_iy_i\in \operatorname{ker}(f)$. Then it should be (again a typo) that $\sum\lambda_iy_i=\sum\alpha_jx_j$ because the $x_j$ span $\operatorname{ker}(f)$. Now that's an element both in the span of the $x$'s and the $y$'s and hence equal to $0$ (we can use 2.) This means that $\sum\lambda_iy_i=0$ and hence $\lambda_i=0$ for all $i$ since $y_i$ forms a basis.
  5. After that we are left with proving that the $f(y_i)$ span the image of $f$. (That's the part that starts with "Then he says") First he starts with noting that for $z\in \operatorname{im}(f)$ there exists $x\in V$ with $f(x)=z$. As you noted this is obvious by definition. Now we write the $x$ in the basis consisting of the $x$'s and the $y$'s. Here is again a typo, it should probably be a $+$ instead of a $-$. Then the last equalities follow from the linearity of $f$. There are again two typos: The scalars in front of the $f(y_i)$ should be $\lambda_i$ instead of $x_i$. Then you get to the equality $z=\sum \lambda_i f(y_i)$. But this means that $z$ is in the span of the $f(y_i)$, hence these span the image of $f$.
share|improve this answer
    
I know they lack precision; that's sort of the point. I want to be sure that I understand something and I am not a mathematician, you know? I'm just trying to get through this class. (Not that the mathematics aren't interesting, but at this point I am desperately trying to get it so I don't fail). That said, thanks for your help -- it helps to see where typos and such are because there's no way for me to know, you know? –  Jesse Jun 23 '13 at 21:07
    
anyhow i think i might need a bit of elaboration on point #2. Are you saying that it should be {0}, the zero vector? –  Jesse Jun 23 '13 at 21:11
    
@Jesse No, not quite, but almost. It should be the zero vector space, i.e. the subspace of $V$ just consisting of the zero vector. –  Julian Kuelshammer Jun 24 '13 at 6:12
    
ok thanks. Understand this was all transcribed as my prof aid it, which is why i said things like "then he says." –  Jesse Jun 24 '13 at 10:51

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.