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 (second edition). The first edition is also entirely adequate for this class. Note that a new Chapter 2 has been inserted in the second edition so for $i\ge 3$ if you can find something in Chapter $i$ in the second edition, it will appear in Chapter $i-1$ in the first edition.
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.
Note: The last problem session will be held Thursday, Dec 4.
15.1 DO: Recall that a legal coloring of the directed graph ignores orientation of the edges: if two vertices are adjacent (in either direction), they must have a different color. Prove: a strongly connected directed graph is not 2-colorable if and only if it has an odd (directed!) cycle.
15.2 DO: Let $G$ be a digraph. Suppose every vertex has out-degree $\le k$. (a) Prove: $G$ is $(2k+1)$-colorable. (b) Show that the $2k+1$ bound is tight for every $k$, i.e., give an example where $2k$ colors do not suffice.
15.3 HW (rotation matrix): Let $$R_{\theta} = \left(\matrix{\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta}\right).$$ This is called the matrix of the rotation of the plane by $\theta$. Find the complex eigenvalues and eigenvectors of this matrix. Savor the result. (Hint: compute the characteristic polynomial. Use it to find the eigenvalues. For each eigenvalue, find the corresponding eigenvectors.) (8 points)
15.4 HW: Given a matrix $A\in M_n(\fff)$ (where $\fff = \rrr$ or $\ccc$), we say that a basis of $\fff^n$ is an eigenbasis of $A$ if the basis consists of eigenvectors of $A$. (a) Consider the matrix $A = \left(\matrix{1 & 1 \\ 0 & 1}\right)$. Compute the characteristic polynomial of this matrix. Find its eigenvalues and eigenvectors. Prove: this matrix does not have an eigenbasis. (b) Consider the matrix $B = \left(\matrix{1 & 1 \\ 0 & 2}\right)$. Find its eigenvalues. Prove, without any computation, that this matrix has an eigenbasis. (6+6 points)
15.5 HW: (a) Consider the $n\times n$ matrix $M = \left(\matrix{a & b & b & \cdots & b \\ b & a & b & \cdots & b \\ b & b & a & \cdots & b \\ \vdots & & & \ddots & \vdots \\ b & b & b & \cdots & a \\ }\right)$.
(All diagnal elements are equal to $a$ and all off-diagonal elements
are equal to $b$.)
Determine $\det(M)$. Your answer should be a simple closed-form expression.
(Hint. Use Gaussian elimination to obtain a triangular matrix.
Your first step should be to add each of the first $(n-1)$ rows to the
last row.)
(b) Let $J$ be the $n\times n$ all-ones matrix (every entry is 1).
(b1) Find the characteristic polynomial of $J$. (Hint: use part (a).)
(b2) Determine the eigenvalues of $J$ and their multiplicities
(in the characteristic polynomial). (b3) Find an eigenbasis
of $J$.
(8+3+4+6 points)
14.1 DO: Let $G=(V,E)$ be a digraph and $x,y\in V$. Suppose there is a directed walk $x\to\dots\to y$. Prove: there is a directed path $x\to\dots\to y$ (no repeated vertices).
14.2 DO: Review gcd of a (possibly infinite or possibly empty) set of integers. Prove: it exists and it is a (finite!) linear combination.
14.3 HW (due Thu, Dec 4): Prove: if $x,y$ are vertices and they belong to the same strong component of $G$ then their periods are equal. (8 points)
14.4 DO: Prove: a digraph $G$ is a DAG $\iff$ $G$ has a topological sort.
14.5 DO: Let $T$ denote the transition matrix of a finite Markov Chain. Prove: $T^j$ is the $j$-step transition matrix.
14.6 DO: Prove: if $A,B$ are $n\times n$ stochastic matrices then so is $AB$.
14.7 DO (evolution of Markov Chains): Let $q(t)$ denote the distribution of the particle at time $t$. Then $q(t+1)=q(t)T.$ Consequently, $q(t)=q(0)T^t$.
14.8 DO: Prove: the uniform distribution is stationary $\iff$ $T$ is doubly stochastic.
14.9 DO: Prove: a digraph $G=(V,E)$ is not strongly connected $\iff$ $V$ can be split into two parts, $A$ and $B$ ($A\cup B=V$, $A\cap B=\emptyset$, $A,B\neq \emptyset$) such that there is no edge going from $B$ to $A$. (This is a "good characterization.")
14.10 DO: Consider the simple random walk on a connected undirected graph. Find its stationary distribution in terms of basic parameters of the graph.
14.11 DO: Prove: If a Markov Chain is irreducible (strongly connected) then its stationary distribution is unique.
14.12 DO: Prove: If a Markov Chain is ergodic then $\lim T^k$ exists.
14.13 DO: Prove: if $\lim T^k$ exists then its rows are stationary distirbutions.
14.14 DO: Prove: the determinant of a triangular matrix is the product of the diagonal.
14.15 DO: Prove: elementary row and column operations do not change the value of a determinant.
14.16 DO: Prove: if we switch two columns then the determinant changes sign (is multiplied by $-1$).
14.17 DO: If a column of the matrix $A$ is zero, or if two columns are equal, then $\det(A)=0$.
14.18 DO: Prove: $\det(A^T)=\det(A).$ (Here $A^T$ denotes the transpose of $A$.)
14.19 DO: Prove: for an $n\times n$ matrix $A$ we have $\det(A)=0$ if and only if the columns of $A$ are linearly dependent, i.e., $\rank(A) < n$.
14.20 TERMINOLOGY. An $n\times n$ matrix $A$ is non-singular if it has full rank. Equivalently, if $\det(A)\neq 0$. As we saw previously, this is also equivalent to the existence of $A^{-1}$ and a long list of other properties, including this one: the homogeneous system $Ax=0$ of linear equations has no non-trivial solution.
14.21 DO: Prove: $\lambda$ is an eigenvalue of $A$ if and only if $\det(\lambda I - A) =0$.
14.22 DO: Prove: the right eigenvalues of a square matrix are the same as its left eigenvalues.
More problems will follow, please check later.
13.1 DO: Prove: $\rank(AB) \le \rank(B)$
13.2 HW: Prove: $\rank(A+B)\le \rank(A)+\rank(B)$. Here $A$ and $B$ are $k\times \ell$ matrices. Make your proof simple; elegance counts. (8 points)
13.3 HW: Find an $n\times n$ matrix $A$ of rank $n-1$ such that $A^n=0$. (8 points)
13.4 HW: Prove: if the $n\times n$ matrix $A$ has rank $n$ then $(\forall k)(\rank(A^k) = n)$. (4 points)
13.5 DO: An $n\times n$ matrix is called non-singular if it has full rank. In class we have seen that this condition is equaivalent to a number of other conditions, including invertibility. Add the following equivalent condition: the system $Ax=0$ of homogeneous linear equations ($n$ equations in $n$ unknowns) has no non-trivial solution. (Prove that this condition is also equivalent to $A$ being non-singular.) Here $x = (x_1,\dots,x_n)^T$ is a column vector with $n$ entries; the superscript $T$ stands for "transpose."
13.6 HW (due Tue, Dec 2): Prove: the rank of the matrix $A$ is the largest $k$ such that $A$ contains a non-singular $k\times k$ submatrix. (6 points)
13.7 HW (due Tue, Dec 2) We have seen that the space of Fibonacci-type sequences has dimension 2 and has a basis consisting of two geometric progressions, $e_i=(1,\lambda_i,\lambda_i^2,\lambda_i^3,\dots)$, where $\lambda_i = (1\pm\sqrt{5})/2$ $(i=1,2)$. Recall that the Fibonacci sequence is the sequence $f=(0,1,1,2,3,5,8,13,21,\dots)$. Represent the Fibonacci sequence as a linear combination of $e_1$ and $e_2$. Infer an explicit formula for the $n$-th Fibonacci number $F_n$. (Here $F_0=0, F_1=1,$ and $F_n=F_{n-1}+F_{n-2}$.) (5 points)
13.8 DO: Find the elements of the matrix $B^n$ where $$B = \left(\matrix{1 & 1 \\ 1 & 0}\right).$$
13.9 DO: Find the elements of the matrix $C^n$ where $$C = \left(\matrix{1 & 1 \\ 0 & 1}\right).$$
13.10 DO: Prove: $(AB)^T = B^TA^T$. (Again, the "T" stands for "transpose.")
13.11 DO: Prove: $\rank(AA^T) = \rank(A)$.
13.12 DO: Let $V$ be a finite-dimensional vector space. Prove that every linearly independent set can be extended to a basis.
13.13 DO: (a) Prove: If $U,V$ are subspaces of the vector space $W$ then $U+V$ is also a subspace. (Here, as before, $U+V=\{u+v \mid u\in U, v\in V\}$.) (b) Prove: $\dim(U+V)\le \dim(U)+\dim(V)$.
13.14 DO: Let $U,V$ be subspaces of the vector space $W$. Prove: $\dim(U) + \dim(V) = \dim(U\cap V) + \dim(U+V)$.
13.15 DO: (a) Study the Inclusion-Exclusion formula. (b) Study the derangement problem as an application of Inclusion-Exclusion. (Can be found in the two printed texts listed on the course home page: Matoušek -- Nešetříl, and Rosen.) (c) Let $L_n$ be the set of those $n$-digit integers of which every digit is odd and every odd digit actually occurs in them. Find $|L_n|$. Your answer should be a closed-form expression.
13.16 DO: We say that a digraph $G=(V,E)$ is Eulerian if for every vertex $v$ we have $\deg^+(v)=\deg^-(v)$ (the out-degree is equal to the in-degree). Prove: if the digraph $G$ is Eulerian and weakly connected then it is strongly connected. ("Weakly connected" means it becomes connected as an undirected graph if we ignore the orientation of the edges.)
13.17 DO: A topological order of the vertices of a digraph with $n$ vertices is a numbering of the vertices $1$ to $n$ such that if $i\to j$ is an edge then $i< j$. Prove: a topological order exists $\iff$ $G$ is a DAG (directed acyclic graph, i.e., $G$ has no directed cycles).
13.18 DO: The adjacency matrix of a digraph with vertex set $[n]$ is an $n\times n$ matrix $A=(a_{ij})$ such that $a_{ij}=1$ if $i$ and $j$ are adjacent, $a_{ij}=0$ otherwise. In particular, $a_{ii}=0$ unless there is a self-loop at vertex $i$. Let $b_{ij}(k)$ denote the $(i,j)$ entry of the matrix $A^k$. Prove: $b_{ij}(k)$ counts the $i\to\dots\to j$ walks of length $k$.
13.19 HW (due Tue, Dec 2): Let $A$ be the adjacency matrix of the digraph $G$ with $n$ vertices. Prove: $A^n = 0$ $\iff$ $G$ is a DAG. (6 points)
13.20 HW (due Tue, Dec 2): The trace of the $n\times n$ matrix $A$ is the sum of its diagonal elements: If $A=(a_{ij})$ then $\trace(A)=\sum_{i=1}^n a_{ii}$. Prove: if $A\in\rrr^{k\times \ell}$ and $B\in\rrr^{\ell\times k}$ then $\trace(AB)=\trace(BA)$. (4 points)
13.21 DO: Let $A$ be the adjacency matrix of an undirected graph $G$. Notice that $\trace(A)=0$ because all diagonal elements are zero. Express (a) $\trace(A^2)$ and (b) $\trace(A^3)$ in terms of simple parameters of the graph.
12.1 HW: Midterm bonus problem #8. Note: this problem as stated in the midterm had an error. The updated midterm is posted here. (8 points)
12.2 HW: Midterm bonus problem #9. (6 points)
12.3 HW (due Tuesday, Nov 25): Midterm bonus problem #12. (10 points)
12.4 HW (due Tuesday, Nov 25): Midterm bonus problem #11. (8 points)
12.5 READ: directed graph concepts (from LN): in-degree, out-degree, directed walks, paths, closed walks, cycles, strong components, DAG (directed acyclic graph), topological sort, tournament, etc.
12.6 HW: Prove: every strongly connected tournament has a Hamilton cycle. (8 points)
12.7 DO: Let $S$ be a subset of the vector space $V$. Prove: $S\le V$ ($S$ is a subspace) $\iff$ $S=\span(S)$.
12.8 DO: Prove: The union of two subspaces is a subspace $\iff$ one of the subspaces contains the other.
12.9 CHALLENGE: Prove: the union of a finite number of subspaces is a subspace $\iff$ one of them contains all the others.
12.10 DO: Let $v_1,\dots,v_{k+1}$ be vectors in a vector space $V$. Prove: if $v_1,\dots,v_{k}$ are linearly independent but $v_1,\dots,v_{k+1}$ are linearly dependent then $v_{k+1}\in \span(v_1,\dots,v_{k})$.
12.11 DO: Recall: a basis is defined as a linearly independent set of generators. (a) Prove: every maximal linearly independent set is a basis. (b) Infer that every vector space has a basis; in fact, every linearly independent set can be extended to a basis. Assume for the proof that there is a $k$ such that every linearly independent set has at most $k$ elements. (The result is true without this assumption but the proof in the general case requires Zorn's Lemma.)
12.12 DO: Recall the First Miracle of Linear Algebra: In a vector space $V$, all bases have the same cardinality (same number of vectors). Prove that this statement is equivalent to the following: In a vector space, all maximal linearly independent sets are maximum.
12.13 DO: Find a very simply described basis in $\rrr^n$. Use this and the First Miracle to prove that every set of $n+1$ vectors in $\rrr^n$ is linearly dependent.
12.14 DO: Recall that the dimension of a vector space is the common cardinality of it bases. So for instance $\dim(\rrr^n)=n$ (because it has a basis of size $n$ according to the preceding exercise). Recall that the rank of a set of vectors is the maximum number of linearly independent vectors among them. Prove: if $S\subseteq V$ then $\rank(S) =\dim(\span(S))$.
12.15 DO: Find a very simply describe basis in the space $\rrr[t]$ of polynomials. (Note: the basis will be infinite.)
12.16 DO: Given a list $v_1,\dots,v_k$ of vectors, an elementary row-operation consists of picking two indices $i\neq j$ and a scalar $\lambda$ and replacing $v_i$ by $v_i -\lambda v_j$. For example, if $a,b,c$ is a list of three vectors, the an elementary operation mat turn this list into $a,b-3c,c$. Prove that elementary operations do not change the rank of a list of vectors.
12.17 DO: Define the column-rank of a $k\times\ell$ matrix $A$ as the rank of the list of columns of $A$ (regarded as vectors in the space $\rrr^k$). The row-rank is defined analogously. An elementary column operation is an elementary operation, as defined in the preceding problem, applied to the list of columns. Elementary row operations are defined analogously. Prove: (a) Elementary column operations do not change the column-rank of a matrix. (Note: this question is essentially the same as the preceding exercise.) (b) The row-rank does not change under elementary column operations. (Note: this is a very different exercise.)
12.18 DO: Suppose a martix has at most one non-zero element in every row and in every column. Prove that both the row-rank and the column-rank of such a matrix is equal to the number of its non-zero entries.
12.19 DO: Prove that by making a sequence of elementary column and row-operations, every matrix can be brought to the form described in the preceding exercise (at most one non-zero entry in every row and in every column).
12.20 DO: Prove the Second Miracle of Linear Algebra: for every matrix, the column-rank and the row-rank are equal. (Hint: use the three preceding exercises.)
12.21 HW: Determine the rank of the following $3\times 3$ matrix: $$A = \left(\matrix{1 & 3 & -3 \\ 5 & -1 & 6 \\ 7 & 5 & 0}\right).$$ Show and describe each step (state whether row or column operation and state the triple $(i,j,\lambda)$ you use). (Note: Often the following operations are also called "elementary column operations": swapping columns or multiplying a column by a non-zero scalar. The concept of "elementary row operations" is expanded analogously. Do NOT use these additional operations.) (7 points)
12.22 HW: Determine the ranks of the following $n\times n$ matrices: (a) $A_n= (a_{i,j})$ where $a_{i,j} = i+j$; and (b) $B_n= (b_{i,j})$ where $b_{i,j} = ij$. For instance, $$A_3 = \left(\matrix{2 & 3 & 4 \\ 3 & 4 & 5 \\ 4 & 5 & 6}\right)$$ and $$B_3 = \left(\matrix{1 & 2 & 3 \\ 2 & 4 & 6 \\ 3 & 6 & 9}\right)$$ (6+6 points)
11.1 HW: Let $\vf\,:\, V\to V$ be a linear transformation and let $v_1,\dots,v_k$ be eigenvectors to distinct eigenvalues. Prove: $v_1,\dots,v_k$ are linearly independent. (8 points)
10.1 CHALLENGE (almost disjoint sets). Let us say (for the purposes of this problem only) that two sets $A$ and $B$ are almost disjoint if $|A\cap B|\le 1$. Let us fix an integer $k\ge 2$. Prove: there exists $\Omega(n^2)$ almost disjoint $k$-subsets of $[n]$.
10.2 HW: Let $k\ge 2$ be fixed. Prove: the probability that a random graph on $n$ vertices does not contain a clique of size $k$ is $\exp(-\Omega(n^2))$. (Notation: $\exp(x)=\eee^x$.) Use 10.1. (6 points)
10.3 HW: Let $G$ be a triangle-free graph on $n$ vertices. Prove: $\chi(G) \le 2\sqrt{n}+1$. (10 points)
10.4 DO: Let $d(n)$ denote the number of positive divisors of the positive integer $n$. Prove: $d(n) < 2\sqrt{n}$.
10.5 CHALLENGE (average number of divisors). Let $X$ be a random number from $[n]$. Prove: $E(d(X)) \sim \ln n$.
10.6 CHALLENGE (Mario Szegedy). A graph $G$ is vertex-transitive if for every pair $x,y$ of vertices there is an automorphism of $G$ (i.e., a $G\to G$ isomorphism) that sends $x$ to $y$. Prove: if $G$ is vertex-transitive then $\alpha(G)\chi(G)\le n(1+\ln n)$.
10.7 DO: The girth of a graph is the length of its shortest cycle. The girth is $\infty$ if the graph has no cycle. Determine the girth of (a) $K_n$ (b) $K_{r,s}$ (c) the $k\times \ell$ grid (d) the dodecahedron (e) Petersen's graph.
10.8 DO: (a) Prove: if $G$ is a regular graph of degree $k$ and girth $\ge 5$ then $G$ has $n\ge k^2+1$ vertices. (b) Show that under the conditions of part (a), $n=k^2+1$ is possible for $k=1,2,3$. (Comment: The Hoffman--Singleton Theorem states that the only values of $k$ for which $n=k^2+1$ is possible are $k=1,2,3,7,$ and maybe $57$. The proof uses the Spectral Theorem of linear algebra.)
10.9 HW: A tournament is an orientation of the complete graph: every edge $\{u,v\}$ becomes an arrow: either $u\to v$ or $v\to u$. (This represents the outcome of a "round-robin tournament" where each player plays against every other player exactly once. (The players are the vertices.)) Prove: every tournament has a Hamilton path, i.e., it is possible to line up the players so that each player beat the player behind him/her in the line. (6 points)
10.10 HW (the probabilistic method, Paul Erdös): In a tournament we say that player $u$ dominates the set $A$ of players if $(\forall v\in A)(u\to v)$ (player $u$ beat each player in $A$). We say that a tournament with $n$ vertices is $k$-paradoxical if every set $A$ of $\le k$ players is dominated by some player. Prove that for every $k$ there exists a $k$-paradoxical tournament. Use the probabilistic method: rather than trying to construct such a tournament (a difficult task already for $k=2$), prove that for a fixed $k$, almost all tournaments are $k$-paradoxical. (In a random tournament, the outcome of each match is decided by flipping a coin.) What is the size of the sample space for this experiment if there are $n$ players? (12+2 points) (The 2 points for the size of the sample space.)
10.11 HW: Prove that the following vectors in $\rrr^4$ are linearly dependent (not linearly independent): ${\mathbf a}=(-3,0,8,5)$, ${\mathbf b}=(1,-2,-6,1)$, ${\mathbf c}=(2,5,3,-10)$. You need to find the coefficients $x,y,z$ in a nontrivial linear combination that gives the zero vector: $x{\mathbf a}+y{\mathbf b}+z{\mathbf c}=(0,0,0,0)$. ("Nontrivial" means $x=y=z=0$ is not allowed.) Although in general the coefficients $x,y,z\in\rrr$ can be arbitrary real numbers, your coefficients in this case should be integers; minimize the sum of their absolute values. You do not need to prove that your solution is minimal. Your answer should be the list of three coefficients. Show how you obtained your answer. Merely stating the answer and checking its correctness earns you 1 point. You need to show a systematic way how to arrive at the answer for this type of questions. (6 points)
10.12 DO: Prove: If a polynomial $f(t)=c_0+c_1 t + c_2t^2+ \dots + c_nt^n$ has degree $n$ (i.e., $c_n\neq 0$) then $f$ has at most $n$ roots (zeros).
10.13 HW: Let $a_1 < a_2 <\dots < a_n \in \rrr$.
Prove that the following $n$ vectors in $\rrr^n$ are
linearly independent:
${\mathbf v_0} = (1,1,1,\dots,1)$
${\mathbf v_1} = (a_1,a_2,a_3,\dots,a_n)$
${\mathbf v_2} = (a_1^2,a_2^2,a_3^2,\dots,a_n^2)$
$\dots$
${\mathbf v_{n-1}} = (a_1^{n-1},a_2^{n-1},a_3^{n-1},\dots,a_n^{n-1})$
Hint: use the preceding exercise.
(8 points)
10.14 HW: Let $a_1 < a_2 <\dots < a_n \in \rrr$. Consider the polynomial $f(t)=\prod_{j=1}^n (t-a_j)$. Note that $f$ has degree $n$. For $i=1,\dots, n$, define the polynomial $g_i(t)= f(t)/(t-a_i)$. (Delete one term from the product that defines $f$; note that each $g_i$ has degree $n-1$.) Prove that the polynomials $g_1,\dots,g_n$ are linearly independent in the space $\rrr[t]$ of polynomials. (Note: at the end of class, the special case $n=4$ was stated. Consider that special case a "warm-up" exercise, do not hand in. Solve the problem for general $n$.) The solution should be very simple, a few lines only. Complicated solutions will not be graded. (10 points)
10.15 HW: Consider the following sets of polynomials. In each
case, decide whether or not the given set is a subspace of the space
$\rrr[t]$ of polynomials. Convention: the degree of the identically zero
polynomial (all coefficients zero) is $-\infty$.
(a) $A = \{f\in\rrr[t] \mid \deg(f)=5 \}$
(b) $B = \{f\in\rrr[t] \mid \deg(f)\le 5 \}$
(c) $C = \{f\in \rrr[t] \mid f(\sqrt{2}) = 0 \}$
(d) $D = \{f\in \rrr[t] \mid f(\sqrt{-1}) = 0 \}$
(e) $E = \{f\in \rrr[t] \mid f(1) = f(2) \}$
(f) $F = \{f\in \rrr[t] \mid f(1) = 5f(2) \}$
(g) $G = \{f\in \rrr[t] \mid f(1) = 5f(2)+2f(3) \}$
(h) $H = \{f\in \rrr[t] \mid f(1) = 5f(2)+2f(3)+1 \}$
(i) $I = \{f\in \rrr[t] \mid f(1) = (f(2))^2 \}$
(j) $J = \{f\in \rrr[t] \mid (f(1))^2 = (f(2))^2 \}$
(k) $K = \{f\in \rrr[t] \mid f(1)f(2) = 0 \}$
(l) $L = \{f\in \rrr[t] \mid f(1) \ge f(2) \}$
Clearly state YES (subspace) or NO (not a subspace) for each
question. In each case that your answer is NO, prove your answer.
You do not need to prove your YES answers. Remember: to prove a NO
answer, you need to give a concrete counterexample.
(15 points; lose 4 points for each wrong answer and
up to 3 points for each correct "NO" answer if the proof is wrong or missing.
Lose up to 2 points for each correct proof that is
unnecessarily complicated)
10.16 HW: Prove that $\rrr^2$ has infinitely many subspaces. (5 points)
10.17 DO: Let $V$ be a vector space. (a) Prove: the intersection of two subspaces is a subspace. (b) The intersection of any number of subspaces (possibly infinitely many subspaces) is a subspace. (c) When is the union of two subspaces a subspace? Give a very simple characterization, of this form: "The union subspaces $A$ and $B$ is a subspace if and only if (some simple statement about $A$ and $B$)."
10.18 CHALLENGE: (a) Let $X_1,\dots,X_k$ be random variables over the same probability space. Assume $E(X_1)=\dots=E(X_k)=0$ and $\var(X_1)=\dots=\var(X_k)=1$. Prove: if the $X_i$ are pairwise uncorrelated then they are linearly independent (as functions $\Omega\to\rrr$). (b) Infer from this that over a sample space of size $n$ there cannot be more than $n-1$ pairwise independent nontrivial events.
MORE PROBLEMS TO FOLLOW; PLEASE CHECK BACK LATER.
9.0 DO: Prove: a disconnected graph with $n$ vertices has at most $\binom{n-1}{2}$ edges.
9.1 DO: Prove: If $G$ is a graph with $n\ge 2$ vertices then either $G$ or its complement must be connected.
9.2 DO: Let $\diam(G)$ denote the diameter of the graph $G$. Prove: (a) If $G$ has $n$ vertices then $\diam(G)\le n-1$. (b) $\diam(G)=n-1$ if and only if $G = P_n$ (the path of length $n-1$).
9.3 DO: Determine the diameter of (a) the complete bipartite graph $K_{r,s}$ and (b) the $r\times s$ grid.
9.4 DO: A cut-vertex in a connected graph is a vertex whose removal makes the graph disconnected. Prove: If $G$ is a connected graph with $n$ vertices and diameter $\diam(G) > n/2$ then $G$ has a cut-vertex.
9.5 HW (a) Find the expected number of cliques of size $k$ in a random graph with $n$ vertices. (A clique of size $k$ is a set of $k$ vertices that are pairwise adjacent. Unless otherwise specified, in our random graphs every edge is chosen independently with probability $1/2$.) Your answer should be a simple closed-form expression (no summation symbols or dot-dot-dots). (b) Prove: for any fixed value of $k$, almost all graphs contain a clique of size $k$. (6+8 points)
9.6 DO: Prove: Every subset of a set of independent random variables is independent.
9.7 DO: Prove: the events $A_1,\dots,A_k$ are independent if and only if their indicator variables are independent.
9.8 CHALLENGE: If $X_1,\dots,X_k$ are $t$-wise independent non-constant RVs (random variables) then $$ |\Omega| \ge \binom{k}{\lfloor t/2\rfloor}$$
9.9 DO: Prove: if $X_1,\dots,X_k$ are independent RVs then $$ E(\prod X_i) = \prod E(X_i) $$ (First prove it for $k=2$.)
9.10 HW: Construct random variables $X,Y$ that are uncorrelated but not independent. (See def. in problem 9.15 below.) Minimize the size of the sample space. You do not need to prove that your sample space has minimum size. (8 points)
9.11 DO (Markov's Inequality): Let $X$ be a nonnegative random variable. Prove: $(\forall a>0)\left(P(X\ge a)\le \frac{E(X)}{a}\right)$. The proof should be one line.
9.12 DO (Variance): The variance of the random varoable $X$ is defined as $\var(X)=E((X-E(X))^2)$. Prove: $\var(X)=E(X^2)-(E(X))^2$.
9.13 DO (Cauchy-Schwarz): (a) Prove: $E(X^2)\ge (E(X))^2$. (b) Determine when these two quantities are equal. (c) Show that this inequality is equivalent to the inequality $|x\cdot y|\le ||x||\cdot ||y||$ where $x,y\in\rrr^n$, their dot product is defined as $x\cdot y =\sum_{i=1}^n x_iy_i$, and $||x||=\sqrt{x\cdot x}$ is the Euclidean norm.
9.14 DO (Chebyshev's Inequality): Prove: for any $b>0$, $$P(|X-E(X)|\ge b)\le \frac{\var(X)}{b^2}.$$
9.15 DO: The covariance of the random variables $X,Y$ is defined as $\cov(X,Y)=E(XY)-E(X)E(Y)$. Notice that $\var(X)=\cov(X,X)$. We say that the random variables $X$ and $Y$ are positively correlated, uncorrelated, and negatively correlated if their covariance is positive, zero, or negative, respectively. Let $Y=\sum_{i=1}^k X_i$ where the $X_i$ are random variables. Prove: $$\var(Y)=\sum_{i=1}^k\sum_{j=1}^k \cov(X_i,X_j).$$
9.16 DO: Prove: if the random variables $X_1,\dots,X_k$ are pairwise independent then $\var\left(\sum X_i\right) = \sum \var(X_i)$.
9.17 DO: Let $Y$ be the indicator variable of "heads" in a biased coin flip where $P($heads$)=p$ and $P($tails$)=1-p$. ($Y$ is called a Bernoulli trial with success probability $p$. "$Y=1$" represents "success.") Prove: $\var(Y) = p(1-p)$.
9.18 DO: Let $X$ be the number of successes in a sequence of $n$ independent Bernoulli trials with parameter $p$. Prove: (a) $E(X)=np$ (b) $\var(X)=np(1-p)$ (c) $P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}$ ("binomial distribution") (d) What value of $X$ has the highest probability?
9.19 DO (Weak Law of Large Numbers): Let $X_k$ denote the number of successes in a sequence of $k$ independent Bernoulli trials with parameter $p$ where $0 < p < 1$. Prove: for all $\epsilon >0$ $$ \lim_{k\to\infty} P(|X_k - pk| \ge \epsilon k)\to 0.$$
9.20 DO (functions of disjoint sets of independent variables are independent): Prove: If $X_1,\dots, X_k$ are independent random variables and we partition $[k]$ as $[k]=A_1\cup\dots\cup A_m$ and $f_1,\dots,f_m$ are functions where $f_i$ has $|A_i|$ variables and $Y_i$ is the result of applying function $f_i$ to the variables $(X_j \mid j\in A_i)$ then $Y_1,\dots,Y_m$ are independent.
9.21 HW (due Tuesday, Nov 11) Let $X$ denote the number of triangles in a random graph with $n$ vertices. (a) What is the size of the sample space for this experiment? (b) Determine $E(X)$. (c) Determine $\var(X)$. Get a reasonable closed-form expression. (d) Evaluate $\var(X)$ asymptotically. Your answer should be a formula of the form $an^bc^n$ where $a,b,c$ are constants. Determine $a,b,c$. Prove your answers. (3+3+10+6 points)
8.1 DO: What is the number of edges of a forest with $n$ vertices and $c$ connected components?
8.2 DO: Study "Finite probability spaces" from LN
8.3 DO: Let $\overline B$ denote the complement of the event $B$, i.e., $\overline B = \Omega\setminus B$. Prove: $P({\overline B})= 1 - P(B)$.
8.4 DO (modular identity): Let $A,B$ be events over the same probability space. Prove: $P(A\cup B) + P(A\cap B) = P(A) + P(B)$.
8.5 DO (additivity): Let $A_1,\dots, A_k$ be events. If $(\forall i\neq j)(P(A_i\cap A_j) = 0)$ then $P(\bigcup_{i=1}^k A_i) = \sum_{i=1}^k P(A_i)$.
8.6 DO (union bound): Let $A_1,\dots, A_k$ be events. Prove: $P(\bigcup_{i=1}^k A_i) \le \sum_{i=1}^k P(A_i)$.
8.7 DO: (a) Prove: If $A, B$ are independent events then $A$ and $\overline B$ are also independent. (b) Infer from this that $\overline A$ and $\overline B$ are also independent (without repeating the argument). (c) Assume $A_1,\dots, A_k$ are independent events. For each $i$, let $C_i$ be either $A_i$ or $\overline A_i$. Prove that $C_1,\dots, C_k$ are independent.
8.8 DO: Prove: If there exist $k$ non-trivial independent events in a probability space of size $n$ then $n \ge 2^k$. (The size of the probability space $(\Omega, P)$ means the size of the sample space, $|\Omega|$.)
8.9 HW Find a probability space and three events that are pairwise but not fully independent. Make your probability space as small as possible. You don't need to prove that it is the smallest. (6 points)
8.10 HW (due Tuesday, Nov 4) Find a probability space and $k$ events that are $(k-1)$-wise but not fully independent. Make your probability space as small as possible. You don't need to prove that it is the smallest. (6 points)
8.11 DO: Consider the uniform probability space over a sample space $\Omega$ where $|\Omega|=p$ is a prime number. Prove: if $A, B$ are non-trivial events then they are not independent.
8.12 CHALLENGE. (a) Construct a probability space of size $O(k)$ with $k$ pairwise independent non-trivial events. (b) Do the same with triple-wise independent events.
8.13 CHALLENGE. Prove: (a) If there exist $k$ pairwise independent non-trivial events in a probability space then the size of the space is $\ge n$. (b) If there exist $k$ 4-wise independent non-trivial events in a probability space then the size of the space is $\Omega(k^2)$.
8.14 DO: Let $X$ be a random variable. Prove: $\min X \le E(X) \le \max X$.
8.15 DO: Prove: $E(X+Y)=E(X)+E(Y)$. Here $X,Y$ are random variables over the same sample space.
8.16 DO (linearity of expectation): Let $X_1,\dots,X_k$ be random variables over the same probability space. Prove: $E(\sum \alpha_iX_i)=\sum\alpha_i E(X_i)$.
8.17 DO: We flip $n$ coins. Let $X$ denote the number of heads. Prove: $E(X) = n/2$. (Note: The sample space in this problem has size $2^n$ and we consider the uniform distribution over the sample space.)
8.18 DO: LN 7.1.8 and 7.1.14 (independence/correlation of "sum of dice" events)
8.19 HW (due Tuesday, Nov 4): Let $(A\mid C)$ ("$A$ given $C$") denote the event $A$ conditioned on $C$ (so our sample space is $C$ and all probabilities are conditional on condition $C$). Construct a probability space and three events $A,B,C$ such that $A$ and $B$ are not independent but $(A\mid C)$ and $(B\mid C)$ are independenet and $(A\mid {\overline C})$ and $(B\mid {\overline C})$ are also independent. (7 points)
8.20 DO: LN 7.1.9 (Theorem of Complete Probability)
8.21 HW (Probability of causes, due Tuesday, Nov 4) 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$?
(b) 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$? Show all the intermediate results you need to compute. (8+8 points)
8.22 HW (due Tuesday, Nov 4): LN 7.2.13 (club with 2000 members). Assume the club serves vodka legally to all its members. - Make sure you give a clear definition of the random variables you use. The clarity of the definition accounts for 2/3 of the credit. Hint. Learn about indicator variables (LN 7.2.6, 7.2.7). Represent the number of lucky members as a sum of indicator variables. (9 points) What is the size of the sample space for this experiment? (2 points)
8.23 DO (spanning tree): Let $G=(V,E)$ be a graph. A spanning tree of $G$ is a tree $T=(V,F)$ (on the same vertex set!) that is a subgraph of $G$ (i.e., $F\subseteq E$). Prove: a graph $G$ has a spanning tree if and only if $G$ is connected.
8.24 DO: Prove: A connected graph with $n$ vertices has at least $n-1$ edges.
8.25 DO: Prove that for a graph $G$ with $n$ vertices,
the following conditions are equivalent:
(a) $G$ is a tree.
(b) $G$ is connected and has $n-1$ edges.
(c) $G$ has no cycles and has $n-1$ edges.
(d) There is a unique path between every pair
of vertices of $G$.
8.26 HW (due Tuesday, Nov 4):
Let $g_n$ denote the number of non-isomorphic graphs
with $n$ vertices. Let
$\displaystyle{N = 2^{\binom{n}{2}}} .$
(a) Prove: $N/n! \le g_n \le N$.
(b) Prove: $\log_2 g_n \sim n^2/2$.
(6+5 points)
7.1 DO: Study the concepts of graph theory from LN (instructor's online lecture notes).
7.2 DO: Prove: A graph $G$ is bipartite $\iff$ $G$ contains no odd cycles.
7.3 HW: Recall that $\alpha(G)$ denotes the independence number of the graph $G$ (size of the largest indpendent set). (a) Let Gr$(k,\ell)$ denote the $k\times\ell$ grid. (This graph, defined in class, has $k\ell$ vertices and $2k\ell -k-\ell$ edges.) Determine $\alpha$(Gr$(k,\ell))$ where $k,\ell$ are given odd numbers. (b) Let TG$(k,\ell)$ denote the $k\times \ell$ toroidal grid ($k,\ell \ge 3$). This graph is defined as follows: its vertex set is $V=\zzz_k \times \zzz_{\ell}$ where $\zzz_k$ denotes the set of residue classes modulo $k$. (So TG$(k,\ell)$ has $k\ell$ vertices.) The vertex $(i,j)$ is adjacent to $(i\pm +1,j)$ and to $(i,j\pm 1)$, where arithmetic (addition/subtraction) in the first coordinate is modulo $k$ and in the second coordinate is modulo $\ell.$ So this is a regular graph of degree 4. Determine $\alpha($TG$(k,k))$ where $k$ is an odd number. Prove your answers. In each case you have to prove that no independent set is larger than the one you provide. Give a very short and convincing proof. If your proof is longer than a couple of sentences or it begins distinguishing cases or it makes proclamations like "clearly it is best if we start from a corner" without a clear justification then you are on the wrong track. As a model, recall our proof of the result that if a graph $G$ is regular of degree $d\ge 1$ then $\alpha(G) \le \lfloor n/2\rfloor$ where $n$ is the number of vertices. (8+8 points)
7.4 DO: Prove if every vertex of the graph $G$ has degree $\le d$ then $\chi(G)\le d+1$, where $\chi$ denotes the chromatic number.
7.5 HW: Prove: For every graph $G$ with $n$ vertices, $\alpha(G)\chi(G) \ge n$. (7 points)
7.6 DO: (a) For every $k,\ell \ge 1$ find a graph $G$ on $n=k\ell$ vertices such that $\alpha(G)=k$ and $\chi(G)=\ell$. (b) Find infitely many graphs $G$ such that $\alpha(g)\chi(G)=\Omega(n^2)$ where $n$ is the number of vertices of $G$. (The big-Omega notation is the inverse of the big-Oh notation. Find its explanation in the "Asymptotic notation" chapter of LN.)
7.7 HW: Recall: a Hamilton cycle in a graph is a cycle that passes through every vertex. A graph is Hamiltonian if it has a Hamilton cycle. For what values of $k$ and $\ell$ is the grid Gr$(k,\ell)$ Hamiltonian? Prove your answers. The proof of the positive answer can be explained by picture. The proof of the negative answer should be a concise, convincing argument (one line). (2+2+5 points: 2 for the correct separation of cases (statement of the answer); 2 for an indication of the proof of the positive answer, 5 for an elegant, very short proof of the negative answer)
7.8 HW: Construct a graph $G$ such that $G$ has no triangles and yet $\chi(G)\ge 4$. Instructions: 11 vertices, 5-fold symmetry. It is sufficient if you provide a nice drawing that displays the 72-degree ($2\pi/5$) rotational symmetry. (6 points)
7.9 HW (Manhattan routing): Count the shortest paths from the bottom left corner to the top right corner of a $k\times\ell$ grid. Your answer should be a very simple formula. Prove your answer. (7 points)
7.10 HW: Draw all 7-vertex trees. Make sure you do not draw two isomorphic trees and you do not miss any. Clearly state the number of non-isomorpohic trees you found. (9 points; lose 4 points for each mistake)
7.11 DO: Prove that every tree with $n\ge 2$ vertices has a vertex of degree 1.
7.12 DO: Prove: every tree with $n$ vertices has $n-1$ edges. (Use the preceding exercise).
7.13 DO: Prove: in a connected graph, every pair of longest paths shares a vertex.
7.14 CHALLENGE: Prove: in a tree, all longest paths share a vertex.
7.15 DO: Let $d_1,\dots,d_n\ge 1$ be integers such that $d_1+\dots+d_n= 2n-2$. (a) Prove that there is a tree on vertex set $[n]=\{1,\dots,n\}$ such that $(\forall i)(\deg(i)=d_i$. (b) Prove that the number of trees with these prescribed degrees is $$\frac{(n-2)!}{(d_1-1)!\dots (d_n-1)!}$$ (Note: here we are counting all trees, not just non-isomorphic trees.) Hint: Induction on $n$. Use Problem 7.11.
7.16 HW (Cayley's formula): Prove: the number of trees on a given set of $n$ vertices is $n^{n-2}$. Use the preceding exercise. (4 points)
7.17 DO: Study the Pascal triangle modulo 2. Discover striking decorative pattern. Formalize, prove.
7.18 DO: Study the standard deck of 52 cards (4 suites, 13 kinds) and the named configurations of a poker hand (5 cards).
7.19 DO: Calculate the probability that a poker hand is a full house (3 of a kind and 2 of another kind, like 3 kings and 2 9s). Give a simple formula; do not evaluate.
7.20 HW: A generalized deck has $4n$ cards coming in fours suites of $n$ cards each; the cards within each suite are numbered $1$ to $n$. What is the probability that a hand of $k$ cards contains no two of the same kind? Give a simple formula; do not evaluate. Your formula should be a closed-form expression (no dot-dot-dots, no summation or product symbols). (6 points)
7.21 DO: Study "Asymptotic notation" from LN.
7.22 DO: Prove: $\sqrt{1+1/n} -1 \sim 1/(2n)$. Here $\sim$ denotes asymptotic equality.
7.23 HW: Find the constants $a,b,c$ such that the following asymptotic equality holds: $\binom{2n}{n}\sim ab^nn^c$. Use Stirling's formula: $n! \sim (n/\eee)^n \sqrt{2\pi n}$. (7 points)
7.24 HW: Let $a_n >1$ and $b_n >1$ be sequences of real numbers.
Consider the following two statements:
(A) $a_n \sim b_n$ (B) $\ln a_n \sim \ln b_n$.
(a) Prove that (B) does not follow from (A). (Give a counterexample.)
(b) Prove: if $a_n \to \infty$ then (B) does follow from (A).
(7+8 points)
6.1 DO: Review the Multinomial Theorem.
6.2 Notation: $[n]=\{1,\dots,n\}$.
6.3 HW: (a) A function $f : [k]\to [n]$ is monotone increasing
if $(\forall x,y\in [k])(x > y \implies f(x) > f(y))$. Count the
monotone increasing functions $f : [k]\to [n]$.
Your answer should be a very simple expression. Give a very
simple bijective proof.
(b) A function $f : [k]\to [n]$ is monotone non-decreasing
if $(\forall x,y\in [k])(x \ge y \implies f(x) \ge f(y))$. Count the
monotone non-decreasing functions $f : [k]\to [n]$.
Your answer should be a simple formula. Give two bijective proofs:
(b1) By reduction to part (a). (b2) By reduction to the
chocolate coins problem discussed in class.
(5+5+5 points)
6.4: Review the basic concepts of graph theory from LN.
6.5 DO: A graph is regular of degree $k$ if every vertex has degree $k$. Count the walks of length $r$ from a given vertex in a regular graph of degree $k$. Your answer should be a very simple formula.
6.6 DO: Prove: if $y$ is reachable from $x$ (by a walk) in a graph then there exists a path from $x$ to $y$.
6.7 DO: Count the triangles in the complete graph $K_n$.
6.8 DO: Count the 4-cycles in $K_n$.
6.9 DO: Review the notion of isomorphism of graphs.
6.10 HW: Find two regular graphs of degree 3 on 6 vertices that are not isomorphic. (6 points)
6.11 HW: A graph is self-complementary if it is isomorphic to its complement. (a) Find a self-complementary graph with 4 vertices. (b) Find a self-complementary graph with 5 vertices. (c) Prove: if $G$ is a self-complementary graph with $n$ vertices then $n\equiv 0$ or $1 \pmod 4$. (2+3+8 points)
6.12 CHALLENGE (Mantel - Turán Theorem). A graph is triangle-free if it does not contain triangles. Let $G$ be a triangle-free graph with $n$ vertices and $m$ edges. Prove: $m \le n^2/4$.
6.13 CHALLENGE (Köváry - Turán - Sós Theorem). Prove: if $G$ has no 4-cycles then $m = O(n^{3/2})$, i.e., there exists a constant $C$ such that $m \le Cn^{3/2}$.
6.14 DEFINITION. A legal coloring of a graph is an
assignment of a color to each vertex such that adjacent vertices
receive different colors. A graph is $k$-colorable if $k$
colors suffice for a legal coloring. (We are not required to use
all the $k$ colors.) So for instance $K_n$ is $k$-colorable for
all $k\ge n$. The chromatic number $\chi(G)$ of a graph $G$
is the smallest $k$ such that $G$ is $k$-colorable.
6.15 DO: Determine the chromatic number of (a) the $n$-cycle (b) the $k\times n$ grid.
6.16 DO: Prove: If a graph is 2-colorable then it has at most $n^2/4$ edges (where $n$ is the number of vertices).
5.1 HW: Solve problem #4 from the First Quiz. (10 points; lose 4 points for each mistake)
5.2 HW (trinomial theorem): Determine the coefficient of $x^8y^{12}z^5$ in the expansion of $(x+y+z)^{25}$. Give a simple expression in terms of factorials, do not evaluate. (4 points)
5.3 HW: Find the largest $k$ such that $3^k$ divides $100!$ (100-factorial). (7 points)
5.4 CHALLENGE: Prove: If a prime power $q=p^t$ divides $\binom{n}{k}$ then $q\le n$.
5.5 DO: Count the $(0,1)$-strings (strings over the alphabet $\{0,1\}$) of length $n$ without consecutive ones. E.g., for $n=6$, count $101001$ in but do not count $101100$.
5.4 terminology, notation: $[n]$ denotes the set $\{1,2,\dots,n\}$. We say that $A$ is an $n$-set if $A$ is a set with $n$ elements. We say that $B$ is a $k$-subset of $A$ is $B\subseteq A$ and $|B|=k$. Recall that $\binom{n}{k}$ is the number of $k$-subsets of an $n$-set.
5.5 DO: Consider the following identity:
$$\sum_{k=0}^n \binom{n}{k} = 2^n.$$
Give two proofs of this identity: a combinatorial proof, based on the
meaning of the binomial coefficients (what do they count?), and
(b) an "algebra proof" (use the Binomial Theorem).
5.6 HW: Let $E_n$ denote the number of even subsets of $[n]$ and $O_n$ the number of odd subsets of $[n]$. (We call a subset even if it has an even number of elements and odd if it has an odd number of elements.) Prove: if $n\ge 1$ then $E_n = O_n$. Give two proofs: (a) a bijective proof: find a bijection between the even subsets and the odd subsets; and (b) an algebra proof (use the binomial theorem). (6+3 points)
5.7 DO: Prove Pascal's identity: ${n+1 \choose k+1} = {n\choose k} + {n \choose k+1}.$ Give two proofs: (a) a bijective proof and (b) and algebra proof.
5.8 CHALLENGE: Let $S(n,3)$ denote the number of those subsets of an $n$-set which have cardinality (number of elements) divisible by 3. Prove: $$|S(n,3) - 2^n/3| \le 1.$$
4.1 DO: Prove that there are infinitely many promes $p$ such that $p\equiv -1 \pmod 4$.
4.2 DO*: Prove that there are infinitely many promes $p$ such that $p\equiv 1 \pmod 4$. Hint: use Ex. 3.16.
4.3 DO: Prove: $\gcd(a_1,\dots,a_m)\neq 1$ if and only if there exists a prime that divides each $a_i$.
4.4 DO: The Chinese Remainder Theorem makes the assumption that the moduli $m_i$ are pairwise relatively prime and concludes that the given system of congruences has a solution. Prove that this sufficient condition is not necessary: find a system of congruences where the moduli are not pairwise independent and yet the system has a solution. In fact, given any list of moduli $m_1,\dots, m_k$, find values $a_1,\dots,a_k$ such that the system of congruences $x\equiv a_i \pmod {m_i}$ $(i=1,\dots,k)$ has a solution (i.e., there exists an $x$ that satisfies all congruences simultaneously).
4.5 DO Consider the following system of simultaneous congruences:
$x\equiv a_1 \pmod{m_1}$
$x\equiv a_2 \pmod {m_2}$
$\dots$
$x\equiv a_k \pmod {m_k}$
Prove: If this system has a solution then the solution is unique modulo $\lcm(m_1,\dots,m_k)$. (Note: no assumption is made on the $m_i$ in this problem.)
4.6 DO: The Chinese Remainder Theorem (CRT) asserts that if the $m_i$ are pairwise relatively prime then the system of simultaneous congruences given in the preceding exercise does have a solution. Review the proof of CRT.
4.7 DO: Assume the numbers $m_1,\dots,m_k$ are pairwise relatively prime. Let $S_j$ be the product of all the $m_i$ except $m_j$. Prove: $\gcd(S_1,\dots,S_k)=1$.
4.8 DO (CRT) Consider the following system of simultaneous
congruences:
$x\equiv 5 \pmod{24}$
$x\equiv 2 \pmod {33}$
$3x\equiv 7 \pmod {26}$
Prove that this system has a solution. Your proof should be short and elegant, involve no calculation, only correct references to results learned in class. Do not calculate a solution, only prove it exists.
4.9 DO: Find all solutions of the system of congruences given in the preceding exercise.
4.10 DO (CRT?)
Decide whether or not the following system of simultaneous
congruences has a solution. Prove your answer.
$x\equiv 11 \pmod{21}$
$x\equiv 5 \pmod{12}$
$x\equiv 1 \pmod{14}$
Your proof should be very short, only a line or two.
4.11 DO: Let $p$ be a prime number. Prove that the only solutions of the congruence $x^2 \equiv 1 \pmod p$ are $x\equiv \pm 1 \pmod p$.
4.12 HW (due Tuesday, Oct 21): Let $p,q$ be distinct odd primes. Prove that the congruence $x^2\equiv 1 \pmod {pq}$ has four solutions modulo $pq$. (Don't forget to prove that the four solutions you found are indeed pairwise not congruent modulo $pq$.) (8 points)
4.13 DO (computing multiplicative inverses): Find the following multiplicative inverses:
(a) $6^{-1} \pmod{19}$.
(b) $k^{-1} \pmod{2k+1}$. (Here $k\ge 1$.)
(c) $k^{-1} \pmod{3k+1}$. (Here $k\ge 1$.)
Show your work (show how you got the answer). Each answer should be a positive integer that is less than the modulus.
4.14 HW (due Tuesday, Oct 21): Let $p$ be a prime number and let $k,\ell \ge 1$. Prove: if $k\equiv \ell\pmod {p-1}$ then $(\forall a)(a^k \equiv a^{\ell} \pmod p)$. (4 points)
4.15 HW (RSA, due Tuesday, Oct 21): Recall the elements of the RSA public-key crypto system: Alice picks two (large) primes $p\neq q$. Let $N=pq$ and $M=(p-1)(q-1)$. Alice picks a number $e\ge 1$ such that $\gcd(e,M)=1$ and computes $f\ge 1$ such that $ef\equiv 1 \pmod M$ ($f$ is a multiplicative inverse of $e$ modulo $M$). The pair $(N,e)$ is Alice's public key; $f$ is her private key. The "message space" is the set of integers $W$ in the interval $0\le W\le N-1$. Both the plaintext and the ciphertext will be from this message space. If Bob wants to send an encrypted message to Alice, he proceeds as follows. His plaintext is a number $X$ from the message space. He computes the ciphertext $Y=E(X):= (X^e \bmod N)$ and sends it to Alice. Alice computes $D(Y):=(Y^f \bmod N)$. Prove: the functions $E$ and $D$ (encryption/decryption) are inverses of one another: $(\forall X)(D(E(X)=X)$ and $(\forall Y)(E(D(Y))=Y$. (Here the quantifiers range over the message space.) (8 points)
4.16 DO: Given $N$ and $M$ as in the preceding exercise, efficiently compute $p$ and $q$. Here "efficient" means "polynomial time": the number of bit-operations should be bounded by a constant power of the length of the input (total number of bits in $N$ and $M$). Remark: This exercise means that if we assume it is hard to factor $N$ then it is also hard to compute $M$ given $N$.
4.17 DO: You are Eve (the eavesdropper). You intercepted the ciphertext $Y$. Suppose you also possess a number $T$ which is a multiple of $M$. Break the code (efficiently compute the plaintext $X$). Hint: find $f'$ such that $ef'\equiv 1\pmod M$. (Note: you do not know $M$.)
3.1 HW: Let $k\in \zzz$. Let $a=9k+2$ and $b=5k-3$. (a) Prove: $\gcd(a,b)$ is $1$ or $37$. Try to find a very simple proof (one or two lines). (Hint: linear combinations.) (b) Find all values of $k$ for which $\gcd(a,b)=37$ . (8+6 points)
3.2 HW (improving Euler-Fermat): (a) Prove: $\gcd(a,72)=1 \iff \gcd(a,6)=1$. (b) Recall that $\vf(72)=\vf(8)\vf(9)=4\cdot 6=24$, where $\vf$ denotes Euler's $\vf$ function. So it follows from the Euler--Fermat congruence that if $\gcd(a,6)=1$ then $a^{24} \equiv 1 \pmod{72}$. Prove the stronger statement that if $\gcd(a,6)=1$ then $a^{6} \equiv 1 \pmod{72}$. (Hint: Ex. 1.44.) (1+8 points)
3.3 HW: Calculate $5^{11^{666666}} \bmod{73}$. (The exponent of the exponent is 666666.) Your answer must be an integer between $0$ and $72$. (Warning about implicit parenthesization of iterated powers: $a^{b^c}$ means $a^{(b^c)}$ (the exponent is evaluated first).) Do not use electronic devices. This problem requires no calculation that you could not perform in your head. Show all your work. A mere statement of the answer gets zero credit. (Hint: to compute $5^N \bmod{73}$ you first need to compute $N$ modulo what? [Note: NOT 73.]) (1+8 points)
3.4 DO: Prove: if $k$ is a common divisor of $a$, $b$, and $m$ then $a\equiv b\pmod m \iff (a/k) \equiv (b/k) \pmod{(m/k)}$.
3.5 DO: Prove: If $m \mid ab$ and $\gcd(a,m)=1$ then $m\mid b$.
3.6 DO: Prove: If $m \mid ab$ and $\gcd(a,m)=d$ then $m \mid bd$.
3.7 DO: Prove: if $\gcd(c,m)=1$ and $ac\equiv bc \pmod m$ then $a\equiv b\pmod m$.
3.8 DO: Prove: if $\gcd(c,m)=d$ and $ac\equiv bc \pmod m$ then $a\equiv b\pmod{(m/d)}$.
3.9 HW: Recall that $x$ is a multiplicative inverse of
$a$ modulo $m$ if $ax\equiv 1 \pmod m$. This number, if exists,
is unique modulo $m$ and is denoted $a^{-1} \bmod m$. For
each of the following multiplicative inverses, find their
value (an integer between $0$ and the modulus minus 1)
or prove it does not exist. In (c) --(e), $k$ is a
given integer $\ge 2$.
(a) $7^{-1} \bmod{73}$;
(b) $21^{-1} \bmod{57}$;
(c) $k^{-1}\bmod {k^2-1}$ (d) $k^{-1} \bmod {k^2+1}$;
(e) $(k-1)^{-1} \bmod{k^2-1}$.
Clearly state your answer in each case.
For (a), (b) show all your work. A mere statement and verification
of the answer earns no credit. For (c)--(e), state and prove your
answer.
(5+4+4+5+4 points)
3.10 DO: Calculate $17^{-1} \bmod{557}$. You may use a calculator for multiplication of integers but not for more advanced functions such as gcd. Show all your work.
3.11 DO: Find $x$ and $y$ such that $17x+557y=1$. (Hint: Use your answer to the preceding exercise.)
3.12 DO: (a) Is $4\zzz \cup 6\zzz$ a subgroup of $\zzz$? (b) For what pairs $(a,b)$ is $a\zzz\cup b\zzz$ a subgroup?
3.13 DO: For a positive integer $n$, let $f(n) = \sum_{d\mid n}\vf(d)$ where the summation is over all positive divisors $d$ of $n$. For instance, $f(6)=\vf(1)+\vf(2)+\vf(3)+\vf(6)=1+1+2+2=6$. (a) Evaluate $f(n)$ for all $n\le 20$. Notice the pattern, make a conjecture. (b) CHALLENGE: Prove your conjecture.
3.14 DO: Prove: If $\gcd(a,b)=1$ then $\vf(ab)=\vf(a)\vf(b)$.
3.15 DO: Prove: If $x^2 \equiv 1 \pmod p$ then $x\equiv \pm 1 \pmod p$. ($p$ is a prime.)
3.16 DO: Prove: If $p$ is an odd prime and $p\mid a^2+1$ then $p\equiv 1 \pmod 4$.
2.1 DO: Recall that a relation on a set $A$ is a subset of the Cartesian product $A\times A$. If $|A|=n$, what is the number of relations on $A$?
2.2 DO: (a) Prove: If $T_1$ and $T_2$ are transitive relations on the set $A$ then $T_1\cap T_2$ is also a transitive relation. (b) If $\{T_i \mid i\in I\}$ is a family of transitive relations on the set $A$ then $\bigcap_{i\in I} T_i$ is also a transitive relation on $A$.
2.3 DO: Construct two transitive relations on some set $A$ such that their union is not transitive. Make your set $A$ as small as you can.
2.4 DO: Recall: Given a relation $R\subseteq A$, we say that $b\in A$ reachable from $a\in A$ in $k$ steps if there exist elements $c_0,\dots,c_k\in A$ such that $c_0=a$, $c_k=b$, and for $i=1,\dots,k$ we have $c_{i-1} Rc_i$. We say that $b$ is reachable from $a$ if it is reachable in some non-negative number of steps. Prove that reachability is a transitive relation. It is also reflexive by convention ($k=0$).
2.5 DO: Recall: the transitive closure of a relation $R$ is the smallest transitive relation $T$ such that $R\subseteq T$. Prove: every relation has a transitive closure. Use
2.6 DO: Recall: we say that $b$ is strictly reachable from $a$ if $b$ is reachable from $a$ in a positive number of steps. Prove that "strict reachability" is the same as "transitive closure."
2.7 HW (due Tue Oct 14): Let $\Div^+(n)$ denote the set of non-negative divisors of $n$. Let $D$ denote the divisibility relation on $\Div^+(n)$. (a) Given a positive integer $n$, find a relation $R$ on $\Div^+(n)$ such that $D$ is the transitive closure of $R$ and $|R|$ is minimal subject to this condition. -- Prove your answer. (b) If $n = p_1^{k_1}\cdots p_s^{k_s}$ (where the $p_i$ are distinct primes and $k_i\ge 1$) then determine (b1) the number $d(n)=|\Div^+(n)|$ (the number of positive divisors of $n$) and (b2) $|R|$. Your results should be simple expressions in terms of $k_1,\dots,k_s$. (6+6+4 points)
2.8 HW (due Tue Oct 14): Let $A$ be a set of $n$ elements.
(a) Count the reflexive relations on $A$.
(b) Count the symmetric relations on $A$.
(c) Prove: the number of transitive relations on $A$
is $2^{\Omega(n^2)}$, i.e., there exists a constant
$c >0$ such that the number in question is at least
$2^{cn^2}$ for all sufficiently large $n$.
(3+3+8 points)
2.9 DO: Recall: a partition $\Pi=\{B_1,\dots,B_k\}$ of the set $A$ into $k$ blocks $B_i$ means the $B_i$ are non-empty subsets of $A$; they are pairwise disjoint (for $i\neq j$ we have $B_i\cap B_j=\emptyset$), and their union is $A$: $A=B_1\cup\dots\cup B_k$. Define the relation $R_{\Pi}$ on $A$ as follows: for $a,b\in A$ we have $a R_{\Pi} b$ if they belong to the same block, i.e., if $(\exists i)(a, b\in B_i)$. Prove that $R_{\Pi}$ is an equivalence relation.
2.10 DO (Fundamental theorem of equivalence relations):
Prove: if $T$ is an equivalence relation on the set $A$ then
there exists a (unique) partition $\Pi$ of $A$ such that
$T = R_{\Pi}$.
Terminology: This is the partition defined by $\Pi$.
The blocks of this partition are called the equivalence
classes defined by $T$. If $T$ denotes congruence
modulo $m$ then the equivalence classes are called the
residue classes modulo $m$. So two number $a,b$ belong
to the same residue class modulo $m$ if and only if
$a\equiv b \pmod m$.
1.1 DO: Prove: $\sqrt{n^2+100} = O(n)$. (Review big-Oh notation from LN, "Asymptotic notation" chapter.)
1.2 DO: Recall that for $A,B\subseteq \zzz$ the set $A+B$ is defined as $A+B = \{a+b \mid a\in A, b\in B\}$. Prove: $|A+B|\le |A|\cdot |B|$.
1.3 DO: For all $k, m \ge 0$ find set $A,B\subset \zzz$ such that $|A|=k$, $|B|=m$, and $|A+B|=km.$
1.4 DO: (a) Prove: Prove: if $|A|=n$ and $B\neq\emptyset$ then $|A+B|\ge n$. (b) What is $A+\emptyset$ ?
1.5 CHALLENGE: Prove: if $|A|=k$ and $|B|=m$ then $|A+B|\ge k+m-1$.
1.6 DO: Prove that the previous exercise is tight for all $k,m$, i.e., prove that for all $k,m$ there exist sets $A,B$ such that $|A|=k$, $|B|=m$, and $A+B|=k+m-1$.
1.7 DO: Prove: if $|A|=n$ then $|A+A|\le \binom{n+1}{2}= n(n+1)/2$.
1.8 HW (due Thursday, Oct 9): Prove: if $|A|=n$ then $|A+A+A|\le \binom{n+2}{3}= n(n+1)(n+2)/6$. (10 points)
1.9 DO: (a) Prove: $(\forall y)(z\mid y) \iff z=\pm 1$. (b) Prove: If $a\mid b$ and $b\mid a$ then $b=\pm a$.
1.10 DO: Recall that we write $\Div(a)$ for the set of divisors of the integer $a$. Is there an integer $a$ such that the set $\Div(a)$ is infinite?
1.11 DO: Recall that in our notation, $\Div(a,b)=\Div(a)\cap \Div(b)$ denotes the set of common divisors of $a$ and $b$. For what values $a$ and $b$ is this set infinite?
1.12 DO: Prove: If $d\in \Div(a,b)$ then $d\in \Div(a+b)$ and $d\in \Div(a-b)$; in fact $d\in\Div(c)$ for all linear combinations $c=ax+by$. State what property of multiplication (and addition) we use in the proof.
1.13 DO: Review relations and transitive relations. Prove: divisibility is a transitive relation on the integers, i.e., if $a\mid b$ and $b\mid c$ then $a\mid c$. What property of multiplication do we use in the proof?
1.14 DO: Recall the definition of greatest common divisors: we say that $d$ is a greatest common divisor of $a$ and $b$ if (i) $d$ is a common divisor (i.e., $d\mid a$ and $d\mid b$) and (ii) every common divisor of $a$ and $b$ divides $d$, i.e., if $e\mid a$ and $e\mid b$ then $e\mid d$.
1.15 DO: Prove: $d$ is a greatest common divisor of $a$ and $b$ if and only if $\Div(a,b) = \Div(d)$.
1.16 DO: Prove: If both $r$ and $s$ are greatest common divisors of $a$ and $b$ then $r=\pm s$.
1.17 NOTATION. Recall that for $A\subseteq \zzz$ and $m\in \zzz$ we write $mA = \{mx \mid x\in A\}$. Notice that $m\zzz$ consists of all multiples of $m$.
1.18 HW: Prove: $(\forall a,b)(\exists m)(a\zzz \cap b\zzz = m\zzz)$. (6 points)
1.19 DO: Prove: $a\zzz = b\zzz \iff a=\pm b$.
1.20 HW: Prove: $\Div(a,b) = \Div(a-b,b)$. (Recall that two sets $A$ and $B$ are equal $\iff$ they have the same elements, i.e., $\iff$ $(\forall x)(x\in A \iff x\in B)$.) (8 points)
1.21 DO: Use the previous exercise to prove the existence of a greatest common divisor.
1.22 DO: Review mathematical induction.
Recall the Division Theorem and prove it by induction on $|a|$:
Division Theorem.
$(\forall a)(\forall b\neq 0)(\exists q,r)(a=bq+r$ and $0\le r< |b|)$.
1.23 HW: Recall that a subset $A\subseteq \zzz$ is called a
subgroup if $A$ is not empty and $A$ is closed under substraction
(i.e., $A-A\subseteq A$).
We write $A\le \zzz$ to indicate that $A$ is a subgroup.
Prove: If $A\le\zzz$ then $(\exists m)(A = m\zzz)$.
Comments: In class we proved that if $A\le \zzz$ then
$0\in A$; $A$ is closed under taking the negative of an element
(i.e., $-A\subseteq A$), and it is closed under addition
(i.e., $A+A\subseteq A$). We also proved that if $a\in A$
and $q\in\zzz$ then $aq\in A$. You do not need to reprove these
facts; you can use them in your proof. Hint: Use the
Division Theorem.
(8 points)
1.24 DEFINITION: Recall that a linear combination of the numbers $a$ and $b$ is a number of the form $ax+by$. For instance $3$ is a linear combination of $12$ and $21$ because $3 = 12\cdot 2 + 21\cdot (-1)$. Observe that the set of linear combinations of $a$ and $b$ is the set $a\zzz + b\zzz$.
1.25 DO: Prove: $a\zzz + b\zzz \le \zzz$ (i.e., the set of linear combinations of two numbers is a subgroup of $\zzz$).
1.26 DO: Prove: If $d$ is (i) a common divisor of $a$ and $b$ and (ii) $d$ is a linear combination of $a$ and $b$ then $d$ is a greatest common divisor of $a$ and $b$.
1.27 DO: Use the previous two exercises and Exercise 1.23
to prove the main result of this section:
Theorem. $(\forall a,b)(\exists d)(d$ is a greatest common divisor
of $a$ and $b$ and $d$ is a linear combination of $a$ and $b)$.
1.28 gcd NOTATION. Recall that if $d$ is agreatest common divisor of $a$ and $b$ then $-d$ is alos a greatest common divisor of $a$ and $b$. We write $\gcd(a,b)$ to denote the nonnegative greatest common divisor of $a$ and $b$. So for instance $\gcd(-12,-15)=3$ and $\gcd(a,a)=|a|$. We say that $a$ and $b$ are relatively prime if $\gcd(a,b)=1$.
1.29 HW (multiplication distributes over gcd, due Thursday, October 9): Prove: $\gcd(ac,bc) = \gcd(a,b)\cdot |c|$. Do not use unique prime factorization. Use that the greatest common divisor can be written as a linear combination. Hint: Prove that each side of this equation divides the other. Which direction is trivial, and which direction requires the theorem about linear combinations? (10 points)
1.30 DO: Use the previous exercie to prove that every prime number has the prime property. (Recall that a number $p$ is prime if $p\ge 2$ and the only positive divisors of $p$ are $1$ and $p$. Recall that an integer $r$ has the prime property if $(\forall x,y)((p\mid xy) \Rightarrow (p\mid x \ \vee \ p\mid y))$.
1.31 DO: Prove by induction that every integer has a prime factorization.
1.32 DO (Fundamental Theorem of Arithmetic): Use the prime property of prime numbers (Ex. 1.30) to prove that every positive integer has a unique prime factorization. The point is uniqueness; the existence is an easy exercise (1.31).
1.33 DO (greatest common divisor of a set of integers) (a) Let $S\subseteq \zzz$ be a set of integers. Define what it means that $d$ is a greatest common divisor of $S$. (b) Prove: every (finite or infinite) set of integers has a greatest common divisor and it can be written as a linear combination of (a finite number of) elements of $S$.
1.34 HW: Find $n$ positive integers such that their $\gcd$ is 1 but the $\gcd$ of any $(n-1)$ of them is greater than 1. (4 points)
1.35 DO (least common multiple): (a) Define least common multiple of a set of integers analogously to our definition of greatest common divisor. (b) Prove that $\lcm(S)$ exists. (Hint: you may use the fact that any, possibly infinite, set of integers has a $\gcd$.)
1.36 DO: Prove: $\gcd(a,b)\lcm(a,b)=|ab|.$
1.37 DEFINITION. We say that $a$ is congruent to $b$ modulo $m$,
notation: $a\equiv b \pmod m$, if $m \mid a-b$.
1.38 DO: (a) The $i$-th and the $j$-th days of the month fall on the same
day of the week $\iff$ $i\equiv j \pmod 7$ ("calendar arithmetic")
(b) $a\equiv b \pmod 2$ if either both $a$ and $b$ are even or both
$a$ and $b$ are odd.
(c) $(\forall a,b)(a\equiv b \pmod 1)$
(d) $(a\equiv b \pmod 0)\iff a=b$.
1.39 DO: Fix $m$. Prove: congruence modulo $m$ is an equivalence relations on $\zzz$. The equivalence classes are called modulo $m$ residue classes. What properties of divisibility are used to prove each property of the equivalence relation?
1.40 DO: Prove: for $m\ge 1$, the number of modulo $m$ residue classes is $m$.
1.41 DO: Prove: If $a\equiv x \pmod m$ and $b\equiv y \pmod m$ then (i) $a+b \equiv x+y \pmod m$; (ii) $a-b \equiv x-y \pmod m$; (iii) $ab \equiv xy \pmod m$.
1.42 HW, due Thursday, Oct 9: Prove: If $a\equiv b \pmod m$ then $(\forall k\ge 1)(a^k \equiv b^k \pmod m)$. (Hint: Induction on $k$. Use the preceding exercise.) (4 points)
1.43 DO: Prove: If $a\equiv b\pmod m$ and $d\mid m$ then $a\equiv b\pmod d$. From what property of divisibility does this follow? (WARNING: Typo corrected 10-8 6pm)
1.44 HW, due Thursday, Oct 9: Given $k,\ell$ find $m$ such that
$(\forall x,y)((x\equiv y\pmod m)\iff(x\equiv y \pmod k\ \wedge\
x\equiv y \pmod \ell))$. Prove your answer.
(8 points)
1.45 DO: Understand Fermat's little Theorem: If $p$ is a prime number then $(\forall a)(p\nmid a \Rightarrow a^{p-1}\equiv 1 \pmod p)$.
1.46 HW: Compute $3^{1,000,000}$ modulo 11. Your answer should be an integer between $0$ and $10$. Do not use any electronic devices. Clearly state and prove your answer. Your proof should be no more than two or three lines. It should involve no calculation you could not perform in your head. Use Fermat's little Theorem. (5 points)
1.47 HW (sum of three squares, due Thursday, Oct 9): Prove that there are infinitely many positive integers that cannot be written as the sum of three squares. (Hint: experiment with small numbers (say up to 50); notice pattern; formulate conjecture; prove.) (8 points)
1.48 CHALLENGE PROBLEM. Prove that in the divisor game over the positive divisors of the number $n\ge 2$, the first player has a winning strategy.
1.49 HW (due Thursday, Oct 9):
Recall that a sequence $a_1 < a_2 < \dots$ of positive integers
is superincreasing if for all $k$ we have
$a_k > \sum_{i=1}^{k-1} a_i$. For instance, the sequence
$a_i = 2^{i-1}$ $(i=1,2,\dots)$ is superincreasing.
Prove: If $a_1 < a_2 < \dots < a_n$ is a superincreasing sequence
and $I, J$ are two distinct subsets of $\{1,2,\dots,n\}$
(i.e., $I\neq J$) then $\sum_{i\in I} a_i \neq \sum_{j\in J} a_j$.
(8 points)