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:

$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}}$

We want to equate $span(M_{1},M_{2},M_{3})$ to the set of all symmetric $2\times 2$ matrices. Here is the wrong way to write this:

$span(M_{1},M_{2},M_{3})={\begin{pmatrix}a&b\\b&c\\\end{pmatrix}}$.

Firstly, $span(M_{1},M_{2},M_{2})$ is the set of all linear combinations of $M_{1},M_{2},M_{3}$. To equate it to a single symmetric $2\times 2$ matrix makes no sense. Secondly, the elements $a,b,c,d$ 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:

$span(M_{1},M_{2},M_{3})=\{{\begin{pmatrix}a&b\\b&c\\\end{pmatrix}}:a,b,c\in F\}$ where $F$ 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 $(-2,2,2)$ is a linear combination of the vectors $(-(1,2,-1),(-3,-3,3)$ in $R^{3}$.

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 $F$, determine if the matrix ${\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}$ is in span $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}}\}$.

Proof:

We show that ${\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)\iff char(F)=2$.

We show that $char(F)=2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)$.

Assume that $char(F)=2$.

Let $c_{1}=0,c_{2}=1,c_{3}=1$.

Then $c_{1},c_{2},c_{3}\in F$.

Then $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}}$.

Since $char(F)=2$ and the entries of the matrix are from $F$, then $0=2$.

Then ${\begin{pmatrix}1&2\\0&1\\\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)$.

Then $char(F)=2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)$.

We show that $char(F)\neq 2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\notin span(S)$.

Assume to the contrary that $char(F)\neq 2\land {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)$.

Then $\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}}$.

Then this system of linear equations has a solution:

$(11)c_{1}+c_{3}=1$

$(21)-c_{1}=0$

$(12)c_{2}+c_{3}=0$

$(22)c_{2}=1$.

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

This contradicts the assumption that it has a solution.

Then $char(F)\neq 2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\notin span(S)$.

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

A Field Problem

Find the solution to $x^{2}=-2$ in $Z_{11}$.

Note that a polynomial of $n$ degree has at most $n$ solutions.

Algorithm:

We find the solution to $x^{2}=-2$ in $Z_{11}$.

Since in $Z_{11},-2=9$, then $x^{2}=9$.

Since $-9$ is additive inverse of $9$, then $x^{2}-9=9-9=0$.

By the result that we proved in Question 2 of Homework 1, then $(x^{2}-9)=(x-3)(x+3)=0$.

Then $x=\pm 3$ are the solutions.

A Dimension Problem

Let $W_{1},W_{2}$ be subspaces of a finite dimensional vector space $V$ over a field $F$ where $W_{1}\cap W_{2}=\{0\}$. Then

$dim(span(W_{1}\cup W_{2}))=dim(W_{1})+dim(W_{2})$.

Proof:

We show that $dim(span(W_{1}\cup W_{2}))=dim(W_{1})+dim(W_{2})$.

Since $V$ is finite dimensional, then $W_{1},W_{2}$ are finite dimensional.

Then we can let $B_{1}=\{u_{1},u_{2},u_{3},...,u_{m}\}$ be a basis of $W_{1}$ and $B_{2}=\{v_{1},v_{2},v_{3},...,v_{n}\}$ be a basis of $W_{2}$.

We show that $B_{1}\cup B_{2}$ is a basis of $span(W_{1}\cup W_{2})$.

We show that $span(B_{1}\cup B_{2})=span(W_{1}\cup W_{2})$.

We show that $span(B_{1}\cup B_{2})\subset span(W_{1}\cup W_{2})$.

Since $(B_{1}\cup B_{2})\subset (W_{1}\cup W_{2})$, then $span(B_{1}\cup B_{2})\subset span(W_{1}\cup W_{2})$.

We show that $span(W_{1}\cup W_{2})\subset span(B_{1}\cup B_{2})$.

Since $B_{1}\subset (B_{1}\cup B_{2})$, then $span(B_{1})=W_{1}\subset span(B_{1}\cup B_{2})$.

Since $B_{2}\subset (B_{1}\cup B_{2})$, then $span(B_{2})=W_{2}\subset span(B_{1}\cup B_{2})$.

Then $(W_{1}\cup W_{2})\subset span(B_{1}\cup B_{2})$ and $span(W_{1}\cup W_{2})\subset span(B_{1}\cup B_{2})$.

Then $span(B_{1}\cup B_{2})=span(W_{1}\cup W_{2})$.

We show that $B_{1}\cup B_{2}$ is linearly independent.

Let $\displaystyle \sum _{i=1}^{m}b_{i}u_{i}+\displaystyle \sum _{j=1}^{n}c_{j}v_{j}=0$ where $b_{i},c_{j}\in F$.

Then $\displaystyle \sum _{i=1}^{m}b_{i}u_{i}=\displaystyle \sum _{j=1}^{n}(-c_{j})v_{j}$.

Since $W_{1}\cap W_{2}=\{0\}$, then $\displaystyle \sum _{i=1}^{m}b_{i}u_{i}=\displaystyle \sum _{j=1}^{n}(-c_{j})v_{j}=0$.

Since $B_{1},B_{2}$ are linearly independent, then $b_{i}=(-c_{j})=0$.

For $\displaystyle \sum _{i=1}^{m}b_{i}u_{i}+\displaystyle \sum _{j=1}^{n}c_{j}v_{j}=0$, then $b_{i}=c_{j}=0$.

Then $B_{1}\cup B_{2}$ is linearly independent.

Then $B_{1}\cup B_{2}$ is a basis of $span(W_{1}\cup W_{2})$.

Since $\left|B_{1}\cup B_{2}\right|=\left|B_{1}\right|+\left|B_{2}\right|$, then $dim(span(W_{1}\cup W_{2}))=dim(W_{1})+dim(W_{2})$. Q.E.D.

Nikita

File:1014.240.pdf

Scanned Tutorial Notes by Boyang.wu

File:Tut6.pdf