Sign In Sign-Up

Welcome!

Close

Would you like to make this site your homepage? It's fast and easy...

Yes, Please make this my home page!

No Thanks

  Don't show this to me again.

Close

Published in MATCH 32 (1995) 193-203

AN EQUIVALENCE RELATION BETWEEN DISTANCE AND COORDINATE MATRICES

Milan Kunz

ABSTRACT

It is shown that distance matrices D (where d_ij is squared graph distance between vertices i and j) are equivalent with quadratic forms CC^T of coordinate matrices C, (which elements c are coordinates of vertices i on axes j) in the differences -2SCC^TS^T = SDS^T (where S^T is the transposed incidence matrix of the oriented complete graph K(m).

Topological distance matrices were used extensively, till Trinajstic with coworkers formulated geometrical distance matrices [1], where elements counting the number of arcs between vertices _ij were replaced by straight geometrical distances of atoms in molecules, corresponding to the graph.

It was found, that distance matrices of trees form a part of the inverse of their incidence matrices S, SDS^T = -2I [2, 3]. In this note, a relation between coordinate and distance matrices will be shown.

A possibility, how to define positions of points in the space, is to give their coordinates in a system of orthogonal axes. Such a list forms a coordinate matrix C of type m*n, which elements c_ij are coordinates of m points i (vertices) in n axes. The quadratic forms CC^T of coordinate matrices have on the diagonal squared Euclidean distances of each vertex from the center of the coordinate a system. Off-diagonal elements are quadratic products of Euclidean distances of vertices i and j from the center. Thus, the structure of these matrices is different from distance matrices D, where the diagonal elements are zeroes. Newertheless, both kind of matrices are equivalent, because their products with incidence matrices S of oriented complete graphs K(m) (s_ij = -1, if the arc i goes from the vertex j, s_ij = 1, if the arc i goes to the vertex j, s_ij = 0 otherwise) are identical to a constant -2SCC^TS^T = SDS^T.

This relation is explained by the formal construction of a distance matrix from the coordinate one. It can be shown simply on an example of coordinates of a linear chain with 4 vertices, spanned on a axis L(l) and winded by two ways on the unit cube L(3) and L(4), respectively. Distances between vertices of the linear chain L(4), spanned on the 4 dimensional cube diagonally, cross its 2 dimensional faces and are longer.

L(1) L(3) L(4)

Multiplying the quadratic form CC^T (square m x m matrix) with

S from the left S^T and by S^T from the right, where S^T is a m x m(m-1)/2 matrix, here

we get m(m-1)/2 x m(m-1)/2 matrices which have on diagonals L(1):(1, 4, 1, 9, 4, 1), L(3): (1, 2, 1, 3, 2, 1) and L(4): (2, 2, 2, 2, 2, 2), respectively. In all cases these numbers are squares of Euclidean distances d_ij in corresponding spaces [4].

These diagonals can be transformed into distance matrices by the other quadratic form of the incidence matrix S^TS, if we multiply inside of this product by the diagonal matrices which elements are distances d²_ij : S^T (diagonal d²_ij)S = Q - D, where Q is the diagonal matrix of row or colum sums of suares of Euclidean distances of the vertex j to all other vertices. Since all off- diagonal elements are always negative, the result does not depend on orientations of arcs. Otherwise, we find at first the product (diagonal d_ij)S and then its quadratic form S^T(diagonal d_ij)(diagonal d_ij)S. In the given examples we get

L(1) L(3) L(4)

The quadratic form SS^T itself has on the diagonal 2. These elements count the number of vertices adjacent to each arc. But SS^T is identical with SIS^T or SI²S^T, where I is the unit diagonal matrix, these numbers can be interpreted as squared distances in the product SCC^TS^T of chain L(4). Off-diagonal elements form an ajacency matrix of the corresponding bond graph and determine orientations of adjacent arcs.

A symmetric matrix M inside the quadratic forms S(M)S^T or S^T(M)S transforms the output of the whole form by weighting. In our cases these weights were distances d_ij. They can be adjacencies a_ij, too. Then S^T(diagonal a_ij)S is known as the Laplace-Kirchhoff matrix (V-A), where V is a diagonal matrix of vertex degrees vi =  a_ij and A is the adjacency matrix.

Using the unit diagonal weighting matrix of the dimension m(m-1)/2, the quadratic form S^T(*)S has on the diagonal of the length n a sum of squares of distances d_ij or adjacencies a_ij. If the quadratic form SS^T is weighted by CC^T, true weights appear, and their double, if it is weighted by D or A, because each weight appears twice as _ij and ji elements in the distance ajacency matrices.

At topological graphs, if d_ij = 1, then a_ij = 1, if d_ij >1, then a_ij = 0. This relation between distances and adjacencies can be wieved as a limit of negative moments k of distances a_ij = lim 1/d_ij2. This is true for matrices of graphs without multiple arcs.

Another simple example is a unit square with the center. It can be placed arbitrary onto the plane. Lets be C(A) and C(B) two possible coordinate matrices of its corners and its center

The distance matrix D of these five points is in both cases identical and does not depend on connectivity of the points

The structure of the product SDS^T was already shown [3] to be a difference of distances. At the product SCC^TS^T, it is sufficient to analyze, what elements of SC are. They are differences of coordinates corresponding to each arc _ij. Each arc is weighted differently in each column according its angle to the corresponding axis.

Klein and Randic [5] introduced recently the notion of resistance distances induced by electrical forces in networks with resistances and capacities. The square graph C(4) distances are changed into induced distances as follows

This change can be explained as if electrical forces squeezed the graph from the original planar form into the

deformed tetrahedron. The corresponding change of coordinates computed by operation SCC^TS^T is e. g.

Matrices are known as operators acting on vectors. Therefore, the incidence matrices S of complete graph graphs K are operators, too. Vectors can have matrix form M. Matrix multiplications from the left and from the right have different effect. To SM and MS products, their quadratic forms exist SMM^TS^T and S^TM^TMS, respectively. Since these forms contain all elements twice, once as sums on the diagonal and once as off- diagonal elements, they can be split into matrices of diagonal and off-diagonal elements. Larger diagonal matrices are compacted by the operation S^T(*)S, into matrices (Q-D) or (V-A) respectively. Off-diagonal elements, put inside the operator S(*)S^T, appear back on the diagonal. Both operators form a loop. It is not easy to say, what is inside and what is outside.

At oriented graphs with simple arcs, adjacencies and distances are inverse elements. It was shown already at trees by inversing their SS^T matrices [6] or by generalized inversing their S^TS matrices [3].

When the graph theory was applied on chemical problems, new topological indices were introduced empirically many times, which were not consistent with another algebraic properties of graphs.

By embedding of molecules into the three dimensional space, topological distances are replaced by geometrical ones, which are squares of Euclidean distances as topological distances are. Because graphs are isomorphic without regard on their shape, this dimensionality is a secondary one [7].

As adjacencies a_ij, negative infinite moments of distances d_ij can be used at graphs without multiple bonds. Accepting chemical experience, that at multiple bonds distances are shorter, we find from correlation of actual distances between carbon atoms connected with simple, double and triple bonds, 1.54, 1.33 and 1.20, respectively as the effective moment k relating distances to multiplicities about -4.40 (3 = (1.54/1.20)k, the relation is not strictly linear between double and triple bonds). Using this value for calculating adjacencies a induced by longer distances between atoms, we get as the distance increment in the adjacency matrix value 0.0472 for the distance 2 and 0.0079 for the distance 3, respectively. These values seem to be reasonable as the damping action of distance on forces between atoms.

The relation between distance and coordinate matrices together with the notion of resistance distances could be important especially in crystallography [2].

1. B. Bogdanov, S. Nikolic and N. Trinajstic, On the three dimensional Wiener index, J. Math. Chem., 3, 399 (1989).

2. J. S. Rutherford, Acta. Cryst., B46, 289 (1990).

3. M. Kunz, J.Math.Chem.,9, 297 (1992).

4. M. Kunz, J. Chem Inf. Comput. Sci., 34, 957 (1994).

5. D. J. Klein, M. Randic, J. Math. Chem. 12, 81 (1993).

6. M. Kunz, Coll. Czech. Chem. Commun., 54, 2148 (1989).

7. M. Kunz, J. Math. Chem., 13, 145 (1993).