Adjacency Matrix to Coordinate Transformations

[lightfire]

I've come up with a curious two-part question while working on a map program:

What is the minimum number of points necessary in order to transform an NxN adjacency matrix into a coordinate matrix in terms of N given Euclidean space?

As this question relates to map-making, where I don't believe the parallel-postulate holds, what is the minimum number of point necessary for this transformation on the Earth's space?

 

[Stephen Tashi]

to transform an NxN adjacency matrix into a coordinate matrix in terms of N given Euclidean space?

You should explain what you mean by "a coordinate matrix in terms of N". Give an example of "a coordinate matrix".

 

[lightfire]

A coordinate matrix is just a set of coordinates of N vertices or nodes.

So the points (1,2), (3,4), (5,6) are stored as:

\begin{pmatrix} 1 & 2\\ 3 & 4\\ 5 & 6 \end{pmatrix}

It's adjacency matrix is roughly:

\begin{pmatrix} 0 & 2.82 & 5.66\\ 2.82 & 0 & 2.82\\ 5.66 & 2.82 & 0 \end{pmatrix}

\begin{pmatrix} 0 & (8^1/2) & (32^1/2)\\ (8^1/2) & 0 & (8^1/2) \\ (32^1/2) & (8^1/2) & 0 \end{pmatrix}

 

[Stephen Tashi]

In graph theory, the entries of "adjacency" matrix are only 0's or 1's. I think your version of an adjacency matrix gives the distance between each pair of points. So the question is how to assign the points (x,y) coordinates that are consistent with the distances. You hint that the distances might not be Euclidean distances, but could be something like distances over the surface of spheroid. I suppose the (x,y) coordinates might not be coordinates on a plane, but might be some other system. We need to state the question precisely.

If we are dealing with Euclidean distances on a plane, then each given distance between a pair of points gives an equation. If we arbitrarily assign point 1 to have coordinates (0,0) then the question is whether the simultaneous equations can be solved. Since you mention a "transformation" perhaps your question is more complicated that this.

 

[lightfire]

In graph theory, the entries of "adjacency" matrix are only 0's or 1's. I think your version of an adjacency matrix gives the distance between each pair of points. So the question is how to assign the points (x,y) coordinates that are consistent with the distances. You hint that the distances might not be Euclidean distances, but could be something like distances over the surface of spheroid. I suppose the (x,y) coordinates might not be coordinates on a plane, but might be some other system. We need to state the question precisely.

If we are dealing with Euclidean distances on a plane, then each given distance between a pair of points gives an equation. If we arbitrarily assign point 1 to have coordinates (0,0) then the question is whether the simultaneous equations can be solved. Since you mention a "transformation" perhaps your question is more complicated that this.

I'm technically talking about a "weighted" adjacency matrix that can be used to represent distances. I have figured out the problem for Euclidean space in two and three dimensions using the distance formula comparisons, as you suggested.

\[d_{12}^{2}=(y_{1}-y{2})^2 + (x_{1}-x_{2})^2\]

\[d_{14}^{2}=(y_{1}-y{4})^2 + (x_{1}-x_{4})^2\]

\[d_{34}^{2}=(y_{3}-y{4})^2 + (x_{3}-x_{4})^2\]

\[d_{45}^{2}=(y_{4}-y{5})^2 + (x_{4}-x_{5})^2\]

\[d_{35}^{2}=(y_{3}-y{5})^2 + (x_{3}-x_{5})^2\]

\[d_{25}^{2}=(y_{2}-y{5})^2 + (x_{2}-x_{5})^2\]

Carry this out to its conclusion reveals that the number of determined equations that are instantiations of the distance formula given N points is
\[Number Of Equations=\frac{n(n-1)}{2}\]

Whereas the number of unknowns is:
\[Number of Unknowns = 2n \]

This is because the only unknowns are the coordinates(assume two-dimensions coordinates)

So, the answer is 5 points for 2D and 7 for 3D in order to be able to specifically convert relative distances to coordinates.