The notation "MN" refers to the Matoušek--Nešetříl text
The notation "LIN" refers to the instructor's Linear Algebra notes, currently in progress.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the
instructor's attention) and no deadline (except they expire when
discussed in class). Make sure you hand them in on a separate sheet,
state your name, the fact that this is a challenge problem
solution, and indicate the problem being solved. One further
request: if you hand in a solution a challenge problem, send email to the
instructor giving the problem number and the brief indication of the
problem (copied from the problem announcement: like "n+1 numbers"
or "another limit related to the def of "e"" -- no detailed description
needed, this suffices to remind me which problem it was). Such
email will create an easy record and help avoid mistakes in bookkeeping.
-- Please also send me email at this time about challenge problems
to which you handed in solutions earlier in this course. This will
help me create a complete record.
REWARD PROBLEMS are challenge problems that you should NOT hand in.
The solution is its own reward. No deadline. Of course you may discuss
your thoughts with the TA and the instructor.
If you hand in material before its due date, make sure you
put it on a separate sheet since solutions are graded in batches
by their due dates.
15.1 HW: Let φ : V → V be a transformation such that
Ker(φ) = Im(φ). Prove: such a φ exists if and only
if dim(V) is even. (5+7 points: 5 for "only if" (right arrow),
7 for "if" (left arrow))
15.2 HW: Show that the first miracle fails
for the following independence
concepts: (a) independence of vertices in a graph; (b) independence
of random variables. In each case, construct an example
(a graph for (a) and a list of random variables over the same
probability space for (b)) such
that your example contains two maximal independent sets A
and B such that |A| > 100 |B|. (5+15 points)
15.3 HW: Let ρθ denote the counterclockwise
rotation of the plane by θ as in Ex. 14.17.
Let e and f be two perpendicular
unit vectors in the plane; e points East and f
points North. (a) Determine the matrix A
corresponding to ρθ under this basis.
(b) Let g = ρθ(e).
Draw a picture showing e,f,g when θ = π/6.
(c) For what values of θ are e, g linearly independent?
(d) Suppose θ is such a value; then {e, g} form
a basis of the plane. Determine the matrix B
corresponding to ρθ under this basis.
(e) We know from a theorem that A and B are
similar, i.e., B = S-1AS for some
matrix S. Find such an S. Explain how you
found S.
(f) Determine the trace and the determinant of A
and B. Make an observation about your results
and state why that outcome was predictable. - Show all your work.
Calculation without explanation will not get full credit and
may get zero credit.
(4+1+2+8+8+3)
15.4 DO: (a) Prove: if φ is a linear transformation of a vector
space over the complex numbers then φ always has an eigenvector.
(b) Prove: if φ is a linear transformation of a vector
space of odd dimension over the real numbers then φ always
has an eigenvector. (c) Show that (b) is false for every even dimension.
15.5 DO: Prove: an n × n matrix A is invertible if
and only if zero is not an eigenvalue of A.
15.6 DO: Prove: the right eigenvalues of a square matrix are the same
as the left eigenvalues.
15.7 DO: Prove: if v1 , ... , vk
are eigenvectors of the transformation φ : V → V
corresponding to k distinct eigenvalues then
v1 , ... , vk are linearly
indepedent.
15.8 DO: We say that a matrix is diagonalizable if
it is similar to a diagonal matrix. Prove: an n × n
matrix is diagonalizable if and only if there exists an
eigenbasis in Fn (i.e., a basis consisting of
eigenvectors of A).
15.9 DO: Prove: a polynomial f has no multiple roots over the
complex numbers if and only if g.c.d.(f, f') = 1 (i.e.,
f is relatively prime to its derivative).
15.10 DO: (a) Prove: if the charcateristic polynomial of a matrix is
relatively prime to its derivative then the matrix is
diagonalizable over the complex numbers. (b) Show an n × n
matrix which is diagonalizable even though the
characteristic polynomial and its derivative are not
relatively prime.
15.11 HW: (a) Suppose a matrix
A is known to be diagonalizable; and the characteristic
polynomial of A is fA(t) =
(t+3)2(t-1)(t-5)3.
Find a diagonal matrix D which is similar to A.
Prove your answer.
(b) Prove that the matrix (1,1;0,1) is not diagonalizable.
(First row: 1,1; second row: 0,1.)
(Hint: if it were diagonalizable, to what diagonal matrix would
it be similar?) (5+5 points)
15.12 DO: exercise 13.25 reassigned, no longer as a "reward problem."
(Eigenvalues and eigenvectors of the shift operator on the
Fibonacci-type sequences)
15.13 DO: (a) Let A, B be n × n matrices.
Prove: trace(AB) = trace(BA). Use only the definition of
matrix multiplication. (b) Use (a) to give a half-line proof of the fact
that similar matrices have equal trace.
15.14 DO: Prove: if √2 is an eigenvalue of the matrix A
then A2-2I is not invertible.
15.15 DO: We stated (but did not prove) the following theorem in class:
over the complex numbers, every matrix is similar to an upper
triangular matrix. Use this to prove: (a) if the characteristic
polynomial of a matrix A is fA(t) =
(t - &alpha1) ... (t - &alphan)
then the characteristic polynomial of A2 is
fA2(t) =
(t - &alpha12) ...
(t - &alphan2).
(b) Let p be a polynomial. Then the characteristic
polynomial of the matrix p(A) is
fp(A)(t) =
(t - p(&alpha1)) ...
(t - p(&alphan)).
15.16 DO: Let Cn denote the adjacency matrix
of the directed
cycle of length n. Find the characteristic polynomial, the
eigenvalues, and the eigenvectors of Cn.
15.17 DO: Find the determinant of the n × n matrix
A = (αi,j) with the following entries:
αi,i-1 = -1, αi,i = 1,
αi,i+1 = 1 (for all i where both
subscripts are in [n]), all other entries are zero.
The answer will be appealing.
14.1 DO: Let φ : V → W be a linear map. Let
e=(e1 , ... , ek)
be a basis in V and
f=(f1 , ... , fm)
be a basis in W. Prove: for all v ∈ V
we have [φ(v)]f =
[φ]e,f[v]e.
14.3 DO: (muliplicativity of determinants) Prove:
det(AB) = det(A)det(B). Hint.
(a) Prove the result when A is a diagonal matrix.
(b) Prove the result when one of the rows of A is all zero.
(c) Perform elementary row operations on A and the same
row operations on AB simultaneously until we reach either
situation (a) or situation (b).
14.4 DO (prescribing a linear map on a basis):
Let V, W be vector spaces over the field F.
Let e=(e1 , ... , ek)
be a basis of V. Prove:
(∀ w1 ,..., wk ∈ W)
(∃! a linear map φ : V → W)(∀ i
∈ [k])
(φ(ei) = wi).
(The symbol "(∃! φ)" reads "there exists a unique φ
such that ...")
14.5 DO: Let dim(V) = k and dim(W) = m.
Let e be a basis of V and f a basis
of W.
Let Hom(V, W) denote the set of V → W linear
maps. (a) Prove that the function φ ↦
[&phi]e,f defines a bijection
between Hom(V, W) and Fm × k.
(b) Prove that Hom(V, W) is a vector space of dimension
mk.
14.6 DO (change of basis: change of coordinates):
Let e=(e1 , ... , ek)
and e'=(e1' , ... , ek')
be two bases of V (the "old" basis and the "new" basis).
We define the basis change transformation
σ : V → V by setting σ(ei) =
ei'. Let S = [σ]e
(the "basis change matrix"). (a) Prove that S is invertible.
(b) Prove: (∀ v ∈ V)([v]e' =
S-1 [v]e).
14.7 DO (change of bases: change of matrix): Let
φ : V → W. Let e, e' be two bases
of V and f, f' be two bases of W.
Let S be the basis change matrix corresponding to the
basis change e ↦ e' in V and let T
be the basis change matrix corresponding to the basis change
f ↦ f' in W. Let A be the matrix
of φ in the "old bases"
(i.e., A = [φ]e,f) and
A' the matrix of φ in the "new bases"
(i.e., A = [φ]e',f'). Prove:
A' = T-1AS. Hint.
Use Exx. 14.2 and 14.6. Start by writing φ(v) = w.
Translating this to matrix form you get matrix equations of the form
Ax = y (in the old bases) and A'x' = y' (in the new bases)
(explain the meaning of x, x', y, y'). Now
x' = S-1x and y' = T-1y
(by Ex. 14.6).
Therefore A'S-1x = T-1y,
so TA'S-1x = y = Ax. Now use
Ex. 14.2.
14.8 DO (similar matrices): Recall: the n × n
matrices A and B are similar if
(∃ nonsingular matrix S)(B = S-1AS).
Let us fix a basis e in the n-dimensional space V.
Prove: A and B are similar if and only if there exists
a basis e' of V and a transformation
φ : V → V such that
[φ]e = A and
[φ]e' = B.
14.9 DO: Prove: simlar matrices have the same (a) determinant; (b)
characteristic polynomial; (c) trace.
14.10 DO: review the expansion of a determinant by a row (or column).
Check the title "Laplace expansion" on Wikipedia.
14.11 DO: Review the definition of a field. (a) Show that the mod m
residue classes form a field if and only if m is a prime
number. (b) Prove: in a field, αβ = 0 ⇔
α = 0 or β = 0.
14.12 DO: Review the definition of a vector space V. Define a
basis as a linearly independent list of vectors that spans V.
Prove: a list L of vectors is a basis if and only if it is a
maximal linearly independent set if and only if every vector is a unique
linear combination of the vectors in L. (Prove from the
definition, do not use theorems such as the first miracle.)
14.13 DO: Prove: if φ : V → W is a linear map then
φ(0V) = 0W.
14.14 DO: Prove: if f : V → W is an isomorphism,
then f-1 : W → V is an isomorphism,
14.15 DO: Let e = (e1 , ... , en)
be a basis of V. Prove: the assignment
v ↦ [v]e is a
V → Fn isomorphism.
14.16 DO: Let φ : V → W be a linear map. Prove:
(a) Ker(φ) is a subspace of V;
(b) Im(φ) is a subspace of W;
(c)* (rank plus nullity theorem)
dim Ker(φ) + dim Im(φ) = dim(V).
Note: dim Im(φ) is called the rank of φ
and dim Ker(φ) the nullity of φ. This
explains the name of (c).
14.17 DO: Let ρθ denote the rotation of the
plane about the origin by θ counterclockwise.
(a) Compute the matrix of ρθ relative
to a basis consiting of two perpendicular unit vectors.
(b) Determine the complex eigenvalues and eigenvectors
of this matrix.
14.18 DO: Prove: the eigenvalues of an upper triangular matrix
are the diagonal elements.
All the above are due Mon, Dec 1. Check back later for the problems
due Wed, Dec 3.
13.1 DOa: Study the online "Linear Algebra Lecture Notes" (LIN)
(click "Text" on the banner on the class home page).
Specifically, study sections 1.1 (groups), 1.2 (fields),
3.1 (vector spaces), 3.2 (subspace, span, dimension, basis)
3.3 (first miracle), 3.5 (matrix rank, second miracle)
13.2 DOa: LIN 3.2.9 (the span of any set of vectors is a subspace)
13.3 DOa: LIN 3.2.16 (basis ⇔ every vector a unique lin comb)
13.4 DOa: LIN 3.2.17 (basis of space of polynomials)
13.5 DOb: LIN 3.2.18 (one polynomial of each degree ⇒ basis)
13.6 DOa: LIN 3.2.20 (every max lin indep set is a basis)
13.7 DOb: LIN 3.2.19 (every lin indep set can be extended to a basis;
every set of generators contains a basis) (a set of generators
is a set of vectors that spans the space)
13.8 DOb: LIN 3.2.4 (intersection of subspaces is a subspace)
13.9 HW (due Wed, Nov 26): LIN 3.2.5 (union of two subspaces)
(8 points)
13.10 DOa: if a list (v1,...,vn)
is linearly independent but the list
(v1,...,vn,w) is
linearly dependent then w ∈
span(v1,...,vn).
13.11 DOa: Prove that statements LIN 3.3.1 and LIN 3.3.2 are equivalent.
(these are two versions of the statement of teh First Miracle:
|L| ≤ |G| and "all bases are equal")
13.12 DOa: infer LIN 3.3.3 from the first miracle (rank = dim span)
13.13 DOb: LIN 3.3.6 (dimension invariance), LIN 3.3.9 (coordinates)
13.14 DOb: LIN 3.3.10 (size of finite vector space)
13.15 DOb: LIN 3.3.13 (modular equation), LIN 3.3.14 (submodular inequality)
13.16 DOb: LIN 3.5.6 (transpose of AB)
13.17 HW (due Wed, Nov 26): LIN 3.5.7 (rk(A+B)) (8 points)
13.18 DOb: LIN 3.5.8 (rk(AB ≤ min {rk(A), rk(B) })
13.19 HW (due Wed, Nov 26):
Find a basis in the subspace of Rn
consisting of the vectors x=(x1,...,
xn) such that x1+...+
xn = 0. (10 points)
13.20 DOb: Let R(n)[x] denote the space of polynomials
of degree ≤ n over R. Let f(x) be a polynomial
of degree n. Prove that the polynomials
f(x), f(x+1) ,..., f(x+n) form a basis of
R(n)[x]. (Hint: induction on n.)
13.21 DOb: Compute the characteristic polyomial of the
n × n "all-ones matrix" (every entry is 1).
Find its eigenvalues and their multiplicities (as roots of the
characteristic polynomial). Find an
eigenbasis (a basis consisting of eigenvectors).
13.22 DOa: Prove: elementary row operations do not change (a) the
row rank (b) the column rank. (Do not use the second miracle).
(c) Infer (prove from (a) and (b)) the second miracle.
13.22 DOa: Prove that the n × n matrix A
has an inverse if and only if its determinant is not zero.
13.23 DOb: LIN 3.6.2 (space spanned by shifted sine functions)
13.24 DOb: LIN 3.6.3 (space of Fibonacci-type sequences)
13.25 REWARD PROBLEM (due with the DOb problems):
Let Fib denote the space of Fibonacci-type sequences
from the preceding exercise.
(a) Let T : Fib → Fib
be the left shift transformation: b = Ta is defined by
bn = an+1. Find
the eigenvectors and eigenvalues of T.
(b) Infer the explicit formula for Fibonacci numbers.
13.26 DOb: Prove: the determinant of an (upper) triangular matrix is the
product of the diagonal elements. (An upper triangular matrix
has only zeros under the main diagonal: if i > j then
ai,j = 0.)
13.27 DOb: Let A(x,y) be the n × n matrix
with ai,i = x and
ai,j = y for j ≠ i.
Evaluate det(A(x,y)).
Your answer should be written as a product
of linear polynomials of x,y.
13.28 DOb: LIN 3.6.5 (rank of matrix
ai,j = i+j)
13.29 DOb: Find the rank of the n × n matrix with
entries ai,j = ij.
13.30 DOb: Prove: for almost all graphs G,
χ (G) ≥ (ω (G))100.
(χ (G) denotes the chromatic number;
ω (G) denotes the clique number (size of largest clique).)
12.1 DO: LN 8.1.5 (draw transition digraph corresponding to given
2 × 2 matrix; label the edges by transition probabilities)
12.2 HW: (a) Determine the (unique)
stationary distribution
corresponding to the transition matrix in the preceding problem.
(b) Prove that from any starting distribution q0,
the distributions qt will converge to the stationary
distribution. (5+10 points)
12.3 DO: LN 8.1.16 (if the powers of the transition matrix converge,
then every row of the limit is a stationary distribution)
correction posted 11-18, 3pm (previously problem number
LN 8.1.6 was given by error)
12.4 DO: Construct a transition matrix T and an
initial distribution q such that q is
not stationary but starting from q, in a finite number of
steps, the Markov Chain reaches a stationary distribution.
(Note that in Exercise 12.2, the distribution is not stationary
at any finite time.) Draw the transition digraph.
Use as few states as possible.
12.5 DO: Construct a weakly connected finite Markov Chain
with more than one stationary distribution. State two
stationary distributions. Use as few states as possible.
12.6 DO: Prove: if there are two stationary distributions then there
are infinitely many.
12.7 DO: LN 8.1.18 (random walk on the directed cycle of length n).
12.8 DO: Prove: the uniform distribution is stationary if and only if
the transition matrix is doubly stochastic.
12.9 DO: Prove: if the uniform distribution is stationary and the transition
digraph is weakly connected then it is strongly connected.
12.10 DO: Recall that a finite Markov Chain is irreducible if
the transition digraph is strongly connected. Prove: if an irreducible
finite M.C. has period > 1 then there exists a starting distribution
such that the process (the sequence of distributions) will not converge.
12.11 DO: recall that a finite Markov Chain is ergodic if it is
irreducible and aperiodic. Is the Markov Chain in Fig. 8.3
(LN Chap, p.89) ergodic?
12.12 DO: (a)* Prove that the product of an odd number of transpositions
is never the identity permutation. (b) Infer that half the permutations
is even, half is odd (find a bijection between even and odd permutations).
12.13 BONUS PROBLEM Prove that if we swap the squares 1 and 2 in
the initial configuration of Sam Lloyd's 15 puzzle then we get an infeasible
configuration (cannot be returned to the initial configuratin by a
sequence of legal moves). (6 bonus points)
12.14 DO: (a) Prove that the transpositions generate Sn.
(b) Prove that neighbor-swaps (transpositions (i,i+1)) generate
Sn.
12.15 DO (card shuffling) Let L be a nonempty subset
of Sn. Consider the Markov Chain of which the state
space is Sn; and the transitions are defined by
L: if we are in state s then the next state is
one of the states su for u ∈ L; each
u has the same probability 1/|L|. Prove:
(a) This Markov Chain is irreducible if and only if
L generates Sn.
(b) This Markov Chain is ergodic if and only if
L generates Sn and not all
members of L are odd permutations.
11.1 STUDY LN Chap 6.2 (Digraph terminology)
11.2 REVIEW conditional probabilities from LN and web sources
11.3 STUDY LN Chap 8, pp. 79-81 (first three pages of Markov Chains)
11.4 DO: LN 7.1.9 ("Theorem of Complete Probabilities")
11.5 HW: Diseases A and B have similar
symptoms. Let W be the population of all patients showing these
symptoms. The two diseases can only be differentiated by costly
tests. We know (from sampling the population and performing these
costly tests) that 70 % of W have disease A, 25 % have
disease B, and 5 % have some other disease. We consider the
effectiveness of treatment T. We know that 60 % of the patients
with disease A respond to T, while only 12 % of the patients
with disease B respond to treatment T. From the rest of the
population W, 40 % respond to treatment T.
(a) A new patient arrives at the doctor's office. The doctor
determines that the patient belongs to W. What is the probability
that the patient will respond to treatment T? (5 points)
(b) ("Probability of causes") The patient's insurance will not pay
for the expensive tests to differentiate between the possible causes
of the symptoms. The doctor bets on treatment T. A week later it
is found that the patient did respond to the treatment.
What is the probability that the patient had disease A?
(10 points)
11.6 BONUS PROBLEM: (a) Prove: if every vertex of a digraph G
has outdegree
≤ k then the chromatic number of G is
≤ 2k+1. (b) Prove that this bound is tight, i.e.,
for every k, prove that 2k colors may not suffice.
(What quantifier is hiding in the "may not" expression?)
(5+2 bonus points)
11.7 HW (good characterization of strong connectivity):
Prove: a digraph G is not strongly connected
if and only if there exists a one-way cut, i.e., if it is possible
to partition the vertex set V into non-empty parts
A, B such that all edges between A and B
go from A to B (so once in B, there is no way
back to A). (10 points)
11.8 DO: LN 6.2.15 (if indegree = outdegree for each vertex then
weak connectivity implies strong connectivity)
11.9 DO: LN 6.2.20 (a digraph has a topological sort if and only
if it is a DAG = directed acyclic graph)
11.10 HW: (period) Recall that the period
of vertex v in a digraph G is the g.c.d. of the lengths
of all closed walks through v. Prove: if v and
w are in the same strong component of G then they have
the same period. (10 points)
11.11 DO: Prove: if G is strongly connected then its period
(i.e., the period of each vertex) is the g.c.d. of the lengths
of all cycles in G.
11.12 DO: We say that G is a "k-cycle of blobs" if
the vertices can be arranged in k blocks
V1, ... ,Vk in
such a way the if (v,w) is an edge and
v ∈ Vi then
w ∈ Vi+1 where arithmetic on the
subscripts is mod k.
Prove: a strongly connected digraph G is a
k-cycle of blobs precisely if k divides
the period of G.
11.13 DO: (a) If G is a connected undirected graph
(modeled as a digraph with back-and-forth edges) then
G is strongly connected (as a digraph) and its period
is either 1 or 2. (b) Prove that the period is 2 exactly if
G is bipartite.
11.14 DO: LN 6.2.22 (powers of adjacency matrix count walks)
11.15 DO: (a) LN 8.1.6 (evolution of Markov Chains). First prove that
q(t+1) = q(t)T. (b) Prove that the k-step
transition matrix is Tk, i.e.,
P(Xt+k = j | Xt = i)
is the (i,j)-entry of Tk.
(Hint. Use the Theorem of Complete Probabilities.)
11.16 DO: Prove that the product of two stochastic matrices is
a stochastic matrix.
10.1 DO by Mon: LN 6.1.69 (simple arrow relations)
10.2 DO by Mon: LN 6.1.70 (Erdős - Szekeres)
10.3 DO by Mon: LN 6.1.71 (Hint: diagonal case of Erdős - Szekeres)
10.4 DO by Mon: r2 does not arrow (r+1,r+1)
(Done in class.)
10.5 HW due Wed, Nov 12: LN 6.1.72 (use three colors) (10 points)
10.6 DO by Mon: 6.1.67 (large independent set in planar graphs)
10.7 DO by Mon: 6.1.68 (4-coloring triangle-free planar graphs)
(Use only facts proved in class.)
10.8 HW due Wed, Nov 12: Prove: if a graph G is triangle-free
(has no K3 subgraph) then
χ(G) = O(&radic n). (Hint: use a separate strategy
for vertices of degree > √n.) (12 points)
10.9 HW due Wed, Nov 12: Let G be a random graph with
vertex set [n] where n ≥ 4. Let A denote the
event that vertex 1 has degree 3; and B the event that vertex 2
has degree 3. (a) Determine P(A). (b) Determine
the conditional probability P(A | B).
(For (a) and (b), give simple closed-form expressions.)
(c) Decide whether A and B are independent, positively
correlated, or negatively correlated. (Your answer should be
a function of n.) (d) Find the limit of the quotient
P(A | B)/P(A) as n → ∞. (3+7+5+3 points)
REVIEW:
9.1 DO (a) Prove: if a simple planar graph has at least 3 vertices and
no triangles then m ≤ 2n - 4. (b) Infer that
K3,3 is not planar.
9.2 HW: (a) Prove: almost all graphs are not planar. In other
words, let pn denote the probability that a
random graph on a given set of n vertices is planar.
Prove that lim pn = 0 (as n goes
to infinity). A random graph on a given set of n
vertices is constructed by flipping an unbiased coin (n
choose 2) times to decide adjacency between each pair of
vertices. (So for each pair (i, j) of vertices, the
probability that i and j are adjacent is 1/2
and these (n choose 2) events are independent.)
(b) Prove that for every ε > 0 and all sufficiently
large n, the probability that a random graph is planar
is less than 2-(1/2 - ε)n2.
(6+8 points; if you solved part (b), it earns
you all the 14 points since it also solves part (a))
(Hint to part (b): Chernoff)
9.3 DO: Prove: If the complete graph Kn
is represented as the union of k planar graphs
then k ≥ n/6.
9.4 DO: Let X be the number of triangles in a random
graph. (a) Determine E(X). (b) Detremine Var(X)
(give a closed-form expression involving binomial coefficients).
(c) Evaluate Var(X) asymptotically. Your answer should be
of the form cnd; determine the constants
c and d. (3+8+6 points)
9.5 DO (Inclusion-Exclusion, probability version): Let
A1,...,An be events
and let B be the complement of
A1 ∪ ... ∪ An.
Prove: P(B) = S0 - S1 + S2 - ...
where Sk is the sum of the probabilities of
the (n choose k) k-wise intersections
of the Ai. (So what is
S0 ?)
9.6 DO (Truncated inclusion-exclusion: Bonferroni's
inequalities): With the notation of the previous exercise,
let Ri denote the truncation of the right hand side
of the Inclusion-Exclusion formula at item i, i.e.,
9.7 HW: Prove: almost all graphs have no vertex of
degree ≥ 0.51n. (Hint: Chernoff) (10 points)
9.8 HW Prove: for all sufficiently large n,
the number of nonisomorphic trees on
n vertices is greater than 2.7n.
(10 points)
8.1 DO: Prove: if a graph is not complete then its chromatic number
is less than n.
8.2 HW: Let α(G) denote the independence number
of the graph G (size of the largest independent set)
and let χ(G) denote the chromatic number of G.
Prove: α(G)χ(G) ≥ n.
(8 points)
8.3 HW: Construct a graph G of chromatic number 4
which does not contain any triangles. Hint.
G should have 11 vertices and 5-fold symmetry.
(Draw the graph so that it remains unchanged if you rotate
the plane by 72 degrees.) (8 points)
8.4 DO: Prove: a graph G is a tree if and only if there is
exactly one path between every pair of vertices.
8.5 DO: Prove: every connected graph has at least n - 1 edges.
8.6 HW (due Wed, Nov 5): Prove that in a random graph, almost surely
each pair of vertices has a common neighbor. Hint: prove that the
probability that a particular pair (x,y) of vertices does not have a
common neighbor is exponentially small. Then use the union bound
to show that even the existence of such a pair is exponentially unlikely.
(10 points)
7.1 DO: Find random variables X,Y such that E(XY) = E(X)E(Y)
but X,Y are NOT independent. Make your sample space as small
as possible.
7.2. DO by Wednesday, Oct 29: (a) LN 7.4.4 (b) 7.4.5
(functions of disjoint blocks of independent
random variables are independent)
7.3. READ by Friday, Oct 24: Read the definitions in LN Section 6.1
(Graph Theory terminology) (read all but the exercises
on pp. 43-48)
7.4. DO: Prove: for every graph G, either G or
its complement is connected (or both).
7.5. DO: Prove: if in a graph there is a walk from vertex x to
vertex y then there is a path from x to
y.
7.6. DO: Prove: the distance in a graph is a metric (satisfies the
triangle inequality)
7.7. DO: prove that the graphs P4 (path of length 3)
and C5 (cycle of length 5) are self-complementary.
7.8. HW (Due Friday, Oct 24): LN 6.1.5 (if a graph is self-complementary
then n ≡ 0 or 1 mod 4). (6 points)
7.9. HW (Due Friday, Oct 24): LN 6.1.16 (draw all trees on 7 vertices,
one of each isomorphism type (i.e., do not draw isomorphic copies))
(9 points) (lose 2 points for each mistake (missing tree or
repeated tree)
6.1 STUDY asymptotic notation: little-oh, big-Oh, big-Omega, big-Theta
(all of LN Chap 2 except Sections 2.5 and 2.6). Remember the convention
that for the little-oh notation we replace 0/0 terms by 0.
6.2. DO: Prove:
If an ∼ bn
and an = o(bn)
then an = bn = 0 for all sufficiently
large n.
6.3. DO: LN 2.4.2 (asymptotic notation if limit of quotient exists)
6.4. DO: Find an , bn > 0
such that an = Θ (bn) but
limn → ∞ | an / bn |
does not exist.
6.5. DO: LN 2.4.7 (effect of the Θ relation on logarithms)
6.6. STUDY LN Chapters 7.1, 7.2, 7.4 (Finite probability spaces) with
special attention to the notions of independence and positive/negative
correlation of events
and conditional probability (7.1.6 - 7.1.18) and independence of
random variables (7.4) as well as the use of indicator variables
(from yur class notes as well as several exercised in Sec. 7.1).
6.7. HW: Find random variables X, Y, Z
such that they are pairwise
independent but not (fully) independent. Make your sample space
as small as possible. (10 points; 2 bonus points if you
give an elegant short proof that your sample space is indeed
the smallest possible.)
6.8. DO: Find events A, B, C such that they are pairwise
independent but not (fully) independent. Make your sample space
as small as possible.
6.9. DO: Prove: if events A and B satisfy the
equation P(A ∩ B)=P(A)P(B) then this equation remains
true if we replace either A or B or both by
their complements.
6.10. DO: Prove that events A, B and C are independent
(i.e., their
indicator variables are independent) if and only if
they are (a) pairwise independent and (b)
P(A ∩ B ∩ C) = P(A) P(B) P(C).
6.11. DO: Prove that the definition of independence of k events
given in class (their indicator variables are
independent) and the definition given in LN 7.1.16 are equivalent.
6.12. DO: Understand the meaning of equation (7.3) in LN, Def. 7.1.16
if |S| ≤ 1; show that in this case, the equation is
automatically satisfied.
6.13. DO: LN 7.1.25 (if we have n nontrivial independent events,
the sample space must have size ≥ 2n).
6.14. DO: LN 7.1.24 (k events that are (k-1)-wise
but not fully independent)
6.15. CHALLENGE PROBLEM. LN 7.1.26 (small sample spaces for pairwise
independent events)
6.16. CHALLENGE PROBLEM*. LN 7.1.27
(lower bound for sample spaces for
pairwise independent events) (Hint. Prove the same lower
bound for pairwise independent non-constant random variables with
zero expected value.)
6.17 HW: Consider a random string of length n over
the alphabet {A, B}. Let X denote the number of
occurrences of the substring AB and Y the
number of occurrences of the substring BA.
(Example: if the outcome of the experiment is ABBBAB
then X = 2 and Y = 1.) (a) Determine E(X).
(b) Prove that X and Y are not independent.
(8+8 points) Half the credit for part (a) goes for the accurate
definition of your random variables.
6.18 HW: Pick a random integer x ∈ [n].
Let A denote the event that x is even;
and B the event that 3 | x. (a) For n = 1000,
decide whether the events A and B are independent or
positively or negatively correlated. (6 points)
(b) REWARD PROBLEM.
Decide for what values of n are A and
B (i) independent; (ii) positively correlated;
(iii) negatively correlated.
5.0. If you have not done so yet, please respond (by email)
to the Questionnaire posted on the Course homepage.
5.1. DO: Quizzes 1 and 2 have been posted. (Go to the course home page
and click the "grading, tests" banner.) Solve the problems.
5.2. READING: LN Chapters 7.1, 7.2 (Finite Probability Spaces)
5.3. HW: Let pn
denote the probability that out f 2n coin flips,
exactly n come up Heads. (a) Give a simple exact
formula for pn.
(b) Prove: pn ∼ c/(√ n)
for some constant c. Determine c.
(2+8 points).
5.4. DO: Calculate the probability that a poker hand has two or more
cards of a kind.
(In the standard deck of 52 cards there are 13 kinds of cards
(Queen, 9, etc), and 4 cards of each kind.) (Hint: calculate the
probability that no two are of the same kind.) Your answer to the
question in the Hint should be a fraction reduced to lowest terms,
with both the numerator and the denominator written as a product
of primes. Do not use a calculator or computer.
5.5. DO: Let A be an event and let θA denote
its indicator variable. Prove: E(θA) = P(A).
5.6. DO: (a) Prove: if X is a random variable then
min X ≤ E(X) ≤ max X. (b) If equality holds
in either of these
inequalities then what can we say about X ?
5.7. DO: Prove: if X, Y are random variables (over the same probability
space) then E(X+Y) = E(X) + E(Y).
5.8. HW: LN 7.2.13 (club with 2000 members). Prove your answer.
Make sure you give
a clear definition of the random variables you use. The clarity of
the definition accounts for 3/4 of the credit. (8 points)
5.9. DO: Let us write down the numbers 1,...,n in a random order;
let r1,...,rn be the result
(all the n! sequences are equally likely). We say that a pair
{i,j} forms an inversion if
(i-j)(ri - rj) < 0.
Determine the expected number of inversions.
5.10. DO: find closed-from expressions for the generating functions of the
following sequences: (a) an = n ;
(b) bn = (n choose 2) ;
(c) cn = n2.
5.11. DO: Prove: ∑k=0n
(n choose k)2 = (2n choose n).
(a) Give a combinatorial proof. (b) Give an algebra proof (use the
Binomial Theorem).
5.12. HW: Prove that the binomial coefficients
(n choose k), k = 0,...,n,
increase till the middle and then decrease. (5 points)
5.13. REWARD PROBLEM. Prove that n+1 divides
(2n choose n). (The quotients are called "Catalan numbers.")
5.14. CHALLENGE PROBLEM. Let v(n) denote the number of distinct
prime divisors of n (so for instance v(24) = 2).
Let A(n) be the average of v(1),v(2),...,v(n).
Prove: A(n) ∼ ln ln n. (Hint: use the linearity
of expectation and the fact that
∑p ≤ n (1/p) ∼ ln ln n.)
Homework set #15. Due Wed, Dec 3. (Posted Sun, Nov 30, 6pm.
Note that Problem set #14 is due Mon, Dec 1.)
Homework set #14. All problem listed below are DO problems stated in class;
they are posted here for your convenience. They are due Monday, December 1.
(Posted Sun, Nov 30, 3:45pm.)
Remember: there will be a tutorial Thursday, December 4, 4:30pm.
The last class is Friday, December 5 (attendance mandatory).
14.2 DO: Let A,B be m × k matrices. Prove:
(a) The conditions x ∈ Fk, x ≠ 0,
and Ax = Bx do not imply A = B.
(b) If (∀ x ∈ Fk )(Ax = Bx)
then A = B.
Homework set #13. DOa problems (stated in class) due Monday, Nov 24.
DOb problems (not stated in class) due Tuesday, Nov 25, before tutorial.
HW problems due Wed, Nov 26. Posted Sun, Nov 23, noon.
Homework set #12. Due Wed, Nov 19. Posted Sat, Nov 15, 2:50pm.
(Don't forget: HW#11 is due Mon, Nov 17.)
Homework set #11. Due Mon, Nov 17. Posted Wed, Nov 12, 3:30pm.
Homework set #10. "DO" exercises due Mon, Nov 10. HW
due Wed, Nov 12. Posted Fri, Nov 7, 2:35 pm. (Don't forget
Homework set #9 which is due Monday, Nov 10.)
Homework set #9. Due Mon, Nov 10. Posted Wed, Nov 5, 9:30pm.
R0 = S0 ;
R1 = S0 - S1 ;
R2 = S0 - S1 + S2 ; etc.
Prove: if i is even then P(B) ≤ Ri; and if
i is odd then P(B) ≥ Ri.
Homework set #8. Due Mon, Nov 3: NEXT CLASS.
Posted Sun, Nov 2, 4am. (The HW problems were assigned in class
on Wed, Oct 29.) Problem 8.6 added on Mon, Nov 3, 5am; due Wed,
Nov 5. (This problem was stated in class on Fri, Oct 31.)
Homework set #7. Due Fri, Oct 24: NEXT CLASS, along with HW #6.
Posted Wed, Oct 22, 1:15pm.
Homework set #6 (due Fri, Oct 24, before class) Posted Mon, Oct 20, 3:20pm.
Homework set #5 (due Wed, Oct 22, before class) Posted Fri, Oct 17, 8:30pm.
Homework set #4 (due Fri, Oct 17, before class) Posted Mon, Oct 13, 2am.
Problems 4.18-4.26 were stated in Wednesday's class and were
added to the list below on Wednesday at 10:20pm.
4.1. HW: LN 4.1.17 (b) (c) (4+6 points) (muliplicative inverses) (for part (b), show your work, explain how you got your answer)
4.2. REVIEW: When does the congruence ax ≡ b mod m have a solution? State and prove the necessary and sufficient condition.
4.3. DO: LN 4.1.31 (no square root of -1 mod 103) This is an "AH-HA" problem; the solution should be just one line.
4.4. REVIEW the Chinese Remainder Theorem (CRT) on Wikipedia.
4.5. DO: LN 4.1.18 (CRT) Show your work! It is insufficient just to state the solution.
4.6. HW: LN 4.1.19 (CRT) Show your work! (8 points)
4.7. DO: LN 4.1.24 ("square root mod m," application of CRT)
4.8. DO: LN 4.1.26 (a) (b) (FlT with composite modulus)
4.9. HW: Compute 2N mod 37, where N =10300. Your answer should be a number between 0 and 36. Show all your work. Do not use a calculator or computer. Clearly state your intermediate results. None of your intermediate results should have more than three digits. (Hint: first calculate a value X such that 2X ≡ 2N mod 37, and 0 ≤ X ≤ 35.) (8 points)
4.10. REVIEW the Binomial Theorem and its proof on Wikipedia.
4.11. HW: LN 5.1.1. (Inductive proof of an identity involving binomial coefficients) (6 points)
4.12. DO: LN 5.1.2. (p divides "p choose k")
4.13. DO: LN 2.2.4, 2.2.5 (basic properties of asymptotic equality)
4.14. DO: LN 2.2.6 (asymptotic evaluation of certain sequences)
4.15. HW: LN 2.2.7 (find asymptotically equal sequences of positive numbers whose n-th powers are not asymptotically equal) (6 points)
4.16. DO: LN 2.2.9 (asymptotics of middle binomial coefficient)
4.17. HW: (a) Find two sequences an > 1
and bn > 1 such that
an ∼ bn
but ln an ≁ ln bn.
(b) Prove: if an > 1.001 and
an ∼ bn
then ln an ∼ ln bn.
(7+7 points)
4.18. DO: (a) Evaluate the Newtonian binomial coefficient (-1 choose n). (b) Use this to express (1-x)-1 as a power series; compare with what you have known about the sum of a geometric series.
4.19. DO: (a) Evaluate (-1/2 choose n) as a simple expression of "ordinary" binomial coefficients. (b) Use this to express (1-x)-1/2 as a power series. (c) Evaluate the coefficients asymptotically. (Your answer to (c) should be a very simple formula which does not involve binomial coefficients).
4.20. DO: Let f,g be formal power series and let the apostrophy denote the formal derivative. Prove: (fg)'=f 'g + fg'.
4.21. DO: Complete the proof given in class of the theorem that a formal power series has an inverse if an only if the constant term is not zero.
4.22. DO: Give a simple proof that lim Fn+1/Fn is the golden ratio, assuming the limit exists. (Use only the Fibonacci recurrence; do not use the explicit formula proved in class.)
4.23. DO: Prove: Fn is the integer nearest to (1/√5)gn where g is the golden ratio, g=(1+√5)/2.
4.24. DO: Give a closed form expression (no summation symbol or dot-dot-dots) for the generating function of the sequence {bn} defined by the recurrence bn=3bn-1 - bn-2 + 7bn-3 and the initial values b0=0, b1=0, b2=5.
4.25. DO: (a) Give a closed form expression for the generating function of the sequence {cn} defined by the recurrence cn = cn-1 + cn-2 + 1 and the initial values c0 = c1 = 0. (b) Give an explicit formula for cn. (Hint. Relate your sequence to the Fibonacci numbers, do not use the generating function.)
4.26. REVIEW this limit relation: limn → ∞ (1 + z/n)n = ez.
3.1 REVIEW concept of limit. Write the definitions as properly quantified expressions.
3.2 STUDY asymptotic equality (LN Chap 2.2)
3.3. DO: LN 1.2.5 (d)(f)(h) (logic and numbers)
3.4. DO: Prove: gcd(a-b,b) = gcd(a,b).
3.5. DO: LN 4.2.9 (gcd vs congruence)
3.6. DO: LN 4.1.27 (logic and gcd)
3.7. DO: Prove: if d is a common divisor of a and b and at the same time d is a linear combination of a and b then d is a greatest common divisor of a and b.
3.8. DO: LN 4.14 (a) (b) (compute gcd's using Euclid's Algorithm). In addition, find a representation of the gcd's obtained as linear combinations.
3.9. DO: LN 4.1.22 (a) (consecutive Fibonacci numbers are relatively prime)
3.10. REWARD PROBLEM: LN 4.2.6 (gcd of powers of a minus 1)
3.11. CHALLENGE PROBLEM (no point value but earns instructor's attention; no deadline): LN 4.2.8 (gcd of Fibonacci numbers)
3.12. DO: Prove the multiplicativity of Euler's φ function (see LN, Definition 4.3.25)
3.13. DO: LN 4.3.3 (summation of the φ function)
3.14. REWARD PROBLEM: Prove: inf φ(n)/n = 0 (where the infimum is taken over all positive integers). Hint: use the divergence of the sum ∑ 1/p and the inequality 1+x ≤ ex which holds for all real numbers x.
3.15. DO: LN 4.4.22 (sum of two squares never -1 mod 4) (done in class; review)
3.16. DO: LN 4.2.15 (existence of multiplicative inverse) (done in class; review)
3.17. REWARD PROBLEM: LN 4.2.16 (Wilson's Theorem)
3.18. DO: LN 4.2.17 - 4.2.20 (proof of the Euler-Fermat congruence; done in class; review)
3.19. DO: LN 4.1.23 (application of FlT to large exponent) Show your work! You may use a calculator for division but for nothing else.
3.20. CHALLENGE PROBLEM. LN 4.3.4. (Determinant of gcd's.)
3.21. CHALLENGE PROBLEM. LN 4.2.13 (Integer-preserving polynomials)
3.22. DO: LN 4.2.10 (Product of g.c.d. and l.c.m.)
3.23. DO: (a) Define the least common multiple in analogy with our definition of the greatest common divisor.
(b) Prove that l.c.m. exists. Hint: do not try to mimic the proof of the existence of a g.c.d.; use instead the fact that g.c.d. exist: represent the l.c.m. as the g.c.d. of a certain set of numbers (which numbers?).
3.24. DO: LN 4.1.27 (tiny questions on gdc, lcm, congruence mod 24)
3.25. DO: LN 4.1.30 (FlT mod 12,328)
3.26. DO: LN 4.1.21 (gcd vs congruence mod 5)
3.27. DO: Give an algebra proof of Pascal's Identity. (Use the Binomial Theorem.) (In class we gave a combinatorial proof.)
3.28. DO: Let En denote the number of even subsets of [n] and let On denote the number of odd subsets of [n]. (Recall the notation [n]={1,2,...,n}.) In class we gave an algebra proof of the fact that En=On (assuming n ≥ 1). Give a combinatorial proof of the same result. (Find a simple bijection between the set of even subsets and the set of odd subsets.)
3.29. DO: (a) Count the increasing functions
f : [k] → [n].
(b) Count the nondecreasing functions f :
[k] → [n]. Your answers should be
very simple formulas.
3.30. DO: Let an denote the number of those strings of length of length n over the alphabet {A,B} which have no consecutive occurrences of B. (For instance the strings ABAAAB and ABABAA should be counted, but the strings AAABBA and ABBBAB should not be counted toward a6.) Determine the number an. (Hint: experiment. Tabulate an for small values of n. Discover pattern, make a conjecture, prove.)
3.31. CHALLENGE PROBLEM. Let S3(n) denote the number of those subsets of an n-set of which the size is divisible by 3. Prove: |S3(n) - (2n/3)| < 1.
2.1. REVIEW mathematical induction.
2.2. HW LN 4.2.9 (members in a mod m residue class have the same common divisor with m) (6 points)
2.3. HW Calculate 3N mod m where m = 173 and N = 114,555. Your answer should be a number between 0 and 172. (173 is a prime) (6 points)
2.4. HW LN 4.1.33 (solve a congruence of degree 3p) (10 points)
2.5. CHALLENGE PROBLEM. LN 4.2.2, part 2. (Divisor game)
1.1. DO: review the concept of limits, especially at infinity. Define them using properly quantified formulas.
1.2. DO: Prove: every equivalence relation arises from a partition. (Two elements are equivalent if and only if they belong to the same block of the partition.)
1.3. DO: (a) When are two integers congruent modulo 1? (b) When are two integers congruent modulo 0?
1.4. HW: LN 1.2.5 (a)(b)(c) (5+5+5 points) (Numbers and quantifiers) Give clear TRUE/FALSE answers to each problem and prove your answers. The proofs should be very short.
1.5. DO: LN 4.1.15 (a)(b) (Number of divisors)
1.6. HW: LN 4.1.15 (c) (10 points) (Upper bound on the number of divisors)
1.7. HW: LN 4.2.12 (10 points) (Periodicity of the Fibonacci numbers modulo m).
1.8. DO: Study Euclid's Algorithm (LN Sec 4.1)
1.9. HW: Prove: there are infinitely many primes of the form 4k-1 (such as 3, 7, 11, 19, 23, etc.). Hint: modify Euclid's trick. (8 points)