187 – Midterm 2

March 24, 2010

Here is midterm 2. 

Solutions follow.

Read the rest of this entry »

Leave a Comment » | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

187 – Extra credit problems

March 24, 2010

These questions are due Friday, April 9 at the beginning of lecture.

  1. Let f:{\mathbb N}\times{\mathbb N}\to{\mathbb N} be the function given by \displaystyle f(x,y)=\frac{(x+y)(x+y+1)}2+y. Show that f is a bijection.
  2. Define g:{\mathbb N}\to{\mathbb N} by setting g(0)=0, g(1)=1 and, if n>1, then, letting p be the smallest prime such that p|n, then g(n)=2^p\times 3^{g(n/p)}. [Here, n/p=n\mathrel{\rm div} p.] Compute g(n) for n\le 15, and show that g is one-to-one. 
Advertisement

1 Comment | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

187 – Quiz 7

March 22, 2010

Here is quiz 7.

Solutions follow.

Read the rest of this entry »

Leave a Comment » | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

403/503 – Homework 5

March 15, 2010

This set is due Friday, March 26.

Read the rest of this entry »

16 Comments | 403/503: Linear Algebra II | Permalink
Posted by andrescaicedo

187 – Quizzes 5 and 6

March 14, 2010

Here is quiz 5 and here is quiz 6.

Problem 1 asks to show that the relation R defined as follows is antisymmetric: Given a set A, the relation R is defined on the subsets of A by setting x\mathrel{R}y for x,y\subseteq A, iff y\setminus x=\emptyset, where \setminus denotes set-theoretic difference of sets.

To show that R is antisymmetric, we need to show that whenever x,y\subseteq A are such that x\mathrel{R}y and y\mathrel{R}x, then x=y. Suppose x,y satisfy these assumptions. We need to show that they are equal as sets, i.e., that they have the same elements.

By definition, x\mathrel{R}y holds iff y\setminus x=\emptyset, and y\mathrel{R}x holds iff x\setminus y=\emptyset. Recall that if B,C are sets, then B\setminus C=\{a\in B\mid a\notin C\}. It follows that y\setminus x=\emptyset iff every element of y is also an element of x, and that x\setminus y=\emptyset iff every element of x is also an element of y. But these two facts together mean precisely that x and y have the same elements, i.e., that x=y, as we needed to show.

Problem 2(a) of quiz 6 asks to consider the relation R defined on {\mathbb N} by setting x\mathrel{R} y for x,y\in{\mathbb N}, iff 5|(2^x-2^y), and to show that R is an equivalence relation. This means that R is reflexive, symmetric, and transitive. Problem 2(a) of quiz 5 asks to show one of these properties. 

To show that R is reflexive, we need to show that for any x\in{\mathbb N}, we have that x\mathrel{R}x, i.e., that 5|(2^x-2^x). But 2^x-2^x=0 is certainly divisible by 5.

To show that R is symmetric, we need to show that for any x,y\in{\mathbb N}, if it is the case that x\mathrel{R}y, then it is also the case that y\mathrel{R}x. Suppose then that x\mathrel{R}y. This means that 5|(2^x-2^y), i.e., there is an integer a such that 5a=2^x-2^y. But then 2^y-2^x=-5a=5(-a), showing that also 5|(2^y-2^x), i.e., y\mathrel{R}x.

To show that R is transitive, we need to show that if x,y,z\in{\mathbb N} and both x\mathrel{R}y and y\mathrel{R}z hold, then also x\mathrel{R}z holds. But if x\mathrel{R}y and y\mathrel{R}z, then 5|(2^x-2^y) and 5|(2^y-2^z). But then it is certainly the case that 5|\bigl((2^x-2^y)+(2^y-2^z)\bigr). Since (2^x-2^y)+(2^y-2^z)=2^x-2^z, this proves that, indeed 5|(2^x-2^z), or x\mathrel{R}z, as we needed to show.

(If one feels the need to be somewhat more strict: That 5|(2^x-2^y) means that there is an integer a such that 5a=2^x-2^y. Similarly, 5|(2^y-2^z) means that there is an integer b such that 5b=2^y-2^z. But then 5(a+b)=5a+5b=(2^x-2^y)+(2^y-2^z)=2^x-2^z, showing that there is an integer c such that 5c=2^x-2^z, namely, we can take c=a+b.)

Problem 2(b) asks to find all natural numbers n such that 3\mathrel{R}n, where R is as defined for problem 2(a).

That 3\mathrel{R}n means exactly the same that 5|(2^3-2^n). Since 2^3=8 and an integer is a multiple of 5 iff it ends in 5 or 0, we need to find all natural numbers n such that 2^n ends in 8 or 3. Since 2^0=1 and 2^m is even for all  naturals m\ne 0, we actually need to find all natural numbers n such that 2^n ends in 8. For this, we only need to examine the last digit of the numbers 2^1,2^2,2^3,2^4,2^5,\dots, and we find that these last digits form the sequence 2,4,8,6,2,4,8,6,2,4,8,6,\dots which is periodic, repeating itself each 4. This means that the numbers n we are looking for are precisely 3,7,11,15,19,\dots, i.e., the natural numbers of the form 4k+3 with k\in{\mathbb N}.

3 Comments | 187: Discrete mathematics | Permalink
Posted by andrescaicedo

403/503 – Homework 4

March 5, 2010

This set is due Friday, March 12.

It is common in algebraic settings to build new structures by taking quotients of old ones. This occurs in topology (building quotient spaces), in abstract algebra when building field extensions, or in the homomorphism theorems. Here we explore quotients in vector spaces.

First we briefly consider an example from differential equations.

Let V be the space C^1({\mathbb R}) consisting of all continuously differentiable functions f:{\mathbb R}\to{\mathbb R} and let W be the space C({\mathbb R}) of all continuous functions g:{\mathbb R}\to{\mathbb R}. Let T:V\to W be the linear transformation Tf=f'-2f. 

Show that {\rm null}(T) is a real vector space of dimension 1, by showing that Tf=0 iff e^{-2x}f is a constant. This means, of course, that {\rm null}(T)={\rm span}(e^{2x})=\{\alpha e^{2x}\mid \alpha\in{\mathbb R}\}.

Show that e^x\in{\rm ran}(T) by finding a particular solution f_0 to the equation Tf=e^x. One way of doing this is by looking for such a function f_0 of the form ae^x for some constant a. Find the form of an arbitrary function f such that Tf=e^x by noting that if Tf=Tf_0 then T(f-f_0)=0.

More generally, show that T is surjective, by finding for any g\in C({\mathbb R}) the explicit form of the solutions f to the equation Tf=g. It may help you solve this equation if you first multiply both sides by e^{-2x}.

For another example, denote by {\mathbb R}^{3\times 3} the space of all 3\times 3 matrices with real entries. Define a map T:{\mathbb R}^{3\times 3}\to{\mathbb R}^3 by TA=A\begin{pmatrix}1\\1\\1\end{pmatrix}. Show explicitly that {\rm null}(T) has dimension 6 and that T is surjective.

Now we abstract certain features of these examples to a general setting:

Suppose {\mathbb F} is a field and T:V\to W is a linear transformation between two {\mathbb F}-vector spaces V and W. It is not necessary to assume that V or W are finite dimensional.

Let w\in{\rm ran}(T), and let v_0\in V be any preimage, i.e., Tv_0=w. Show that the set T^{-1}\{w\} of all preimages of w is precisely v_0+{\rm null}(T)=\{v_0+v\mid Tv=0\}.

Define a relation \sim in V by setting v_1\sim v_2 iff Tv_1=Tv_2. Show that \sim is an equivalence relation. Denote by {}[v] the equivalence class of the vector v\in V.

Let U=V/\sim be the quotient of V by \sim, i.e., the collection of equivalence classes of the relation \sim. We want to give U the structure of an {\mathbb F}-vector space. In order to do this, we define {}[v_1]+[v_2]=[v_1+v_2] and a[v]=[av] for all v_1,v_2,v\in V and a\in{\mathbb F}. Show that this is well-defined and satisfies the axioms of an {\mathbb F}-vector space. What is the usual name we give to the 0 vector of this space?

It is standard to denote V/\sim by V/{\rm null}(T). Define two functions \pi and \phi as follows: \pi:V\to V/{\rm null}(T) is given by \pi(v)=[v]. Also, \phi:V/{\rm null}(T)\to W is given by \phi([v])=Tv. Show that \phi is well-defined and that both \pi and \phi are linear. 

Show that T=\phi\pi, that \pi is a surjection, and that \phi is an isomorphism between V/{\rm null}(T) and {\rm ran}(T). In particular, any surjective image of a vector space V by a linear map can be identified with a quotient of V.

6 Comments | 403/503: Linear Algebra II | Permalink
Posted by andrescaicedo