From: "Christian Meland" <christian.meland@pfi.no>
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