• Option I: Algebra Complex Analysis Real Analysis Topology
• Option III: Applied Analysis Linear Programming Numerical Analysis Probability

Department of Mathematics and Computer Science
Comprehensive Examination-Option I
Fall 2004

Algebra

1.

Suppose N is a normal subgroup of a group G. Prove:

a.

If M is also a normal subgroup of G, then MÇN is a normal subgroup of G.

b.

If [G:N]=n, then aⁿ Î N for each a Î G.

2.

An element a in a ring is idempotent if a²=a.

a.

Show that the set of all idempotent elements in a commutative ring is closed under multiplication.

b.

Find all idempotent elements in the ring \Z₆×\Z₁₂, where \Z_n is the ring of integers modulo n.

c.

Show that each division ring contains exactly two idempotent elements.

3.

Prove that each finite integral domain is a field; deduce that for each prime p, \Z_p is a field.

4.

Let V and W be vector spaces over a field, and suppose T:V® W is a linear transformation. Prove:

a.

N(T)={x Î V | T(x)=0} is a subspace of V.

b.

T is one-to-one if and only if N(T)={0}.

c.

If for each linearly independent subset S of V, T(S) is a linearly independent subset of W, then T is one-to-one.

Complex Analysis

1.

Find a linear fractional transformation that maps

·

4 to 0,

·

1 to -1, and

·

the circle |z-2|=2 onto the line y=-x.

2.

Find all Laurent expansions for

f(z)=  4 z2+2z-3

centered at z₀=1 and discuss their regions of convergence.

3.

a. For each of the functions

f(z)=  1 sinz        g(z)=sin æ è  1 z ö ø        h(z)=  sinz z

determine whether z=0 is a removable singularity, a pole, or an essential singularity.

b.

Suppose C is the unit circle oriented clockwise; use residues to compute

ó (ç) õ C  sin æ è  1 z ö ø (z2+1) dz.

4.

In each part below determine whether there exists an entire function f satisfying the stated conditions. If so, give an example; if not, explain why.

a.

|f(0)|=1, and |f(z)|=1/2 for each z Î \C such that |z|=1.

b.

f(0)=1, f(1)=0, and |f(z)| £ 1 for each z Î \C.

Real Analysis

1.

Let f,g:[a,b]®\R be continuous on [a,b] with a < b, and assume that

inf {f(x) | x Î [a,b]}= inf {g(x) | x Î [a,b]}.

Prove that there exists x₀ Î [a,b] such that f(x₀)=g(x₀).

2.

a. Prove that each convergent sequence in a normed space is a Cauchy sequence.

b.

Prove that each Cauchy sequence in a normed space is bounded.

3.

Let

å n ³ 0  (-1)nan

converge with sum S, and suppose 0 < a_n+1 £ a_n "n ³ 0. Prove

ê ê S- N å n=0  (-1)nan ê ê £ aN+1

for each N=0,1,2,3,¼ .

4.

Let f be Riemann integrable on [0,1] and define F:[0,1]®\R as follows.

F(x)= ó õ x 0  f(t) dt

a.

Use properties of integrals to prove that F is uniformly continuous on [0,1].

b.

Provide an example which illustrates that F may not be differentiable on [0,1].

Topology

1.

Suppose that X is a Hausdorff topological space. Prove:

a.

If A is a subspace of X, then A is Hausdorff.

b.

If Y is a topological space and there exists an open bijection f:X® Y, then Y is Hausdorff.

2.

Let f,g:X®\R be continuous functions on a topological space X. Prove that if A={x Î X | f(x)=g(x)} is dense in X, then f(x)=g(x) "x Î X.

3.

Prove that each open connected subset of \Rⁿ is path-connected.

4.

Give an example of two homeomorphic metric spaces X and Y with X complete and Y not complete. Justify your answer.

Department of Mathematics and Computer Science
Comprehensive Examination-Option III
Fall 2004

Applied Analysis

1.

Find two linearly independent series solutions about x=0 of the equation

4xy¢¢+2y¢-y=0.

2.

Find the general solution of X¢(t)=AX(t) where

A= æ ç ç ç ç ç ç ç è 2 0 -1 0 0 2 1 0 0 0 2 0 0 0 -1 2 ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø .

3.

Let f,g:[a,b]®\R be continuous on [a,b] with a < b, and assume that

inf {f(x) | x Î [a,b]}= inf {g(x) | x Î [a,b]}.

Prove that there exists x₀ Î [a,b] such that f(x₀)=g(x₀).

4.

a. Prove that each convergent sequence in a normed space is a Cauchy sequence.

b.

Prove that each Cauchy sequence in a normed space is bounded.

Linear Programming

1.

Powerco has three electric power plants that supply the needs of four cities. The numbers of kilowatt-hours (kwh) of electricity that can be supplied by power plants 1, 2, and 3 are 35 million, 50 million, and 40 million, respectively. The peak power demands in the cities, which occur at the same time of day (2 pm), are as follows (in kwh). City 1: 45 million; City 2: 20 million; City 3: 30 million; City 4: 30 million. The costs (in dollars) of sending one million kwh of electricity from each plant to each city depend on the distance the electricity must travel. These costs are shown in the following table.

To:	City 1	City 2	City 3	City 4
From:
Plant 1	8	6	10	9
Plant 2	9	12	13	7
Plant 3	14	9	16	5

Powerco wants to determine how much electricity to send from each plant to each city to minimize the total cost of meeting each city's peak power demand.

a.

Use the northwest corner method to obtain an initial feasible solution to Powerco's transportation problem.

b.

Starting with the initial feasible solution from part a. find an optimal solution to Powerco's problem.

c.

If the cost of sending one million kwh of electricity from Plant 1 to City 1 changes from $8 to $12, does the optimal solution found in part a. change? Explain.

2.

a. State the Complementary Slackness Theorem for a pair of linear programming

problems of the following form.

P. minimize ctx subject to Ax ³ b x ³ 0              Q. maximize bty subject to Aty £ c y ³ 0

where A is an m×n matrix.

b.

Use the Complementary Slackness Theorem to prove or disprove that (5,0,1) is an optimal solution of the following linear programming problem.

minimize   2x1+3x2+4x3 subject to  x1- x2+3x3 ³ 5 2x1+ x2- x3 ³ 4  x1+2x2+ x3 ³ 6 xj ³ 0,    j=1,2,3

3.

Let problems P and Q be as follows:

P. minimize ctx subject to Ax ³ b x ³ 0        Q. maximize bty subject to Aty £ c y ³ 0

where A is an m×n matrix.

a.

Prove: If [`(x)] and [`(y)] are feasible vectors for P and Q, respectively, then c^t[`(x)] ³ b<sup>t</sup>[`(y)].

b.

Consider the following problem.

Q: maximize b1y1-4y2+ y3 subject to    y1- y2+ y3 £ 1 -2y1+ y2+2y3 £ 1 yj ³ 0,    j=1,2,3

For what values of b₁ is the objective function of this problem unbounded above over the feasible region? For these values of b₁, what conclusion can you draw about the dual of problem Q?

Justify your answers.

4.

Consider the following problem.

P: minimize z=6x1+2x2+x3-3x4 subject to       x1-2x2- x3+3x4 £ 2 2x1-4x2- x3+3x4 =3 3x1-6x2+ x3+6x4 =6 xj ³ 0,    j=1,2,3,4

a.

Solve problem P using the two phase simplex method.

b.

Let c₂ be the coefficient of x₂ in the objective function of problem P, and let b₁ be the number on the right side of the first constraint. Use sensitivity analysis to determine:

i.) the range of values for q such that replacing c₂=2 by c₂=2+q does not

change the optimal basis found in part a.

ii.) the range of values for r such that replacing b₁=2 by b₁=2+r does not

change the optimal basis found in part a.

Numerical Analysis

1.

a. Prove that the equation e^x=2+x+[(x²)/2] has exactly one real solution.

b.

Let a be the solution in part a. Find an approximation b of a such that

|a-b| < 10^-6.

c.

Prove that the inequality in b. holds.

2.

Recall that the truncation errors ET_n and ES_m in approximating ò_a^bf using the (extended) trapezoidal rule with n subintervals and Simpson's rule with m subintervals are given by the following formulas.

ETn =-  (b-a)3 12n2 f¢¢(xT),   some xT Î (a,b),   and ESm =-  (b-a)5 180m4 fiv(xS),   some xS Î (a,b)

Suppose one approximates ò_p/6^p/3sinq dq using the trapezoidal rule and Simpson's rule. Show that Simpson's rule with m=6 yields a more accurate approximation of this integral than the trapezoidal rule with n=100; i.e., for this function |ES₆| < |ET₁₀₀|.

3.

Let A be a n×n matrix of the following form.

A= æ ç ç ç ç ç ç ç ç ç ç ç ç ç ç ç è a1 d1 0 0 0 0 ¼ 0 b1 a2 d2 0 0 0 ¼ 0 c1 b2 a3 d3 0 0 ¼ 0 0 c2 b3 a4 d4 0 ¼ 0 : ··· : 0 ¼ ¼ cn-4 bn-3 an-2 dn-2 0 0 ¼ ¼ 0 cn-3 bn-2 an-1 dn-1 0 ¼ ¼ 0 0 cn-2 bn-1 an ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø

a.

Construct an algorithm which generates the upper-triangular matrix obtained by applying Gaussian elimination to A. That is, show how to construct the upper-triangular matrix U so that A=LU where L is lower-triangular and U has only two significant diagonals; i.e.,

U= æ ç ç ç ç ç ç ç ç ç ç ç è u1 v1 0 0 ¼ 0 0 u2 v2 0 ¼ 0 0 0 u3 v3 ¼ 0 : ··· : 0 0 0 ¼ un-1 vn-1 0 0 0 ¼ 0 un ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø .

You may assume that pivoting is unnecessary. Exploit the sparsity pattern by writing everything in terms of the given vectors. (Do not use double subscripts.)

b.

Determine the number of additions/subtractions, multiplications, and divisions in your algorithm.

4.

Let

A= æ ç ç ç ç ç è 3 -1 0 0 -5 2 0 1 4 ö ÷ ÷ ÷ ÷ ÷ ø .

Suppose Gauss-Seidel is used to solve the linear system Ax=b.

a.

Construct the matrix T_GS such that Gauss-Seidel may be described as

x(i+1)=TGS x(i)+c,    i=0,1,2,3,¼ .

b.

Determine the minimum k, (0 < k < 1) where it is guaranteed that

||x-x(i+1)||¥ £ k||x-x(i)||¥,

and justify your answer.

Probability

1.

According to a survey conducted by the American Bar Association 1 in every 410 Americans is a lawyer, but 1 in every 64 residents of Washington, D.C. is a lawyer.

a.

If you select a random sample of 1500 Americans, what is the approximate probability that the sample contains at least one lawyer?

b.

If you select the same size random sample from among the residents of Washington, D.C., what is the approximate probability that the sample contains at least thirty lawyers?

c.

What is the expected number of lawyers in America from the sample of 1500 persons? What is the expected number of lawyers in Washington, D.C. from the sample of 1500 persons?

d.

If you stand on a Washington, D.C. street corner and interview the first 1000 persons who walk by, and thirty say that they are lawyers, does this suggest that the frequency of lawyers passing the corner exceeds the density within the city? Justify and explain your answer.

2.

Suppose the joint probability mass function (p.m.f.) of X and Y is given by the following table.

\BeginTable \BeginFormat | l | c | c | c | c | \EndFormat " " \use4 x " "y | 0 " 1 " 2 " 3 " +20 _ " 1 | 1/8 " 1/16 " 3/16 " 1/8 " " 2 | 1/16 " 1/16 " 1/8 " 1/4 " \EndTable

a.

Determine the marginal p.m.f. of X, f_X(x), and the marginal p.m.f. of Y, f_Y(y).

Sketch these p.m.f.s and describe their shapes.

b.

Calculate E[X], E[Y], and E[X | Y=y], for y=1,2.

c.

Calculate E[E[X | Y]]. Compare E[X] and E[E[X | Y]].

d.

Calculate Var(X) and Var(Y).

3.

A test correctly identifies a disease D with probability 0.95 and wrongly diagnoses D with probability 0.01. From past experience it is known that the disease occurs in a targeted population with frequency 0.2%. An individual is chosen at random from this population and is given the test. Calculate the probability that

a.

the test is positive, P(+).

b.

the individual actually suffers from the disease D if the test turns out to be positive, P(D|+).

c.

the individual actually does not suffer from the disease D^c if the test turns out to be negative, P(D^c|+).

4.

If X₁,X₂ are independent Gamma(a_i,1), i=1,2, where

f(xi)=  1 G(ai) xiai-1e-xi   0 < xi < ¥

determine the following.

a.

Determine the joint density of X₁ and X₂, f(x₁,x₂).

b.

Let

Y1=  X1 X1+X2

and let

Y2=X1+X2.

Determine the joint density of Y₁ and Y₂, f(y₁,y₂).

c.

Calculate the marginal densities of Y₁, Y₂, f_Y1(y₁), and f_Y2(y₂).

d.

Is Y₂ independent of Y₁?

(Note: The distribution of Y₁ is called the Beta distribution.)