# 14-240/Tutorial-October14

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Boris

#### Elementary and (Not So Elementary) Errors in Homework

Consider these three matrices:

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

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

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

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

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

Proof:

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

We show that ${\displaystyle char(F)=2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)}$.
Assume that ${\displaystyle char(F)=2}$.
Let ${\displaystyle c_{1}=0,c_{2}=1,c_{3}=1}$.
Then ${\displaystyle c_{1},c_{2},c_{3}\in F}$.
Then ${\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}}}$.
Since ${\displaystyle char(F)=2}$ and the entries of the matrix are from ${\displaystyle F}$, then ${\displaystyle 0=2}$.
Then ${\displaystyle {\begin{pmatrix}1&2\\0&1\\\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)}$.
Then ${\displaystyle char(F)=2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)}$.
We show that ${\displaystyle char(F)\neq 2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\notin span(S)}$.
Assume to the contrary that ${\displaystyle char(F)\neq 2\land {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\in span(S)}$.
Then ${\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}}}$.
Then this system of linear equations has a solution:
${\displaystyle (11)c_{1}+c_{3}=1}$
${\displaystyle (21)-c_{1}=0}$
${\displaystyle (12)c_{2}+c_{3}=0}$
${\displaystyle (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 ${\displaystyle char(F)\neq 2\implies {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}}\notin span(S)}$.
Then ${\displaystyle {\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 ${\displaystyle x^{2}=-2}$ in ${\displaystyle Z_{11}}$.

Note that a polynomial of ${\displaystyle n}$ degree has at most ${\displaystyle n}$ solutions.

Algorithm:

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

Since in ${\displaystyle Z_{11},-2=9}$, then ${\displaystyle x^{2}=9}$.
Since ${\displaystyle -9}$ is additive inverse of ${\displaystyle 9}$, then ${\displaystyle x^{2}-9=9-9=0}$.
By the result that we proved in Question 2 of Homework 1, then ${\displaystyle (x^{2}-9)=(x-3)(x+3)=0}$.
Then ${\displaystyle x=\pm 3}$ are the solutions.

#### A Dimension Problem

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

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

Proof:

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

Since ${\displaystyle V}$ is finite dimensional, then ${\displaystyle W_{1},W_{2}}$ are finite dimensional.
Then we can let ${\displaystyle B_{1}=\{u_{1},u_{2},u_{3},...,u_{m}\}}$ be a basis of ${\displaystyle W_{1}}$ and ${\displaystyle B_{2}=\{v_{1},v_{2},v_{3},...,v_{n}\}}$ be a basis of ${\displaystyle W_{2}}$.
We show that ${\displaystyle B_{1}\cup B_{2}}$ is a basis of ${\displaystyle span(W_{1}\cup W_{2})}$.
We show that ${\displaystyle span(B_{1}\cup B_{2})=span(W_{1}\cup W_{2})}$.
We show that ${\displaystyle span(B_{1}\cup B_{2})\subset span(W_{1}\cup W_{2})}$.
Since ${\displaystyle (B_{1}\cup B_{2})\subset (W_{1}\cup W_{2})}$, then ${\displaystyle span(B_{1}\cup B_{2})\subset span(W_{1}\cup W_{2})}$.
We show that ${\displaystyle span(W_{1}\cup W_{2})\subset span(B_{1}\cup B_{2})}$.
Since ${\displaystyle B_{1}\subset (B_{1}\cup B_{2})}$, then ${\displaystyle span(B_{1})=W_{1}\subset span(B_{1}\cup B_{2})}$.
Since ${\displaystyle B_{2}\subset (B_{1}\cup B_{2})}$, then ${\displaystyle span(B_{2})=W_{2}\subset span(B_{1}\cup B_{2})}$.
Then ${\displaystyle (W_{1}\cup W_{2})\subset span(B_{1}\cup B_{2})}$ and ${\displaystyle span(W_{1}\cup W_{2})\subset span(B_{1}\cup B_{2})}$.
Then ${\displaystyle span(B_{1}\cup B_{2})=span(W_{1}\cup W_{2})}$.
We show that ${\displaystyle B_{1}\cup B_{2}}$ is linearly independent.
Let ${\displaystyle \displaystyle \sum _{i=1}^{m}b_{i}u_{i}+\displaystyle \sum _{j=1}^{n}c_{j}v_{j}=0}$ where ${\displaystyle b_{i},c_{j}\in F}$.
Then ${\displaystyle \displaystyle \sum _{i=1}^{m}b_{i}u_{i}=\displaystyle \sum _{j=1}^{n}(-c_{j})v_{j}}$.
Since ${\displaystyle W_{1}\cap W_{2}=\{0\}}$, then ${\displaystyle \displaystyle \sum _{i=1}^{m}b_{i}u_{i}=\displaystyle \sum _{j=1}^{n}(-c_{j})v_{j}=0}$.
Since ${\displaystyle B_{1},B_{2}}$ are linearly independent, then ${\displaystyle b_{i}=(-c_{j})=0}$.
For ${\displaystyle \displaystyle \sum _{i=1}^{m}b_{i}u_{i}+\displaystyle \sum _{j=1}^{n}c_{j}v_{j}=0}$, then ${\displaystyle b_{i}=c_{j}=0}$.
Then ${\displaystyle B_{1}\cup B_{2}}$ is linearly independent.
Then ${\displaystyle B_{1}\cup B_{2}}$ is a basis of ${\displaystyle span(W_{1}\cup W_{2})}$.
Since ${\displaystyle \left|B_{1}\cup B_{2}\right|=\left|B_{1}\right|+\left|B_{2}\right|}$, then ${\displaystyle dim(span(W_{1}\cup W_{2}))=dim(W_{1})+dim(W_{2})}$. Q.E.D.