Some minor stylistical changes against the published paper

Key words: Adjacency matrix A, distance matrix D, code matrix C, incidence matrix S, walk matrix W, eigenvalues.

Distance matrices D, where the element d_ij is the number of arcs between vertices i and j, were used in graph theory to characterize graphs¹. Rutherford² has found that at trees the distance matrix is a part of the left inverse of the incidence matrix S^T. This was interpreted as the orthogonality of (n -1) arcs of the trees^3,4.

An acyclic oriented graph is characterized in the space of vertices by its code (coordinate) matrix⁵C. The elements of C are c₁₁ = 1, for the root vertex, c_ij = 1, if the vertex j is on the path i to the vertex i, c_ij = 0 otherwise. The inverse matrix C^-1 is equal to the incidence matrix S (s = -1, if the arc i goes out the vertex j, s = 1, if the arc i goes into the vertex j, s = 0 otherwise) rooted by the element s₁₁ = 1.

There appears the question, how to interpret this relation, since the graph algebra rows with a single element s_ij = 1 are used sometimes (inconsistently) in the graph algebra for marking loops. In the vector algebra, a row (column) vector is an arc going from the origin of the coordinate system (zero vector, not given explicitly) to the point with coordinates determined by the row. Thus, either we got the matrix S with its first column deleted, since we delete the zero row from the code matrix, or we remove the singularity of the mx(m-1) code matrix with the zero row by adding the unit column J. This transform the matix S into mxm matrix, removes its singularity, but shifts the structure into the higher dimension. The element s₁₁ = 1 in C^-1matrix is then just the rooting arc-vector going from the additional vertex 0 to the vertex 1. The other rows are vectors parallel (isomorphic with) with corresponding arcs. An oriented loop leaves, according to the definition of an arc, an empty row.

Moreover, the code matrix C transforms the incidence matrix S_k of the complete oriented graph K, into the path₆ matrix W with n(n-1)/2 rows and (n-1) columns, which characterizes all pathes in the space of arcs. Matrices W are defined for trees as

W^TWSS^T= nI_{n- 1}. The quadratic form W^TW is the n- multiple of inverse SS^T. The rows of W represent paths between vertices of the respective tree. The columns correspond to arcs. Recall that the element w_ij = 1 if the arc j is incident with the path i and has the same orientation, w_ij = -1, if the arc j is incident with the path i and has the opposite orientation, w_ij = 0 otherwise. For unoriented trees were found walk matrices to obey the relation W^TWGG^T= nI_{n- 1}.

As an example of this transformation we present matrix C^Tof the 2-methylbutane rooted in position 2:

C^T

C^TS^T_k= W^T

Squared Euclidean distances appear in the corresponding distance matrix. For obtaining proper distances, we must either change moments of all elements of D, or the conformation of the chain. All angles between arcs are 180⁰.

Coordinate matrix C corresponding to the distance matrix D with topological distances is following (the rooting column J has been omitted):

The linear chain is winded consecutively onto the edges of the unit cube. The proper distances are, in fact, squared Euclidean (Hilbert) distances. All angles between arcs are 90⁰.

The third basic conformation of the linear chain L₅ is obtained by winding it onto the unit cube through diagonals of its 2-dimensional sides, or by finding a path in the topological conformation of the complete graph. (Our imagination ends here, unfortunately, with the regular tetrahedron.) The corresponding code matrix C (normalized for the unit distances) is:

All distances between vertices of the linear chain in this conformation are equal. It is equivalent as the zero-th moments of all distances have been inserted into D(k). All angles between consecutive arcs are 60⁰, otherwise 90⁰. This folding of a chain can be checked on three arcs on the tetrahedron.

The adjacency matrix A of the linear chain L₅ corresponds to the lowest negative moments of distances between vertices, because A = D(-∞).

It is well known, that the eigenvalues of the adjacency matrix A of the linear chain L_n are expressed in terms of cosines. They are symmetric, therefore their sum is zero. The eigenvalues of the adjacency matrix A, and simultaneously the distance matrix D of the complete graph, are assymmetric, one eigenvalue is (n- 1), n-1 other ones are -1. In Table I, eigenvalues of different power distance matrices of L₅ are tabulated. This chain is long enough to show the main properties of such a system, where second power geometric distance matrices of straight line chains have always only 3 nonzero eigenvalues.

Eigenvalues of linear chain L₅ distance matrices D(k) with different moments and/or conformations

* The eigevalues of the geometric distance matrix of the n-pentane in the optimal conformation . They were normalized to the unit length of C-C bond dividing by the factor 1.54.

** The eigevalues of the Hilbert distance matrix of the n-pentane in the linear conformation¹³. The distances were normalized to the unit length of C-C bond dividing by the factor 1.53.

The positive unnormalized eigenvector v is the deformed unit column (row) vector. At adjacency matrices A, the values corresponding to the unit vector are decreased on both ends. At positive distance moments k, they decrease in the center.

The eigenvalues of the geometric distance matrix of n-pentane, introduced by Trinajstic and others, fit between moments 1/2 and 1, with one exception. The eigenvalues of Hilbert distance matrix of the linear conformation of n-pentane fit excelently between moments 1 and 2. This corresponds to the increasing of the distances by stretching the molecule from the topological conformation to the geometric one. One eigenvalue nearly vanishas due to the planarity of the conformation.

Another case is the cycle C₄, which can be bent from the plane square shape to the regular tetrahedron shape by decreasing both diagonal distances, or till to a rod by decreasing one diagonal distance and increasing the other. Its topological distance matrix D is thus undistinguishable from the second moment geometric distance matrix of the square. The matrix JJ^T- I corresponds to one of possible geometric conformations, the regular tetrahedron (similar to the chain L₄, but there the adjacency matrix is different). By decreasing d₁₃ and d₂₄ distances of the regular tetrahedron, the cycle is folded, untill positions of opposite vertices coincide.

Therefore at the cycle C₄, the adjacency matrix A is simultaneously the distance matrix of this cycle, when vertices 1 and 3, 2 and 4 are identified and the cycle is folded. It is also possible to identify only a pair of vertices and fold all arcs of this cycle onto a line, if only one from the distances of 1 and 3, or 2 and 4 is zero.

The eigenvalues of the distance matrix with the elements d₁₃ = d₂₄ are obtained simply by adding or subtracting these elements from the eigenvalues of A:

This scheme leads to the change of ordering of eigenvalues, at positive k the second eigenvalue is obtained as the fourth one. The distance 8 is geometrically impossible, it must be therefore the sixth moment of 2^1/2. All distance matrices of C₄ have the same set of eigenvectors, corresponding to the matrix of the Vierergruppe:

The second case is the extreme, all vertices lie on a straight line. The third case represents two double bonds bended to 60⁰, or the adjacency matrix of the graph (K₄ - L₂), or the distance matrix of one of its conformations with identified positions of two vertices. The eigenvectors are deformed, too, going to lover values and to higher ones again (in the third case it is 0.7808, respectively) and having zero values, which are possible for other conformations or moments, too:

There exists the third possible deformation, corresponding to changes of two distances, the square transforms into a rectangle, which is a model of the formation of the cycle from two chains L₂. Here the zero distances give a permuted adjacency matrix, the second conformation is a permuted square and other changes are expressed as

All eigenvectors remain the same as for C₄. It can be conjectured that the distance matrix D of the graph consisting of two components L₂ entirely separated has two infinite eigenvalues, the other two are 0 and -2. This follows from its eigenvectors which remain identical without regard on distances of both components. The eigenvalues are again determined by symmetry elements. Nonzero eigenvalues are three for the square and two at the configuralation corresponding to L₂.

Here we study the formation of the cube from two cycles C₄. The adjacency matrix A of two cycles C₄ can be written similarly as for two chains L₂ in the block form as

Only the half of eight eigenvalues is tabulated in Table III. The other four eigenvalues are either zero, or, in the case of matrices A, they have inverse signs.

Eigenvalues of two squares in zero distance between them are just twice eigenvalues of one square. The distance in the third direction adds four times to the first eigenvalue and subtracts four times from the second one.

There seems to exist a pattern, how spectra of lattice graphs are formed. The spectrum of the square lattice formed by 3 L₃ is 25.4164, -12, -1.4164, -12, whereas 3 identified L₃ have spectrum 13.3485, -1.3485, 12. This are 3x(4.4495, -0.4495, -4), the eigenvalues of D[L₄].

Generalizing distance matrices D(k) to adjacency matrices is ambiguous at topological distance matrices of graphs which are embedded differently from their standard configuration. For example, on a cube many different graphs can be embedded, which adjacency matrices are subgraphs of the cube.

Some things appear to be obvious and trivial. Graphs were considered to be dimensionless, one dimensional or at most two dimensional mathematical notions which are isomorphic with some real objects, as molecules are. Then they must be spanned into the third dimension³.

I realize only now, that I interpreted textbooks differently: Graphs are multidimensional objects which must be squeezed and deformed, if we try to imagine them. As molecules, they are embedded in a lower dimension.

Coding of trees by matrices⁵ is probably unknown in chemical literature. Specialists overlooked, that the rooting of incidence matrices S removes the singularity of quadratic form S^TS of cyclic graphs, too. This can be exploited for solving the Kirchhoff problem²³.

Distance matrices of acyclic graphs are involved in the problem of embedding of molecules into crystalline latices², what is still an open problem. Acyclic molecules there form higher structures with many cycles and circuits.

Changes of a conformation of a graph from the standard topological configuration to geometric configurations lead to the change of eigenvalues of the distance matrix D. It can influence the eigenvalues of the adjacency matrix, too, if we admit partial adjacencies when k in d^-k_ij is not infinite. The relation between eigenvalues and moments is quadratic (and/or exponential, the correlation coefficients are excellent, but the number 4 of correlated points is low, to decide between both possibilities).

Pentane eigenvalues moments are 0.688-0.683 for the geometric distance matrix (the lowest and highest eigenvalue, respectively) and 1.64-1.62 for the second moment geometric distance matrix. The interpretation of these numbers is a puzzle. But the position of the geometric distance matrix is not compatible with stretched angles between bonds of n-pentane.

That the second-moment distance matrices have specific properties is not too surprising. It follows from their relations with the adjacency matrices A and the Laplace- Kirchhoff matrices S^TS, which, on the other hand, are quadratic forms of incidence matrices S. Eigenvalues and eigenvectors of the graph matrices seem to correspond to the elements of symmetry of graph embeddings.

The Wiener index is the sum of elements of the topological distance matrix. Its value surprisingly appeared as the lowest eigenvalue of the second moment geometric Hilbert distance matrices of straight chains. It seems reasonable to expect similar relations for other molecules as well.

The linear change of eigenvalues of the geometric Hilbert distance matrices was observed in the studied special cases, when distances were changed. This could explain why molecules prefer some configurations, especially in crystaline state. Eigenvalues and eigenvectors of adjacency matrices A correlate well with energy of bonding electrons of aromatic compounds, but eigenvalues and eigenvectors of distance matrices change with the configuration, as our examples showed.

Topological indices based on matrix elements should be not only practical, it means correlate well with physicochemical properties of chemical compounds, but should also be consistent with mathematical properties of matrices. The geometric Wiener index disappointed expectations^8-15. The present study of eigenvalue transformations indicates that the second moment geometric Wiener index could perform better, at least theoretically.

Acknowledgement. Thanks the Guest Editor for his constructive comments of the first version of the paper.