COL726 (Numerical Algorithms) Take-home for Minor II
March 25, 2017
Note: You may submit by 23:55 on 2.4.2017 electronically through the course Moodle page.
Please include a declaration of originality. Please submit jointly if you collaborate on the
entire problem with somebody else and please give credits if you obtain any part of your
solutions from somebody else or some other source.
Consider the problem of drawing a map of n cities given the pair-wise distances between
them.
More formally, we have n cities, an array D of the n2 distances, Dij = dist(cityi , cityj )
(Dij = Dji with ordinary luck!), and we want to know if there are points Pi in the plane such
that dist(Pi , Pj ) = Dij . We may also wish to find an appropriate “approximate solution”
if such Pi ’s do not exist (perhaps by fudging a little).
Please do not despair. The situation is not that bad! Just read on...
Let us first see if there are such points in Rn . If there are, we may shift the lot so that
the center of mass is at origin. ThenPthe distances can be related to the inner products
in the following way. Assuming that i Pi = 0, you can show that the inner products are
Pit Pj = Aij , where
n n
1X 2 1 X 2 1 2
Si = Dij , T = Dij , Aij = − Dij − Si − Sj + T
n n2 2
j=1 i,j=1
Thus, if such Pi ∈ Rn can be found whose inner products are Aij , we can readily compute
that dist(Pi , Pj ) = Dij . Also if X is the matrix with the Pi ’s as columns, the problem
reduces to one of finding if there is a X such that A = X t X. Clearly, in such a case, A must
be symmetric and positive definite, since if v is any vector in Rn then v t Av = (Xv)t (Xv) ≥
0. Is this related to triangular inequality?
So, now our (actually your) problem is as follows:
Given a symmetric matrix A, (a) how do we decide if there are n-dimensional vectors whose
inner products are the entries of A? (b) How do we know if they lie in a plane? (c) How
do we find them if they exist? and (d) fudge if they do not?
Here are a few hints: (a) positive definite symmetric matrices have an orthonormal basis
of real eigenvectors and corresponding positive eigenvalues; (you may show this for A by
considering the SVD of X) (b) if you want the points to lie on a plane, you want X to
be a 2 × n matrix; (c) same as (a); (d) think of a galaxy of stars in R3 . Some galaxies
(like ours!), while contained in R3 , are pretty close to being planar. Least-squares appears
to be a good choice for projection on to a plane which will overall be close to preserving
inter-point distances. Of-course you will have to find the “residual error” in such a case.
So now you can write out the formal solutions to (a), (b), (c) and (d) (not so hard after
all!).
You can also throw some more light on the problem
1. Verify the relationship between [Dij ] and [Aij ]. Can you think of a geometric inter-
pretation?
2. Can you relate the necessary condition that A is positive definite to triangular in-
equality?
3. If the solution exists then it is normalized for translation. We have achieved this by
putting the center of mass at origin. Can we normalize for rotation and reflection?
COL726: Take-home question for Minor II 2
Will it help to show that X exists iff an upper-triangular X exists (with +ve diagonal
entries) such that X t X = A? Can we then say that if the solution exists then it is
essentially unique (modulo rotation and translation which we can normalize). You
may wish to read up about Given’s rotations.
4. What does it mean if some eigenvalues of A are negative?
5. What if the matrix D is not symmetric (may be different measurements have made
some Dij 6= Dji ). Can we still approximate? Think in terms of SVD.
If instead of the pairwise distances Dij s we are given the unit vectors tij s (pointing
towards j from i). Can we still plot the cities? What would be a good algorithm for finding
an approximate solution if the tij s have errors?
