a. Prove: If Z is the center of a group G and G/Z is cyclic, then G is abelian.
b.
Let N be a normal subgroup of a group G.
Prove: If N is cyclic, then each subgroup of N is normal in G.
2.
Let G be a group and let H be the subgroup generated by {x-1y-1xy | x,y Î G}. Prove:
a.
H is normal in G.
b.
G/H is abelian.
3.
Let R be a division ring. Prove each of the following.
a.
The center of R is a field.
b.
If f:R® R¢ is a ring homomorphism, then f(R) is a division ring.
4.
Let l1,¼,ln be distinct eigenvalues of a linear operator T:V® V, and let
v1,¼,vn be corresponding eigenvectors. Prove that {v1,¼,vn} is a linearly
independent set.
Let (X,TX) be a topological space, Y be a set, and f:X® Y be a surjective function.
Prove that (Y,T) is a topological space where T={U Ì Y | f-1(U) Î TX}.
2.
Prove each of the following statements.
a.
If A is a connected subspace of a topological space X, then the closure [`A]
of A in X is connected.
b.
The image of a connected space under a continuous map is connected.
3.
Prove that a subspace of a compact Hausdorff space is compact if and only if it is closed.
4.
Prove:
a.
If U and V are disjoint open subsets of a topological space X, then [`U]ÇV=Æ.
b.
If A and B are disjoint closed subsets of a normal space X, then there exist open sets U and
V with A Ì U, B Ì V, and [`U]Ç[`V]=Æ.
In the following problems At is the transpose of matrix A and bt the transpose of vector b.
1.
Use linear programming duality theorems to prove Farkas' lemma; that is, prove that the system
Aty
£ 0
bty
> 0
has a solution if and only if the system
Ax
=b
x
³ 0
has no solution.
2.
Let P be the linear programming problem:
minimizectx
subjectto Ax £ b
dtx=e
x ³ 0
where
c=
æ ç ç ç
ç ç è
5
-3
0
ö ÷ ÷ ÷
÷ ÷ ø
, A=
æ ç ç
ç è
2
-1
4
1
1
2
ö ÷ ÷
÷ ø
, d =
æ ç ç ç
ç ç è
2
-1
1
ö ÷ ÷ ÷
÷ ÷ ø
, b=
æ ç ç
ç è
4
5
ö ÷ ÷
÷ ø
, and e=1.
a.
Using the two-phase simplex method find an optimal solution for problem P.
b.
Using the results of part a., and without re-applying the simplex method, find an optimal solution for the
dual of problem P.
c.
Suppose the objective function is replaced by gtx where g=c+d and
suppose the constraints are unchanged. Without re-applying the simplex method find an optimal solution for the dual of this
new problem. Explain how you obtain your solution.
3.
Consider the linear programming problem
minimize z=-x1-2x2
subjectto -2x1+ x2
£ 2
-x1+2x2
£ 7
x1
£ 3
x1,x2
³ 0
Using techniques of sensitivity analysis answer the following questions. Note that each of the following questions is
independent of its predecessors, in the sense that after each question that involves changing a number, the number should
be re-set to its original value before answering the next question.
a.
Suppose the right hand side of the second constraint is perturbed so that b2=7 is replaced by
b2¢=7+d. For what values of
d does the current optimal basis remain unchanged?
b.
Suppose the coefficient of x2 in the objective function is changed from -2 to +2. What are the
optimal values of the variables in this new problem?
c.
Suppose a new variable, x3, is added to the problem. If the coefficient of x3 in the objective
function is 2 and the coefficients of x3 in constraints 1, 2, and 3 are 4, -5, and 1, respectively, is x3 a
basic variable in the optimal solution of this new problem?
In solving parts a, b, and c use the fact that
æ ç ç ç ç
ç ç ç è
-2
1
1
0
0
2
-1
2
0
1
0
7
1
0
0
0
1
3
-1
-2
0
0
0
0
ö ÷ ÷ ÷ ÷
÷ ÷ ÷ ø
can be transformed by elementary row operations into
æ ç ç ç ç
ç ç ç è
0
1
0
1/2
1/2
5
1
0
0
0
1
3
0
0
1
-1/2
3/2
3
0
0
0
1
2
13
ö ÷ ÷ ÷ ÷
÷ ÷ ÷ ø
.
4.
Consider the linear programming problem:
P
ì í
î
max z
=ctx
Ax
£ b
x
³ 0
where x is n×1, c is n×1, A is m×n, b is m×1, and
ct is the transpose of c. Prove or disprove the following. (If you make use of any duality theorems in
your proof, prove them as well.)
a.
If the objective function of Problem P is unbounded above over the feasible region, then the dual of
Problem P is infeasible.
Prove that the equation x=g(x) has exactly two positive solutions.
b.
Consider approximating the larger solution, a, by applying fixed-point iteration on g(x). Determine
an interval [a,b] such that the iteration sequence will converge to a for any initial approximation
x0 Î [a,b]. Justify your answer.
2.
Suppose that f(5) is continuous. Show that
f¢¢¢(x0)=
-f(x0-2h)+2f(x0-h)-2f(x0+h)+f(x0+2h)
2h3
+O(h2).
3.
a. Let
A1=\matc6.3-9521.1-80.327.117.321.4-3.55.2-1.1 and A2=\matc0.400.370.120.71-0.63-1.202.001.002.20.
Consider applying Gaussian elimination to systems with the above matrices. Which of the two matrices would you
expect to cause more serious problems resulting from finite precision arithmetic when calculating x1 in the final step
of the back solve? Explain your choice.
b.
Consider using the quadratic formula with finite precision arithmetic to solve
x2+1230x-1=0.
Which of the two solutions would you expect to be approximated by a value that is only accurate to a limited number of
significant digits? Explain your choice.
Give an algebraic equivalent of the quadratic formula that could be used for this calculation to avoid the loss
of significance.
4.
a. Decompose
A=
æ ç ç ç ç
ç ç ç è
9
0
0
3
0
5
-1
1
0
-1
4
0
3
1
0
8
ö ÷ ÷ ÷ ÷
÷ ÷ ÷ ø
into LLt, where L is lower-triangular. Show your work.
b.
Let LLt be the Choleski decomposition of a positive definite matrix A. Show that A can also be
decomposed as L1DL1t, where D is a diagonal matrix and L1 is lower-triangular with (L1)ii=1 for
each i. Your description of L1 and D should be given in terms of L.
A salesperson has three clients in district A, five clients in district B, and seven clients in district C.
(a)
In how many ways can the salesperson select a group of clients so that in this group there are exactly two
clients from each district?
(b)
In how many ways can the salesperson select six clients from these districts?
(c)
If the salesperson randomly selects six clients from these districts, then what is the probability that at
least one of them is from district A?
(d)
If the salesperson randomly selects six clients from these districts and none of them is from district B,
then what is the probability that exactly two of them are from district A?
(e)
If the salesperson randomly selects six clients from these districts and exactly three of them are from
district B, then what is the probability that the salesperson selects the other three clients from district C?
2.
Suppose that calls to a computer help desk are independent. For each positive integer k let
Xk=
ì ï í
ï î
1
ifthekthcallisaboutanoperatingsystem,
0
otherwise.
Suppose that p is a positive number less than 1. Assume P[Xk=1]=p for each positive integer k.
(a)
Let K be the smallest positive integer k such that Xk=1.
(i) Find P[K=3].
(ii) Find E(K).
(b)
For each positive integer n let Yn=åk=1nXk.
(i) Find P[Y4=3].
(ii) Find the variance of Y4.
(iii) Find the approximate value of P[Y1000 < 1000p].
3.
Suppose that the survival time X, in years, of a patient has the probability density function
f(x)=
ì ï í
ï î
e-x
ifx ³ 0,
0
otherwise.
(a)
Find the probability that a patient survives more than one year.
(b)
If a patient survives less than one year, then what is the probability that the patient survives
less than half of a year?
(c)
Let V be the survival time of a patient and let W be the survival time of another patient. Suppose
that V and W are independent and have the same probability density function as X. Let Z be the minimum of
V and W.
(i) Find P[Z < 1].
(ii) Find the probability density function of Z.
(iii) Find P[Z > 1 | W > 2].
4.
Suppose that the cost X, in dollars, and the time Y, in minutes, of a job have the joint probability density
function
f(x,y)=
ì ï ï ï í
ï ï ï î
1
5000
if100 > x > y > 0,
0
otherwise.
(a)
Let g be the probability density function of X and let h be the probability density function of
Y. Find g and h.