Week 5: October 9-13, 2017.

Homework #4 is due 11pm on Friday, October 13

Required reading: Chapters 1.5, 1.6

Bases and dimension. Replacement lemma. Examples and applications: Lagrange polynomials, the dimension of a vector space over a finite field. See also here. The formula for the dimension of a sum of subspaces, $$ \dim(W_1+W_2)+\dim(W_1\cap W_2)=\dim(W_1)+\dim(W_2).$$

From now on, we'll make use of the following notations: If $A,B$ are sets, we denote $ A\backslash B = \{x\in A|\ \ x\not\in B\}.$ The symbol $\# A$ will denote the cardinality of $A$, that is, the number of elements in $A$.

In class, we used a different (but equivalent) formulation of Theorem 1.10 of the textbook:

Replacement Lemma: Let $V$ be a vector space, and $S$ a subset generating $V$, i.e. $\operatorname{span}(S)=V$. Suppose $v_1,\ldots,v_m\in V$ are linearly independent vectors. Then there exist distinct vectors $u_1,\ldots,u_m\in S$ such that the subset $ (S\backslash \{u_1,\ldots,u_m\})\cup \{v_1,\ldots,v_m\}$ spans V.

Additional homework (do not hand in).

Section 1.6, Problems 1, 7, 9, 10 (unless you did them last week.) Also Section 1.6, Problems 29, 33 and 35 Section 2.1, Problems 1, 2, 3, 21
Let $F$ be a finite field with $q$ elements. Show that every function $f\in\mathcal{F}(F,F)$ is uniquely a polynomial of degree $\le q-1$ with coefficients in $F$. That is, $\mathcal{F}(F,F)=\mathrm{Pol}_{q-1}(F)$. (Here $\mathrm{Pol}_n(F)$ is not to be confused with $P_n(F)$ from the textbook.)

In a town with $n$ inhabitants, there are $N$ clubs. Each club has an odd number of members, and for any two distinct clubs there is an even number of common members. Prove that $n\ge N$. Hint: Work with the field $\mathbb{Z}_2$, and use facts about bases and dimension. Solution.

About next week's midterm:

The midterm test takes place on Tuesday, October 17, 11:10-1:00 in the Examination Centre.
Please bring your student ID !!
It's `no tools allowed' -- especially no electronic gadgets.
It's a `crowdmark' exams, which means that we'll scan your solutions, and grade and return online. It is hence ok (perhaps even recommendable) to use a pencil, but if so, please use a dark pencil since otherwise it won't come through on the scan.
Material covered: Anything covered in this course until then. In terms of the textbook chapters, this is Appendices A-D and Chapters 1.1-1.6. We didn't manage to cover Lagrange interpolation before the midterm, so it won't be on teh midterm.
See Blackboard, under Course Materials, for last year's midterm. (With solutions.)
There will be additional TA office hours before the test; for information see the recent Blackboard announcement.