14-240/Tutorial-October14

DBN: Classes: 2014-15: 14-240 / Navigation Welcome to Math 240! (additions to this web site no longer count towards good deed points) # Week of... Notes and Links 1 Sep 8 About This Class, What is this class about? (PDF, HTML), Monday, Wednesday 2 Sep 15 HW1, Monday, Wednesday, TheComplexField.pdf,HW1_solutions.pdf 3 Sep 22 HW2, Class Photo, Monday, Wednesday, HW2_solutions.pdf 4 Sep 29 HW3, Wednesday, Tutorial, HW3_solutions.pdf 5 Oct 6 HW4, Monday, Wednesday, Tutorial, HW4_solutions.pdf 6 Oct 13 No Monday class (Thanksgiving), Wednesday, Tutorial 7 Oct 20 HW5, Term Test at tutorials on Tuesday, Wednesday 8 Oct 27 HW6, Monday, Why LinAlg?, Wednesday, Tutorial 9 Nov 3 Monday is the last day to drop this class, HW7, Monday, Wednesday, Tutorial 10 Nov 10 HW8, Monday, Tutorial 11 Nov 17 Monday-Tuesday is UofT November break 12 Nov 24 HW9 13 Dec 1 Wednesday is a "makeup Monday"! End-of-Course Schedule, Tutorial F Dec 8 The Final Exam Register of Good Deeds Add your name / see who's in!

Boris

Elementary and (Not So Elementary) Errors in Homework

(1) Bad Notation

Consider these three matrices:

[math]\displaystyle{ M_1 = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, M_2 = \begin{pmatrix} 0 & 0 \\ 0 & 1 \\ \end{pmatrix}, M_3 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} }[/math]

We want to equate [math]\displaystyle{ span(M_1, M_2, M_3) }[/math] to the set of all symmetric [math]\displaystyle{ 2 \times 2 }[/math] matrices. Here is the wrong way to write this:

[math]\displaystyle{ span(M_1, M_2, M_3) = \begin{pmatrix} a & b \\ b & c \\ \end{pmatrix} }[/math].

Firstly, [math]\displaystyle{ span(M_1, M_2, M_2) }[/math] is the set of all linear combinations of [math]\displaystyle{ M_1, M_2, M_3 }[/math]. To equate it to a single symmetric [math]\displaystyle{ 2 \times 2 }[/math] matrix makes no sense. Secondly, the elements [math]\displaystyle{ a, b, c, d }[/math] are undefined. What are they suppose to represent? Rational numbers? Real numbers? Members of the field of two elements? The following way of writing erases those issues:

[math]\displaystyle{ span(M_1, M_2, M_3) = \{ \begin{pmatrix} a & b \\ b & c \\ \end{pmatrix} :a, b, c \in F \} }[/math] where [math]\displaystyle{ F }[/math] is an arbitrary field.

(2) Algorithm vs. Proof (Boris's Section Only)

When solving a problem that requires a solution to a linear equation, it is not always obvious which of the following you should show:

a) An algorithm for finding the solution

b) A proof that a solution is correct

If the problem asks to solve a linear equation, then just show (a). Otherwise, consider problems such as this:

Determine if the vector [math]\displaystyle{ (-2, 2, 2) }[/math] is a linear combination of the vectors [math]\displaystyle{ (- (1, 2, -1), (-3, -3, 3) }[/math] in [math]\displaystyle{ R^3 }[/math].

Show both (a) and (b) to be on the safe side.

Problem 5h) on Page 34 in Homework 3 for all Fields

For an arbitrary field [math]\displaystyle{ F }[/math], determine if the matrix [math]\displaystyle{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} }[/math] is in span [math]\displaystyle{ S=\{ \begin{pmatrix} 1 & 0 \\ -1 & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 1 \\ \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 0 \\ \end{pmatrix} \} }[/math].

Proof:

We show that [math]\displaystyle{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \in span(S) \iff char(F)=2 }[/math].

We show that [math]\displaystyle{ char(F)=2 \implies \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \in span(S) }[/math].

Assume that [math]\displaystyle{ char(F)=2 }[/math].

Let [math]\displaystyle{ c_1=0, c_2=1, c_3=1 }[/math].

Then [math]\displaystyle{ c_1, c_2, c_3 \in F }[/math].

Then [math]\displaystyle{ c_1 \begin{pmatrix} 1 & 0 \\ -1 & 0 \\ \end{pmatrix} + c_2 \begin{pmatrix} 0 & 1 \\ 0 & 1 \\ \end{pmatrix} + c_3 \begin{pmatrix} 1 & 1 \\ 0 & 0 \\ \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ \end{pmatrix} }[/math].

Since [math]\displaystyle{ char(F)=2 }[/math] and the entries of the matrix are from [math]\displaystyle{ F }[/math], then [math]\displaystyle{ 0=2 }[/math].

Then [math]\displaystyle{ \begin{pmatrix} 1 & 2 \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \in span(S) }[/math].

Then [math]\displaystyle{ char(F)=2 \implies \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \in span(S) }[/math].

We show that [math]\displaystyle{ char(F) \neq 2 \implies \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \notin span(S) }[/math].

Assume to the contrary that [math]\displaystyle{ char(F) \neq 2 \and \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \in span(S) }[/math].

Then [math]\displaystyle{ \exists c_1, c_2, c_3 \in F, \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} =c_1 \begin{pmatrix} 1 & 0 \\ -1 & 0 \\ \end{pmatrix} +c_2 \begin{pmatrix} 0 & 1 \\ 0 & 1 \\ \end{pmatrix} +c_3 \begin{pmatrix} 1 & 1 \\ 0 & 0 \\ \end{pmatrix} }[/math].

Then this system of linear equations has a solution:

[math]\displaystyle{ (11)c_1+c_3=1 }[/math]

[math]\displaystyle{ (21)-c_1=0 }[/math]

[math]\displaystyle{ (12)c_2+c_3=0 }[/math]

[math]\displaystyle{ (22)c_2=1 }[/math].

When solving this system, we see that it has no solution.

This contradicts the assumption that it has a solution.

Then [math]\displaystyle{ char(F) \neq2 \implies \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \notin span(S) }[/math].

Then [math]\displaystyle{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \in span(S) \iff char(F)=2 }[/math]. Q.E.D.

A Field Problem

Find the solution to [math]\displaystyle{ x^2 = -2 }[/math] in [math]\displaystyle{ Z_{11} }[/math].

Note that a polynomial of [math]\displaystyle{ n }[/math] degree has at most [math]\displaystyle{ n }[/math] solutions.

Algorithm:

We find the solution to [math]\displaystyle{ x^2 = -2 }[/math] in [math]\displaystyle{ Z_{11} }[/math].

Since in [math]\displaystyle{ Z_{11}, -2 = 9 }[/math], then [math]\displaystyle{ x^2 = 9 }[/math].

Since [math]\displaystyle{ -9 }[/math] is additive inverse of [math]\displaystyle{ 9 }[/math], then [math]\displaystyle{ x^2 - 9 = 9 - 9 = 0 }[/math].

By the result that we proved in Question 2 of Homework 1, then [math]\displaystyle{ (x^2 - 9) = (x - 3)(x + 3) = 0 }[/math].

Then [math]\displaystyle{ x = \pm 3 }[/math] are the solutions.

A Dimension Problem

Let [math]\displaystyle{ W_1, W_2 }[/math] be subspaces of a finite dimensional vector space [math]\displaystyle{ V }[/math] over a field [math]\displaystyle{ F }[/math] where [math]\displaystyle{ W_1 \cap W_2 = \{0\} }[/math]. Then

[math]\displaystyle{ dim(span(W_1 \cup W_2)) = dim(W_1) + dim(W_2) }[/math].

Proof:

We show that [math]\displaystyle{ dim(span(W_1 \cup W_2)) = dim(W_1) + dim(W_2) }[/math].

Since [math]\displaystyle{ V }[/math] is finite dimensional, then [math]\displaystyle{ W_1, W_2 }[/math] are finite dimensional.

Then we can let [math]\displaystyle{ B_1 = \{u_1, u_2, u_3, ..., u_m\} }[/math] be a basis of [math]\displaystyle{ W_1 }[/math] and [math]\displaystyle{ B_2 = \{v_1, v_2, v_3, ..., v_n\} }[/math] be a basis of [math]\displaystyle{ W_2 }[/math].

We show that [math]\displaystyle{ B_1 \cup B_2 }[/math] is a basis of [math]\displaystyle{ span(W_1 \cup W_2) }[/math].

We show that [math]\displaystyle{ span(B_1 \cup B_2) = span(W_1 \cup W_2) }[/math].

We show that [math]\displaystyle{ span(B_1 \cup B_2) \subset span(W_1 \cup W_2) }[/math].

Since [math]\displaystyle{ (B_1 \cup B_2) \subset (W_1 \cup W_2) }[/math], then [math]\displaystyle{ span(B_1 \cup B_2) \subset span(W_1 \cup W_2) }[/math].

We show that [math]\displaystyle{ span(W_1 \cup W_2) \subset span(B_1 \cup B_2) }[/math].

Since [math]\displaystyle{ B_1 \subset (B_1 \cup B_2) }[/math], then [math]\displaystyle{ span(B_1) = W_1 \subset span(B_1 \cup B_2) }[/math].

Since [math]\displaystyle{ B_2 \subset (B_1 \cup B_2) }[/math], then [math]\displaystyle{ span(B_2) = W_2 \subset span(B_1 \cup B_2) }[/math].

Then [math]\displaystyle{ (W_1 \cup W_2) \subset span(B_1 \cup B_2) }[/math] and [math]\displaystyle{ span(W_1 \cup W_2) \subset span(B_1 \cup B_2) }[/math].

Then [math]\displaystyle{ span(B_1 \cup B_2) = span(W_1 \cup W_2) }[/math].

We show that [math]\displaystyle{ B_1 \cup B_2 }[/math] is linearly independent.

Let [math]\displaystyle{ \displaystyle\sum_{i=1}^{m} b_iu_i + \displaystyle\sum_{j=1}^{n} c_jv_j = 0 }[/math] where [math]\displaystyle{ b_i, c_j \in F }[/math].

Then [math]\displaystyle{ \displaystyle\sum_{i=1}^{m} b_iu_i = \displaystyle\sum_{j=1}^{n} (-c_j)v_j }[/math].

Since [math]\displaystyle{ W_1 \cap W_2 = \{ 0 \} }[/math], then [math]\displaystyle{ \displaystyle\sum_{i=1}^{m} b_iu_i = \displaystyle\sum_{j=1}^{n} (-c_j)v_j = 0 }[/math].

Since [math]\displaystyle{ B_1, B_2 }[/math] are linearly independent, then [math]\displaystyle{ b_i = (-c_j) = 0 }[/math].

For [math]\displaystyle{ \displaystyle\sum_{i=1}^{m} b_iu_i + \displaystyle\sum_{j=1}^{n} c_jv_j = 0 }[/math], then [math]\displaystyle{ b_i = c_j = 0 }[/math].

Then [math]\displaystyle{ B_1 \cup B_2 }[/math] is linearly independent.

Then [math]\displaystyle{ B_1 \cup B_2 }[/math] is a basis of [math]\displaystyle{ span(W_1 \cup W_2) }[/math].

Since [math]\displaystyle{ \left| B_1 \cup B_2 \right| = \left| B_1 \right| + \left| B_2 \right| }[/math], then [math]\displaystyle{ dim(span(W_1 \cup W_2)) = dim(W_1) + dim(W_2) }[/math]. Q.E.D.

Nikita

File:1014.240.pdf

Scanned Tutorial Notes by Boyang.wu

File:Tut6.pdf