A. MillerM340Exam 2RULES: Do not discuss this exam with anyb ody except me. Iwill explain any definition or clarify the statement of any of theseproblems. My office is 403 Van Vleck, office hours MF 2:30-3:30and W 4:30-5:30, or you can make an appointment. You may useminimat to do any calculation. The exam is due in class on WedApril 11. Exam 2 Part II will be in class on Mon April 16.Linear differential equations.1. A mass m1is hung from a spring with spring constant k1is attached to arigid support. A mass m2is hung from a second spring with spring constantk2is attached to the mass m2. Let y1be the displacement from equilibriumof the mass m1and similarly y2the displacement from equilibrium of themass m2. Then using Hooke’s law and F = ma we get that:m1y001= −k1y1+ k2(y2− y1)m2y002= −k2(y2− y1).Let u1= y1, u2= y01, u3= y2, and u4= y02. Find a matrix A such thatU0= AU.2. Suppose k1= 21, k2= 15, m1= 7, m2= 3 in the appropriate units. Findthe general solution.3. Suppose y1(0) = 1, y2(0) = −1, and both have 0 initial velocities. Findthe solution. Find the displacements and velocities of the masses at timet = 2.1The method of least squares.4. Prove that if A is an n × m matrix of functions of t and B is an m × rmatrix of functions of t, thenddt(AB) = (ddtA)B + A(ddtB).5. Prove that if U and V are n × 1 vectors of functions of t, thenddthU, V i = hddtU, V i + hU,ddtV i.6. Let An×m, Bm×1be matrices of reals. Prove that∂∂xi||AX − B||2= 2hAX − B, Aeii.7. Prove that if X minimizes ||AX − B||2, then AT(AX − B) = 0.8. It is good surveying practice to make more observations than are strictlynecessary. For example, to determine the altitude of four points x1, x2, x3, x4,eight observations were taken:x1= 2.947x2= 1.735x3= −1.449x4= 1.321x1− x2= 1.204x1− x4= 1.631x2− x3= 3.186x3− x4= −2.778Note that all of these observations contain error and there do not exists anysolutions to all eight equations. Find A8×4and B8×1such that the mostlikely altitudes X minimize ||AX − B||2. Find X.2Linear programming or linear optimization.Let A be n × m, B be m × 1 and C = [c1, c2, . . . , cn] be 1 × n.(∗) Maximize z = c1x1+ c2x2+ · · · + cnxnsubject to the constraints:AX = B and X ≥ 0.X ≥ 0 means that x1≥ 0, x2≥ 0, . . ., and xn≥ 0. X is called feasible iffAX = B and X ≥ 0. A solution to (∗) is a vector X which is feasible and forwhich the value of z is as large as the value of z is for any feasible solution.X is called an extreme point iff there exists m1, m2, . . . , mksuch that X isthe unique solution of AX = B, xm1= 0, xm2= 0, . . . , and xmk= 0.9. Give an example of (∗) where there are no feasible solutions. Give anexample of (∗) where there are feasible solutions but no solutions. Givean example of (∗) where there are there infinitely many solutions. Give anexample of (∗) with an extreme point which is not feasible.10. Let X1and X2be solutions of AX = B, xm1= 0, xm2= 0, . . . , andxmk= 0. Define L[t] = X1+ t(X2− X1) where t is a scalar. Show that L[t]is a solution of AX = B, xm1= 0, xm2= 0, . . . , and xmk= 0 for every t.11. Suppose in addition to above that all coordinates of X1other thanm1, m2, . . . , mkare strictly positive. Show that there exists  > 0 such thatL[t] ≥ 0 for every t with − < t < .12. Define Z(t) = CL[t]. Prove that for some scalars p and q that Z(t) =pt + q. Prove that Z is maximized at t = 0 iff p = 0.13. Given the problem (∗) suppose X0is any solution which has the maximumnumber of zero coordinates as any other solution. Prove that X0is an extremepoint.3Graph theory.Suppose that A is an n × n matrix such that for any i, j we have thatai,j= 0 or ai,j= 1. The matrix A determines a graph GAon n verticesv1, v2, . . . , vnby the rule that viand vjare connected by an edge iff ai,j= 1.A path in a graph G is a s equence of vertices u1, u2, . . . , uksuch that for eachi = 1, . . . , k − 1 there is an edge in G which connects uiand ui+1. A graphG is connected iff any two vertices of G can be connected by a path.14. Give an example of a 4 × 4 matrix A as above whose graph is connected.Give an example of a 4 × 4 matrix A as above whose graph is not connected.15. Prove that if Am= [cij], then cijis the number of paths of length mconnecting vito vj.16. Prove that the graph associated to such an n × n matrix A is connectediff every entry of I + A + A2+ · · · + An−1is positive.Markov processes.In the Land of OZ there are three states for the weather: nic e, rain, andsnow. The weather follows the following rules:(a) There are never two nice days in a row.(b) When it rains or snows, half the time it the same the next day.(c) If the weather changes, the chances are equal for a change to eachof the two other types of weather.17. Draw a graph with vertices N, R, and S and label the edges with theappropriate probabilities.18. Find the 3 × 3 transition matrix A corresponding to this graph.19. Prove that the probability that it will rain exactly one week after it wasnice is the (1, 2) entry of the matrix A7. Find this probability.20. Find the probability that the weather will be nice, rain, or snow on arandom day in the Land of OZ.4Determinants, etc.The trace of an n × n matrix A is defined bytrace(A) = a11+ a22+ · · · + ann.The characteristic polynomial of a matrix A is defined by p(x) = det(xI −A).21. Prove that if A and B are similar, then trace(A) = trace(B).22. Prove that if A and B are similar, then det(A) = det(B).23. Prove or disprove: if two matrices A and B have the same characteristicpolynomial, then they are similar.24. Prove or disprove: if two matrices A and B are similar, then they havethe same characteristic