"LN" refers to the instructor's online DM lecture notes.
"LA" refers to the instructor's online Linear Algebra text available in two-column as well as single-column formats.
18.1 DO review coordinatization, effect of change of basis
18.2 DO Define the characteristic polynomial of a linear transformation.
18.3 DEF Review diagonalizability, eigenbasis, their equivalence (Exercises 17.41-17.45).
18.4 CH Prove: the diagonalizable matrices are dense in $M_n(\ccc)$.
18.5 DO Define angles in $\rrr^n$. Show your definition is sound using Cauchy--Schwarz.
18.6 DEF Define isometry of Euclidean spaces.
18.7 DO Prove: every $n$-dimenional Eclidean space is isometric with $\rrr^n$ (with the standard dot product).
18.8 DO Review orthogonal matrices, 3rd miracle (Ex. 17.56-17.59).
18.9 DO Prove: orthogonal matrices preserve the standard dot product, i.e., if $S\in M_n(\rrr)$ is an orthogonal matrix and $\bfx,\bfy\in \rrr^n$ then $(A\bfx)^T(A\bfy)=\bfx^T\bfy$.
18.10 DO Let $\lambda\in\ccc$ be an eigenvalue of the orthogonal matrix $A$. Prove: $|\lambda|=1$.
18.11 DO Find all $2\times 2$ orthogonal matrices. Show that they are the rotation matrices and the reflection matrices (corresponding to reflections in a line passing through the origin).
18.12 CH Prove: In dimension $n$, every orthogonal matrix is a product of reflection matrices (reflections in hyperplanes).
18.13 DO Review the Spectral Theorem (Ex. 17.61), its immediate consequences (17.62-17.66).
18.14 DO Ex.17.67: a matrix $A\in M_n(\rrr)$ is symmetric if and only if it is orthogonally diagonalizable.
18.15 DEF Let $A\in M_n(\rrr)$. The bilinear form associated with $A$ is the function $f(\bfx,\bfy)=\bfx^TA\bfy = \sum_i \sum_j a_{ij}x_iy_j$ for $\bfx,\bfy\in\rrr^n$.
18.16 DEF Let $A\in M_n(\rrr)$ be a symmetric matrix. The quadratic form associated with $A$ is the function $q(\bfx) = f(\bfx,\bfx)=\bfx^TA\bfx = \sum_i \sum_j a_{ij}x_ix_j$.
18.19 DEF We say that the quadratic form $q$ is positive definite if $(\forall \bfx\neq\bfzero)(q(\bfx) > 0)$.
18.20 DO Prove: the quadratic form $q$ is positive definite if and only if all eigenvalues of the corresponding symmetric matrix $A$ are positive.
18.21 CH Prove: the quadratic form $q$ is positive definite if and only if all corner determinants of the corresponding symmetric matrix $A$ are positive. The $k\times k$ corner determinants is the determinant of the $k\times k$ submatrix at the intersection of the first $k$ rows and the first $k$ columns.
18.23 DO Study quadratic forms, LA 11.3. Solve exercises 11.3.1--11.3.17.
18.24 DO Let $A\in M_n(\rrr)$ be symmetric with orthonormal eigenbasis $\ule=(\bfe_1,\dots,\bfe_n)$. Let $\bfx \in\rrr^n$ and let $[\bfx]_{\ule}= {\mathbf \alpha}= (\alpha_1,\dots,\alpha_n)^T$. Prove: $\bfx^TA\bfx= {\mathbf \alpha}^TD{\mathbf \alpha}$ where $D=\diag(\lambda_1,\dots,\lambda_n)$.
18.25 DO Use the Spectral Theorem to show that the equation $q(\bfx)=1$ defines a (possibly degerate) conic section in 2D (ellipse, hyperbola) and in 3D (ellipsoid, hyperboloids of two kinds).
18.26 DO Review the definition of the Rayleigh quotient, LA 10.2.5.
18.27 DO Prove Rayleigh's Principle, LA 10.2.6.
18.28 DO Let $A$ be the adjacency matrix of the graph $G$. Let $\lambda_1$ be the largest eigenvalue of $A$. Let $\deg_{\max}$ denote the maximum degree of vertices in $G$ and let $\deg_{\avg}$ denote the average degree. Prove: $$ \deg_{\avg} \le \lambda_1 \le \deg_{\max} $$
18.29 DO Understand and prove the Courant--Fischer theorem, LA 10.2.7
18.30 DO Let $f\in\rrr[t]$ be a polynomial such that all roots of $f$ are real. Prove: the roots and $f$ and the roots of $f'$ interlace.
18.31 DO Prove the interlacing property for symmetric real matrices, LA 10.2.8. (Use Courant--Fischer.)
18.32 DO Prove: for any $A\in\rrr^{k\times n}$, the matrix $A^TA$ is symmetric and all of its eigenvalues are nonnegative.
18.33 DO Study the operator norm, LA Chap. 13.1.
18.34 DO Prove LA 13.1.2 -- 13.1.13, 13.1.15.
18.35 DO (optional) Study the Singular Value Decomposition, LA Chap. 21.1.
18.36 DO (optional) (Low-rank approximation) Given $A\in \rrr^{k\times n}$, how do we find the nearest matrix $B\in \rrr^{k\times n}$ of rank $\le s$? Study LA, Chap. 21.2.
HW set #17, due Thursday, Nov 30. DO exercises due Wed Nov 29 before the problem session. Posted 11-28 at 8:25pm. READ the relevant sections from LA.
17.1 DEF/DO Isomorphism of vector spaces (must be over the same field!). Study LA, Chap 16.2
17.2 DO Prove: if a linear map is invertible then the inverse is also a linear map.
17.3 DO Prove: Isomorphism is an equivalence relation among vector spaces.
17.4 DO Coordinates of a vector, LA Def. 15.3.34.
17.5 DO If $V$ is a vector space of dimension $n$ over the field $\fff$ then $V\cong \fff^n$. Hint. Let $\ule=(\bfe_1,\dots,\bfe_n)$ be a basis of $V$. Prove that the correspondence $\bfv \mapsto [\bfv]_{\ule}$ is a $V\to\fff^n$ isomorphism.
17.6 COR If $V,W$ are vector spaces over the same filed then $V\cong W$ of and only if $\dim V=\dim W$.
17.7 DEF "Old" basis $\ule=(\bfe_1,\dots,\bfe_n)$, "new" basis $\ule=(\bfe_1',\dots,\bfe_n')$. Change of basis matrix $S=[[\bfe_1']_{\ule},\dots,[\bfe_n']_{\ule}]$.
17.8 DO Change of coordinates: $[\bfv]_{\ule'}=S^{-1}[\bfv]_{\ule}$.
17.9 EXAMPLE If $\bfe_i'= 2\bfe_i$ then $S=2I$ and $\bfv=\sum \alpha_i\bfe_i$ then $\bfv=\sum (1/2)\alpha_i\bfe_i'$ and therefore $[\bfv]_{\ule'} = (1/2)[\bfv]_{\ule}$. 17.10 DO LA Theorem 16.1.6 (Degree of freedom of linear maps) -- review, prove.
17.11 DO Prove: $\dim(\hom(V,W))=(\dim V)\cdot (\dim W)$.
17.12 DEF Coordinatization of linear maps. LA, Sec. 16.5. Given a linear map $\vf : V\to W$ and a basis $\ule=(\bfe_1,\dots,\bfe_n)$ of $V$ and a basis $\ulf=(\bff_1,\dots,\bff_n)$ of $V$ of $W$, the matrix $[\vf]_{\ule,\ulf}$ is defined as the $k\times n$ matrix of which the $j$-th column is $[\vf(\bfe_j)]_{\ulf}$.
17.13 THEOREM (DO) (Action of linear map corresponds to matrix multiplication) $(\forall \bfv\in V)([\vf(\bfv)]_{\ulf}=[\vf]_{\ule,\ulf}[\bfv]_{\ule}$
17.14 THEOREM (DO) (Composition of linear maps corresponds
to matrix multiplication)
Let $V,W,Z$ be vector spaces over the field $\fff$
with respective bases $\ule$, $\ulf$, and $\ulg$.
Let $\vf : V\to W$ and $\psi : W\to Z$ be linear maps.
Then $[\psi\vf]_{\ule,\ulg}=[\psi]_{\ulf,\ulg}[\vf]_{\ule,\ulf}$.
Use the previous exercise and the next exercise for the proof.
17.15 LEMMA (DO) Let $A, B\in \fff^{k\times n}$. Prove: $A=B$ if and only if $(\forall \bfx\in\fff^n)(A\bfx=B\bfx)$.
17.16 NOTATION If $\vf:V\to V$ is a linear transformation, we write $[\vf]_{\ule}$ for $[\vf]_{\ule,\ule}$.
17.17 DO all exercises in LA, Chap. 16.5 (Coordinatization)
17.18 DO Let $\rho_{\theta}$ be the rotation of the plane by $\theta$. Let $\bfe_1$ and $\bfe_2$ be two perpendicular unit vectors in the plane, and $\ule=(\bfe_1,\bfe_2)$. Then $$[\rho_{\theta}]_{\ule} = \left(\matrix{\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta}\right)$$
17.19 DO $\heartsuit$ Deduce the addition theorems for the trigonometric functions from Theorem 17.14 by applying it to the identity $\rho_{\alpha}\rho_{\beta}=\rho_{\alpha+\beta}$.
17.20 HW (a) Let $\theta$ be an angle, not of the form $k\pi$. Let $\bfe_1$ and $\bfe_2$ be two perpendicular unit vectors in the plane. Let $\bff_1=\bfe_1$ and $\bff_2=\rho_{\theta}\bfe_1$. Then $\ulf=(\bff_1,\bff_2)$ is a basis of the plane. Determine the matrix $[\rho_{\theta}]_{\ulf}$. (b) Compute the determinant and the trace of this matrix. (c) Compute the determinant and the trace of the "rotation matrix" $[\rho_{\theta}]_{\ule}$. Compare the answers to (b) and (c). Show your work. (The answers should be equal.)
17.21 THEOREM (DO) (Change of basis for linear maps) Let $\vf : V\to W$ be a linear map. Let us consider an old basis $\ule$ and a new basis $\ule'$ for $V$ as well as an old basis $\ulf$ and a new basis $\ulf'$ for $W$. Let $S=[\ule']_{\ule}$ be the corresponding basis change matrix for $V$ and $T=[\ulf']_{\ulf}$ the corresponding basis change matrix for $W$. Let $A=[\vf]_{\ule,\ulf}$ be the "old" matrix for $\vf$ and $A'=[\vf]_{\ule',\ulf'}$ the "new" matrix for $\vf$. Then $$ A' = T^{-1}AS .$$
17.22 COR (Change of basis for linear transformations) Let $\vf : V\to V$ be a linear transformation. Let us consider an old basis $\ule$ and a new basis $\ule'$ for $V$. Let $S=[\ule']_{\ule}$ be the corresponding basis change matrix. Let $A=[\vf]_{\ule}$ be the "old" matrix for $\vf$ and $A'=[\vf]_{\ule'}$ the "new" matrix for $\vf$. Then $$ A' = S^{-1}AS .$$
17.23 DEF Let $A,B\in M_n(\fff)$. We say that $A$ and $B$ are similar matrices if there exists a nonsingular matrix $S\in M_n(\fff)$ such that $B=S^{-1}AS$. Notation: $A\sim B$.
17.24 DO Prove: similarity is an equivalence relation on the set of square matrices.
17.25 COR The matrices that describe a linear transformation with respect to different bases are similar.
17.26 COR Show that the condition of the previous exercise is necessary sufficient for similarity. More precisely, let $V$ be an $n$-dimensional space over $\fff$. Prove that two matrices, $A, B\in M_n(\fff)$ are similar if and only if there exists a linear transformation $\vf : V\to V$ and two bases $\ule$ and $\ule'$ of $V$ such that $A=[\vf]_{\ule}$ and $B=[\vf]_{\ule'}$.
17.27 DO $\displaystyle{\det(S^{-1}) = \frac{1}{\det(S)}}$. Proof: $\det(S)\cdot\det(S^{-1})=\det(S\cdot S^{-1})= \det(I)=1$.
17.28 DO Prove: If $A\sim B$ then $\det(A)=\det(B)$.
17.29 DO Similar matrices have the same characteristic polynomial. Hint. If $A\sim B$ then $tI-A\sim tI-B$.
17.30 DO Let the characteristic polynomial of $A\in M_n(\fff)$ be $f_A(t)=t^n+a_{n-1}t^{n-1}+\dots+a_0$. Prove: (a) $a_{n-1}=-\trace(A)$ (b) $a_0 = (-1)^n \det(A)$. (Hint for (b): look at $f_A(0)$.)
17.31 COR Similar matrices have the same determinant and the same trace.
17.32 COR We can define the characteristic polynomial of a linear transformation $\vf:V\to V$ as follows. Pick a basis $\ule$ of $V$, take the characteristic polynomial of the matrix $[\vf]_{\ule}$. This polynomial does not depend on the choice of the basis $\ule$.
17.33 COR Let $A\sim B\in M_n(\fff)$. For each $\lambda\in\fff$, the algebraic multiplicity of $\lambda$ is the same in $A$ as in $B$.
17.34 HW Prove: similar matrices have the same rank.
17.35 COR Let $A\sim B\in M_n(\fff)$. For each $\lambda\in\fff$, the geometric multiplicity of $\lambda$ is the same in $A$ as in $B$.
17.36 DO Use the identity $\trace(AB)=\trace(BA)$ to give a half-line direct proof that similar matrices have the same trace.
17.37 HW (The characteristic polynomial is not a complete invariant of the similarity relation among square matrices) Show that the following two $2\times 2$ matrices have the same characteristic polynomial yet they are not similar: the identity matrix and the matrix $\displaystyle{A= \left(\matrix{1 & 1\\ 0 & 1}\right)}.$
17.38 THEOREM Let $A\in M_n(\ccc)$. Then $A$ is similar to a triangular matix.
17.39 DO Let $A\in M_n(\ccc)$ have characteristic polynomial $f_A(t)=\prod_{i=1}^n (t-\lambda_i)$. Prove: (a) $\trace(A)=\sum_{i=1}^n \lambda_i$ (b) $\det(A)=\prod_{i=1}^n \lambda_i$ . Use Thm 17.38. (What is the charcateristic polynomial of a triangular matrix?)
17.40 DO Prove 17.39 directly, without using Thm 17.38.
17.41 DEF An eigenbasis of a matrix $A\in M_n(\fff)$ is a basis of $\fff^n$ consisting of eigenvectors of $A$.
17.42 DEF We say that the matrix $A\in M_n(\fff)$ is diagonalizable if it is similar to a diagonal matrix.
17.43 DO Prove: $A\in M_n(\fff)$ is diagonalizable if and only if $A$ has an eigenbasis.
17.44 DO : Let $A\in M_n(\ccc)$. Suppose the characteristic polynomial $f_A$ has no multiple roots. Prove that $A$ is diagonalizable.
17.45 DO Show that having no multiple eigenvalues is not a necessary condition of diagonalizability over $\ccc$. (It is a sufficient condition by the preceding exercise.)
17.46 DEF Real Euclidean spaces. LA, Chap 19.1 (revised 11-28 at 7:30pm) Norm, orthogonality.
17.47 DO Verify that the exmaples given in LA, Ex. 19.1.3 are indeed Euclidean spaces.
17.48 DO Prove LA, Theorems 19.1.6 (Cauchy--Schwarz) and 19.1.7 (triangle inequality).
17.48 DO Let $X,Y$ be random variables. Prove: $|\cov(X,Y)|^2 \le \var(X)\cdot \var(Y)$. Use the relevant Euclidean space from LA, Ex. 19.1.3. Note that in this exercise, we are not assuming that the random variables are centered (i.e., that their expected value is zero).
17.49 HW Prove: if $\bfv_1,\dots,\bfv_k$ are pairwise orthogonal nonzero vectors in a Euclidean space then they are linearly independent.
17.50 DO Prove that the functions $1, \cos t, \sin t, \cos(2t),\sin(2t),\cos(3t),\sin(3t),\dots$ are linearly independent. Use LA, Ex. 19.1.12.
17.51 DEF An orthonormal system is a list of vectors $\bfv_1,\bfv_2,\dots$ such that $\langle \bfv_i,\bfv_j\rangle =\delta_{ij}$, i.e., all $\bfv_i$ have unit norma and they are pairwise orthogonal. An orthonormal basis (ONB) is an orthonormal system that is a basis.
17.52 THEOREM Every finite-dimensional Euclidean space has an ONB. Moreover, every orthonormal system can be extended to an ONB.
17.53 DO (optional) Study the Gram--Schmidt orthogonalization procedure, LA 19.2. A proof of Thm 17.52 follows from the procedure.
17.54 DO (Coordinates with respect to an ONB) Let $V$ be a Euclidean space, $\bfe_1,\dots,\bfe_n$ an ONB, and $\bfv=\sum_{i=1}^n \alpha_i\bfv_i$. Then $\alpha_i=\langle \bfe_i, \bfv\rangle. Finding the coordinates with respect to an ONB is also called Fourier expansion.
17.55 DO (Inner product via coordinates) Let $V$ be a Euclidean space, $\ule=(\bfe_1,\dots,\bfe_n)$ an ONB, and $\bfv,\bfw\in V$. Let $\bfx=[\bfv]_{\ule}$ and $\bfy=[\bfw]_{\ule}$. Then $\langle \bfv,\bfw\rangle = \bfx^T\bfy$ (standard dot product of the coordinate vectors).
17.56 DEF An orthogonal matrix is a matrix $S\in M_n(\rrr)$ such that the columns of $S$ form an ONB of $\rrr^n$ (with respect to the standard dot product).
17.57 DO $S\in M_n(\rrr)$ is orthogonal if and only if $S^TS=I$.
17.58 DO (Third miracle) If $S$ is an orthogonal matrix then so is $S^T$. In other words, if the columns of $S$ form an ONB of $\rrr^n$ then so do the rows.
17.59 DO Show that the rotation matrix is an orthogonal matrix.
17.60 DEF A matrix $A\in M_n(\rrr)$ is symmetric if $A=A^T$.
17.61 SPECTRAL THEOREM Every real symmetric matrix has an orthonormal eigenbasis.
17.62 COR &nbps; All (complex) eigenvalues of a real symmetric matrix are real.
17.63 COR Every real symmetric matrix is diagonalizable over $\rrr$.
17.64 DEF Let $A\in M_n(\rrr)$. We say that $A$ is orthogonally diagonalizable is there exists an orthogonal matrix $S$ such that $S^{-1}AS$ is a diagonal matrix.
17.65 THEOREM Every real symmetric matrix is orthogonally diagonalizable.
17.66 DO Prove that 17.65 is equivalent to the Spectral Theorem.
17.67 DO Prove: a matrix $A\in M_n(\rrr)$ is orthogonally diagonalizable if and only if $A$ is symmetric.
17.68 DO Prove by direct calculation that the eigenvalues of a $2\times 2$ real symmetric matrix are real. Hint: compute the discriminant of the characteristic polynomial.
17.69 DEF The image if a linear map $\vf : V\to W$ is the set $\imm(\vf):=\vf(V)=\{\vf(\bfv) \mid \bfv\in V\}$. The kernel of $\vf$ is $\ker(\vf):=\vf^{-1}(\bfzero)= \{\bfv\in V\mid \vf(\bfv=0\}$. The kernel is also called the null space of $\vf$.
17.70 DO Prove: the kernel is a subspace of $V$ and the image is a subspace of $W$.
17.71 (Rank-Nullity Theorem for linear maps) $\dim(\imm(\vf))$ is called the rank of $\vf$ and $\dim(\ker(\vf))$ the nullity of $\vf$. Prove: $\dim(\imm(\vf))+\dim(\ker(\vf)) =\dim(V)$.
17.72 How is this related to the rank-nullity theorem for matrices?
Remember: last class: Thursday, Nov 30. New material will be covered.
HW set #16, due Tuesday, Nov 28. First batch (16.1-16.49)
posted 11-25 at 4am. Full set posted 11-26 at 4:30am.
READ the relevant sections from LN and LA.
16.1 HW Prove: a triangle-free graph with $n$ vertices has at most $n^2/4$ edges. Hint: induction. Given a graph with $n$ vertices, remove a pair of adjacent vertices and apply the Inductive Hypothesis.
16.2 DO Study the definition of planar graphs. These are graphs that can be drawn in the plane so the arcs representing edges do not intersect. For instance, $K_4$ is planar.
16.3 DO Every subgraph of a planar graph is planar.
16.4 FACT (a) A planar graph with $n\ge 3$ vertices has at most $3n-6$ edges. (b) A triangle-free planar graph with $n\ge 3$ vertices has at most $2n-4$ edges.
16.5 DO Prove: (a) $K_5$ is not planar. (b) $K_{3,3}$ is not planar. Use the FACT above.
16.6 DO Prove: every planar graph has a vertex of degree $\le 5$. Use the FACT above.
16.7 HW Prove: every planar graph is 6-colorable. You may use the DO exercises above. Clearly state what you use. (N.B. Actually, every planar graph is 4-colorable -- this the is famous "Four-Color Theorem.")
16.8 DO Prove: the chromatic number of a triangle-free graph with $n$ vertices is $O(\sqrt{n})$.
16.9 READ The greedy coloring algorithm takes as input
a graph with vertex set $[n]$ and proceeds as follows.
for $i=1$ to $n$
color vertex $i$ by the smallest positive integer $c$ such that
$(\forall j < i)($ if $j\sim i$ then the color of $j$ is not $c)$
end(for)
16.10 DO Greedy coloring always provides a legal coloring of the graph. (Adjacent vertices never get the same color.)
16.11 DO (OK performance by greedy coloring) The greedy coloring algorithm colors every graph by no more than $1+\deg_{\max}$ colors.
16.12 DO (Dismal performance by greedy coloring) For every even number $n$, find a bipartite graph with vertex set $[n]$ on which the greedy coloring algorithm uses $n/2$ colors.
16.13 DO Study the basic terminology of directed graphs (digraphs) (in-degree, out-degree, directed walk, directed path, directed cycle) (LN).
16.14 DO Prove: (a) If the out-degree of every vertex in a directed graph $G$ is $k$ then $G$ is $(2k+1)$-colorable. (A legal coloring of a directed graph ignores the orientation of the edges; adjacent vertices must get different colors.) (b) Prove: this bound is tight for every $k\ge 1$. (You need to find a digraph where every vertex has out-degree $k$ and the digraph cannot be colored by fewer than $2k+1$ colors.)
16.15 CH Let $G$ be a graph with $n$ vertices. For a positive integer $t$, let $f_G(t)$ denote the number of legal colorings of $G$ using colors from the set $[t]$. (a) Prove: $f_G(t)$ is a polynomial of $t$. This polynomial is called the chromatic polynomial of $G$. (b) Prove that $f_G(t)$ has degree $n$ and is monic.
16.16 DO Find the chromatic polynomial of (a) $K_n$ (b) $\Kbar_n$ (c) $P_n$ (the path of length $(n-1)$ (d) all trees with $n$ vertices.
16.17 CH Find the chromatic polynomial of the $n$-cycle $C_n$.
16.18 DEF An orientation of a graph is an assignment of a direction to each edge. An orientation is acyclic if it has no directed cycle.
16.17 DO A graph with $m$ edges has $2^m$ orientations. Six out of the eight orientations of $K_3$ are acyclic.
16.18 DO Count the acyclic orientations of $K_n$.
16.19 CH (Richard Stanley) Prove: the number of acyclic orientations of the graph $G$ is $|f_G(-1)|$ where $f_G$ is the chromatic polynomial of $G$.
16.20 DEF The Erdös-Rényi G$(n,p)$ model of random graphs. Fix a set of $n$ vertices. For each of the $\binom{n}{2}$ pairs $\{i,j\}$ of vertices, perform an independent Bernoulli trial with success probability $p$. In case of success, make $\{i,j\}$ an edge of your "random graph" $G$; otherwise not.
16.21 HW Let $G=(V,E)$ be a random graph from the G$(n,p)$ model. (a) Determine the expected number of edges of $G$. (b) Determine the expected number of triangles in $G$. Prove your answer. (c) Determine the variance of the number of edges of $G$. Give a simple closed-form expression. Prove your answer. (d) Let $p=1/2$ and let $t_n$ denote the variance of the number of triangles. Prove that $t_n \sim an^b$ for some constants $a$ and $b$ (as $n\to\infty$). Determine the values of $a$ and $b$.
16.22 DEF The distance $\dist(u,v)$ between two vertices, $u$ and $v$, of the graph $G$ is the length of the shortest path between them. The diameter of $G$ is the maximum distance between pairs of vertices, i.e., $\max_{u,v\in V} \dist(u,v)$.
16.23 DO The diameter of $K_n$ is 1. The diameter of $C_5$ is 2. What is the diameter of $C_n$ ? What is the diameter of the complete bipartite graph $K_{n,n}$ ?
16.24 DO Find all trees of diameter 2.
16.25 DO Prove: almost all graphs have diameter 2. The meaning of this statement is the following. Let $p_n$ denote the probability that a random graph in the G$(n,1/2)$ model has diameter 2. Then $\lim_{n\to\infty} p_n = 1$.
16.26 REVIEW the definition of the parity (odd/even) of permutations (Ex. 15.28, also check LA) and the sign $\sgn(\sigma)$ of a permutation $\sigma$. Recall how this is used in the definition of the determinant.
16.27 DO Let $\sigma, \tau$ be permutations of $[n]$ and let $\sigma\tau$ denote their composition. Prove: $\sgn(\sigma\tau)=\sgn(\sigma)\sgn(\tau)$.
16.28 DO Prove: for $n\ge 2$, half of the $n!$ permutations of $[n]$ is even, the other half is odd.
16.29 DO Observe that the identity permutation is even. Infer from this that the determinant of a diagonal matrix $\diag(\lambda_1,\dots,\lambda_n)$ is $\prod \lambda_i$ (the product of the diagonal elements).
16.30 DO Prove: the determinant of a triangular matrix is the product of the diagonal elements.
16.31 DO Use the definition of the determinant to verify how elementary row and column operations affect the determinant.
16.32 DO Prove: the rank of a matrix $A$ is the largest $k$ such that $A$ has a nonsingular $k\times k$ submtarix.
16.33 DO Prove: $\det(AB)=\det(A)\det(B)$. Hint: perform elementary column operations on $B$; show that $AB$ undergoes the same elementary column operations. Once you reach a diagonal matrix from $B$, what happens to $AB$ ?
16.34 REVIEW cofactors and the expansion of the determinant by the $i$-th row (or column).
16.35 HW Compute the following $n\times n$ determinant. $$ B_n = \left(\matrix{1 & 1 & 0 & 0 & \cdots & 0 & 0 \\ -1 & 1 & 1 & 0 & \cdots & 0 & 0 \\ 0 & -1 & 1 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & & \ddots & & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & -1 & 1 }\right) $$ (The diagonal elements are $b_{ii}=1$, immediately above the diagonal is $b_{i,i+1}=1,$ and immediately below the diagonal is $b_{i,i-1}=-1$. All other entries are zero: if $|i-j|\ge 2$ then $b_{ij}=0$.) Your answer should be a simple closed-form expression in terms of a known sequence. Prove your answer.
16.36 STUDY the explicit form of the inverse matrix and Cramer's rule. (LA)
16.37 DO Let $A\in\rrr^{k\times n}$. Prove that the following statements are equivalent. (a) $A$ has a left inverse. (b) $A$ has full column rank. (c) The system $A\bfx=\bfzero$ of homogeneous linear equations has no nontrivial solution. (d) The system $A\bfx=\bfb$ of linear equations has at most one solution for every $\bfb$. (e) There exists $\bfb$ such that the system $A\bfx=\bfb$ of linear equations has a unique solution.
16.38 DO Let $A\in M_n(\rrr)$. Prove that the following statements are equivalent. (a) $A$ is nonsingular. (b) The system $A\bfx=\bfzero$ of homogeneous linear equations has no nontrivial solution. (d) The system $A\bfx=\bfb$ of linear equations has at least one solution for every $\bfb$. (e) The system $A\bfx=\bfb$ of linear equations has at most one solution for every $\bfb$. (f) The system $A\bfx=\bfb$ of linear equations has a unique solution for every $\bfb$. (g) There exists $\bfb$ such that the system $A\bfx=\bfb$ of linear equations has a unique solution.
16.39 HW One afternoon Dragon visits Princess and orders her to produce a nonsingular $10\times 10$ matrix. Every night at midnight, while Princess is supposed to be asleep (rather than be texting with her friends), Dragon sneaks into the palace and changes any number of entries in a row or a column of the matrix. (It is up to Dragon, which row or column she wants to alter.) At noon each day, Princess gets to change one entry of the matrix. (It is up to Princess, which entry she wants to alter.) If Princess is ever caught with a singular matrix in an afternoon, Dragon swoops down and devours Princess's cell phone. Let us help Princess keep texting indefinitely. (Prove that whatever Dragon does at midnight, next noon Princess can restore nonsingularity of the matrix.)
16.40 DO Let $A\in\rrr^{k\times n}$. Let $U=\{\bfx\in\rrr^n \mid A\bfx=\bfzero\}$. Prove that $U$ is a subspace. It is called the null-space of $A$.
16.41 DO (Rank-nullity Theorem) Prove: $\dim(U)=n-\rank(A)$.
16.42 REVIEW complex numbers. Remember: $\rrr\subset \ccc$ (every real number is a complex number).
16.43 DEF Let $A\in M_n(\ccc)$ and $\lambda\in\ccc$. The eigenspace of $A$ to scalar $\lambda$ is the space $U_{\lambda}=\{\bfx\in\ccc^n \mid A\bfx = \lambda\bfx\}$.
16.44 DO Show that $U_{\lambda}$ is the nullspace of the matrix $\lambda I-A$.
16.45 DEF/DO $\dim(U_{\lambda})$ is the geometric multiplicity of $\lambda$. Note that this number is $n-\rank(\lambda I - A)$.
16.46 DO Prove: $\lambda$ is an eigenvalue of $A$ if and only if its geometric multiplicity is not zero.
16.47 DEF/DO Let $A\in M_n(\ccc)$. Let $t$ be a variable and let $f_A(t)=\det(tI-A)$. Prove: $f_A(t)$ is a monic polynomial of degree $n$. It is called the characteristic polynomial of $A$.
16.48 DO $\lambda\in\ccc$ is an eigenvalue of $A$ if and only if $f_A(\lambda)=0$. In other words, the eigenvalues are precisely the roots of the characteristic polynomial.
16.49 COROLLARY. An $n\times n$ matrix has at most $n$ eigenvalues. (Prove!)
16.50 ARITHMETIC OF POLYNOMIALS over a field $\fff$. (Think of $\fff$ being either $\rrr$ or $\ccc$.) Define divisibility, gcd among polynomials over $\fff$ (with coefficients in $\fff$) analgously to integers.
16.51 DIVISION THEOREM for polynomials over $\fff$. $(\forall f,g\in\fff[t])($ if $g\neq 0$ then $(\exists! q,r\in\fff[t])(f=qg+r$ and $\deg(r)<\deg(g))$. (Prove!)
16.52 DO Use the Division Theorem to prove the existence of gcd. Design Euclid's algorithm for polynomials.
16.53 DO Prove: $(\forall f\in\fff[t])(\forall \alpha\in\fff) (t-\alpha \mid f(t)-f(\alpha))$.
16.54 COROLLARY $\alpha\in \fff$ is a root of $f\in\fff[t]$ (i.e., $f(\alpha)=0$) if and only if $t-\alpha \mid f$.
16.55 COROLLARY A polynomial of degree $k\ge 0$ has at most $k$ roots.
16.56 FUNDAMENTAL THEOREM OF ALGEBRA. If $f\in\ccc[t]$ has degree $\ge 1$ then $f$ has a complex root.
16.57 COROLLARY If $f\in \ccc[t]$ has degree $n\ge 0$ then $f$ can be written as $f(t)=a_n\prod_{i=1}^k(t-z_i)^{m_i}$ where $a_n$ is the leading coefficient of $f$, the $z_i$ are distinct complex numbers (the distinct roots of $f$), $m_i$ is the multiplicity of the root $z_i$, and $\sum_{i=1}^k m_i=n$.
16.58 DEF We say that $\alpha\in\fff$ is a multiple root of $f\in\fff[t]$ if $(t-\alpha)^2 \mid f(t)$.
16.59 HW Prove: $\alpha\in\fff$ is a multiple root of $f\in\fff[t]$ if and only if $f(\alpha)=f'(\alpha)=0$. Here $f'$ denotes the derivative of $f$.
16.60 COROLLARY The multiple roots of $f$ are precisely the roots of $\gcd(f,f')$. (Prove!)
16.61 DO Prove: if $n\ge 2$ then the polynomial $f(t)=t^n+t+1$ has no multiple roots in $\ccc$.
16.62 DEF Let $A\in M_n(\ccc)$. The algebraic multiplicity of the eigenvalue $\lambda\in\ccc$ is the multiplicity of $\lambda$ in the charactristic polynomial $f_A$.
16.63 DO Prove: for every $\lambda$, the geometric multiplicity is less than or equal to the algebraic multiplicity: $\geom_A(\lambda)\le\alg_A(\lambda)$.
16.64 DO Prove: for a diagonal matrix, the geometric and the algebraic multiplicity of each eigenvalue is equal.
16.65 DO Let $A=(a_{ij})\in\fff[t]$ be a triangular matrix. Then the characteristic polynomial of $A$ is $f_A(t)=\prod_{i=1}^n (t-a_{ii})$. In particular, the eigenvalues are precisely the diagonal elements, and the algebraic multiplicity of $\lambda$ is the number of times $\lambda$ occurs in the diagonal.
16.66 HW Determine the eigenvalues and their algebraic and geometric multiplicities for the matrix $$A= \left(\matrix{1 & 1\\ 0 & 1}\right)$$
16.67 HW For every $n$ find an $n\times n$ matrix $A$ such that the only eigenvalue of $A$ is zero (and therefore the algebraic multiplicity of zero is $n$) but the geometric multiplicity of zero is 1.
16.68 HW Determine the complex eigenvalues of the "rotation matrix" $$ R_{\theta} = \left(\matrix{\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta}\right)$$ and find an eigenvector to each eigenvalue.
16.69 CH If the diameter of the connected graph $G$ is $d$ then the adjacency matrix of $G$ has at least $d+1$ distinct eigenvalues.
16.70 HW LA has been posted in two-column as well as in single-column formats. Which format is easier for you to read? (Please spend a few minutes reading each version and comparing before you answer this question.) Your answer could be "single-column is easier to read" or "the two-column format is easier to read" or "there is no noticeable difference between the two." Feel free to add any further comments on the pros and cons of each layout.
HW set #15, due Tuesday, Nov 21 except where other due date is specified. -- First batch (15.1-15.15) posted 11-20 at 3:05am. Full set posted 11-20 at 3:55pm. Two HW problems not stated in class have been added.
15.1 DO Review First Miracle of Linear Algebra (LA Chaps. 1.3 and 15.4). Study its proof (Chap 15.4).
15.2 DEF Let $A\in\rrr^{k\times n}$. The column space of $A$, denoted $\col(A)$, is the span of the columns of $A$.
15.3 DO Prove: the column rank of $A$ (max number of linearly independent columns of $A$) is equal to $\dim(\col(A))$. In fact this statement is equivalent to the First Miracle.
15.4 DO The system $A\bfx=\bfb$ is solvable if and only if the column-rank of $A$ is the same as the column-rank of the $k\times (n+1)$ "augmented matrix" $[A\mid b]$ (we added $b$ as an $(n+1)$-st column).
15.5 HW Prove: $\col\rank(A+B)\le\col\rank(A)+\col\rank(B)$.
15.6 DO Prove: $\col(AB)\le \col(A)$, i.e., the column space of $AB$ is a subspace of the column space of $A$.
15.7 COROLLARY $\col\rank(AB)\le \col\rank(A)$.
15.8 DO Derive from 15.6 and the Second Miracle that $\rank(AB) \le \min\{\rank(A),\rank(B)\}$.
15.9 DO Study the elementary column operations (shearing, scaling, swapping) (LA Sec. 3.2).
15.10 DO Show that the elementary column operations are invertilbe and the inverse of each is an elementary operation of the same kind.
15.11 DO Prove that elementary column operations do not change the column space.
15.12 COROLLARY Elementary column operations do not change the column rank.
15.13 HW Find a matrix $A=[v_1,\dots,v_5]\in \rrr^{3\times 5}$ such that the first three columns of $A$ are linearly independent, but after a column shearing operation, the first three columns are linearly dependent. State the shearing operation you apply and the resulting matrix $A'\in \rrr^{3\times 5}$.
15.14 HW Find a real matrix $A$ and find three elementary row operations: a shearing, a scaling, and a swapping, such that each of these operations changes the column space of $A$. Make your matrix as small as possible. Prove that the column space has changed in each case.
15.15 DO Show that elementary row operations preserve the linear relations among the columns. More formally, let $A=[\bfa_1,\dots,\bfa_n]\in\rrr^{k\times n}$, and let $A'= [\bfa_1',\dots,\bfa_n']\in\rrr^{k\times n}$ be the result of an elementary row operation applied to $A$. (The $\bfa_i$ are the columns of $A$ and the $\bfa_i'$ are the columns of $A'$.) Let $\alpha_1,\dots, \alpha_n\in\rrr$. Prove: if $\sum_{j=1}^n \alpha_j\bfa_j=\bfzero$ then $\sum_{j=1}^n \alpha_j\bfa_j'=\bfzero$.
15.16 DO Prove: If certain columns of $A$ are linearly independent, then the same columns remain linearly independent after an elementary row operation.
15.17 DO Prove: If a matrix $D\in\rrr^{k\times\ell}$ has at most one non-zero entry in each row and at most one non-zero entry in each column then the row-rank and the column-rank of $D$ are equal and their common value is the number of nonzero entries in $D$.
15.18 DO Given any matrix $A\in\rrr^{k\times\ell}$, prove that there is a sequence of row and column shearing operations that turns the matrix into some matrix $D$ of the form described in the preceding exercise.
15.19 DO Infer the Second Miracle (row rank = column rank) from the preceding three exercises.
15.20 DEF We say that a matrix $A\in\rrr^{k\times n}$ has full row rank if its rows are linearly independent, i.e., $\rank(A)=k$. We say that $A$ has full column rank if its columns are linearly independent, i.e., $\rank(A)=n$.
15.21 DO : Prove: (a) $A\in\rrr^{k\times \ell}$ has full row rank $\iff$ the columns of $A$ span $\rrr^k$. (b) $A\in\rrr^{k\times \ell}$ has full column rank $\iff$ the rows of $A$ span $\rrr^n$.
15.22 DO Define right inverse and left inverse.
15.23 DO Prove: (a) $A$ has a right inverse $\iff$ $A$ has full row rank. (b) $A$ has a left inverse $\iff$ $A$ has full column rank $\iff$ the homogeneous system $A\bfx=\bfzero$ of linear equations has no nontrivial solution.
15.24 DO Prove: if $A$ has a left inverse $B$ and a right inverse $C$ then $B=C$. Consequently, if a left inverse exists then there is at most one right inverse and conversely.
HW 15.25 Find a matrix that has infinitely many right inverses. Make your matrix as small as possible. Describe the set of all right inverses of your matrix.
15.26 DO If a left inverse as well as a right inverse exists then the matrix is a square matrix and a two-sided inverse exists.
15.27 DO/DEF A matrix $A\in M_n(\rrr)$ is called nonsingular if any of the following equivalent conditions holds. Prove that these are indeed equivalent.
15.28 DEF Look up the definition of even and odd permutations in LA, Chap. 6.1. Here are the pertinent facts. A transposition is a permutation that swaps two elements and fixes all other elements of the permutation domain.
15.28 DEF (determinant) Recall that the function $\det : M_n(\rrr)\to\rrr$ is defined by the formula $$ \det(A) = \sum_{\sigma\in\perm(n)} \sgn(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}$$ where $\perm(n)$ denotes the set of all permutations of $[n]$.
15.29 DO If $A$ has an all-zero column then $\det(A)=0$.
15.30 DO Prove: shearing does not change the value of the determinant.
15.31 HW Prove: If the columns of $A$ are linearly dependent then $\det(A)=0$. Hint: Use a series of column shearing operations to create an all-zero column. State the shearings used.
15.33 DO Swapping two columns switches the sign of the determinant: $\det(A')=-\det(A)$.
15.34 DO Scaling a column by $\lambda$ multiplies the determinant by $\lambda$: $\det(A')=\lambda\det(A)$.
15.35 DO Prove: $\det(\lambda A)=\lambda^n\det(A)$.
15.36 DO The identity permutation is even.
15.37 DO Prove: If $A$ has full rank then $\det(A)\neq 0$. Hint: use column shearing and column swapping operations to bring the matrix to diagonal form. The resulting matrix $D$ has the same rank as $A$ so $D$ has full rank and therefore none of the diagonal entries $d_{ii}$ is zero. On the other hand, $\det(D)=\prod_{i=1}^n d_{ii}$ by the preceding exercise (identity is even), and $\det(A)=(-1)^k\det(D)$, where $k$ is the number of column swappings employed in turning $A$ into $D$.
15.38 THEOREM (Multiplicativity of the determinant) (DO) Prove: if $A,B\in M_n(\rrr)$ then $\det(AB)=\det(A)\det(B)$. Hint. If $B$ does not have full rank then both sides are zero. (Why?) If $B$ has full rank, transform it into a diagonal matrix as in the preceding exercise and follow what happens to $AB$.
15.39 DO The determinant of a triangular matrix is the product of the diagonal.
15.40 HW (a) Calculate the determinant of the $n\times n$ matrix described in LA, Ex. 6.3.4 (a) (all diagnoal elements are $\alpha$, all off-diagonal elements are $\beta$). Use a series of elementary opreation to turn the matrix into a triangular matrix. State the series of elementary operations used. Show your intermediate results. Your answer should be a product of $n$ linear factors in terms of $\alpha$ and $\beta$. (b) State, for what pairs $(\alpha,\beta)$ is this matrix nonsingular.
14.1 WARNING. Last night (11-15 0:30am) I updated several of the relevant sections of LA, and did more updating today (11-15 at 1:30pm). If you downoaded the book, please download it again.
14.2 DO Review the abstract definition of vector spaces (LA, Chap 15). You can always think of $\fff$, the "field of scalars," as $\rrr$, or, later, $\ccc$.
14.3 DO Review the concept of linear independence.
14.4 DO Prove: (a) the empty set is linearly independent; (b) a set $\{\bfv\}$ of just one vector, $\bfv$, is linearly dependent if and only if $\bfv = \bfzero$; (c) a list of two vectors is linearly dependent if and only if one of them is a scalar times the other.
14.5 DO A sublist of a linearly independent list of vectors is linearly independent. In particular, a linearly independent list of vectors cannot include the zero vector, and it cannot include the same vector twice.
14.6 DO (Maximality lemma) Prove: If $\bfv_1,\dots,\bfv_k$ are linearly independent but $\bfv_1,\dots,\bfv_k,\bfw$ are linearly dependent then $\bfw\in\span(\bfv_1,\dots,\bfv_k)$, i.e., $\bfw$ can be written as a linear combination of the $\bfv_i$. --- This lemma plays a central role in understanding dimension; in particular, it is central to the proof of the "First Miracle of Linear Algebra."
14.7 DEF A list $L$ of vectors generates $V$ if $\span(L)=V$. In this case we refer to $L$ as a list of generators.
14.8 DEF A basis of $V$ is a linearly independent list of generators.
14.9 DO A list $L$ of vectors is a basis if and only if $L$ is a maximal linearly independent list (i.e., $L$ is linearly independent, but if we add a vector to it, it becomes linearly dependent). --- The proof will be based on the Maximality lemma, 14.6.
14.10 DO (Coordinates) A list $B=[\bfv_1,\dots,\bfv_k]$ is a basis if and only if every vector $\bfw\in V$ can be uniquely written as a linear combination of the $v_i$, i.e., $(\exists! \alpha_1,\dots,\alpha_k\in\rrr)(\bfw=\sum_{i=1}^k \alpha_i\bfv_i)$. The $\alpha_i$ are called the coordinates of $\bfw$ with respect to the basis $B$.
14.11 DO Prove: the polynomials $1,t,t^2,\dots$ form a basis of $\rrr[t]$, the space of polynomials.
14.12 DO Prove: the columns of the identity matrix form a basis of $\rrr^n$.
14.13 DEF We say that a vector space $V$ is finite-dimensional if there exists an integer $k$ such that every linearly independent list has length at most $k$.
14.14 THEOREM Every vector space has a basis.
Proof for the finite-dimensional case: algorithmic.
$L \leftarrow$ empty list. (Loop invariant: $L$ is linearly independent.)
while $L$ not maximal, add a vector to it so it remains linearly
independent
return $L$
The correctness of this algorithm follows from Ex. 14.9. (Note that this proof is based on the Maximality lemma, 14.6, through 14.9.)
Proof for the infinite-dimensional case (optional). Use Zorn's lemma to show that a maximal linearly independent set of vectors exists. Then we are again done by Ex. 14.9.
14.15 THEOREM (First Miracle of Linear Algebra) Let $\bfv_1,\dots,\bfv_k$ be linearly independent vectors and let $\bfw_1,\dots,\bfw_{\ell}$ be vectors such that $\bfv_1,\dots,\bfv_k \in \span(\bfw_1,\dots,\bfw_{\ell})$. Then $k\le \ell$. ("Impossibility of boosting linear independence")
14.16 DO Check the proof in LA. Note that it is based on the Maximality lemma.
The following series of corollaries illustrates the central role this result plays in linear algebra.
14.17 COROLLARY (DO!) If $B_1$ and $B_2$ are bases of $V$ then $|B_1|=|B_2|$.
14.18 COROLLARY (DO!) $\dim(\rrr^n) = n$.
14.19 COROLLARY (DO!) Every maximal linearly independent set is maximum.
14.20 RECALL: The column space of a matrix is span of the columns. The column-rank of a matrix is the maximum number of linearly independent columns of the matrix.
14.21 COROLLARY (DO!) Let $A$ be a matrix and let $\bfa_1,\dots,\bfa_k$ be a maximal independent set of columns of $A$. Then the column-rank of $A$ is $k$ and $\bfa_1,\dots,\bfa_k$ is a basis of the column space of $A$. In particular, $\bfa_1,\dots,\bfa_k$ is a maximum independent set of columns.
14.22 STUDY Linear maps (LA, Chap. 16.1) and linear transformations (LA, Chap. 16.4) Examples of linear maps, especially linear transformations in 2D and 3D geometry.
14.23 THEOREM (DO!) (Degree of freedom of a linear map) Let $V, W$ be vector spaces, $\bfe_1,\dots,\bfe_n$ a basis of $V$, and $\bfw_1,\dots,\bfw_n\in W$ be arbitrary vectors. Then there exists a unique linear map $\vf : V\to W$ such that $(\forall i)(\vf(\bfe_i)=\bfw_i)$.
14.24 STUDY Eigenvectors, eigenvalues (LA, Chap. 8.1 and 16.4.1).
14.25 DO Solve all exercises in Chap. 8.1 except 8.1.24 (b) and (c).
14.26 HW Let $\vf : V\to V$ be a linear transformation. Prove: If $\bfv_1,\dots,\bfv_k$ are eigenvectors to distinct eigenvalues then they are linearly independent.
14.27 HW Let $S$ denote the left shift transformation of the space $\rrr^{\nnn}$ of infinite sequences of real numbers, defined by $S(\alpha_0,\alpha_1,\alpha_2,\dots) = (\alpha_1,\alpha_2,\alpha_3,\dots)$. Find all eigenvalues and eigenvectors of this transformation.
14.28 STUDY the determinant from LA, Chapters 6.1 and 6.2.
HW set #13, due Tuesday, Nov 14 except where other due date is specified. -- First batch (13.1-13.11) posted 11-12 at 7:00pm, full set posted 11-13 at 1:10am. Do not forget: there are HW problems assigned last Tuesday that are also due Tue Nov 14, namely, 12.21, 12.26, 12.31, 12.32. If you already submitted some of these, please resubmit. Please submit solutions on their due date; early submission causes clerical difficulties to the grading team.
13.1 STUDY instructor's online Linear Algebra text (LA).
13.2 DO STUDY LA, Chapters 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 3.1, 4.1, 4.2,
15.1, 15.2, and 15.3,
except for the references to the determinant in Chapters 4.1 and 4.2
which will be due Wednesday, November 15.
(Replace $\fff$ by $\rrr$ in all exercises for now.)
Understand especially Examples 15.1.5.
Solve most exercises in the chapters listed,
including but not limited to those stated in class.
13.3 HW Prove that the columns of the $3\times 3$ matrix $B$ below are linarly independent. Use only the definition of linear independence given in class and in LA. Do not use any results or algorithms related to linear independence or rank. Show your work. $$ B=\left(\matrix{-1 & 2 & 1 \\ 0 & 7 & 2 \\ 5 & 3 & 4}\right) .$$
13.4 HW Find a $2\times 2$ matrix $A$ such that $A\neq 0$ but $A^2=0$. (a) Make your matrix $A$ such that at least one of its entries is zero. (b) Make your matrix $A$ such that none of its entries is zero.
13.5 HW Let $A\in \rrr^{k\times\ell}$ and $B\in \rrr^{\ell\times k}$. Prove: $\trace(AB)=\trace(BA)$. (Recall that the trace of a square matrix is the sum of its diagonal elements. Note that $AB$ is a $k\times k$ matrix and $BA$ is an $\ell\times\ell$ mtrix.)
13.6 REVIEW the concept of polynomials and the basic properties of their degree. Recall the convention $\deg(0)=-\infty$. Show that with this convention in place, we have (a) $\deg(f+g)\le \max\{\deg(f),\deg(g)\}$ and (b) $\deg(fg)=\deg(f)+\deg(g)$ for all pairs of polynomials $f,g\in\rrr[t]$, no exceptions.
HW 13.7 Solve LA Exercise 15.2.6. This exercise asks you to decide about an number of subsets of the space $\rrr[t]$ of polynomials whether or not they are subspaces. Clearly state your answer in each case ("YES" meaning it is a subspace, "NO" meaning it is not). When you claim "YES," no proof is necessary. When you claim "NO," prove your answer. (Hint. Remember that every subspace must contain the zero vector -- in this case, the zero polynomial.)
13.8 HW Let $\alpha_1, \dots, \alpha_k$ be $k$ distinct real numbers. Let $f(t)=\prod_{i=1}^k (t-\alpha_i)$. This is a polynomial of degree $k$ in $\rrr[t]$. For $j=1,\dots,k$, let $g_j(t)=f(t)/(t-\alpha_j)$. This is a polynomial of degree $k-1$ (we cancel out one term of the product). Prove: the polynomials $g_1,\dots,g_k$ are linearly independent. Your proof should begin with the assumption that $\sum_{j=1}^k \beta_j g_j=0$ for some (unknown) real numbers $\beta_i$. The desired conclusion from this assumption should be that $\beta_1=\dots=\beta_k=0$. Note that this is not a "proof by contradiction" -- it is a direct application of the definition of linear independence.
13.9 DO Prove: $(AB)^T=B^TA^T$ where $A^T$ denotes the transpose of the matrix $A$.
13.10 UNDERSTAND that a system of $k$ linear equations in $n$ unknowns can be written as $A\bfx=\bfb$ where $A\in\rrr^{k\times n}$, $\bfb\in \rrr^{k\times 1}$ are given and $\bfx\in\rrr^{n\times 1}$ is an unkown column vector.
13.11 DO Prove: the system $A\bfx=\bfb$ is solvable if and only if $\bfb$ can be written as a linear combination of the columns of $A$, i.e., if $\bfb$ belongs to the column space of $A$ (defined as the span of the columns of $A$).
13.12 HW Consider the $k\times \ell$ matrix $B=(\beta_{ij})$ where $\beta_{ij}=ij$ ($1\le i\le k$, $1\le j\le\ell$). ($k,\ell \ge 1.$) Determine the column-rank of $B$, i.e., the maximum number of linearly independent columns of $B$. Do not use any theorems related to the rank or any algorithms to determine the rank of general matrices; use only the definition of linear independence.
13.13 HW Let $|\Omega|=n$. Find $n+1$ functions in the space $\rrr^{\Omega}$ of $\Omega\to\rrr$ functions such that every $n$ of them are linearly independent. (Note: as we shall see, every list of $n+1$ functions in $\rrr^{\Omega}$ is linearly dependent; this nontrivial fact is equivalent to the "First Miracle of Linear Algebra.")
13.14 DO Observe: in the space $\rrr[t]$ of polynomials (where $t$ denotes the variable) the following infinite list of polynomials is linearly independent by definition: $1,t,t^2,\dots$. (An inifinite list of vectors is linearly independent by definition if every finite sublist is linearly independent.)
13.15 DO Let $f_0,f_1,f_2,\dots\in\rrr[t]$ be an infinite sequence of polynomials such that $(\forall i)(\deg(f_i)=i)$. Prove: the $f_i$ are linearly independent.
13.16 DO Prove: if $f\in\rrr[t]$ is a polynomial of degree $k\ge 0$ then $f$ has at most $k$ distinct roots.
13.17 DEF The Vandermonde matrix $V_n(x_1,\dots, x_n)=(v_{ij})$ is an $n\times n$ matrix where the $(i,j)$-entry is $v_{ij}=x_j^{i-1}$. So the $j$-th column is the geometric progression $1,x_j,x_j^2,\dots,x_j^{n-1}$.
13.18 HW (due Thursday, Nov 16) Prove: if $x_1,\dots,x_n$ are distinct real numbers then the rows of the $n\times n$ Vandermonde matrix $V_n(x_1,\dots, x_n)$ are linearly independent. Use exercise 13.16 and the definition of linear independence only. Do not use any results or algorithms regarding linear independence and rank.
13.19 DEF Let $G=(V,E)$ be a graph where $V=[n]$. The adjacency matrix of $G$ is an $n\times n$ matrix $A_G=(a_{ij})$ where for $1\le i,j\le n$ we set $$ a_{ij}=\cases{1 & if $i\sim j$\\ 0 & if $i\not\sim j$ }$$ In particular, $(\forall i)(a_{ii}=0)$ (all diagonal elements are zero). 13.19a NOTE on notation. Properly we should insert a comma between the double subscript, like $a_{i,j}$. We often omit this comma for typographic convenience; but we must be careful not to omit the comma if the omission could be misunderstood as multiplication.
13.19b DO Observe: $\trace(A_G)=0$.
13.20a DO Let $B=(b_{ij})=A_G^2$. Prove: $b_{ij}$ is the number of common neighbors of $i$ and $j$. In particular, $b_{ii}=\deg(i)$.
13.20b DO Let $C=(c_{ij})=A_G^k$. Prove: $c_{ij}$ counts the walks of length $k$ from $i$ to $j$.
13.21 DO The graph $G$ is regular of degree $r$ if and only if (a) the sum of each row of $A_G$ is $r$ and equivalently if and only if $A_G\bfone=r\cdot\bfone$ where $\bfone=(1,1,\dots,1)^T$ is the all-ones column vector.
13.22 HW Let $G$ be a regular graph of degree $r$. Let $k\ge 0$. Prove: the sum of each row of $A_G^k$ is $r^k$. You may use the exercise 13.20.
13.23 HW Let the graph $G$ have $n$ vertices, $m$ edges, and $t$ triangles. (So $0\le m\le \binom{n}{2}$ and $0\le t\le \binom{n}{3}$.) Let $A=A_G$ be the adjacency matrix. Compute (a) $\trace(A^2)$ (b) $\trace(A^3)$. Your answers should be very simple closed-form expressions in terms of the parameters $n,m,t$. Reason your answers.
13.24 HW (due Thursday, Nov 16) Let $G$ be a graph with $n$ vertices and $m$ edges. Prove: $G$ has a bipartite subgraph with $\ge m/2$ edges. Hint: color the vertices red and blue at random. Compute the expected number of red-blue edges.
13.25 DO Prove: (a) a bipartite graph with $n$ vertices has at most $n^2/4$ edges. (b) Prove that this bound is tight, i.e., for every $n$ there exists a bipartite graph with $m=\lfloor n^2/4\rfloor$ edges. (Typo in formulas fixed 11-13 at 4:30pm.)
13.26 CH Prove: a triangle-free graph has at most $n^2/4$ edges. (Typo in formula fixed 11-13 at 4:30pm.)
13.27 CH Prove: if a graph does not contain 4-cycles then $m=O(n^{3/2})$. Specify the implicit constant you get.
13.28 CH Prove: if the graph $G$ is triangle-free then $\chi(G)=O(\sqrt{n})$. Specify the implicit constant you get.
HW set #12, HW problems due Thursday, Nov 7 unless otherwise stated. DO exercises due Wednesday, 11-08, before the problem session. -- Posted 11-08 at 4:30am.
12.01 DO REVIEW matrix multiplication.
12.02 HW Let $A$ and $B$ be the following $2\times 2$ matrices. $$ A=\left(\matrix{1 & 1 \\ 0 & 1}\right) \quad\text{ and}\quad B=\left(\matrix{0 & 1 \\ 1 & 1}\right) .$$ Compute $A^n$ and $B^n$. Your answers should be very simple, the entries of each matrix given by simple closed-form expressions involving functions/sequences discussed in class.
12.04 DO Study Petersen's graph and learn the spelling of Petersen's name.
12.05 DEF The girth of a graph is the length of its shortest cycle. If the graph has no cycle, the girth is infinite.
12.06 DO The girth of Petersen's graph is 5.
12.07 HW Prove: If $G$ is a regular graph of degree $r$ and girth $\ge 5$ then $n\ge r^2+1$.
12.08 HW Find an automorphism of Petersen's graph that moves a vertex on the outer pentagon to a vertex inside that pentagon.
12.09 DO (optional) Prove: Petersen's graph has 120 automorphisms.
12.10 DEF An arc is a walk without immediate reversals. (It is permitted to repeat vertices but not to immediately backtrack.) So an arc of length $k$ is a sequence $x_0,x_1,\dots,x_k$ of vertices such that $(\forall i\ge 1)(x_{i-1}\sim x_i)$ and $(\forall i\ge 1)(x_{i-1}\neq x_{i+1})$.
12.11 DO Count the arcs of length 3 in the Petersen graph. (The answer is $10\times 3\times 2\times 2=120$. Why?)
12.12 DO (optional) Prove: for every pair $(A,B)$ of arcs of length 3 in the Petersen graph, there is an automorphism of the Petersen graph that moves $A$ to $B$.
12.13 HW Prove that Petersen's graph is isomorphic to another drawing shown in class that has a symmetry of order 3 (120-degree rotations don't change the drawing). (You don't need to Latex your figures, just hand-draw them.)
12.14 DO Prove: a graph $G$ is bipartite if and only if $G$ contains no odd cycles.
12.15 DEFINITION. A legal coloring of a graph is a function $f: V\to \{\text{colors}\}$ such that $(\forall x,y\in V)(x\sim y \implies f(x)\neq f(y))$, i.e., 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.
12.16 OBSERVE: $G$ is $k$-colorable if and only if $\chi(G)\le k$.
12.17 DO Observe that for all graphs $G$ we have $1\le \chi(G)\le n$. Prove: $\chi(G)=1 \iff G\cong \Kbar_n$.
12.18 HW Prove: $\chi(G)=n \iff G \cong K_n$.
12.19 DO Prove: $G$ is bipartite if and only if $G$ is 2-colorable.
12.20 DO: Determine the chromatic number of (a) the $n$-cycle (b) the $k\times\ell$ grid.
12.21 HW (due Tue, Nov 14) Let $\deg_{\max}$ denote the maximum degree of the graph $G$, i.e., $\deg_{\max}=\max\{\deg(x) \mid x\in V\}$. Prove: $\chi(G)\le \deg_{\max}+1$. Your proof should be algorithmic: provide a clearly stated algorithm that colors the graph by at most $\deg_{\max}+1$ colors. Best is if you write your algorithm in pseudocode, but this is not required.
12.22 HW For all $n\ge 3$, find a graph $G_n$ with $n$ vertices, and a maximal independent set $A_n\subseteq V(G_n)$, such that $\alpha(G_n)$ is large (close to $n$) while $|A_n|$ is small. For each $n$, make the ratio $\displaystyle{\frac{|A_n|}{\alpha(G_n)}}$ as small as possible.
12.23 DEF A clique in $G$ is a subset $A\subseteq V$ such that every pair of vertices in $A$ are adjacent. The clique number $q(G)$ is the maximum size of a clique in $G$.
12.24 DO $\chi(G)\ge q(G)$.
12.25 DO Find the smallest graph $G$ such that $\chi(G)\ge 4$ (i.e., $G$ is not 3-colorable), yet $q(G)\le 3$ (i.e., $G\not\supseteq K_4$).
12.26 HW (due Tue Nov 14) Construct the smallest triangle-free graph $G$ (i.e., $q(G)\le 2$) that is not 3-colorable (i.e., $\chi(G)\ge 4$). Instructions: 11 vertices, rotational symmetry of order 5 (i.e., you can draw your graph in the plane such that the 72-degre rotation of the plane will induce automorphisms of $G$). It is sufficient if you provide a nice drawing that displays the 72-degree ($2\pi/5$) rotational symmetry; no proof needed.
12.27 CH Prove: for every $k$ there exists a triangle-free graph of chromatic number $\ge k$.
12.28 DEF A subset $A\subseteq V$ is an independent set in the graph $G=(V,E)$ if there are no edged amon $A$, i.e., $A\cap \binom{V}{2}=\emptyset$. The size of the largest independent set is the independence number of $G$ and is denoted $\alpha(G)$.
12.29 DO $\alpha(G)=q(\Gbar)$.
12.30 HW Prove: For every graph $G$ with $n$ vertices, $\alpha(G)\chi(G) \ge n$.
12.31 HW (due Tue Nov 14) Let Gr$(k,\ell)$ denote the $k\times\ell$ grid. (This graph, defined in class, has $n=k\ell$ vertices and $2k\ell -k-\ell$ edges.) Prove: $\alpha$(Gr$(k,\ell))= \lceil n/2\rceil$. You need 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.
12.32 HW (due Tue, Nov 14) Prove: If a graph $G$ is regular and not empty (i.e., it is regular of degree $\ge 1$) then $\alpha(G) \le n/2$.
12.33 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)$.
12.34 DO Recall that a tree is connected graph with no cycles. Prove: every tree is bipartite.
12.35 DO Prove that a tree with $n$ vertices has $n-1$ edges. Use the following lemma for an inductive proof.
12.36 DO Every tree with $n\ge 2$ vertices has a vertex of degree 1.
HW set #11, due Tuesday, Nov 7, before class. Posted 11-05 at 7:15am.
11.1 DO Review the basic concepts of graph theory from LN.
11.2 REVIEW Graph $G=(V,E)$ where $V$ is the set of "vertices" (singular: "vertex") and $E\subseteq \binom{V}{2}$ is the set of "edges." Unless otherwise stated, we write $n=|V|$ and $m=|E|$.
11.3 DO $0\le m \le \binom{n}{2}$.
11.4 DEF $x,y\in V$ are adjacent if $x\neq y$ and $\{x,y\}\in E$. Notation: $x\sim_G y$ or simply $x\sim y$ if the graph $G$ is understood. Adjacent vertices are also called neighbors.
11.5 DO Adjacency is an irreflexive, symmetric relation.
11.6 REVIEW the concept of isomorphism. If the graphs $G$ and $H$ are isomorphic, we denote this circumstance by $G\cong H$. Latex: $\texttt{G\cong H}$. We write $\iso(G,H)$ to denote the set of isomorphisms $G\to H$. An isomorphism of $G$ to itself is an automorphism and $\aut(G):=\iso(G,G)$ denotes the set (group) of automorphisms of $G$.
11.7 DO Let $G, H$ be graphs. Prove: $$|\iso(G,H)| = \begin{cases} 0 &\text{ if }& G \ncong H \\ |\aut(G)| &\text{ if }& G\cong H\\ \end{cases} $$
11.8 REVIEW the definition of special classes of graphs: $C_n$, the cycle of length $n$ (also called the "$n$-cycle") (here $n\ge 3$); the path $P_n$ of length $n-1$ (this graph has $n$ vertices, hence the subscript) (here $n\ge 1$; the path $P_1$ consists of a single vertex); the complete graph $K_n$. We call $C_3=K_3$ the triangle and $C_5$ the pentagon. Complete graphs are also called cliques and $K_n$ is called the $n$-clique.
11.9 DO Count the automorphisms of the cube graph. (This graph has 8 vertices and 12 edges.)
11.10 HW Count the automorphisms of $P_n$, $C_n$, $K_n$. Give a very brief reasoning of your answer. Don't overlook that the identity permutation is always an automorphism.
11.11 REVIEW the definition of the complement $\Gbar$ of the graph $G$. We call $\Kbar_n$ the empty graph on $n$ vertices.
11.12 DO We call the graph $G$ self-complementary if $G\cong \Gbar$. Prove that the following graphs are self-complementary: $P_1$, $P_4$, $C_5$.
11.13 HW Prove: if $G$ is self-complementary then $n\equiv 0$ or $1 \pmod 4$ .
11.14 DO (a) Observe that $|\iso(G,H)|\le n!$ for all pairs $(G,H)$ of graphs. (b) Find all pairs $(G,H)$ of graphs for which $|\iso(G,H)|= n!$.
11.15 DO Fix a set $V$ of $n$ vertices. Count the graphs on this set of vertices. (Answer: $\displaystyle{2^{\binom{n}{2}}}$. Why?)
11.16 DO Fix a set $V$ of $n$ vertices and an integer $0\le m\le \binom{n}{2}$. Count the graphs with $m$ edges on this set of vertices. (Answer: $\displaystyle{\binom{\binom{n}{2}}{m}}$. Why?)
11.17 DEF The graph $H=(W,F)$ is a subgraph of the graph $G=(V,E)$ if $W\subseteq V$ and $F\subseteq E$.
11.17 DEF A Hamilton cycle of a graph $G$ with $n$ vertices is a $C_n$ subgraph. A graph $G$ is Hamiltonian if it has a Hamilton cycle. A Hamilton path is a subgraph that is a path $P_n$.
11.18 DO (a) Observe that if a graph is Hamiltonian then it has a Hamilton path. (b) Observe that the converse is false.
11.19 DO Find a Hamilton cycle in the dodecahedron graph.
11.20 HW (a) For $1\le k\le n$, count the paths of length $k$ in $K_n$. Remember that a path and the same pat backwards is the same subgraph. (b) For $3\le k\le n$, count the $k$-cycles in $K_n$. For each question, your answer should be a simple closed-form expression (see def in Midterm) involving factorials and binomial coefficients. Give a brief reasoning supporting your answer.
11.21 DEF. Let $L\in\rrr\cup\{\pm\infty\}$. Let $f,g$ be two functiosn mapping a subset of $\rrr$ to $\rrr$. We say that $f=O(g)$ (big-Oh notation) as $x\to L$ if $(\exists C)($for all $x$ that is sufficiently close to $L)(|f(x)|\le C|g(x)|)$. Under the same condition we say that $g=\Omega(f)$ (big-Omega notation). In other words, $g=\Omega(f)$ if $(\exists c>0)($for all $x$ that is sufficiently close to $L)(|g(x)|\ge c|f(x)|)$. Finally $g=\Theta(f)$ (big-Theta notation) if $f=O(g)$ and $f=\Omega(g)$ hold simultaneously. In other words, $g=\Theta(f)$ if there exist positive constants $C, c$ such that for all $x$ that is sufficiently close to $L$ we have $c|f(x)|\le |g(x)|\le C|f(x)|$. In this case we say $f$ and $g$ have "the same rate of growth" as $x\to L$.
11.22 DO Prove: if $f$ is a polynomial of degree $n$ then $f=\Theta(x^n)$ as $x\to\infty$.
11.23 DO Prove: if $f\sim g$ as $x\to L$ then $f=\Theta(g)$ as $x\to L$.
11.24 DO Prove: if the limit $\lim_{x\to L} f(x)/g(x)$ exists and is neither zero nor $\pm\infty$ then $g=\Theta(f)$.
11.25 HW Find functions $f,g : \rrr\to\rrr$ such that $\lim_{x\to\infty}f(x)=\lim_{x\to\infty}g(x)=\infty$ and $g=\Theta(f)$ as $x\to\infty$ but $\lim_{x\to\infty}f(x)/g(x)$ does not exist.
11.26 DO Fix $L\in\rrr\cup\{\pm\infty\}$. Prove: the $\Theta$ relation (as $x\to L$) is an equivalence relation on functions defined in a neighborhood of $L$.
11.27 HW Find an infinite sequence of graphs, $G_n$, such that (i) $G_n$ has $n$ vertices; (ii) $G_n$ has a Hamilton path; (iii) $G_n$ has no Hamilton cycle; and (iv) the number of edges of $G_n$ is $m_n=\Omega(n^2)$.
11.28 DEF The degree of a vertex $x$ in a graph $G$ is the number of neighbors of $x$. We denote the degree of $x$ be $\deg_G(x)$, or simply $\deg(x)$ if the reference graph $G$ is clear.
11.29 DO (Handshake Theorem) (a) Prove: $\displaystyle{\sum_{x\in V}\deg(x) = 2m}$. (b) Why is this called the "Handshake Theorem"?
11.30 DO In every graph, the number of vertices of odd degree is even.
11.31 DEF $G$ is $r$-regular if every vertex has degree $r$. $G$ is regular if every vertex has the same degree.
11.32 HW Prove: if a graph is regular and self-complementary then $n\equiv 1\pmod 4$.
11.33 REVIEW for LN: DEF of an $x\to\dots\to y$ walk of length $k$ in a graph.
11.34 DEF We say that vertex $y$ is accessible from vertex $x$ if there exists an $x\to\dots\to y$ walk.
11.35 DO Prove: accessiblity is an equivalence relation among the vertices of a graph. (Note: to prove reflexivity, you need to take walks of length zero.)
11.36 DO Prove: If there exists an $x\to\dots\to y$ walk then there exists an $x\to\dots\to y$ path. Hint: any shortest walk is a path.
11.37 DEF The equivalence classes of the accessibility relation are called the connected components of $G$. So two vertices belong to the same connected component if they are accessible from one another.
11.38 DEF A graph is connected if it has just one connected component, i.e., if every vertex is accessible from every vertex.
11.39 DEF A tree is a connected graph with no cycles.
11.40 HW Draw all 7-vertex trees up to isomorphism. State how many trees you found. You lose credit for each mistake. There are two kinds of mistakes to avoid: (a) listing two trees that are isomorphic (b) missing a tree (that is, if there is a tree on seven vertices that is not isomorphic to any of your drawings). Do your drawings systematically -- this will help avoid mistakes and also makes grading easier.
11.41 REVIEW DEF of bipartite graphs.
11.42 HW Determine, for what values of $n\ge 3$ is the $n$-cycle bipartite.
11.43 DO Learn the moves of the chess pieces.
11.44 DO Prove that the graph of the knight's moves is bipartite. (The vertices are the cells of the chessboard, the edges correspond to the knight's moves.)
11.45 DO Prove: (a) the graph of the pawn's moves is not bipartite. (b) But it becomes bipartite if we prohibit the initial double advance. (A pawns moves include it forward moves and its diagonal capture moves.)
11.46 DO Prove: for every graph $G$, either $G$ or $\Gbar$ is connnected.
11.47 DO Prove: If both $G$ and $\Gbar$ are bipartite then $n\le 4$.
11.48 CH Find the maximum number of edges of a graph on $n$ vertices without a Hamilton cycle.
11.49 CH Prove: if every vertex of a graph has degree greater than $n/2$ then $G$ is Hamiltonian.
11.50 DO Fix positive integers $k\le\ell\le n$. Let $\Omega$ be a set of $n$ elements. Let $A$ be a random $k$-subset and $B$ a random $\ell$-subset of $\Omega$, selected independently. (a) What is the size of the sample space for this experiment? (b) Determine $E(|A\cap B|)$.
11.51 CH Find a graph $T$ with $n$ vertices and $n-1$ edges such that any two subgraphs of $K_n$ isomorphic to $T$ share an edge.
11.52 CH Prove: all longest paths in a tree share a vertex. (Warning: proving that every pair of longest paths shares a vertex is not sufficient.)
HW set #10, due Tuesday, Oct 31, before class. -- First batch (10.1--10.28) posted 10-26 at 4:25pm. Full set posted 10-27 at 1:30pm.
10.1 HW
Let $f,g: \rrr^+ \to \rrr$ be real functions whose domain is $\rrr^+$,
the set of positive real numbers. Assume $(\forall x)(f(x)>1$ and
$g(x)>1)$. Examine the following statement.
(*)
If $f\sim g$ then $\ln f\sim \ln g$
as $x\to\infty$.
(a) Prove that (*) is false.
(b) Prove that (*) is true if we assume additionally
that $f$ and $g$ are bounded away from $1$, i.e.,
$(\exists c >0)(\forall x)(f(x)\ge 1+c$ and $g(x)\ge 1+c)$.
(For instance, $f(x) \ge 1.001$ and $g(x)\ge 1.001$.)
10.2 HW Let $B(n)$ denote the number of equivalence
relations on a set of $n$ elements. Prove:
(a) $B(n) \le n^n$
(b) $(\forall k)($
if $1\le k\le n$ then $B(n) \ge k^{n-k})$
(c) $\ln B(n) \sim n \ln n$.
10.3 DEF The list $(x_1,\dots,x_n)\in\rrr^n$ of $n$ real numbers is a probability distribution if $(\forall i)(x_i\ge 0)$ and $\sum_{i=1}^n x_i =1$.
Warning. The next definition as given in class was inaccurate. Take the following definition instead.
10.4 DEF Let $X:\Omega\to\rrr$ be a random variable
with range $M=\{y_1,\dots,y_m\}$. (The $y_i$ are distinct,
so $|M|=m$.
The distribution of the random variable $X$
is the function $p : M\to \rrr$ defined by $p(y)=P(X=y)$
for $y\in T$. If the list $(y_1,\dots,y_m)$ is known (in order),
it suffices to state the list $(p(y_1),\dots,p(y_m))$
because with reference to the list $(y_1,\dots,y_m)$,
$(p(y_1),\dots,p(y_m))$ determines the function $p$.
Note that the list $(p(y_1),\dots,p(y_m))$ is a probability
distribution in the sense of DEF 10.3.
We say that $X$ is uniformly distributed over the set $M$
if $(\forall y\in M)(p(y)=1/m)$.
We say that two random variables over possibly different
probability spaces are identically distributed (i.d.)
if their range $M$ is the same and their distribution
functions are the same. If in addition they are also
independent, we talk about i.i.d. random variables
(independent, identically distributed r.v.'s.)
10.5 HW Construct a non-uniform probability space $(\Omega,P)$ and a random variable $X$ on this space such that $X$ is uniformly distributed over a set of 4 values. Make $|\Omega|$ as small as possible.
10.6 DEF "Bernoulli trial" is another name for a $(0,1)$-valued random variable; the outcome "1" is called "success," the outcome "0" is "failure." If the probability of success is $p$ then the distribution of this variable is $(p,1-p)$ (with reference to the list $(1,0)$ of values).
10.7 DEF Let $X$ denote the number of successes among $n$ i.i.d. Bernoulli trials, each with probability $p$ of success. The range of this r.v. is the set $\{0,1,\dots,n\}$, and the distibution is $p(k)=\binom{n}{k}p^k(1-p)^{n-k}$. This is called the binomial distribution.
10.8 DO Verify that the probabilities in the binomial distribution indeed add up to 1, i.e., $\sum_{k=0}^n p(k) = 1.$ (Hint: Binomial Theorem.)
10.9 DO Prove: $\displaystyle{\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}}$.
10.10 DO Use the preding exercise to prove that the expected number of "heads" among $n$ coin flips is $n/2$.
10.11 DO THEOREM (linearity of expectation) Let $X_1,\dots,X_k$ be random variables over the same probability space and let $c_1,\dots,c_k\in \rrr$. Let $Y=\sum_{i=1}^k c_i X_i$. (We say the that the random variable $Y$ is a linear combination of the $X_i$.) Then $E(Y) = \sum_{i=1}^k c_iE(X_i)$. REMARK. There is no assumption on the variables. Most importantly, they do not need to be independent.
10.12 DO Let $X_1,\dots,X_n$ be Bernoulli trials with
repsective probability of success $p_i$, i.e., $P(X_i=1)=p_i$
and $P(X_i=0)=1-p_i$. Let $Y$ be the number of successes
in the sequence $X_1,\dots, X_n$. Then $E(Y)=\sum_{i=1}^n p_i$.
Proof. Note that $Y=\sum_{i=1}^n X_i$. Now apply the linearity
of expectation.
10.13 REMARK Taking $p_1=\dots=p_m=p$ in the preceding exercise we obtain that the expected number of successes is $pn$. For $p=1/2$ this gives the expectation of $n/2$, giving a more insightful alternative solution to problem 10.10.
10.14 REMARK. Note that in problem 10.12, we did not assume independence of our Bernoulli trials.
10.14 DO (Hat-check problem, easy question)
$n$ patrons of an event check their hats. On leaving,
a randomly chosen hat is handed to each owner.
What is the expected number of happy patrons?
(A patron is happy is he gets back his own hat.)
A alternativ ewording of this problem is, what is
the expecte dnumber of fixed points
of a random permutation of a set of $n$ elements.
Solution. The sample space for this experiment
is the set of all permutations of the $n$ hats, so
$|\Omega|=n!$. The permutation is picked "at random"
without a stated probability distribution, so
according to our convention, so the distribution is
assumed to be uniform. Let $A_i$ be the event that
the $i$-th patron is happy, and let $X_i$ be the
indicator variable of the event $A_i$. We note
that $P(A_i)=1/n$ for reasons of symmetry (the $i$ hat
could go to any of the $n$ patrons with equal
probability). Let $Y$ be the number of happy patrons.
Then $Y=\sum_{i=1}^n X_i$. Now applying the
linearity of expectation to this equation we get
$E(Y)=\sum_{i=1}^n E(X_i)=\sum_{i=1}^n P(A_i)=
\sum_{i=1}^n (1/n) = 1.$
10.15 REMARK The "hard question" about this model is to determine the probability that no patron is happy (the "derangement problem"). We shall discuss that problem later.
10.16 HW Let $f :[k]\to [n]$ be a function. We say that $x,y\in [k]$ collide if $x\neq y$ and $f(x)=f(y)$. Let $\colll(f)$ denote the number of collisions, i.e., the number of pairs $\{x,y\}$ that collide. So $0\le \colll(f)\le \binom{k}{2}$. Pick $f$ at random (from among the $n^k$ functions $[k]\to [n]$). Determine $E(\colll(f))$. (As always, prove your answer.) More than half the credit will go for an accurate definition of the random variables you define along the way.
10.17 THEOREM. Let $X_1,\dots,X_n$ be independent random variables. Then $E\left(\prod_{i=1}^n X_i\right)=\prod_{i=1}^n E(X_i)$.
10.18 DO Prove this for $n=2$.
10.19 DO Prove: If $X,Y,Z$ are independent random variables then $X,Y+Z$ are independent; and also $X, YZ$ are independent. Indeed, $X, f(Y,Z)$ are independent for any function $f$.
10.20 DO Prove Theorem 10.17 for $n=3$ using the two preceding exercises. Generalize the proof to an inductive proof for all $n$.
10.21 HW We roll $n$ dice. Let $X$ be the product of the numbers that come up. Determine $E(X)$.
10.22 DEF The variance of the random variable $X$ is the quantity $\var(X)=E\left((X-E(X))^2\right)$.
10.23 DO $\var(X)\ge 0$. Moreover, $\var(X)=0$ if and only if $X$ is almost constant, i.e., $(\exists c\in \rrr)(P(X=c)=1)$.
10.24 THEOREM $\var(X)=E(X^2)-(E(X))^2.$
(Proved in class, review the proof.)
10.25 COROLLARY (Cauchy–Schwarz inequality) $E(X^2)\ge (E(X))^2$.
10.26 DO Compare this with the following more familiar form
of Cauchy–Schwarz.
Let $x_1,\dots,x_n,y_1,\dots,y_n\in \rrr$. Then
$$ \left(\sum_{i=1}^n x_iy_i\right)^2 \le
\left(\sum_{i=1}^n x_i^2\right)\left(\sum_{i=1}^n y_i^2\right)$$
Prove this from the preceding exercise and vice versa.
10.27 DO Let $X$ be a Bernoulli trial with probability $p$ of success. Then $E(X)=p$ and $\var(X)=p(1-p)$.
10.28 HW We roll a die; let $X$ be the number that comes up (so $1\le X\le 6$). Determine (a) $E(X)$ (b) $\var(X)$. Show your work, don't just state the result.
10.29 HW (a) 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 more than half the credit. – Clarify the role of the vodka. Hint. Review indicator variables (LN 7.2.6, 7.2.7). Represent the number of lucky members as a sum of indicator variables. (b) What is the size of the sample space for this experiment?
10.30 DO Let $x_1,\dots,x_n\in\rrr$. Prove: $$\left(\sum_{i=1}^n x_i\right)^2 =\sum_{i=1}^n\sum_{j=0}^n x_ix_j = \left(\sum_{i=1}^n x_i^2\right) + \left(\sum_{i\neq j} x_ix_j\right)$$
10.31 DEF The covariance of the random variables $X,Y$ is the quantity $\cov(X,Y)=E(XY)-E(X)E(Y)$.
10.32 DO Observe that the random variables $X,Y$ are positively correlated if $\cov(X,Y) > 0$, negatively correlated if $\cov(X,Y) < 0$, and uncorrelated if $\cov(X,Y) = 0$. (Compare with DEF 9.33.) –
10.33 DO : If $X,Y$ are independent random variables then $\cov(X,Y)=0$. (This says independent variables are uncorrelated. The converse is false, see Exercise 9.34.)
10.34 DO Observe: $\var(X)=\cov(X,X)$.
10.35 DO (Variance of sum) Let $X_1,\dots,X_n$ be random variables (over the same probability space). Let $Y=X_1+\dots+X_n$. Prove: $$ \var(Y) = \sum_{i=1}^n\sum_{j=1}^n \cov(X_i,X_j) = \left(\sum_{i=1}^n \var(X_i)\right) + \left(\sum_{i\neq j}\cov(X_i,X_j)\right)$$ Hint. Notice the analogy with Exercise 10.30.
10.36 DO: COROLLARY (Variance of sum of pairwise independent random variables). If $X_1,\dots,X_n$ are pairwise independent random variables (over the same probability space) then $$\var(X_1+\dots+X_n) = \var(X_1)+\dots+\var(X_n).$$
10.37 DO Let $X$ be the number of successes in $n$ pairwise independent Bernoulli trials. Prove: $E(X) = np$ and $\var(X)=np(1-p)$.
10.38 HW Let us roll $n+1$ dice; the numbers that come up are $X_0,X_1,\dots,X_n$ (so $1\le X_i\le 6$). For $i=1,\dots, n$ let $Y_i=X_{i-1}X_i$. Let $Z=\sum_{i=1}^n Y_i$. Compute (a) $E(Y_i)$ (b) $\var(Y_i)$ (c) $\cov(Y_i,Y_j)$ for all $i,j = 1,\dots,n$ (d) $\var(Z)$.
10.39 DO (updated 11-02 at 1:20am because of error in original posting).
Let $X_1,\dots, X_n$ be random variables. Prove:
(a)
$\sum_{i=1}^n \var(X_i) \ge \sum_{i\neq j} -\cov(X_i,X_j)$.
(b)
$(n-1)\sum_{i=1}^n \var(X_i) \ge \sum_{i\neq j} \cov(X_i,X_j)$.
10.40 CH Hint to CH 8.30 (strongly negatively correlated events): "the variance is non-negative."
HW set #9 HW problems due Thursday, Oct 26, before class. DO exercises due Wednesday, Oct 25, before the problem session. -- First batch (9.1--9.8) posted 10-24 at 5:36pm. The rest posted 10-25 at 6:05am.
9.1 DO (Multinomial Theorem) Prove the following identity. $$ (x_1+\dots +x_r)^n = \sum_{k_i\ge 0, \sum k_i=n} \binom{n}{k_1,\dots,k_r} x_1^{k_1}\dots x_r^{k_r} .$$
9.2 DO (Stars and bars) Count the terms in the Multinomial Theorem. This is the number of solutions to the equation $k_1+\dots+k_r=n$ in integers $k_i\ge 0$. Bijective argument: put the solutions into 1–1 correspondence with the strings of length $n+r-1$ over the 2-letter alphabet $\{\ast, \mid\ \}$ consisting of $n$ stars and $r-1$ bars. It will follow that the answer is $\displaystyle{\binom{n+r-1}{n} = \binom{n+r-1}{r-1}}.$
9.3 HW Count the solutions of the equation $x_1+\dots+x_r=n$ in integers $x_i\ge 2$. Your answer should be a very simple binomial coefficient. Prove your answer. Hint. Reduce the question to the preceding exercise.
9.4 NOTATION For a set $S$ we write $\displaystyle{\binom{S}{k}}$ to denote the set of all $k$-subsets of $S$.
9.5 DO Prove: $\displaystyle{\left|\binom{S}{k}\right| = \binom{|S|}{k}} .$
9.6 DO (Pascal's indentity) Give (a) a combinatorial proof and (b) an algebra proof of the identity $$ \binom{n+1}{k+1} = \binom{n}{k}+\binom{n}{k+1} .$$ The combinatrial proof should use only the definition of the binomial coefficients. Use Notation 9.4 to express your argument. For the algebra proof, use the identity $(1+x)^{n+1} = (1+x)^n (1+x)$. Compare the coefficient on $x^{n+1}$ on each side.
9.7 DO Give (a) a combinatorial proof and (b) an algebra proof of the identity $$ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} .$$ For the combinatorial proof, let $S$ be a $(2n)$-set of $n$ red points and $n$ blue points; count the $n$-subsets of $S$ in two ways and compare. Use Notation 9.4 to express your argument. For the algebra proof, use the identity $(1+x)^{2n}=(1+x)^n(1+x)^n$. Compare the coefficient of $x^n$ on each side.
9.8 HW Prove the identity $\displaystyle{\sum_{j=k}^n \binom{j}{k} = \binom{n+1}{k+1}} .$
9.9 CONVENTION If $S$ is a non-empty finite set and we say "pick an element of $S$ at random," we mean the uniform choice (each element has probability $1/|S|$ to be chosen) unless a different distribution is specified.
9.10 ASYMPTOTIC NOTATION. Let $L\in \rrr\cup {\pm\infty}$.
Let $f,g$ be functions from a subset of $\rrr$ to $\rrr$.
(a) We say that $f(x) = o(g(x))$ as $x\to L$
if $\displaystyle{\lim_{x\to L}\frac{f(x)}{g(x)}=0}.$
We read this expression as "$f$ is little-oh of $g$
as $x$ approaches $L$."
(b) We say that $g(x) = \omega(f(x))$ as $x\to L$
if $f(x)=o(g(x))$, or, in other words, if
$\displaystyle{\lim_{x\to L}\frac{f(x)}{g(x)}=0}.$
If $f(x)\neq 0$ when $x$ is sufficiently close to $L$ then
this is also equivalent to saying that
$\displaystyle{\lim_{x\to L}\left|\frac{g(x)}{f(x)}\right|=\infty}.$
In both cases we can suppress the name of the variable
and just write $f=o(g)$ and $g=\omega(f)$.
9.11 DO Prove: for fixed $L$, the little-oh relation is transitive.
9.12 DO Fix $L$. Prove: if $f = o(g)$ and $g\sim h$ then $f=o(g)$.
9.13 DO Fix $L$. Let $C>0$ be a constant. Prove: if $f=o(g)$ then $f^C=o(g^C)$ (as $x\to L$).
9.14 DO Fix $L$. Prove: if $f=o(h)$ and $g=o(h)$ then $f+g=o(h)$.
9.15 DO Fix $L$. (a) Prove that the following statement is false. "If $f=o(g)$ and $f=o(h)$ then $f=o(g+h)$." Find counterexamples such that $(\forall x)(g(x)+h(x) \neq 0)$. (b) Prove that the statement becomes true if $g(x), h(x)>0$ for all $x$ that is sufficiently close to $L$.
9.16 HW Prove: $\ln x = o(x)$ as $x\to\infty$.
9.17 DO Prove: $\ln x = o(\sqrt{x})$ as $x\to\infty$. Do not use calculus, just use the preceding exercise. (This is called "bootstrapping": turning a result into a stronger result with little effort.)
9.18 DO Fix $L$. Let $f,g$ be functions from a subset of $\rrr$ to $\rrr$. Prove: $f\sim g$ if and only if $f-g = o(f)$.
9.19 HW Find two functions $f,g: \rrr\to\rrr$ such that (1) $\lim_{x\to\infty} f(x)= \lim_{x\to\infty} g(x)= \infty$, (2) $f = o(g)$ as $x\to\infty$ (3) $\ln f \sim \ln g$ as $x\to\infty$.
9.20 DEF We say that a function $f:A\to B$ has a collision if $(\exists x,y\in A)(x\neq y$ but $f(x)=f(y)$.
9.21 DO Let $B(n,k)$ denote the probability that a random function $f: [k]\to [n]$ has no collisions. (In accordance with the convention stated, this means we pick $f$ from the uniform distribution over the $n^k$ functions that consitute the sample space for this experiment.) Prove: $$B(n,k) = \frac{n(n-1)\cdots (n-k+1)}{n^k} = \prod_{i=0}^{k-1} \left(1-\frac{i}{n}\right) .$$
9.22 THEOREM (Birthday paradox) Let $k_n\to \infty$
be a sequence of positive integers, $0\le k_n\le n$.
(a) If $k_n=o(\sqrt{n})$ then $B(n,k_n)\to 1.$ (Collision
is unlikely.)
(b) If $k_n=\omega(\sqrt{n})$ then $B(n,k_n)\to 0.$
(Collision is likely.)
9.23 DO Let $0\le a_i\le 1$ be real numbers $(i=1,\dots,m)$. Prove: $\prod_{i=1}^m (1-a_i)\ge 1-\sum_{i=1}^m a_i.$ (Induction on $m$.) This inequality is used in the proof of part (a) of the Birthday paradox.)
9.24 DO Prove: $\sum_{i=1}^{k-1} i = \binom{k}{2}$.
9.25 DO Prove: (a) If $k_n=o(\sqrt{n})$ then $\binom{k_n}{2} = o(n)$ (as $n\to\infty$). (b) If $k_n=\omega(\sqrt{n})$ then $\binom{k_n}{2} =\omega(n)$ (as $n\to\infty$).
9.26 DO Prove: $(\forall x\in\rrr)(\eee^{x} \ge 1+x)$. (This inequality is used in the proof of part (b) of the Birthday paradox.)
9.27 FACT (the actual Birthday Paradox) $B(365, 23) < 1/2$. So among 23 people, it is more likely than not that two of them have the same birthday. (A more accurate figure is $B(365,23)\approx 0.4927$.)
9.28 Study independence of random variable from LN.
9.30 DEF The random variables $X_1,\dots,X_k$ (over the same probability space) are independent if $$(\forall x_1,\dots,x_k\in\rrr)(P((\forall i)(X_i=x_i))= \prod_{i=1}^k P(X_i=x_i)$$
9.31 HW Prove: If $X,Y,Z$ are independent random variables (over the same probability space) then $X,Y$ are also independent.
9.31 THEOREM If $X_1,\dots,X_k$ are independent random variables (over the same probability space) then $$ E\left(\prod_{i=1}^k X_i\right) = \prod_{i=1}^k E(X_i) .$$
9.32 DO Prove the Theorem for $k=2$, i.e., prove: if $X,Y$ are independent then $E(XY)=E(X)E(Y)$.
9.33 DEF The random variables $X,Y$ are positively correlated if $E(XY) > E(X)E(Y)$; negatively correlated if $E(XY) < E(X)E(Y)$; and uncorrelated if $E(XY)= E(X)E(Y)$. -- Note that the preceding ezxercise says that if two random variables are independent then they are uncorrelated. The next exercise say the converse is false.
9.34 HW Construct a probability space and two random variables that are uncorrelated yet not independent. Make your sample space as small as possible. -- You don't need to prove that it is smallest possible.
9.35 DO Prove: the events $A_1,\dots,A_k$ are independent if and only if their indicator variables $\vt_{A_1},\dots,\vt_{A_k}$ are independent.
9.36 DO Prove: two events are positively correlated if and only if their indicator variables are positively correlated. Same about negative correlation.
HW set #8 problems due Tuesday, Oct 24, before class.
-- First batch (8.1--8.18) posted 10-21 at 4:20pm.
Complete set posted 10-22 at 2:25am.
-- NOTE. There were multiple typos in the statement of the
Binomial Theorem (7.19); they are fixed now.
"LN" refers to the instructor's
online DM lecture notes.
8.1 STUDY the proof of Fermat's little Theorem given in class. The next two exercises contain the main ingredients of the proof.
8.2 DO Let $m\ge 1$. Prove: $m$ integers form a complete set of residues modulo $m$ if and only if they are pairwise not congruent modulo $m$.
8.3 DO Let $m\ge 1$. Prove: if $a_1,\dots,a_m$ is a complete set of residues modulo $m$ and $\gcd(c,m)=1$ then $ca_1,\dots,ca_m$ also form a complete set of residues modulo $m$.
8.4 DO Let $p$ be a prime. (a) Prove: if $\gcd(a,p)=1$ then $a^{p^2-p}\equiv 1 \pmod{p^2}$. (b) Generalize this to a similar result modulo $p^k$.
8.5 HW Calculate the probability that a poker hand is "two pairs." Give your answer (a) as a simple expression involving binomial coefficients (b) as a decimal to 3 significants digits of accuracy. Show all your work, including the details of how you arrived at your answer in decimals. You may use a calculator for arithmetic but not for higher functions such as binomial coefficients. (We assume the uniform distribution over the $\binom{52}{5}$ poker hands.)
8.6 HW Out of $n$ candidates, a society elects a president, three vice presidents (of equal roles) and a treasurer. (a) Count the possible outcomes. Give your answer in the form $a\cdot\binom{n}{b}$ for some constants $a,b$. Find $a$ and $b$. (b) Asymptotically evaluate your answer in the form $c\cdot n^d$ for some constants $c,d$. State the values of $c$ and $d$.
8.7 HW For $n\ge k\ge 0$, let $p(n,k)$ be the probability that a random word of length $k$ over an $n$-letter alphabet has no repeated letters. (We assume the uniform distribution over the $n^k$ possible words.) (a) Give a simple formula for $p(n,k)$. (b) Show that for every fixed value of $k$ we have $\lim_{n\to\infty} p(n,k)=1$.
8.8 HW Let $p$ be a prime. Prove: for $1\le k\le p-1$ the number $p$ divides the binomial coefficient $\binom{p}{k}$. Use the prime property; do not use the Fundamental Theorem of Arithmetic.
8.9 HW Use the preceding exercise to prove $(a+b)^p \equiv a^p + b^p \pmod p$. ($p$ is a prime.)
8.10 HW Use the preceding exercise to prove Fermat's little Theorem in the form that for all primes $p$, $(\forall a)(a^p\equiv a \pmod p)$. For $a\ge 0$ proceed by induction on $a$. Then settle the case of negative $a$ by a simple argument.
8.11 DO (Modular identity) Let $(\Omega,P)$ be a finite probability space and $A,B\subseteq \Omega$ events. Prove: $$ P(A\cup B) + P(A\cap B) = P(A) + P(B) .$$
8.12 DO (Union bound) Let $(\Omega,P)$ be a finite probability space and $A_1,\dots,A_m \subseteq \Omega$ events. Prove: $$ P\left(\bigcup_{i=1}^m A_i\right) \le \sum_{i=1}^m P(A_i) .$$
8.13 DO (continued) If the $A_i$ are pairwise disjoint then $ P(\bigcup_{i=1}^m A_i) = \sum_{i=1}^m P(A_i) .$
8.14 DO (continued) For the equality $ P(\bigcup_{i=1}^m A_i) = \sum_{i=1}^m P(A_i) $ to hold, it is necessary and sufficient that $(\forall i\neq j)(P(A_i\cap A_j)=0)$.
8.15 DO Study independence of events and conditional probability from LN, Ch. 7.
8.16 DO Prove: if $P(B) > 0$ then the events $A$ and $B$ are independent if and only if $P(A) = P(A\mid B)$.
8.17 DO Prove the "Theorem of Complete Probability" (LN, Exercise 7.1.9).
8.18 HW ("probability of causes") 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.19 HW Prove: If $A_1,\dots,A_m$ are independent events then $A_1,\dots,A_{m-1},\Abar_m$ are independent (where $\Abar = \Omega\setminus A$ is the complement of $A$).
8.20 COROLLARY (DO) Notation: for event $A$ we write $A^1=A$ and $A^{-1}=\Abar$. Prove: if $A_1,\dots,A_m$ are independent events then $A_1^{\epsilon_1},\dots,A_{m}^{\epsilon_m}$ are independent for any choice of $\epsilon_i\in\{\pm 1\}$. In other words, we can complement any subfamily of the $A_i$ and they remain independent.
8.21 DO We call an event $A$ "trivial" is $P(A)=0$ or $P(A)=1$. Prove: if $A_1,\dots,A_m$ are independent events and $B$ is a trivial event then $A_1,\dots,A_m, B$ are independent.
8.22 HW If there exist $m$ nontrivial independent events in the probability space $(\Omega,P)$ then $|\Omega|\ge 2^m$.
8.23 CH Show that pairwise independence can be realized on a much smaller sample space. Specifically, for every $m\ge 1$, construct $m$ pairwise independent events, each of probability $1/2$, on a sample space of size $O(m)$. The big-Oh notation means there is a constant $c$ such that the sample space has size $\le cm$ for all $m$. Specify the value of your constant $c$.
8.24 CH Prove that the linear upper bound in the preceding exercise is tight, apart from the value of the constant. Specifically, prove that if there exist $m$ pairwise independent nontrivial events in $(\Omega,P)$ then $|\Omega|\ge m+1$. (Here $P$ is an arbitrary distribution, not necessarily uniform.)
8.25 HW Construct a probability space $(\Omega,P)$ and three events in $(\Omega,P)$ that are pairwise but not fully independent. ("Fully independent" means the same thing as "independent"; the word "fully" is only added for emphasis.) Make your sample space as small as possible.
8.26 DO Let $A,B,C$ be events. True or false: If $A$ and $B$ are independent, and $A$ and $C$ are independent, then $A$ and $B\cap C$ are independent. (If true, prove; if false, give a smallest possible counterexample.)
8.27 DEF We say that the events $A,B$ are positively correlated if $P(A\cap B) > P(A)P(B)$. They are negatively correlated if $P(A\cap B) < P(A)P(B)$.
8.28 DO Prove: (a) Events $A$ and $B$ are positively correlated if and only if $P(A\mid B) > P(A)$. (b) They are negatively correlated if and only if $P(A\mid B) < P(A)$. In particular, you need to show that in these cases $P(B) > 0$.
8.29 HW Consider the uniform probability space with sample space $[n]=\{1,\dots,n\}$. Pick $x\in [n]$ at random. Let $A$ be the event that $2\mid x$ and $B$ the event that $3\mid x$. (So $A=[n]\cap 2\zzz$ and $B=[n]\cap 3\zzz$.) Decide whether the events $A$ and $B$ positively correlated, negatively correlated, or independent. (Your answer will be a function of $n$.)
8.30 CH (Strongly negatively correlated events) Let $A_1,\dots, A_m$ be events such that $P(A_i)=1/2$ for all $i$ and $P(A_i\cap A_j)\le 1/5$ for all $i\neq j$. Prove: $m\le 6$. (This is a generalization of CH 1.26.)
8.31 DO (Independence of Boolean functions of disjoint sets of independent events) (a) Prove: If $A,B,C$ are independent events, then $A,B\cup C$ are also independent. (b) Infer from this that $A,B\cap C$ are independent. (Use complementation (8.20) and DeMorgan's laws.) (c) LN, Exercise 7.1.18.
8.32 DO Review the definition of expected value from the previous class. Let $X$ be a random variable. Prove: $$E(X) = \sum_{y\in \rrr} y\cdot P(X=y) .$$ COMMENTS. (1) In our treatment of the topic, this is a theorem, not the definition. It is easier to prove basic properties such as linearity of expectation based on the original definition. (2) The event "$X=y$" means the set $\{a\in\Omega\mid X(a)=y\}$. (3) The sum over all real values of $y$ is in fact a finite sum; if $y$ is outside the range of $X$ then $P(X=y)=0$.
8.33 DO Use the preceding exercise to prove that $E(\vt_A)=P(A)$. Here $A$ is an event and $\vt_A$ is the indicator variable of $A$.
HW set #7 problems due Thursday, Oct 17, before class. -- First batch (7.1--7.12) posted 10-18 at 3pm, the rest at 4:20pm.
7.1 STUDY Asymptotic notation from the instructor's online lecture notes (Ch. 2). Review the definition and properties of asymptotic equality.
7.2 DO Understand Striling's formula.
7.3 HW Prove: $$ \binom{2n}{n} \sim an^bc^n $$ for some constants $a,b,c$. Determine $a,b,c$. Prove you answer. Hint: $\displaystyle{\binom{2n}{n}=\frac{(2n)!}{(n!)^2}}$.
7.4 DEF For $n,k\ge 0$ we define $\binom{n}{k}$ as the number of $k$-subsets of an $n$-set. For $k > n$ this definition says that $\binom{n}{k}=0$.
7.5 DO For $0\le k\le n$ we have $\binom{n}{k}=\binom{n}{n-k}$. Give a bijective proof. (Done in class; review.)
7.6 DO $\binom{n}{0}=\binom{n}{n}=1$, $\binom{n}{1}=\binom{n}{n-1}=n$.
7.7 DO Give a direct proof of the statement that $$\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots(n-k+1)}{k!}$$
7.8 DO Let $\Sigma=\{A_1,\dots,A_r\}$ be a finite alphabet. The number of strings (words) of length $n$ over $\Sigma$ is $r^n$.
7.9 DO Multinomial coefficients As before, let $\Sigma=\{A_1,\dots,A_r\}$ be a finite alphabet. Let $k_1,\dots,k_r\ge 0$ and $\sum k_i=n$. Let $$\binom{n}{k_1,\dots,k_r}$$ denote the number of those strings of length $n$ over $\Sigma$ that contain $k_i$ occurrences of the letter $A_i$ for every $i$. These numbers are called the multinomial coefficients.
7.10 THEOREM $$ \binom{n}{k_1,\dots,k_r}= \frac{n!}{\prod_{i=1}^r k_i!}$$ Proof (done in class) by counting equivalence classes on a set of $n!$ strings; each equivalence class contains $\prod_{i=1}^r k_i!$ strings. ("King Matthias' shepherd's method.")
7.11 DO Prove: $\displaystyle{\binom{n}{k}=\binom{n}{k,n-k}}$. (On the left-hand side we use our notation for binomial coefficients, on the right-hand side, the notation for multinomial coefficients with $r=2$.) Bijective proof via indicator functions.
7.12 HW Prove: If $1\le k\le n$ then $\displaystyle{\binom{n}{k}\ge \left(\frac{n}{k}\right)^k}$. Give a simple direct proof. Do not try to use Stirling's formula - an asymptotic formula cannot give you a result for all $n$ and $k$, only for "sufficiently large values."
7.13 HW Prove (for all $n\ge 0$) $\displaystyle{n!\ge \left(\frac{n}{\eee}\right)^n}$. Again, don't try to use Stirling's formula. Hint: $\displaystyle{\eee^x =\sum_{i=0}^{\infty}\frac{x^i}{i!}}$.
7.14 DO Prove: If $1\le k\le n$ then $\displaystyle{\binom{n}{k}\le \left(\frac{\eee n}{k}\right)^k}$.
7.15 CH Prove: If $1\le k\le n$ then $\displaystyle{\sum_{j=0}^k\binom{n}{j}\le \left(\frac{\eee n}{k}\right)^k}$.
7.16 DO Recall; the number of subsets of an $n$-set is $2^n$. (Bijective proof via indicator functions.)
7.17 DO $\displaystyle{\sum_{k=0}^n\binom{n}{k} = 2^n}$
7.18 HW Let $E_n$ denote the number of even subsets of an $n$-set and $O_n$ the number of odd subsets. So $\displaystyle{E_n=\sum_{k=0}^{\infty}\binom{n}{2k}}$ and $\displaystyle{O_n=\sum_{k=0}^{\infty}\binom{n}{2k+1}}$.
Give a simple bijective proof of the identity $E_n=O_n$ for $n\ge 1$. Indicate where your proof uses the assumption that $n\neq 0$. (The statement is false for $n=0$.)
7.19 DO Binomial Theorem $$(x+y)^n = \sum_{j=0}^n \binom{n}{j} x^j y^{n-j}$$ Review the proof from class.
7.20 DO Give an "algebra proof" of the identity in Problem 7.17. Proof: Substitute $x=y=1$ in the Binomial Theorem.
7.21 DO Give an "algebra proof" of the identity $E_n=O_n$ for $n\ge 1$. Proof: Substitute $x=1, y=-1$ in the Binomial Theorem.
7.22 DO Let $S(n,k)=\displaystyle{\sum_{j=0}^{\infty}\binom{n}{jk}}$. Prove: (a) $S(n,1)=2^n$ (b) $S(n,2)=2^n/2$
7.23 CH Prove: $|S(n,3)-2^n/3| < 1$.
7.24 STUDY Finite probability spaces from the instructor's online lecture notes (Ch. 7).
7.25 DEF A finite probability space is a pair $(\Omega, P)$ where $\Omega$ is a non-empty finite set called the sample space and $P :\Omega\to\rrr$ is a probability distribution, i.e., a function such that $(\forall a\in\Omega)(P(a)\ge 0)$ and $\sum_{a\in\Omega} P(a)=1$.
7.26 EXAMPLES of SAMPLE SPACE. Shuffled deck: $|\Omega|=52!$, $n$ dice rolled: $|\Omega|=6^n$, poker hand $|\Omega|=\binom{52}{5}$.
7.27 STUDY the concept of events, random variables, indicator variables, the uniform distribution.
7.28 STUDY the probability $P(A)$ of an event $A\subseteq\Omega$ and the expected value $E(X)$ of a random variable $X:\Omega\to \rrr$.
7.29 HW Prove: $\min X \le E(X) \le \max X.$
Here $\min X = \min\{X(a) \mid a\in \Omega\}$. The quantity
$\max X$ is defined analogously.
7.30 HW Let $X,Y :\Omega\to \rrr$ be two random varibles. Prove: $E(X+Y)=E(X)+E(Y)$.
7.31 HW Let $X :\Omega\to \rrr$ be a random varible and $c\in\rrr$. Prove: $E(cX)=cE(X)$.
7.32 DO Let $\vt_A$ denote the indicator variable of the event $A$. Prove: $E(\vt_A) = P(A)$.
HW set #6 problems due Tuesday, Oct 17, before class. Those who submitted 5.23 early, please resubmit. Please submit all problems on the due date; early submissions cause extra clerical work for the grading operation. -- First batch (6.1--6.3) posted 10-14 at 3:45pm. Complete set posted 10-14 ar 13:59pm.
6.1 HW (lemma for the soundness of RSA encryption/decryption) Let $p\neq q$ be primes and $M=\lcm(p-1,q-1)$. Let $k$ be a positive integer such that $k\equiv 1\pmod M$. Prove: $(\forall x)(x^{k}\equiv x \pmod{pq})$.
6.2 RSA public-key cryptosystem If Alice wants to receive an encrypted message from Bob, she proceeds as follows.
Alice selects two large primes, $p\neq q$. Let $N=pq$ and $M=\lcm(p-1,q-1)$. Alice also selects a positive integer $e$ such that $\gcd(e,M)=1$. She then computes a positive integer $f$ such that $ef\equiv 1 \pmod M$ (multiplicative inverse of $e$ mod $M$). Alice publishes $N,e$; this pair of numbers constitues her public key. She keeps $f$ secret; $f$ is her private key. She destroys $p,q$, she will not need those primes anymore.
Bob's message (the plaintext) is an integer $x$ between $0$ and $N-1$. Bob encrypts this message using the encryption function $E(x)=(x^e \bmod N)$ (using Alice's public key). The number $E(x)$ is the ciphertext. Bob sends the ciphertext to Alice. Alice applies the decryption function $D(y)=(y^{\,f} \bmod N)$ to $y=E(x)$.
In Problems 6.3 -- 6.5 we continue to use the notation of 6.2.
6.3 HW (Soundness of RSA encryption/decryption) Prove: $(\forall x)(0\le x\le N-1 \implies D(E(x))=E(D(x))=x)$. Your proof should be just one line based on Problem 6.1.
Comments. It follows that the RSA encryption function $E$ is a permutation of the domain $\{0,1,\dots,N-1\}$, and the decryption function $D$ is the inverse permutation. -- Alice recovers Bob's plaintext because $D(E(x))=x$. The fact that $E(D(x))=x$ is required for the application of RSA to obtain digital signatures.
6.4 DO Observe that an efficient factoring algorithm would be sufficient to break RSA. Indeed, knowing $p$ and $q$ we can efficiently compute $M$ and then a multiplicative inverse $f$ of $e$ modulo $M$, all this because of the efficiency of Euclid's algorithm. -- No efficient factoring algorithm is known either in the practical sense (factor 500-digit integers before the sun gets cold) or in the theoretical sense (factor $n$-digit integers in time not greater than $n^C$ for some constant $C$, i.e., in polynomial time).
6.5 HW Suppose Whizzy comes across a positive integer $R$ such that $M\mid R$. ($M$ is not known to Whizzy, but somehow it happens to be a divisor of $R$.) Prove that Whizzy can break Alice's code. Hint. Whizzy does not need to factor $N$ or find Alice's private key $f$. Show that given $R$ and Alice's public key, Whizzy can efficiently compute a positive integer $g$ such that $(\forall y)(y^{\, g}\equiv y^{\, f} \pmod N)$. You need to find a very simple and efficient algorithm that computes $g$ from $R, N$, and $e$. The computation should take time, polynomial in the number of digits of the three input numbers, so if $R$ is very large, Wizzy gets more time to compute $g$.
6.6 HW Let $p\neq q$ be two unkown primes. Suppose we are given the numbers $N=pq$ and $K=(p-1)(q-1)$. Show how to compute the pair $\{p,q\}$ efficiently, given $N$ and $K$. "Efficiently" means if both $N$ and $K$ have at most $n\ge 2$ digits then the computation should take no more than $n^C$ arithmetic operations on numbers having no more than $n^C$ digits, for some constant $C$. (Comment added 10-16 at 5:40pm. You may use binary search (see handout) to compute square roots; explain the number of arithmetic operations you will need in terms of $n$.) -- The moral of this story is the following. What this exercise proves then is that given $N$, computing $K$ is as hard as factoring $N$ (which we believe is hard).
6.7 HW Let $a$ and $b$ be two unknown positive integers and let $L=\lcm(a,b)$. Given $L$, efficiently compute a nonzero multiple of $ab$. Your description of the number you compute (call it $T$) (you need to express $T$ in terms of $L$, your input) should be just a few characters (less than one tenth of a line). This description will make efficient computability of $T$ obvious, you don't need to argue it. The one thing you do need to argue is that $ab\mid T$. The proof of this statement should take no more than one line.
6.8 READ Efficiency of RSA encryption/decryption. The
modular exponentiation problem takes as input
the integers $a\ge 1$, $b\ge 0$, $m\ge 1$, and asks to
compute $(a^b \bmod m)$. We could do this by repeated
multiplication as follows.
initialize $X=1$
for $i=1$ to $b$ do
$X\leftarrow (aX \bmod m)$
end(for)
return $X$
This, however, would take $b$ rounds, and of $b$ is an $n$-digit
number then this would mean about $10^n$ rounds; this is
an exponential-time algorithm. For $n=500$, it
would take many times longer than the lifetime of the Universe
even on computers with idealized speed.
The "method of repeated squaring" dramatically speeds this up.
If, for instance,
$b=2^k$ then instead of $2^k$ multiplications, it suffices to do
$k$ multiplications as follows.
initialize $X=a$
for $i=1$ to $k$ do
$X\leftarrow (X^2 \bmod m)$
end(for)
return $X$
So this process takes only $k=\log_2 b$ rounds. In each round we have
to do arithmetic with numbers not greater than $m^2$; so if $b$ ad $m$ each
have at most $n$ digits then the total number of digit-operations
involved is $O(n^3)$ (not more than some constant times $n^3$), so
it is a polynomial-time algorithm.
6.9 DO Verify that the algorithms described in 6.8 compute the results claimed.
6.10 STUDY the Repeated squaring handout for an elegant implementation of the "repeated squaring" method when $b$ is not necessarily a power of 2. Verify its stated $O(n^3)$ efficiency.
6.11 HW Prove that $F_k$, the $k$-th Fibonacci number, has at least $k/2$ binary digits $(k\ge 1)$. Give a very simple proof; don't use any results not proved in class).
6.12 CH Given the positive integers $k$ and $m$, compute $(F_k \bmod m)$ in polynomial time. (Warning: "polynomial time" means the number of steps is bounded by a constant power of the bit-length of the input which in this case is about $\log_2 k + \log_2 m$.)
6.13 REVIEW Theorem (Euclid) There are infinitely many primes.
Proof. Suppose for a contradiction that $L=\{p_1,\dots,p_k\}$ is
the set of all primes. Let $M=\prod_{i=1}^k p_i$. Let $q$ be a
prime divisor of $M+1$. Then $\gcd(q,M+1)=q$ while
$\gcd(p_i,M+1)=1$ (why? DO!), so $q$ is not among the $p_i$,
contradicting the assumption that $L$ contains all primes.
6.14 HW Prove: there are infinitely many primes $p\equiv -1\pmod 4$.
6.15 CH Prove: there are infinitely many primes $p\equiv 1\pmod 4$. Use results proved or assigned in class only.
6.16 DO Prove: there are infinitely many primes $p\equiv -1\pmod 6$.
6.17 CH Prove: there are infinitely many primes $p\equiv 1\pmod 6$. Use results proved or assigned in class only.
6.18 READ Dirichlet's Theorem (1837) Let $R = a+m\zzz$ be a
residue class where $m\neq 0$ and $\gcd(a,m)=1$.
Then $R$ contains infinitely many prime numbers.
Comment. The four preceding exercises are simple special
cases of this beautiful theorem, proved by
German mathematician Lejeune Dirichlet using complex analysis.
6.19 DO Prove that the condition in Dirichlet's theorem that $\gcd(a,m)=1$ is necessary; if $\gcd(a,m)\neq 1$ then $a+m\zzz$ contains at most one prime number.
6.20 CH (Nonlinear congruences: Hensel lifting) Let $p$ be a prime and let $f(x)$ be a polynomial with integer coefficients. (a) Suppose $(\exists a\in\zzz)(f(a)\equiv 0\pmod p$ and $f'(a)\not\equiv 0 \pmod p)$. Prove: $(\forall k\ge 0) (\exists b)(f(b)\equiv 0\pmod{p^k})$. (b) Prove that this inference becomes false for every $p$ if we drop the assumption that $f'(a)\not\equiv 0 \pmod p$. (Prove that for every $p$ there exists a counterexample.) -- Do not hand in a solution if you looked this up on the web.
6.21 REVIEW the concept of limits.
6.22 DEF We say that two functions $f(x)$ and $g(x)$ are asymptotically equal as $x\to L$, where $L$ is either a real number of $L=\pm\infty$, if $$ \lim_{x\to L} \frac{f(x)}{g(x)}=1.$$ Notation: $f(x)\sim g(x)$ as $x\to L$.
6.23 DO Prove the following asymptotic equalities as $x\to\infty$. (a) $7x^2+100x-55 \sim 7x^2$ (b) $x+\cos x \sim x$ (c) $\frac{1}{x}-\frac{1}{x+1}\sim \frac{1}{x^2}$.
6.24 DO If $f_1(x)\sim g_1(x)$ and $f_2(x)\sim g_2(x)$ as $x\to L$ then $f_1(x)f_2(x) \sim g_1(x)g_2(x)$ and $f_1(x)/f_2(x) \sim g_1(x)/g_2(x)$. For the latter we also need that $g_1(x)g_2(x) \neq 0$ for all $x\neq L$ that is sufficiently close to $L$. "Sufficiently close to $\infty$" means "sufficiently large."
6.25 HW Find a counterexample to the following
statement.
If $f_1(x)\sim g_1(x)$ and $f_2(x)\sim g_2(x)$
as $x\to\infty$ then $f_1(x)+f_2(x) \sim g_1(x)+g_2(x)$.
Make your counterexample so that for all sufficiently large $x$,
the values $f_1(x)+f_2(x)$ and $g_1(x)+g_2(x)$ are
not zero.
6.26 HW (a) Prove: $\sqrt{x^2+1}-x \sim ax^b$ for some constants $a,b$, as $x\to\infty$. Determine $a$ and $b$. Hint: use the indentity $u^2-v^2 = (u+v)(u-v)$. (b) Prove: $\ln(1+x) \sim x$ as $x\to 0$. Your proof should be one line. Hint: apply the definition of the derivative to the function $\ln(1+x)$.
6.27 Prime counting function. Let $\pi(x)$ denote the number of primes $p\le x$. For instance, $\pi(10)=4$, $\pi(100)=25$, $\pi(\pi)=2$, $\pi(-\pi)=0$.
6.28 Prime Number Theorem (PNT) (proved independently in 1896 by Jacques Hadamard and Charles Jean de la Vallée Poussin) As $x\to\infty$, $$ \pi(x) \sim \frac{x}{\ln x} \,.$$
6.29 HW Pick an integer $r$ at random, uniformly from
the set $\{1,\dots, N\}$ where $N=10^{100}$ (so every number in this
interval has the same $1/N$ chance to be chosen). Estimate the
probability that $r$ is prime. Your estimate should be given in
the form $1/m$ where $m$ is an integer. So this tells you,
how many random numbers $\le N$ you expect to have to generate
until you encounter a prime. (Make the assumption that $N$ is
large enough for the PNT to be quite accurate.)
Use the fact that $\ln 10\approx 2.3026$; do not use electronic
devices.
Comment. The large frequency of prime numbers, combined with
efficient primality testing (see below), provide the means
to efficiently generate random primes -- a requirement for
RSA.
6.30 DO (two forms of Fermat's little Theorem)
Prove the equivalence of the following two statements.
6.31 READ (primality testing via FlT)
While factoring integers is a difficult algorithmic problem,
primality testing can be done efficiently. How can we conclude
that a number is composite if we don't know a nontrivial divisor?
Here is an example. Let $b, m$ be relatively prime positive integers.
If $b^{m-1}\not\equiv 1 \pmod m$ then we know that $m$ is composite
(why?), even though we don't know any nontrivial divisor of $m$.
In this case we call $b$ a "Fermat witness" of compositeness of $m$.
6.32 DO Suppose $m$ has a Fermat witness. Prove: a number $x$ selected at random from $\{1,\dots,m-1\}$ has at least $1/2$ chance of being either not relatively prime to $m$ (in which case $\gcd(x,m)$ will be a nontrivial divisor of $m$) or being a Fermat witness. -- In each case we shall have a proof that the number is composite.
6.33 READ (optional) Unfortunately not all composite numbers have a Fermat witness. Those that don't are called Charmichael numbers. So the number $m$ is a Carmichael number if it is composite but $(\forall a)(\gcd(a,m)=1\implies a^{m-1}\equiv 1\pmod m)$. There are infinitely many Carmichael numbers but they are rare.
6.34 DO (optional) (a) Prove: if $m=pq$ where $p\neq q$ are primes then $m$ is not a Carmichael number. (b) Prove: $561=3\cdot 11\cdot 17$ is a Carmichael number. (This is the smallest.)
6.35 DO (optional) If $m$ is a composite number and it is not a Carmichael number then find efficiently and with high probability, either a nontrivial divisor of $m$ or a Fermat witness for $m$. (Hint: pick $a\in \{1,\dots,m-1\}$ at random; show that with probability $\ge 1/2$, the number $a$ will work as described in 6.32. So the probability that each of say 20 independent trials fail to turn up an approrpiate $a$ is less than $2^{-20} < 10^{-6}$.)
6.36 READ (optional) Primality testing.
There are two classical algorithms to test primality,
the Solovay-Strassen test and the Miller-Rabin test.
These tests work for all $m$, so in particular they detect the
compositeness of $m$ even if $m$ is a Carmichael number.
While these algorithms are necessarily more sophisticated,
their basic idea already appears in the preceding section.
Both tests are randomized and fast, and both are based
on Fermat's little Theorem. Randomization means they
add random bits to their input before they start the computation.
(In this case, they select a number between $1$ and $m-1$ at
random.) Given a composite integer $m$,
each algorithm finds, with probability $\ge 1/2$, either a
nontrivial divisor of $m$, or a generalized Fermat witness
(of compositeness of $m$). (Each algorithm has its own generalization
of the concept of a Fermat witness.)
If say 20 independent trials don't produce
a nontrivial divisor or a generalized Fermat witness, the algorithms
"bet" that $m$ is prime.
Now if $m$ is actually prime, such an algorithm always correctly
bets that it is prime, even though it will never have a
proof of this statement. If $m$ is composite, the algorithm
will, with probability $\epsilon\le 2^{20} < 10^{-6}$ make the mistake
of betting that $m$ is prime, but with probability
$\ge (1-\epsilon)$ it will not only declare $m$ to be composite
but will also supply a proof of this fact (provide a nontrivial
divisor or a generalized Fermat witness).
Both algorithms are elementary, as is their analysis; you may
want to read about them from readily accessible sources.
HW set #5 problems due Thursday, Oct 12, before class (except where otherwise stated), typeset in Latex. Please print and submit on paper. Please solve the "DO" exercises in problem sets #4 and #5 before Wednesday's problem session. -- First batch (5.1 - 5.14) posted 10-10 at 5:50pm. The rest posted 10-11 at 0:50am. -- Applications of CRT to computer science and technology were added on 10-11, 8pm.
5.1 DO Let $k\ge 1$. Find a multiplicative inverse of $k$ modulo $2k+1$. Your answer should be an integer between $0$ and $2k$.
5.2 HW Let $k\ge 1$. Find a multiplicative inverse of $k$ modulo $3k+1$. Your answer should be an integer between $0$ and $3k$.
5.3 HW Let $k\ge 1$. Find a multiplicative inverse of $k$ modulo $k^2+k+1$. Your answer should be an integer between $0$ and $k^2+k$.
5.4 (Recall) THEOREM. The congruence $ax\equiv b\pmod m$ is solvable if and only if $d\mid b$ where $d=\gcd(a,m)$.
5.5 DO THEOREM. Let $S(a,b,m)$ denote the set of solutions
to the congruence $ax\equiv b\pmod m$:
$$ S(a,b,m) = \{ x \mid ax\equiv b \pmod m\}$$
Let $d=\gcd(a,m)$.
(a) If $d\nmid b$ then $S(a,b,m)=\emptyset$.
(b) If $d\mid b$ then there exists $u\in\zzz$ such that
$$ S(a,b,m) = u + (m/d)\zzz .$$
In other words, $x\in\zzz$ is a solution if and only if
$x\equiv u \pmod{m/d}$. In particular, the soluton is
unique modulo $m/d$ and the set of solutions is a
residue class modulo $m/d$.
5.6 DO Count the solutions modulo $m$. In other words, how many mod $m$ residue classes consist of solutions to the congruence $ax\equiv b\pmod m$?
5.7 DO Assume $a,m$ are relatively prime. Solve $ax\equiv b\pmod m$ using Euclid's algorithm by the method described in the Handout.
5.8 DO Consider the system of $k$ congruences $$(\ast) \qquad x\equiv a_i\pmod{m_i} \qquad (i=1,\dots,k).$$ Let $\lcm(m_1,\dots,m_k)=M$. Prove: if this system has a solution then the set of solutions for a residue class modulo $M$. In other words, if $u$ is a solution than a number $x$ is a solution if and only if $x\equiv u\pmod M$, i.e., the set of solutions is the residue class $u+M\zzz$.
5.9 HW Prove: $(\forall k)(\forall m_1,\dots,m_k) (\exists a_1,\dots,a_k)$ such that the system $(\ast)$ is solvable. COMMENTS. This problem shows that the sufficient condition for solvability assumed in CRT (that the $m_i$ are pairwise relatively prime) is as far from being necessary as it gets. --- This is an "ah-ha" problem, the solution can be described in half a line. Please do NOT collaborate on this problem.
5.10 CHINESE REMAINDER THEOREM (CRT). Consider the system $(\ast)$ of simultaneous congruences. If the $m_i$ are pairwise relatively prime then the system is solvable.
Proof sketch. We assume none of the $m_i$ is zero. (See Problem 5.12 below.) Let $M=\prod m_i$ and $N_i=M/m_i$. So $m_j \mid N_i$ for $i\neq j$ and $\gcd(N_i,m_i)=1$. We try to find $x$ in the form $x = \sum_{i=1}^k N_ix_i$. Then $(\ast)$ takes the form $N_jx_j\equiv a_j \pmod m_j$ $(j=1,\dots,k)$ (why?), so we succeeded in separating the unknowns. Solve each of these linear congruences and combine them to $x$. The teps are necessary and sufficient, so the $x$ we get is indeed a solution. QED
5.10a DO Prove: $\gcd(N_1,\dots,N_k)=1$.
5.11 DO Under the conditions of CRT, the solutions form a residue class modulo $M=\prod_{i=1}^k m_i$.
5.12 DO Prove CRT in the case when one of the $m_i$ is zero.
5.13 DO If $m_1,\dots, m_k$ are pairwise relative prime then their lcm is $\pm$ their product.
5.14 DO Show that the converse is false: If $\lcm(m_1,\dots,m_k)=\pm\prod_{i=1}^k m_i$, it does not follow that the $m_i$ are pairwise relatively prime. Find all counterexamples.
5.15 HW Solve the following system of
simultaneous congruences or prove that there is no
solution.
$x\equiv 7 \quad\pmod{24}$
$x\equiv -5 \ \pmod {28}$
$x\equiv 25 \ \ \pmod {54}$
5.16 DO If $p$ is a prime number then $x^2\equiv 1\pmod p$ if and only if $x\equiv \pm 1 \pmod p$. (Done in class. Review!)
5.17 HW Let $m=pq$ where $p > q \ge 3$ are primes. Prove: the congruence $x^2\equiv 1\pmod m$ has solutions other than $x\equiv\pm 1\pmod m$. (Comment added 10-10 at 1:135am. As stated before, in a mathematical statement, unquantified variables are interpreted as universally quantified. So for instance when we make the statement that "$a+b=b+a$," we mean $(\forall a,b)(a+b=b+a)$. Relevance to the present problem: you have to prove the conclusion for all $p$ and $q$ that satisfy the conditions.)
5.18 FERMAT'S LITTLE THEOREM (FlT) If $p$ is a prime and $\gcd(a,p)=1$ then $a^{p-1}\equiv 1\pmod p$.
5.19 DO Give simple proofs of FlT for small primes ($p=2,3,5,7$).
5.20 NOTATION For $m\neq 0$ we write $(a \bmod m)$ to denote the smallest non-negative remainder of $a$ modulo $m$. For instance, $(53 \bmod 17)=2$ and $(-53 \bmod 17)=15$. If $x=(a\bmod m)$ then $a\equiv x\pmod m$ and $0\le x \le |m|-1$. The LaTeX code is \$(a\bmod{m})\$.
5.21 HW Compute $$\left(2^{3^{10^6}}\bmod{67}\right)$$
Show all your work. Do NOT use electronic devices.
Warning: the tower of exponentials with no parentheses
is evaluated top-down:
$$2^{\left(3^{(10^6)}\right)}$$
So this number is $2^a$ where $a=3^b$ where $b=10^6$.
5.22 DO Prove: If $\gcd(a,247)=1$ then $a^{36}\equiv 1\pmod{247}$. Note: $247=13\times 19$.
5.23 HW, due Tuesday, Oct 17 Prove: if $p\ge 3$ is a prime and $p\mid x^2+1$ for some integer $x$ then $p\equiv 1\pmod 4$. For instance $5\mid 7^2+1$ but $3$ is not a divisor of any number of the form $x^2+1$. (Hint. Write the assumption as a congruence. Use FlT.)
5.24 CH Prove the converse: If $p$ is a prime and $p\equiv 1\pmod 4$ then $(\exists x)(p\mid x^2+1)$. You may use a theorem stated but not proved in class. Do not use results not stated in class.
5.25 Please solve the "DO" exercises in problem sets #4 and #5 before Wednesday's problem session.
5.26 Math history and entertainment. Study Fermat's Last Theorem and its 357-year saga, including the human drama on the way to its solution by Andrew Wiles (1994). For a light take, see the musical "Fermat's Last Tango." (Note: FLT has nothing to do with FlT, other than that they were both conceived by Pierre de Fermat, a 17th century French lawyer, in his spare time. FlT is an easy exercise; FLT was the most famous open problems of mathematics for three and a half centuries (1637-1994).)
5.27 Application of CRT to parallel computation and computation with limited storage. If you need to do a long sequence of additinos, subtractions, and multiplications on very large numbers, instead of using multiple-precision arithmetic, you can pick a list of distinct primes, $p_1,\dots,p_k$, reduce your numbers modulo $p_i$, perform all calculations modulo $p_i$, and in the end combine your result by CRT. You can do the calculations on $k$ processors in parallel, saving time, or you can do them sequentially, saving space. The space reduction can be dramatic: if each $p_i$ has say 10 digits and you take say 1000 primes, you will be able to perform arithmetic on 10,000-digit numbers by working with 20-digit numbers.
5.28 Application of CRT to radar systems. An example of CRT, with moduli 3, 5, and 7, was first described by 3rd-century Chinese mathematician Sunzi. Could Sunzi have imagined that his mathematical puzzle would, 17 centuries later, become an indispensable tool for aviation? I found this compelling technological example on Mathoverflow. The comment was made by "Ian" on July 30, 2010 and is quoted below verbatim.
"Many radar systems work by sending electormagnetic pulses out at regular intervals, waiting in between pulses to look for reflections from objects. You want to calculate an object's distance from the time it takes to see a reflection. If time between pulses is very long, this works, but if you are observing something dynamic you want fast updates, so you need shorter time between pulses. But then you don't know which pulse's reflection you are seeing, so object range is only known modulo (speed of light)*(pulse interval). The solution is to send out a few different types of pulses (say, with different wavelengths of light), with each type of pulse having its own pulse interval, and making those intervals coprime. Then you can use the CRT to calculate range mod some very large distance (where you know, practically speaking, that you won't be registering any reflections from such large distances)."
HW set #4 problems due Tuesday, Oct 10, before class, typeset in Latex. Please print and submit on paper. -- First batch (4.1--4.7) and Euclid's algorithm handout (including calculation of the multiplicative inverse) posted 10-06 at 7:15pm. The rest posted in installments between 6pm and 8pm on 10-09. All problems except 4.40 were assigned in class. If you wish, you can submit 4.40 in legible handwriting.
4.1 HW Let the decimal digits of the positive integer $x$ be
$a_n,a_{n-1},\dots,a_0$ (in this order).
(a) The "$9$-rule" gives an easy way to compute the
remainder of $x$ modulo $9$. The rule says that
$$x\equiv \sum_{i=0}^n a_i \pmod{9}.$$
For instance, $8193 \equiv 8+1+9+3=21 \equiv 2+1 = 3 \pmod{9}$.
Prove the validity of the $9$-rule.
(b) The "$11$-rule" says that
$$x\equiv \sum_{i=0}^n (-1)^i a_i \pmod{11}.$$
For instance, $8193 \equiv -8+1-9+3=-13\equiv -(-1+3)=-2 \pmod{11}$.
Prove the validity of the $11$-rule.
4.2 CH Let $F_n$ be the $n$-th Fibonacci number, as defined in DEF 3.20. Let $k,\ell \ge 0$. Prove: $\gcd(F_k, F_{\ell}) = F_d$ where $d=\gcd(k,\ell)$.
4.3 DO Prove: $(\forall a,b,d)(a\zzz + b\zzz = d\zzz \iff d $ is a g.c.d. of $a$ and $b)$
4.4 Division Theorem. $(\forall a,b)($ if $b\neq 0$ then $(\exists ! q,r)(a=bq+r $ and $0\le r \le |b|-1))$
4.5 DO Prove the Division Theorem for $a\ge 0$ by induction on $a$. Then infer from this that the Division Theorem also holds when $a <0$.
4.6 DO Euclid's algorithm. Review the Handout (click). Solve all problems in the Handout.
4.7 HW Let $a\ge b \ge 1$. Let $n$ be the number of binary digits of $b$. Prove: The algorithm, as described in the Handout (Pseudocode A) terminates in $\le 2n$ rounds (executions of the while loop).
4.8 DEF G.c.d. of a set of numbers Let $T\subseteq \zzz$. We say that $d\in\zzz$ is a g.c.d. of $T$ if
4.9 DO Prove uniqueness of g.c.d. up to sign:
(a) if $d$ is a g.c.d. of $T$ then $-d$ is also
a g.c.d. of $T$ (b) $d$ and $-d$ are the only
g.c.d.'s of $T$.
NOTATION. We write $\gcd(T)$ to
denote the nonnegative value among the g.c.d's of $T$.
4.10 DO Prove: $d$ is a g.c.d. of $T$ if and only if $$\Div(d) = \bigcap_{a\in T} \Div(a)$$
4.11 HW (a) Find $\gcd(\emptyset)$. (b) Find $\gcd(\zzz)$. Reason your answers.
4.12 HW Find the gcd of all numbers of the form $p^2-1$ where $p\ge 5$ is a prime number, i.e., find $\gcd(5^2-1, 7^2-1, 11^2-1, 13^2-1,\dots)$. Note that this is the gcd of an infinite set of numbers. Prove your answer.
4.13 DEF We say that the subset $G\subseteq\zzz$ is a subgroup of $\zzz$ if (1) $G\neq\emptyset$ ; (2) $G$ is closed under subtraction, i.e., $(\forall a,b)(a,b\in G \implies a-b\in G)$. Notation: $G\le \zzz$.
4.14 DO (a) Prove: $(\forall d)(d\zzz\le \zzz)$. (b) Prove: the intersection of subgroups is a subgroup. (This is true even if we take the intersection of infinitely many subgroups.)
4.15 DEF A subgroup of the form $d\zzz$ is called a cyclic subgroup, generated by $d$. The number $d$ is called the generator of $d\zzz$.
4.16 THEOREM Every subgroup of $\zzz$ is cyclic.
4.17 DO Prove the Theorem. First prove the following. Assume $T$ is a subgroup.
4.18 DO Prove: $a\zzz+ b\zzz\le \zzz$.
4.19 DO (Second proof of the existence of gcd) Combine the preceding exercise with Problem 4.3. This proves the existence of gcd and also that it is a linear combination of $a$ and $b$.
4.20 DEF A linear combination of a set $T\subseteq\zzz$ means a finite sum of the form $\sum x_ia_i$ where $a_i\in T$. (We take the linear combinations of all finite subsets of $T$.) Let $\lin(T)$ denote the set of linear combinations of $T$.
4.21 DO (a) Find $\lin(\emptyset)$. WARNING: this is not empty! (Hint: empty sum.) (b) Find $\lin(\zzz)$.
4.22 DO Prove: $\lin(T)\le \zzz$ ($\lin(T)$ is a subgroup).
4.23 DO Prove: $d$ is a g.c.d. of $T$ if and only if $d$ generates $\lin(T)$, i.e., $\lin(T)=d\zzz$.
4.24a THEOREM (a) Every subset $T\subseteq\zzz$ has a greatest common divisor, and it can be written as a linear combination of $T$.
4.24b DO Prove the Theorem. Hint: Combine the preceding two exercises with Theorem 4.16 (all subgroups of $\zzz$ are cyclic).
4.25 DEF We say that $m$ is a least common multiple (l.c.m.) of the set $T\subseteq\zzz$ if
4.26 DO Prove uniqueness of l.c.d. up to sign: (a) if $m$ is a l.c.m. of $T$ then $-d$ is also a l.c.m. of $T$ (b) $d$ and $-d$ are the only l.c.m.'s of $T$. NOTATION. We write $\lcm(T)$ to denote the nonnegative value among the l.c.m.'s of $T$.
4.27 DO Find (a) $\lcm(\emptyset)$ (b) $\lcm(\zzz)$.
4.28 THEOREM Every subset $T\subseteq\zzz$ has a l.c.m.
4.29 DO Prove the Theorem. Hint.
First proof. Take the gcd of all common multiples.
Second proof. Take a generator of $\bigcap_{a\in T} a\zzz$.
In each case you got a suspect. Prove: each works.
4.30 DO Prove: $\gcd(a,b)\cdot\lcm(a,b) = |a|\cdot |b|$
4.31 DO Prove: (a) $(\forall a,b,r)(r$ is a common divisor of
$a$ and $b$ if and only if $r\mid \gcd(a,b)$)
(b) $(\forall a,b,s)(s$ is a common multiple of
$a$ and $b$ if and only if $\lcm(a,b)\mid s$)
4.32 HW Find three positive integers such that they are pairwise not relatively prime but the gcd of the three numbers is 1.
4.33 DO Prove: if $d$ is a common divisor of the numbers $a$, $b$, and $m$, and $d\neq 0$, then $$ a\equiv b \pmod m \implies \frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}}$$
4.34 DO If $a\equiv b\pmod m$ and $d\mid m$ then $a \equiv b \pmod d$. What property of divisibility is being used in the proof?
4.35 DEF Linear congruence: Given $a,b,m$ solve $ax\equiv b \pmod m$.
4.36 THEOREM The congruence $ax\equiv b \pmod m$ is solvable if and only if $\gcd(a,m)\mid b$. (Proved in class, review)
4.37 DEF We say that $x$ is a multiplicative inverse of $a$ modulo $m$ if $ax\equiv 1\pmod m$.
4.38 COROLLARY to THM 4.36 The number $a$ has a multiplicative inverse modulo $m$ if and only if $a$ and $m$ are relatively prime.
4.39 DO Prove: the multiplicative inverse is unique modulo $m$. More precisely, suppose $x$ is a multiplicative inverse of $a$ modulo $m$. Then a number $y$ is a multiplicative inverse of $a$ modulo $m$ if and only if $x\equiv y\pmod m$.
4.40 HW Calculate a multiplicative inverse of $17$ modulo $61$. Your answer should be a number between $0$ and $60$. Use the method shown in the Handout. Show all your steps.
HW set #3 problems due Thursday, Oct 5, before class, typeset in Latex. Please print and submit on paper. Grace period has expired. -- First batch (3.1--3.23) posted 10-03 at 3:30pm. Euclid's lemma (3.15) was promoted to "HW" (as stated in class). Posting completed 10-03 at 6:30pm.
3.1 NOTATION For $a\in\zzz$ we write $\Div(a)$ to denote the set of divisors of $a$. For instance, $\Div(6)=\{\pm1,\pm2,\pm3,\pm 6\}$, and $\Div(0)=\zzz$.
3.2 NOTATION $\Div(a,b)$ denotes the set of common divisors of $a$ and $b$. In other words, $\Div(a,b)=\Div(a) \cap \Div(b)$.
3.3. DO $\Div(a) = \Div(-a)$ and $\Div(a,b)=\Div(\pm a,\pm b)$
3.4 DEF We say that $d$ is a greatest common divisor of $a$ and $b$ if
3.5 DO Prove: $d$ is a greatest common divisor of $a$ and $b$ if and only if $\Div(a,b)=\Div(d)$.
3.6 DO Prove: if $d$ is a g.c.d. of $a$ and $b$ then (a) $-d$ is also a g.c.d., and (b) there is no greatest common divisor other than $\pm d$.
3.7 NOTATION : If the greatest common divisors of $a$ and $b$ are $\pm d$ then we shall write $\gcd(a,b)=|d|$. So we use the $\gcd$ notation to denote the nonnegative value among the two g.c.d. values. (We write "g.c.d." with periods between the letters to refer to both greatest common divisors, and $\gcd$ to refer to just the nonnegative one.)
3.8 DO Prove: $\gcd(0,0)=0$.
3.9 DO Prove: $(\forall a)(\gcd(a,a) = \gcd(a,0)=|a|)$.
3.10 DO Prove: $a,b$ are relatively prime, i.e., $\Div(a,b)=\pm1$, if and only if $\gcd(a,b)=1$.
3.11 DEF A linear combination of the numbers $a,b$ is a number of the form $ax+by$ $(x,y\in\zzz$ in our context). So the set of linear combinations of $a$ and $b$ is the set $a\zzz+b\zzz$.
3.12 DO If $d$ is a common divisor of $a,b$ then $d$ is also a common divisor of all linear combinations of $a$ and $b$.
3.13 REMARK The following result states the existence of $\gcd$ and adds the powerful fact that the $\gcd$ is a linear combination. This added power will be the key to our proof of the unique prime factorization theorem.
3.14 THEOREM (Euclid) (a) $(\forall a,b)(\exists \gcd(a,b))$
(b) The $\gcd$ can be written as a linear combination, i.e.,
$(\forall a,b)(\exists x,y)(ax+by=\gcd(a,b))$.
3.15 HW (Euclid's lemma) $\Div(a,b)=\Div(a-b,b)$.
3.16 DO Prove Thm 3.14.
Sketch. For part (a) we need to show:
$(\forall a,b)(\exists d)(\Div(a,b)=\Div(d))$
First observe that we may assume
$a\ge b\ge 0$. Now prove the theorem by induction
on $a+b$. Base case: $b=0$ true by setting $d=a$:
$\Div(a,0)=\Div(a)$.
Now $a\ge b\ge 1$.
INDUCTIVE HYPOTHESIS (I.H.) The result is true
for all $a',b'\ge 0$ such that $a'+b' < a,b$.
Now $\Div(a,b)=\Div(a-b,b)$ by Euclid's lemma,
and $(\exists d)(\Div(a-b,b)=\Div(d))$
by the IH, applied to
$a'=a-b, b'=b$ (so $a'+b'=a < a+b$ because $b\ge 1$).
QED
Prove part (b) by the same inductive scheme.
3.17 DO Prove: $\gcd(a,b)=\gcd(a-b,b)$.
3.18 DO Prove: $\gcd(a,a+1)=1$.
3.19 DO For what values of $a$ is $\gcd(a,a+2)=1$ ?
3.20 DEF The sequence of Fibonacci numbers, $F_0, F_1, F_2, \dots$, is defined as follows. $F_0=0, F_1=1$, and for $n\ge 2$ we have $F_n=F_{n-1}+F_{n-2}$. So the sequence begins with $0,1,1,2,3,5,8,13,21,34,55,89,\dots$.
3.21 HW Prove that consecutive Fibonacci numbers are relatively prime, i.e., $\gcd(F_n,F_{n+1})=1$.
3.22 DO Prove, without using unique prime factorization, that if $a\mid bc$ and $\gcd(a,c)=1$ then $a\mid b$. Hint: write $1$ as a linear combination of $a$ and $c$.
3.23 HW Let $k,\ell \ge 0$ and let $d=\gcd(k,\ell)$. Prove: $\gcd(2^k-1,2^{\ell}-1)=2^d-1$. Hint: induction on $k+\ell$.
3.24 HW Write the number $1$ as a linear combination of the numbers $55$ and $89$, i.e., find an integer solution to the equation $55x + 89y =1$. Describe how you found your solution.
3.25 DEF The number $p\in\nnn$ is prime if $|\Div(p)|=4$. In other words, $p > 1$ and $\Div(p)=\{\pm 1, \pm p\}$.
3.26 DEF The number $n\in\nnn$ is composite if $n >1$ and $n$ is not prime. (So the number $1$ is neither prime nor composite.)
3.27 DEF The number $z\in\zzz$ has the prime property if $(\forall a,b)(z\mid ab \implies (z\mid a \vee z\mid b))$.
3.28 DO Composite numbers do not have the prime property.
3.29 DO The number $0$ has the prime property.
3.30 THEOREM (Euclid) The prime numbers have the prime property.
This theorem is at the heart of the proof of the Fundamental Theorem of Arithmetic (below).
3.31 PROOF of Thm 3.30. (Done in class, review.)
Let $p$ be a prime. Suppose $p\mid ab$ but
$p \nmid a$. We need to show that $p\mid b$.
Claim. $\gcd(p,a)=1$.
Indeed, the only positive divisors of $p$ are $1$ and $p$
and $\gcd(p,a)\neq p$ (because $p\nmid a$). It follows that
$(\exists x,y)(px+ay=1)$. Multiplying each side by $b$
we obtain that $pbx+aby=b$.
Now $p\mid pbx$ (obviously) and $p\mid aby$ (because
$p\mid ab$). Consequently, $p\mid pbx+aby=b$. QED
3.32 FUNDAMENTAL THEOREM OF ARITHMETIC (FTA). Every positive integer can be written uniquely as a product of prime numbers (uniquely up to ordering).
3.33 DO Prove the existence of a prime factorization. This is the easy part of the FTA. (Proof by induction, done in class, review.)
3.34 DO Prove the hard part (uniqueness) in the FTA. Hint: induction. For the inductive step, use the prime property of prime numbers.
3.35 CONVENTION Empty sum is zero; empty product is one. This is the only possible consistent way to define empty sum and product. In particular, $0!=1$ and $0^0=1$. Based on this convention, the number $1$ has a prime factorization: it is the product of the empty set of primes.
3.36 DO Let $d(n)$ denote the number of positive divisors of $n$. Prove: $d(n) < 2\sqrt{n}$.
3.37 DO Let $n=p_1^{e_1}\cdot\dots\cdot p_k^{e_k}$ be the prime factorization of $n$ where the $p_i$ are distinct primes. Prove: $d(n)=\prod_{i=1}^k (e_i+1)$.
3.38 DO (optional) Let $s > 1$ be a real number. The zeta function is defined as $$ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} .$$ Prove: $$\zeta(s) = \prod_{p}\frac{1}{1-\frac{1}{p^s}}$$ where the product extends over all primes $p$. (What does this have to do with today's lesson?)
3.39 HW Prove: if $a\equiv b \pmod{m}$ then $\gcd(a,m)=\gcd(b,m)$. Do not use the FTA.
3.40 CH Let $p$ be a prime number. Assume the power $p^t$ divides the binomial coefficient $\binom{n}{k}$. Prove: $p^t \le n$.
HW set #2 problems due Tuesday, Oct 3, before class, typeset in Latex. Please print and submit on paper. Those who are not familiar with Latex may submit their solutions in handwriting on Oct 3 for a last time. The grace period expires after that.
2.1 NOTATION. Let $A\subseteq \zzz$ and $u\in\zzz$. We write $A+u = \{a+u \mid a\in A\}$ and $uA = \{ua \mid a\in A\}$. So fir instance $2\zzz$ is the set of even integers and $2\zzz+1$ is the set of odd integers.
2.2 HW Prove: $(\forall a,b\in \zzz)(\forall n\in\nnn)(a-b \mid a^n-b^n)$ (Note: $0^0=1$.)
2.3 HW Recall the notation $\nnn=\{0,1,2,\dots\}$. Prove: $(\forall a,b\in \zzz)(\forall n\in 2\nnn+1)(a+b \mid a^n+b^n)$
2.4 HW (Updated 9-30, 8:00pm)
Find all relatively prime pairs $(a,b)$ of
integers such that $a+b\mid a^2+b^2$.
In addition to describing all solutions by
a small number of simple formulas,
explicitly list the six
"smallest" solutions where the "size" of a solution
$(a,b)$ is measured by the quantity $|a|+|b|$.
COMMENTS. (A) See DEF 2.44 for the definition
that the integers $a$ and $b$ are relatively prime.
(B) You may use the "DO" exercise 2.45 in your solution.
(C) There are infinitely many solutions;
give a simple description of the set of all solutions.
This description should not take up more than two lines.
(D) The bulk of your solution will be a proof that
you found all solutions.
(E) Partial credit.
Find infinitely many (but not necessarily all)
solutions for partial credit. There is a very
simple description of an infinite set of easily verified
solutions. It takes less than half a line to describe those
solutions and only three or four words to verify them.
("Ah-ha" problem.) Remember that $a$ and $b$ are
integers, not necessarily positive.
(F) The condition that $a$ and $b$ are relatively prime was
stated in class but was omitted in the original posting of this
problem. So, for instance,
the pair $(10,15)$ does not qualify, because even though
$10+15 = 25 \mid 10^2+15^2=325$, the pair $(10,15)$ is not
relatively prime.
This omission was corrected and further explanations were added
on Saturday, Sep 30, at 8:00pm.)
2.5 DO Prove the identity $|A\cup B|+|A\cap B|=|A|+|B|$ using indicator functions. (Done in class; review.)
2.6 DEF A predicate on a set $\Omega$ is a "TRUE/FALSE" assignment to each element of $\Omega$. This is essentially the same as an indicator function (1 = TRUE, 0 = FALSE).
2.7 DO Count the predicates on a set of $n$ elements. (Answer: $2^n$. Done in class; review.)
2.8 DEF A relation on a set $\Omega$ is a predicate on $\Omega\times\Omega$ (assignment of TRUE/FALSE to each ordered pair of elements of $\Omega$).
2.9 DO Count the relations on a set of $n$ elements. (Answer: $2^{n^2}$. Done in class; review.)
2.10 DEF reflexive, irreflexive, symmetric, antisymmetric, transitive relations (see class notes or other source)
2.11 HW Count (a) the irreflexive, symmetric relations (b) the symmetric relations on a set of $n$ elements. Your answers should be very simple expressions in terms of $n$. Reason your answer.
2.12 DO Prove: divisibility is a transitive relation on $\zzz$.
2.13 DEF A relation is an equivalence relation if it is reflexive, symmetric, and transitive.
2.14 DEF A partition of a set $\Omega$ into blocks $A_1,\dots,A_m$ means $A_1,\dots,A_m$ are nonempty subsets of $\Omega$ that are pairwise disjoint, i.e., $(\forall i\neq j)(A_i\cap A_j=\emptyset)$, and they cover all of of $\Omega$ ($\bigcup_{i=1}^m A_i=\Omega$). The order of the blocks does not matter.
2.15 DEF Given a partition $\Pi=\{A_1,\dots,A_m\}$ of $\Omega$, define the relation $\sim_{\Pi}$ on $\Omega$ by letting $x\sim_{\Pi}y$ if and only if $x$ and $y$ belong to the same block, i.e., $(\exists i)(x,y\in A_i)$.
2.16 DO Prove: $\sim_{\Pi}$ is an equivalence relation.
2.17 FUNDAMENTAL THEOREM OF EQUIVALENCE RELATIONS. If $R$ is an equivalence relation on $\Omega$ then there exists a unique partition $\Pi$ such that $R = \sim_{\Pi}$.
2.18 Discussion. This theorem is the basis of how we form concepts (numbers, colors, etc.)
2.19 DO Prove the Fundamental Theorem of Equivalence Relations. Hint. For $a\in\Omega$ let $[a]=\{b \mid aRb\}$. We claim that the sets $[a]$ ($a\in\Omega$) form a partition of $\Omega$ and this partition corresponds to $R$. To prove this, we need to prove:
2.20 DEF Congruence For $a,b,m\in\zzz$ we say that $a$ is congruent to $b$ modulo $m$, denoted $a\equiv b \pmod m$, if $m\mid a-b$. Examples: $3\equiv 17 \pmod 7$, $-8\equiv 32 \pmod{20}$, $3\equiv 17 \pmod{-7}$. LaTeX code for the last example: \$ 3\equiv 17 \pmod{-7} \$
2.21 DO When are two numbers congruent modulo $0$ ?
2.22 DO When are two numbers congruent modulo $1$ ?
2.23 DO When are two numbers congruent modulo $2$ ? (Answer: when they have the same parity, i.e., either both are even or both are odd. Verify!)
2.24 DO Find all values of $m$ such that $(\forall a,b)(a\equiv b\pmod m)$.
2.25 DO Find all values of $m$ such that $(\forall a,b)(a\equiv b\pmod m \implies a=b)$.
2.26 DO If March 3 is Tuesday then what day of the week is March 24 ? When do days $k$ and $\ell$ of a month fall on the same day of the week? Express your answer in terms of a congruence. Explain why "modular arithmetic" (the study of congruences) is called "calendar arithmetic" when taught to children.
2.27 DO Let $p$ be a prime number. Prove: (a) if $p\ge 3$ then $p\equiv \pm1 \pmod 4$ (b) if $p\ge 5$ then $p\equiv \pm1 \pmod 6$.
2.28 HW Prove: if $a$ is odd then $a^2\equiv 1 \pmod 8$.
2.29 DO Fix $m\in\zzz$. Prove: congruence modulo $m$ is an equivalence relation.
2.30 TERMINOLOGY The equivelence classes of this equivalence relation are called "mod $m$ residue classes." Example: the mod 2 residue classes are the set of even numbers and the set of odd numbers.
2.31 DO Prove: for $m\ge 1$, the mod m residue classes are the sets $m\zzz, m\zzz+1,\dots,m\zzz+(m-1)$.
2.32 Let $a\equiv x \pmod m$ and $b\equiv y \pmod m$. Prove:
2.33 DO Prove: $(\forall a,b,m\in\zzz)(\forall n\in\nnn)
(a\equiv b\pmod m \implies a^n\equiv b^n\pmod m)$
Hint #1. Use the preceding exercise and
mathematical induction.
Hint #2 (second solution). Use one of the HW problems
stated earlier in this problem set.
2.34 HW Find all values of $m$ for which the following statement is true: $(\forall a,b,c)(ca\equiv cb\pmod m \implies a\equiv b\pmod m)$. Prove your answer.
2.35 DEF Let $\Pi=\{A_1,\dots,A_m\}$ be the set of equivalence classes under the equivalence relation $R$. A complete set of representatives for $R$ is a set $B\subseteq\Omega$ such that $(\forall i)(|A_i\cap B|=1)$, i.e., $B$ contains one element from each equivalence class $A_i$.
2.36 DO (Characterization of a complete sets of representatives) Let $R$ be an equivalence relation on $\Omega$ with $m$ equivalence classes. Prove: a set $B\subseteq\Omega$ is a complete set of representatives for $R$ if and only if (a) $|B|=m$ and (b) no two distinct elements of $B$ are in relation $R$ with each other.
2.37 DEF A complete set of residues modulo $m$ is a complete set of representatives of the congruence modulo $m$.
2.38 DO Let $m\ge 1$. Infer from 2.36: The numbers $a_1,\dots,a_m$ form a complete set of residues modulo $m$ if and only if $(\forall i,j)(a_i\equiv a_j\pmod m \implies i=j)$.
2.39 HW Find a complete set of residues modulo 7 that consists of prime numbers.
2.40 HW Find a complete set of residues mod 13 that consists of a 12-term geometric progression and the number 0.
2.41 DEF (optional) Let $p\ge 2$ be a prime number. A number $g$ is is called a primitive root mod $p$ if the $(p-1)$-term geometric progression $1,g,g^2,\dots,g^{p-2}$ together with the number $0$ forms a complete set of residues mod $p$.
2.42 Theorem (Primitive roots) (optional) For every prime number $p$ there exists a primitive root mod $p$.
2.43 DO (optional) Find the smallest primitive root modulo the prime numbers 2, 3, 5, 7, 11.
2.44 DEF We say that two integers are relatively prime
if they have no common divisors other than $\pm1$.
For instance,
$24$ and $42$ are not relatively prime since $3$ is a common divisor
of these numbers. ($2$ and $6$ are also common divisors;
any of these demonstrate that $24$ and $42$ are not
relatively prime.)
The numbers $a=10$ and $b=-21$ are relatively prime.
To prove this, assume $d$ is a common divisor of these two numbers.
Then $d\mid 2a+b= -1$, so $d=\pm 1$.) (Expanded
explanation to this definition was added 9-30 at 8:30pm.)
2.45 DO (a) Prove: if $a$ and $b$ are relatively prime then $a$ and $a+b$ are also relatively prime. (b) Prove: if $a$ and $b$ are relatively prime then $a+b$ and $ab$ are relatively prime. (c) Prove: if $a\mid bc$ and $a$ and $c$ are relatively prime then $a\mid b$. (This problem was expanded on 9-30 at 8:00pm to assist with the solution of HW 2.4.)
2.46 HW Prove: if $ac\equiv bc \pmod m$ and $c$ and $m$ are relatively prime then $a\equiv b \pmod m$. Use the preceding exercise.
2.47 HW Let $m\ge 1$. Prove: if $a_1,\dots,a_m$ form a complete set of residues mod $m$ and $c$ and $m$ are relatively prime then $a_1c,\dots,a_mc$ form a complete set of residues mod $m$.
HW set #1 problems due Thursday, Sep 28, before class, typeset in Latex. Please print and submit on paper. There is a week's grace period for those not familiar with Latex. -- Solve DO exercises 1.19 - 1.25 before Wednesday's problem session.
1.1 DO Let $A$, $B$ be finite sets. Prove: $|A\cup B|+|A\cap B|=|A|+|B|.$
1.2 DEF Let $A,B\subseteq \zzz$ be subsets of the integers. We define the sumset $A+B$ as $$A+B = \{a+b \mid a\in A, b\in B\}.$$
1.3 DO "$\emptyset$" denotes the empty set. Prove: $A+\emptyset = \emptyset$.
1.4 DO Prove: $|A+B|\le |A|\cdot |B|$.
1.5 HW Let $A,B\subseteq \zzz$ be non-empty finite subsets of the integers; let $|A|=k, |B|=\ell$. (So $k,\ell \ge 1$.) Prove: $|A+B|\ge k+\ell -1 $.
1.6 HW Let $k\ge 0$ be a non-negative integer. Find the maximum value of $|A+A|$ for all $k$-subsets $A\subseteq\zzz$ (i.e., for all subsets $A$ of $\zzz$ with $k$ elements). (a) Guess this maximum. It should be a simple function of $k$. (b) Prove that the value you guessed is a valid upper bound on $|A+A|$. (c) Prove that this upper bound is actually attained, i.e., find a set $A$ such that $A+A$ has the size you guessed.
1.7a DEF A family of sets is defined as an assignment of a set $A_i$ to each member $i\in I$ of an index set $I$. Notation: $\{A_i \mid i\in I\}$.
1.7b DEF Let $\{A_i \mid i\in I\}$ be a family of sets. The union of this family, $ \bigcup_{i\in I} A_i $, is defined by its members as follows. $$(\forall x)\left(x\in \bigcup_{i\in I} A_i \iff (\exists i)(x\in A_i)\right).$$ So membership in the union of a family of sets is defined using the existential quantifier. Similarly, membership in the intersection of a family of sets is defined using the universal quantifier: $$(\forall x)\left(x\in \bigcap_{i\in I} A_i \iff (\forall i)(x\in A_i)\right).$$
1.8 DEF If we discuss subsets of a fixed "universe" $\Omega$, the complement $\Abar$ of a subset $A\subseteq\Omega$ is the set $\Abar=\Omega\setminus A= \{x\in\Omega \mid x\notin A\}$.
1.9 DO Prove De Morgan's laws: if all the sets $A_i$ are subsetes of $\Omega$ then $$ \overline{\bigcup_{i\in I} A_i} = \bigcap_{i\in I} \Abar_i$$ and $$ \overline{\bigcap_{i\in I} A_i} = \bigcup_{i\in I} \Abar_i$$
1.10 DEF Let $A,B$ be sets. We write $B^A$ to denote the set of functions with domain $A$ and codomain $B$ (i.e., the set of functions $f: A\to B$).
1.11 DO Prove: $|B^A|=|B|^{|A|}$.
1.12 DEF The powerset $\calP(A)$ of the set $A$ is the set of all subsets of $A$.
1.13 DEF Let $\Omega$ be a set. An indicator function (or characteristic function) is a function $f:\Omega\to \{0,1\}$. For $A\subset\Omega$, the indicator function (or characteristic function) of $A$ is the function $f_A:\Omega\to\{0,1\}$ defined by the assignment $$ f_A(x) = \begin{cases} 1 &\text{ if }& x\in A \\ 0 &\text{ if }& x\notin A \end{cases} $$
1.14 DO Prove: If $|\Omega|=n$ then the number of indicator functions on $\Omega$ is $2^n$. (This is a special case of a previous exercise. Which one?)
1.15 DO Use Problem 1.11 to prove: $|\calP(A)|=2^{|A|}$. Hint. Bijection between the powerset and the set of indicator functions.
1.16 DO Let $A,B\subseteq\Omega$. Prove: (a) $f_{A\cap B}=f_A\cdot f_B$. (b) $f_{\Abar} = 1 - f_A.$
1.17 DO Prove: $f_{A\cup B} = f_A+f_B - f_A\cdot f_B.$ (Use the preceding exercise.)
1.18 DEF $\zzz$ denotes the set of integers (positive and negative whole numbers and zero). Let $a,b\in \zzz$. We say that $a$ divides $b$ if $(\exists x\in\zzz)(ax=b)$. We also describe the same circumstance by saying that $a$ is a divisor of $b$; and $b$ is a multiple of $a$. Examples: $3\mid 21$ (proof: take $x=7$), $-3\mid 21$ (proof: take $x=-7$), $3\mid -21$ (proof: take $x=-7$).
1.19 DO Prove: if $a\mid b$ then $a\mid -b$ and $-a\mid b$ and $-a\mid -b$. (In brief, $\pm a\mid \pm b$.)
1.20 DO Prove: if $a\mid b$ and $b\mid a$ then $b=\pm a$.
1.21 DO (a) Determine those integers $d$ which are
divisors of all integers, i.e., $(\forall z)(d\mid z)$.
(b) Determine those integers $h$ which are
divisible by all integers, i.e., $(\forall z)(z\mid h)$.
1.22 HW Let $a,b,d\in\zzz$. Prove: if $d\mid a$ and $d\mid b$ then $d\mid a+b$. State, what property of arithmetic is being used in your proof.
1.23 HW Let $f :\rrr\to\rrr$ be a real function. Give a properly quantified formula that defines the statement $\displaystyle{\lim_{x\to\infty} f(x) = 5}$.
1.24 DO Find all those integers $x$ for which $x\mid x-14$. Prove your answer.
1.25 DO Find all those integers $x$ for which $2x+3\mid 3x-1$. Prove your answer.
1.26 CH Let $\Omega$ be a set of $n\ge 1$ elements and let $A_1,\dots, A_m$ be subsets of $\Omega$ such that $|A_i|=n/2$ for all $i$ and $|A_i\cap A_j|\le n/5$ for all $i\neq j$. Prove: $m\le 6$.
1.27 CH Let $\Omega$ be a set of $n\ge 1$ elements and let $A_1,\dots, A_m$ be distinct subsets of $\Omega$ such that $|A_i\cap A_j|=1$ for all $i\neq j$. Prove: $m\le n$.