Linear Algebra II

September 18, 2014

Lecture 9

Filed under: 2014 Fall — Y.K. Lau @ 9:31 PM

We give a brief summary of the vector space theory covered today.

Next, we recap the key ideas in the proof of the dimension formula:

${\dim (U+W)=\dim U+\dim W-\dim (U\cap W)}$.

If ${\{x_1,\cdots, x_d\}}$ is a basis for ${U\cap W}$, ${\{x_1,\cdots, x_d, u_1,\cdots, u_m\}}$ and ${\{x_1,\cdots, x_d, w_1,\cdots, w_p\}}$ are bases for ${U}$ and ${W}$ resp., then ${\{x_1,\cdots, x_d, u_1,\cdots, u_m, w_1,\cdots, w_p\}}$ is a basis for ${U+W}$.

To show the linear independence, we consider

$\displaystyle r_1x_1+\cdots+r_d x_d +s_1 u_1+\cdots+ s_mu_m$ ${+}$ $\displaystyle t_1 w_1+\cdots+t_p w_p$ ${=\underline{0}.}$

From this we deduce

$\displaystyle r_1x_1+\cdots+r_d x_d + s_1 u_1+\cdots+ s_mu_m$ $\displaystyle =$ $\displaystyle (-t_1)w_1+\cdots +(-t_p)w_p$           ${(*)}$

Keypoints:

1. The LHS is in ${U}$ while the RHS is ${W}$.
Thus ${(-t_1)w_1+\cdots +(-t_p)w_p\in W}$ ${\cap}$ ${U}$.
2. As ${\{x_1,\cdots, x_d\}}$ is a basis for ${U\cap W}$,
${(-t_1)w_1+\cdots +(-t_p)w_p = a_1x_1+\cdots a_dx_d}$.
Rearranging, we get

$\displaystyle a_1x_1+\cdots a_dx_d+t_1w_1+\cdots +t_pw_p =\underline{0}.$

3. As ${\{x_1,\cdots, x_d, w_1,\cdots, w_p\}}$ is a basis for ${W}$, we infer ${a_1=\cdots =a_d=t_1=\cdots =t_p=0}$.
4. Put ${t_1=\cdots =t_p=0}$ into ${(*)}$, ${r_1x_1+\cdots+r_d x_d+s_1 u_1+\cdots+ s_mu_m=\underline{0}}$.
5. As ${\{x_1,\cdots, x_d, u_1,\cdots, u_m\}}$ is a basis for ${U}$, we infer ${a_1=\cdots =a_d=s_1=\cdots =s_m=0}$.

September 15, 2014

Questions

Filed under: 2014 Fall — Y.K. Lau @ 8:28 PM

Today we further discuss Remark 1 in the last post – what happens when we perform set operations on two subspaces. A key point is that we are led to the concepts of the sum of two subspaces, and the direct sum. (The lecture slides are uploaded in the folder Slides at moodle.)

After the lecture ended, some classmates asked questions that I would share with you here.

• Qn 1. Is the direct sum (of subspaces) related to quotient vector spaces?

You may wonder why your classmate ask this question because they (direct sum and quotient space) seem to be very different objects. If the vector space ${V=U\oplus W}$, then ${U}$ and ${W}$ are containing vectors in ${V}$. However, ${V/W}$ contains the equivalence classes ${[v]}$ where ${v\in V}$, which is more abstract and complicated. Nevertheless, there are interesting relations between the concepts of direct sum and quotient vector space. You will get some ideas in Tutorial 2 and Assignment 2.

• We explained in lecture that even if ${X}$ and ${Y}$ are subspaces of ${V}$, ${X\setminus Y}$ is NOT a subspace of ${V}$. Our proof is that both ${X}$ and ${Y}$ contain the zero vector ${\underline{0}}$; thus ${\underline{0}\notin X\setminus Y}$ and so ${X\setminus Y}$ is not a subspace.

Qn 2. A classmate asked why the zero vector of ${X}$ must equal the zero vector of ${Y}$.

(Well our proof does not work if they are different.) This question sounds silly but indeed it makes sense very much! If you were me, how would you reply?

Mine is: the zero vector of any subspace (of ${V}$) has to be the zero vector of ${V}$.

First of all, zero vector in a vector space is unique (i.e. given a vector space, there is only one element fulfilling (A4)). [Prove it! If you cannot work it out, please ask me or our tutor.]

Next, let ${V}$ be a vector space and ${X}$ be its subspace. Suppose ${0_V}$ is the zero vector of ${V}$ and ${0_X}$ is the zero vector of ${X}$. Now ${0_X\in X\subset V}$, i.e. ${0_X}$ is a vector in ${V}$. Write ${0}$ for the real number zero and use Part (1) of Theorem 6.1.3 (i.e. Thm 3 of Section 6.1) twice, we infer

$\displaystyle 0_V\stackrel{{\rm Thm \,6.1.3 (1)\, for} \, V}{=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!}$ $\displaystyle \ \ 0$ $\displaystyle\cdot 0_X \stackrel{{\rm Thm \,6.1.3 (1)\, for} \, X}{=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!=\!\!\!}\ \ 0_X.$

September 11, 2014

Lecture 6

Filed under: 2014 Fall — Y.K. Lau @ 8:00 PM

Today we completed our introduction on quotient vector spaces and introduced a couple of important concepts:

• Linear combination & Span,
• Spanning set,
• Minimal spanning set,
• Linear independence,
• Basis & dimension.

[This is also a checklist for your learning outcomes! You have to understand all these concepts and the theory related to them.]

Below is a flowchart to help you see how/what the theory is developed.

Remark 1. One may try to use set operations to make subspaces. Suppose ${U}$ and ${V}$ are subspaces of a vector space. Will

(i)   ${U\cup V}$,       (ii)   ${U\cap V}$,       (iii)   ${U\setminus V}$

be subspaces?
In general the answer is (i) NO,   (ii) YES,   (iii) NO.

Indeed, we have the following results:

Let ${U}$ and ${V}$ be subspaces of a vector space. Then ${U\cup V}$ is a subspace if and only if ${U\subset V}$ or ${V\subset U}$.

(Proof. See Assignment 1 Q. 3.)

${U\cap V}$ is a subspace.

(Proof. Exercise.)

${U\setminus V}$ is never a subspace.

(Proof. Exercise.)

[In view of this, you may appreciate more the definition of “Span”, which teaches you how to make subspaces.]

Remark 2. Recall the following two convention:

1. ${{\rm Span}(\emptyset)=\{\underline{0}\}}$ (the zero subspace).
2. Let ${S}$ be any subset (not necessarily finite) of a vector space. Then

$\displaystyle {\rm Span}(S)=\left\{a_1\underline{v}_1+a_2\underline{v}_2+\cdots +a_m\underline{v}_m: \ \begin{array}{l} a_1,\cdots, a_m\in {\mathbb R}, \\ \underline{v}_1,\cdots, \underline{v}_m\in S, \\ m\in {\mathbb N}\end{array}\right\}.$

Remark 3. We mentioned in lecture that linearly independence is a notion to characterize minimal spanning set. But how?! This is explained in the following

Claim: Let ${V}$ be a vector space. A linearly independent spanning set of ${V}$ is a minimal spanning set for ${V}$.

Proof. Suppose ${B=\{v_1,\cdots, v_n\}}$ is a linearly independent spanning set but not minimal.

That means we can find a proper subset ${C}$ of ${B}$ such that ${V={\rm Span}(C)}$.

As ${\displaystyle {} \ C\mathop{\subset}_{\neq} B \ {} }$, ${C}$ has less than ${n}$ elements.

i.e. The spanning set ${C}$ has less elements than the linearly independent set ${B}$.

This contradicts to the Fundamental Thm (in p. 305 of the textbook). So ${B}$ is minimal.

Finally we remark the often used equivalent definitions of linearly independence/dependence:

Let ${\underline{v}_1,\underline{v}_2,\cdots, \underline{v}_n}$ be vectors in a vector space. The following are equivalent:

1. ${\underline{v}_1,\underline{v}_2,\cdots, \underline{v}_n}$ are linearly independent.
2. The (vector) equation

${s_1\underline{v}_1+s_2\underline{v}_2+\cdots+s_n \underline{v}_n=\underline{0}}$

(regarding ${s_1,\cdots, s_n}$ as variables) has the trivial solution ${s_1=\cdots = s_n=0}$ only.

Below are various equivalent ways to define linearly dependent vectors.

Given vectors ${\underline{u}_1,\underline{u}_2,\cdots, \underline{u}_m}$, then the following are equivalent:

1. ${\underline{u}_1,\underline{u}_2,\cdots, \underline{u}_m}$ are linearly dependent.
2. ${\underline{u}_1,\underline{u}_2,\cdots, \underline{u}_m}$ are not linearly independent.
3. The equation ${s_1\underline{u}_1+s_2\underline{u}_2+\cdots+s_m \underline{u}_m=\underline{0}}$ has non-trivial solution(s).
4. There exist ${s_1,s_2,\cdots, s_m}$, not all zero, such that ${s_1\underline{u}_1+s_2\underline{u}_2+\cdots+s_m \underline{u}_m=\underline{0}}$.

September 8, 2014

Lecture 4

Filed under: 2014 Fall — Y.K. Lau @ 10:18 PM

Last week we learnt the definitions of vector spaces and subspaces. Today we want to introduce a new and important concept — quotient vector space.

To start with we need some fundamental concepts in set theory, that is, equivalence relation, equivalence class and quotient set. Given a set ${X}$, we may specify a rule, called relation, to link up pairs of elements in ${X}$. As there is no requirement on how to specify the rule, we shall not get a nice object to play with. Hence, we consider a special kind of relations that satisfy the following 3 properties:

1. (Reflexive)     ${\forall}$ ${x\in X}$, ${x\sim x}$.
2. (Symmetric)   ${\forall}$ ${x,y\in X}$, ${x\sim y}$ implies ${y\sim x}$.
3. (Transitive)     ${\forall}$ ${x,y,z\in X}$, ${x\sim y}$ & ${y\sim z}$ implies ${x\sim z}$.

A relation satisfying the above 3 properties is called an equivalence relation.

To help understanding, below are some examples and non-examples: let ${X}$ be the set of all men in Hong Kong,

1. For any ${x,y\in X}$, define ${x\sim y}$ iff ${x}$ is the father of ${y}$. This relation satisfies NONE of the 3 properties.
2. For any ${x,y\in X}$, define ${x\sim y}$ iff ${x}$ and ${y}$ have the relationship of father and son. Then ${\sim}$ satisfies the symmetric property but not the others.
3. For any ${x,y\in X}$ define ${x\sim y}$ iff ${x}$ and ${y}$ have the same ancestor in the Tang dynasty. Now ${\sim}$ is an equivalence relation.

Next we define equivalence class and quotient set. Given a set ${X}$ with an equivalence relation ${\sim}$, we define for any ${x\in X}$,

$\displaystyle [x]=\{y\in X: \ y\sim x\}.$

This set ${[x]}$ is called the equivalence class of ${x}$. Then we have the following important result:

Given a set ${X}$ with the equivalence relation ${\sim}$, ${X}$ is a disjoint union of equivalence classes. (Often people say that ${X}$ is partitioned into equivalence classes.)

Finally, we define

$\displaystyle X/\!\!\sim\,\ =\{[x]: \ x\in X\}$

which is the quotient set of ${X}$ by ${\sim}$.

Recall that in lecture, we illustrated the concepts with the example ${{\mathbb N}}$ and the relation: ${x\sim y}$ iff ${x}$ and ${y}$ have the same parity (${x,y\in{\mathbb N}}$).

With these fundamental concepts, we return to our concerned object — quotient space.

Suppose ${V}$ is a vector space and ${W}$ is a subspace of ${V}$. For any ${x,y\in V}$, define the relation

${x\sim y}$ iff ${x-y\in W}$.

Claim 1. The relation ${\sim}$ is an equivalence relation.

Denote the quotient set ${V/\!\!\sim}$ by ${V/W}$. Now we impose two operations on ${V/W}$, defined as follows:

1. Addition:   ${\forall}$ ${[x],[y]\in V/W}$,

${[x]+[y]=\{a+b: \ a\in [x], \, b\in [y]\}}$.

2. Scalar multiplication:   ${\forall}$ ${\alpha\in{\mathbb R}}$,   ${\forall}$ ${[x]\in V/W}$,

${\alpha\cdot [x]=\{\alpha a: \ a\in [x]\}}$.

Claim 2. ${(V/W, +, \cdot\,)}$ is a vector space, called the quotient (vector) space of ${V}$ by ${W}$.

We haven’t completed the proof of Claim 2 yet and will do next lecture. To end this post, let us have an exercise.

Exercise: Consider ${{\mathbb R}^2}$ and ${W={\mathbb R}\begin{pmatrix} 1\\ 1\end{pmatrix}}$   (see Example 2 in p.297 of the textbook). Let

$\displaystyle \underline{a} = \begin{pmatrix} 1\\ 0\end{pmatrix}$,    ${\displaystyle\underline{b} = \begin{pmatrix} 3\\ 3\end{pmatrix}}$,   ${\displaystyle\underline{c} = \begin{pmatrix} 0\\ 1\end{pmatrix}}$.

1. Describe ${[a]}$ and ${[b]}$.
2. Draw out ${[a]}$, ${[b]}$ and ${[c]}$ if ${{\mathbb R}^2}$ is represented as the ${xy}$-plane.

September 1, 2014

Lecture 1

Filed under: 2014 Fall — Y.K. Lau @ 3:54 PM

There are many ways to introduce linear algebra. Quite often one starts with system of linear equations, for example,

$\displaystyle \left\{\begin{array}{lcr} 2x+y&=& 8\\ x+3y & =& 9. \end{array} \right.$

Everybody (in our course) knows how to solve it — using the method of elimination.

Algebraically, there are two important things stemming from this simple example:

• (A) Matrix notation — a shorthand for the system.
• (B) The method of Gaussian elimination.

The method in (B) involves three types of operations:

• (I) Interchange two rows.
• (II) Multiply one row by a nonzero number.
• (III) Add a multiple of one row to another row.

These operations are called elementary row operations of type (I), (II), (III) resp.. All systems of linear equations can be solved by these three elementary row operations with a suitable algorithm — Gaussian Algorithm (also called the method of Gaussian elimination). [You are supposed to know it. If you don’t or you forgot, please study Chapter 1, Sections 1.1-1.2 (p. 1-17), of the textbook and do some exercises therein.]

Geometrically, we can also give an interpretation for systems of linear equations. Firstly let us link up geometric vectors with matrices: A geometric vector is an “arrow” which carries two pieces of information: magnitude (its length) and direction.

Geometric vectors can be added up by joining the head and tail. To describe this addition algebraically we represent a geometric vector (in a plane) by a ${2\times 1}$ matrix, say, ${\begin{pmatrix} x_1\\ y_1\end{pmatrix}}$. Suppose the geometric vectors ${\vec{a}}$ and ${\vec{b}}$ are represented by

$\displaystyle \vec{a} = \begin{pmatrix} 2 \\ 1 \end{pmatrix}, \quad \vec{b} = \begin{pmatrix} 1 \\ 3\end{pmatrix}, \quad \vec{c} = \begin{pmatrix} 8\\ 9\end{pmatrix}.$

Then ${\vec{a}+\vec{b}=\begin{pmatrix} 3\\ 4\end{pmatrix}}$.

The scalar multiplication of a geometric vector can also be represented by a matrix operation, for example:

${2\vec{a}=\begin{pmatrix} 4\\ 2\end{pmatrix} = 2 \begin{pmatrix} 2 \\ 1\end{pmatrix}}$,     and    ${3\vec{a}+2\vec{b}= \vec{c}}$.

Now, we can give a geometric interpretation of the system ${ \left\{\begin{array}{lcr} 2x+y&=& 8\\ x+3y & =& 9. \end{array}\right. }$ Observe that the system can be expressed as

$\displaystyle x\begin{pmatrix} 2 \\ 1\end{pmatrix} + y \begin{pmatrix} 1 \\ 3\end{pmatrix} = \begin{pmatrix} 8\\ 9\end{pmatrix}$    i.e.   ${x\vec{a}+y \vec{b}=\vec{c}}$.

Thus, to solve the system, it is equivalent to find ${x,y}$ such that the vector sum ${x\vec{a}+y\vec{b}}$ equals ${\vec{c}}$. We have observed that ${3\vec{a}+2\vec{b}= \vec{c}}$; consequently ${x=3,y=2}$ is a solution for the system.

The concept of vectors can be extended to other objects, i.e. not merely matrices, so that we may apply the methodologies in matrices to these objects. (Mathematics is powerful as it can be applied to various objects!) Hence, what we did in today lecture is: Define Vector Spaces; Look at Examples & a Non-example.

August 30, 2014

Logical Warm-up

Filed under: 2014 Fall — Y.K. Lau @ 4:49 PM

Someone said, “If mathematics is regarded as a language, then logic is its grammar.” This is true and that’s why we have the course MATH1001/2012 — Fundamental concepts of mathematics. Here we start with an introductory remark on “logic”, serving as a warm-up and a preliminary.

1. Statements

A statement is a declarative sentence, conveying a definite meaning that may be either true or false but not both simultaneously.

Example 1 Which of the following is a statement?

1. Every HKU undergraduate student has a university number.
2. There is a man who is over six feet tall.
3. Linear algebra smells good.
4. If there is life on Mars, then the postman delivers letters.
5. This sentence is false.

Ans.

Clearly, (1) and (2) are statements. Definitely (2) is a true statement. For (1), it is either true or false, although frankly I don’t know the answer because I haven’t checked through every student of HKU.

(3) is not a statement. (Does linear algebra have odor?)

(4) is a statement and it is a true statement, because the job of postman is to deliver letters. So no matter whether or not Mars has life, the conclusion is valid.

(5) is a bit more tricky — it is not a statement. The reason is that you cannot assign a true/false value to it. Why? Think about what it means if (5) is true — it says “this sentense, i.e. (5), is false”. So (5) is true and false at the same time! If (5) is false, that means “This sentence is false” is not valid. In other words, this sentence (5) is true. Again (5) is false and true simultaneously. That’ why we cannot give it a true/false value.

Important Remark

1. TRUE means absolutely and completely true. There is no in-between stage. So there is no such thing as saying a statement is somewhat true’ or almost true’.
2. For some statements, you may pay careful attention to what member of a class the statement applies. For statement (1) of Example 1, a single exception will renders false. But for (2), I am shorter than six-feet (and I am a man). This fact of my height cannot conclude statement (2) is false. We call “for all/for every/for any” and “there exists/for somequantifiers, which will arise often in our course.
3. The truth value of a statement may depend upon the way it is interpreted. For example, “you are intelligent”. I would say that it is a true statement (because you take MATH1111), but you may say it is a false statement. (You are humble!) But in any case, once intelligence is clearly defined, then the statement must be declared as either completely true or false.

2. Negation

Negation turns a statement into another statement which will be opposite to the original one in terms of truth value. For example, “X is rich”. Its negation is “X is poor”. It sounds easy. Well, finish the example below.

Example 2 Write down the negation of each of the following statements.

1. Some men are rich.
2. Every man is happy.
3. There exists a man who is rich.
4. Some unhappy men are rich.
5. There is a happy man that all of his friends are unhappy.

If you have finished, see answers below.

Ans.

1. All men are poor. (I suppose the negation of rich (i.e. not rich) is the same as poor.)
2. Some men are unhappy. (Think carefully if your answer is “Every man is unhappy” or “No man is happy”, which are not correct.)
3. All men are poor. (Because “There exists a man who is rich” means the same as “Some men are rich”.)
4. All unhappy men are poor. (The answer is not “All happy men are poor”, because for the given statement “Some unhappy men are rich”, we are considering the group of “unhappy men” and the statement says that some members in this group are rich. So the negation is “All member in this group are poor”.)
5. Every happy man has some happy friends. Alternatively, the negation can be stated as “For any happy man, there exists some friends of him who are happy.”

3. Logical Implications

Here I would not tell precisely what is a logical implication. Instead, let me introduce some notation and terminologies. We write “${p\Rightarrow q}$” when the statement ${p}$ implies (affirmatively) the statement ${q}$“. What does “${p\Rightarrow q}$” tell? There are two important points:

1. If ${p}$ is true, then ${q}$ is true.
2. If ${q}$ is false, then ${p}$ is also false.

Let us look at an example.

Example 3

1. ABC is a triangle ${\Rightarrow}$ ${\angle A + \angle B+ \angle C = 180}$ degrees. (I think you know this fact. This is an example of point 1.)
2. ${\sin \frac{\pi}4 >\frac45}$ ${\Rightarrow}$ ${-1>0}$. (Refer to point 2. Hence we know ${\sin \frac{\pi}4 >\frac45}$ is false.)

You may wonder how the deduction in (ii) comes up. Below is the details:

${\sin \frac{\pi}4 >\frac45\Rightarrow \sin^2 \frac{\pi}4 >\frac{16}{25}\Rightarrow 1-2\sin^2\frac{\pi}4 < 1-\frac{32}{25}\Rightarrow \cos \frac{\pi}2 < -\frac{7}{25} \Rightarrow 0 <-1.}$

Remark. When the statement ${p}$ in “${p\Rightarrow q}$” is false, we cannot draw any conclusion on ${q}$, i.e. ${q}$ may be true or not. For example,

$\displaystyle 1\ge 2 \Rightarrow -1 \ge 0.$

(This is deduced by subtracting 2 on both sides of $\displaystyle 1\ge 2.$) The consequence ${-1\ge 0}$ is of course a false statement. However,

$\displaystyle 1 \ge 2 \Rightarrow 0\ge 0.$

(We have multiplied ${0}$ on both sides of ${1\ge 2}$.) Now the consequence ${0\ge 0}$ is a true statement! So we don’t know the truth value of the conclusion from a false hypothesis.

There are other ways to phrase “${p}$ implies ${q}$“:

1. ${p}$ is a sufficient condition for ${q}$.
2. ${q}$ is a necessary condition for ${p}$.
3. ${p}$ only if ${q}$.

4. Final Remark

Logic is, but not just confined to be, the grammar of MATHEMATICS. For more, you may browse the following website:

http://philosophy.hku.hk/think/logic/intro.php

« Previous Page

Blog at WordPress.com.