Citation
Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of [0,1]-matrices

Material Information

Title:
Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of [0,1]-matrices
Creator:
Siewert, Daluss J
Publication Date:
Language:
English
Physical Description:
126 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Bipartite graphs ( lcsh )
Directed graphs ( lcsh )
Bipartite graphs ( fast )
Directed graphs ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 124-126).
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Daluss J. Siewert.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
45217305 ( OCLC )
ocm45217305
Classification:
LD1190.L622 2000d .S55 ( lcc )

Downloads

This item has the following downloads:


Full Text
BICLIQUE COVERS AND PARTITIONS OF
BIPARTITE GRAPHS AND DIGRAPHS
AND RELATED MATRIX RANKS OF
{0,1}-MATRICES
by
Daluss J. Siewert
B.S., University of Alaska Anchorage, 1994
M.A., University of Colorado at Boulder, 1996
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2000


This thesis for the Doctor of Philosophy
degree by
Daluss J. Siewert
has been approved
by
J. Richard Lundgren
Stanley E. Payne
Stephen C. Billups
Margaret B. Cozzens
William J. Wolfe
Date


Siewert, Daluss J. (Ph.D., Applied Mathematics)
Biclique Covers and Partitions of Bipartite Graphs and Digraphs
and Related Matrix Ranks of {0,1}-Matrices
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
During the past twenty years there has been considerable research on
the biclique cover and partition numbers of bipartite graphs and digraphs and
several related matrix ranks. These include the boolean rank, nonnegative in-
teger rank, term rank, and real rank. The main goal of the work in this thesis
is to find classes of graphs with equal biclique cover and partition numbers or
classes of {0,l}-matrices with at least two of the matrix ranks equal.
In 1991, Lundgren and Maybee showed that all four matrix ranks
of nearly reducible matrices are equal. In 1977, Lovasz and Plummer gave
bipartite graph representations of nearly decomposable and fully indecompos-
able matrices. New results in this thesis complement this work. Three of the
matrix ranks for nearly decomposable matrices are determined and bipartite
graph representations of nearly reducible and irreducible matrices will be given.
In 1991, de Caen proved that the real rank of an n-tournament ma-
trix is at least n 1. This lower bound implies that the term rank of an
n-tournament matrix is also at least n 1. A new result in this thesis char-
acterizes those tournaments with term rank n. The classification of singular
tournaments remains an open problem, but some results are known for spe-
cific subclasses of tournaments. In 1990, Shader characterized singular upset
tournament matrices and proved that the nonnegative integer rank of upset
tournament matrices is equal to the real rank.
New results concerning the boolean rank and term rank of upset tour-
nament matrices are discussed in this thesis. Specifically, a characterization
of upset tournament matrices with respect to their boolean rank and a best
m


possible lower bound for the boolean rank is given. In addition, it is shown
that the number of nonisomorphic upset tournaments with equal biclique cover
and partition numbers can be given in terms of convolutions of the Fibonacci
sequence. These results, together with Shaders work, give a complete char-
acterization of upset tournament matrices with respect to each rank and with
respect to their biclique cover and partition numbers.
This abstract accurately represents the content of the candidates thesis,
recommend its publication.
Signed
J. Richard Lundgren


DEDICATION
This thesis is dedicated to my parents and my fiancee Lynette.


ACKNOWLEDGMENTS
It has been a privilege to do research and complete this thesis un-
der the direction of my advisor, J. Richard Lundgren. I thank him for his
encouragement, his guidance, and his generosity. The many trips to Rockies,
Avalanche, and Nuggets games were much appreciated. I will strive to follow
his example of excellence in both teaching and research. I also want to thank
my thesis committee for their time and their advice.
Much of the work in this thesis was presented at the Discrete Mathe-
matics Seminar at the University of Colorado at Denver. I would like to thank
the discrete math group, faculty and students, for listening to my talks and
offering advice. I greatly appreciated this opportunity to present and refine
this material.
I would like extend my appreciation to the Graduate Committee at
the University of Colorado at Denver for offering me teaching assistantships
each semester. This type of financial support not only allowed me to pursue
my degree, but gave me significant teaching experience that proved invaluable
during the job search process.
Over the past ten years of undergraduate and graduate school, faculty,
friends, and family have provided immeasurable amounts of encouragement. I
will name just a few of them here. Brian Wick, Hilary Davies, Roi Miranda,
and Marty Calderone provided the inspiration to get me to graduate school.
My office-mates and friends, Faun Doherty, Janine Kennedy, Cary Miller, Dave
Brown and Chris Mehl were always helpful and supportive. My brother and his
wife, Dalynn and Tammy Siewert, and my parents, Manley and Arlene Siewert,
were always quick with words of encouragement. Finally, I want to thank my
ftnacee, Lynette Buss, for her unconditional love and unfailing support as I
wrote this thesis. I will always be indebted to you.
Daluss. J. Siewert
Denver, Colorado


CONTENTS
Figures .......................................................... ix
Chapter
1. Introduction................................................... 1
1.1 Background...................................................... 1
1.2 Preliminaries................................................... 4
1.2.1 Biclique Cover and Partition Numbers............................ 4
1.2.2 Boolean Rank.................................................... 6
1.2.3 Nonnegative Integer Rank........................................ 7
1.2.4 Real Rank...................................................... 10
1.2.5 Term Rank...................................................... 11
1.2.6 Lower Bounds................................................... 12
1.2.7 Basic Rank Relationships....................................... 13
2. Classes With Equal Ranks.......................................... 15
2.1 Bipartite graphs............................................... 15
2.2 Digraphs....................................................... 19
2.3 Examples With Dominos.......................................... 21
3. Matrices.......................................................... 25
3.1 Nearly Reducible Matrices...................................... 25
3.2 Nearly Decomposable Matrices .................................. 28
3.2.1 Preliminaries.................................................. 28
3.2.2 Ranks.......................................................... 31
3.3 Bipartite Graph Representations ............................... 39
4. Tournaments .......................................... 47
4.1 Preliminaries.................................................. 47
4.2 General Results................................................ 48
4.3 Regular and Near-Regular Tournaments........................... 51
4.4 Boolean Rank................................................... 54
4.5 Classes With All Four Ranks Equal.............................. 63
4.5.1 Rotational Tournaments......................................... 63
4.5.2 Un Tournaments................................................. 70
4.6 Existence of Strict Inequalities............................... 73
5. Upset Tournaments................................................. 84
5.1 Definitions and Standard Form.................................. 84
5.2 Term Rank...................................................... 87
5.3 Real Rank and Nonnegative Integer Rank......................... 89
5.4 Boolean Rank................................................... 91
vii


5.5 Equal Biclique Cover and Partition Numbers................... 106
6. Summary ..................................................... 118
6.1 Bipartite.................................................... 118
6.2 Digraphs..................................................... 119
6.3 Nearly Reducible Matrices.................................... 120
6.4 Nearly Decomposable Matrices ................................ 120
6.5 Tournaments ................................................. 121
6.6 Upset Tournaments............................................ 123
7. References................................................... 124
viii


FIGURES
1.1 Digraph D........................................................ 5
1.2 The digraph D, given in Figure 1.1, can be covered with two
bicliques........................................................ 5
1.3 The digraph D, given in Figure 1.1, can be partitioned into three
bicliques........................................................ 5
1.4 Maximum matching in the bipartite graph B(A).................... 12
2.1 Domino.......................................................... 15
2.2 Digraph that is minimally strong but not unipathic.............. 21
2.3 Bipartite graph with bc(B') = bp(B') = n and more than
dominos......................................................... 22
3.1 Minimally strong digraph with b(A(D)) = rz+(A(D)) = r(A(D)) =
t(A(D)) = k............................_..................... 27
3.2 Perfect matching of a uniform subgraph B........................ 41
3.3 Perfect matchings MH of H C B(A) and M of B(A^)................. 43
3.4 Every edge in the bipartite graph B is in a perfect matching of
a uniform subgraph Bj........................................... 44
4.1 U5 ............................................................. 71
4.2 Only two possible forms of bicliques in the biclique partition P
of T(A) ........................................................ 78
5.1 Upset tournament in standard form. Upset arcs are directed
upward and non-upset arcs (not shown) are directed downward.
The arcs tq > t>2 and vn-\ > vn are always present in the
tournament................................................. 85
5.2 For upset tournaments in standard form, there exists a unique
path from vertex tq to vertex vn and this path includes the arcs
(tq,tq>) and {vn-i,vn)..................................... 86
5.3 Structures of upset path that cause singularity................ 90
5.4 Subgraphs which reduce the biclique covering number............. 92
5.5 Hq and an H or two H's can share at most one arc............... 95
5.6 Upset path which maximizes copies of the subgraphs H0 and H. 105
5.7 bA + b5 = be................................................... 108
IX


1. Introduction
1.1 Background
The covering of bipartite graphs and digraphs with bicliques has ap-
plications in many areas. Amilhastre et al. [AVJ98] gave references regarding
applications in automata and language theories, graph compression, partial
orders, artificial intelligence, and biology [NMWA78]. During the past twenty
years there has been considerable research on the biclique cover and partition
numbers of bipartite graphs and digraphs and several related matrix ranks
including the boolean rank, nonnegative integer rank, term rank, and the
real rank. See Alexe et al. [AAF+], Brualdi et al. [BHM80], de Caen et
al. [dCGP81], Fishburn and Hammer [FH93], Gregory et al. [GJLP91], Mon-
son et al. [MPE95], Orlin [Orl77], and Shader [Sha90]. Biclique covering and
partitioning numbers and related matrix ranks for some individual classes of
graphs have been determined. For example, for domino-free bipartite graphs,
see Amilhastre et al. [AVJ98]; for tournaments, see Bain et al. [BLM92] and
Shader [Sha90]; for unipathic digraphs, see Hefner et al. [HLM93]; and for
directed cockades, see Lundgren and Maybee [LM91]. The main goal of the
1


work in this thesis is to find classes of graphs with equal biclique cover and
partition numbers or classes of {0,l}-matrices with at least two of the matrix
ranks equal.
In 1991, Lundgren and Maybee showed that all four matrix ranks of
nearly reducible matrices are equal [LM91]. In 1977, Lovasz and Plummer gave
bipartite graph representations of nearly decomposable and fully indecompos-
able matrices [LP77]. New results in this thesis will complement this work.
Three of the matrix ranks for nearly decomposable matrices are determined
and bipartite graph representations of nearly reducible and irreducible matri-
ces will be given.
In 1991, de Caen proved that the real rank of an n-tournament matrix
is at least n 1 [dC91]. This lower bound implies that the term rank of an
n-tournament matrix is also at least n 1. A new result in this thesis char-
acterizes those tournaments with term rank n. The classification of singular
tournaments remains an open problem, but some results are known for spe-
cific subclasses of tournaments. In 1990, Shader characterized singular upset
tournament matrices and proved that the nonnegative integer rank of upset
tournament matrices is equal to the real rank [Sha90]. New results concerning
the boolean rank and term rank of upset tournament matrices are discussed in
this thesis. Specifically, a characterization of upset tournament matrices with
2


respect to their boolean rank and a best possible lower bound for the boolean
rank is given. In addition, it is shown that the number of nonisomorphic upset
tournaments with equal biclique cover and partition numbers can be given in
terms of convolutions of the Fibonacci sequence. These results, together with
Shaders work, give a complete characterization of upset tournament matrices
with respect to each rank and with respect to their biclique cover and partition
numbers.
Chapter 1 will give the necessary background and preliminary infor-
mation concerning biclique covers and partitions and related matrix ranks.
Chapter 2 will focus on classes of graphs where at least two of the matrix
ranks are equal for the corresponding adjacency matrix. Chapter 3 will give
the ranks of nearly reducible and nearly decomposable matrices and will dis-
cuss a bipartite graph representation of each of these classes. Chapter 4 will
give rank results for tournaments in general and for some specific classes of
tournaments. Chapter 5 gives a complete classification of upset tournaments
with respect to each rank and shows that the number of upset tournaments
with equal biclique cover and partition numbers can be given in terms of con-
volutions of the Fibonacci sequence. Chapter 6 summarizes the known results,
both new and old, and gives some open problems.
3


1.2 Preliminaries
Throughout this thesis, A(D) will be the adjacency matrix corre-
sponding to the digraph D(A) and A(B) will be the reduced adjacency matrix
corresponding to the bipartite graph B(A). The reduced adjacency matrix of
a bipartite graph is the submatrix of the adjacency matrix that corresponds
to the arcs from one set of the bipartition to the other set of the bipartition.
That is, if A is the adjacency matrix of a bipartite graph B. then
0's A(B) 1
A(BY O's
1.2.1 Biclique Cover and Partition Numbers The biclique
cover number of a graph G, denoted by bc(G), is the smallest number of com-
plete bipartite subgraphs that cover the edges of G. For example, the digraph
D, given in Figure 1.1, can be covered with two bicliques. See Figure 1.2. The
bicliques in the covering must have the same orientation as in the digraph D
and all the arcs my be from one bipartition set to the other bipartition set.
The biclique partition number of a graph G, denoted by bp(G), is the
smallest number of complete bipartite subgraphs that partition the edges of G.
For example, the digraph D, given in Figure 1.1, can be partitioned into three
bicliques. See Figure 1.3.
4


Figure 1.1. Digraph I).
Figure 1.2. The digraph D, given in Figure 1.1, can be covered with two
bicliques.
Figure 1.3. The digraph D, given in Figure 1.1, can be partitioned into three
bicliques.
5


1.2.2 Boolean Rank The boolean rank of anmxn {0,l}-matrix
A, denoted by b(A), is defined to be the smallest k for which there is an
m x k {0,l}-matrix B and a k x n {0,l}-matrix C such that A = BC where
boolean arithmetic is used (1 + 1 = 1). The boolean rank of a {0,l}-matrix
A is equivalent to the minimum number of {0,l}-matrices of rank one whose
boolean sum is A. For example, let A = A(D) be the adjacency matrix of the
digraph given in Figure 1.1. Then
A
' 0 1 0 1 1 1'
0 0 0 1 1 1
0 1 0 1 1 1
0 0 0 0 0 0
0 1 0 1 0 0
. 0 1 0 1 0 0 _ 6x6
' 1 1'
1 0
1 1 0 0 0 1
0 0 0 1 0 1
0 1
. 0 1 _ 6x2
' 1'
1
1 0 [ 0 0 0 1 1 1
0
0
1 1
0 0
2x6
1
0
1
0
1
1
0 1 0 1 0 0 ]
6


o 0 0 1 1 1' o 1 0 1 0 o
0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 1 1 1 1 0 1 0 1 0 0
0 0 0 0 0 0 + 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 1 0 0
i o 0 0 0 0 0 _ _ 0 1 0 1 0 0 _
The two rank one matrices correspond to the two bicliques used to cover the
digraph D = D(A). See Figure 1.2. Every factorization

Bn x k Ck x m
of A into {0,l}-matrices corresponds to a biclique covering of size k. Conversely,
every biclique covering of size k, corresponds to a factorization
Anxm BnxkCkxm
of A into {0,l}-matrices.
The same result holds for bipartite graphs. Thus, we have Lemma 1.2.1.
Lemma 1.2.1 (Gregory et al. [GJLP91]) If D is a digraph and B is a
bipartite graph, then
b(A(D)) = bc(D) and b(A(B)) = bc(B).
1.2.3 Nonnegative Integer Rank The nonnegative integer rank
of an m x n matrix A, denoted by rz+(A), is defined to be the smallest k for
7


which there is an m x k matrix B and a k x n matrix C, over the nonnega-
tive integers, such that A = BC. If A is a {0,l}-matrix, then B and C are
{0,l}-matrices. The nonnegative integer rank of a matrix A is equivalent to the
minimum number of rank one matrices, over the nonnegative integers, whose
sum is A. For example, let A = A(D) be the adjacency matrix of the digraph
given in Figure 1.1. Then
A
0 1 0 1 1 1
0 0 0 1 1 1
0 1 0 1 1 1
0 0 0 0 0 0
0 1 0 1 0 0
0 1 0 1 0 0
1 1 0 '
1 0 0 ' 0 0 0
1 1 0
0 0 0
0 1 1
0 1 1 _ 6x3
1'
1
1 0 [ 0 0 0 1
0
0
6x6
0 0 0 1 0 0
0
1
0
1
1
3x6
[ 0 1 0 0 0 0 ]
0
0
0
0
1
1
[ 0 0 0 1 0 0 ]
8


' 0 0 0 1 1 1' ' 0 1 0 0 0 0 ' ' 0 0 0 0 0 o
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 + 0 0 0 0 0 0 + 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
1 o 0 0 0 0 0 _ _ 0 1 0 0 0 0 _ _ 0 0 0 1 0 0 _
The three rank one matrices correspond to the three bicliques used to partition
the digraph D = D(A). See Figure 1.3. Every factorization
A
nxm
B
nxk
C'kxm
of A into matrices B and C over the nonnegative integers corresponds to a
biclique partition of size k. Conversely, every biclique partition of size k, cor-
responds to a factorization
of A into matrices B and C over the nonnegative integers.
The same result holds for bipartite graphs. Thus, we have Lemma 1.2.2.
Lemma 1.2.2 (Gregory et al. [GJLP91]) If D is a digraph and B is a
bipartite graph, then
rz+(A(D)) = bp(D) and rz+(A(B)) = bp(B).
9


1.2.4 Real Rank The real rank (usual rank) of the matrix A,
denoted by r(A), can be defined as the smallest k for which there is an m x k
matrix B and a, k x n matrix C, over the real numbers, such that A = BC.
The real rank of a matrix A is equivalent to the minimum number of rank one
matrices, over the real numbers, whose sum is A. This factorization into rank
one matrices can be found using the LU-decomposition of A. For example,
A
1 0 0 0 1 1
1 1 0 0 0 1
1110 0 0
0 1110 0
0 0 1110
0 0 0 1 1 1
LU
6x6
1 0 0 0 0 0 ' 1 0 0 0 1 1
1 1 0 0 0 0 0 1 0 0 -1 0
1 1 1 0 0 0 0 0 1 0 0 -1
0 1 1 1 0 0 0 0 0 1 1 1
0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 1 0 1 6x6 . 0 0 0 0 0 0
1 0 0 0 '
1 1 0 0 1 0 0 0 1 1
1 1 1 0 0 1 0 0 -1 0
0 1 1 1 0 0 1 0 0 -1
0 0 1 1 0 0 0 1 1 1 4 x6
0 0 0 1
1
1
1
0
0
0
6x4
1 0 0 0 1 1
0
1
1
1
0
0
6x6
0 1 0 0 -1 0
10


o o
0 0
+ i i o o o o + 0 i
i i
i 0 1 i
0 0 0 1 1 1 ]
1.2.5 Term Rank The term rank of a matrix A, denoted by
t(A), is the smallest number of rows and columns containing all the nonzero
entries of A. If A is a {0,l}-matrix, a set of ls of A is called an independent
set if no two ls in this set are in the same row or column of A. Hence, t(A)
is the maximum number of independent ls in A. Also, if A is the adjacency
matrix of a bipartite graph B, then t(A) is the size of a maximum matching
in B. For example, let
r i o i o'
0 0 1 0
A~ 1101 '
. 0 0 1 0 .
Then rows one and three and column three form a minimum line cover of all
the ls in A and the three bold ls give a maximum set of independent ls.
These independent ls correspond to a maximum matching in the bipartite
graph B(A). See Figure 1.4.
11


Figure 1.4. Maximum matching in the bipartite graph B(A).
1.2.6 Lower Bounds Lemma 1.2.3, Lemma 1.2.4, and Corol-
lary 1.2.5 will be useful in finding lower bounds for the boolean rank and the
biclique covering number.
Lemma 1.2.3 (Gregory et al. [GJLP91]) If a bipartite graph B contains
a matching S, no two edges of which are in a four-cycle of B, then bc(B) > (S'!,
the number of edges in S.
A set S of independent ls of a {0,l}-matrix is said to be isolated if
no two ls of S are in a submatrix of the form
1 1
1 1
Lemma 1.2.4 is a matrix formulation of Lemma 1.2.3.
12


Lemma 1.2.4 (Gregory et al. [GJLP91]) If the adjacency matrix A of a
bipartite graph B has an isolated set of k Vs, then b(A) = bc(B) > k.
Corollary 1.2.5 If the adjacency matrix A of a digraph D has an isolated set
of k 1 s, then b(A) = bc(D) > k.
Corollary 1.2.6 If a {0,l}-matrix A has an isolated set of k Vs, then
b(A) > k.
For example, the bold ls in the adjacency matrix
'010111'
0 0 0 1 1 1
010111
0 0 0 0 0 0
0 10 10 0
. 0 1 0 1 0 0 _
of the digraph D, given in Figure 1.1, give a set of two isolated ls. By Corol-
lary 1.2.5, b(A) = bc(D) > 2. Thus, b(A) = bc(D) = 2, since we previously
exhibited a biclique covering of size two.
1.2.7 Basic Rank Relationships From the definitions of non-
negative integer rank and real rank, it is clear that r{A) < rz+{A). Since
13


every biclique partition is a biclique covering, Lemmas 1.2.1 and 1.2.2 imply
that b(A) < rz+(A), for any {0,l}-matrix A. Also, for any {0,l}-matrix A,
rz+ (A) < t(A).
There is no relationship between b(A) and r(A) for a {0,l}-matrix A.
To illustrate this, consider ' l 0 0 0 1 1'
l 1 0 0 0 1
A l 1 1 0 0 0
J\ 0 1 1 1 0 0
0 0 1 1 1 0
. 0 0 0 1 1 1 _
which has r(A) = 4. The ls on the main diagonal of A give a set of six isolated
ls. By Corollary 1.2.5, b(A) > 6. Thus,
4 = r(A) < b(A) = 6.
But, for the adjacency matrix A of the digraph D, given in Figure 1.1, we have
3 = r(A) > b(A) = 2.
We can summarize the basic relationships between the ranks in the
following way. If A is a {0,l}-matrix, then
b(A) < rz+ (A) < t{A) and r(A) < rz+(A) < t(A).
14


2. Classes With Equal Ranks
2.1 Bipartite graphs
A domino is a 6-cycle with exactly one chord and this chord creates
two four-cycles. See figure 2.1. Bipartite domino-free graphs are bipartite
graphs without any induced subgraphs isomorphic to a domino [AVJ98].
------------
------------
Figure 2.1. Domino.
A recent breakthrough concerning the problem of determining what
bipartite graphs B have the property that bc(B) = bp(B) is the following result.
Theorem 2.1.1 (Amilhastre et al. [AVJ98]) If B is a bipartite domino-
free graph, then bc(B) = bp(B).
A bipartite Cf-free graph is a bipartite graph without any induced
subgraphs isomorphic to a four-cycle. By definition, a bipartite (' 1-free graph
15


is necessarily domino-free. Corollary 2.1.2 follows from the fact that every set
of independent ls is isolated in an adjacency matrix corresponding to a C 1-free
bipartite graph.
Corollary 2.1.2 If A is the reduced adjacency matrix of a Cf-free bipartite
graph B, then
r(A) < b(A) = rz+(A) = t(A).
The following example shows that we can have r(A) < t(A) if A is
the reduced adjacency matrix of a (' 1-free bipartite graph. Let
'10 0 1'
4 _ 1100
0 110 '
.0011.
B(A) is C 1-free and 3 = r(A) < b(A) = rz+{A) = /(. 1) = 4.
Open problem.If B(A) is a C4-free bipartite graph, find a lower bound
for
r(-4)
M.4)'
Recall, if A is the reduced adjacency matrix of a domino-free bipartite
graph,then
r{A) 16


The following two examples show there exists a class of domino-free bipartite
graphs with
r(A) r(A) 3
b(A) t(A) 4
and a class with
b(A) r(A) 3
t(A) t(A) 4
where A is the reduced adjacency matrix of any graph in
First, let
1 0 0 1 0 0 0 0
1 1 0 0 ,Fi = 0 0 0 0
0 1 1 0 0 0 0 0
0 0 1 1 _ _ 1 1 0 0
Ei Fi 0's
E\ F\
0's Ei
Then Ai is of order n = 4m, for some positive integer m.
main diagonal of Ai are isolated, b(Ai) > n and hence
b(Ai) = t(Ai) = 4m.
Furthermore, r{Ai) = 3m since
r(Ei) = r
Fi
Ei
3.
Thus,
r{Ai) r{Ai) 3
b{Ai) t(Ai) 4
the particular class.
and
Since the Fs on the
17


Second, let
Eo
1 1 0 1 ' 0 0 0 0
1 1 0 1 F2 = 0 0 0 0
0 1 1 1 0 0 0 0
. 0 0 1 0 . . 1 0 0 0 .
e2 f2 0's '
and
Ao
E2 F2
0's
F2
Eo
Then A2 is of order n = 4m, for some positive integer m. Since the bold ls
in each of the F2 s are isolated, b(A2) > 3m. Clearly, there exists a biclique
covering of
B Q e2 f2
consisting of three bicliques. Thus,
b(A2
3m.
Furthermore, r{A2) = 3m since
r(A2) = r
F2
e2
3.
Since the bold ls and the upper left 1 in the E2 s give an independent set in
A2 of cardinality 4m, t(A2) = 4m. Thus,
^(^2) ^(^2) 3
^(^2) ^(^2) 4
18


Open problems: If B(A) is a domino-free bipartite graph, find lower
bounds for
r(A) KA) r(A)
b(A) f(A) t(A)'
2.2 Digraphs
A digraph is strongly connected if there is a directed path between
any two vertices. A digraph is strongly unipathic if it has exactly one directed
path between any two vertices.
Theorem 2.2.1 (Hefner et al. [HLM93]) If D is a strongly unipathic di-
graph, then
b(A(D)) = r(A(D)) = rMA(Dj) = t(A(D)).
Hefner et al. [HLM93] showed that the simultaneous value of the
ranks of strongly unipathic digraphs of order n is any number in the range 2
though n. Each of these values can be realized for any n > 2. A strongly
connected digraph is called minimally strong if the removal of any arc results
in a digraph that is not strongly connected. Lundgren and May bee [LM91]
showed that minimally strong digraphs are a subclass of a class of digraphs,
called directed cockades, for which all four matrix ranks are equal and every
biclique is a claw. Theorem 2.2.2 and Lemma 2.2.3 follow from this work.
19


Theorem 2.2.2 (Lundgren and Maybee [LM91]) If D is a minimally strong
digraph, then
b(A(D)) = r(A(D)) = r,UA (D)) = t(A(D)).
Lemma 2.2.3 (Lundgren and Maybee [LM91]) If A is the adjacency ma-
trix of a minimally strong digraph, then B{A) is a Cf-free, hence domino-free,
bipartite graph.
Lemma 2.2.4 If D is a strongly connected unipathic digraph, then D is min-
imally strong.
Proof: Suppose D is a strongly unipathic digraph. Suppose e is an arc in D.
Then e is in a directed path from some vertex v.-, to some other vertex vj. If e is
removed, there is no directed path from tp to vj. Thus, D is minimally strong.
The digraph in figure 2.2 is minimally strong, but not unipathic, so
the converse of Lemma 2.2.4 is false. Lemma 2.2.4, and the fact that the con-
verse is not true, will be useful in section 3.1.
20


1
Figure 2.2. Digraph that is minimally strong but not unipathic.
Corollary 2.2.5 If A is the adjacency matrix of a strongly unipathic digraph,
then B(A) is a Cf-free, hence domino-free, bipartite graph.
2.3 Examples With Dominos
Recall, bp(G) = bc(G) if G is a domino-free bipartite graph or if G
is a unipathic or minimally strong digraph. From Lemma 2.2.3 and Corollary
2.2.5, B(A(G)) is domino-free for these three classes of graphs. The following
two examples show that we can have bp(B) = bc(B) with B containing a large
number of dominos relative to n. Furthermore, both examples have subclasses
with
b(A(B)) = r(A(B)) = rMA(B)) = t(A(Bj).
The first example is straight forward to construct from a bipartite
graph and the resulting graph is such that bp(B) = bc(B) = n. Let B'
be a bipartite graph with disjoint vertex sets X = {.r t...r} and Y =
{t/i, t/2, yn} where n = 3m + 1. Suppose B' has the form given in figure 2.3.
21


Figure 2.3. Bipartite graph with bc(B') = bp(B') = n and more than L^V^J
dominos.
Now construct a bipartite graph B, with the same bipartition sets as B', by
adding any edges to B' with the following two restrictions:
(1) If (Xi,yj), i ^ j, is an edge in B, then (Xj,y,i) is not an edge in B.
(2) and {xzj-2,y?jj+i) are not an edges in B for j > 1.
B contains at least m dominos and bc(B) = bp(B) = n since the set :
i = 1,2, is a perfect matching of B with no two edges in a four-cycle.
Furthermore, the B's's give a class of bipartite graphs with at least m dominos
and
b(A(B')) = r(A(B')) = rz+(MB')) = t(A(B')) = n.
The second example is not as straight forward as the first example,
but its properties are more significant. For each k. 3 positive integer, we will construct a bipartite graph B& on 2n vertices with at
least m dominos,
b(A(Bk)) = r(A(Bk)) = rz+(A(Bk)) = t(A(Bk)) = k
22


for k = 5j + i, i {0,1}, j e {1, 2, 3,and
b(A(Bkj) = r(A(Bk)) = rz+(A(Bkj) = k
for all k. Furthermore, for each n = 5m, the graphs will have 11m edges for
all k. We will construct these graphs from a matrix perspective. Let
' 1 0 0 0 1 o ' 1 0 0 0 1 o
1 0 0 0 0 0 1 0 0 0
1 1 1 0 0 ,C2 = 1 1 1 0 0
0 1 1 0 0 0 1 1 0 0
1 0 1 1 1 1 0 1 1 1
' 1 0 0 0 0 ' ' 0 0 0 0 0 1 0 0 0 1 o
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
1 1 1 0 0 5 C4 = 0 1 1 0 0 1 0 0 0 0
0 1 1 1 0 0 1 1 0 0 0 0 0 0 0
1 0 1 0 1 _ 0 0 1 1 1 1 0 0 0 0
' 0 0 0 0 0 1 0 0 0 0 '
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 1 0 0 5
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 1 0 0 0 0
and O be the 5x5 zero matrix. Let n = 5m, m a positive integer. For each k,
3 < k < n, deline the 5m x 5m matrix Ak = Ak , = A(Bk) inductively.
cx 0 0 ' c2 0 0
3 ,m Cl 0 0 i 1 I.//I C2 0 0
. Ci 0 0 _ . C2 0 0 _
r c3 0 0 ' rc3 0 0 0
C3 0 0 A C4 0 0
5 ,m . C3 0 0 _ j ^6,m . C4 0 0 _
23


and
An
A,
k.m
^3 0 0 0
C5 0 0
m J':, 0 0
0 0
0 Ak5,01 1
0
for k > 8.
Since Ak>m is lower triangular, the k ls on the diagonal form a set of k isolated
ls. Thus, b(Akjm) > k. Using the inductive construction of Akjm it is not
difficult, but tedious, to find a partition of Bk = B(Ak>m) consisting of k
bicliques. Hence, rz+(AkjTn) < k for 3 < k < n. This implies that b(AkjTn) =
rz+(Akjm) = k. When the first k entries on the main diagonal are nonzero,
they will form a set of independent ls of largest cardinality in Akjm. Thus,
t(Aktm) = k for fc = 5j + Me{0,l},je{l,2,3,...}.
Using the inductive construction of it is easy to verify that r(Akjm) = k
for k > 3. In matrix form, a domino is a permutation of the submatrix
'111'
Oil.
_ 1 0 1 _
Such submatrices occur at least m times in Akjm. Thus, Bk = B(Ak) =
B{Am^k) has the desired properties. Note that for small k, the above construc-
tion gives a bipartite graph with many isolated vertices. These isolated vertices
were included so the class could be constructed inductively. If k > n ^ 3. there
are no isolated vertices.
24


3. Matrices
3.1 Nearly Reducible Matrices
The {0,l}-matrix A js reducible if there exists a permutation matrix
P such that
PAP

Ai O
A21 a2
where Ai and A2 are square of order at least one and O is the zero matrix. If A
is not reducible, then A is irreducible. An irreducible matrix A is called nearly
reducible provided the replacement of any 1 with a 0 results in a reducible
matrix. The matrix
'0100'
0 0 10
10 0 1
0 10 0
is an example of a nearly reducible matrix. The matrix
'0101'
0 0 10
10 0 1
0 10 0
is irreducible, but not nearly reducible since the 1 in position (1,4) can be
changed to a 0 without resulting in a reducible matrix. The following theorem
is a well known result that was given in [BR92].
25


Theorem 3.1.1 The matrix A is irreducible if and only if the digraph D(A)
is strongly connected.
Corollary 3.1.2 The matrix A is nearly reducible if and only if the digraph
D{A) is minimally strong.
Corollary 3.1.3 follows from Corollary 3.1.2 and Theorem 2.2.2.
Corollary 3.1.3 If A is a nearly reducible matrix, then
b(A) = r(A) = rM^) = t(A).
The following example shows that, for any n > 2, we can construct
a nearly reducible matrix where the simultaneous value of the ranks is k, for
any k, 2 < k < n. Let
where B is an (n
B C
O D
k + 2) x (n
B
k + 1) matrix of the form
0 1 i i
1 0 o 0
1 o o o
1 o o 0
26


C is an (n k + 2) x (A; 1) matrix of the form
C
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
D is an (A; 2) x (A; 1) matrix of the form
'1 0 0 O'
0 1 0 0
0 0 1 0
and O is the (A; 2) x (n k +1) zero matrix. The matrix A is nearly reducible
since the digraph D(A) is minimally strong. See figure 3.1. Clearly, r{A) = k.
Hence,
b(A) = r z+ (A) = r(A) = t(A) = k.
Figure 3.1. Minimally strong digraph with b(A(D)) = rz+(A(D)) =
r(A(D)) = t(A(D)) = k. '
Note that D(A) is also a strongly unipathic digraph. Hence, this example
shows that for every k, 2 < k < n, we can find a strongly unipathic digraph
on n vertices such that
b(A(D)) = rMA(D)) = r(A(D)) = t(A(D)) = k.
27


3.2 Nearly Decomposable Matrices
3.2.1 Preliminaries The {0,l}-matrix A is partly decomposable
if there exists an integer k with 1 < k < n 1 and permutation matrices P
and Q such that
PAQ
B O
D C
where O is the k x (nk) zero matrix. A is fully indecomposable if it is not partly
decomposable. A fully indecomposable matrix is called nearly decomposable
provided the replacement of any 1 with a 0 results in a partly decomposable
matrix [BR92]. The matrix
'10 0 1'
0 10 1
0 0 11
.1110.
is an example of a nearly decomposable matrix. The matrix
'10 0 1'
0 10 1
0 0 11
.1111.
is fully indecomposable, but not nearly decomposable since the 1 in position
(4,4) can be changed to a 0 without resulting in a partly decomposable matrix.
Lemma 3.2.1 summarizes some properties of these matrices as discussed by
Brualdi and Ryser in [BR92], Lemma 3.2.2 gives a sufficient condition for a
fully indecomposable matrix to be nearly decomposable.
28


Lemma 3.2.1 (Brualdi and Ryser [BR92]) Let A be a {0,1}-matrix of or-
der n. A is partly decomposable if and only if it has a minimum, line cover other
than the all rows cover or the all columns cover. Hence, A is fully indecompos-
able if and only if t(A) = n. Furthermore, every line of a fully indecomposable
matrix has at least two ones.
Lemma 3.2.2 Let A be a fully indecomposable matrix. If a,ij = 1 implies row
i or column j (or both) has exactly two Vs, then A is nearly decomposable
Proof: Suppose A is a fully indecomposable matrix, = 1, and row i or
column j has exactly two ls. Without loss of generality, assume = 1
and a,t = 0 for \ < t < n. t ^ j, and t^k.
j k
i 0 1 0 0 1 0
If a,ij = 1 is changed to = 0, the resulting matrix can be covered with
column k and all rows except row i.
j k
i 0 0 0 0 1 0
Thus, A has a line cover that is not the all rows cover or the all columns cover.
Therefore, by Lemma 3.2.1, A is nearly decomposable.
29


Theorem 3.2.3 shows how irreducible and fully indecomposable ma-
trices are related. This will be used to verify matrices are fully indecomposable
and to find bipartite graph representations of irreducible and nearly reducible
matrices. The inductive structure given in Lemma 3.2.4 will be used to deter-
mine the boolean rank of nearly decomposable matrices.
Theorem 3.2.3 (Brualdi and Ryser [BR92]) Let A be a {0,1}-matrix of
order n. Let Af be the matrix obtained from A by replacing each entry on
the main diagonal with a 1. Then A is irreducible if and only if A$ is fully
indecomposable.
Lemma 3.2.4 (Brualdi and Ryser [BR92]) Let A be a nearly decompos-
able {0,1}-matrix of order n > 2. Then there exists permutation matrices P
and Q of order n and an integer m with 1 < m < n 1 such that
' 1 0 0 0 0
1 1 0 0 0
0 1 1 0 0 Fi
0 0 0 1 0
0 0 0 1 1
F2 B
'where B is a nearly decomposable matrix of order m. The matrix T\ contains a
unique 1 and it belongs to its first row and column j for some j with 1 < j < m.
30


The matrix F2 contains a unique 1 and it belongs to its last column and row i
for some i with 1 < i < m. If m >2, then m ^ 2 and the element in position
(i,j) of B is 0.
3.2.2 Ranks In this section we will discuss the term rank, boolean
rank, nonnegative integer rank, and real rank of nearly decomposable matri-
ces. The term rank, boolean rank, and nonnegative integer rank of a nearly
decomposable matrix is equal to the order of the matrix; however, the real
rank can be less. The term rank of a fully indecomposable matrix of order n
is equal to n [BR92]. Thus, the term rank of a nearly decomposable matrix
of order n is equal to n. This is stated in Lemma 3.2.5. This result will be
used in determining the boolean rank and nonnegative integer rank of nearly
decomposable matrices given in Theorem 3.2.6.
Lemma 3.2.5 (Brualdi and Ryser [BR92]) If A is a nearly decomposable
matrix, then t(A) = n.
Theorem 3.2.6 If A is a nearly decomposable matrix of order n > 3, then
b(A) = rz+(A) = n.
31


Proof: To prove the theorem, we will use induction on n to show that if A is
a nearly decomposable matrix of order n > 3, then A does not contain the
submatrix
'll'
1 1 '
Let A be a nearly decomposable {0,l}-matrix of order n = 3. By Lemma 3.2.4,
there exists permutation matrices P and Q such that
\ 1 0 1 1
PAQ = 1 1 0
_ 0 1 1 _
Thus, A does not contain the submatrix
' 1 1
1 1
Now assume that any nearly decomposable matrix of order k, 3 < k < n, does
not contain the submatrix
' 1 1 '
1 1 '
Let A be a nearly decomposable {0,l}-matrix of order n > 3. By Lemma 3.2.4,
there exists permutation matrices P and Q of order n and an integer m with
32


1 < m < n 1 such that
PAQ
1 0 0 0 0
1 1 0 0 0
0 1 1 0 0 Fi
0 0 0 1 0
0 0 0 1 1
f2 B
where B is a nearly decomposable matrix of order m. The matrix F\ contains a
unique 1 and it belongs to its first row and column j for some j with 1 < j < m.
The matrix F2 contains a unique 1 and it belongs to its last column and row %
for some % with 1 < i < m. If m > 2, then m^2 and the element in position
(i,j) of B is 0. By the induction hypothesis, B does not contain the submatrix
1 1
1 1 '
If A contained the submatrix
1 1 '
1 1 J
then the unique 1 in T\ and the unique 1 in F2 must be the upper right 1 and
lower left 1, respectively, of this submatrix. This implies that m = n ^ 1 > 2
and hence the element in position (i,j) of B is 0. Thus, A cannot contain the
submatrix
1 1
1 1
33


By Lemma 3.2.5, A has a set of n independent ls. Since A does not contain
any submatrices of the form
' 1 1 '
1 1 J
every set of independent ls is isolated. Therefore, by Corollary 1.2.6,
b(A) = n. m
Corollary 3.2.7 If A is a nearly decomposable matrix of order n > 3, then
b(A) = rz+{A) = t(A) = n.
The only nearly decomposable matrices of order one or two are
Ai = [ 1 ] and A2 = [ [ ,
respectively. Trivially, t(A2) = 2 and
KAi) = r'z+{Ai) = r(Ai) = t(Ai) = b(A2) = rz+(A2) = r(A2) = 1.
The real rank of a nearly decomposable matrix of order n can be less
than n. The following examples show that r{A) = n,n 1, and n 2 can be
34


obtained for a nearly decomposable matrix A of order n. Let
r l 0 o 0 0 i i
l i o 0 0 0
O i i 0 o o
o o 0 1 O o
0 0 0 1 i 0
i o 0 0 0 i i .
The digraph D(An I) is strongly connected since it is a cycle of length n.
Thus, by Theorem 3.1.1, An I is irreducible. Hence, by Theorem 3.2.3, An
is fully indecomposable. Finally, by Lemma 3.2.2, An is nearly decomposable
since every row and column of An has exactly two ls. If n is odd, then
r(An) = n. If n is even, then r(An) = n 1 since the last row is a linear
combination of the first n 1 rows.
The numerous examples of nearly decomposable matrices of order n
we constructed all had real rank n or n 1. This lead us to conjecture that
the real rank of a nearly decomposable matrix is at least n 1. However, the
proof of this was illusive and we now know it is not true. Finding an example
of a nearly decomposable matrix A of order n with r(A) < n 2 was difficult,
but was finally accomplished in the following way. From Lemma 3.2.4, if A is a
nearly decomposable matrix of order n > 2 there exists permutation matrices
35


P and Q of order n and an integer m with 1 < m < n 1 such that
PAQ
1 0 0 0 0
1 1 0 0 0
0 1 1 0 0 Fl
0 0 0 1 0
0 0 0 1 1
f2 B
where B is a nearly decomposable matrix of order m. The matrix Fx contains a
unique 1 and it belongs to its first row and column j for some j with 1 < j < m.
The matrix F2 contains a unique 1 and it belongs to its last column and row %
for some % with 1 < % < m. The converse of Lemma 3.2.4 is not true; however,
the inductive structure gives insight regarding constructions that may give a
nearly decomposable matrix. We construct a nearly decomposable matrix A
of order n with r{A) = n 2 by letting
r l 0 0 -
l i 0
0 i 1 Fi
_ F2 B J
where B is a nearly decomposable matrix of order m with r(B) = m 1. The
unique ls in T\ or /_,. must be placed so that = 1 implies row i or column j
(or both) has exactly two ls. Furthermore, B is such that a vector in the left
nullspace and a vector in the right nullspace of B have zeros in the positions
corresponding to the row or column of the unique 1 in or /_.. respectively.
36


The smallest matrix B that we could find that satisfied these conditions is
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 1
where
[ -1 1 1 | 1 -1 1 | 1 0 0 0 -1 1 -1 1 -i]b = o
and
B
1
-1
1
l
-l
l
-l
l
-l
o
0
0
1
0.
37


Now, let
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1
With the assistance of computer software, we can show that r(A) = 16 = n^2.
We can use similar reasoning as we did with An to show that A is nearly de-
composable. It is not difficult, but tedious, to show the digraph D(A I) is
strongly connected. Thus, by Theorem 3.1.1, A I is irreducible. Hence, by
Theorem 3.2.3, A is fully indecomposable. Finally, by Lemma 3.2.2, A is nearly
decomposable since = 1 implies row % or column j (or both) has exactly
two ls. This construction has been extended to construct nearly decompos-
able matrices of orders n = 36 and n = 54 with real rank n 3 = 33 and
n 4 = 50, respectively. This leads us to make the following conjecture.
38


Conjecture 3.2.8 For every nonnegative integer k, there exists a nearly de-
composable matrix of order n = 18k with r(A) = n k 1 = 17k 1. Thus,
there exists a class of nearly decomposable matrices such that
r(A) 17
-------> as n > oo.
n 18
Open problems: If A is a nearly decomposable matrix, find a lower
bound for the ratio
r(A)
n
Find a characterization of nearly decomposable matrices with respect to their
real rank. Specifically, classify nonsingular nearly decomposable matrices.
3.3 Bipartite Graph Representations
Every {0,l}-matrix is the reduced adjacency matrix of a bipartite
graph. In this section we will study the bipartite graph representation of ir-
reducible, nearly reducible, fully indecomposable, and nearly decomposable
matrices. In [LP77], a bipartite graph is called elementary if it is connected
and each edge is contained in a perfect matching. A minimal elementary bi-
partite graph is one in which the removal of any edge results in a bipartite
graph which is not elementary.
39


Theorem 3.3.1 (Brualdi and Ryser [BR92]) A {0,1}-matrix A is fully in-
decomposable if and only if B{A) is an elementary bipartite graph.
Corollary 3.3.2 (Brualdi and Ryser [BR92]) A {0,1}-matrix A is nearly
decomposable if and only if B{A) is a minimal elementary bipartite graph.
From the proof of Theorem 3.2.6, bipartite graphs with nearly de-
composable adjacency matrices of order n > 3 are C 1-free. Thus, we can use
Corollaries 3.3.2 and 3.2.7 to give a class of domino-free bipartite graphs with
b{A{B)) = rz+{A{B)) = t{A{B))=n.
This is stated in Corollary 3.3.3.
Corollary 3.3.3 If A is the reduced adjacency matrix of order n > 3 corre-
sponding to a minimal elementary bipartite graph, then
b(A) = r z+ (A) = t(A) = n.
One can find a similar characterization of bipartite graphs corre-
sponding to irreducible and nearly reducible matrices. To do this, we will
40


need the following definitions. Let B be a bipartite graph with bipartition
X = {.ri. ...,xn} and Y = {yi,y2, ,yn}- A subgraph B of B will be called
uniform, if Xi v(B) if and only if y.-, e v(B). See Figure 3.2. B will be called
sub-elementary if each edge is contained in a perfect matching of a uniform
subgraph B of B. A minimal sub-elementary bipartite graph is one in which
the removal of any edge results in a bipartite graph that is not sub-elementary.
Figure 3.2. Perfect matching of a uniform subgraph B.
Theorem 3.3.4 Let A be a {0,1}-"matrix. A is irreducible if and only if B(A)
is a sub-elementary bipartite graph.
Proof: Suppose B is a sub-elementary bipartite graph with reduced adjacency
matrix A = A(B). Let Af be the matrix obtained by replacing all the 0s on
41


the main diagonal of A with ls. Suppose e e e(B). Then e is an edge in a per-
fect matching MH of some uniform subgraph H C B. M along with all edges
(.Xi,yi) with xi 0 v(H) (y,i 0 v(H)) is a perfect matching of B(A^). See Figure
3.3. B(A^) is connected since B(A) is sub-elementary. This implies that B(A^)
is an elementary bipartite graph. Hence, A is fully indecomposable. Thus, by
Theorem 3.2.3, A is irreducible.
Conversely, let A be an irreducible matrix and B = B(A) the cor-
responding bipartite graph with reduced adjacency matrix A. By Theorem
3.2.3, A is fully indecomposable and hence, by Theorem 3.3.1, B(A^) is an
elementary bipartite graph. Suppose e e e(B). Then e e e(B(A$)) which
implies e is in a perfect matching M of B(A'i). Removing all edges (xt, y,j) 0 B
forms a perfect matching MH of a uniform subgraph H C B. See Figure 3.3.
Furthermore, B(A'i) is connected since it is elementary. Therefore, B is a sub-
elementary bipartite graph.
For example, consider the matrix
A
0 0 110
1 0 0 0 0
110 0 1
0 10 0 0
0 0 0 1 0
As illustrated in Figure 3.4, every edge in B = B(A) is in a perfect matching
of one or more of the uniform subgraphs B\,B2, B3, or S4. Thus, by Theorem
42


Figure 3.3. Perfect matchings MH of H C B(A) and M of B(A$).
3.3.4, A is irreducible. One can easily verify that A is irreducible by observing
that the digraph D(A) is strongly connected. See Theorem 3.1.1. Now note
that B is not an elementary bipartite graph since not every edge is in a perfect
matching of B. In particular, the edge between the first vertex and the fourth
vertex cannot be in a perfect matching that involves the fifth vertex in each set
of the bipartition. Thus, A is not fully indecomposable. One can also observe
that A is partly decomposable since row three and columns one, two, four, and
five cover all the ls in A and hence A has a minimum line cover that is not
the all rows cover or the all columns cover.
Corollary 3.3.5 Let A be a {0,l}-matrix. A is nearly reducible if and only if
B(A) is a minimal sub-elementary bipartite graph.
43


B i B2 B3 B4
Figure 3.4. Every edge in the bipartite graph B is in a perfect matching of a
uniform subgraph Bj.
44


Corollary 3.3.6 follows from Corollaries 3.3.5 and 3.1.2. We can then
use Corollaries 3.3.5, 3.3.6, and 3.1.3 and Lemma 2.2.3 to give a class of domino-
free bipartite graphs with all four ranks equal. This is stated in Corollary 3.3.7.
Corollary 3.3.6 Let A be a {0,1}-"matrix. B{A) is a minimal sub-elementary
bipartite graph if and only if D{A) is a minimally strong digraph.
Corollary 3.3.7 Let A be an adjacency matrix corresponding to a minimal
sub-elementary bipartite graph, then
b(A) = r(A) = rM^ = t(A).
Proposition 3.3.8 summarizes the relationships between irreducible
and fully indecomposable matrices and their bipartite graph representations.
Proposition 3.3.8 Let A be a square {0,l}-matrix. Let Aff be the matrix
obtained from A by replacing each entry on the main diagonal with a 1. Then
the following statements are equivalent.
(1) B(A) is a sub-elementary bipartite graph.
(2) A is an irreducible matrix.
45


(3) Af is a fully indecomposable matrix.
(4) B(Af) is an elementary bipartite graph.
Proof: (1) 4=r (2), (2) (3), and (3) <£> (4) are Theorems 3.3.4, 3.2.3, and
3.3.1, respectively. Therefore, (1) (4).
46


4. Tournaments
4.1 Preliminaries
A digraph T is called a tournament if for each pair of vertices u and
v, either (u, v) is an arc in T or (v,u) is an arc in T, but not both. We will
call A an n-toumament matrix if A is the adjacency matrix corresponding to
a tournament on n-vertices. T(A) will denote the tournament with adjacency
matrix A. A square {0,l}-matrix A is a tournament matrix if and only if
A + AT +1 = J, where I is the identity matrix and ,J is the all ls matrix. In
this chapter we will discuss the ranks of various classes of tournament matrices,
we will give several classes of tournament matrices with
b(A) = r(A) = rMA) = t(A),
and we will construct examples of tournament matrices to show that all of
the above equalities can be strict inequalities. First, we will give some general
results concerning the ranks of tournament matrices and a property of vectors
in the null space of singular tournament matrices.
47


4.2 General Results
In 1991, de Caen found a lower bound for the real rank of an n-
tournament matrix. See Theorem 4.2.1. This was a significant result, not only
because it was an open problem for many years, but because it allows only two
possible values for the real rank, n or n 1. Hence, the nonnegative integer
rank and the term rank are also norn-l, since the real rank is a lower bound
for these two ranks. See Corollary 4.2.2.
Theorem 4.2.1 (de Caen [dC91]) If A is an n-tournament matrix, then
r{A) > n 1.
Corollary 4.2.2 If A is an n-tournament matrix, then
n 1 < r(A) < rz+(A) < t(A) < n.
Corollary 4.2.3 For every tournament matrix, at least two ranks are equal.
Specifically, if A is an n-tournament matrix, then
rz+{A) = r{A) = n 1 or rz+{A) = t(A) = n
48


Open problem: Classify singular tournaments as mentioned by de
Caen [dC91]. See Katzenberger et. al [KS90] for some results on the form
of a vector spanning the null space of a singular tournament.
From Corollary 4.2.2, we know that three of the ranks are either n
or n 1. Classifying those tournament matrices with r(A) = n 1 and those
tournament matrices with rz+{A) = n 1 are very difficult unsolved problems.
However, we do know which tournament matrices have t(A) = n 1 and this
classification is given in Theorem 4.2.4.
Theorem 4.2.4 Let A be an n-tournament matrix. Then t(A) = n 1 if and
only if there exists a strongly connected component ofT(A) containing exactly
one vertex. Hence, t(A) = n if and only if every strongly connected component
ofT(A) has three or more vertices.
Proof: Tournaments can be partitioned into strongly connected components
C\. C-2..(),. such that there is an arc from u C% to v e Cj if and only if
i < j. Thus, there exists a permutation matrix P such that
Ai l's
PAP1
L 0's Ak J
where Aj, 1 < j < k, is the adjacency matrix of order nj corresponding to the
component C'j.
49


Suppose t(A) = n 1 and rij > 1 for 1 < j < k. Since Cj is a strongly
connected tournament on three or more vertices, Cj contains a Hamiltonian
cycle [Cam59, Fou59]. This implies that t(Aj) = rij for 1 < j < k and hence
t(PAPT) = n. This contradicts t(A) = n 1. Thus, there exists a strongly
connected component of T(A) containing exactly one vertex.
Conversely, suppose rij = 1 for some j. Then the submatrix Aj is a 0
on the diagonal of PAPT. Suppose this 0 is in the position (m, nn) of PAPT.
Then the first m 1 rows and the last n m columns form a line cover of
PAP1. Thus,
t(A) = I (PAP1) < m 1 + n m = n 1.
Therefore, by Corollary 4.2.2, t(A) = n 1.
Since r{A) = n or n 1 for an n-tournament matrix A, we know the
null space of a singular tournament matrix is spanned by one vector. Maybee
et. al [MP90] showed that if a vector spans the null space of a tournament
matrix, then the sum of the squares of its components equals the square of the
sum. This is called the admissible property and it will be used to prove that
the real rank of a regular n-tournament is n.
50


Lemma 4.2.5 (Maybee and Pullman [MP90]) J/x = (.rt...,xn)T spans
the null space of an n-tournament matrix, then
4.3 Regular and Near-Regular Tournaments
A tournament is regular if all its vertices have equal scores. Thus,
a regular n-tournament matrix is a tournament matrix with equal row sums.
If A is a regular n-tournament, then n must be odd. A tournament is near-
regular if the maximum difference between its scores is 1. Thus, a near-regular
n-tournament matrix is a tournament matrix where half of the row sums equal
| 1 and half of the row sums equal |. If A is a near-regular n-tournament,
then n must be even. There have been several proofs that regular tournament
matrices are nonsingular, including de Caen [dC91] and Maybee and Pullman
[MP90]. We give the following simple proof that uses Lemma 4.2.5.
Theorem 4.3.1 A regular tournament matrix is nonsingular.
51


Proof: Let A be a regular n-tournament matrix and let v = (vi,V2, ...,vn)T be
a vector such that Av = 0. Then
4 Vl ^ieAi vi ' 0 '
/l _ V _ . ^2ieAn Vi _ _ 0 _
where Aj = {i : j > i}. This implies that
E Vi + ... + E
ieAi iAn
Vi = o.
In the above sum, each Vi must appear exactly11^ times which corresponds to
the number of vertices which beat vertex i. Thus,
n 1
2
(t>i + ... + vn) 0
n
=*X> =
i=1
n
i=1
=> v = 0.
Therefore, A is nonsingular.
Corollary 4.3.2 If A is a regular n-tournament matrix, then
r(A) = r z+ (A) = t(A) = n.
52


The proof that near-regular tournament matrices are nonsingular is
not as straight forward and it requires Theorem 4.3.3. Theorem 4.3.3 could
also be used to prove nonsingularity for regular tournament matrices.
Theorem 4.3.3 (Katzenberger and Shader [KS90]) Let s = (s\. s-2,..., 8)'
be a score vector. If
then every n-tournament with this score vector is nonsingular.
Theorem 4.3.4 For n > 4, a near-regular n-tournament matrix is nonsingu-
lar.
Proof: The score vector of a near-regular n-tournament matrix is some permu-
tation of
,n n n n.T
S -L.. ^ ^ ^ ^ ^ )
where each of the two different terms occurs exactly f
n n
2 2
x o Tl ,Tl.cf
if + -i-f
J 2l2;
n3 + 2 n
4
times. Thus,
- 2n2
Now n3 + 2n 2n2 < n3 r? for n > 4. Thus,
Is|2<
n2(n 1)
53


Therefore, by Theorem 4.3.3, near-regular tournament matrices are nonsingu-
lar.
Open problem: Is the boolean rank of a regular or near-regular n-
tournament matrix, n > 3, equal to n as well?
4.4 Boolean Rank
By Corollary 4.2.2, the real, nonnegative integer, and term rank of an
n-tournament matrix are each either norn-1. However, the boolean rank can
be much smaller. Bain et al. [BLM92] constructed the following tournament.
Let T be the tournament defined by
Tk T ^Ot u Vm-l J^Ql-2 J^Ql J-Ql
Qm1 Tk J Qm-1 J-Ql J-Ql
T = Qm2 Qm1 Tk J-Ql
q2 Qa Qi Tk J-Qm-
Qi q2 Qa Qm1 Tk
where k = m2 + m + 1, P is the permutation matrix of order k given by
\ 0 i 0 0 0 01
0 0 1 0 0 0
o 0 0 0 0 0
o 0 0 0 1 0
0 0 0 0 0 1
. i 0 0 0 0 0 .
54


and
A i = Pm'
A2 = Pm2~m~l + prn?-m
Ai = + pm2-(!-l)m-(i-2) +____j_ pm2 (il)m
Am_! = P"i+2 + Pm+3 + + p2m
Am = P + P2 + .. . pm
Qi Ai
Q2 := -/I4 "f" y4.2
Vn1 = Ai + A.2 "f" * + Am.
Tfc A\ "4 A2 h * + Am
55


For example, if n = mk = (2) (7) = 14, then
0 1 1 0 1 0 0 1 1 1 0 1 1 1
0 0 1 1 0 1 0 1 1 1 1 0 1 1
0 0 0 1 1 0 1 1 1 1 1 1 0 1
1 0 0 0 1 1 0 1 1 1 1 1 1 0
0 1 0 0 0 1 1 0 1 1 1 1 1 1
1 0 1 0 0 0 1 1 0 1 1 1 1 1
1 1 0 1 0 0 0 1 1 0 1 1 1 1
0 0 0 0 1 0 0 0 1 1 0 1 0 0
0 0 0 0 0 1 0 0 0 1 1 0 1 0
0 0 0 0 0 0 1 0 0 0 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1 1 0
0 1 0 0 0 0 0 0 1 0 0 0 1 1
0 0 1 0 0 0 0 1 0 1 0 0 0 1
o 0 0 1 0 0 0 1 1 0 1 0 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 0
0 0 0 1 1 0 1
1 0 0 0 1 1 0 ' 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 1 1
1 0 1 0 0 0 1
1 1 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 1 1 0
0 0 0 0 0 1 0 0 0 1 1
0 0 0 0 1 0 1 0 0 0 1
1 0 0 0 1 1 0 1 0 0 0
0 1 0 0 0 1 1 0 1 0 0
0 0 1 0 0 0 1 1 0 1 0
0 0 0 1 0 0 0 1 1 0 1
Since A = BC using boolean arithmetic where B is 14 x 7 and C is 7 x 14,
b(T) < 7.
56


Lemma 4.4.1 (Bain et al. [BLM92]) For each integer m > 2 and n suffi-
ciently large,
Ti
min{b(T) : T is an n x n tournament matrix} < .
m
Open problem;. Can this bound be improved, or is it best possible?
Conjecture 4.4.2 Let T be the tournament defined above. Them A(T) is non-
singular and hence
r(A(T)) = rMA(T)) = t(A(T)) = n.
It has not been proven that A(T) is nonsingular; however, by The-
orem 4.4.3, we know that t(T) = n. Also, using Lemma 4.4.4, it has been
shown that A(T) is nonsingular for all possible values of k and m up through
n = mk = (10) (111) = 1110.
We will need the following terminology in the proof of the next the-
orem. The diagonal beginning in column j of a matrix A of order n is the n
elements
A(l,j),A(2,j + l), ,A(n-j,n),A(n-j +1,1), A(n-j+2,2), ,A(n,j-1).
57


Theorem 4.4.3 IfT is the tournament defined above, then t(A(T)) = n.
Proof: Let T be the tournament defined above. We will show that the diagonal
that begins with column m2 + 1 of T will give a set of n independent ls. The
ls on any diagonal will be independent, so we just need to show that every
element on this diagonal is a 1.
Tk
A\ + Ao
+ Ar
where A\ = Pm\ Thus, the diagonal of Tfe that begins with column ni2 + 1
will be all ls.
rri2 + 1
1
Tk
771 + 1
1
(m2+m+l) x(m2+m+l)
The diagonal of Qm-i that begins with column m + 2 will be all zeros
since Pm+1 does not occur in the sum that gives Qm-1. Thus, the diagonal of
J Qm-1 that begins with row m + 2 will be all ls. Thus, we have
\Tk\J - ]
m2 + 1
m + 2
... 1
1
1
1 .
(m2+m+l) x2(m2+m+l).
58


Lastly, since
rri2 + 1
1
Qi = P[
m + 2
1
1
(m2+m+l)x(m2+m+l)
has a diagonal of all ls beginning with row m + 2, the diagonal of T beginning
with column m2 + 1 will give mk = m(m2 + m + 1) = n independent ls.
Therefore, t(T) = n. u
Lemma 4.4.4 Let N(M) be the number of 1 s in each row and column of a
regular {0,1}-matrix M and let
Tk T -nT Vm-l J Ql-2 J-Ql J-QT
Qm1 Tk J C-1 J^Ql 3-Ql
T = Qm2 Qm 1 Tk J^Qf J-QI
q2 Qa Qi Tk J ~ Ql-l
Qi q2 Qa Qm1 Tk
be the tournament defined above. Then A(T) is nonsingular if N =
N(Tk) k N(Ql_i) k N(QIW k-N{Q%) k-N(Qj) -
N(Qm-l) X(Tk) k N(Qi_ J k-N{C%) k N(QT)
N(Qm-2) N(Qm-1) N(T) /.' V((9' ) k ml)
n(q2) N(Qt) N(Tk) k N(Ql-1)
. N(Qi) Ar(Q2) N(Q3) N(Qm-l) N(Tk) .
59


m(m+1) 2 V. (m-l)m K 2 1, (m2)(m1) K 2 A; 3 A: 1
(ml)m 2 m(m+1) 2 7 (m-l)m K 2 A; 6 k^ 3
? 1 to to 3 i (ml)m 2 m(m+l) 2 O i1 -se k^6
3 6 10 m(m+1) 2 , (m-l)m a> 2
1 3 6 (ml)m 2 m(m+l) 2 -1
is nonsingular.
Proof: Let N(M) be the number of ls in each row and column of a regular
{0,l}-matrix M and let N =
' iV(T*) k N(Ql_2) *-JV(QD fc-;V(Qf) ]
Ar(Tl) k N(Ql_,) k-N{QT) - U(Q$)
iV(Qm-2) A(Qra-i) N(T) -fe-iV(QD k ;V(QP
iV(Q2) AlQs) N(Qt) iV(T*) k N(CZ_i)
. NiQi) A(Q2) Nm iV(Qm_i) N(Tk)
Let
T ^ Cl1' Vm-l J"<&-2 J ~ Q% J-Qf
Qm 1 Tk J ~ Qm-1 J-Ql J Q 2
T = Qm2 Qm1 J-Ql
q2 Qa q4 Tk j QL-i
Qi q2 Qa Qm1 Tk
be the tournament defined above. N(Tk) = N(Qm) = and N(Qj) =
M+1) since Qj is the sum of ^Czil distinct powers of the permutation matrix
P. Let v be a vector such that Tv = 0. Consider the system of km equations
and km unknowns given by Tv = 0. Adding equations 1 through k, k + 1
through 2k,.. .,(m l)k + 1 through mk will give the following system of m
60


equations and mk unknowns.
TJX (TJX -f- 1)
0 = -----------------(id + + Vk) + + (A; + + vmk)
(jj~f 2. \tjx
0 = ------------(fi + + Vk) + (& + + vmk)
/ (tjx 1)771 \
0 = 3(t>i + + Vk) + + I A;------------------ ] (f(m-l)fe+l + + Vmk)
0 = (iq H-----------h vk)
'm(m + 1)
{V(ml)fe+l + ' + Vmk)
This is equivalent to
N
Vl -
Vk+1
Vk
t V2k
V(ml)k+l T ' + Vmk
0.
If N is nonsingular, then
N
Vl +
Vk+l +
Vk
Vc2k
V(ml)k+l T ' + Vmk
0
implies
0 = V\ H----------h vk
0 Vk+1 + + V2k
0 1,(m l)fe+l T ' + Vmk
61


Thus, by Lemma 4.2.5
n \ 2 n
5> = 5>2 =0
i=1 / i=1
=>- V = 0.
Conjecture 4.4.5 Let N(M) be the number of 1 s in each row and column of
a regular {0,1}-matrix M and let
' Tk T -qt u Vm-l J"<&-2 J-Q& J-Ql
Qml Tk J-Ql
T = Qm2 Qm 1 J-Ql J-Ql
q2 Qa Qi Tk J Qm-l
Qi q2 Qz Qm1 Tk
be the tournament defined above. Then N =
N(T) k N(Ql_V k-mQiw k N(Ql) k N(Ql)
N(Qm-1) N(Tk) k-N(Ql-V k N(Ql) k N(QI)
N(Qm-2) N(Qm_i) N(Tk) k N(Ql) k N(QJ)
N(Q2) N(Q3) N(QQ N(Tk) k-N(Qm_.)
[ iV(Qi) N(Q2) ;V(Q3) N(Qm-l) N(Tk) -
r m(m+l) r (m-1) 2 v 2 m / (m2)(m1) lb 2 k^ 3 k-1 1
(ml)m m(m+1) 7 (m-l)m lb 2 k^ 6 k^3
(m2)(m1) (ml)m 2 2 m(m+l) 2 k -10 k^ 6
3 6 10 m(m+l) 2 7. (m-l)m lb 2
1 3 6 (ml)m 2 m(m+l) 2 J
is nonsingular.
62


4.5 Classes With All Four Ranks Equal
4.5.1 Rotational Tournaments A regular tournament is called
a rotational tournament if its vertices can be labeled 0,1, 2, ...r in such a way
that for some subset S of {1, 2,..., r}, vertex i beats i + j mod (r + 1) for all
j S. For example,
0 1 0 0 1 0 1 1 0
0 0 1 0 0 1 0 1 1
1 0 0 1 0 0 1 0 1
1 1 0 0 1 0 0 1 0
0 1 1 0 0 1 0 0 1
1 0 1 1 0 0 1 0 0
0 1 0 1 1 0 0 1 0
0 0 1 0 1 1 0 0 1
. 1 0 0 1 0 1 1 0 0 .
is an adjacency matrix corresponding to a rotational tournament on r + 1 =
n = 9 vertices determined by the set S = {1, 4, 6, 7}.
Lemma 4.5.1 Let T be a rotational tournament onn = r+1 vertices, 0,1, 2,... ,r,
given by a subset S of {1,2,... ,r}. Them |Sj = | and
j E S r + 1 j 0 S.
Proof: Let T be a rotational tournament on n = r + 1 vertices, 0,1, 2,..., r,
given by a subset S'of{l,2,...,r}. |Sj = | since, by definition, T is a regular
tournament. Suppose j e S. Since T is a tournament, A(T) + A(T)T + I = J
63


where
0
0
j r + 1 j r
1 0
1
A(T)
0 1
0
r + 1 j
0
0
0 0
and ,J is the all ls matrix. Hence, r + 1 j ^ S. Similarly, if r + 1 j 0 S,
then j e S. m
Theorem 4.5.2 Let T be a rotational tournament on n = r + 1 vertices,
0,1,2,...,r, given by a subset S of {1,2,... ,r}. If there exists a j e S such
that
j + k mod (r + 1) e S j k mod (r + 1) 0 S
for all k e {1,2,..., r}, then bc(T) = n.
Proof: Let T be a rotational tournament on n = r + 1 vertices, 0,1, 2,..., r,
given by a subset S of {l,2,...,r}. Suppose there exists a j E S such that
j + k mod (r + 1) e S ^ j k mod (r + 1) 0 S
64


for all 6 {1,2,..., r}. Let W be the set of ls of the adjacency matrix A(T)
corresponding to the arcs
i > i + j mod (r + 1) for i = 0,1,... r.
By definition, W consists of n independent ls; hence, we just need to show
that all the ls in W are isolated. Suppose two ls of W are in a submatrix of
A(T) of the form
' 1 1 '
1 1 '
First, suppose the bold ls in
1 1 '
1 1
are in W. By the definition of a rotational tournament, we can assume the
top row or the left column of this submatrix is in the top row or left column,
respectively, of A(T). Without loss of generality, assume the top row of the
submatrix is the top row of A(T). There are two cases to consider. If j k > 0,
65


then
A(T)
0 j-k 3 3+1 £
0 1 1 1
0 1 1 1
0 1 1
0 1
0
and j k E S. This contradicts the assumption that j k mod (r + 1) 0 S.
If j k < 0, then
0
k-j
A(T)
0 1 1
1 0 1 1
1 0 1
1 0 1
1 1 o
k j S, and r + l- (l:-j)6S. But,
r + 1 {k j)=r + l+ j k=j k mod (r + 1).
This contradicts j k mod (r + 1)0 S.
Second, suppose the bold ls in the submatrix
1 1
1 1
66


are in W. Again, without loss of generality, we can assume the top row of the
submatrix is the top row of A(T). If the two non-bold ls are on the same
diagonal modulo r + 1, then
A(T)
0 j A-
r + 1 j
1 o 1 1
1 0 1
10 1

and r + 1 = 2k, since the bold ls are on the same diagonal. This is a contra-
diction since regular tournaments have odd order. If the two non-bold ls are
not on the same diagonal modulo r + 1, then there are three cases to consider.
First suppose j + k < r + 1. Then the submatrix
1 1
1 1
has the form
A(T)
0 J - k 3 j + k
0 0 1 1 1
j k 1 0 1 1
1 ~j 1 1 0 1
1 1 0

in A(T). This implies that,
r + l^j^k = r + l^(j + k) mod (r + 1)0 S.
67


Thus, by Lemma 4.5.1, j + k £ S. This contradicts the assumption that
j^keS.
Second, suppose j + k; > r + 1 and the submatrix
1 1 '
1 1
has the form
0 j k j + k
r + 1 j
A(T)
0 1 1 1
1 0 1 1
1 0 1 1
1 0 1
1 0
in A(T). Then j + k £ S. This contradicts the assumption that j ^ k £ S.
Third, suppose j + k > r + 1 and the submatrix
1 1
1 1
68


has the form
AT)
0 j + k j k
r + 1 j
1 o 1 i 1
1 0 i 1
i 0 1 1
1 0 1
1 0
in A(T). Then j + k E S. This contradicts the assumption that j k E S.
Thus, two ls of W cannot be in a submatrix
1 1
1 1
of A(T). Therefore, by Corollary 1.2.5, bc(T) = bp(T) = n. m
Corollary 4.5.3 gives s sufficient condition, in graph theoretic terms,
for rotational tournament T on n vertices to have the property that bc(T) = n.
It follows directly from Theorem 4.5.2 and Corollary 4.3.2.
Corollary 4.5.3 Let A be an adjacency matrix corresponding to a rotational
tournament T on n = r + 1 vertices, 0,1,2, ...,r, given by a subset S of
69


{1, 2,..., r}. If there exists a j e S such that
Vj-k -> Vq
Vj+k
in T for all k {1, 2,..., r} modulo r + 1, then
b(A) = r(A) = rz+(A) = t(A) = n.
Theorem 4.5.2 and Corollary 4.5.3 may appear to be quite restrictive.
However, for every n one can easily construct a rotational tournament with the
desired property. See Section 4.5.2. Furthermore, only one rotational tourna-
ment of order n < 11 does not have the specified property.
4.5.2 Un Tournaments Un is defined to be a tournament on n-
vertices where i > j if and only if j i is even and positive or odd and negative.
Un is a regular tournament if n is odd and a near-regular tournament if n is
even. Also, note that if n is odd, Un is a rotational tournament. 17$ is given in
Figure 4.1.
70


5
Figure 4.1. U5
Now consider the adjacency matrices of Un.
A(Un
0 0 i 1 0 1
1 0 0 0 1 0
o i o o o 1
o i 0 0 o 1
i 0 1 1 0 0
o i 0 0 1 1 o
for n odd, and
0 0 1 0 1 0
1 0 0 1 0 1
o 1 o o 1 o
i o i 0 o i
0 i 0 1 0 0
M 0 1 0 1 1 o
for n even.
The Sets {U13, U24: 6^35: : 2,n: 1,1: ^n2^ and {$33, 6^24: ^35: : n2,n; ^n1,2:
will give a set of n isolated ls for n odd and n even, respectively. Thus,
b(An) = n. Hence,
b(A(Un)) = r(A(Un)) = rz+(A(Un)) = t(A(Unj) = n.
Now we will give two classes of tournaments where all four ranks equal
71


n 1. A transitive tournament matrix has the form
' 0 1 1 1 '
0 1
. 0 0 .
A has a zero column and the ls on the super diagonal give a set of n 1
isolated ls. Thus,
b(A) = r(A) = rz+(A) = t(A) = n 1.
Note that transitive tournaments have a source and a sink which correspond to
a zero row and a zero column in the adjacency matrix. Next, we will construct
a class of tournaments without a source or sink and where all four ranks equal
n 1. Define
'0 100 000 0'
0000 0001
1 1 0 0 0 0 0 1
111 1
A = jj :
ill l
ill l
ill l
_1 0 00---000 0_
where Um is the regular or near-regular tournament matrix described previ-
ously. The ls in the top two rows and the 1 in the lower left position of A are
isolated from the m isolated ls in l since they are each in a row or column
72


with all other elements are 0. Thus, A has a set of m + 3 = n 1 isolated
ls. Now suppose there was a set of n independent ls in A. The above three
mentioned ls would have to be in this set which would leave no possible inde-
pendent 1 for the third row. Thus, A is a tournament matrix with no source
or sink and
b(A) = r(A) = rz+(A) = t(A) = n 1.
Note that the above result will hold if the submatrix
0
A!
0 0
1
1
U
of A is replaced by any matrix with a 0-row, no 0-column, and a.set of m = n 3
isolated ls.
4.6 Existence of Strict Inequalities
In all of the previous results and examples of tournament matrices,
n 1 < r(A) = rz+(A) = t(A) < n.
The next example, given by May bee and Pullman [MP90], is a class of singular
irreducible tournament matrices. This example also shows it is possible to find
73


a class of singular tournament matrices with t(A) = n. For n > 6, let
M
P Q
R S
where
P
0 1 0
0 0 1
1 0 0
S is any (n 3) x (n 3) tournament matrix with
Sn3,1 12 S23 Sn_4jn_3 1,
the ith row of R is [0,0,0] if sn = 0 or [1,0,0] if = 1, and Q = Jz,n-z RT-
M is singular since
M
1
1
1
-1
0
0.
The ls on the super diagonal and the 1 in the position (0,1) give a set of n
independent ls. Thus,
n 1 = r(A) < t(A) = n.
74


The following is an example of a singular n-tournament matrix with
rz+ = n. Let
0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 1 0 0
A is a singular tournament matrix. In particular,
Let
1 -1 -1 1 1 1 1 1 1 ] A = A
1
1
1
1
1
1
-1
-1
-1
0.
-1 ' 1 '
-1 1
-1 1
1 1
1 and xr = 1
1 1
1 -1
1 -1
1 . -1 .
be the vectors that span the left and right null spaces of A, respectively. Any
biclique partition of T(A) is equivalent to a sum of n or 1 rank one matrices
75


with nonnegative entries. That is,
A = A + A + + A(s)
for
or s = n 1.
xjA = 0T and . lxr = 0
=* xj A^ = 0T and A^Xr = 0 for 1 < k <
xT4(fe) = 0 for 1 < j < n and 1 < k < s
and A^xr = 0 for 1 < i < n and 1 < k < s.
Suppose P is a biclique partition of T(A) of size eight and suppose the bicliques
in P have bipartition sets X^ and where all arcs go from the set to the
set Yi for 1 < i < -s. Since
xf-tf = 0,
the biclique in the partition of T(A) that contains the arc
t>3 -> Vi
must also contain the arc
t>4 } V\ .
That is, since the first three elements of x; are -ls and the last six are +ls,
every bipartition set of each biclique in P must contain an equal number of
76


vertices from the subsets {iq, u2, iq} and {tq, v5, u6, tq, u8, t>9}. Similarly, every
bipartition set Yi of each biclique in P must contain an equal number of vertices
from the subsets {tq, u2, iq, tq, v5, u6} and {tq, u8, tq}. This implies that each
bipartition set in every biclique in P must have even order. Hence, the number
of arcs in every biclique in P must be divisible by four. It follows that the
pairs of arcs
t>3 > tq and tq > tq
tq > tq and i>5 > v2
tq > ''3 and tq > tq
> vq and Vg > U7
^8 > U5 and t>8 > fg
t>7 > U4 and U7 > u8
must be in the same biclique in P. These arcs correspond to the bold ls in
r 0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 O 0 0 0 0 1 1 0 0
T(A) consists of = 36 arcs. Since rz+ = n1 = |P| = 8, at
least one biclique in P has eight or more arcs or at least two bicliques in P
have six or more arcs. Thus, we can assume there is a biclique in P that has
eight or more arcs since the number of arcs in each biclique is divisible by four.
Simple observation shows that any biclique with eight or more vertices must
be of one of the two forms given in Figure 4.2.
77


Figure 4.2. Only two possible forms of bicliques in the biclique partition P
of T(A)
Without loss of generality, by symmetry, we can assume that one of
the bicliques in P corresponds to a submatrix of the form
[ 1 1 1 1 '
[ 1 1 1 1 '
There are three possible submatrices of A of this form. These correspond to
the bold ls in the matrices given below.
0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1 5 0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1
1 o 0 0 0 0 1 1 0 0 . . 0 0 0 0 0 1 1 0 0 .
78


0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 1 0 0
In each case, one can easily verify that we get a contradiction. For example,
suppose the biclique of size eight is represented by the bold ls in
0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 o 0 0 0 0 1 1 0 0
Every biclique must have at least four arcs, so there is only one possible choice
for the biclique containing the arcs
vs > i>5 and vs > v$.
This biclique is given by the additional ls in
0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 o 0 0 0 0 1 1 0 0
79


There is only one possible choice for the biclique containing the arcs
Vj > t>4 and Vj ¥ v%.
This biclique is given by the additional bold ls in
0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 1 1 0 0
There is only one possible choice for the biclique containing the arcs
Vi > t>2 and V5 y V2-
This biclique is given by the additional bold ls in
0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 1 1 0 0
Finally, there is only one possible choice for the biclique containing the arcs
v2 > ''3 and ve > v?J.
80


This biclique is given by the additional bold ls in
0 1 0 0 1 1 1 1 1
0 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1
1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 1
o 0 0 0 0 1 1 0 0
This gives a contradiction since there is there is no possible biclique with four
or more arcs that contains the arcs
t>9 > i>6 and ng } V'j.
All other cases are similar. Thus, there is no biclique partition of T(A) con-
sisting of eight bicliques. Thus,
n 1 = r{A) < rz+ = n.
Lastly, the following is an example of a n-tournament matrix with
n 2 = b(A) < r(A) = rz+(A) < t(A) = n.
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 1 0 0 0 1 0 0 0
1 1 1 1 0 0 0 0 0
1 1 1 0 1 0 1 0 0
1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1
. 1 1 1 1 1 1 1 0 0 .
81


Then the factorization
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
1 1 0 0 1 0 0 0
1 1 1 1 0 0 0 0
1 1 1 0 0 1 0 0
1 1 1 1 0 0 1 0
1 1 1 1 1 0 0 1
1 1 1 1 1 1 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
shows that rz+(A) = n 1 = 8. The factorization
A
1 0 0 0 0 0 0
0 1 0 0 0 0 0 ' 0 1 0 0 0 0 0 0 0 '
0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0
1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0
1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0
1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1
. 1 1 1 1 1 0 0 .
arithmetic shows that b(A) < n 2 = 7. The bold ls in
A
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 1 0 0 0 1 0 0 0
1 1 1 1 0 0 0 0 0
1 1 1 0 1 0 1 0 0
1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 0 0
give a set of n 2 = 7 isolated ls. By Corollary 1.2.6, b(A) = n
82


Furthermore, the ls in
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 1 0 0 0 1 0 0 0
1 1 1 1 0 0 0 0 0
1 1 1 0 1 0 1 0 0
1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 0 0
give a set of n = 9 independent ls. Thus,
n 2 = b(A) < r(A) = rz+(A) < t(A) = n.
Note: This is an example of an upset tournament matrix. This class of tour-
nament matrices will be studied in detail in Chapter 5.
Open problem;. Does there exist a singular n-tournament matrix (or
class) with b(A) = n?
83


5. Upset Tournaments
5.1 Definitions and Standard Form
The score-list of a tournament is the multiset of the outdegrees of its
vertices. An upset tournament is a tournament on n > 4 vertices with score-list
{I. 1.2. 3> n 4,n 3, n 2,n 2}.
An upset tournament is in standard form provided its vertices are labeled
Vi, u2,..., vn such that the score of v\ is 1, the score of vn is n 2, the score of
vertex v,i is % 1 for 2 < % < n 1, and arcs and (un_i,un) are arcs
in the tournament. As stated in [PS], each upset tournament is isomorphic to
exactly one upset tournament in standard form.
It is customary to represent an upset tournament by lining up the
vertices v\, u2,vn vertically from bottom to top and including in the picture
only those arcs with upward orientation. An arc {vi,Vj) of an upset tourna-
ment is an upset arc if the score of vj is at least the score of Vi. In an upset
tournament in standard form, (vi,Vj) is an upset arc if and only if i < j.
Equivalently, (vi, Vj) is an upset arc if and only if it is present in the customary
representation of an upset tournament. See Figure 5.1.
84


n
n-1 6
y
Upset arcs
t
O
2
1
Figure 5.1. Upset tournament in standard form. Upset arcs are directed
upward and non-upset arcs (not shown) are directed downward. The arcs
V\ > i>2 and un_i > vn are always present in the tournament.
Lemma 5.1.1 (Poet and Shader [PS]) Let T be an upset tournament in
standard form. Then T has a unique path from, vertex V\ to vertex vn, and this
path consists of the upset arcs of T.
The unique path given in Lemma 5.1.1 will be called the upset path of
an upset tournament. The upset path includes the arcs (v\,V2) and (un_i,un)
since the upset tournament is in standard form. See Figure 5.2. In an ad-
jacency matrix of an upset tournament in standard form, the ls above the
main diagonal represent the upset path. For example, the ls in the upset
85


tournament matrix
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 1 0 0 0 1 0 0 0
1 1 1 1 0 0 0 0 0
1 1 1 0 1 0 1 0 0
1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1
. 1 1 1 1 1 1 1 0 0 .
represent the upset path of T(A). There are 4 vertices, u3, tq, , un_3, un_2,
that may or may not be included in the upset path. Thus, there are 2"-4 non-
isomorphic upset tournaments on n vertices.
n-l
o
Q
2
1
Upset
path
Figure 5.2. For upset tournaments in standard form, there exists a unique
path from vertex iq to vertex vn and this path includes the arcs (tq,-i>2) and
(Tn1 j Vn)
86


5.2 Term Rank
As stated by Poet and Shader [PS98], upset tournaments are strongly
connected. Thus, by Theorem 4.2.4, upset tournament matrices of order n
have term rank n. This gives us Lemma 5.2.1. Lemma 5.2.2 gives another way
of showing that upset tournaments have term rank n by constructing a set of
n independent ls.
Lemma 5.2.1 Let A be an adjacency matrix corresponding to an upset tour-
nament on n> 4 vertices. Then t(A) = n.
Lemma 5.2.2 Let A be an adjacency matrix corresponding to an upset tourna-
ment onn > 4 vertices in standard form,. Let S be a set of 1 s of A constructed
by moving from row 1 to row n selecting for S the furthest right 1 in each row
that is not in a column of a 1 already represented in S, if such a 1 exists. Then
|Sj = n and hence t(A) = n.
Proof: Let A be an adjacency matrix corresponding to an upset tournament
on n > 4 vertices in standard form. Suppose S is a set of ls of A constructed
by moving from row 1 to row n and selecting for S the furthest right 1 in each
row that is not in a column of a 1 already in S, if such a 1 exists. All ls above
the main diagonal of A are in S, since these correspond to arcs in the unique
87


upset path. S contains the lone ls from the the first two rows and last two
columns of A, since A is in standard form. Furthermore, the 1 in S from row 1
is in column 2 and the 1 from column n is in row n 1. Now suppose that for
some k, 3 < k < n^3, all ls in row k are in columns which contain ls already
in S. Then vu is not a vertex in the upset path since otherwise it would be in
S. Thus, row k has the form
1 1 1 0 0 0.
V------v------" '------y------"
fc 1 1'S fc+1 l's
This implies that the ls in S from rows 1 through k 1 must be from columns
1 through k 1. Since vu is not a vertex in the upset path, there exists an
upset arc {vi,Vj) with i < k < j. Thus, the 1 in S from row i would be from
column j. This contradicts all ls in S from rows 1 through k 1 being from
columns 1 through k 1. Therefore, |5| = n and hence t(A) = n. m
For example, the ls in the upset tournament n
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 1 0 0 0 1 0 0 0
A = 1 1 1 1 0 0 0 0 0
1 1 1 0 1 0 1 0 0
1 1 1 1 1 0 0 1 0
1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 0 0
are the n = 9 independent ls in the set S given by Lemma 5.2.2.


5.3 Real Rank and Nonnegative Integer Rank
Complete results concerning the real rank and nonnegative integer
rank of upset tournaments are given in [KS90] and [Sha90]. Theorem 5.3.1 is
an upset path formulation of a result given in [KS90].
Theorem 5.3.1 (Katzenberger and Shader [KS90]) Let A be an adjacency
matrix of order n > 4 corresponding to a upset tournament T in standard form,.
A is singular if and only if the upset path ofT has one or more of the structures
given in Figure 5.3.
Theorem 5.3.2 (Shader [Sha90]) Let A be an adjacency matrix of order
n > 4 corresponding to a upset tournament. Then
r(A) = r z+ (A).
Corollary 5.3.3, which follows from Theorems 5.3.1 and 5.3.2, char-
acterizes upset tournaments which have bp(T) = n 1. Since bp(T) = n 1
or bp(T) = n, this completely characterizes upset tournaments with respect to
their biclique partitioning number.
89


Solid vertices are
isolated in upset path
6
5
4,
3C>
2
10
Hi
n 9
5* n-1 1 i+2
40 n-2 O^ i+1 O
n-3 O i 0/
J n-4 i-1
lO H2 h3 h4
15
14
13 Oj
12 Oj
no;
10 o;
9;
8;
7;
6;
5;
4;
so:
2
16
h5
n
14 n-1
13 0 n-2
12 0 n-3
11 O^ n-4 O',
10 O^ n-5 0(
90^ n-6 C)
8 o' n-7 o;
lO n-8 o;
60^ n-9 o;
50^ n-10 o;
40^ n-11 d
30. n-12 o'
n-13
i+11
i+10 0(
i+9o;
i+8o;
i+70;
i+60;
i+5o;
i+4o;
i+3o;
i+20;
i+i o;
i o'
i-1
16
H6
h7 hs
Figure 5.3. Structures of upset path that cause singularity.
90


Corollary 5.3.3 Let T an upset tournament on n vertices in standard form.
bp(T) = n 1 if and only if the upset path ofT has one or more of the structures
given in Figure 5.3.
5.4 Boolean Rank
In this section, a characterization of upset tournament matrices with
respect to their boolean rank and a best possible lower bound for the boolean
rank is given. In addition, it is shown that the number of nonisomorphic upset
tournaments with equal biclique cover and partition numbers can be given in
terms of convolutions of the Fibonacci sequence. These results, together with
Shaders work [Sha90], give a complete characterization of upset tournament
matrices with respect to each rank and with respect to their biclique cover and
partition numbers.
Theorem 5.4.1 Let A be an adjacency matrix of order n > 4 corresponding
to a upset tournament T in standard form,. Then bc(T) = b(A) = n q if and
only if the upset path ofT contains q copies (total) of the subgraphs HQ and H
given in Figure 5.4-
91


Full Text

PAGE 1

'46?4@A. '.B./AAB./ A6ACD E8$
PAGE 2

A." #" AG % ) ) G 6# ." 4 ---#' 4** :KL

PAGE 3

% AG +. A '&4).'BA# !(E 8 $ < F".G 6# '4 A#%"" &)## )!( ( #M-N #($($( #%( #%&&) E 8 < F-%%!(& <22< 6#"%!( O& <2HH$6)*.#) #""N %%( !(" #"%#) <22<$4)(-N P< %( -! P< %N *%( # $(%N <228$*# )#)#( &( %#((N "$* %(

PAGE 4

%(#) $% %&&) #)) & $#%Q%($#)N *%(% &) "K # G 6# @

PAGE 5

AA4 ""6" R

PAGE 6

4DS6AB )#N ")$G 6# ( #$#$#" "( )$###% %)% !!# %( ") %(%AN )"4A) %(( #$"$#"( #) #"" %(!"B4 )"4A)## ""% "#$#)##!)) #J )"##$"$ $"))# %J% 'S($/"A)$$ "4)## "-$A"$GD"$4" A) '%4%%") %$A)"%$"$"%$ %%"&(%%# "$%(" $6"'$)# % %%""

PAGE 7

4 # 4 < < <'(# < < >. : < > <'&4). : < > >'( 0 < > 7#)#( H < > :( <8 < > =( << < > 06%' <> < > H'( <7 > 4S&( <= > <'# <= > >A# <2 > 7!SA >< 7 >= 7 <" >= 7 >"A >; 7 > <. >; 7 > >( 7< 7 7'B 72 : :H : <. :H : >B : : 7#-# =< : :'( =: : =4S(& 07 : = < 07 : = > H8 : 0!& H7 = ;: = ( ;H = 7(#)#( ;2 = :'( 2< )

PAGE 8

4 =&'&4). <80 0 <<; 0 <' <<; 0 >A# <<2 0 7" <>8 0 :"A <>8 0 = <>< 0 0 <>7 H <>: )

PAGE 9

B < < A# = < ># #)#< <$)%% & = < 7# #)# < < $ & = < :!## !"# <> >
>A#"# >< > 7'#% $%! &#'$(! &#) >> 7 <"##%=+ :+A,,T *!"!##)!"!##) !"!##)+ >H 7 >.## :< 7 7.# ,-. !"# !"# :7 7 :)"## # # / :: : "%&& 0 1!"# H; = < %-+%,%% & '2 I < '2 %" ;= = >$!& )!)! !/3# +)V ), ;0 = 7#" 28 = :#%&)# 2> = =' % & 2= = 0%!*# 456 45 <8= = 0: -0= T <8;

PAGE 10

< < < '(# )###%&N W@G2;X#)## ##$#$ $#$#"WSH;X A#%" "&) ##)!( #($#)#($($ ( WYX$' W'/;8G 4 W4B.X$/W/27X$B#" WBG6.2X W28X$-#$/ W/627XZ ($6#"W62
PAGE 11

%(#%&&) E 8 $F-%%! (& <22<$6#"%!( "&W62
PAGE 12

(% (#) $% %&&)#) )& $#% Q%($#)* %(%&) 4%#)"(#"N #&)!( 4>%#%%! (&#J"! 47%#) (""%N # 4:% #)(# 4=#) %(% %&&)#)N )& 4 0 *(%$ %$#) 7

PAGE 13

< >. #$ "!# %J"!N ## !"# "! # %J"! ## !"# J"! #!J"! $ :J"!# 8 K # < "! #&7 8 K < > <'&4). $%8 %9$ #B$" $%!:# N #)# : !$# #)#< <$)%%& #< > &)#)# $%8(9$ #B$" $(!: ,$ ## : !$#[\$#)# < < $ & #< 7 :

PAGE 14

! #< < A# 7 = ]^= 7 _0 #< > #A #)#< < )%% & -^ _0 7 #< 7 # $#)#< < & =

PAGE 15

< > >'( $+9 E 8 $F-! : "0+ :,$ + % 9 + + 8 $F-! + E 8 < F-! :T % +<` K<] < < 8 $ 88 8<< 8 8 0!B G>!0 < ` < 8 < 8 < < 8 <8 <8 8

PAGE 16

K % %% ]K % % ] % %% % %% %% Q % % % % & %(%&) # T !"# # < > )"* '()*+),) :E8 < 6< > <+B#" WBG6.2 7#)#( ;;+ 9 ! :$" V+ :,$L a H

PAGE 17

% 9 + + ! )#N )#$ :T :E 8 < F-!$ E 8 < F#)#(! :&) ($)#)#$% : !$ :T "!# J"!# #)# < < : K < < % % %% % % %% % % % I % % 1 %% K % K I %% %% % % 0!7 U % ] % % W % 0!0 8 8< << < 88 88 88 < 88 ] 8 < < G!0 W 8 < 8 8 8 8 X 8 8 8 8 < < W 8 8 8 < 8 8

PAGE 18

# %% %# % # # # %% % %%% % / / % % " % & % (& # TA+ :, #< 7 )"* -:!TV!4Q! : )#)# &* + 4)"$)"&* + N ^!K : )#)# # $%)6< > > 6< > >+B#" WBG6.2
PAGE 19

< > :( + +(,! : "+ :, + % 9 + + )$ :T (! :&)( $)$% : *( #6Q: :T 1 <88 8 < < 88 <<< 8 8 << < 88 < < 8 88 < @ K < 888 <<8 8 <<< 8 8< < < 88 < < 8 88< 1 < 888 <<8 8 << < 8 8< < < 88< < 8 8 8 < ] < K < < 8 $ < 8 8 8 < < 8 < 8 8 8 8 < 8 < < 0 0!0 # < 8 88<< 8 <88-<8 8 8 < 88 -< 8 88 <<< 8 8888 8 0!0 8 88 8 8 8 <8 88<<] 8 <8868 8 8 <88-< 8 88< < < UX 8 < 6 < 8 8 B! !0 W 8 < 8 8 -< 8 X <8

PAGE 20

< < P 8< < W 8 8 < 8 8 -< X` 8 < << < 8 < < < > =( 9+ : !"# %#* : :E 8$< W-!$ : ( %% : /$+ :, !R : $ :J" !# $ !"# *!# !$ 4 < 8 < 8 1 8 8 < 8 <<8 < 88<8 %) :Q#)! !# # !"# #< : %%

PAGE 21

#< : !##b+ :, < > 06%'6< > 7$6< > :$4N < > = %#%( &)# 6< > 7+B#" WBG6.2 :!6< > 7 <>

PAGE 22

6< > :+B#" WBG6.2 = 5- 0 5-=67B9 : <-+3< $!"#2+ !$aJ"! K 8<8<<< K % % % %%%% 8 <8 <8 8 % % # #)#< <$#)% '"4N "< > =$ $="#)$%!#2C $0+ :,T $%=# T> %)" !&)#*% < > H'(#)#(($+ :,d `+ :, %

PAGE 23

)"&&)# 6< > < < > > 0+ :,d-`+ :, "E 8 < F-! : $"E 8 < F-! : V+ :,d !"# % $!"# + :,+ 8 < F-! : $ K % % % K % % % <<<8 8 8 8 <<<8 8 8 8 <<<8 % % % %+ :,T: # :#)! R '"4"< > = 0+ :,\ 0 :T !"#D$!"#) 0 '$J"! :# #)#< <$%) 7T+ :,\ $="#) > S*%( %#%" :E 8 < F-!$ $!"#D Z`+ :,d !"# + :,d ?*!"#D!"# <:

PAGE 24

> 4S&( > <'# 9 0 -"%!" %-" #> < 9# #%"#W@G2;X #> < A (###% # )" $%! # T $(= # %# > < <+ W@G2;X, 5$(9 -;(<<$%! # T $(! # E!##%" #-" '"$4--# <=

PAGE 25

"4"> < >%)" ZJ"!#4:# 4"> < > 5-"<%/%%9-F-$( ;(< < + :, D$!"#)?*!"#)!"# %#!%%)+ :,d+ :, : J"!4:-# 6 :T % % <<8 8 8 <<8 %% !"# 4:-7T+ :,d0+ :,T *!"#)!"#) : G(($9 !"# 4:-#$% $!"# $ :J"!#$ + :,d0+ :,T V-+ :,d !"# <0

PAGE 26

%#%!%!#% !"# + :,7 % $!"#!"# : $!"#!"# 7 +, !"# :Q % :J"!"# $ T #% %# 1 %% %% 2 % % % % ///% -P H4 -^^8K H4 4 6&IIIH : T:$)# # :$0+ :,\ $="#) + :6,T: $+ :,T7 +,T 4 H 3/(4"3(4 :K
PAGE 27

$ ]< <8<^ ]8 88 8] << 8 < T 8 88 8 8 <<< 8 8 88 8 8 < 8 < 8 88 T 8K K 4 H $:> T "9 )# 9 4C $0+ :>,\7 4"$!& )# 53$6 CJ# #& $ 0+ :>,T7 $+ :>,T7 + :>,T 4 ) 7 e< #) ":$ $ + :>,7 + :>,: <;

PAGE 28

G(($9 !"# -#$% 4 &78 3/(4 0+:, K!"#&L ++ :,] > >A# # ;%% % "%) # ;(<% !" %"%) > > <+/ W/627X, 5-;(<%M ;(<< $!"!##)!"!##) I `+ :+A,,T !"!## / W/627X%) (#"# "#> # )*" 2 > #" # 99; )" ##" 6#"W6 2 > >6> > 7%%( <2

PAGE 29

> > >+6#"W62 > 7+6#"W62 > : 5-;%%(<%;(<<9M 9; 0#"# )!L!)! )$ 3/ $ "# ] ##> >"#$$ )6> > : 6> > : N )$%7 <

PAGE 30

#> > A#"# 4"> > = 5-" 7!SA $ $(!:# )$%!:# : -# : "## 6> > 74" > > =$ ="=:## -# %# %!%%) $(! # T $%! # % ## ) $!) % $!"! ##)!"! ##),, ## T !"! ## !#% ### $(! #)$%= # ) 6 & #%J)! N TE! *-,$ F=KT EeLR$JL > $^-$aEL_F% )O `< & #)#> 7 ><

PAGE 31

\< H #> 7 '#% $%! &#)$(! &#) %# % K$" #"# & %%#%a +<,+ N/ ,$ P/ # $+ N/ $JL,# +>, !Q/RQ/# +7JI>"7J`,# / \< 9 $%! #)$(! ,T =! # a > T< > $F# %%#-" $ &A #)#% 9 $!"! &##)!"! &##)?*!"! &##)!"! &##) !#%!$ # + 7d + d T 9 )#$%%#[U>)% 9 $ $!"! +## T+ :+[$,,T ,"! +##)!"! +##)+ 22

PAGE 32

+ T /* gE8$< B/S E< >$7 F$ $!"! +## T+ :+'J,,T ?!"! +##)+ + $ ) =$#%)<<# + S%#!) 6 % ] % < % % & T %%% & 9 % %% %% % % 9 %% %% % %% % K % ] ] % Y % % %%% $ J P % % % % % % %% % % % I % % % K % / % % : % %% % % % % % G =!=*! 6 ) =$)# + 7 D+D =!=! :UT :\T :+J=,)" % I IG& # 6 ; ; 6 # ,< I ;; 6 I ; 6 = >'((& = % IG 6 ;; ; 6 ]47 6 I ^^ G& 7 6 6 I I 6 & 6 I ;; 6 $ 6 I I 6 e-V0 47 6 I I 6 4 $ 6 I I 6 >7

PAGE 33

:-T Uhd P %QIII 66 7 G + \; : 69:9 %#$ + # + $ $!"+9# \ + #) $$ + T# + & /$$`+ :,d + 7d +D 0+-:\,T -`+ :L\,T + S + #*$ "%#" "+9 $ ="+9# T + +) / BE8$$7$ F #) :e$")" !"+9# T + +2 7 !$! <<< 8<< <8< 9 -:U$ + T '+ :,T ="9+# + )N #)#%") ) %)) L 2' 7 ) >:

PAGE 34

7 7 <" E8$F-! %$ !! 0 0"0 T G "?" C % : & G *! $ %$ %$ )"<%8 ! % 8 8 <8 % % 8 <8 8 !"! % % % <8 8 < 8 <8 8 $"<+<$:, #8%#! %# %(%%#)W'2>X >=

PAGE 35

7 < < 1<9 : %$--<;(< !"# ;%% 4"7 < > 1<9 : %$--<;(< !" 99; 4"7 < 7%4"7 < >> > > 4"7 < 7 5-"%$9< $!"#) + :,T `+ :,T+ :, %#!%$" 2 >$% )!%)( + +CD+D 6 :T G % !'+* >,!+P +* <,! ) 8<<^^^< <888 % <88^^^8 >0

PAGE 36

='+ ->,!+aP<,! ) 8^^^88< 8888 8888 8888 !+' >,!+aP<,! ) <8 88 8<^^^88 88<8 G !+'C#!'+* <,*! :" # !"# "# #7 < 4"$+ :,T + /$ $!"#)?* + :,T+ :,T[+-:,T + >b -(`> -(`< 7b #7 < "##% $!"!## TZ `+ :+A,,T !"!##)!"!##)+ !"# #"# /$! %)" + >d +D %#"# ) 0+ :+[\,,T`+ :+A,,T+ :+[\,,T !"!## T + >H

PAGE 37

7 >"A 7 > <.E8$F-! : (%9($ !# + %X % % % % 8 8 << <<<8 !"! <8 8 < % % %% <<<< "$"< +: :,#8%#"! 67 > <*" '"W'2>X 67 > >#) "!" >;

PAGE 38

67 > <+'"W'2>X, @"$=67B9-M : (%9($--<999%< <<%<%9%.% : -%9( $-!"# T 4<9--%9($ R 9< 67 > > @ : $-%9($95-B T< 9( %9/!$<#<%< : %9($ 0" "! GT<$% / !"% S#"$U$-T$UT< T8< DDP/ V + /+ ^^^8<8^^^8<8^^^ / T<#T8$#!)% + %!% + 5 ^^^88^^^8<8^^^ :)%)) $"67 > <$ :" ] >2

PAGE 39

7 > 7%%"N %)"" #" )#)67 > :%N (" 7 > 7+'"W'2>X, @ : $=67B9@"7$<9$-9 : $(%;%< <9;< < 1< : %$--"%9($ 67 > :+'"W'2>X, @ : $%9(M $=67B9-2 > 1<<(99%0 -;9<
PAGE 40

1<94%8 < $;%9 -9< < DD95-92C<9 > <9( + /# 8 7 > >(%%($ ($#)#($("N ($($#)#(" !&!Z%)$ ( ("! & W'2>X $("! & 67 > = % #(#)#(" #)7 > 0 67 > =+'"W'2>X, 5"%9($ 9< + :,T 7 > 0 5-"%9($9-2 7$ < ) 7< 1?+?.

PAGE 41

0)$%% % : "! 2 7$ : 6 :"E8 :$ 0 K <8 :$ 0 #% 7> << <<

PAGE 42

%@@9% K<8 8 8 8 < < 8 8 8 << 8 8 8 88 < 8 8 8 8 ^-4 % "! 4 &<#% / / %$V> !/# 8 '""$ K << K << :! A << < < BC &< 4J &< 4 #< %<$)"$! )' <\> !/# 8 $ : K << K << 77

PAGE 43

'"67 > = :Q : ) << << )" $"4"< > 0$ $!"# T 4"7 > H 5-"%9($9-2 7$ < $!"#)?*!"#) [+ :,T ""% : < TVT << << )" )"$[+ :>,T> $!"# TT+ :,T !"# 0+ :>,T `+ :>,T+ :>,T< ("! %#!%+ :,T P<$ 'C 7:

PAGE 44

"! 6 ;; %# %;; %%;; ; ;% ;;% % ;; %% # !"'5# #""# $"7 < < :iP 5 /$"7 > 7$ :i "$"67 > >$ :i" )"% !"%%$ %"%#%" 67 > : : "! 2 >! 7=

PAGE 45

0 %@ D 9% < 88 8 < <8 8 8<< 8 88 8 < 8 888 < < % "! 9 &<#% / / %&<#% %< DD9 )67 > :a%)$ )#)###"#) "! S"! %+ :, )' >"# & <88 ] <<8 8 << 4 B % "!% #)9 P< &Q 4J 4C "T<% / +,!"%Q ) )# )* #%&< 4J 4C )" 70

PAGE 46

! % 1 % % % % % % % % %% % % % % % % % % % % % % % % % % % % % % %% % -<<-
PAGE 47

% ] % % K % % %% % % %% % % % % %% % % % % % % % % % %% % % % %% %% % % % % % S%$%%+ :,T<0T > S#%% % "N $$%# !" 5# #" $"7 < <$ :5 /$" 7 > 7 :" "$"67 > >$ :" >) <% / +,!" %< !"N T70T=:%( P7T-7 7 :T=8$)" (%#J

PAGE 48

4J7 > ; 4;;+
PAGE 49

7 7 <+'"W'2>X, : =67B9"-M %9($-!"# 9$(;(< 4"7 7 >+'"W'2>X, : =67B9" %9($-!"# 999$(;(< 7 > 0$#%"N J" 2 74:$% 47 7 >7 > H#)-#% $!"! ##),, ##)!"! ## ) 4"7 7 7 4"7 7 7 5: <%/%%9-2 7 %M (;999$(;(< $ < $!"# T /3(4 T !"# *#N #" $%% :8

PAGE 50

%# 6 #% N TE! > !F T T = PB # % -9 N [ = # [ # #7 > % $9 ## # 99$9 #% )"##-" ^^ #7 > .## 7 7 : @"$=67B9"%$-!"# $9$(;(< 0-"#%J" ") "! # 6 : 7 !"#8a :<

PAGE 51

# % 0 # #N #LLL# , #%# +!J "$,%!$[ =.# +"-[ =.## # !"# # 7 7 !"# !"# -" !"# "# / "R $" 7 > 7$ : 4)"$-:! T N ##%J"! : '" 7 > 7$ "$"7 7 <$ !" a, "# g # 0 % # )##+!$"J,V # # #7 7 $ !" ," $ "# ] !$! %% :T 8 <8888 <<88< <8 8 8 8 8 888< #7 :$)"# ) ="# # # \$'7$ = $" :>

PAGE 52

#7 7 .# ,. 4 !"# !"# 7 7 : ")" :")# # !"# #" 7 < < % "#)"# # $#%)! )!#)))! $ :" ) :"%$%$$ )) :) %)) 4"7 7 = @ : $=67B9 : %$-!"# 99$9$(;(< :7

PAGE 53

5 5 5/ 5 #7 : )"## # # B ::

PAGE 54

4"7 7 0%47 7 =7 < > j@ 47 7 =$7 7 0$7 < 76> > 7#)#%(& 4"7 7 H 4"7 7 0 @"$=67B9 !"# 99$9 $(;(<-="# 99;;(< 4"7 7 H @"$/%%9%(;99 $9$(;(<< $="# T+ :,T ?*!"#)!"# .7 7 ;*% "# .7 7 ; @"$8=67B9@ :R $<9 $-9 : $(%;%<<9;< < 1< <-;98 !7# !"# $9$(;(< !C# : %$9 :=

PAGE 55

!Q#"&-%9($9 !F# !"# 9$(;(< 0+<, U +>,$+>,+7, +7,dUT\+:,7 7 :$7 > 7 7 7 <$)" $+<,+:, ] :0

PAGE 56

: : <. # 1 9 ) + 1 V 1 S% : 999 : J"!# ) 1!"# %%J" : &E8
PAGE 57

: >B <22<$4%( : > < %#$" %""$%"% )($ P< /$#)# ((-<$(% %( 4": > > : > <+4W42 > 5-"999< P 7 499+8 (%-%: 999< -+ :,T+ :, '' < ?W!"#)!"#) :;

PAGE 58

G(($9 a4"#" 4W42 > %(%( P< 4"#%+ :,T < %-`+ :,T <)") /%)$%(%%)+ :,T < #): > : : > : @ : $9991< !"# TP< -<;%%%9( -1!"# %;% .% + :,T --;%%%9( -1!"# <<9% 0#" 4$ C + 0? 0 / D/ $!! 0 K "3 Y UV> 0"0 T :J % "Q5D/D+ J"! Q # :2

PAGE 59

!"# T < B2 < >$[+ :,T < ] +$:,T P<-! :$%(% #!") W.28X%) !$&&& 9$ "%) (#^=8

PAGE 60

6: > =+".W.28X,LL!T+!Z!>$ #1( <(%-999< : 7#-# ; ))& $ ; -!!%&% #M ; !%< $ ; -!!%%& H P%& :-#-$ ) ))# #$#4W42 = : 7 < ";99; =<

PAGE 61

06 #-!)T+$ C#1 ) :)T8 : 1 3 [-[ : 3 K 8 K I 8 %:I$TEa /'B D, 3 E/E ) 8 -K ) !"<=V-% )%)! $ P<$$ 9?9 EE %T6 1 Tk T 8 T T\)T8 :# 4": 7 > 5-";999< + :,T V-+ :,T[+-:,T =>

PAGE 62

-## #%&: 7 7 : 7 7 )#"# : 7 7+D*#WD28X, @ T+Z>ZP$i, $%%5cc>d <99<<%%; : 7 : 42 :$ ;999;M 0)-#-!N J1 P CWC& 1 C %%!"[ c> I O> $ CXQ$C' > C ) *C!C2Y G%7`> '5CD 7P 2 : C!' <, P @ =7

PAGE 63

$": 7 7$-##G(($9 (#-# !$ 2 7 & %e : :'( '"4": > >$$#)#$( -!-< /%)$( W'62>X%# 6" 1+ "#$ /% "#% ^ & "#$ #% # % 1+ "#' % ^ &"#( #( # # 1+ &"#) #( # #* 1+ + #( # # # % 1+ % +)C -9 -<$ 0 + #)" #% ^ ^ # % ^ ^ ; ^ ^^ % -^ % F ^^

PAGE 64

-:$ T ,!! IJI P I ,!! ,P+aP,IJI ,-$)., "9 T`V-V ?T-: 4e>T`? -< T-:--:->-^^Y--:I % T-:--:,:-^^^`-: == + <,

PAGE 65

!$ T 9+ T+>,+H,T<:$ #%% % %%%% %. %% % %%%% % % %% %%%%%% % % %% % %%%% % % % %%%%% % % % % %%%% % %% %% % %% %% % % % % % % % % % % % %% % % %% % % % % % % %% % % % %% ] %% % ] %% % % %% % %% % %% %% % %% % % % % % % % % % % %% % % %% %% % % % %% % %% % % % % % % % % % % :T #% <:!H H!<: $=1 ,dH =0

PAGE 66

6: : <+' W'62>X, 4%<;2 > --M %; 9=$!1 ,a 1 99 FdP G(($9 a4)$e 4J: : > @1 $<9-$1< "!1# ;<% ="!1## T *!"!1##)!"!1##) ) "!1# #Z%)$"N : : 7$%(% !1 ,T $#6: : :$ % :+,#) -% 9 # )9+) +<8,+<<<,T<<<8 S%%##"!N ; ## / : -:+<$J,$ :+>$ / :-<,$^^^ "!'/#"!/ /<$<,$ :+-J-->$>,$^^]$-:+$ / <,

PAGE 67

: : 7 5-1 <9-$< !"=1## T 0F 1 GH<<< <(/% 1 <-`<,!+ 9 >-P, I< 9 < < (/<<< W ,! &C!9 P%, :

PAGE 68

6) / % #0 9 `>< < 3BE<4)3//4 #Q##%% 9* > # 1 ## %> <%#) 9+ T+>`:-<,T !1#)9 6: : : @ Z!,# $<9$-A%<%9;=67B9, K 1+ 19 -< C ^ ^ #!$ 1+ -<^ ^ P 9 -> 9 -< 1+ ^ ?P 1+ @ ^^ 7 # # # /F % B $<9-$1< "=1# ;-Z) ?3K'4 K+?-, +?^)+U, +?-, $ C & %$ ; -@+-, ^ +Z!# ^-K+?, +Z!# & +3!# + $ -@+?>, K+?, @+?, C -@+?:, V@+?7, ^d@+, ^a+?-,7\d < -a=2

PAGE 69

Z !9'#9 <, + 7 + < + 7 +' 0 > +P, [C I +-, D> Z+P, + 0 +->,1+-, ]\ > +P<, > [ >K J-6, ^ + <8 7 0 <8 9! P, /!9# <7 0 9' <, 9 C 9! >-< ; 06 Z!,# R%# E8 , 2#4 Q -# %4 @+, 6 # P?->Q ^ # % # 1+ /O/0 ^L-# -? # # / -?K+ # 7 ? # e> #7 #$ ) 1% *Q3O4*J 1#) #5 %! 0 6)) % ) 8 4" +9 & + (%#)")T8 #&<# ++ P< # C+!9' < #+ <# 9+ %#)%#" 08

PAGE 70

R 9+ P 9!9 `<,$$$ JE 8T---------------------+LK -^^ ^` Q, -^^^!+ P<,+-+-,Z:-6 %% <, *6 8T----------------------+$K!-^^^` 78 *II !+ 7,++I,`-^^ 8T Q!& -^^^-,+' !9 P< #9 $ -9!9 -<,O$ 8T+&------+# --------`^^ &) ]@ &-^ +* ` 3+ K C+ I$^UU1 + ) 8 @#$ Z `U 3+ f 3+ T8 8P-^^-:31+ 0< l @+# 1 39+ `^^^39+# 1 39+#

PAGE 71

$"6: > =$ 6'*S T T ?-< 1+ $<9-$1, K@+?-, $ 9!9 % -<, !' <, 9 !' >,+P<, 7 < -@+?, a!9' <, & +P<, 7 a+P>,+P6, aP +P, <8 a a a @+?A @+?, +?A a a QC /N3O4 -@+?A Q+?A )+,+?[I$, CN34 aP7aP< aP0Z-7 --<8aP0 9!9* <, > +P #9 / I+ 9 <, ; 8>

PAGE 72

(:,$ %" E<$ >$ $ F )! */ +-`-<, / g K % % % % % % %% % % %% %% % % %% % % %% % % % % % % % %% % % % % % J"!#` ;$$-= <$>$ $F 1< c=JTc / D2 `

#)" E<$ >$ $ F cJTRJ$" 1 # / B 1 $ :+HK,::+H1,-`-LT L 07

PAGE 73

% /* $ $ ;$$=7CB 5-$ B< $%!1# T 06 1 T`<)$ 8$<$>$ $ #)" E<$>$ $ F /H /*+ +-,B /'+ +`<, 0:

PAGE 74

+ E< > 6 ] QJ"! :+HQ, # '^I*/ +, ) 8$< '" ] Qa$%J% Q ] %Q ] :+HQ, K << Y <
PAGE 75

/ + /*+ "!1#) 8< << 8<< 8 < 8 < 8 /'+ g /'+ +`<,V / P +D 8$ 8 +/ "!1#) 8 // ` + 8<< <8 < <8< <8 < < 8 +'/; I*I P !+'/# g :-<=+ P /#) :-` /+)/+ +`, /'+ +-, V= $! < << !!

PAGE 76

J3 #$%#"$%% !%-:+, %#`<$ 8 8 "!1#)*/< < < 8 8< T C+ Q# N #) %-Q #:-<$ / K:+D -< << << /+ / ]`] + 8 ]8<< <


PAGE 77

$"6: = < / + 0 /+ $ / +2 :
PAGE 78

8 /*+/ +

=$ $%!1# T $(!1# ) 4": = 7#)$#$ 1 ))" $%!1 ,T %): = >4): 7 > 4": = 7 @ : $/%%9%(; 91) -< % 8$ <$>$ $ ;$$02

PAGE 79

% & U 5- 9 `<$ < $="#)!"#)?*!"#)!"#) : = >4": = 7"&) /%)$M-" "% : = > $"N D <<)" (: J I )% '2/ -/' ))#) # -# ) $ $ #) #: < H8

PAGE 80

(%,M: %J" K8 8< ^<8 <] <88^^8 < 8 8 <8^ ^88 < "!# T ZZ Z K 8 < ^ ^8 8 <8 ^^<8 8 8 < 8^ ^^8< 8 "!#) ]88 < ^^ 8 < 8 ] < 8 8 ^^< 8 < 8< 8 8 <8 <8 < ^^ 8 8 < 8< 8 ^ ^ < 8 8 <8 < ^^8 < 8 P> a 5H<6 e C FE ) %#) Q )$)" $="#) /$ $!"!##)!"!@-##)?!"=##)!"!##) %%%#)%%(&

PAGE 81

P< )! ") 8<< 8< 8 8 8<< 8< 8 :*Q##) Q $ -< 0+,T+,THM-+,T[+,T P< ))(% *%*J"! !$%% %(%(& P< A % /// % <<88^^^888< <<<< -:TaaZ 9J <<<< <<<< <<<< % #;; % #-#!)N Q%%<% 9 Q 9 "% H>

PAGE 82

%8 9 :7T P< Q %% Q ) Q%)%%)N <% $ :!% ( 0+ :,T+ :,TV`+ :,T !"#)' < )%! ^8 :KT 88 < < < :""!%8-%$8-$ 9 Q T 7 (!T)+R< )! P
PAGE 83

<<63(4* 2 !&< ,) 0 ` % 0) 8<8 88< <88 "+P7,!+P7,!% ]-7$7P^^^P^I :$I7 P
PAGE 84

I<<)<
PAGE 85

GI : T : +,` : + > TT < T 61 :!T8 T\! :+,T 61 :+a,!T8
PAGE 86

)E&$>JVQ 7 FE: ; #F "$)" ;& 0 &) EL < !J>ZVK 7 $&$ 3 a *h0F =b <5 )"& 0 )) /$ G )"& 0 )" % @ 7 P" < LK: PV W 3J 0K b P 3 C K7 Q# @ 7 @#P")# ; ?&; 'b ; '; W 4 : 3/ '; & 0 ]8 <8 8<<< <

PAGE 87

#: > "%&& 0 1!"# S#"$"""$% & 0 : R#)% H H;

PAGE 88

% %% <<<<< << 8< % <8 8 <<8 <<< % % % % 8<888<<8< %%%% % % 8888<888< 88888<<88 $")"%# &*#"Q 8<88 <<<<< 88<<8<<<< <88<<8<<< %%%% ") 8<888<<8< % % % % % % % % % % )"&)$" &# & P\ & '2 # &#)" ^ %% %% % % ] %%% % % % % %% % % % % % % % % %% % % % % % % % % % % % H2

PAGE 89

I<< P Q0 6K7

PAGE 90

") Q K8<88 << < <
PAGE 91

IL K8 < 88 8888] 8 8 < 888 8 8 <8 8 <888 8 < < 8 8 < 8 8 8 :T < < < <88 88 << <8 8<88 < < < <88<8 < < < <<88< << < << <8 8 < 88 8 888 8 8 8 <88 8888 8 8 8 < 88 888 8 8 88<8 8 8 8 8 8 8 8 88 <8 88 8 888<8 <8 8 8 888888 < 8 8 888 888 8 < %-` +-:, T P< T; Q<8 8 88 88K 8 <8 8 888 K 8 < 888 8 8 88 8 8 < 88 88 88 < 8 8888 8 <8 8 <8 88 <8 8<88 8 8 8 :T< < < 8888 < 8 888 < 8 88 < < 8 8<88 < 8 88 < 8< 88 < < < 88<8 8 8 88 <8 8 <8 < < < <88 <8 8 88 <8 8 8< < < < <<88 #%0+ :, D' >TH Q ") % % % % % 8<8<88 <<88<8 %%% % <<<<88 #) P>THQ '"4"< > 0$ $!"# T P ;>

PAGE 92

&I& K % ] % % % %% % T %% %% %%% % % %% %%% % %%%% %% % %%%% % %% #) T2 $ C)$!"#D!"# T-`+ :,d ="#) a!! N %4= G(($9 A!#-!+ ,%0+-:,T ;7

PAGE 93

:I :%+ % # ) (9 \:)%E< < > 7$P:$P7$ P> P>F )) $ C &< P> )!$ P<>d d P<$+& &, !W# W.X$ !" ""# )&$ C )"# "%% 3 7) N (% / J +& $5 D/ &)"$+$$ 3/# "" #= < ;:

PAGE 94

e -0 -]\ > #= < %-+%,%% Ph C IP\ %" 6= < <+.W.X, @1$(9 -91<1<8(<-93J< (<%-<(%-1 &#)6= < <% ((< +& C# +iI # #= > N J"!$Q) # !$Q ;=

PAGE 95

) ]8 <88 88 888K 88 <8 8 888 8 <8 8 < 88 88 8 < <8 8 8< 88 8 < < << 88 8 88 < <<8 < 8<88 < < < < <8 8 <8 < < << < < 8 8< < < << < <<88 + :, ) Q"II ]$7$ X2 "" $>I:N ) #= > $!& )!&)! +& +-KP < $), -!

PAGE 96

:IP ".W.2;X$#" $": > :$ )( #)6= > < 6= > >#)%" %#)( "# 6= > < @ : $/%%9%(;(M 92 : %1 > @ : $/%%9%(;(M 92 : %-9@$-7-"%% $9;-97%;-<-<;<7%< <%9-7(-%<71< ccT <%!"#) 06 :J"!# 2 :) : ")#%<%# #< %<"
PAGE 97

=Q%%% : $<=%< >< % P< % + 7d +D 7$Q% + %a" + )!%% $% + << <88^^^8 K /$ K Q=%<# + P< <# +' < + )!$! +$ /# % D+D/ $< % % / Q %#(P<# #(P< $ccT +-:,T ] !$Q! % % %% :T < < < < < < % <<88888 <8<8<88 <<<88<8 %%%% % <<<<<88 2Q #)"6= > > +

PAGE 98

: +W28X, @"$/%%92 : %(;(91< ="# TZ-+ :, 4"= 7 7 %%= 7 <= 7 > N *%) $(!1 ,TP< $(!1 ,T P< $(!1# T "*% &# ;2

PAGE 99

<=d ) =b-< >dG-: $R 8 8 8 Q `>b `< @ 57 8< ^<-<^ <: <7 c" A 7 08 = :mZ 7K <4 /d e <:^-< # `^ Y78-> `V <>8 -7 <`2V 1? -: L# `;V 4R -= D `HV G -0 `04V < -H D `=L Hm -; m `:V 0m-2 `7V =&, -4V `>L 7+ / -<V `
PAGE 100

4"= 7 7 @1(9%-9 $(!1#)' < --<((<-1<9-<% ;4;aQ :(5


PAGE 101

/8a 8C2 `" ^^_-#= : #%&)# 06 :J"! 2F # 1 $%%% 1 8 # .6 $%!1 ,d '8 $%%% $%!1#)'8 1 8 # .6 % 1 8 # .6 $%!1#D'8 %) $ $%!1 )'8 1 8 # .6 $%) S% $%!1#D P 8 $%%% "$ $%!1# .6 1 8 # .6 2>

PAGE 102

1 "!1# T < > 7: / +8 << 8 8^^^ 8 8 8 <8^^^ 8 8 8< 8 <8 8 < < < 88 < <<< 8 8 , -/ :+ 27

PAGE 103

# $ `> / + ##)%& $%!1# 1 % J$ 8 => %" $%!1# d P 8 1 => J )"%) < > 7 : / + < K8 <88^ I 8 88-^ I 8^ 8^^ > 8 88^ ^8 88-^ 8^ 8^^ 7 < 88 < ^8 88^^ 8^ ^^ : < <88^ ^8 <8^^ 8^ 8^^ << << ^8 8 8^^ 8^ 8-^ < <<8^ < 8< 8^ ^^ < <<< < 88^^ < 8 / < < < < <8^^ 8^ < + < <<< < << 8^ ^8^^ T:-!* <, ` / ` + ) :`+*-`-<, :-+ `>,]`] / + 2:

PAGE 104

# #= = $)< : P $-> / + ##)%) & $%=1# "% "$ % J ) "%"$ #= = => % K 2=

PAGE 105

+ 5 II 88 8^^ 888-^^8 8 <8 < 888^-^8 < 88^^ 8 < 8^ ^^8 8 <<< 8 8 8^^8 8 <<8-^ < 8<^8 << < <88^-< 8 < <<<< 8^^8 < << < <<< -8 8 < *< E4E< / (/< !/ (/%4 (/< !/ E4E< + (/
PAGE 106

4)"$ $%!1 ,T '8 S% 1 8 # .6 8 T8 )" 8 \<$!= 9 : !# )%& %%= S#"$%= =4 ,)%c=J & )"&&)# ,)) % $&&)# !# ))J '% 4 !'%# )%ccP>&%" :+ T< :T-:+,T < 7 : <>7: 8<88^^^ 88 <8 <8 $%%%+7$ )"& )"&)# ))%=

PAGE 107

+L-7$K,)%&))#V< 7= 4%=< :+< >,"< % f>\: $) ? Q7 % 1 "$< :+>$7,"<%%$ + 3# )%&))# //2 = /$)! 1 $ 1 < '2C' \7P\:P\ J /aD/D < > 7 : / < K8 <88^ I 8 > 8 8<8^ -8 7 < 8 8<^8 : < <8 8^< / < <<8^^8 !/J# ) ,%&))# +%=d +D/ /D+D =d +D/ + /D :P\ / $) 2;

PAGE 108

52/ V! W % 7<88< :<<88 % ( % a ) 5 88^^^8 8^^^8^^^8 ^^^ ^^^ ^^^ % ^^^ <<<8^^^<^^^8^^^< 5 <<<PV7Pk: PV ) $ % # => $>$J$ ) =# % & '""=$ccT:$ 2 !# ))" )! 1 )"&)# =# ))% $ %# TE< :$J$aF 2 < %$&) 22

PAGE 109

L 88^^^ <8 <8 P >&P\ C %"% )"&)# !# ))% +`< !,) %&))#\* (/ >= "$ &)#+: >$, !# )) ) 25 `< *--<$ ) b*` $*:-> $T`> (/%9S /( $# L(/% !? (/9S ) <88

PAGE 110

5 +,T < 8 < < 8<8 <8< <88 <<8 8 8 < 8 4)#+)J$ # ,%&))# < )) + g % <&CD+D//D+D *:d +D/ + ) ->P\ / $ ) K:-P\ /'25 52/ /D+D + $ # > --< >>PV / P\ + <8<

PAGE 111

/ + 8] I 8 <8^ II 8 --8^^ ^8 8 8^ -8 8 ^ ^< 8 < ^8 8-^< 8 8^ < 8^^ / ^< <8^ ^8 < + ^< <<^ ^8 ^^ $ % # :> / + ) !# %& '"" cWT:$$ TE C/+B $ $%=1# T P 8 1 8 # ] &)#& #$%%" <$%%(% &)# 1 $Q-:+,# 1 $"4"< > =$ %

PAGE 112

1 #)%&) 1 6= : > 6= : :#)% &)# 6 = : :%"6= : 7= : < 6= : > @ : $/%%9-2 : %(; (91-95-<((<-1%-+ %<$%!1 ,T $!"# 2 + 6= : 7 5-<((<-(9-9 2 : %%8%(-<$;(< = ;4; aF< 8DQ 4<9<%-(9%<< 8 < 2 P\ 7 0!* 8 %)*) = # = % =@ #= = $ 8 %!* <87

PAGE 113

& & %!"% #= 0 !/D PP 7 '2 .= : =$%%6= > <= 7 >$ *( N < > H %(( <8:

PAGE 114

&T(T7(? // &T(-> 4 (T7F---&T ; >3 (T> \&T8 0 = :8V (T / &T8 7? 0 #= 0 %!*# <8=

PAGE 115

"E8
PAGE 116

%%* )% &)& < $%% #*%& &) = = < @1$(9-92 0 %1<$%!1 )--<((<% %-<-9 Z`, 7d D P7 06 1 ) N 1 !P# 7 @ @ P7 $# = #) #= : 1 /$"= : <$ $%!1#) 4)"$ $%!1#) 1 N +$$, 7d D P7 ) 7$ \:$ = : < ] = = > @1$(9-9% @$$<9$-(<%(9%%< < $%!1# )1< T<$ 0= T>$ $* > T $* -$-2 : <8H

PAGE 117

00: T < 0= T>%" D =)) $%!1#) #= H 0`> T $P // $ 2 : T: '"6= = <$ !)% $%!1#) 0 +7$&, #= H$" !)%" &" 0: ` 0= T $\ ")) % $*C TV :-< $ "$:d D+ + a`>)% $%!1 ,Ta:-> Q> !? e7 CC %(% Q$)! K /$ <8;

PAGE 118

Q=EG $%!1 4* + / 3 0K7 &) + ) % $%!1#)+ &)%")# %) Q : !! $ + `>)% $%!1#)+* > 3E^ Q &) + P<)% $%!1# T + P<%")# )! Q !! $ \I> T $ -< :$9 $(%#)# ($$#)#(%"& ( $( ) ( #$%= = > ( "$4"= = 7% = = >= 7 > <82

PAGE 119

,<<:: @$$<9$-9(<%(9 9%-%<< $!"# TZ`+ :,T+ :,T ="# ) 1<$F T< $b)C$*C T5*-2 : ,<<::( @$$<9$-9(<%(9 9%-%<< $!"# )* !"# ) + :,T+ :,T @$<4$%8% T<$ T<$ *C T`--i 2C1< $ P P7 <`)K1><-)K11> 06 $ 0+ :,T ?W!"# T+ :,T <<8

PAGE 120

6 & % T<$ J T < *C T `< -\> W'#28X$%) 4"= = 7 %) $" T< 0= T> `> TV-fm\: = = = @ : $/%%9-2 0 %(; (91-91< --<((<-1<%-<%; 4;aQ<((<-1%%-< -9 7d D P7 06 :J"! 2 0 # 1 0 + :,T $%!1#)' <$ 1 !" # = #)#= : :#$ I $/ PII 7 +,T 2 T+ :,T P < 0+ :,T -+ :,T+ :,T < <<

PAGE 121

1 ##)#= 7 !"" .6 !*# 7d d P7%#)# .6 = % $!"# ) P< $ 1 "+ `,7 DD' 7 4)"$!"N #)#= 7"N +e$QDD' 7 1 !" # # = #)#= : $ "= : <$ $%=1 ,T $!"#)' < % #)#= 7$ # $ $!"# P ?*!"# T+ :,T P< ] = = 0 @$<9$-9(<%(99M %-%<< $="# T>`+ :,T+ -,T < @ EF $<4$%8% 8T<$ T<$ P T_-` 2 > 1< <<>

PAGE 122

< -D = -) 0 -) !A B 1`] 9#CBD ;d d<: :>< H:0 -' <= T<0 9%! PP0`Q-?-<=` +G+\ ` +) =7II<=L\ 1 "# 0I7T X\ )# .2 N "# $!"!1##)?*!"!1##)!"!1##) < ;d d<: = = =$ -..? .* $!"!1##) *-+ :+,,T !"!1##) -< $!"!1##)?!"!1## T+ :+,,T-<$ <<7

PAGE 123

&) -7 ))#( $XQ TI01K#) )# .Q "# $!"!1## T ?W!"!1##)!"!1## T-< : d D' :$0iI# )+$$--,$&) )%( "$ $ #% &) )% ( $ : d D : TI 7 iI$I7 ) ./ $!"!1##)O*!"!1##)!"!1##) < P: ,*"!??D" ,<"J" -? %$ ?
PAGE 124

T<= #)")! .aI "$ ,J C; EOOW/E%?*(% >Q <& \f6V------. =E@ % 2
PAGE 125

#= = <= = > %*N %&&) #)4N "= = H R4"= = H @1$(9-9 \0 %1< $%!1# T $(!1# --<((<%%-<-9!J7d D P7 <((<-1<%-<%; 4;aQ<((<-1%%-< -9 K`, 7d d P7 4#= = == = =#)N %&&) #) 4"= = ; 4"= = ; @$<9$-9(<%(9 9%-%<< $%!1# T $(!1# <<0

PAGE 126

@ EF $<4$%8% T<$BT< *C T W < ` 2 > 1< )D : H UL 1 d= )\ ) VP7>9I= ,R -P 8 0 T 0=: <<>7 PHP<0II V-7` \ `K--<=`<7--0`[7 ++-27 ;d d<: -) <= -) <0 T <
PAGE 127

! + !%5 ^ -#$ $!"! ##)?!"! ## K 4:-#$ $!"! ##)?*!"! ##)!"! ## ^ "#%J" !-: +<7, 2 7$ $!"! ##),"= ## T !"! ##) K -"#$ $!"! ##)!"! ##)*!"! ##)!"! ## K !-#% !"#!"# 7 % 0+ :, !"# : 0+ :,V !"# 7 !"#!"# :K <<;

PAGE 128

+ 7d +D)$9 !# N #% $!"! ## T+ :+[,,T ?*!"! ##)+ ^Z$7d + d )$9+'$/ BE8 7$ F$ !# #% $!"! ## T+ :+[,,TT`+ :+[,,T++',,T( G(0$9 K !"# 4:-#$% 3(4 $!"# ^ ^ !"# -#$% !"#$!"# + :, $!"#&!"#& ? !"#& K %#% $%! # T $(! # % !(&#J"! ^A#"#$ $!"!##)!"!##) `+ :+[\,,T !"!## <<2

PAGE 129

^ "##$ $!"!## T !"!## T !"!##)!"! h G(0$9 ^%#% $%= # T $(! # % !(&#J"! V<< ^ "!$ 0+ :,T+ :,TI + :,T+ :, ^ + >d + d !"! :% 0+ :,T+ :,T `+ :,T !"# T + ^ :"!"b+-:,"# !(V<< ^ :"! 2 7$ [3#;D4 **3(4*33/;\4*1; ^!" % + :,T + :,T < ) %

PAGE 130

^!"! %+ :,TP> ^"!" ="# "# G(0$9 ^% +-:, $:"! ^*"% ( ^"$"#" !:I ^ :-!$ P
PAGE 131

^# 92 > "# E0+,a 1 !FdP 9 ^!-% $!"#)!"#) )U + :,T ="#) ^!-%( 0+ :,T+ :,T`+ :,T[+I:,T-< ^!#-! :%[+ :,T K !#-! :% -+ :,T ^!#-! :% ->T $!"#D!"#)*!"#D="# ) G(0$9 K 4"# ^)( %) ^S(#-#N e ^A!#-!% $!"# Te <>>

PAGE 132

!!I ^)% ( ^ :-!#$ Vd0+ :,d+ :,T d[+ :,T ^!$!"# > P--------2 Ph 7 ^% $%V1# T $(!1#) $%!1#)$(!1# TP #))& <>7

PAGE 133

K W`X W@G2;X W'/G6;0X W'/;8X W'G6;0X W'62>X W'#28X W'2>X W4=2X B!$!$$.6 /$ ."# !#+, G $ 4 @ G 4!" &)& -# %"((,<9% ;0a<>=-<:: <22; 4 '$D /$D G$G 6# 'N &)"# ;Z99 $=7a<77-<:0$<2;0 '$(/"$9) '# )#) -:(<1< $:a=<-H7$ <2;8 4 '$D G$G 6#$G) '&)## 8Z99 =7a<:H-<=:$<2;0 B#'$G 6#$G ( ;Z99 2$<22> D. '# 5%9$% /' G))$$6$$<228 '/G 9$, 1< 4#)".$<22> 4 4# `"%%0 >:2a><=<-><=>$<2=2 %(

PAGE 134

W422-;7<$<22< W4BD.2>X W4B.J W/27X W=2X WBG6.2 A 4$A B#"$ G ( *-$#<02-;<->;2$<2=2 A G B#"$D G$G 6#$ G 'N &)####( # -9$1< =<+,aH7-;2$<22< D /$G 6#$G '&)# $$ :(<,%; <: # ><7->>: A(( <227 B D*#'"6 # ;Z99 H>aH<-;8$<228 G 6#G )"# -9$% 5-99%% <0+,a>2-70$<22< 6 6)* A # -9$1< >7a<>H-<7;$<2HH G "G N #*$ @,";$ >;a=H-H8$<228 ")A $G .$ )" <>=

PAGE 135

WSH;X $2< KK ] W.X W.2;X W28X &&)#*+ ,-<5" <:a:7->H8$<2H; G 4#"a4)##% & Z"+]%<5;,< 72a:80-:>:$<2HH G"6 .'"6 +, G"6 .'"6 N H%%-9$% =a>:$<22; '"6 %8019,% .A$)"S-$<228 <>0