CMSC 37110-1: Discrete Mathematics

Autumn 2009

Current and recent homework assignments

Course home | Past homework (1-10) | Policy on collaboration | #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.

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 to a challenge problem, send email to the instructor giving the problem number and a 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.

REWARD PROBLEMS are challenge problems that you should NOT hand in. The solution is its own reward. No deadline. Of course you are welcome to discuss your thoughts with the TA, the instructor, and your peers.

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.

Go to top

Homework set #16 (due Friday, Dec 4, before class) [for Wednesday, do homework set #15 below!]

16.1 DO: Study Inclusion-Exclusion from MN, including the chapter "Hatcheck Lady & Co."

16.2 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 ?)

16.3 HW: (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.    (12 points)

16.4 NOTATION: Let V be a vector space over the field F and let e=(e1 , ... , ek) be a basis of V. Then every vector x ∈ V can be expressed uniquely as a linear combination x = ∑ αi ei. The αi are the coordinates of x with respect to the basis e; we write [x]e to denote the column vector [α1, ..., αn]T. (The superscript T indicates the transpose.)

16.5 NOTATION: Let V and W be vector spaces over the same field F. Recall that a linear map φ : V → W is a function that satisfies φ(x+y) = φ(x) + φ(y) and φ(αx) = αφ(x). Let now e = (e1 , ... , ek) be a basis in V and f = (f1 , ... , fm) be a basis in W. We associate with φ an m × k matrix A which we denote by A = [φ]e,f ; the j-th column of A is [φ(ej)]f.
If W = V then we call φ a linear transformation of V and use the notation [φ]e = [φ]e,e .

16.6 HW (a) Let V be the real plane and ρα the rotation of V by α about the origin. Let e = (e1, e2) be a pair of orthogonal (perpendicular) unit vectors. Find the matrix [ρα]e. Explain your answer.   (b) Let V be the space of polynomials of degree ≤ 3 over the field F. Let D : f ↦ f ' (where f ' is the derivative of f). D is a linear transformation of V. Determine the matrix [D]e, where e = (1, x, x2, x3) is the standard basis of V. (c) Compute the 4th power of this matrix. Explain what you found.     (5+5+2 points)

16.7 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 ...")
(b) Prove that the correspondence φ ↦ [φ]e,f described in 16.5 is a bijection between the V → W linear maps and the m × k matrices over F.

16.8 HW (Fibonacci shift): (a) Consider the space V consisting of all infinite sequences a = (a0, a1, ...) of real numbers. Let σ denote the left shift operator: σ(a) = (a1, a2, ...). Show that the eigenvectors of σ are precisely the geometric progressions. What are the eigenvalues of σ ?   (b) Let W be the subspace if V consisting of the sequences that satisfy the Fibonacci recurrence an = an-1 + an-2 (n ≥ 2). Show that the dimension of this "Fibonacci space" is 2; find a basis consisting of a sequence beginning with (0, 1, ...) and a sequence beginning with (1, 0, ...).   (c) Consider the shift operator on W. This is a linear trasformation of W. Find the 2 × 2 matrix B corresponding to this transformation with respect to the basis found in (b).   (d) Determine the eigenvalues of the shift operator on the Fibonacci space.   (e) Find an eigenbasis of the shift operator on the Fibonacci space. Each sequence should start with 1.   (f) Represent the Fibonacci sequece as a linear combination of the eigenbasis. Infer the explicit formula for Fibonacci numbers.    (4+4+4+4+4+4 points)

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

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

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

16.12 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. 16.10 and 16.11. 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. 16.11). Therefore A'S -1x = T-1y, so TA'S-1x = y = Ax. Now use Ex. 16.10.

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

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

Go to top

Homework set #15 (due Wednesday, Dec 2, before class)

15.1 DO: Prove: if the vector spaces Fn and Fm are isomorphic then n = m. (F is a field.)

15.2 DO: Let A be a k × n matrix and B be an n × k matrix over the field F. Prove: Tr(AB) = Tr(BA). Here "Tr" denotes the trace of a square matrix (sum of the diagonal elements). What are the dimensions of AB and of BA?

15.3 DO: Recall that the matrices A, B ∈ Mn(F) are similar if there exists a nonsingular matrix S ∈ Mn(F) such that B = S -1AS. Assume A and B are similar. Prove: (a) det(B) = det(A);   (b) fB(t) = fA(t) (where fA(t) = det(tI - A) is the characteristic polynomial);   (c) for every eigenvalue λ, the (c1) geometric (c2) algebraic multiplicity of λ is the same for A as for B. (Recall that the algebraic multiplicity of the eigenvalue λ of the matrix A ∈ Mn(F) is its multiplicity in the characteristic polynomial of A. The geometric multiplicity is the nullity of the matrix λI - A.)

15.4 DO: Let A ∈ Mn(F) and let fA(t) be its characteristic polynomial. Let fA(t) = a0 + a1x + ... + anxn. Prove:
    (a) an = 1   (b) an - 1 = - Tr(A)   (c) a0 = (-1)n det(A).

15.5 HW: Let λ1, ... , λn be the eigenvalues of A ∈ Mn(F) with the right (algebraic) multiplicities. Prove: (a) Tr(A) = ∑ λi ;   (b) det(A) = ∏ λi . You may use 15.4 without proof. (The sum and the product are for i = 1,...,n. The λi belong to the algebraic closure of F.)    (5+5 points)

15.6 DO: Prove: for every eigenvalue λ of A, the geometric multiplicity of λ is not greater than its algebraic multiplicity.

15.7 DO: Let A ∈ Mn(F) be an upper triangular matrix (all elements under the diagonal are zero). Prove that the eignevalues of A are precisely the diagonal elements, with the right algebraic multiplicity.

15.8 DO: A diagonal matrix is a square matrix with zeros everywhere outside the diagonal (diagonal entries may or may not be zero). For instance the zero matrix and the indentity matrix are diagonal matrices. A matrix A ∈ Mn(F) is diagonalizable if it is similar to a diagonal matrix. Prove: A is diagonalizable if and only if there exists an eigenbasis for A. (An eigenbasis for A is a basis of Fn which consists of eigenvectors of A.)

15.9 HW: Diagonalize Jn , the n × n all-ones matrix, i.e., find a diagonal matrix similar to Jn. Prove.    (6 points)

15.10 DO: Prove: the matrix A ∈ Mn(F) is diagonalizable if and only if the sum of the geometric multiplicities of its eigenvalues is n.

15.11 HW: Show a 2 × 2 matrix over C that is not diagonalizable. Prove. State the eigenvalues of your matrix along with their algebraic and geometric multiplicities. Prove. (Hint: make your matrix triangular. This will lead to very short proofs.)    (10 points)

Go to top

Homework set #14 (due Monday, Nov 30, before class; DO exercises due Tuesday, Dec 1, before the tutorial)

14.1 HW: Let   Jn denote the n × n "all ones" matrix (every entry is equal to 1). (a) Compute the characteristic polynomial of this matrix. Your answer should be a simple closed-form expression. (b) Determine the roots of the characteristic polynomial over R along with their multiplicities. (c) Find an eigenbasis for Jn, i.e., find a basis of Rn which consists of right eigenvectors of Jn.     (10+5+8 points)

14.2 HW: Let a1,...,an be distinct elements of the field F. Let f(x) = (x - a1)...(x - an). For i = 1,...,n, let gi(x) = f(x)/(x - ai). Prove: the polynomials g1, ... ,gn are linearly independent over F.   Clearly state what it is that you need to show. Your proof should be elegant, no more than five lines.     (10 points)

14.3 HW: (a) Study Gaussian elimination. (b) Let B = (bij) denote the n × n matrix with entries bij = i+j. Determine the rank of B over R.    (0+8 points)

14.4 HW: A (0,1)-matrix is a matrix whose entries are zeros and ones. Construct a 3 × 3 (0,1)-matrix whose columns are linearly independent over R but linearly dependent over F2. Prove your answers.     (8 points)

14.5 DO (due Tuesday, Dec 1, before the tutorial): (a) Let A be an n × n matrix over the field F. Let v1, ... ,vk be right eigenvectors of A corresponding to k distinct eigenvalues. Prove that v1, ... ,vk are linearly independent.   (b) Find an n × n matrix over the field F wich has an eigenbasis corresponding to just one eigenvalue (i.e., all the n vectors in the eigenbasis correspond to the same eigenvalue).   (c) Find a 2 × 2 matrix over Z which does not have an eigenbasis over C.

14.6 DO (due Tuesday, Dec 1, before the tutorial): Prove the second miracle: for every matrix (any shape, over any field), the row-rank and the column-rank are equal. (Hint: Gaussian elimination.)

14.7 DO (due Tuesday, Dec 1, before the tutorial): Let A and B be k × n matrices over the field F. Prove: rank( A + B) ≤ rank( A) + rank( B).

14.8 DO (due Tuesday, Dec 1, before the tutorial): Let F be a field. Prove: (a) if F has characteristic zero then F contains a subfield isomorphic to Q;   (b) if F has characteristic p then F contains a subfield isomorphic to Fp, the field of residue classes mod p.

14.9 CHALLENGE PROBLEM. Let a0,...,an-1 C. The circulant C = C(a0,...,an-1) is defined as the n × n matrix C = (cij) where cij = a (i-j) mod n. Find the eigenvalues of C as simple expressions involving the ai. - Hint: find a common eigenbasis for all n × n circulants.

14.10 (irreducibility over Q). (a) REWARD PROBLEM: Use the Gauss Lemma (about primitive polynomials) to prove that if an integral polynomial can be factored nontrivially over the rationals (i.e., into factors of lower degrees) then it can be factored nontrivially over the integers.   (b) CHALLENGE PROBLEM: Let a1,...,an be distinct integers. Let f(x) = (x - a1)...(x - an) - 1. Prove that f is irreducble over Q. (c) REWARD PROBLEM: Prove the Schönemann - Eisenstein irreducibility criterion: Let f(x)=a0 + a1x + ... + anxn be a polynomial over the integers. Let p be a prime number. Suppose p divides ai for i = 0,...,n-1 but p does not divide an; and further p2 does not divide a0. Prove that f is irreducible over the rationals.   (d) DO (based on (c)): Prove that xn - p is irreducible over Q for every n ≥ 1 and for every prime p.   (e) CHALLENGE PROBLEM: Prove that xn - 4 is irreducible over Q for every odd n. (f) CHALLENGE PROBLEM: Use the Schönemann - Eisenstein irreducibility criterion (plus a simple trick) to prove that for every prime p, the polynomial 1 + x + x2 + ... + xp-1 is irreducible over Q.

Go to top

Homework set #13 (due Wednesday, Nov 25, before class; the problems have been announced in class)

13.1 HW: Let A be an n × n complex matrix and let G = ([n], E) be the associated digraph ( i → j exactly if aij ≠ 0). Suppose G is strongly connected and has period d. Prove: if λ is an eigenvalue of A and ω is a complex d-th root of unity (i.e., ωd = 1) then λω is also an eigenvalue.    (8 points)

13.2 HW: Prove: if R is a finite integral domain then R is a field. Recall that an integral domain is a commutative ring with an identity element that is distinct from zero (so R has at least two elements) and with no zero-divisors, i.e., if ab = 0 then a = 0 or b = 0. The only thing you need to verify is that under the conditions stated, every nonzero element of R has a (multiplicative) inverse.    (8 points)

Go to top

Homework set #12 (due Friday, Nov 20, before class, except where indicated otherwise). Note that 12.7 requires you to read a chapter from MN, so even though that problem is only due Monday, Nov 23, take an early start on it.

12.1 HW (a Ramsey bound): (a) Define the Erdős - Rado arrow symbol n → (r,s,t). (b) Prove: 17 → (3,3,3).     (3+8 points)
(c) CHALLENGE PROBLEM: Prove that (b) is tight, i.e., 16 ↛ (3,3,3)   (16 does not arrow (3,3,3).   Hint: GF(16).

12.2 HW (convergence of a finite Markov Chain): LN 8.1.8. (Prove the convergence of the powers of a certain 2 × 2 stochastic matrix.) State the limit matrix. -- Your proof should be short. Elegance counts.     (8 points)

12.3 HW: LN 8.1.17. (Prove that the powers of certain 2 × 2 stochastic matrix do not converge; find a stationary distribution.)     (2 + 4 points)

12.4 HW: LN 8.1.24 (if a nonnegative matrix with strongly connected associated digraph has a nonnegative eigenvector then that eigenvector is positive). (A matrix is "nonnegative" if all entries are nonnegative. A matrix is "positive" if all entries are positive. The same definitions apply to vectors [which are 1 × n matrices].)     (10 points)

12.5 HW (due Monday, Nov 23): Solve problem 2(e) of the Third Quiz. (Go to the Course home page, then click "Grading, tests" on the banner, then click "third quiz.") The problem asks you to prove a Chernoff-style inequality for the number of occurrences of the substring ABA in a random string over the alphabet {A,B}. State explicitly the values of the constants c,d. -- Your solution should be short and elegant. If you cannot describe the essence of the solution in three lines, you are on the wrong track. (12 points)

12.6 HW (due Monday, Nov 23): Prove: for almost all graphs G we have χ(G) > (α(G))100.   (χ denotes the chromatic number, α the independence number. -- The entire solution should take no more than 6 lines.)     (8 points)

12.7 HW (due Monday, Nov 23): (a) A graph is planar if it can be drawn in the plane so that the edges don't cross. Study planar graphs from MN (MN2 Chapter 6; MN1, Chapter 5) (MNi: i-th edition of MN). Learn Kuratowski's Theorem and Euler's formula. (b) Understand MN2, Proposition 6.3.3 (MN1, Prop. 5.3.3) - that a planar graph with n ≥ 3 vertices has m ≤ 3n-6 edges. (c) Use (b) to prove that every planar graph has a vertex of degree ≤ 5. (d) Use (c) to prove the "six-color theorem:" every planar graph is 6-colorable. Your proof should be a very short induction.     (0 + 0 + 3 + 8 points)

12.8 DO (due Monday, Nov 23): Prove that for all sufficiently large n, the probability that a random graph is planar is less than 2-0.49n2.

12.9 CHALLENGE PROBLEM. Let S3(n) denote the number of those subsets of an n-set whose size is divisible by 3. Prove: |S3(n) - 2n/3| < 1.

Go to top

Homework set #11 (due Monday, Nov 16, before class. These problems were announced in class.)

11.1 HW: LN 6.2.27 (in a digraph, vertices in the same strong component have the same period)     (8 points)

11.2 HW: Prove: if C is a strong component of a digraph G then the period of any vertex in C is equal to the gcd of the lengths of all cycles contained in C. (Note: a cycle has no repeated vertices.)     (8 points)
Note: 11.1 follows from 11.2. A full solution to 11.2 also earns you full credit for 11.1 (but no extra credit, if you had a separate solution to 11.1). A partial solution to 11.2 may earn you zero credit for 11.1. On the other hand, it is possible to solve 11.2 using 11.1. Naturally, such a solution will earn you full credit for 11.2 but no credit for 11.1 (unless you separately solve 11.1).

11.3 DO: A digraph G=(V,E) is Eulerian if (∀ x ∈ V)( deg+ (x) = deg- (x)) (the out-degree of x is the same as the in-degree of x). A digraph is weakly connected if by ignoring orientation we get a connected graph.
Prove: if G is an Eulerian digraph and G is weakly connected then G is strongly connected.

Go to top

Here is the link to homework sets 1-10.


Unless otherwise stated, homework is always due the next class (before class). Please check the website for updates. The problems will be posted shortly after class. However, errors may occur, so please recheck the website, especially if you suspect an error. If you find an error or something that looks suspicious in an assignment, please notify the instructor (by email). If you are the first to point out an error, you may receive bonus points. "DO" problems are meant to check your understanding of the concepts. Do them but do not hand them in. If you encounter any difficulties, please check with teh TA during office hours. Challenge problems don't have a specific deadline except they cease to be problems once they have been discussed in class. If you are working on a challenge problem, please send email to the instructor so as to avoid the problem being discussed before you handed in the solution. Solutions to Challenge problems don't earn you credit toward your grade but they do earn you the instructor's respect, in addition to giving you valuable experience.

Go to top

Policy on collaboration

Studying in groups is strongly encouraged. Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give name of collaborator). DO NOT COPY someone else's solution: after the discussion, throw away any written records. Understand the ideas discussed and give your own rendering. The same applies to other sources such as the Web: give the source (URL), but DO NOT COPY. Understand; then write your own version without looking at the source or your notes.

View the instructor's class material from previous years

Return to the Department of Computer Science home page

Course home

Go to top