SQU Journal for Science, 2017, 22(1), 40-47                                 DOI: http://dx.doi.org/10.24200/squjs.vol22iss1pp40-47 

2017 Sultan Qaboos University  

40 

 

Incidence Matrices of Directed Graphs of 
Groups and their up-down Pregroups 

Wadhah S. Jassim  

Department of Mathematics, Faculty of Science, Soran University, Soran, Erbil, Iraq. 
Email: wadhahjasim@maths.soran.edu.krd. 

ABSTRACT: The aim of this work is to give a definition of the incidence matrices of the directed graph of groups, 

construct an up-down pregroup of the incidence matrices of the directed graph of groups and then give an 

algorithm for the up-down pregroup of the directed graph of groups. 

 

Keywords: Incidence matrix of X-labeled graph; up-down pregroup; directed graph of groups and incidence matrix 

of a directed graph of groups. 

سفل ما قبل زمرهاأ -على ألبيانات الزمر الموجه و  مصفوفات الوقوع  

 وضاح س. جاسم 

سفل ما قبل زمره أعلى أبناء  ،سفل ما قبل زمرها أ –على ت الوقوع لبيانات الزمرالموجه وأهو اعطاء تعريف لمصفوفا هدف بحثنا هذا :ملخصال

 الزمر الموجه.سفل ما قبل زمره لبيانات أ –على أمن ثم اعطاء خوارزمية لبناء ت الوقوع لبيانات الزمر الموجه ولمصفوفا

 

مصفوفة الوقوع لبيان بيانات الزمر الموجه و ،سفل ما قبل زمره أ -على أ ،X  –مصفوفة الوقوع للبيان المحمول بعناصر ا لمجموعه  : مفتاحيةالكلمات ال

 الزمر الموجه.
   

1. Introduction 

n [1] we gave the definition of the incidence Matrices of X- Labeled graphs. In [2], [3] we gave the definition of 

the directed graph of groups, constructed graph of groups for pregroups directly from the ordered tree of 

pregroups, and from that directed graph of groups we constructed the up-down pregroups, and then we 

showed those two pregroups are isomorphic. In [4] Rimlinger gave an example of a pregroup P of finite height; he 

said “but Jim Shearer and I spent a very long evening with the computer and verified the pregroup axioms”. I bear 

this point in mind. In [2], [3] we have a direct method to obtain examples of pregroups in the form of up-down 

pregroups from any directed graph of groups, but sometimes those graphs of groups are large, and then will take a 

long time to find those up-down pregroups. In [1] we defined the incidence matrices of X-labeled graphs. The main 

aim of this work is to represent the directed graph of finite groups in terms of the incidence matrices of X-labeled 

graphs, so that by adding certain conditions to allow the incidence matrices of the X-labeled graph to be more 

confident with the definition of the directed graph of groups; we can then write a computer program to record 

all elements of the up-down pregroup of that directed graph of groups, as an application of the incidence matrices of 

X-labeled graph. Therefore, this paper is divided into  s i x  sections. In section 2, we give the basic concepts of 

graphs, pregroups and incidence matrices of X-labeled graphs. In section 3, we give the definition of incidence 

matrices of directed graphs of groups. In section 4, we construct the up-down pregroup of the incidence matrices of 

the directed graph of groups. In section 5, we define an algorithm on the incidence matrices of the directed graph of 

groups, so we can then write a computer program for this algorithm. 

2. Basic concepts 

2.1 Pregroups 

 
The idea of pregroups goes back to Baer [5] and the definition of pregroup was given independently by Stallings 

[6] in 1971. The theory of pregroups has been developed by [4], Stallings [6], Hoare [7] and Hoare – Jassim [3] and 

others. We now return to the original definition of pregroups [6]. 

I 



INCIDENCE MATRICES OF DIRECTED GRAPHS 

41 

Let P be a set with an element 1  P and a mapping of a subset D of P  P into P, denoted 

by ( x, y)  xy. We shall say that xy is defined instead of ( x, y)  D. Suppose that there is an involution on P denoted 

by  x  x 
1 

, such that the following axioms hold: 

P1: x1 = 1x for all x  P, 

  P2: xx 
1  

 1  x 
1 

x for all x  P , 

P3: If xy is defined, then y 
1 

x 
1  

is defined and ( xy) 
1  

 y 
1 

x 
1 

. 

P4: if xy and yz are defined then (xy)z is defined if and only if x(yz) is defined, in which case the two are equal and we 

will say xyz is defined. 

P5: For any w, x, y and z in P, if wx, xy and yz are defined, then either wxy or xyz is defined . 

 

Hoare [7] showed that we could prove axiom P3 above by using the following proposition, and axioms P1, P2 and P4. 

 

Definition 2.2. [7]: For any x  P, put L(x)  {a  P: ax is defined}. We write x  y if L( y)  L( x), x  y if L( y)  

L( x)  and L( x)  L( y) , and x ~ y if L( x)  L( y) . It is clear that ~ is an equivalence relation compatible with . 

 

The following results are taken from Stallings [6] and Rimlinger [4]. (See [7] for shorter proofs). 

 

Proposition 2.3. 

 

   (i) If x  y or y  x , then x 
1 

y and y 
1 

x are defined. 

(ii) If xa and a 
1 

y are defined, then ( xa)(a 
1 

y) is defined if and only if xy is defined, in which case they are 

equal. 

 

  By using axiom P5 above (which will be denoted by P5(i)) Rimlinger [4] proved conditions P5(ii) 

and P5(iii) of Lemma 2.4 below. 

 

Lemma 2.4 [7]. The following conditions on elements of P are equivalent:  

P5(i). If wx,xy and yz are defined , then either  wxy  or  xyz  is defined . 

P5(ii). If x 
1

a  and a 
1 

y are defined but x 
1 

y is not , then a < x and a < y. 

P5(iii). If x 
1 

y is defined, then x  y or y  x .



Therefore, we will say P is a pregroup if it satisfies axioms P1, P2, P4, and the conditions of Lemma 2.4, 

above. The universal group of a pregroup P [13] is denoted by U (P) and has the following presentation  P; x.y  

xy whenever xy is defined, for x, y, P . Now if P is a pregroup, then (P, ) is tree -  like partial ordering; that is P/~ 

has a minimum element and, for any x,y and z in P , x  z and y  z we have x  y  or y  x . Moreover Rimlinger in 
[4] defined that for any element x in P, we say that x has finite height n  0, if there exists a maximal totally ordered 

subset {x0 , x1 ,, xn } of P such that 1  x0   x1     xn   x . He also showed that the elements of P form an 

order tree (denoted by O ) whose vertices , [x], are the equivalence classes of the elements of P under ~, and whose 

edges e, are formed by joining each vertex [x] of height n > 0 to the unique vertex [y] of height n – 1 satisfying 
][][ xy 

, 
and all edges e of O are directed away the  base vertex [ 0

x
] of height 0. In [8] Stallings constructed an 

up – down pregroup for a free group F generated by 
},{ baX 

 of infinite height, and he showed that U(P) the 

universal group of a pregroup P is isomorphic to F. In [2,3] we gave the definition of a directed graph of groups 

which consists of a directed graph Y, with a base vertex 


v and a spanning tree T, whose edges are directed away 

from the base vertex 


v , together  with a group v
G

for each vertex v and for each  directed edge Ye  , a subgroup 

e
G

of 
)( ei

G
 which is embedded in 

)( e
G


by e


which is defined by eee
ayya

1
)(




, where e
Ga 

and e
y

is the 

labeled of the edge e. It is denoted by 
),,,,,(

*

eev
vTYGG 

. We also constructed a directed graph of groups of P 

directly from the order tree O of P and then showed that the fundamental group  of a graph of groups 
),,,,,(

*

1 eev
vTYGG 

 is isomorphic to U(P) , We constructed an up – down  pregroup Q directly from the 

directed graph of groups 
),,,,,(

*

eev
vTYGG 

 of a pregroup P and we showed that U(Q) is isomorphic to 

),,,,,(
*

1 eev
vTYGG 

 and then that
)()( PUQU 

.  

 



WADHAH S. JASSIM  

42 

2.5   Incidence Matrices of X – Labeled Graphs 

In [1] we gave the definition of the incidence matrices of X – Labeled graphs (where an X-labeled graph is a 

directed graph with each edge labeled by an element x of the subset X of the group F and X generating the group 

F), and some definitions and results related to it.  Recall that from graph theory the directed graphs   are without 

loops, because we cannot define the incidence matrices of directed graphs . The incidence matrices of directed graphs  

 are with n vertices and m edges (i.e. it is mn   matrices 
][

ij
x

, where 
mjni  1,1

) such that: 

 

 

 

 

 

 

 

Since all edges e in X – Labeled graphs are labeled 
1

 XXx  and the incidence matrices of the directed graphs 
do not deal with the labeling of edges, we will put more conditions on the incidence matrices of directed graphs as 

below to obtain the definition of the incidence matrices of the X- Labeled graphs.  

 

Definition 2.6: Let  be any X – Labeled graph without loops (where
},{ baX 

), then the incidence matrix of the  

X – Labeled graph   is an mn   incidence matrix  
][

ij
x

, where 
mjni  1,1

) with 
ij

x
  entries such that   

Xxlabelse

ewithincident

Xxlabelse

ande

notisv

andei

v

if

v

if

if

x

x

x

j

j

j

j

i

j

i

i

ij




















)(

)(

0
1


 

N.B. Incidence matrices of X – Labeled graphs  will be denoted by
)(

X
M

. For example: the Cayley graph
),( XF

of the group F generated by
FX 

, the Cayley coset graph 
)(H

of the subgroup H of F, the core graph 

of the Cayley coset graph 
)(H




of the subgroup H of F and the product of core graphs
)(

~
)( KH




are X-

labeled graphs. 

 

Now if 
},{ baX 

 and the X – Labeled graph  has loops with labeling a or b, then choose a mid point on all edges 

labeled a or b to make all of them two edges labeled  aa  or bb respectively . Therefore in the rest of this work we will 

assume that all X – Labeled graphs are without loops.  

 

Definition 2.7: Let 
)(

X
M

 be an incidence matrix of X –Labeled graph . If 
)(

X
M

  doesn't contain any row i
r

 

with non zero entries 
ij

x
and ik

x
 in 

1
 XX  such that ikij

xx 
, then 

)(
X

M
 is called a folded incidence 

matrix of X – Labeled graph .  

 

Now we give the basic definitions and some results on the incidence matrix of X – Labeled graph
)(

X
M

,  as 

given in [1].  

 

Let 
)(

X
M

be an mn   incidence matrix  
][

ij
x

  of X – Labeled graphs , and let  i
r

 and 
j

c
 be a row and a 

column in 
)(

X
M

 respectively. If 
ij

x
 is a non – zero entry in the row i

r
, then i

r
 is called  an incidence row with  

the column 
j

c
 at the non – zero entry 

ij
x 1

 XX , and if the non – zero entry 
Xx

ij


 , then the row i
r

 is 

called the starting row  (denoted by 
))(

j
cs

of the column 
j

c
, and the row i

r
 is called the ending row ( denoted by 

)(
j

ce
 )  of the column 

j
c

 if 

1
 Xx

ij
. If the rows i

r
 and k

r
 are incident with column 

j
c

 at the non – zero entries 

ij
x

 and 
kj

x
 respectively, then we say that the rows i

r
 and k

r
 are adjacent. If 

j
c

 and h
c

are two distinct columns in 

)(
X

M
 such that the row i

r
 is incidence with the columns 

j
c

 and h
c

  at the non – zero entries  
ij

x
 and ih

x

respectively (where 

1
,


 XXxx

hij
), then we say that 

j
c

 and h
c

 are adjacent columns. For each column c 

there is an inverse column denoted by c  such that 
)()(),()( cscececs 

and cc  . The degree of a row i
r

 of 















)(1

0

)(1

ji

ji

ji

ij

evif

ewithincedencenotisvif

eivif

x





INCIDENCE MATRICES OF DIRECTED GRAPHS 

43 

)(
X

M
 is the number of the columns incident to i

r
and is denoted by

deg( ).
i

r
 If the row i

r
 is incident with at least 

three distinct columns 
j

c
, h

c
 and k

c
 at the non – zero entries  , then the row i

r
 is called a branch row. If the row i

r
 

is incident with   only one column   
j

c
 at the non- zero entry 

ij
x 1

 XX  and all other entries of i
r

 are zero, then 

the row i
r

 is called an isolated row. A scale in 
)(

X
M

 is a finite sequence of form 

kkk
rcrcrcrS k ,,,,,,, 121

112211





 

, where 
,1k
 

, jj rcs
j 


)(

, and 
1 1

( ) ( ),1 .j
j j j

e c r s c j k


 
   

.The starting row of a scale kkk
rcrcrcrS k ,,,,,,, 121

112211





 

 is the starting row 1
r

of the column 1
c

 and the 

ending row of the scale S is the ending row k
r

of the column 1k
c

  and we say that S is a scale from 1
r

 to k
r

 and S is 

a scale of length k for 
21  kj

. If 
)()( SeSs 

, then the scale is called a  closed scale. If the scale S is 

reduced and closed, then S is called a circuit or a cycle. If  
)(

X
M

 has no cycle, then  
)(

X
M

 is called a forest 

incidence matrix of  X – Labeled graph Γ. Two rows  i
r

 and k
r

in 
)(

X
M

 are called connected if there is a scale S 

in 
)(

X
M

 containing i
r

 and k
r

. Moreover 
)(

X
M

 is called connected if any two rows i
r

 and k
r

 in 
)(

X
M

are 

connected by a scale S. If 
)(

X
M

 is a connected  and forest , then 
)(

X
M

is called a tree incidence matrix of X – 

Labeled graph Γ. Let   be a subgraph of  Γ, then 
)(

X
M

is called  a subincidence matrix of 
)(

X
M

, if the set 

of rows and columns of  
)(

X
M

  are subsets of 
)(

X
M

 and if c is a column in 
)(

X
M

, then 
)(),( cecs

 and c

have the same meaning  in 
)(

X
M

 as they do in 
( ).

X
M 

 If  
)()( 

XX
MM

, then 
)(

X
M

  is called a 

proper subincidence matrix of 
)(

X
M

. A component of 
)(

X
M

is a maximal connected subincidence matrix of 

)(
X

M
. If 

)(
X

M
   is a subincidence matrix of 

)(
X

M
, and every two rows i

r
 and k

r
in 

)(
X

M
 are joined 

by at least one scale S in 
)(

X
M

, then 
)(

X
M

  is called spanning incidence matrix  of 
)(

X
M

 and 
)(

X
M

  

is called spanning tree of 
)(

X
M

 if 
)(

X
M

  is a spanning and tree incidence matrix . The inverse of 
)(

X
M

is 

an incidence matrix of 
1

X  - Labeled graph Γ.  
 

Now by direct calculations and the definitions above, we can prove the following results. 

 

Lemma 2.8: If 
)(

X
M

is a tree incidence matrix of X – Labeled graph Γ with n rows, then  
)(

X
M

 has n –1 

columns.  

3. Incidence matrices of directed graphs of finite groups. 

Definition 3.1: An incidence matrix of a directed graph of finite groups consists of  an incidence matrix of X- 

labeled graph 
)(

X
M

 with a spanning tree matrix of X- labeled graph 
)(TM

X , and a base row 1
rr 



, together 

with a finite group r
G

 for each row r, and a finite group c
G

 for each column c , such that:  

1) The columns of 
)(

X
M

 are directed away from 1
rr 



; 

2) Each column group c
G

is a subgroup of
)( ci

G
; 

3) Each column group c
G

is embedded in 
)( ct

G
by a fixed monomorphism c


, defined by ccc

ayya
1

)(



, 

c
Ga 

, and c
y

= 
)(

j
cs

 is the non- zero entrance of 
j

c
of 

)(/)( TMM
XX


. It is denoted by 

),),(),(,,(
cXXcr

rTMYMGG 


. 

 

N.B.: Any incidence matrix of a graph of groups may be made into an incidence matrix of a directed graph of groups, 

that by choosing 
)(TM

X , a base row 1
rr 



,  an orientation on columns and then identifying c
G

 with the image of  

)( ci
G

 under the 
)(

X
M

relevant monomorphism. 



WADHAH S. JASSIM  

44 

For each directed column 
),(

tjijj
xxc 

 in 
)(

X
M

, let 


c be c, and let 
),(

1

ijtj
xxc 



 be the inverse 

column with starting row 
)()(

1

jj
cecs 



, and 
)()(

1

jj
csce 



, where, jjij
ycsx  )(

, 

1
)(




jjtj
ycex

and 

j
y

are the entries of the column 
j

c
, such that 

1
j

y
, if 

),(
tjijj

xxc 
 is in 

)(TM
X . 

 

N.B. We will denote j
c

y
by

j
y

, (where, j
c

y
are nonzero entries of

),(
tjij ccj

yyc 
,  

Xy
ijc


, 

1
 Xy

tjc ), such 

that j
c

y
is equal to 1 or -1, if  

)(TMc
Xj


. 

Example: In this example, we will give a directed graph of groups and then, construct the incidence matrix  of this 

directed graph of groups 
),),(),(,,(

cXXcr
rTMYMGG 


. 

 

Let the directed graph of groups 
),,,,,(

*

eev
vTYGG 

 be as follows:  

 

 

 1 

 1  

 

 

 1 

 1                                              1 

 

 

 

 

Figure 1. The directed graph of groups constructed in [3] p72 of the pregroup given in [4] p41. 

The incidence matrix of the above directed graph of groups 
),),(),(,,(

cXXcr
rTMYMGG 


 is as below: 

 

1 2 3 4 5 6 7 8

1

2

3

1 1 1

4

1

5

6

7

{1} {1, } {1, } {1} {1} {1} {1, } {1, }

{1} 1 0 0 0 1 1 0 0

{1, } 1 1 0 0 0 0 0

{1, , , , } 0 1 0 0 0 0 0 0

{1, , , } 0 0 0 0 1 0

{1} 0 0 0 1 0 0 0

{1, } 0 0 0 0 0 1 1 1

{1, , , } 0 0 0 0 0 0 0 1

b b a a

e e e e e e e e

r

b r x

b b r

a x bx ax bx r x

r

a r

a a r

 





 

  













  

Figure 2. The incidence matrix of the directed graph of groups given in Figure 1 above. 

}1{
1


 VV

  }1{1e
},1{

2
bV

 

},1{
2

be
 

},,,1{
3

bbV 
 

x

 

        
},1{

3
be

    

 

                     
},,,1{

11

4
bxaxbxxaV



      

4
}1{ e

 


   

            
7

},1{ ea
 

  6
},1{ Va

 

6
}1{ e

 

                  
7

},,,1{ Vaa 
 

8
},1{ ea

 

5
V

 

}1{
5

e
 



INCIDENCE MATRICES OF DIRECTED GRAPHS 

45 

4. The up-down pregroup of an incidence matrix of a directed graph of finite groups. 

In this section we construct the up- down pregroup of the incidence matrix of a directed graph of groups as 

below;  

Let 
)(

X
M

be the incidence matrix of a directed graph of groups 
),),(),(,,(

cXXcr
rTMYMGG 


.  

The fundamental group of 
))((

11


X
M

has the following presentation: 

 



)(/)(1),(1,),(;,

1
TMYMcyTMcyGaaayyyG

XXcXccccccr


. Now for each 

directed column 
)(YMc

X


, let c be also denoted by 
1

c and let 
1

c denote the inverse column with 

)()(
1

cecs 


and 
)()(

1
csce 



; also let i
c

y
be of form nn

gyygygw n ..... 21
2110


 

, where 
1

i  and 

1
i

 
and  

121

121
,,, 





 n
n

ccc 
 is a circuit at 


r , with rows 






 rrrrr

n 121
,,, 

 say, and where each i
g

is in 

ir
G

. A word of this form and any subword of it is reduced if it contains no subword cc
yay ..

1

 or 

1
).(.



ccc
yay 

, 

where c
Ga 

. If it does contain such a subword, we can , using the relations, substitute 
)(a

c


 or a respectively to 

obtain a shorter word of the given form representing the same element. Thus each element of the fundamental group is  

represented by a reduced word w of this form. Its inverse is representable by the word 
1

w defined in the usual way. 
Moreover, by [13], the reduced word representing any element is unique modulo a succession of interleaving, i.e. 

substituting 
 hayga

cc
)(..

1




for 
 ... hyg

c  or vice – versa for any c
Ga 

. Let
)(

X
M

be the incidence 

matrix of the directed graph of groups 
),),(),(,,(

cXXcr
rTMYMGG 


and let n
cccq ,,,

21


 be an upward 

scale in 
)(

X
M

 which is a finite sequence of columns directed away of the base row r . Let the rows of the scale q 

be n
rrrr ,,,

21


. A word of type q is a word 12211
..,....




nnn
gygygygw 

, where i
ri

Gg 
, 

11  ni , and every word w must be reduced and i
y

is the non- zero entry of the starting row
)(

i
cs

 of the 

column i
c

. Now Let k
cccq ,,,

21


and h
cccq  ,,,

21


be upward scales in 
)(

X
M

 both starting at 


r . 

Let 132211
.......




kkk
gyggygygw 

 and 132211
.......



hh

yggygygw 
 be words of type q and 

q

respectively, where hk  .  The word w is called an initial subword of the word w , written ww  , if jj
cc 

, 

and hence jj
cc

yy 
, for 

kj 1
, and if  

jjjjjj
gygyggygyg 












...........

111

1

1

1

1

1

1

1

1

1 
 is an element of 

,
jr

G
 for each j.  

Lemma 4.1: The relation " is an initial subword of " is both transitive and tree incidence matrix like, that is ww   

and ww   , then ww  , and if ww  ,  
ww  , then either ww   or ww  .  

Proof: The result follows directly from the definition.  

Now let k
cccq ,,,

21


and h
cccq  ,,,

21


be upward scales in
)(

X
M

 both of them starting at 


r

and ending at the same row r, and let k
ggygygw .....

32211


 and  h
ggygygw  ......

32211


 be words of 

type q and  
q

respectively, such that the elements h
g

 and 

1

k
g

are in r
G

, and then  such a word
1ww is called an up – down 

word.  

For example, the word 
1.1.1..1...1 xb

is an up-down word, from Figure 2 derived from the upward scales q, with 

rows 


r  and 5
r

, and 
q

, with rows 


r , 542
&, rrr

. 

Let 
))(( 

X
MQ

be the set of all up-down words of the incidence matrix of a directed graph of groups
)(

X
M

. 

Reducing an up-down word in 
)(

X
M

 gives another up-down. Therefore, we assume that such a word is reduced.  

We use 
1ww  to denote an up-down word. 

Lemma 4.2: Let 
1ww  and 

1zz be reduced up-down words, then 
)()(

111   zzww
is in 

))(( 
X

MQ
 if and 

only if w is an initial segment of z or z is an initial segment of w . 

Proof: Since the words 
1ww  and 

1zz are both reduced, so reduction can only take place in the word 
)()(

111   zzww
between the last c

y
 of 

1w and the first one of z . 



WADHAH S. JASSIM  

46 

Moreover 
)()(

111   zzww
reduces to an up-down word if and only if either all c

y
in w or all c

y
in z are 

eliminated when putting 
)()(

111   zzww
in reduced form. This happens if and only if w is an initial segment of 

z or z is an initial segment of w respectively. 

Now we show that 
))(( 

X
MQ

 is a pregroup. Since 
))(( 

X
MQ

is a subset of 
))((

11


X
M

, so 

))(( 
X

MQ
satisfies conditions 

,
1

P
2

P
and 4

P
. It remains to be shown that 

))(( 
X

MQ
satisfies condition 5

P
. 

Define 
))}((.;{)(

1111




X
MQwwuuuuwwL

, for 
))((

1




X
MQww

, as before. 

Lemma 4.3: Let 
1ww  and 

1zz be reduced up-down words, then zw  , implies that
11   zzww . 

Proof: Suppose that zw  . To show
11   zzww , we must show that

)(
1zzL

 is a subset of 
1

( ).L w w


If 

)()(
111   zzuu

 is in
))(( 

X
MQ

, for some 
))((

1




X
MQuu

, then , by Lemma 4.2, z is an initial segment 

of u or u is an initial segment of z ( i.e. uz   or )zu


 respectively. Since zw  , in either case, by 

Lemma 4.1, we have uw   or )wu


 
and then by Lemma 4.2 again, 

)()(
111   wwuu

 is defined in

))(( 
X

MQ
. Therefore 

)(
1zzL

 is a subset of 
1

( ).L w w


Hence
11   zzww . 

Theorem 4.4: 
))(( 

X
MQ

is a pregroup. 

Proof: To show 
))(( 

X
MQ

is a pregroup, we will show that
))(( 

X
MQ

satisfies condition 
)(

5
iiiP

 of Lemma 2.4. 

Therefore let 
1ww  and 

1zz be reduced up-down words in
))(( 

X
MQ

, and suppose that 
)()(

111   zzww
is 

defined in
))(( 

X
MQ

. Hence by Lemma 4.2, we have wz   or .w z   Thus by Lemma 4.3, 
11   zzww  

or 
1 1

.z z w w
    Therefore condition 

)(
5

iiiP
 of Lemma 2.4 holds in

))(( 
X

MQ
. 

Definition 4.5: The set of all up – down words of the incidence matrix of a directed graph of groups
))(( 

X
MQ

 is 

called the up- down pregroup of 
),),(),(,,(

cXXcr
rTMYMGG 


the Incidence matrix of a directed graph of  

groups, where Q is the up- down pregroup of the directed graph of groups, as shown in [2] and [1].  

Theorem 4.6: The Universal group of 
))(( 

X
MQ

 (it is denoted by 
))((( 

X
MQU

) is isomorphic to the 

fundamental group 
))((

11


X
M

.  

Proof: Since every element in 
))(( 

X
MQ

is an element in 
))((

11


X
M

, and since the tree incidence matrix  

)(TM
X  spans 

)(YM
X and is directed away from r , every element of 

))((
11


X

M
can be written as a 

product of elements of
))(( 

X
MQ

. Moreover the partial multiplication in 
))(( 

X
MQ

implies the relations of 

))((
11


X

M
. 

5. An algorithm for the up-down Pregroup of incidence matrices of directed graphs of groups. 

Let 
),),(),(,,()(

cXXcrX
rTMYMGGM 



be the incidence matrix of a directed graph of groups, then 

we use the representation of the directed graph of groups of an up-down pregroup, to write down all the elements of the 

up-down pregroup of that graph of groups by applying the following algorithm. The steps are given below: 

I) Find all up words 1211
......




nnn ijiiji
gyggygw 

of type upward scales                                  

132211
,,,,,,),(






nnn iiiiiiii
rcrrcrcrrq 

, where ik
ri

Gg 
, nk 1  and kj

y
is the non- zero entrance of the 

row k
i

r
 which is the starting of the column k

j
c

, as defined  above and then proceed step II;  

II) 1) If two up words  1211
.....




nnn ijiiji
gyggygw 

 and  1211
......



mmm ijiiii

gyggygw 
 , ending at the 

same row
i

r
, (i.e. row i

r
contains non-zero entrances of forms 

1

ij
x

 and 
1

ik
x

), then makes one of them an up word, 

say 1211
......



mmm ijiiii

gyggygw 
 and makes the  other up word  

1
.....

211 


nnniji
gyggygw 

 , down word 

by changing the direction of all i
g

,  columns and its entrance 
j

y
 to be

111111

111
.....






ijiji
gygygw

nnn


, and  by,         

identifying them we get an up-down  word 
1

.ww
111

32211 111
.............






ijjiimm
gyyggyggygyg

nnm


, 

(where, 1111
1

.





ninnn
riii

Gggg
). Then proceed to step III; 



INCIDENCE MATRICES OF DIRECTED GRAPHS 

47 

2) If the up words 1211
.....




nnn ijiiji
gyggygw 

  end at an isolated row, then change the direction of all columns 

and its label to be  

111111

111
.....






ijiji
gygygw

nnn


, and by identifying them with the row i
r

that both of them end 

with i
r

, then we get an up-down word  
1

.ww 1211
.....

nnn ijiiji
gyggyg 

.

11111

111
.....



 ijiji
gygyg

nnn


 

 = 1211
.....



nnn ijiiji

gyggyg 
.

1111

11
.....



ijij
gygy

nn


, ( where, 1111
1

.





ninnn
riii

Gggg
). Then proceed to step 

III; III) If there is no other up-down word, then stop. 

Proposition 5.1: All up words 1211
......




nnn ijiiji
gyggygw 

of type upward scales in  

),),(),(,,()(
cXXcrX

rTMYMGGM 



 are same as all up words 1211

......



nnn ijiiji

gyggygw 
of type  

upward paths in 
),,,,,(

ecr
vTYGG 


. 

Proof: Since all vertices v and edges e in 
),,,,,(

ecr
vTYGG 


are represented by rows 
r

and columns 
c

in 

))(
X

M
, and associated vertex groups v

G
 and edge groups e

G
are represented by row groups 

r
G

and columns 

groups c
G

respectively, with entrances 
ij

x
of the labeled e

y
of the edges of 

),,,,,(
ecr

vTYGG 


such that 

1
e

y
if Te  and 

1
e

y
if TYe  . Therefore the direction and the labeling of columns of

)(
X

M
, are same 

as in 
( , , , , , ).

r c e
G G Y T v 



 Hence all up words 1211
......




nnn ijiiji
gyggygw 

of type upward scales in 
)(

X
M

are 

same as all up words 1211
......




nnn ijiiji
gyggygw 

of type upward paths in
),,,,,(

ecr
vTYGG 


. 

Proposition 5.2: The algorithm must stop. 

Proof: Since the size of 
)(

X
M

is mn   and all vertex groups and edge groups are finite, so )(XM is finite 

incidence matrix. By step I, we get all reduced up- words, by step II we get all up- down reduced words, and then by 

step III, we will get all up- down reduced words. Since the origin X- labeled graph does not contain loops, so the set of 

all reduced up-down words is finite and then the algorithm must be stop after a finite time. 

6. Conclusion 

We have given a new application for the incidence matrices of X-labeled graphs. This application is the incidence 

matrices of directed graph of finite groups. Therefore, we have added certain conditions to allow the incidence of X- 

labeled graphs to be more confident with the definition of the directed graph of finite groups. By this way we can write 

a computer program to record all elements of the up- down pregroups of that the directed graphs of finite groups. 

References  

1. Jassim, W.S. Incidence Matrices of X-Labeled Graphs and an application, Sultan Qaboos University Journal for 
Science, 2009, 14, 61-69. 

2. Hoare, A.H.M. and Jassim, W.S. Directed graphs of groups and their up-down pregroups, Faculty of Science 
Bulletin, Sana'a University, 2004, 17, 137-154.  

3. Jassim, W.S. Pregroups and graphs of groups, Ph.D. Thesis, Birmingham University, 1992. 
4. Rimlinger, F. Pregroups and Bass – Serre theory. American Mathematical Society Memoirs, 1987. 
5. Baer, R. Free Sums of groups and their generalizations III. American Journal of Mathematics, 1950, 647-670. 

6. Stallings, J.P. Group theory and Three dim. Manifolds. Yale Monographs, 1971. 
7. Hoare, A.H.M. Pregroups and Length functions. Proceedings of the Cambridge Philosophical Society. 1988, 21-

30. 
8. Stallings, J.P. Adyan Groups and Pregroups, Essays in group theory, MSRI Publications 8ed. By S.M. Gersten, 

1987. 

9. Abdu, K.A. Representing Core graphs and Nickolas's Algorithm. M.Sc. Thesis, Baghdad University, 1999. 
10. Chiswell, I.M. Abstract Length functions in groups. Proceedings of the Cambridge Philosophical Society. 1976, 

417-429. 

11. Jassim, W.S. Directed Core Graphs and their up-down pregroups, Al-Mustansiriya Journal of Science, 2006, 
17(4): 68-81. 

12. Lyndon, R.C. Length functions in groups. Mathematica  Scandinavica, 1963, 209-234. 
13. Serre, J.P. 1968. Groupes discrets. College de France. Translation, Trees. Springer Verlag, 1980. 
 

 

Received 10 September 2015          

Accepted 7 December 2016