# Invariants for Weighted Digraphs under One-Sided State Splittings

Authors: Sheng Chen; Xiaomei Chen; Chao Xia
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Using Matrix-Forest theorem and Matrix-Tree theorem, we present some invariants for weighted digraphs under state in-splittings or out-splittings.


---

## Body

## 1.Introduction

State in-splittings and out-splittings are very important operations in the theory of one-sided, or two-sided Markov shifts ([1, 2]). Lind and Tuncel introduced a spanning tree invariant for Markov shifts in [3]. Spanning tree invariants are further studied in [4–6]. Motivated by these works, we consider some other graph structures like cycles and forests and present some invariants for weighted digraphs under state in-splittings or out-splittings.Firstly we give some basic definitions in graph theory and a brief introduction of Matrix-Forest theorem for digraphs. Readers can refer to [7, 8] for more details.In this paper, a digraph is an ordered pairD=(V,E) of finite sets, where V is called the vertex set and E⊆V×V is called the edge set. For an edge (u,v)∈E, u and v are called the initial and terminal ends of the edge, respectively. The number of edges having u as the initial end is defined to be the outdegree of u and denoted by d(u). The number of edges having v as the terminal end is defined to be the indegree of v. A walk of length n is a sequence of edges {(ui,ui+1)}(i=1,…,n) and can be denoted by (u1,u2,…,un+1); moreover, if un+1 is the same as u1, we call the walk a closed one. A directed forest is a digraph without closed walks such that the indegree of each vertex is no more than one. The vertices with indegree zero of a forest are called roots. We say that D0=(V0,E0) is a spanning subgraph of D if V0=V and E0⊆E.Suppose thatD is a digraph with vertex set V(D)={1,…,n}. Let w:E(D)→ℝ+ be a weight function on the edge set. We then say that 𝒟=(D,w) is a weighted digraph and M=(w(i,j))n×n is the weight matrix of 𝒟. The Kirchhoff matrix of 𝒟 is defined as L=R-M, where R=(ri,j) is a diagonal matrix and ri,i=∑j=1nw(i,j). The product of the weights of all edges that belong to a subgraph ℋ of 𝒟 is defined to be the weight of ℋ and denoted by w(ℋ).Letℱ(𝒟)=ℱ be the set of all spanning rooted forests of 𝒟 and ℱi→j(𝒟)=ℱi→j the set of those spanning rooted forests of 𝒟 such that i and j belong to the same tree rooted at i. For a matrix A, Ai,j denotes the cofactor of the (i,j)-entry of A. The Matrix-Forest theorem then states as follows.Lemma 1 (cf. [8]).
Let𝒟=(D,w) be a weighted digraph. Let L be the Kirchhoff matrix of 𝒟. Then one has (1)
∑F∈ℱw(F)=det(I+L);(2)
for anyi,j∈V(D), ∑F∈ℱi→j‍w(F)=(I+L)i,j.


## 2. Invariants for Weighted Digraphs under State In-Splitting

Before giving the main result, we recall the definition of state in-splitting.Definition 2.
Let𝒟=(D,w) be a weighted digraph. For a vertex u of D, Eu denotes the set of edges of D with terminal end u. The state in-splitting of 𝒟 at u induces a new weighted digraph 𝒟~=(D~,w~) in the following way: let 𝒮={S1,S2,…,Sr} be a partition of Eu. The vertex set of the new digraph is V(D~)=(V(D)∖{u})⋃‍{u1,u2,…,ur}. The edge set E(D~) and weight w~ of 𝒟~ are defined as follows.(i)
Forx,y∈V(D)∖{u}, (x,y)∈E(D~) if and only if (x,y)∈E(D) and in this case w~(x,y)=w(x,y).(ii)
Forx∈V(D)∖{u}, (x,ui)∈E(D~) if and only if (x,u)∈Si and in this case w~(x,ui)=w(x,u).(iii)
Forx∈V(D)∖{u}, (ui,x)∈E(D~) if and only if (u,x)∈E(D) and in this case w~(ui,x)=w(u,x).(iv)
If(u,u)∈Si, then (uj,ui)∈E(D~), for j=1,2,…,r, and in this case w~(uj,ui)=w(u,u).
For more details about state splittings, readers can refer to [2, 3, 9]. Now we give the definition of our new invariant.Definition 3.
Let𝒟=(D,w) be a weighted digraph. We define Wk(𝒟)(k≥1) as
(1)Wk(𝒟)=∑v‍d(v)∑C∈Cvk‍w(C),
where v runs over V(D) and Cvk denotes the set of closed walks of 𝒟 with length k at vertex v. Furthermore, we define the generating function W𝒟(t) as
(2)W𝒟(t)=∑k≥1‍Wk(𝒟)tk.
LetA be a square matrix. The trace of A is defined to be the sum of the elements on the main diagonal and denoted by tr(A). For a digraph D, the diagonal matrix O(D)=(oi,i) denotes the outdegree matrix of D that is, oi,i=d(vi). Then we have the following result.Theorem 4.
Let𝒟 be a weighted digraph with weight matrix M. Then W𝒟(t) is an invariant under state in-splitting and can be computed in the following way:
(3)W𝒟(t)=tr(O·adj(I-tM))det(I-tM)-tr(O).Proof.
We firstly prove the invariance ofWk(𝒟) for k≥1. Without loss of generality, if there is a loop at vertex u, we assume that it belongs to S1, where 𝒮={S1,S2,…,Sr} denotes the partition of Eu as in the definition of state in-splitting.
We define the mapping(4)φ:⋃v∈V(D)‍Cvk(𝒟)⟶⋃v∈V(D~)‍Cvk(𝒟~)
in the following way: for a closed walk C of 𝒟 with length k, if C=(u,u,…,u), then φ(C)=(u1,u1,…,u1); otherwise, we replace each maximum path of C of the form (v,u,u,…,u)(v≠u) with (v,ui,u1,…,u1) if (v,u)∈Si. it is not difficult to see that
(5)φ:Cvk(𝒟)⟶Cvk(𝒟~),
where v≠u, and
(6)φ:Cuk(𝒟)⟶⋃i=1r‍Cuik(𝒟~)
are both weight-preserving bijections.
Sinced(v)(v≠u) is the same for 𝒟 and 𝒟~ and d(u)=d(u1)=d(u2)=⋯=d(ur), we know that Wk(𝒟)=Wk(𝒟~) for k≥1, and the invariance of W𝒟(t) follows.
Finally, we notice thatWk(𝒟)=tr(OMk). Thus
(7)W𝒟(t)=∑k≥1‍tr{O·(tM)k}=tr{O·∑k≥1‍(tM)k}=tr(O·adj(I-tM))det(I-tM)-tr(O).Example 5.
Let𝒟=(D,w) be a weighted digraph as in the left of Figure 1. D^ is the opposite of D (see the right of Figure 1), that is, the digraph obtained from D by reversing the direction of all its edges. It is easy to see that D and D^ have the same outdegree sequence {1,1,2,2,3}. The weight of any edge (u,v)∈E(D) or (u,v)∈E(D^) is defined to be 1/d(u). Since W3(𝒟)=5/4 and W3(𝒟^)=19/9, we know that 𝒟^ cannot be obtained from 𝒟 by a sequence of in-splittings or reverse operations.Figure 1LetP be a nonnegative matrix. P is called row stochastic if the summation of each row equals 1 and column stochastic if the summation of each column equals 1 P is called double stochastic if it is row and column stochastic.Definition 6.
LetP be a row-stochastic matrix and t a real positive number. Let 𝒟 be the weighted digraph with weight matrix M=tP. We define K(𝒟,t) as
(8)K(𝒟,t)=(1+t)∑vd(v)∑Fvw(Fv)∑Fw(F),
where v runs over all vertices of V(D), F runs over all spanning directed forests of D, and Fv runs over all spanning directed forests including v as a root.In general,K(𝒟,t) is not an invariant under state in-splitting, but the following result shows that it indeed reflects some invariance.Corollary 7.
LetP be a row-stochastic matrix and t a real positive number. Let 𝒟 be a weighted digraph with weight matrix M=tP. Then K(𝒟,t)-K(𝒟~,t) is an integer independent of t.Proof.
LetO=(oi,j) be the outdegree matrix of D. Then we get by Lemma 1 that
(9)K(𝒟,t)=(1+t)∑vd(v)∑Fvw(Fv)∑Fw(F)=(1+t)tr(O·adj[I+(tI-M)])det[I+(tI-M)]=tr(O·[I-t1+tP]-1).
Since P is stochastic and 1/(1+t)∈(0,1), we have
(10)[I-t1+tP]-1=[I-r(tP)]-1=∑i≥0‍(M)iri,
where r=1/(1+t).
Therefore(11)K(𝒟,t)=tr(O·[I-t1+tP]-1)=∑i≥0‍tr{O(M)i}ri=W𝒟(r)+tr(O).
By Theorem4, we know that W𝒟(r) is an invariant under in-splitting; thus
(12)K(𝒟,t)-K(𝒟~,t)=tr(O)-tr(O~)∈ℤ.
The result follows.Lind and Tuncel defined a spanning tree invariantτ(𝒟) for Markov shifts in [3] as follows:
(13)τ(𝒟)=∑T‍w(T).
Here the weight matrix P of 𝒟 is an irreducible row-stochastic matrix, and T runs over all spanning trees of 𝒟.By considering the outdegree matrix as in Definitions3 and 6, we can define a new spanning tree invariant as
(14)τd(𝒟)=∑T‍d(T)w(T),
where T is as above, and d(T) denotes the outdegree of the root of T.Corollary 8.
τ
d
(
𝒟
) is an invariant under in-splitting.Proof.
LetP be the weight matrix of 𝒟 and thus row stochastic as in [3]. By the Matrix-Tree theorem (Theorem 2 in [8]), we have
(15)τd(𝒟)=tr(O·adj[I-P])=limt→1-{det[I-tP]·tr(O·[I-tP]-1)}=limt→1-{det[I-tP]·∑i≥0‍tr(OPi)ti}=limt→1-{det[I-tP]·(W𝒟(t)+tr(O))}.
By Theorem4, we know that W𝒟(t) is an invariant under state in-splitting. it is also well known that det[I-tP] is an invariant under state splitting. Therefore
(16)τd(𝒟)-τd(𝒟~)=limt→1-{det[I-tP]·(tr(O)-tr(O~))}.
Since tr(O)-tr(O~) is a constant and limt→1-det[I-tP]=0, we have
(17)τd(𝒟)-τd(𝒟~)=0.
The result follows.Let𝒟=(D,w) be a weighted digraph. The out-weighted line digraph L+(𝒟)=(L(D),w+) of 𝒟 is a weighted digraph defined in the following way: the vertex set of L(D) is E(D); ((u,v),(x,y))∈E(L(D)) if and only if v=x, and in this case, w+(((u,v),(x,y)))=w(x,y). Similarly, if we let w-(((u,v),(x,y)))=w(u,v) in the above definition, then we get the in-weighted line digraph L-(𝒟)=(L(D),w-). Galeana-Sánchez and Gómez show that L+(𝒟) can be obtained by sequences of state in-splittings from 𝒟 (see Proposition 2.2 in [9], which has a small typo there by stating L-(𝒟) can be obtained by sequences of state in-splittings). Now the following conclusion is an immediate result of Corollary 8.Corollary 9.
τ
d
(
𝒟
) is an invariant under out-weighted line digraph operation.


## 3. The State Out-Splitting Case

LetP be a row-stochastic matrix. Let 𝒟=(D,W) be the weighted digraph with weight matrix W=P. We first give the definition of state out-splitting, which is a little more complicated than the case of state in-splitting. Readers can refer to [3] for more details.Definition 10.
For a vertexu of D, let E*u denote the set of edges of D with initial end u. The state out-splitting of 𝒟 at u induces a new weighted digraph 𝒟~*=(D~*,w~) in the following way: let 𝒮*={S1*,S2*,…,Sr*} be a partition of E*u. Let qi denote the sum of the weights of edges in Si*. The vertex set of the new digraph is V(D~*)=(V(D)∖{u})⋃‍{u1,u2…,ur}. The edge set and weight of 𝒟~* are defined as follows.(i)
Forx,y∈V(D)∖{u}, (x,y)∈E(D~*) if and only if (x,y)∈E(D) and in this case w~(x,y)=w(x,y).(ii)
Fory∈V(D)∖{u}, (ui,y)∈E(D~*) if and only if (u,y)∈Si* and in this case w~(ui,y)=w(u,y)/qi.(iii)
Forx∈V(D)∖{u}, (x,ui)∈E(D~*) if and only if (x,u)∈E(D) and in this case w~(ui,x)=qiw(x,u).(iv)
If(u,u)∈Si*, then (ui,uj)∈E(D~*), for j=1,2,…,r, and in this case w~(ui,uj)=w(u,u)qj/qi.
In the definition ofWk(𝒟) and WD(t), by replacing outdegrees with indegrees, we get Wk*(𝒟) and W𝒟*(t); that is,
(18)Wk*(𝒟)=∑v‍d*(v)∑C∈Cvk‍w(C),W𝒟*(t)=∑k≥1‍Wk*(𝒟)tk,
where d*(v) is the indegree of v.Theorem 11.
LetP be a row-stochastic matrix. Let 𝒟 be the weighted digraph with weight matrix P. Then W𝒟*(t) is an invariant under state out-splitting, and can be computed as
(19)W𝒟*(t)=tr(O*·adj(I-tP))det(I-tP)-tr(O*),
where O* is the indegree matrix of D.Proof.
We just need to prove the invariance ofWk*(𝒟) for k≥1. Without loss of generality, if there is a loop at vertex u, we assume that it belongs to S1*, where 𝒮*={S1*,S2*,…,Sr*} denotes the partition of E*u as in the definition of state out-splitting.
We define the mapping(20)φ:⋃v∈V(D)‍Cvk(𝒟)⟶⋃v∈V(D~)‍Cvk(𝒟~*)
in the following way: for a closed walk C of 𝒟 with length k, if C=(u,u,…,u), then φ(C)=(u1,u1,…,u1); otherwise, we replace each maximum path of C of the form (u,u,…,u,u,v)(v≠u) with (u1,u1,…,u1,ui,v) if (u,v)∈Si*. By the definition of state out-splitting, it is not difficult to prove that
(21)φ:Cvk(𝒟)⟶Cvk(𝒟~*),
where v≠u, and
(22)φ:Cuk(𝒟)⟶⋃i=1r‍Cuik(𝒟~*)
are both bijections.
We now prove that they are also weight-preserving. In fact, ifC=(u,u,…,u), then w(C)=w(φ(C)), since w~(ui,ui)=w(u,u). On the other hand, for any walk of C of the form S=(r,u,…,u,u,v)(v≠u), we have w(S)=w(r,u)w(u,u)kw(u,v). (1)
If(u,v)∈S1*, we have
(23)w(φ(S))=w(r,u1)w(u1,u1)kw(u1,v)=q1w(r,u)w(u,u)kw(u,v)q1=w(S).(2)
If(u,v)∈Si*(i≠1) and k≥1, we have
(24)w(φ(S))=w(r,u1)w(u1,u1)k-1w(u1,ui)w(ui,v)=q1w(r,u)w(u,u)k-1(w(u,u)qi/q1)w(u,v)qi=w(S).(3)
If(u,v)∈Si*(i≠1) and k=0, we have
(25)w(φ(S))=w(r,ui)w(ui,v)=qiw(r,u)w(u,v)qi=w(S).
Thus the maps above are weight preserving. Sinced*(v)(v≠u) is the same for 𝒟 and 𝒟~*, and d*(u)=d*(u1)=d*(u2)=⋯=d*(ur), we know that Wk*(𝒟)=Wk*(𝒟~*), for k≥1, and the invariance of W𝒟*(t) follows.
The proof of the equality is similar to that of Theorem4.Similarly, we can defineτd*(𝒟) and prove that it is also an invariant under state out-splitting on the basis of the above result.Now, we consider some weighted digraphs from [10] in the following two examples.Example 12.
The weight matrices of two weighted digraphs are as follows:(26)A=[38121804515274717],B=[1706755638152821511545].
By some computation, we get that W𝒜(1/2)=1316/471, Wℬ(1/2)=1615/471, and W𝒜*(1/2)=Wℬ*(1/2)=1559/471. Thus B cannot be archived by a sequence of in-splittings or reverse operations, but may be archived by a sequence of out-splittings or reverse operations.Example 13.
The weight matrices of three weighted digraphs are as follows:(27)A=[13231323],B=[13232313],C=[23131323].
By some computation, we get that τd*(A)=2=τd(A), τd*(B)=8/3=τd(B), τd*(C)=4/3=τd(C). Thus for any pair of them, we cannot get one from the other and by a sequence of in-splittings or reverse operations either nor by a sequence of out-splittings or reverse operations.


## 4. Invariants for Weighted Digraphs with Double-Stochastic Matrices

Let𝒟=(D,P) be a weighted digraph. If the weight matrix P is column stochastic, the weight distribution after state out-splitting can be defined in an easier way, that is, without multiplying by the coefficients about qi in Definition 10. Under this definition, we can get that τd*(𝒟) is still an invariant under state out-splitting, the proof of which is similar to that of Corollary 8. We also know from [9] that the in-weighted line digraph can be obtained by a sequence of such state out-splittings, so the following result is immediate.Corollary 14.
Let𝒟=(D,P) be a weighted digraph. If the weight matrix P is column stochastic, then τd*(𝒟) is an invariant under in-weighted line digraph operation.Especially, if the weight matrix is doubly stochastic, we have the following result.Corollary 15.
Let𝒟=(D,P) be a weighted digraph. If the weight matrix P is doubly stochastic, then τd(L+(𝒟))=τd*(L-(𝒟)).Proof.
SinceP is doubly stochastic, we have by Corollary 8 that
(28)τd(L+(𝒟))=τd(𝒟)=tr(O·adj[I-P])
and by Corollary 14 that
(29)τd*(L-(𝒟))=τd*(𝒟)=tr(O*·adj[I-P]).
By Matrix-Tree theorem (Theorem 2 in [8]), we know that both adj[I-P] and adj[I-P′]=(adj[I-P])′ are row-constant matrices, where P′ is P transposed. Thus adj[I-P] is a constant matrix. Since the sum of indegrees is equal to that of outdegrees, the result follows.



---

*Source: 823769-2013-04-24.xml*