Learning Calculus II: Limits’ laws for functions and related theorems

2. Limits’ properties and related theorems

We can see that it’s really hard to find the limit of a complex function by using formal definition directly. Hence, here is some limits’ properties and theorems that can be useful in finding limit. Firstly, let’s rewrite definition of limits:

Definition 11 Let {f} be a function defined on an open interval {D} that contains {a}, except possibly at {a}. We say the limit of {f(x)} as {x} approaches {a} is {\ell}, and we write

\displaystyle \lim_{x \rightarrow a}f(x)=\ell

if for every number { \varepsilon>0} there is a number {\delta>0} such that:

if for all {0<|x-a|< \delta} and {x \in D} then {|f(x)-\ell| < \varepsilon}.

2.1. Limit laws for functions

Theorem 12 (Limit laws for functions) Let {f,g} be functions defined on interval {D} that contains {a}. Suppose {f,g} have limit {L,G} at {x=a}. Then

  • (a) {f \pm g} has limit {L \pm G} at {x=a}. We can write

    \displaystyle \lim_{x \rightarrow a}(f \pm g)(x)=\lim_{x \rightarrow a}f(x)+ \lim_{x \rightarrow a}g(x).

  • (b) {\max(f,g)} has limit {\max (L,G)} at {x=a}. Similarly for {\min (f,g)}. We can write

    \displaystyle \lim_{x \rightarrow a} \max (f,g)(x) = \max \left( \lim_{x \rightarrow a} f(x), \lim_{x \rightarrow a} g(x) \right).

  • (c) If {c} is a real number, then {cf} has a limit {cL} at {x=a}. We can write

    \displaystyle \lim_{x \rightarrow a} cf= c \lim_{x \rightarrow a}f(x).

  • (d) {fg} has limit {LG} at {x=a}. We can write

    \displaystyle \lim_{x \rightarrow a} (fg)(x)= \lim_{x \rightarrow a}f(x) \lim_{x \rightarrow a}g(x).

Proof: (a) It suffices to prove {\lim_{x \rightarrow a} (f+g)(x)=L+G}, i.e. according to definition 11 for any {\varepsilon>0} there is {\delta>0} so {|g(x)+f(x)-L-G|<\varepsilon} for all {0<|x-a|<\delta}. We need to use given condition that {\lim_{x \rightarrow a} f(x)=L} and {\lim_{x \rightarrow a}g(x)=G}, i.e. for any {\varepsilon_1, \varepsilon_2} there exists {\delta_1,\delta_2>0} so that {|f(x)-L|<\varepsilon_1} for all {0<|x-a|<\delta_1} and {|g(x)-G| \varepsilon_2} for all {0<|x-a|<\delta_2}. Note that

\displaystyle |f(x)+g(x)-L-G| \le |f(x)-L|+|g(x)-G| <\varepsilon_1+\varepsilon_2.

Hence, we can pick {\varepsilon_1,\varepsilon_2} so that {\varepsilon=\varepsilon_1+\varepsilon_2}. This will follow {|f(x)+g(x)-L-G| <\varepsilon} for all {0<|x-a|< \min (\varepsilon_1,\varepsilon_2)=\delta}. Thus, (a) is proven according to definition 11.

(b) It suffices to prove {\lim_{x \rightarrow a} \max (f,g)(x)=\max (L,G)}. The case where {L=G} is obvious since we can choose {\varepsilon=\varepsilon_1=\varepsilon_2} which follows {| \max (f,g)(x)- L|} equals to either {|g(x)-L|} or {|f(x)-L} which are both less than {\varepsilon} for all {0<|x-a|<\min(\delta_1,\delta_2)}.

WLOG, assume that {L> G}. It suffices to prove that for every {\varepsilon>0} there is a {\delta>0} so {|\max (f,g)(x)-L|<\varepsilon} for all {0<|x-a|<\delta}. In order to do this, we need to bring {\max(f,g)(x)} back to familiar {f,g} where we already knew the limits. Hence, we can pick {\varepsilon_1,\varepsilon_2} so that {g(x)<f(x)} for {x} in some interval {T} to get {\max (f,g)(x)=f(x)} in that interval. Indeed, note that according to definition 11 then {g(x)<G+\varepsilon_2} for all {0<|x-a|<\delta_2} and {f(x)>L-\varepsilon_1} for all {0<|x-a|<\delta_1}. Therefore, we can choose {\varepsilon_1,\varepsilon_2} so {G+ \varepsilon_2<L-\varepsilon_1} or {0<\varepsilon_2+\varepsilon_1<L-G}, which is possible since {L>G}. Hence, for all {0<|x-a|<\min(\delta_1,\delta_2)} then {g(x)<f(x)}.

Therefore, for all {\varepsilon<L-G}, we can pick {\varepsilon_1=\varepsilon} and {\varepsilon_2} so {\varepsilon_2+\varepsilon_1<L-G}. With this, for all {x} so {0<|x-a|<\delta=\min (\delta_1,\delta_2)} then {\max (f,g)(x)=f(x)} so

\displaystyle |\max (f,g)(x)-L|=|f(x)-L|< \varepsilon_1=\varepsilon.

According to definition 11, {\lim_{x \rightarrow a} \max(f,g)(x)=L} for {L>G}.

(c) If {c=0} then it’s obvious. We only need to consider {c \ne 0}. It suffices to prove {\lim_{x \rightarrow a }cf = cL}, i.e. for any {\varepsilon>0} there exists {\delta>0} so {|cf(x)-cL|<\varepsilon} for all {0<|x-a|<\delta}. Pick {\varepsilon_1= \frac{\varepsilon}{|c|}} then since {\lim_{x \rightarrow a}f(x)=L} so for {\varepsilon_1=\frac{\varepsilon}{|c|}>0} there exists {\delta>0} so {|f(x)-L|< \frac{\varepsilon}{|c|}} or {|cf(x)-cL|<\varepsilon} for all {0<|x-a|<\delta}. We are done.

(d) It suffices to prove {\lim_{x \rightarrow a}(fg)(x)=LG}, i.e. for any {\varepsilon>0} there exists {\delta>0} so {|f(x)g(x)-LG|<\varepsilon} for all {0<|x-a|<\delta}. We need to use condition {\lim_{x \rightarrow a}f(x)=L} and {\lim_{x \rightarrow a}g(x)=G} to imply this, i.e. {|f(x)-L|<\varepsilon_1} for all {0<|x-a|<\delta_1} and {|g(x)-G|<\varepsilon_2} for all {0<|x-a|<\delta_2}. We need to apear {|f(x)g(x)-LG|} from {|f(x)-L|} and {|g(x)-G|}, so we can multiply the two to get

\displaystyle |f(x)g(x)-Gf(x)-Lg(x)+LG|=|f(x)-L| \cdot |g(x)-G|<\varepsilon_1\varepsilon_2.

Note that

\displaystyle |f(x)g(x)-LG|-|Gf(x)+Lg(x)-2LG| \le |f(x)g(x)-Gf(x)-Lg(x)+LG|.

Hence,

\displaystyle |f(x)g(x)-LG|<\varepsilon_1\varepsilon_2+|Gf(x)+Lg(x)-2LG|.

Now we have {|f(x)g(x)-LG|}, the next thing is to manipulate the {RHS} so that {\varepsilon_1,\varepsilon_2} can be easily choosen to make {RHS} arbitrary small. Indeed, we have

\displaystyle |Gf(x)+Lg(x)-2LG| \le |Gf(x)-LG|+|Lg(x)-LG|<|G|\varepsilon_1+|L|\varepsilon_2.

From this, we find

\displaystyle   |f(x)g(x)-LG|<\varepsilon_1\varepsilon_2+|G|\varepsilon_1+|L|\varepsilon_2. \ \ \ \ \ (2)

From here {\varepsilon_1,\varepsilon_2} can be easily chosen so that {\varepsilon_1\varepsilon_2+|G|\varepsilon_1+|L|\varepsilon_2=\varepsilon} for any {\varepsilon>0}. Thus, by choosinng {\delta= \min (\delta_1,\delta_2)}, we find that (2) is true for all {0<|x-a|<\delta}. According to definition 11, we are done. \Box

A remark that in order to use above limit laws, we need a condition that {\lim_{x \rightarrow a}f(x)} and {\lim_{x \rightarrow a}g(x)} to be defined or else the limit laws will not work. Evidently, we can see that all of the proofs represented above use the condition that {\lim_{x \rightarrow a}f(x)} and {\lim_{x \rightarrow a}g(x)} are defined to prove the limit laws. Intuitively, if {\lim_{x \rightarrow a}f(x)} or {\lim_{x \rightarrow a}g(x)} are not defined then obviously we can’t calculate {\lim_{x \rightarrow a}(f \pm g)(x), \lim_{x \rightarrow a} (fg)(x), \ldots} from {\lim_{x \rightarrow a}f(x),\lim_{x \rightarrow a}g(x)}.

Theorem 12 is missing one more limit law, which is limit of division:

\displaystyle   \lim_{x \rightarrow a} (f/g)(x)= \frac{ \lim_{x \rightarrow a} f(x)}{\lim_{x \rightarrow a}g(x)} \ \ \ \ \ (3)

What condition of {f(x),g(x)} can we use (3)? Simiarly to above argument, of course {\lim_{x \rightarrow a}f(x)} and {\lim_{x \rightarrow a}g(x)} must be defined. But is that condition good enough to use (3)? Notice that in (3) we have division by {\lim_{x \rightarrow a}g(x)} so one more condition need to be added is {\lim_{x \rightarrow a}g(x) \ne 0} in order to calculate RHS of (3). Hence, we obain the following theorem:

Theorem 13 Let {f,g} be functions defined on interval {D} that contains {a}. Suppose {f,g} have limit {L,G} at {x=a}, respectively and {\lim_{x \rightarrow a}g(x) \ne 0}. Then

\displaystyle \lim_{x \rightarrow a} \left( \frac fg \right) (x)= \frac{ \lim_{x \rightarrow a} f(x)}{\lim_{x \rightarrow a}g(x)}.

With {\lim_{x \rightarrow a}g(x) \ne 0} we guarantee that RHS of (3) can be calculated. Can {\lim_{x \rightarrow a}g(x) \ne 0} guarantee that limit {\lim_{x \rightarrow a} (f/g)(x)} in LHS of (3) satisfy prerequisit condition for a limit to be defined, i.e. the function {f/g} must be defined on some interval containing {a} except possibly at {a} (see definition 11)? Yes, it can. We can show that {\lim_{x \rightarrow a}g(x) \ne 0} is equivalent to {g(x) \ne 0} for all {x \in (a-\varepsilon,a+\varepsilon) \subset D}. Indeed, if {\lim_{x \rightarrow a}g(x)=G} then for any {0<\varepsilon<|G|} there exists {\delta >0} so {|g(x)-G|<\varepsilon} for all {0<|x-a|<\delta}. With this, if there exists {x \in (a-\delta,a+\delta)} so {g(x)=0} then {|g(x)-G|=|G|>\varepsilon}, a contradiction. Thus, for all {x \in (a-\delta,a+\delta)} then {g(x) \ne 0}. The reverse is also true. Hence,

{\lim_{x \rightarrow a}g(x) \ne 0 \iff g(x) \ne 0} for all {x \in E} with {E \subset D} and {E} contains {a}.

Combining this with condition that {f} is defined on {D}, we find {f/g} is defined on {E \subset D}. Thus, the prerequisit condition is satisfied. Hence, we now understand why {\lim_{x \rightarrow a}g(x) \ne 0} is added to the theorem’s condition. We also know that we can replace condition {\lim_{x \rightarrow a}g(x) \ne 0} with {g(x) \ne 0} for {x \in E \subset D} with {E} contains {a}.

Now, let’s try and prove theorem 13.

Proof: If we look at the proof of theorem 12 (d) and try to use the similar idea, we see that it would be harder to manipulate {|f(x)-L|<\varepsilon_1} and {|g(x)-G|<\varepsilon_2} to bring back {\left| \frac{f(x)}{g(x)}- \frac LG \right|<\varepsilon}. Instead, we can prove {\lim_{x \rightarrow a} \frac{1}{g(x)} = \frac{1}{G}} and then use theorem 12 (d) to say

\displaystyle \lim_{x \rightarrow a} \left( \frac{f}{g} \right) (x) = \lim_{x \rightarrow a} \frac{1}{g(x)} \cdot \lim_{x \rightarrow a} f(x) = \frac{L}{G}.

We can see that proving {\lim_{x \rightarrow a} \frac{1}{g(x)} = \frac{1}{G}} is a much easier job. Indeed, note that in above argument, we find that {\frac{1}{g(x)}} is defined on {E} containing {a}. Since {\lim_{x \rightarrow a}g(x)=G}, we consider an {\varepsilon_2>0} so {|g(x)-G|< \varepsilon_2} for all {0<|x-a|<\delta_2}. We have {G-\varepsilon_2<g(x)<G+\varepsilon_2} and note that {G} can be negative number. We notice that {|g(x)|>|G|-\varepsilon_2} for any {\varepsilon_2<|G|} from this. Hence, for all {0<|x-a|<\varepsilon_2} then

\displaystyle  \left| \frac{1}{g(x)}-\frac{1}{G} \right| = \left| \frac{G-g(x)}{Gg(x)} \right|< \frac{\varepsilon_2}{ |G| ( |G| -\varepsilon_2)}.

Let’s just write {\frac{\varepsilon_2}{ |G| ( |G| -\varepsilon_2)}= \varepsilon} then {\varepsilon_2= \frac{G^2\varepsilon}{1+\varepsilon|G|}<|G|}. Thus, we can find {\varepsilon_2} from any {\varepsilon>0}. Therefore, for any {\varepsilon>0} then { \left| \frac{1}{g(x)}-\frac{1}{G} \right| < \varepsilon} for all {0<|x-a|<\delta_2, x \in E}. This follows {\lim_{x \rightarrow a} \frac{1}{g(x)}= \frac{1}{G}}. From this and theorem 12, we obtain the desired result. \Box

2.2. Left, right limit theorem

Theorem 14 Given function {f} defined on {D} containing {A} except possibly at {a}. We have {\lim_{x \rightarrow a^-}f(x)} and {\lim_{x \rightarrow a^+}f(x)} exist and {\lim_{x \rightarrow a^-}f(x)= \lim_{x \rightarrow a^+}f(x)=\ell} if and only if {\lim_{x \rightarrow a}f(x)=\ell}.

The proof for this theorem can be obtained directly from definition 5 of one-side limits.

2.3. Squeeze theorem

Theorem 15 (Squeeze theorem) Given functions {f,g,h} defined on {D} containing {a} except possibly at {a} so that {g(x) \le f(x) \le h(x)} for all {x \in D\setminus \{ a\}}. If {\lim_{x \rightarrow a}g(x)= \lim_{x \rightarrow a}h(x)= \ell} then {\lim_{x \rightarrow a} g(x)=\ell}.

Proof: This is straight off from definition. For any {\varepsilon >0} there exists {\delta_1,\delta_2>0} so {\ell-\varepsilon<g(x)<\ell+\varepsilon} for all {0<|x-a|<\delta_1} and {\ell_\varepsilon<h(x)<\ell+\varepsilon} for all {0<|x-a|<\delta_2}. Hence, we find for any {\varepsilon>0} then

\displaystyle \ell-\varepsilon< g(x) \le f(x) \le h(x) <\ell+\varepsilon

for all {0<|x-a|<\min \{ \delta_1,\delta_2 \}}. This follows {\lim_{x \rightarrow a}f(x)=\ell}. \Box

Let’s go through a classic example using Squeeze theorem:

Problem 1 Prove that {\lim_{x \rightarrow 0} \frac{\sin (x)}{x}=1}.

Geometric solution combining eith Squeeze theorem for this problem can be found on this link. In there, they provide two different geometric approaches to establish the bound

\displaystyle \cos (x) \le \frac{\sin (x)}{x} \le 1.

One solution use areas and the other use comparison between lengths in unit circle. The second solution points out that the limit explicitly depends on {x} being measured in radians.

2.4. Squeeze theorem for limits involving {\log} or {e^x}

When the limit involves with {\log} or {e^x}, we often think of L’Hopital’s Rule. However, we can also use Squeeze theorem to prove some limits of this type. In particular, we need to know two inequalities

\displaystyle \frac{x-1}{x}\le\log(x)\le x-1

for {x>0} and

\displaystyle 1+x\le e^x\le \frac{1}{1-x}

for {x<1}. These was introduced by Mark Viola (Dr. MV) in Math Stack Exchange. Check this problem and this problem if you want to try using those inequalities to find limits.

Posted in Calculus, Mathematics | Tagged , , , | Leave a comment

Learning Calculus I: Definitions of limits

I am learning calculus now I want to type up everything I now about this subject. All solutions written below, if no source is mentioned, are my solutions so if someone find an error in the solutions, please tell me. By the way, thanks to Luca Trevisan’s LaTeX to WordPress, I now don’t have to write LaTeX in WordPress format anymore, which is very convenient.

1. Definition of limits

1.1. Definition of limits of function

For me, the precise definition of limits is a bit hard to understand so I decided to reconstruct the whole thing by writing some of my guesses on why did mathematicians write the definition in this way. By the way, French mathematician, Augustin-Louis Cauchy (1789-1857) is the one who introduced {\delta, \varepsilon} into definition of limits.

Limit, the notation {\lim_{x \rightarrow a}f(x)=\ell} is understood vaguely as: as {x} gets closer to {a}, {f(x)} gets closer to a number {\ell}. What does it mean by ‘get closer’? It is easier to understand if we imagine {a} lies on a number line and suppose we pick an arbitrary point {x} on the line. If we apply the term ‘{x} gets closer to {a}‘, we can understand it as distance from {x} to {a} on the number line decreases. Its distance is {|x-a|} so saying {x} gets closer to {a} is the same as saying {|x-a|} gets closer to {0}. Note that for any distance {|x-a|}, there are two possible {x} on the number line that can satisfy that distance. What we care about is the distance from {x} to {a} not the position of {x}, so using ‘{|x-a|} gets closer to {0}‘ is better than ‘{x} gets closer to {a}‘. Similarly to {|f(x)-\ell|} and we get a new definition:

Definition 1 The symbol {\lim_{x \rightarrow a}f(x)=\ell} means that as {|x-a|} gets closer to {0} then {|f(x)-\ell|} gets closer to {0}.

Note that we can get {|x-a|} as close to {0} as we want by choosing appropriate {x}, but we can’t guarantee the same thing for {|f(x)-\ell|} since {f(x)} depends on {x}. Thus, firsly, in order for {|f(x)-\ell|} to be able to approach {0} we need {|f(x)-\ell|} to be as small as we want. It is equivalent to saying:

For any {\varepsilon>0} there exists some {x} so {\varepsilon>|f(x)-\ell|}.

Secondly, we need the definition to say {|f(x)-\ell|} approaches {0} as {|x-a|} approaches {0}. This means for small enough {\delta}, {|f(x)-\ell|} must be bounded by some {\varepsilon} for all {|x-a|<\delta}. For better understanding more about this argument, let’s assume the contrary, then as {\delta} gets closer to {0}, {|f(x)-\ell|} still does not have a bound for all {|x-a|<\delta}. Say we find at {|x-a|=\delta_1<\delta} has {|f(x)-\ell |=M_1}. We consider all {x} in {|x-a|<\delta_1} and follow that there must be an {x} so {|x-a|=\delta_2<\delta_1} and {|f(x)-\ell|=M_2>M_1} according to the assumption. Next consider all {x} in {|x-a| < \delta_2} and from our assumption, there exists {x} so {|f(x)-\ell |=M_3>M_2} for {|x-a|=\delta_3<\delta_2}. This keeps going and we can see that as {|x-a|} gets closer to {0}, {|f(x)-\ell |} gets larger, which contradicts to our aim that {f(x)} must approaches {\ell}. Thus, we got the second part of the definition: Continue reading

Posted in Calculus, Mathematics | Tagged , , | Leave a comment

LA I: Identify a list of vectors linearly dependent or linearly independent, a vector space infinite-dimensional or finite-dimensional

Inspired from some good exercises from Chapter 2A in the book Linear Algebra Done Right by Sheldon Axler.
First, let’s write out definition of linearly (in)dependent list:

Definition 1 (Linearly independence) A list of {v_1, \ldots, v_m} of vectors in {V} is called linearly independent if the only choice of {a_1, \ldots, a_m \in \mathbf{F}} so {a_1v_1+ \ldots+ a_mv_m=0} is {a_1=a_2= \ldots =a_m=0}.

The definition itself can be applied for linearly (in)dependent test. Also from this, we find

Proposition 2 Every vector in the span of linearly independet list {v_1, \ldots, v_m} can be represented uniquely as {a_1v_1+ \ldots + a_mv_m}.

Proof: Indeed, assume the contrary that {v=a_1v_1+ \ldots +a_mv_m=b_1v_1+ \ldots+b_mv_m} with {a_i} not all equal to {b_i}. Hence,

\displaystyle (a_1-b_1)v_1+(a_2-b_2)v_2+ \ldots + (a_m-b_m)v_m=0,

with {a_i-b_i} not all equal to {0}. This contradicts to our definition. \Box

This proposition doesn’t help us much in testing linearly (in)dependence. But the below proposition, which is also deduced from the definition, has better application in testing, simply by looking at the list of vectors:

Proposition 3 If some vector in a list of vectors in {V} is a linear combination of the other vectors, then the list is linearly dependent, i.e. list that is not linearly independent.

Proof: List {v_1, \ldots, v_m} has {v_1= \sum_{i}a_iv_i} then {v_1-\sum_ia_iv_i=0}, or there exists {x_1, \ldots, x_m} not all {0} so {\sum_{i=1}^mx_iv_i=0}. Hence, {v_1, \ldots, v_m} is linearly dependent. \Box

From this, we develop (in)finite-dimensional test for vector space:

Proposition 4 (Ex 14,2A) {V} is infinite-dimensional if and only if there is a sequence {v_1,v_2, \ldots} of vectors in {V} such that {v_1,v_2, \ldots, v_m} is linearly independent for every positive integer {m}.

Proof: If {V} is infinite-dimensional: Pick {v_1 \in V}, pick {v_i} so {v_i \in V, v_i \not\in \text{span}(v_1, \ldots, v_{i-1})}. Such {v_i} exists, otherwise any {v \in V} must also in {\text{span}(v_1, \ldots, v_{i-1})} so {V \subseteq \text{span}(v_1, \ldots, v_{i-1})} and we also have {\text{span}(v_1, \ldots, v_{i-1}) \subseteq V} so a finite list of vectors span {V}, a contradiction. Note that since {v_1, \ldots, v_{i-1}} is linearly independent and {v_i \not\in \text{span}(v_1, \ldots, v_{i-1})} so by Proposition 3 then {v_1, \ldots , v_i} is linearly independent. By continuing the process, we can construct such sequence of vectors. \Box

Two examples taken from the book use Proposition 4 to solve:

Problem 1 Prove that {\mathbf{F}^{\infty}} is infinite-dimensional.

Proof: With {\mathbf{F}^{\infty}}, consider the sequence {(1,0, \ldots),(0,1,0, \ldots),(0,0,1,0,\ldots), \ldots} then from Exercise 4, we follow {\mathbf{F}^{\infty}} is infinite-dimensional. \Box

Problem 2 Prove that the real vector space of all continuous real-valued functions on the interval {[0,1]} is infinite-dimensional.

Proof: Consider sequence of continuous real-valued functions defined on {[0,1]}: {1,x,x^2,x^3, \ldots} and we are done. \Box

1.1. Steinitz exchange lemma

From Proposition 3, we can also deduce to following lemma.

Theorem 5 (Linear Dependence Lemma) Suppose {v_1, \ldots, v_m} is linearly dependent list in {V}. There exists {j \in \{1,2, \ldots, m \}} such that the following holds:

  1. (a) {v_j \in \text{span}(v_1, \ldots, v_{j-1})}.
  2. (b) if the {j}th term is removed from {v_1, \ldots, v_m}, the span of the remaining list equals {\text{span}(v_1, \ldots, v_m)}.

Condition {(b)} can be followed from {(a)}. And from this lemma, we can prove Steinitz exchange lemma, which gives a bound for length of linearly independent list in finite-dimensional vector space.

Theorem 6 (Steinitz exchange lemma) In a finite-dimensional vector space, the length of every linearly independent list of vector is less than or equal to the length of every spanning list of vectors.

This theorem is also called as Steinitz exchange lemma or Replacement’s theorem. Here is my proof for this theorem.
Proof: Let {v_1,v_2, \ldots, v_m} is linearly independent list and {u_1,u_2, \ldots , u_n} is spanning list of vectors. It suffices to prove for the case that {u_1, u_2, \ldots , u_n} is also linearly independent, otherwise if {u_1,u_2, \ldots , u_n} is linearly dependent, according to Linear Dependence Lemma (2.21), we can take out some vectors from the list without changing the span and bring back to linearly independent list. Assume the contrary that {n<m} and from this assumption, we will prove that list {v_1, \ldots , v_m} is linearly dependent.

Since {u_1, u_2, \ldots , u_n} spans {V} and is also linearly independent so for each {v_i}, there exists unique {c_{i1},c_{i2}, \ldots , c_{in} \in \mathbf{F}} so {v_i=c_{i1}u_1+c_{i2}u_2+ \ldots + c_{in}u_n}. Hence, for {a_1, \ldots , a_m \in \mathbf{F}}, we have

\displaystyle a_1v_1+a_2v_2+ \ldots + a_mv_m= u_1\sum_{i=1}^ma_ic_{i1}+u_2\sum_{i=1}^ma_ic_{i2}+ \ldots +u_n\sum_{i=1}^ma_ic_{in}.

We will show that there exists {a_1, \ldots , a_m} not all {0} so {a_1v_1+ \ldots + a_mv_m=0}. Since {u_1, \ldots , u_n} is linearly independent so form the above, we follow

\displaystyle a_1v_1+ \ldots +a_mv_m=0 \iff \begin{cases} a_1c_{11}+a_2c_{21}+ \ldots + a_mc_{m1}=0, \\ a_2c_{12}+a_2c_{22}+ \ldots + a_mc_{m2}=0, \\ \qquad \qquad \qquad \ldots \\ a_mc_{1n}+a_2c_{2n}+ \ldots +a_mc_{mn}=0.\ \end{cases} \ \ \ \ \ (1)

This system of equation has {m} variable and {n} equation with {n<m}. Here is an algorithm in finding non-zero solution for {a_1, \ldots, a_m}. Number the equations in (1) from top to bottom as {(11),(12), \ldots, (1n)}.

  1. For {1 \le i \le m-1}, get rid of {a_m} in {(1i)} by subtracting to {(1(i+1))} times some constant. By doing this, we obtain a system of equations where the first {n-1} equations only contain {m-1} variables, the last equation contains {m} variables.
  2. For {1 \le i \le m-2}, get rid of {a_m} in {(1i)} by subtracting to {(1(i+1))} times some constant. We obtain an equivalent system of equations where the first {n-2} equations contain {m-2} variables, equation {(1(n-1))} contains {m-1} variables and and equation {(1n)} contains {m} variables.
  3. Keep doing this until we get an system of equation so that the {(1i)} equation contains {m-n+i} variables.
  4. Starting from equation {(11)} with {m-n+1} variables {a_1, \ldots , a_{m-n+1}}, we can pick {a_1, \ldots , a_{m+n-1}} so that it satisfies equation {(11)} and {a_1, \ldots , a_{m-n+1}} not all {0}, which is possible since {m \ge n+1}.
  5. Come to {(12)} and pick {a_{m-n+2}}, to {(13)} and pick {a_{m-n+3}} until to {(1n)} and pick {a_m}.

Thus, there exists {a_1, \ldots a_m} not all {0} so that {a_1v_1+ \ldots + a_mv_m=0}, a contradiction since {v_1, \ldots , v_m} is linearly independent. Hence, we must have {n \ge m}. We are done. \Box

From this proof, we can see that this theorem relates to system of linear equation. The textbook has mush better solution.

1.2. Applications of Steinitz exchange lemma

From this Steinitz exchange lemma, we can prove a theorem about finite dimentional subspaces

Theorem 7 (2.26 Finite dimensional subspaces) Every subspace of a finite-dimensional vector space is finite-dimensional.

Proof: Let {V=\text{span}(v_1,v_2, \ldots , v_m)} be a finite-dimensional vector space and {U} be its subspace. Among vectors in the spanning list {v_1,v_2, \ldots, v_m}, let {u_1,u_2, \ldots u_n} be vectors that are in subspace {U}, {k_1,k_2, \ldots , k_{m-n}} be vectors that are not in {U}. If {U=\text{span}(u_1,u_2, \ldots, u_n)} then we are done. If not, then there exists {\ell \in U} so {\ell \not\in \text{span}(u_1,u_2, \ldots , u_n)}. Hence, since {\ell \in \text{span}(v_1, \ldots , v_m)} so

\displaystyle \displaystyle \ell =\sum_{i=1}^nu_ia_i+\sum_{j=1}^{m-n}k_ib_i

for {a_i,b_i \in \mathbf{F}} and there exists {b_i \; (1 \le i \le m-n)} so that {b_i \ne 0}. Since {u_i,\ell \in U} so that means {\displaystyle h_1= \sum_{i=1}^{m-n}k_ib_i \in U} and also in {\text{span}(k_1, \ldots , k_{m-n})} and {h_1 \ne 0}. We add {h_1} to the list {h_1,u_1,u_2, \ldots , u_n} in {U}. Similarly, we compare {U} and {\text{span}(h_1,u_1, \ldots ,u_n)} and may add another {h_2 \in \text{span}(k_1,k_2, \ldots , k_{m-n})} onto the list. This process will keep going until we obtain a spanning list of {U}. We will prove that after adding at most {m-n} such {h_i}, we can get {U=\text{span}(h_1,h_2, \ldots , h_{j},u_1, \ldots , u_n)} with {j \le m-n}.

Indeed, assume the contrary that after adding at least {m-n} such {h_i \in U} so {h_i \ne 0}, we still can’t obtain a list of vectors that spans {U}. That means there exists {\ell \in U} and {\ell \notin \text{span}(h_1, \ldots , h_{m-n},u_1, \ldots , u_n)}. Similarly, we can construct another {,h_{m+n-1} \ne 0, h_{m-n+1} \in U} and {h_{m-n+1} \in \text{span}(k_1, \ldots , k_{m-n})} based on {\ell}. Let {h_i=c_{i1}k_1+c_{i2}k_2+ \ldots + c_{i,m-n}k_{m-n}} then we have

\displaystyle \begin{array}{rcl} & a_1h_1+ \ldots + a_{m-n+1}h_{m-n+1}=k_1 \\ \iff & \begin{cases} a_1c_{1,1}+a_2c_{2,1}+ \ldots + a_{m-n+1}c_{m-n+1,1}=1, \\ a_1c_{1,2}+a_2c_{2,2}+ \ldots + a_{m-n+1}c_{m-n+1,2}=0, \\ \qquad \qquad \qquad \ldots \\ a_1c_{1,m-n}+ \ldots +a_{m-n+1}c_{m-n+1,m-n}=0. \end{cases} \end{array}

This is a system of {m-n} equations with {m-n+1} variables {a_1, \ldots , a_{m-n+1} \in \mathbf{F}} so similarly to Theorem 6‘s proof, there are infinite number of {a_i} so {a_1h_1+ \ldots +a_{m-n+1}h_{m-n+1}=k_1}. Since {h_i \in U} so {k_1 \in U}, a contradiction. Thus, there are at most {m-n} such {h_i \in U \; (1 \le i \le j)} so that there does not exist {\ell \in U} but {\ell \notin \text{span}(h_1, \ldots , h_j,u_1,\ldots ,u_n)}. Note that {\text{span}(h_1, \ldots , h_j,u_1,\ldots ,u_n) \subseteq U} so this can only mean {U= \text{span}(h_1, \ldots , h_j,u_1,\ldots ,u_n)}. Thus, {U} is a finite-dimensional vector space. \Box

Remark 1 Both my proofs for the two theorems use the result that a system of {m} equations with {n} variables in {\mathbf{R}} with {m<n} has infinite solution in {\mathbf{R}}.

Back to the focus of this post, let me show how Steinitz exchange lemma can identify a particular list of vectors linearly (in)dependent. Problems below are taken from exercises in Sheldon Axler’s book.

Problem 3 Explain why there does not exist a list of six polynomials that is linearly independent in {\mathcal{P}_4(\mathbf{F})}.

Proof: Because {\mathcal{P}_4(\mathbf{F})=\text{span}(1,x,x^2,x^3,x^4)} and from Theorem 6 (2.23) length of any linearly independent list is less than length of a spanning list {1,x,x^2, x^3,x^4}, which is {5}. That explains why we can’t have {6} polynomials that is linearly independent in {\mathcal{P}_4(\mathbf{F})}. \Box

Problem 4 Explain why no list of four polynomials spans {\mathcal{P}_4(\mathbf{F})}.

Proof: Because {1,x,x^2,x^3,x^4} is a linearly independent list of length {5} in {\mathcal{P}_4(\mathbf{F})} and according to Theorem 6 (2.23) length of any spanning list is greater than or equal to length of a linearly independent list, which is {5}. Thus, we can’t have four polynomials that spans {\mathcal{P}_4(\mathbf{F})}. \Box

Problem 5 Suppose {p_0,p_1, \ldots, p_m} are polynomials in {\mathcal{P}_m(\mathbf{F})} such that {p_j(2)=0} for each {j}. Prove that {p_0,p_1, \ldots, p_m} is not linearly independent in {\mathcal{P}_m(\mathbf{F})}.

Proof: Nice problem. Since {p_j(2)=0} for each {j} so that means {x-2} divides each {p_j}. Let {q_i=\frac{p_i}{x-2}} then {q_0,q_1, \ldots , q_m} are polynomials in {\mathcal{P}_{m-1}(\mathbf{F})}. If {q_0,q_1, \ldots, q_m} is linear independent but it has length {m+1} larger than length {m} of spanning list in {\mathcal{P}_{m-1}(\mathbf{F})}, a contradiction according to Theorem 6. Thus, {q_0,q_1, \ldots, q_m} is linear dependent. That means there exists {a_i \in \mathbf{F}} not all {0} so {\sum_{i=0}^ma_iq_i=0}. This follows {(x-2)\sum_{i=0}^ma_iq_i=0} or {\sum_{i=0}^m a_ip_i=0}. Hence, {p_0, \ldots, p_m} is linearly dependent. \Box

Posted in Linear Algebra, Mathematics | Tagged , , | Leave a comment

Reading a solution using algebraic integers of a HMMT number theory problem

I tried to attack the following problem but eventually gave up.

Problem 1 (HMMT Ferb 2015 Team P9) Let {z=e^{\tfrac{2\pi i}{201}}} and {\omega= e^{\tfrac{2 \pi i}{10}}}. Prove that

\displaystyle A=\displaystyle \prod_{a=0}^{9}\prod_{b=0}^{100}\prod_{c=0}^{100}(\omega^a+z^b+z^c)

is an integer and find its remainder upon division by {101}

The only idea I have is to expand this expression, but it was too complex to do. So I decided to read the solution using algebraic integers. I’m new at algebraic number theory and I don’t know much about algebraic integers. My only reference is Problems from the book (PFTB), Chapter 9.

Continue reading

Posted in Number Theory, Olympiad Math | Tagged , , , | Leave a comment

Yellowstone Permutation – St. Petersburg MO 2015, grade 9, 2nd round

This problem was given to the St. Petersburg Olympiad 2015, 2nd round, grade 9 and is known as Yellowstone Permutation. You can see here for the article about this sequence and here for the OEIS entry.

Problem. (Yellowstone Permutation) A sequence of integers is defined as follows: a_1=1,a_2=2,a_3=3 and for n>3, a_n is the smallest integer not occurring earlier, which is relatively prime to a_{n-1} but not relatively prime to a_{n-2}. Prove that every natural number occurs exactly once in this sequence.

M. Ivanov

Here is my proof for this interesting problem. Another proof can be found in the article given link above.

Continue reading

Posted in Number Theory, Olympiad Math | Tagged , , | Leave a comment

The normal approximation to the binomial distribution

A coin is flipped n times with probability of getting heads is p. This is a binomial approximation X \sim B(n,p). The Year 12 MATH B textbook gives an normal approximation to this: B(n,p) \sim N(np,np(1-p))=N(\mu, \sigma^2) where \mu=E[X] is the mean (or expected value) and \sigma is the standard deviation. Since the textbook doesn’t give a proof for this so I will go and prove.

Continue reading

Posted in Combinatorics, Olympiad Math | Tagged , , , , | Leave a comment

IMO 2016

IMO 2016 was held from 6/7/2016 to 16/07/2016. Although I didn’t attend this, I just want to post my solutions and how I think about the difficulty of the problems, which can be found here. I will post my solutions on this post. Many awesome solutions can be found on AoPS.

Continue reading

Posted in Contests, Olympiad Math | Tagged , , , | 1 Comment