Difference between revisions of "14-240/Tutorial-October14"

From Drorbn
Jump to: navigation, search
(A Dimension Problem)
(A Dimension Problem)
Line 274: Line 274:
  
  
''Proof''
+
''Proof:''
 +
 
 +
We show that <math>dim(span(W_1 \cup W_2)) = dim(W_1) + dim(W_2)</math>.
 +
 
 +
:Let <math>B_1 = \{u_1, u_2, u_3, ..., u_m\}</math> be a basis of <math>W_1</math> and <math>B_2 = \{v_1, v_2, v_3, ..., v_n\}</math> be a basis of <math>W_2</math>.
 +
 
 +
:We show that <math>B_1 \cup B_2</math> is a basis of <math>span(W_1 \cup W_2)</math>.
 +
 
 +
::We show that <math>span(B_1 \cup B_2) = span(W_1 \cup W_2)</math>.
 +
 
 +
:::We show that <math>span(B_1 \cup B_2) \subset span(W_1 \cup W_2)</math>.
 +
 
 +
::::Since <math>B_1 \subset W_1 \and B_2 \subset W_2</math>, then <math>(B_1 \cup B_2) \subset span(W_1 \cup W_2)</math>.
 +
 
 +
::::Since <math>span(W_1 \cup W_2)</math> is a subspace, then <math>span(B_1 \cup B_2) \subset span(W_1 \cup W_2)</math>
 +
 
 +
:::We show that <math>span(W_1 \cup W_2) \subset span(B_1 \cup B_2)</math>.
 +
 
 +
::::Since <math>W_1 \subset span(B_1) \and W_2 \subset span(B_2)</math>, then <math>(W_1 \cup W_2) \subset span(B_1 \cup B_2)</math>.
 +
 
 +
::::Since <math>span(B_1 \cup B_2)</math> is a subspace, then <math>span(W_1 \cup W_2) \subset span(B_1 \cup  B_2)</math>.
 +
 
 +
:::Then <math>span(B_1 \cup B_2) = span(W_1 \cup W_2)</math>.
 +
 
 +
::We show that <math>B_1 \cup B_2</math> is linearly independent.
 +
 
 +
:::Let <math>\displaystyle\sum_{i=1}^{m} b_iu_i + \displaystyle\sum_{j=1}^{n} c_jv_j = 0</math> where <math>b_i, c_j \in F</math>.
 +
 
 +
:::Since <math>W_1 \cap W_2 = \{0\}</math>, then the situation in which both <math>b_i</math> and <math>c_j</math> are nonzero produces a contradiction.
 +
 
 +
:::Since <math>B_1, B_2</math> are linearly independent, then the situation in which either <math>b_i</math> or <math>c_j</math> is nonzero also produces a contradiction.
 +
 
 +
:::Then <math>B_1 \cup B_2</math> is linearly independent.
 +
 
 +
::Then <math>B_1 \cup B_2</math> is a basis of <math>span(W_1 \cup W_2)</math>.
 +
 
 +
:Since <math>\left| B_1 \cup B_2 \right| = \left| B_1 \right| + \left| B_2 \right|</math>, then <math>dim(span(W_1 \cup W_2)) = dim(W_1) + dim(W_2)</math>.  ''Q.E.D.''
  
 
==Nikita==
 
==Nikita==

Revision as of 23:51, 15 October 2014

Contents

Boris

Elementary and (Not So Elementary) Errors in Homework

(1) Bad Notation


Let

 
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}


be matrices. 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) 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 \and
  \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) \neq2 \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).

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 \subset W_1 \and B_2 \subset W_2, then (B_1 \cup B_2) \subset span(W_1 \cup W_2).
Since span(W_1 \cup W_2) is a subspace, 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 W_1 \subset span(B_1) \and W_2 \subset span(B_2), then (W_1 \cup W_2) \subset span(B_1 \cup B_2).
Since span(B_1 \cup B_2) is a subspace, then 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_iu_i + \displaystyle\sum_{j=1}^{n} c_jv_j = 0 where b_i, c_j \in F.
Since W_1 \cap W_2 = \{0\}, then the situation in which both b_i and c_j are nonzero produces a contradiction.
Since B_1, B_2 are linearly independent, then the situation in which either b_i or c_j is nonzero also produces a contradiction.
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