From: "Christian Meland"
Newsgroups: sci.math.num-analysis
Subject: Funny/easy(?) matrix question.
Date: 11 Nov 1997 12:03:42 GMT
I have n points, and know (have an estimate of) the distance between all
n(n-1)/2 pairs of points. Now I want to compute one possible set of
coordinates for the (n) points. For n points, I need at most n-1 dimensions
(think like this: with two points, I have one distance. Then I need only
2-1 dimensions (a line) to represent the two points. With three points, I
need 2 dimensions to tkae care of the three known distances etc.)
To keep things simple, I choose the coordinate-system so that the first
point is in the origin, the second point is on the first axis, the third
point is in the first plane etc. Then, for n=4, the coordinates would be on
the form
Point x y z
I 0 0 0
II a 0 0
III b c 0
IV d e f
Now, I let the (symmetric) distance matrix look like this:
I II III IV
I 0 ... ... ...
II A 0 ... ...
III B C 0 ...
IV D E F 0
With some algebra I get the following set of equations:
a^2 =A^2
b^2+c^2 =B^2
d^2+e^2+f^2 =D^2
ab =(A^2+B^2-C^2)/2
ad =(A^2+D^2-E^2)/2
bd+ce =(B^2+D^2-F^2)/2
which again can be written as
| a 0 0 |
m= | b c 0 |
| d e f |
| A^2 ... ... |
m*m' = | (A^2+B^2-C^2)/2 B^2 ... |
| (A^2+D^2-E^2)/2 (B^2+D^2-F^2)/2 D^2 |
(symmetric, m'=transpose(m))
m*m' is known (capital letters is the known distances). How can I decompose
this to get m, which shall be lower triagonal (zeroes above diagonal), and
be such that m*m' equals the above?
This may be simple, but I don't see it.
Thanks for any help.
Christian
--
Christian Meland
Research Scientist, PFI
Oslo, Norway
Phone +47 22566105 ext. 267, at home +47 22221067
==============================================================================
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Newsgroups: sci.math.num-analysis
Subject: Re: Funny/easy(?) matrix question.
Date: 11 Nov 1997 13:59:00 GMT
Christian Meland wrote......
snip snip
|> | a 0 0 |
|> m= | b c 0 |
|> | d e f |
|>
|> | A^2 ... ... |
|> m*m' = | (A^2+B^2-C^2)/2 B^2 ... |
|> | (A^2+D^2-E^2)/2 (B^2+D^2-F^2)/2 D^2 |
|>
|> (symmetric, m'=transpose(m))
|>
|> m*m' is known (capital letters is the known distances). How can I decompose
|> this to get m, which shall be lower triagonal (zeroes above diagonal), and
|> be such that m*m' equals the above?
|>
|> This may be simple, but I don't see it.
m is nothing than the cholesky-factor of your given m*m'.
software for its computation is on the net almost everywhere, e.g.
in
netlib/toms (http://www.netlib.no should be easily accesible for you)
hope this helps
peter