An Algebraic Relation between Distance Matrices of Trees and Simple Cycles and Their Line Graphs

	Sign In Sign-Up

An Algebraic Relation between Distance Matrices of Trees and Simple Cycles and Their Line Graphs.
Milan Kunz, July 23, 2000.

To known relations of quadratic forms of incidence matrices S of oriented trees (G of unoriented graphs), the adjacency matrix A and the distance matrix D, a new formal matrix relation SDS^T + GDG = 4D[L(G)] is added. It is proven true for trees and simple cycles. D[L(G)] is the distance matrix of the line graph of the graph G. Some consequences of this algebraic relation for chemistry are discussed.

INTRODUCTION

Relations between chemistry and graph theory are well known. It is not necessary to enumerate all achievements in this field. Nevertheless, some parts of the graph theory are still applied by the traveling salesman‘s method - by trial and error. This is true especially for topological indices. This unfortunate situation results from the fact, that there were not studied some elementary properties of matrix algebra, or, if such studies had been made, results were overlooked as the Redfield‘s paper about symmetry of graphs (1).

Even such a basic question was not settled, as dimensionality of graphs is: are graphs dimensionless objects (2), one dimensional objects (3), two dimensional object (4) or multidimensional objects in Hilbert space (5)? From different conceptions, different consequences follow: are ideal graphs spanned on three dimensional molecules or squeezed into them and are eigenvalues and eigenvectors just abstract notions or hidden parameters?

There exists, of course, a mathematical model of the logical structure of chemistry, pioneered by Dugundji and Ugi (6) and elaborated for purposes of computer assisted syntheses (7), which is based on matrix formalism and accepts multidimensionality, but it does not exploit all properties of introduced matrices.

Some specialists believe, that microparticles have some strange properties which distinguish them from macroscopic objects (8). But many characteristics of molecules can be deduced from elementary algebraic relations between their elements without any explicate association to some specific conditions of microparticles as orientations of electronic orbitals or geometric positions of nuclei are. If such matrices describing only topological relations in molecules are not specific for microparticles, then we can not postulate some special properties for microparticles and other properties for macroobjects, which could be described by identical matrices. Only size and importance of algebraic effects transformed into forces can be different.

All matrices which represent molecules as graphs can be obtained from strings of unit vector rows e_j (0₁, 0₂,..1_j,.., 0_n). Their strings-vector columns form naive matrices N, having in each row just one unit symbol (9).

According to the known axioms, the elements of a vector space are also sums and differences of its elements. Therefore we have G = N_a + N_b and S = N_b - N_a. Matrices G and S are known as the incidence matrices of unoriented and oriented graphs, respectively. Other elements of a vector space are scalar products, from them especially quadratic forms N^TN, NN^T, G^TG, GG^T, S^TS, SS^T and their inverse matrices, if they exist.

The symmetry of naive matrices is product of two groups of cyclic permutations S_n and S_m, represented by the unit permutation matrices P_n and P_m, acting on the matrix N independently from the left and from the right: P_mNP_n. These symmetries are separated in quadratic forms : P_nN^TNP_n and P_mNN^TP_m. The symmetry of graphs is determined by a wreath product of two groups of cyclic permutations acting on both elements of an incidence matrix and or on the whole matrix .

The rows of the incidence matrices S of oriented graphs are differences of two unit vectors (e_j - e_i). An arc is just a vector going from the vertex i to the vertex j, if both vertices are in n-dimensional space on the ends of corresponding unit vectors. At unoriented graphs, the vector row (e_j - e_i) is orthogonal to a line connecting both vertices or to the arc vector (e_j - e_i). But chemical bonds are formed by electrons and not by some lines, which are just a convenient convention for their depicting. The incidence matrices show the topology of electors in a molecule. For our purposes, it is essential, that the incidence matrices S and G of an unoriented graph, which was arbitrarily oriented or on contrary, of an oriented graph, which orientation was depleted, behave as orthogonal vectors in nm-dimensional space.

The quadratic form S^TS of the incidence matrix S of an oriented graph is known as the Laplace-Kirchhoff matrix. Its generalized inverses (11), and their specific form defined by Moebius inversion, the Eichinger matrices E, were found (12).

They were defined at trees and simple cycles as E = S [d_j(S^TS)]^-1 (13), where the sum is made from j =1 till n.

Their product with the parent Laplace-Kirchhoff matrix is S^TSE = nI - JJ^T, where d_jM is the matrix M which j-th row and column are deleted, J is the unit vector column and I is the unit diagonal matrix.

The existence of generalized inverse matrices E follows from the Le Verrier-Frame-Faddeev recursive method for calculations of characteristic polynomials (14). Their coefficients are obtained according to the Frame technique as an =( 1/n)TrMB_n-1, where Tr is the trace of a matrix. B_n-1 = M_n-1 - aI_n-1 and M_n = MB_n-1. The calculation ends, when it gives the zero matrix 0:

B_n = M_n - a_nI = 0. Since S^TS[S^TS(B_n-2 -nI)] = 0, there appears the equivalence E = B_n-2 and a_n-1 = n.

The elements of Eichinger matrices at trees are topological distances (13). These distances were known from distance matrices D, which elements d_ij are numbers of arcs or edges on walks or paths, respectively, between given vertices. Similar distances or their sums appeared at inverse matrices (SS^T)^-1 and (GG^T)^-1 of trees, which are quadratic forms of walk matrices W (15). At oriented trees, Eichinger matrices E, distance matrices D and the quadratic form W^TW of the walk matrix are equivalent (13, 16).

It was found, that second power distance matrices have specific properties, they yields angles between arcs in the difference frame SDS^T (17, 18). Moreover, these distance matrices can be derived from the coordinate matrices by an algorithm.

Between an ideal shape of a graph corresponding to its distance matrix and a shape of a molecule a discrepancy exists, which should have an effect on properties of the molecule.

The aim of this paper is to prove a new identity relating distance matrices of trees and simple cycles with distance matrices of corresponding line graphs.

DISTANCE MATRICES OF LINE GRAPHS

The other quadratic form of the incidence matrix determines the adjacency matrix of the line graph L(G):

GG^T = 2I + A[L(G)]

SS^T = 2I + A[L(G)]

The line graph is a graph, whose edges or arcs are transformed into vertices which are connected, if both bonds are incident with the same vertex in the parent graph (19). In the case of unoriented graphs, A[L(G)] is simply the adjacency matrix of a line graph, but in the case of oriented graphs, the off diagonal elements of SS^T can have both signs, depending on mutual orientations of parent arcs, whereas in adjacency matrices A all elements have equal signs. Thus, the adjacency matrices of line graphs derived from of oriented graphs need a special interpretation. From rules of matrix multiplication, it can be easily deduced, that all signs can be negative in SS^T, only if all arcs have the same orientation.

This is exceptionally possible at linear chains or simple cycles, when vertex degrees v_j <= 2. All signs can be positive if all arcs are going in or going out of a vertex. Such an orientation is possible generally at bipartite graphs.

It is obvious from the definition of incidence matrices of oriented and unoriented graphs, that their effect on a matrix inside their quadratic frame is opposite, G sums elements of the inner matrix, whereas S subtracts them. But the sum of both operations at trees and simple cycles leads to an unexpected identity

SDS^T + GDG^T = 4D[L(G)] (1)

The sum of inner products of the distance matrix D with the incidence matrices of oriented and unoriented forms of a tree or a simple cycle gives a multiple of the distance matrix of its line graph.

PROOF FOR TREES

At trees SDS^T = -2I,thus for complying with the identity (1), it must be

GDG^T = 4D[L(G)] + 2I.

Some elementary calculations for stars and chains show, that the identity is fulfilled at small trees. We suppose that it is true for all trees with (n - 1) vertices. We add the n-th vertex and connect it with the (n - 1)-th vertex. Permutations of rows and columns of the corresponding matrices D and G make such labeling always possible. In such a way, the first (n - 1) rows and columns of the distance matrix remain unchanged. The last row and column elements are :

d_nj = d_n-1,j+1+1; d_in = d_i,n-1 + 1; d_nn = 0.

The last column of the product DG^T is the sum of two last columns of the matrix D: 2d_i,n-1 + 1. The elements of the final product in the last column are again sums of two such elements (2d_i,n-1 + 1) + (2d_j,n-1 + 1). If there is an edge ij, these parts differ, e.g. d_j,n-1 = d_i,n-1 + 1. The result is 4d_j,n-1 +4. The distances of edges to themselves are zero therefore the diagonal elements are 2. For the last row, we reverse the order of multiplication and consider at first products GD. It is clear that diagonal elements of GDG^T eliminate with the result of the matrix product SDS^T and the result is the multiple of the distance matrix of the line graph.

FORMAL PROOF FOR CYCLES

At cycles, the line graph is identical with the vertex graph, because the number of vertices is the same as the number of arcs or edges. Also both quadratic forms of incidence matrices are identical: G^TG(C) = GG^T(C) and S^TS(C) = SS^T(C) , of course provided, that all arcs have equal orientation. We can then write: G = I + P and S = I - P, where P is the unit permutation matrix of a full cycle, e.g. (2,3,..n,1). The proof of the identity (1) is based simply on the formal multiplication

(I+P)D(I+P)^T + (I-P)D(I-P)^T = 2(D + PDP^T) = 4D = 4D[L(C)].

This result is obtained differently at even and uneven cycles. The elements of the product SDS^T at even cycles are: -2 on the diagonal, and if j = (i + n/2) ş 0 mod n, and zero otherwise.

SDS^T of uneven cycles have on the diagonal -2 and 1 if j = {1+(n-1)/2} ş 0 mod n or {1+(n+1)/2} ş 0 mod n, zero otherwise. At uneven cycles the matrix SDS^T is a matrix -SS^T of a cycle, in which most distant vertices of the original cycle are connected by bonds. At even cycles the most distant vertices form cycles of the length 2. Similar pattern was observed at products GDG^T, which corrects the result.

We can use similar technique for analyzing the identity (1) at trees, too. Their incidence matrices can always be permuted into a form, which can be divided into two block matrices

G = I_n-1ا 0 + 0 اN,where 0 is a zero vector column, provided that nonzero elements of matrices I and N do not cross. Inserting into (1), we obtain similarly as at simple cycles:

2I_n-1DI_n-1 + 2NDN^T = 4D[L(G)]. The distance matrix of the line graph is the sum of the distance matrix of the parent tree with the last row and column deleted and the inner product of the distance matrix with the first row and column deleted inside of the quadratic form NN^T of the naive matrix.

There are two simple cases. At linear chains the naive matrix N is just the permutation matrix P of a full cycle with the last row deleted, which has the unit element on the first place. The product is simply four times the distance matrix of the linear chain with (n - 1) vertices, which is the line graph of the linear chain with n vertices. The other extreme case, which can be simply evaluated, are stars. At stars rooted in the n th vertex, the naive matrix N is just the unit vector column J_n-1. But all elements in the product JDJ^T are produced by the distance d_nn, which is zero.

The result of the multiplication is 2D_S, with the last row and column deleted. Because all off diagonal elements of the distance matrix of a star rooted in the n th vertex are 2, except the last row and column, which was deleted, we obtain four times the distance matrix of the complete graph with (n - 1)vertices, the line graph of the star.

DISCUSSION

Line graphs of stars S_n are complete graphs K_n-1. This gives straightforwardly explanation of the shape of starlike molecules. The optimal shape of K₄ is the tetrahedron. Therefore methane has this form, all distances between its protons are equal. From similar reasons ammonia is not planar and water linear, because deviations from these configurations improve distances of their line graphs.

The line graph of substituents of a pentacoordinate atom is K₅. But this complete graph is a body in 4 dimensional space and in our 3 dimensional space, it can appear in a distorted form, only. It can be decomposed into 5 tetrahedrons which appear in a trigonal bipyramide as two trigonal pyramids and 3 tetrahedrons, which have the central atom on their longer sides.

If this interpretation of algebraic relations seems to be too simplistic, then as the another example of practical results, which came before some formal algebraic identities were noticed. The Flory‘s theory of statistical mechanics of polymer chains. It is based on application of practically only two matrices Zimm matrix and its inverse, Rouse matrix. They are identical with SS^Tand (SS^T)^-1 matrices, respectively. The off-diagonal elements of the Rouse matrix form the adjacency matrix of the line graph. Eigenvalues of the Rouse matrix were connected with relaxation times of polymer chains at their movements, but nobody noticed that the trace of the Rouse matrix coincides with the Wiener index, the most prominent topological index. Its value is just a half of the sum of elements of the distance matrix. It was found as one from three nonzero eigenvalues of distance matrices of straight chains, too.

It has different physical meaning, if we say that boiling points of alkanes correlate well with topological distances of abstract graphs of molecules or with the sum of relaxation times of alkanes.

Recently, 3-dimensional distances in molecules were calculated in the matrix form (4), but their first moments are not consistent with the moments of the topological distance matrices.

Algebraic relations between different graph matrices show that the vector space, molecules exist in, is inseparable. The particle-wave dichotomy appeared in a new form. There are two quadratic forms of incidence matrix vectors. They corresponds to different aspects of these vectors. An inverse matrix of one quadratic form, or its transformed form, can be inserted inside the other quadratic form and has again similar effect. It reminds a Moebius strip, but it is known as Moebius function in combinatorics.

It seemed easy, to compare a molecule with a graph. Atoms were vertices and bonding electrons corresponded to edges or arcs of a graph. The line graph was defined and nobody protested. Now from algebraic calculations distance matrices of line graphs resulted. Their elements are topological distances between electrons. We must ask why can not exist to them similar geometrical distance matrices as for nuclei? But a possibility of localization of bonding electrons was contested .

A new algebraic relation between simplified graph matrices has no practical value, because it rediscovered well known results of quantum and statistical mechanics, only. But a better understanding of all algebraic relations gives us a deeper insight how the molecules are built

Linear algebra can not be rejected as a formal play with simplified matrices. At least some results correlate well with observed physical properties of corresponding molecules. Either all results must be accepted or consistent reasons given, why something is applicable and other not.

But even if the presented results could be superfluous, they pose some philosophical questions which were not still settled. The Laplace operator gives a discrete description of a wave function. The dichotomy of elementary particles puzzled minds from the onset of quantum mechanics. It seemed unbelievable that something could behave as a particle in a situation, and as a wave in another circumstances.

Now this dichotomy appeared in another form: Some properties of molecules are determined by their graph structures, other by their matrix inverses. The inverse elements of incidencies or adjacencies between vertices of a graph appeared as distances. When we accept that incidencies in graphs matrices correspond to electrons in molecules. We must ask: Which form have elements of inverse matrices called distances for wave and particle forms of electrons ?

REFERENCES AND NOTES

1.Lloyd E. K. J.: Graph Theory 8:195 (1984).

2.Turro J.: Ang. Chem. 98:872 (1986).

3.Gordon M., Temple W.B.: Graph like state of matter and polymer science in Balaban A.T. (Ed.) Chemical applications of graph theory, Academic Press, London, 1976, p. 299

4. Mihalic, Z.; Veljan, D.; Amic, D.; Nicolic, S.; Plavsic, D.; Trinajstic, N.: The Distance Matrix in Chemistry, J. Math. Chem., 11, 223-258 (1992).

5.Dugundji J. ,Ugi I.: Top. Cur. Chem. 39:19 (1973).

6.Dugundji J., Gillespie P., Marquarding D., Ugi I., Ramirez F.: Metric spaces and graphs representing the logical structure of chemistry. In: Balaban AT (Ed.) Chemical applications of graph theory, Academic Press, New York, (1976), p. 107.

7.Koča J.: Theor. Chim. Acta. 80:29 (1991).

8. Mezey P.G.: Potential Energy Hypersurfaces, Elsevier, Amsterdam,1987.

9. Kunz, M. in: Mizerski, J.; Posiewnik, A.; Pykacz, J.; Zukovski, M.; Eds.: Problems in Quantum Physics II; Gdansk 89; World Scientific, Singapore,1990, p.377.

10. Harary F. , Palmer E.M., Robinson R.W., Read R.C. Polya‘s contribution to chemical enumeration In: Balaban AT (Ed.) Chemical applications of graph theory, Academic Press, New York, 1976, p. 12.

11.Eichinger B.C.: J. Polymer Sci.: Polymer Symposia 54:127 (1976).

12. Kunz, M.: A Moebius Inversion of the Ulam Subgraphs Conjecture. J. Math. Chem. 9, 297-305 (1992).

13. Trinajstic, N.: The Characteristic Polynomial of a Graph. J. Math. Chem.2, 197-215 (1988).

14. Kunz, M.: Path and Walk Matrices of Trees. Coll. Czech. Chem. Commun.54, 2148-2155 (1989).

15. Kunz, M.: On Topological and Geometrical Distance Matrices. J. Math. Chem.13, 145-151 (1993).

16. Bertz S.H.: J. Chem. Soc. Chem. Comm. 1981: 818.

17. Eichinger B.C.: Macromolecules 131 (1980).

18. Golden S.: J. Mol. Struct. 223:93 (1990).

19.Mohar B.: Laplacian matrices of graphs. In: Graovac A. (Ed.) Studies Phys. Theor. Chem. 63 MATH/CHEM/COMP 1988, Elsevier, Amsterdam, 1989, p. 1.