18.06, Fall 2004, Problem Set 5Due before 4PM on Wednesday October 20th, 2004, in the boxes in 2-106. No late homeworkwill be accepted. Don’t forget to write your name, recitation section and the names of studentsyou have collaborated with on the problem set. There is one box for each recitation section.For full credit, please be sure to show and explain your work. Exercises refer to the 3rd edition ofthe textbook.Reading assignment: Sections 4.1, 4.2 and 8.2.1. Consider the electrical network given below. The conductances of all edges are 1 except forthe four edges 3, 6 ,7 and 10 between the nodes 3, 4, 5 and 6 for which the conductance is 2.Assume there is a source of current between nodes 1 and 8 which injects one unit into node1 and takes 1 unit out of node 8 (this means that for the given network the net current intonode 1 must be -1 (total current into node 1 minus total current out of node 1) while thenet current into node 8 must be 1). Compute the resulting currents y1, · · · , y12. You can useMATLAB, but you should explain what you do.18y6y12y4y7 y8y12y10y11y9y5y343567y22. Show that, for any matrices A of size m × n and B of size n × p, we have r(AB) ≤ r(A) andr(AB) ≤ r(B). (You can rely on exercise 3 of problem set 3.)3. (a) Give the coordinates of n points in Rnsuch that the distances between any two of themare all the same. (The maximum number of such points in Rnis n + 1.)(b) Here you’ll show that the maximum number of points in Rnsuch that the distancesbetween any pair of them are all equal is at most n + 1 (This seems pretty obvious butone nevertheless needs to prove this fact.). Here is one way to prove this. Suppose youhave p points in Rnsuch that all inter-distances are 1 (after scaling). You can translatethe points so that one of them is at the origin. You can also assume they span the space;otherwise you can just decrease n. Now put the other p − 1 points as the column vectorsof a n × (p − 1) matrix Q. Let R = QTQ.1i. What is R? (Give all entries of R.)ii. What is the rank of R? Explain how you obtain it. (There are many ways ofcomputing the rank; here computing dim(N (R)) might be easiest.)iii. How can you now deduce that p − 1 ≤ n? Justify.4. In this subproblem, you will construct 50 points w1, w2, · · · , w50in a 30-dimensional subspaceof R50such that the distances between any of them are all approximately the same usingMATLAB (from the previous exercise you know that achieving precisely the same distancefor all pairs of points is impossible). Here are the steps you need to do for this. Just give aprintout of your MATLAB commands (the diary command is useful for this) and also givethe answer to subquestion 4f.(a) Generate 30 vectors v1, v2, · · · , v30in R50such that each component of each vector isindependently and normally distributed. You do not need to know what “independentlyand normally distributed” means; you should only know that the MATLAB commandrandn(m, n) (this is different from rand(m, n)) generates such an m × n matrix of inde-pendently and normally distributed entries.(b) Compute the projection matrix P corresponding to projecting onto the subspace Vspanned by the 30 vectors vi.(c) Take a 50 × 50 matrix B such that its columns correspond to 50 points in R50whosedistances are all the same. Now compute the projection of all these 50 points onto thesubspace V using the projection matrix P above. Let W be the 50 × 50 matrix suchthat the ith column is the projection wiof the ith column of B onto V .(d) Compute the rank of W .(e) Calculate the distances between wiand wjfor any i and j. Given the matrix W , thiscan be done easily by using the following MATLAB commands (the matrix D will havezeroes on the diagonal and the distance between wiand wjas entry (i, j)).> Q=W’*W;> d=diag(Q);> D=sqrt(d*ones(1,50)+ones(50,1)*d’-2*Q)(f) Give the ratio between the maximum and the minimum distance between two vectors wiand wj. By repeating the steps above (say 50 times), how small a ratio can you achieve?(A convenient way to repeat things in MATLAB is to use a for loop; type help for tosee how to use
View Full Document
Unlocking...