Milan Kunz

Jurkovičova 13, 63800 Brno, The Czech Republic

Abstract: Asymmetric Markov matrices M, which show orientation of arcs in multigraphs, are obtained as linear combinations of scalar products of incidence matrices of the oriented and corresponding orientation depleted graphs. The relation of the stochastic operator P =(I + M), where I is the unit diagonal matrix, with the continuous differential equation model is outlined.

INTRODUCTION

At the beginning of our century, Markov [1] studied probabilities of transitions of consecutive phonemes, as consonants c and vowels v e. g.

A vv A vc M cv A vc R cc K cv O vc V

Probabilities of transitions vv, vc, cc and cv are obtained from direct counts by dividing their sums by all possibilities of transitions, as usual. When arranged into matrices, they form stochastic matrices P, which row sums are 1. The theory of processes connected with these matrices forms a part of the theory of stochastic processes [2-4].

Each phoneme in a text is considered to be a state of the system which fluctuates constantly between its possible states, forming a chain of consecutive events.

There is another possibility how to interpret the phenomenon. A text can be considered as a whole and all observed differences can form one transition into the next state. Or two distinct objects, represented by strings of symbols, can be compared, as two linear molecules are. The differences can be thus expressed as arcs of a graph, e. g.

? A A M A R K O V

A A M A R K O V ?

c * 0 1 -1 1 0 -1 1 *

v * 0 -1 1 -1 0 1 -1 *

The two rows with numbers form the transposed incidence matrix ST of the multigraph with loops, zeroes are on places of loops, arcs beginning and ending on the same site, asterisks * mark undetermined start and end terms.

The aim of this paper is to show, how the stochastic matrices P are obtained from the incidence matrices S and relation of the stochastic operator P to the continuous differential equation model.

DOUBLE ACCOUNTING OF GRAPH ARCS

Adjacency matrices A used in chemistry are usually symmetrical [5,6]. They are related to incidence matrices of either a corresponding oriented graph S, where sij = -1, if arc i is oriented from vertex j, sij = 1, if the arc i is oriented to vertex j, sij = 0 otherwise, or an unoriented graph G, where gij = 1, if the edge i is incident with the vertex j, gij = 0 otherwise [7]:

STS = V - A GTG = V + A,

where V is the diagonal matrix of vertex degrees vij. Each arc or edge appears twice in the matrix A as aij = aji. The matrices STS are known as Laplace-Kirchhoff matrices. Graphs are allowed to have multiple arcs or edges but they must be without loops since the formalism used does not count them, the empty row of an incidence matrix S corresponds to a loop.

The quadratic form STS is a symmetrical matrix. Its elements count simultaneously all arcs between i and j, oriented from i to j as well as oriented from j to i.

Graph theory knows also asymmetric adjacency matrices [8]. In them, arcs going from i to j are distinguished from arcs going from j to i. When row vectors c are multiplied from the right, then aij = k counts arcs going from the vertex j into the vertex i, when column vectors c are multiplied from the left, then aij = k counts arcs going from the vertex i into the vertex j. We will use subscripts r and l at adjacency matrices A. The orientation of arcs can be expressed by signs too, where aij = +k, when k arcs go from the vertex i into the vertex j, or where aij = -k, when k arcs go into the vertex i from the vertex j, or opposite according to the convention used. But no formal algorithm is known how the splitting of arcs should be done and how the Markov operator P can be obtained from graph matrices.

Let S and G be incidence matrices of the same oriented multigraph, where S and G are identical except for signs. An unoriented edge corresponds to each arc. The matching rows of S and G are mutually orthogonal vectors in n dimensional Euclidean space [7].

Fig. 1 Multigraph of transitions

The products STG and GTS of the strings of orthogonal vectors are asymmetrical matrices showing differences in orientation of arcs. We use as an example the multigraph on Fig. 1. It is isomorphic with the transposed incidence matrix ST

The elements of the matrix GTS are

They can be interpreted as

vjj = (arcs into j) - (arcs out of j)

aij = (arcs from i into j) - (arcs from j into i),

The elements of the matrix STG are

They can be interpreted as

vjj = (arc into j) - (arc out of j)

aij = (arcs from i into j) - (arc from j into i),

The off-diagonal elements of the matrix STG differ from the off-diagonal elements of the matrix GTS only by signs. The products STG and GTS can be combined with the quadratic forms of the incidence matrices STS and GTG. There are four additive combinations

This gives the pattern

GTS + STS = 2(Vin - Ar)

GTS - STS = 2(Al - Vout)

GTS + GTG = 2(Vin + Al)

GTS - GTG = -2(Ar + Vout)

The product (G - S)TS can be normalized into the left hand side operator M, when the matrix is multiplied by a constant b or a set of constants scaling all elements down to be less then 1.

The diagonal matrices of vertex degrees of arcs which are going in and out, as well as asymmetric adjacency matrices can be separated by transposing sums or differences GTS with GTG and combining them with sums or differences GTS with STS:

4Vin = (GTS + STS) + (GTS + GTG)

-4Vout = (GTS - STS) + (GTS - GTG)

-4Al = (GTS + STS) - (GTS + GTG)

4Ar = (GTS - STS) - (GTS - GTG).

In graphs without loops GTG = STS. If loops are allowed, they appear in the incidence matrix G as two 1's on the place of vertex j. This gives 4 for each loop on the diagonal of GTG. The number of loops is thus the difference (GTG - STS)/4. The diagonal elements of GTG can be used as constants b for scaling the product (G - S)TS. The same operation with STG gives the pattern

STG + STS = 2(Vin - Al)

STG - STS = 2(Ar - Vout)

STG + GTG = 2(Vin - Ar)

STG - GTG = -2(Al - Vout)

The scalar product ST(G - S) can be normalized into the right hand side operator M as above. The diagonal matrices of vertex degrees of arcs which are going in and out, as well as asymmetric adjacency matrices are separated by transposing sums or differences STG with GTG and combining them with sums or differences STS with STS as previously. These transposes are identical with sums or differences of GTS, because transposing changes ordering of matrices in the product.

Finite Markov processes are usually not connected with the continuous differential equation model. Nevertheless, both processes are isomorphic and Markov chains form transformation groups of the continuous process. This can be demonstrated on the case of a simple irreversible process A ---> B.

The scaled product (G - S)TS has a negative diagonal. It shows fraction which disappears from the matching place of the column vector c and appears on other places. To get the identity operator P, we must add the unit diagonal matrix I, P =(I + M). This is unfortunately confusing, since the theory of finite Markov processes works with the matrix (I - P).

The relation between the discrete and continuous process is shown on Fig. 2.

The horizontal axis represents the concentration of the product B going from 0 to 1 and simultaneously the concentration of the educt A going from 1 to 0 since the balance A + B = 1 in all instants. This balance is given by the diagonal, also, if the vertical axis represents the concentration of the educt A. The plot is dimensionless since time does not appear explicitly.

Fig. 2. Zenon plot differential equation model.

The slope = 0.7, the determinants are 0.7x1 = 0.8x0.9 - 0.2x0.1. Both graphs have the same number of arcs.

On each transformation line are infinite many points as well as infinite many steps corresponding to consecutive multiplications of the matrix P as we know from Zenon aporeas. If the process is reversible, the transformation lines end at the equilibrium concentration.

The plots are dimensionless because time does not appear explicitly. The slopes of transformation groups are determined only by matrix reaction elements. Intuitively, the lesser slope corresponds to a faster reaction.

Comparing to Zenon cases, here the time intervals are constant and the theoretical time needed to reach the end is infinite. But for each scale of the plot, we come soon to the limit when the steps merge with diagonal and horizontal axis. This is given by properties of the infinite sums for the constant e. They converge quickly. Even for the scale corresponding to the fraction of 1 molecule to 1 mol about 25 first terms are sufficient; somewhat more are needed for halflives.

I do not know how to plot Zenon paths for differential equations with more variables, but the dependence of the slope of the transformation lines with determinants gives a hint for comparing different matrices P.

DISCUSSION

Markov processes can be interpreted as multigraphs and connected with the graph theory.

The incidence matrices S and G, or their transposes, used as multiplication operators, transfer each element of the multiplied matrix vector twice, once on the diagonal and once as off-diagonal element. Sums or differences of these matrices S and G have in each row just one element 2 in the ending or starting column, respectively. The relations obtained by the combination of both form products are thus elementary. But they are not explained in textbooks or are not cited in current literature. If they appeared earlier, they were forgotten.

Double entry accounting of arcs using orthogonal vector strings, their sums and differences, quadratic forms, scalar products and transposes gives a web of related matrices describing graphs and to them isomorphic molecules and their transformations and generally the flows in circuits.

The Laplace-Kirchhoff matrix, identical with STS, is usually a symmetrical one. It can describe properties of electrical circuits and resistances of lines connecting vertices of the net. The direction of the flow in the net is induced by electrical tension applied [10-13].

Connecting differential equations with finite Markov processes as relations of symmetry within chemical systems gives an opportunity to exploit results of their theory, for example the existence of the equilibrium operator (I + M)´ in the form of a matrix with identical rows [4]. Since these matrices are obtained even from symmetrical (I + M), the principle of microscopic reversibility [14]

c*ikij = c*jkij

is clearly violated. Asencor and Gracia [15] already doubted its validity before. At chemical reactions, the steepest descent to an equilibrium can be, maybe, the optimal path in a concentration simplex but it is not possible to prove that it is the only possible path for all reaction systems and conditions.

We simplified the analysis leaving geometrical problems aside. Each molecule has its position in space so the distances between molecules should be considered. The reaction behavior depends even on the size of the system as more sophisticated analyses, using the probability theory and the notion of memoryless particle lifetime distribution, have shown [17].

ACKNOWLEDGEMENT

I thank to the reviewer for his detailed and inspiring comments to the first version of the paper.

REFERENCES

1. A. A. Markov, An example of statistical investigation of the text of "Jevgenii Onegin" illustrating the connection of experiments in a chain (in Russian), Bull. Acad. Imp. Scien. de St. Petersbourg, Ser. VI, 7 (1913), 153-162.

2. J. L. Doob, Stochastic Processes, J. Wiley, New York, 1953.

3. S. Karlin, A First Course in Stochastic Processes, Academic Press, New York, 1968.

4. J. G. Kemeny, J. L. Snell, Finite Markov Chains, AMA, Dartmouth 1959.

5. D. H. Rouvray, The topological matrix in quantum chemistry. In Chemical Applications of Graph Theory, Balaban, A.T., Ed., Academic Press London, 1976, pp. 175-221.

6. D. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs, Deutcher Verlag der Wissenshaften, Berlin, 1980.

7. M. Kunz, About Metrics of Bibliometrics, J. Chem. Inf. Comput. Sci., 33, (1993) 193-196.

8. F. Zhang, G. Lin, The complexities of digraphs. In: Graph Theory and Its Applications: East and West, M. F. Capobianco, M. Guan, D. F. Hsu, F. Tian, Eds., Annals of the New York Academy of Sciences, 1989, Vol. 576, 663-670.

9. M. Kunz, Determination of parameters of the pseudomonomolecular reaction (in Czech), Chem. Listy, 75 (1981), 432-433.

10. D. J. Klein, M. Randic, Resistance distance. J. Math. Chem. 12, (1993) 81-95.

11. M. Kunz, An equivalence relation between distance and coordinate matrices, MATCH, 32, (1995) 193-203.

12. M. Kunz, Inverses of perturbed Laplace-Kirchhoff and some distance matrices, MATCH, 32 (1995), 221-234.

13. M. Kunz, Inverting Laplace-Kirchhoff matrices from their roots, J. Chem. Inf. Comput. Sci., in press.

14. J. Wei, C. D. Prater, Structure and analysis of complex reaction systems. In D.D. Eley, P. W. Selwood, P. B. Weisz Eds., Advances in Catalysis, Vol. XIII, 203-392, Academic Press, New York, 1962.

15. F. J. Assencor, J. M. Gracia, A note on essentially positive matrices which appear in chemical kinetics. MATCH, 20, 143-163 (1986).

16. A. Cornish Bowden, Principles of Enzyme Kinetics, Butherworth, London, 1976.

17. M. Šolc, The first passage time to the equilibrium state of a first order reaction, Collect. Czech. Chem. Commun., 52, 1-5 (1987).