# The computational cost of the adjacency-based Euclidean distance matrix

I know that the computational cost of the adjacency matrix is n*n. Namely, this graph-theoretical structure contains value 0 or 1 for every pair of vertices if there the edge exists or not, so it needs n^2 space. I am interesting in the computational cost of the adjacency-based distance matrix in which each entry is the Euclidean distance between the rows of the adjacency matrix. This matrix is a pseudo-distance matrix since it can contain zero in off-diagonal places if two adjacency rows are identical. For instance, we have the graph with five nodes:

whose adjacency matrix has the form:

  1 2 3 4 5
1 0 1 0 0 0
2 1 0 1 0 1
3 0 1 0 1 0
4 0 0 1 0 0
5 0 1 0 0 0


Then we are computing the distance matrix of the Euclidean distances between the rows of the above adjacency matrix. This distance matrix has the form:

  1    2    3    4    5
1 0.00 2.00 1.00 1.41 0.00
2 2.00 0.00 2.24 1.41 2.00
3 1.00 2.24 0.00 1.73 1.00
4 1.41 1.41 1.73 0.00 1.41
5 0.00 2.00 1.00 1.41 0.00


I am interesting in the computational cost of the distance matrix computation and in the computational cost of overall process.

• An adjacency matrix will only give you information about relations of vertices, you cannot infer a geometric embedding from it (see here for more information). So without more information there is no way of determining such a matrix. – KVN Jan 28 at 17:28