Information Technology Reference
In-Depth Information
x n matrices, with off-diagonal elements, as L
ij
kl
=
l
with i =/= j. Thus the ij
basis matrix has a '1' in position ij with a '-1' in position jj on the diagonal. These
n(n-1) matrices form a basis for the Lie algebra of all transformations that preserve
the sum of the components of vector. With this particular choice of basis, we then
showed that by restricting the parameter space to non-negative values,
δ
i
k
δ
j
l
-
δ
j
k
δ
j
>=0, one
obtains exactly all Markov transformations in n dimensions that were continuously
connected to the identity as M = exp (s
λ
ij
L
ij
) where we summarize over repeated
indices and where s is a real parameter separated from
ij
λ
ij
λ
to parameterize the
continuous evolution of the transformation. In other words
L
ij
consists of non-
negative coefficients in a linear combination of L
ij
matrices. This non-negativity
restriction on the parameter space removed the group inverses and resulted in a
continuous Markov monoid, a group without an inverse, in n dimensions, MM(n).
The basis elements for the MM algebra are a complete basis for n x n matrices that are
defined by their off-diagonal terms. The n dimensional Abelian scaling Lie algebra
can be defined by L
ii
kl
=
λ
ij
l
thus consisting of a '1' on the i,i diagonal position.
When exponentiated, A(s) = exp (s
δ
i
k
δ
i
L
ii
), this simply multiplies that coordinate by e
s
giving a scaling transformation. In what follows, we will show that all networks
exactly correspond (one to one) to a combination of this Abelian transformation group
and the Markov monoid transformations.
λ
ii
3 Connecting Markov Monoids to Network Metrics
The essence of this paper is the simple observation that (1) since the non-negative off
diagonal elements of an n x n matrix exactly define a network (via C) and its topology
with that node numbering, and (2) since a Markov monoid basis is complete in
spanning all off-diagonal n ½ n matrices, then it follows that such networks are in one
to one correspondence with the elements of the Markov monoids. Thus each
connection matrix is the infinitesimal generator of a continuous Markov
transformation and conversely. This observation connects networks and their
topology with the Lie groups and algebras and Markov transformations in a well
defined way. Since the Markov generators must have the diagonal elements set to the
negative of the t sum of the other elements in that column, this requirement fixes the
otherwise arbitrary diagonal of the connection matrix to that value also (sometimes
referred to as the Lagrangian).
It now follows that this diagonal setting of C generates a Markov transformation
by M= e
λ
C
. One recalls that the action of a Markov matrix on a vector of probabilities
(an n-dimensional set of non-negative real values whose sum is unity), will map that
vector again into such a vector (non-negative values with unit sum). The next
observation is that by taking
C by
ignoring order l2 and higher order infinitesimals. Here one sees that the bandwidth of
the connection matrix between two nodes, now give that M matrix element as the
relative transition rate between those two components of the vector. Thus it follows
that given a probability distribution xi distributed over the n nodes of a network, then
M gives the Markov transition (flow) rates of each probability from one node to
another. Thus it follows that the connection matrix gives the infinitesimal transition
rates between nodes with the bandwidth reflecting that exact topology.
λ
as infinitesimal, than one can write M = I +
λ
