# Assignments

______________________________________________________________________________________________________________________________________________________________ What's new | Course home | Policy on collaboration | #1 | #2 | #3 | #4 | #5 | #6 | #7 | #8 | #9 | #10 | #11 | #12 | #13 | #14 | #15 | #16 | #17 _____________________________________________________________________________________________________________________________________________________________
The notation "LN 4.1.15" refers to the Instructor's Lecture Notes, Chapter 4, problem 4.1.15.

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.

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.

### Homework set #15. Due Wed, Dec 3. (Posted Sun, Nov 30, 6pm. Note that Problem set #14 is due Mon, Dec 1.)

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.

### 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.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.2 DO: Let A,B be m × k matrices. Prove: (a) The conditions xFk, x ≠ 0, and Ax = Bx do not imply A = B.   (b) If (∀ xFk )(Ax = Bx) then A = B.

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 ,..., wkW) (∃! 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 ee' in V and let T be the basis change matrix corresponding to the basis change ff' 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.

### 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.

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).)

### Homework set #12. Due Wed, Nov 19. Posted Sat, Nov 15, 2:50pm. (Don't forget: HW#11 is due Mon, Nov 17.)

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.

### Homework set #11. Due Mon, Nov 17. Posted Wed, Nov 12, 3:30pm.

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.

### 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.)

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)

### Homework set #9. Due Mon, Nov 10. Posted Wed, Nov 5, 9:30pm.

REVIEW:

• LN Chap 7 (all of "Finite probability spaces," including Chernoff's inequality)
• LN Chapter 6.1 (graph terminology; ignore the bottom portion of p.55 starting with the section title "Ramsey Theory"). Make sure you understand Kuratowski's Theorem.
• MN 9.2, 9.3 (Finite probability spaces) pp. 269-284
• MN Chapters 3.1, 3.2 (graphs), 4.1 (trees)
• MN Chapter 5 (drawing graphs) In Chap 5.1 you may ignore the part about drawing graphs on surfaces other than the plane and the sphere.
• MN Chapters 7.1, 7.2, 7.4 (Cayley's formula with two proofs, including the Prüfer code)
• MN Chapters 2.7, 2.8 (Inclusion-Exclusion, the "derangement problem" (Hatcheck problem))
• MN Chap. 2.3, especially the Multinomial Theorem.

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.,
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.

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)

### 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.)

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)

### Homework set #7. Due Fri, Oct 24: NEXT CLASS, along with HW #6. Posted Wed, Oct 22, 1:15pm.

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)

### Homework set #6 (due Fri, Oct 24, before class) Posted Mon, Oct 20, 3:20pm.

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.

### Homework set #5 (due Wed, Oct 22, before class) Posted Fri, Oct 17, 8:30pm.

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 #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 axb 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 anbn but ln an ≁ ln bn.
(b) Prove: if an > 1.001 and anbn 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.

### Homework set #3 ("DO" problems related to past material; several of these have been assigned in class; due Wed, Oct 15. You do not have to hand in any of these problems.) Posted Mon, Oct 13, 2am. Problems 3.27-3.31 were stated in Monday's class and were added to the list below on Monday at 3pm.

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.

### Homework set #2 (was due Wed, Oct 8)

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)

### Homework set #1 (was due Fri, Oct 3)

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)