Quiz 2 (PDF) has been posted. Solve the problems without time pressure.
WARNING. There will be class on Thursday, Nov 30.
New material will be presented, required for the final exam.
Statistics of Quiz 2 is avaliable.
Final Exam: Tue, Dec 5, 8am -- 10am (30%). Click HERE to preview some of the problems.
If you are between the ages 15 and 105, you may be eligible
for a grade between A and F if you attend the
pre-final office hour held by the instructor
on Monday, December 4, 1pm - 3pm.
No purchase necessary.
Offer expires December 4, 2006, 3pm CST.
Other conditions and restrictions, such as completed course work
and final exam, may apply.
New textbook
Author: I. M. Gelfand (translator: A. Shenitzer)
Title: Lectures on Linear Algebra
Publisher: Dover
ISBN: 0-486-66082-6
Available at the Seminary Bookstore, 5757 S University Avenue.
Reminder: The discussion sessions are mandatory
(Thursdays, 4:30pm to 5:20pm in Ry251). Your participation
counts toward the "class participation" portion of your grade.
If you
missed a session,
please send an explanation
to the instructor by the subsequent weekend; and study somebody's
notes.
Topic started on Tuesday, November 28:
Linear algebra.
Topic started on Thursday, November 23:
Digraphs, Markov Chains, matrices (LN Chap 8)
Topic started on Thursday, November 16:
Generating functions, recurrences (LN Chap 5.2)
Topic started on Tuesday, November 14:
Directed graphs (LN Chap 6)
Topic started on Thursday, November 9:
Planar graphs (LN Chap 6)
Topic started on Tuesday, October 30:
Ramsey Theory (you need your class notes)
Discussion session topic on Thursday, Nov 2, 4:30pm:
The magic of binomial coefficients: proof of Chebyshev's weak
version of the Prime Number Theorem: π(x)=Θ(x / ln(x));
and an inductive proof of Fermat's little Theorem.
Topic started on Tuesday, October 24:
Graph theory (LN Chap 6)
Topic started on Tuesday, October 17:
Finite probability spaces (LN Chap 7).
Topics started on Tuesday, October 10:
asymptotic notation, counting (LN Chaps 2 and 5)
Topics started on Tuesday, September 26:
logic, quantifiers, number theory (LN Chaps 1 and 4)
Most but not all homework is assigned from the instructor's Lecture notes (LN) (PDF, 96 pp)
Click here to find past homework sets.
Posted Wednesday, 11-29, 4pm. Problems 18.1-18.7 are due Thursday, 11-30, before class. The remaining problems are due Monday, 12-4, 1pm (before the instructor's pre-final office hour). All homework is "DO" (do not hand in) and CHALLENGE PROBLEMS.
IMPORTANT. If you are viewing this assignment within 30 minutes of the stated posting time, make sure you check it again for possible immediate updates.
18.1 DO: (a) Based on the axioms of rings, prove that in a ring,
0a = 0a = 0. (Hint: use distributivity.) (eq 3 points)
(b) Based on the axioms of a vector space, prove that
in a vector space, av=0 if and only if a=0
(scalar) or v=0 (vector). Note that there are two kinds
of "zero" in this statement. (Hint: use the distributivity axioms
in one direction and the normalization axiom in the other.) (eq 6 points)
18.2 DO: find 3 vectors in some vector space which are linearly dependent but pairwise linearly independent. (eq 3 points)
If you are not comfortable with the general concept of fields, in each problem below (except 18.7) replace "the field F" by "R (the field of real numbers)."
18.3 DO: Let A be a k × n matrix over the field F. Prove: the columns of A are linearly independent if and only if the matrix equation Ax=0 has no nontrivial solution. Here x ∈ Fn is an unknown column vector and 0 ∈ Fk is the all-zero vector. The trivial solution is x=0 ∈ Fn. Similarly, the rows of A are linearly independent if and only if the matrix equation yA=0 has no nontrivial solution, where y is an unknown row vector (with k components). (Hint: this is just a rephrasing of the definition of linear independence, once you understood what matrix multiplication does.) (eq 4 points)
18.4 DO: Let n ≥ 1 and let A be an n × n matrix (square matrix) over the field F. (a) Prove: the columns of A are linearly independent if and only if the rows of A are linearly independent. (eq 5 points) (b) Prove that this statement is false if applied to non-square matrices. (eq 4 points)
18.5 DO: Let n, k ≥ 1 and let A be an n × n matrix (square matrix) over the field F. Prove: the columns of A are linearly independent if and only if the columns of the matrix Ak are linearly independent. Do not use determinants; use problem 18.3. (eq 6 points)
18.6 DO: For a=(a1,...,an)∈
Fn and b=(b1,...,bn)∈
Fn, define their dot product as
ab = a1b1+a2b2
+...+anbn. We say that a
and b are perpendicular if ab=0.
For a set S ⊆ Fn, let S⊥
denote the set of those vectors which are perpendicular to all
vectors in S.
(a) Prove: S⊥ is a subspace.
(eq 3 points)
(b) Prove: dim(S⊥)
= n - rank(S).
(eq 9 points)
(c) Prove: if U ≤Fn (subspace)
then U⊥⊥=U. (Hint: use (b).) (eq 5 points)
(d) (i) For every n ≥ 1, find
an n-dimensional subspace U in C2n
such that U = U⊥. (eq 5 points)
(ii) Do the same over F5. (eq 4 points)
(iii) Prove that this is impossible over R. (eq 2 points)
18.7 DO:
Let Fq be a finite field.
Recall that q, the order of the field, must be a
prime power.
(a) Prove: if V is a k-dimensional
vector space over Fq then
| V | = qk. (eq 4 points)
(b) (linear vs statistical independence)
Let us select a random vector
x ∈ Fqn (so the sample space
of this experiment is Fqn).
For a ∈ Fqn,
let A(a) denote the event that x is perpendicular
to a. Let now a1,...,ak∈
Fqn. Prove: the events
A(a1),...,A(ak) are independent
if and only if the vectors a1,...,ak
are linearly independent. (eq 8 points)
18.8 DO: let a1,...,an be distinct elements of the field F. Consider the polynomial P(x)=∏i=1n(x-ai) and the polynomials fj(x)=P(x)/(x-aj). Prove: f1(x),...,fn(x) are linearly independent elements in the vector space F[x] of polynomials over F. Elegance counts. (eq 8 points)
18.9 DO: We say that a set S of vectors in an
n-dimensional vector space V is in general
position if every n-subset of S is linearly
independent.
(a) For every n≥1, construct a set of
n+1 vectors in general position in the n-dimensional
space over the field F2. (eq 5 points)
(b) Assume the field
F is infinite. For every n≥1, prove that there
exist infinitely many vectors in general position in the vector space
Fn. (eq 7 points)
18.10 DO: (submodular inequality) Let A and B be
subsets of a vector space. Prove:
rank(A ∪ B)+rank(A ∩ B) ≤
rank(A)+rank(B).
18.11 DO: Observe that R (the field of real numbers)
is a vector space over Q (the field of rational numbers).
(a) Prove that the dimension of this vector space is infinite.
(Requires either some set theory or some abstract algebra. Eq 8 points)
(b) Prove that the real numbers 1, √ 2, √ 3 are
linearly independent over Q. (eq 5 points)
(c) CHALLENGE PROBLEM: Prove that the square roots of all prime
numbers are linearly independent.
18.12 CHALLENGE PROBLEM: Let a1,...,an, b1,...,bn be 2n distinct elements of the field F. Consider the n × n matrix H=(hij) where hij=1/(ai-bj) (Hilbert matrix). Prove that the rows of the Hilbert matrix are linearly independent.
18.13 CHALLENGE PROBLEM: Consider the set Fp[i] of "mod p complex numbers," i.e., expressions of the form a+bi where a,b ∈ Fp (p prime) and the arithmetic operations are performed in the natural way with the stipulation that i2= - 1. (a) Prove that Fp[i] is a commutative ring with identity. (b) For what values of p is Fp[i] a field? (Hint: Experiment. A very simple pattern will emerge. Proving the correctness of the pattern is not so easy.) (Note that through this exercise, fields of order p2 will be constructed for infinitely many values of p.)
Instructor's office hours: by appointment (please send e-mail)
Lectures: Tuesdays and Thursdays, 9:00am to 10:20am in Ry251
Discussion Sessions: Thursdays, 4:30pm to 5:20pm in Ry251.
Teaching Assistants:
Hari Narayanan hari(at)cs(dot)uchicago(dot)edu.
Eric Purdy epurdy(at)cs(dot)uchicago(dot)edu.
Hari holds office hours Monday and Wednesday 5-6pm in Ry256.
Required text:
J. Matoušek, J. Nešetříl: "Invitation to Discrete Mathematics," published by Oxford University Press, ISBN# 098502079.
NEW! I. M. Gelfand: "Lectures on Linear Algebra," published by Dover, ISBN# 0-486-66082-6. NEW!
Available at the Seminary Bookstore, 5757 S University Avenue.
Recommended text:
Edgar G. Goodaire and Michael M. Parmenter, ``Discrete Mathematics with Graph Theory,'' published by Prentice Hall, ISBN# 013602798.
Grades will be based on homework (20%), tests (70%), and class participation (10%).
Test datesMaterial covered on first Midterm includes logic, quantifiers, relations, equivalence relations, number theory (gcd, congruences, multiplicative inverse, linear congruences, Euler's phi function, residue classes mod m, reduced residue classes mod m, Euler-Fermat Theorem, Fermat's little Theorem, Chinese Remainder Theorem and its use in solving congruences modulo composite moduli, prime numbers, primitive roots, discrete logarithm), basic counting problems, binomial and multinomial coefficients, bijective proofs, binomial theorem, Newton's binomial coefficients, Newton's binomial theorem, limit of sequeneces, asymptotic equality, Stirling's formula.