Citation
Semiring ranks of classes of (0,1)-matrices

Material Information

Title:
Semiring ranks of classes of (0,1)-matrices
Creator:
Henson, Teresa Dern
Publication Date:
Language:
English
Physical Description:
86 leaves : illustrations ; 29 cm

Subjects

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

Notes

Bibliography:
Includes bibliographical references (leaves 85-86).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Mathematics ; Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Teresa Dern Henson.

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:
20863592 ( OCLC )
ocm20863592
Classification:
LD1190.L62 1989m .H465 ( lcc )

Full Text
SEMIRING RANKS
OF
CLASSES OF (0,1)-MATRICES
by
Teresa Dern Henson
B.A., University of Colorado at Denver, 1983
A thesis submitted to the
Facuity of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of Mathematics
1989


This thesis for the Master of Science Degree by
Teresa Dern Henson
has been approved for the
Department of
Mathematics
by


Henson, Teresa Dem (M.S., Mathematics)
Semiring Ranks of Classes of (0,1)-Matrices
Thesis directed by Professor J. Richard Lundgren
Semiring ranks of (0,l)-matrices have aroused considerable interest in
recent years. The equivalence of nonnegative integer rank with the biclique par-
tition number of a digraph and of boolean rank with the biclique cover number,
have made it possible to combine graph theoretic and matrix theoretic methods
in the determination of semiring ranks of classes of (0,l)-matrices. Regular
(0,l)-matrices and irreducible (0,l)-matrices have been of particular interest.
Semiring ranks of (n,A:)- and (rc/b)-regular matrices have been determined for
some values of k. In particular, the equivalence of minimum real rank and non-
negative integer rank for certain k has been established. It is also known that
for k = 1,2,3, the minimum nonnegative integer ranks of (n,k)-regular and
(nk)-regular matrices are equal.
In this thesis a subclass A of (rc 3)-regular (0,l)-matrices is considered.
This subclass is derived by constructing a subclass D of [n 3)-regular digraphs.
The adjacency matrices of the digraphs in D form the subclass A. It is shown
that for n > 6, all digraphs in D are strongly connected. Hence, for n > 6,
every matrix in A is irreducible. From A is taken what are believed to be the
first examples of irreducible (0,l)-matrices for which real rank and nonnegative
integer rank differ by more than one.
Real ranks of the matrices in A are computed for n = 1,2,...,12. Exact
values for the boolean and nonnegative integer ranks of these matrices are found
in some cases; upper bounds are given for others. Real rank of two members in


IV
A is determined for all n and used to establish nonnegative integer rank of those
members for certain values of n. It is conjectured that the real rank of any
matrix A in A may be computed by summing the real ranks of certain subma-
trices of A. From A an infinite class of (0,l)-matrices is derived for which it is
proved that real rank and nonnegative integer rank of any matrix in the class
differ by n.
J 3
The form and content of this abstract are approved. I recommend its publica-
tion.
Signed
J.Richard Lundgren, Professor


To Van
For Believing


VI
ACKNOWLEDGEMENTS
I wish to thank my adviser, J. Richard Lundgren, for his guidance and
encouragement. Also, Kathryn F. Jones and Jennifer Ryan for their criticism of
the thesis manuscript. My husband, Van Emden Henson, provided invaluable
technical assistance and prepared this thesis for publication. Finally, special
thanks to my mother and stepfather, Mary and George Tyner, for their love and
support.


Vll
CONTENTS
CHAPTER
I. INTRODUCTION.............................................1
n. BICLIQUES AND SEMIRING RANKS.............................3
2.1 Graphs, Digraphs, and Cliques.......................3
2.2 Bicliques...........................................5
2.3 Semiring Rank and Term Rank........................10
HI. BICLIQUE NUMBERS AND SEMIRING RANKS
OF CLASSES OF DIGRAPHS AND (0,1)-MATRICES...........19
3.1 Lower Bounds for Biclique Numbers..................19
3.2 Examples of Semiring Ranks.........................23
3.3 A Survey of Known Results..........................27
3.3.1 The Classes D(n,k) and D{n,n k)..............28
3.3.2 Other Regular Digraphs........................35
3.3.2 Other Classes of Digraphs.....................37
3.4 Open Questions.....................................38
IV. A SPECIAL CLASS OF (n 3)-REGULAR DIGRAPHS
AND THEIR ADJACENCY MATRICES........................40
4.1 Irreducibility of (n3)-regular Matrices...........40
4.2 A Class of Singular, Irreducible
(n 3)-regular Matrices............................42
4.3 A Subclass of (n 3)-regular Matrices
and Their Adjacency Matrices.......................50
4.4 The Subclasses D and A.............................56
4.5 Semiring Ranks of an Infinite Class................76
V. CONCLUSION.............................................83
REFERENCES
85


vm
TABLES
Table
3.1 Values for S (n)...........................................21
4.1 Semiring Ranks of A?1) ... q for n = 1,2,...,12...........57


IX
FIGURES
Figure
2.1 A Digraph and a Clique from the Digraph..................5
2.2 A Digraph and its Adjacency Matrix.......................7
4.1 The Digraph Dq and its Adjacency Matrix Aq...............42


CHAPTER I
INTRODUCTION
Lundgren and Maybee [13] first introduced the notion of a clique for a
digraph. The term biclique was later adopted to describe such an entity. Jones,
Lundgren, and Maybee [12] then applied the concepts of clique covers and parti-
tions of graphs to biclique covers and partitions of digraphs. Hence arose the
problem of finding the biclique cover number and the biclique partition number
of a digraph. Their initial research into the study of bicliques was extended by
Barefoot, Hefner, Jones, and Lundgren [2], Gregory, Pullman, Jones, and
Lundgren [6], Barefoot, Jones, Lundgren, and Maybee [l], and others.
From the beginning, the adjacency matrix of a digraph was an essential
tool in the study of bicliques. There is a one-to-one correspondence between
digraphs and (0,l)-matrices and between biclique cover and partition numbers
and boolean and nonnegative integer ranks, respectively. As a result, often what
starts out as a question about bicliques turns into a question about semiring
matrix rank. Matrix theory has proven to be indispensable in the study of
bicliques. Conversely, results from digraph theory have often been applied to
obtain results in matrix theory. Real ranks of (0,l)-matrices have been studied
by Brualdi, Manber, and Ross [3], while de Caen, Gregory, and Pullman [4],
Gregory and Pullman [5], Hefner, Lundgren, and Maybee [9], and others have
looked at semiring ranks of (0,l)-matrices. Application of their results to
bicliques as well as other results may be found in the work of Barefoot, et al. [1]
and Gregory, et al. [6] among others.


2
Regular digraphs and regular (0,l)-matrices are of particular interest to
researchers in this field. The regularity of such digraphs and matrices makes
them relatively easy to work with in the sense that regular matrices tend to
behave in predictable ways, which facilitates matrix theoretic arguments. Bru-
aldi, et al. [3] have determined minimum real rank of Avregular and (ft /Ir-
regular (0,l)-matrices for k = 1,2,3. Similar results were obtained by Gregory, et
al. [6] on boolean and nonnegative integer ranks of such matrices.
This paper is organized into three main chapters. Chapter II lays the
ground work. It begins with a brief review of basic terminology from graph
theory and a short discussion of cliques. In Sections 2 and 3 fundamental con-
cepts are defined and illustrated by examples. Basic relationships between
biclique numbers and semiring ranks are discussed in Section 4.
In the first section of Chapter m several lower bounds for the biclique
numbers are discussed. Examples are presented showing the application of these
lower bounds. A number of examples are presented in Section 2 that illustrate
the variety of ways in which the various semiring ranks may be related. The
main part of this chapter is the survey of known results contained in Section 3.
The results of a preliminary exploration of a special subclass of (ft3)-
regular digraphs are presented in Chapter IV. An algorithm is presented which
can be used to construct any member in the subclass. Four theorems derived
from the study of this subclass are stated and proved. Directions for further
research and two conjectures are also discussed. A concluding chapter summar-
izes work completed to date and open questions.


CHAPTER H
BICLIQUES AND SEMIRING RANKS
In this chapter the basic terminology of graph theory is reviewed in Sec-
tion 1. In Section 2 fundamental concepts relating to bicliques are explored and
the notion of the adjacency matrix of a digraph is introduced. Examples are
presented that illustrate the application of these concepts. Semiring ranks of
matrices axe introduced in Section 3. The application of semiring ranks to the
adjacency matrix of a digraph is discussed. The chapter concludes with an
examination of the ways in which biclique numbers and semiring ranks are
related.
2.1. Graphs, Digraphs, and Cliques
A digraph D = (V, A) is a set V of vertices and a set A of arcs connect-
ing vertices in V. If there is an axe connecting a vertex u to a vertex v, it is
denoted by the ordered pair (u, v). A path in a digraph is a sequence
ui5ci)u2>a2>u3) ' where for all t = 1, ,t, Uj is a vertex and a,-
is an axe from u, to w8+1. A graph is a digraph in which the the arc (u,u)
appears whenever the arc (v,u) appears. In this case, the two arcs axe
compressed into a single line called an edge and the graph is designated
G = (V,E), where E is the collection of all edges connecting vertices in V. An
edge in G may be denoted by either {u,u} or {u,u} since direction is unimpor-
tant. A chain in a graph is a sequence ui,ei,u2)e2ju35 ,Uf,et,where uf-
is a vertex and e8- is the edge joining w,- to In this paper it is assumed that


4
all digraphs are loopless, that is, there axe no arcs from a vertex to itself.
There are three categories of connectedness for a digraph. A digraph is
said to be weakly connected if, disregarding arc direction, there is a chain of arcs
connecting every pair of vertices in D. It is said to be connected if there is a
path joining every pair of vertices in D. And it is strongly connected if, for
every pair of vertices u and v there is a path from u to v and a path from v to u.
A graph (digraph) is said to be complete if all vertices are connected by all pos-
sible edges (arcs). A bipartite graph is one in which the vertex set may be parti-
tioned into two disjoint sets X and Y such that if {it,?;} is any edge of G, then u
is in A and v is in Y. This definition may be extended to digraphs by requiring
that all axes go from X to Y. If a digraph satisfies these conditions, then it is
said to be bipartite. Any subset of the vertices and edges of a graph forms a sub-
graph whose edge set is contained in the edge set of the original graph; this
edge set may be empty. A subdigraph may be described in a similar way. A
subgraph that is complete is called a clique.
Cliques in graph theory have been a topic of considerable interest in
recent years. Research has focused on such areas as:
1. The minimum number of cliques needed to cover the edge set of
particular classes of graphs;
2. The minimum number of cliques needed to partition (i.e., cover
without overlap) the edge set of particular classes of graphs;
3. The establishment of suitable lower bounds on these numbers for
all graphs; and
4. The correspondence between the notions of clique covers and parti-
tions and other graph theoretic notions such as matchings.


5
Lundgren and Maybee [13] first defined the concept of a clique in a digraph.
The extension to digraphs of the concepts of clique covers and partitions fol-
lowed naturally. The next section defines and illustrates these basic terms.
2.2 Bicliques
Definition 2.2.1: Directed Biclique [12]
A directed biclique, or briefly, biclique, for a digraph D = (V,A) con-
sists of two disjoint subsets X and Y of V together with all the arcs
(x, y) where x is in X and y is in Y.
A digraph and a biclique from the digraph are shown in Figure 2.1. A biclique
B is denoted by listing the subset of vertices in X, the subset of vertices in Y,
and connecting the two subsets by an arrow indicating the arc direction from X
to Y, e.g. in Figure 2.1, X = {1,2}, Y = {4,5} and B:X> Fis given by {1,2} >
Figure 2.1


6
Every connected digraph has a family of bicliques associated with it
since for every u in V, there exists at least one v in V such that u and v are con-
nected by an arc.
Definition 2.2.2: Biclique Cover and Biclique Partition
(1) A biclique cover of a digraph D is a family of bicliques whose arc
sets cover the arc set of D.
(2) A biclique partition of a digraph D is a family of bicliques whose
arc sets partition the arc set of D.
Given these definitions, two fundamental questions arise:
1. What is the minimum number of bicliques needed to cover the arc
set of a digraph?
2. What is the minimum number of bicliques needed to partition the
arc set of a digraph?
These minimums are called the biclique cover number and the biclique partition
number of D, denoted bc(D) and bp(D), respectively.
Often it is more convenient to consider the adjacency matrix of a
digraph, rather than the digraph itself. The adjacency matrix of a digraph D,
denoted A (D) = [o,y], is a (0,l)-matrix with
fl if (?,y) is an arc
~ |0 if (i,j) is not an arc .
From the definition it is clear that there is a one-to-one correspondence between
the set of all (0,l)-matrices and the set of all digraphs. If D is assumed to be
loopless, then a,- ,- = 0 for all i. A digraph and its adjacency matrix are shown in
Figure 2.2.


7
0 1110
10 111
110 11
1110 1
0 1110
\
Figure 2.2
Related to the notion of strong connectedness in a digraph is the con-
cept of irreducibility of a matrix. The definitions of reducible and irreducible
matrix and an important theorem are presented here. Frequent reference will
be made in Chapters m and IV to irreducible matrices.
Definition 2.2.3 : Reducible Matrix [11]
An re x re matrix A is said to be reducible if either
(a) re = 1 and A = 0; or
(b) re > 2, there is an re x re permutation matrix P and there is
some integer r with 1 < r < re 1 such that
ptap =
B C
O D
where B is r x r, D is (re r) x (re r), C is r x (re r) and O
is an (rer) x r zero matrix.
The entries of B, C, and D may be zero or not; all that is required is that it be
possible to produce an (re r) X r block in the indicated position by some
sequence of row and column interchanges. If A is reducible, it must have at
least re1 zero entries.


8
Definition 2.2.4: Irreducible Matrix [11]
An n x n matrix A is said to be irreducible if it is not reducible.
The relationship between digraphs and irreducible matrices is given in the fol-
lowing theorem. It states necessary and sufficient conditions for a matrix to be
irreducible.
Theorem 2.2.5 [11]
Let A be an n x n matrix. The following are equivalent:
(a) A is irreducible;
(b) (I+ | A |)n ~1 > 0 ; and
(c) The digraph of A is strongly connected.
This characterization of irreducibility will prove useful in the development of a
class of irreducible (0,l)-matrices in Chapter IV.
The adjacency matrix of a digraph may be used to find bicliques of D.
By regarding the rows of A (D) as the vertices of X and the columns as the ver-
tices of Y, a block of ls represents a subset of the vertices in which all arcs go
from A to 7 and hence is a biclique. Finding a biclique cover then is equivalent
to finding the minimum number of blocks needed to cover the ls of A (D)\ a
biclique partition can be found in similar fashion. The following example illus-
trates this process.


Example 2.1:
The adjacency matrix for a digraph D is
A{D) =
/ 0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
1 1 1 0 0 1 1 1 0
1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1
1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0
1 s. 1 1 0 1 1 1 0 0 /
A biclique cover is given by
{l,2,3,7,8}-{4,5}
{1,2,3,4,9}>{6,7}
{1,2,3,5,7}>{8,9}
{4,5}>{1,2,3,7,8}
{6,7}>{1,2,3,4,9}
{8,9}>{1,2,3,5,6} .
That this cover is minimum will be demonstrated in Example 4.5. Hence,
be (D) = 6.
A biclique partition is given by
{1,2,3}>{4,5,6,7,8,9}
{4}->{l,2,3,6,7,8}
{5H{1,2,3,7,8,9}


10
{6}>-{1,2,3,4,8,9}
{7}>{1,2,3,4,5,9}
{8}>{1,2,3,4,5,6}
{9}>{1,2,3,5,6,7} .
Again, it will be shown in Example 4.5 that this partition is minimum. Hence
bp(D) = 7.
Any minimum biclique partition is also a biclique cover, so be (D) may
equal bp (D); but, since arcs of D may appear in more than one biclique in a
cover, it may be possible to cover the arcs of D with fewer than bp (D) bicliques.
Thus
bc{D) < bp(D) .
The problem of finding bp (D) and bc(D) is a difficult one. Some
bounds on these two numbers that hold for all digraphs will be discussed in Sec-
tion 4 of this chapter and in Section 1 of Chapter HI. Biclique numbers for cer-
tain types of digraphs have been determined as well as minimum biclique
numbers for certain classes of digraphs. These results are presented in Chapter
HI.
2.3. Semiring Rank and Term Rank
Since the adjacency matrix may be used to determine bicliques of a
digraph, it is natural to consider the relationships between matrix properties and
biclique properties. It turns out that there are four matrix ranks that play an
important role in the study of bicliques. Three of these may be defined in terms
of the rank of a matrix over a semiring; the fourth is quite different in


11
conception. The following discussion of matrices over a semiring is based on the
work of Gregory and Pullman [5].
Definition 2.3.1: Semiring [5]
A semiring consists of a set S and two binary operations on S, addi-
tion and multiplication, such that
(i) 5 is an Abelian semigroup with identity 0 under addition,
(ii) S is a semigroup with identity 1 under multiplication,
(iii) multiplication distributes over addition, and
(iv) sO = Os = 0 for all s in S.
The set of m x n matrices with entries in a semiring S is denoted 5^^. If the
operations of matrix addition and multiplication, and scalar multiplication, are
performed using the arithmetic defined on the semiring S, then is a semir-
ing under matrix addition and multiplication.
The adjacency matrix of a digraph is an example of a matrix in Rn n
where the field R of real numbers is considered as a semiring. A (D) is also an
element of the semiring i2^n, the semiring of matrices with entries in the non-
negative real numbers; in the semiring Z^n, the semiring of matrices with
entries in the nonnegative integers; and, in the semiring Bn n, the semiring of
matrices all of whose entries are either 0 or 1, where B is the two element
Boolean algebra:
0 + 0 = 0, 1 + 0 = 0 + 1 = 1 + 1 = 1, and (0)(1) = (1)(0) = 0 .


12
Definition 2.3.2: Matrix Rank in a Semiring [5]
The Srank of a nonzero matrix in S^n is the least integer k = 5(A)
such that A = BC for some B in 5^* and for some C in 5^.
Based on this general definition, it is possible to give simple definitions for three
of the four matrix ranks associated with the adjacency matrix of a digraph.
Definition 2.3.3: Real Rank, Boolean Rank, and Nonnegative Integer Rank
Let A be an n x n (0,l)-matrix.
(1) The real rank of A, r^(A), is the smallest k for which
there exists a matrix C G Rnjf and a matrix D G R^n such
that A = CD.
(2) The boolean rank of A, rg(A), is the smallest k for which
there exists a matrix C G Band a matrix D G B^n such
that A = CD.
(3) The nonnegative integer rank of A, r^+(A), is the smallest
k for which there exists a matrix C G Z\^ and a matrix
D G Z\ n such that A = CD.
This definition of the real rank of a matrix is not the one usually encountered in
linear algebra; it is most readily understood by considering the L 17-
decomposition of A(D). Recall that in Gaussian elimination, an nxn matrix A
is reduced to an upper triangular matrix U. The multipliers used in the reduc-
tion process may be stored in a lower triangular matrix L. A may then be fac-
tored into the form
A = LU .


13
If row interchange is required to perform Gaussian elimination, then a
suitable permutation matrix P may be found such that PA has an L 17-
factorization. An alternate definition of the real rank is that it is the number of
nonzero pivots in U. If the real rank is k < n, then the last n k rows of U,
and, without loss of generality, the last n k columns of L are zero. In this
t * it
case, A = L U where L is the nxk matrix formed by deleting the zero
columns of L and U* is the kxn matrix formed by deleting the zero rows of U.
Since k is the smallest number for which this factorization is possible, this k is
the k in Definition 2.3.3.
If S' is a subsemiring of a semiring 5, then it follows from Definition
2.3.2 that 5(A) < 5'(A) for any A in 5. Thus
rit{A) < rz+{A) .
Gregory and Pullman [5] also show that r#(A) < 5(A) for all (0,l)-matrices in
5 from which it follows that
rs(A) < rz+(A) .
There is another way to characterize these three matrix ranks.
Proposition 2.3.4 (Lemma 1.1, [5])
Let A be a nonzero matrix in a semiring S. Then the S-rank of A is
the minimum number of 5-rank one matrices whose sum (under 5-
addition) is A.
The following example illustrates this proposition.


14
Example 2.2:
The adjacency matrix of a digraph
D where r^(A) = 4 = rg(A) and
rz+{A) = 5 is given by
A(D) =
Oil
10 1
110
111
Oil
k
1 o'
1 1
1 1
0 1
1 0
/
A boolean rank factorization is given by
A (D) = CD =
10 10 0 0 1 1 o'
10 0 1 110 0 1
0 10 1 0 110 0
0 110 10 0 11
10 10 \ /
\ / 5x4
which may be written as the sum of four boolean rank one matrices
/ \ 1 / \ 0 / \ 1 / \ 0
1 0 0 1
0 (00110) + 1 (110 0 1) + 0 (01100) + 1
0 1 1 0
1 \ / 0 1 k / 0 k /
!)
Note that these rank one matrices are formed by taking successively the first
column of C times the first row of D, the second column of C times the second
row of D, etc.
In this example, since r%+(A) = 5, a nonnegative integer factorization is
given by A (D) = IA (D), where I is the identity matrix. The matrix may also
be split into the sum of five nonnegative rank one matrices. Since A (D) is a
(0,l)-matrix its nonnegative integer factorization will also consist of (0,1)-
matrices.


15
The fourth matrix rank that will be considered in this paper is very dif-
ferent from the three discussed so far.
Definition 2.3.5: Term Rank [5]
The term rank of an adjacency matrix A (D) is the minimum number
of rows and columns of A which contain all of the nonzero entries of
A; alternatively, it is the maximum number of nonzero entries of A no
two of which share a row or column of A. The term rank of a matrix
is denoted r<(A).
For the matrix above, r*(A) = 5.
The relationship of term rank to semiring rank is given by the following
proposition.
Proposition 2.3.6 (Lemma 1.2, [5])
Let A be nonzero (0,l)-matrix in a semiring 5. Then the 5-rank of A
is less than or equal to the term rank of A.
Proof:
If r*(A) is the term rank of A, then at most rt(A) rows and columns of
A are needed to cover the nonzero entries of A. Take the r^(A) nonzero rows
and columns and for each row (column) form the nxn matrix Bj by replacing
the corresponding row (column) of the nxn zero matrix with the row (column)
from A. Each B{ has 5-rank one since it is a nonzero matrix whose nonzero
entries occur in a single row or column. A can now be written as the sum of
i"t{A) 5-rank one matrices. Therefore, 5 (A) < rt(A).


16
The basic relationships among the four matrix ranks may be summar-
ized as follows:
Let A = A (D) be an nxn (0,l)-matrix. Then
(1) rR{A) < rz+{A) < rt{A) < n
(2) rB(A) < rz+(A) < rt(A) < n .
Note that no relationship exists between tr{A) and rB{A). Examples will be
presented in Chapter HI showing that these may be equal or that one may be
smaller than the other.
2.4. Bicliques and the Semiring Ranks
Associated with every digraph D there is a family of bicliques and an
adjacency matrix A (D). The intent of this section is to establish some very
useful relationships between the biclique cover and partition numbers introduced
in Section 2 and the matrix ranks discussed in Section 3.
So far it has been established that
(1) rR < rz+ < rt < n
(2) rB < rz+ < rt < n
(3) be (D) < bp(D) .
Consider now a minimum biclique cover B = of a
digraph D. Since a biclique is a subdigraph of D in which the vertices are parti-
tioned into two disjoint sets X and Y with all arcs from X to Y, each biclique
Bi can be represented by an nxn (0,l)-adjacency matrix with a 1 in the
(i,j) entry if and only if w,- is in X and v}- is in Y. Each vertex in X has arcs to
all vertices in Y and there are no arcs between vertices in X or Y, hence all rows


17
of Mg axe the same and is a rank one matrix. The sum over the M* would
correspond to the union over all bicliques, which is D. However, since it is possi-
ble for some axe to appear in more than one biclique it is possible for a 1 to
appear in the same position in two or more in which case M, the sum of
Mi s, would have entries greater than 1. To avoid this, the boolean sum is used.
k
Therefore M = Mt- = A (D), where summation is boolean, k is the biclique
*'=l
covering number of D, and all have rank one. Thus r#(A (D)) < be (D). The
converse inequality may be derived by starting with a minimum number k of
boolean-rank one (0,l)-matrices whose boolean sum is A (D) and proceeding
from there to obtain a biclique cover in k bicliques. Thus be (D) < rg(A (£)))
and it follows that tq(A(D)) = bc(D).
Given a minimum biclique partition B = {B1,H2, ,2?*} it can be
shown, using a similar argument, that rz+(A(D)) < bp (D). The distinction, in
this case, is that since the H,- are disjoint, no two Mj can have ls in the same
position, hence the summation is done using regular arithmetic. Alternatively, it
is possible to begin with a minimum number of nonnegative integer-rank one
(0,l)-matrices whose sum is A (£)), and from there build a biclique partition
using & bicliques. Thus bp(D) = rz+(A (D)).
These equalities mean that every result proved for biclique numbers
holds for the nonnegative integer and boolean ranks of (0,l)-matrices and vice
versa. Because of the equivalence of the concepts of biclique partition number
and nonnegative integer rank and of biclique cover number and boolean rank,
exposition and proofs will frequently mix the terminology and concepts of
digraph theory and matrix theory, e.g., the "real rank of a digraph" technically
refers to the real rank of the adjacency matrix of the digraph.


18
Given these fundamental definitions and the relationships between the
semiring ranks of (0,l)-matrices and biclique numbers of a digraph, the next
step is to explore in more detail the ways in which these relationships may occur
and to survey what is known about semiring ranks and biclique numbers for par-
ticular classes of (0,l)-matrices and digraphs.


CHAPTER HI
BICLIQUE NUMBERS AND SEMIRING RANKS
OF CLASSES OF DIGRAPHS AND (0,1)-MATRICES
It has been shown that the biclique cover and partition numbers of a
digraph D are in one-to-one correspondence with, respectively, the boolean and
nonnegative integer ranks of the adjacency matrix A (D). The problem of find-
ing a minimum biclique cover or partition and two lower bounds for the biclique
cover number are discussed in Section 1. In Section 2 examples are presented
which illustrate some of the ways in which the semiring ranks may be related in
terms of equality or inequality of the ranks. Semiring ranks and biclique
numbers for various classes of matrices and digraphs are discussed in Section 3.
The chapter concludes with a summary of these results and a discussion of some
open questions.
3.1. Lower Bounds for Biclique Numbers
It has been noted that tr(A) < r^+(A) and that r#(A) < rg+(A), but
that no such relationship holds for r^(A) and r#(A). The problem of finding a
biclique partition or cover for a digraph is mainly a problem of determining that
the partition or cover is minimum. For a biclique partition, real rank is usually
a reliable lower bound, particularly if the digraph is strongly connected. In fact,
in all cases reported in the literature, real rank and nonnegative integer rank of
an irreducible matrix have never been known to differ by more than one.
Examples of strongly connected digraphs for which these numbers differ by


20
more than one will be presented in Section 2 of this chapter.
There are two nontrivial lower bounds for the biclique covering number.
The first involves the notion of row containment in A (D) and is due to de Caen,
Gregory and Pullman [4]; the second uses the number of isolated ones in A(D)
and is due to Gregory and Pullman [5].
Definition 3.1.1: Row Containment [4]
A matrix A is said to have row-containment if A has rows A,- and Ay
satisfying A,- < Ay entrywise for some t =f= j.
If a (0,l)-matrix is without row containment, then for every pair of rows there
must be a 2x2 submatrix either of the form
0 1
1 0
or
1 O'
0 1
For, if rows A;
and Ay, ¥= j together contain either of these submatrices, then A, ^ Ay, and
Ay A,-, entrywise. For example, the matrix
A =
0 10 11
10 111
0 10 0 1
110 0 1
110 0 0
V /
has row containment as row 3 is less than or equal to row 4 entrywise. On the
other hand, the matrix
B =
0 0 1 1 o'
0 0 0 1 1
1 0 0 0 1
110 0 0
0 110 0
is without row containment.


21
\
Now let s(n) = min
k: n <
. Some values for s[n) axe shown
in Table 3.1.
Table 3.1
n 2 3 4-6 7-10 11-20 21 35 36-70
*() 2 3 4 5 6 7 8
The following proposition (de Caen, et al., Corollary 1 [4]) provides a
lower bound for bc(D). Frequent reference to s (n) and this proposition will be
made in the sections that follow.
Proposition 3.1.2 (de Caen, Gregory, and Pullman [4])
If the adjacency matrix A (D) for a digraph D on n vertices is without
row containment, then bc(D) > s (n).
s (n) is also a lower bound on the boolean rank of the adjacency matrix of D. It
provides a fairly good lower bound for many classes of digraphs. But, as some
examples in Chapter IV will show, there are examples of digraphs for which the
difference between s(n) and bc(D) can be quite large. Still, it proves very use-
ful in a variety of situations. It is possible for equality to be achieved, cf. Exam-
ple 4.1, the digraph D4.


22
Definition 3.1.3: Independent Ones; Isolated Ones [6]
A matrix is said to have a one at (i,j) if o= 1. A set S of ones is
said to be independent if no two occur in the same row or column. A
set S of independent ones is said to be isolated if no two ones occur in
a 2x2 submatrix of A of the form
1 1
i ij n
The following example illustrates these terms.
Example 3.1:
Let
0 0 1 1 1 O'
0 0 0 1 1 1
1 0 0 0 1 1
1 1 0 0 0 1
1 1 1 0 0 0
0 1 1 1 0 0
The set
S = {(1,3), (2,4), (3,5), (4,6), (5,3)}
is not independent as (1,3) and (5,3) are in the same column. The set
S = {(1,4), (2,5), (3,6), (4,1), (5,2), (6,3)}
is independent but not isolated as entries (1,4) and (2,5) lie in a 2x2 submatrix
of ones. Finally, let
S = {(3,1), (4,2), (5,3), (6,4), (1,5), (2,6)}.
The ones in S are underlined in A. It is clear that the ones in S are isolated.


23
The following result provides another lower bound for be (D).
Proposition 3.1.4 (Gregory and Pullman [5])
If the adjacency matrix of a digraph D has an isolated set of k ones,
then bc(D) > k.
As with s (?i), the number of isolated ones in an adjacency matrix is also a lower
bound on the boolean rank of the matrix. In some instances the number of iso-
lated ones may provide a better lower bound than s (n), e.g., in Example 3.1,
the matrix A is without row containment, hence by Proposition 3.1.2,
be (D) > s (6) = 4. But, as shown above, A has 6 isolated ones, hence
be (D) > 6. Unfortunately, finding isolated ones can be very difficult, so the use
of this proposition is not always practicable. Use of these lower bounds for the
biclique cover number of a digraph will be illustrated in the examples of Section
2.
3.2. Examples of Semiring Ranks
The following examples illustrate some of the ways in which real rank,
nonnegative integer rank, boolean rank and term rank may be related for a
specific matrix. For small values of n both the digraph and its adjacency matrix
axe shown; for larger values of n only the adjacency matrix is given. Statements
about these rank values axe in some cases presented without proof; those results
are verified in Chapter IV. In all that follows let D be a digraph on n vertices
and let A be its adjacency matrix.
This first example shows that all matrix ranks may be equal.


24
Example 3.2:
2
0 0 1 1 0
0 0 0 1 1
1 0 0 0 1
1 1 0 0 0
0 1 1 0 0
By Theorem 4.2.1 of Chapter IV, the real rank of A is 5. A has 5 isolated ones
(underlined). So by statements (l), (2) of Section 2.4 and Proposition 3.1.4,
rjz(A) = rB(A) = rz+(A) = rt{A) = n = 5 B
'0 0 0 1 1 1)
0 0 0 1 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
1 < 1 1 0 0 0 )
By Gaussian elimination, the real rank of A is 2. The digraph can be parti-
tioned with two bicliques, so rz+(A) = 2 also. The matrix has row contain-
ment, so Proposition 3.1.2 cannot be applied; however there are two isolated
ones (underlined). It is clear that the term rank is 6. Hence, by (l), (2) of Sec-
tion 2.4 and Proposition 3.1.4
(A) = rB(A) = rz+(A) = 2 < rt(A) = 6 B


25
As was noted earlier, there is no fixed relationship between real rank
and boolean rank. Examples 3.4 and 3.5 show that either one may be less than
the other and that either of them may be equal to the nonnegative integer rank.
Example 3.4 is also an example of an irreducible matrix for which real rank and
nonnegative integer rank differ by two. For a proof that A is irreducible, see
Section 4.1.
Example 3.4:
Refer to the matrix of Example 3.1. It was shown there that the matrix
has 6 isolated ones. It follows by (2) of Section 2.4 that rB(A) = rz+{A) = 6.
However r^(A) = 4 by Theorem 4.2.1. Hence,
rR{A) < rB(A) = rz+(A) = rt{A) and rz+(A) r^(A) = 2
On the other hand:
Example 3.5:
0 0 1 1 1 1 1 1 1 o'
0 0 0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
1 1 1 0 0 0 1 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1 0 0
In this example, rR(A) = 10 (Theorem 4.2.1). Hence rz+[A) = 10 by
(1) of Section 2.4. A biclique cover in eight bicliques has been found, so
rB{A) < 8. Also, A is without row containment, so rB(A) > s (8) = 5. Hence,


26
5 < rB{A) < 8 and rB(A) < r^(A) = rz+(A) .
Note the difference between the size of the smallest biclique cover found so far
and the lower bound of s (8). It should be noted that no more than five isolated
ones have been found.
Example 3.6:
A complete proof of the result claimed here may be found in example 4.5. For
the matrix
A =
0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
1 1 1 0 0 1 1 1 0
1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1
1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0
1 1 1 0 1 1 1 0 0
the following axe true:
rR{A) = 5, rB{A) = 6, rz+(A) = 7
By inspection, rt(A) = 9.
Hence r^(A) < rB(A) < rz+{A) < rt(A).
These examples show some of the situations that can occur when study-
ing biclique numbers and semiring ranks. Researchers have discovered classes of
digraphs for which all the semiring ranks are equal. Whether there are classes
for which other combinations of equality/inequality hold for all members in the
class is an open question. Evidence will be presented in 4.4 for an infinite class
of strongly connected digraphs for which real rank and nonnegative rank differ


27
by two. Also, in Section 4.5 an infinite class of strongly connected digraphs will
be presented for which real rank and nonnegative integer rank differ by n. It
3
is also unclear just how close a bound s(n) is for be (£)); as was seen in Example
3.5, and as is further illustrated by several entries in Table 4.1, this gap may be
sizable. It would be interesting to explore the question of when s (n) fails to pro-
vide a good lower bound on the biclique covering number of a digraph and why
it fails.
3.3. A Survey of Known Results
In this section, the literature on biclique numbers and semiring ranks is
surveyed and from it is gleaned a variety of results that reflect the ways in
which questions about biclique numbers and semiring ranks have been tackled
and solved. Much of the research into biclique numbers and semiring matrix
ranks has focused on finding lower and upper bounds for these numbers and on
determining the semiring rank properties of various special classes of digraphs.
Some general lower and upper bounds have already been discussed. These
bounds apply to any digraph and in some cases they work very well. They are
not always sufficient, however, and the question naturally arises: Do better
bounds exist? In particular, what are the minimum values for the semiring
ranks of certain classes of matrices? Also, the examples in Section 3.2 show that
many different combinations of equality and inequality between the semiring
ranks can occur. A question is: Are there classes of digraphs (matrices) for which
these inequalities or equalities always hold? For certain classes of digraphs some
of these questions have been answered, but many open questions remain.


28
Much research has been done on the class of regular digraphs and regu-
lar matrices. That class will be considered in 3.3.1 and 3.3.2. Work on other
classes of digraphs will be discussed in 3.3.3.
3.3.1. The Classes D(n,k) and D(n,nk)
Definition 3.3.1
1. A (0,l)-matrix A is said to be kregular if every row(column) con-
tains k nonzero entries. In such a matrix the sum of the entries in any
row (column) will be k.
2. A digraph D is said to be kregular if there are k incoming arcs
and k outgoing arcs at each vertex in which case the indegree and the
outdegree of each vertex are k.
Clearly the adjacency matrix of a fc-regular digraph is also fc-regular and the
digraph of a fc-regular matrix is also fc-regular. In this paper the class of fc-
regular digraphs on n vertices will be designated by D(n,k) with the correspond-
ing class of adjacency matrices denoted by A (n,fc). Similarly, D[n,nk) and
A(n,nk) will denote, respectively, the class of all (rcfc)-regular digraphs on n
vertices and the corresponding class of adjacency matrices. Jones, Lundgren, and
May bee [12] have shown that the class D{n,k) is nonempty for fc satisfying
1 < fc < n1.
Since much of the discussion that follows centers on minimum semiring
ranks and minimum biclique numbers for fc-regular matrices and digraphs, the
following notation will be used to designate these minimums.


29
bc(n,k) = min{6c(D): D £ D(n,k)}
bp(n,k) = min{6p(D): D £ D(n,k)}
rR{n,k) = min{r£(il): A £ i4(re,&)}
rs{n,k) = min{rfl(A): A £ A (n,A:)}
rz+{n,k) = min{r^+(A): A £ A (re,&)}
Jones, Lundgren, and Maybee [12] have studied biclique covers and par-
titions of D(n, 1) and D(n,n1). D(n, 1) is the directed cycle on n points and
D[n,n1) is the complete digraph on n vertices, i.e., a digraph with all possible
arcs joining every pair of vertices. They note that there is only one member in
each class. The adjacency matrices of D(n, 1) and D(n,n1) axe
A{n,l)
0 10
0 0 1
0 1
0 1
: 0
0
and
0 0 1
10 0
A(n,n1) =
0 111
10 1
110 1
10 1
: 1 0
1
Ml
1
1
1 1
. 1
1 0


30
Clearly A (n,nl) is without row containment and, as it turns out, the
number s (n) introduced in Section 3.1 provides an exact bound on be (n,n1).
Theorem 3.3.2 (Jones, Lundgren, and Maybee [12])
For n > 2, bc{D(n,n1)) = s(n)
The authors had conjectured that bp(D(n,n1)) = n for all n. This result was
proved by Pritikin [14], using a technique due to Tverberg.
Theorem 3.3.3 (Pritikin [14])
For n > 1, bp(D(n,n1)) = n.
It is easy to see that 6p(Z?(n, 1)) = n = 6c (D(rc, 1). In addition, Brualdi,
Manber, and Ross [3] have shown that rR(n, 1) = r#(ra,n1) = n. Hence for
semiring ranks these results may be summarized as follows:
(1) rz+(n, 1) = rz+(n,n-1) = rR(n, 1) = rR(n,n-l) = rB(n, 1) = n .
Also, it follows that rt(n,n 1) = rt(n, 1) = n. Here is the first of many exam-
ples of a class of digraphs for which real rank and nonnegative integer rank are
equal. Note that the equality in (l) does include rB(n, 1) but not rB(n,n l)
since s (n) =t= n in general.
The classes D(n, l) and D(n,nl) represent the extremes of the family
of k-regular digraphs: the fc-regular digraphs with, respectively, the fewest possi-
ble and the most possible arcs. This family has been eroded at both ends with
complete results obtained for 2-, 3-, 4-, and (n2)-regular digraphs and partial
results for ( 3)-regular digraphs.
Gregory, Pullman, Jones, and Lundgren [6] have established lower and
upper bounds in terms of n and k for bc(n,k) and bp(n,k) for any n and k,


31
which axe exact in some cases. Let [xj denote the greatest integer less than or
equal to x and [x] denote the smallest integer greater than or equal to x.
Theorem 3.3.4 (Gregory, Pullman, Jones, and Lundgren [6])
For all n and k,
< bc(n,k) < bp(n,k) < k +
n_
k

A similar result for rB(n,k) and rz+(n,k) can be stated by replacing be with rB
and bp with rz+. It should be noted that equality of the lower bound holds if k
divides n. The authors also give an example of a type of matrix for which the
upper bound can be achieved. Brualdi, Manber, and Ross [3] found a similar
result for real rank.
Theorem 3.3.5 (Brualdi, Manber, and Ross [3])
n_
k
< rR with equality if and only if k divides n.
From these two theorems, it follows that
n_
k
< rR(n,k) < rz+{n,k) < k +
n_
k '
Moreover, since the lower bound is achieved when k divides n, the class of k-
regulax matrices for which k divides n provides yet another example of a class
for which the minimum semiring ranks are equal, since
-J = rR{n,k) = rB{n,k) = rz+(n,k)
whenever k divides n.
Gregory, Pullman, Jones, and Lundgren [6] also determined complete
results for bp{n,k) and be (n,k) where k <4. Their results are summarized in


32
the following theorem. The case for k = 1 has already been discussed and is
omitted here.
Theorem 3.3.6 (Gregory, Pullman, Jones, and Lundgren [6])
1. For n > 2, bp(n, 2) = bc(n, 2) =
+ l + (-l)B+1
2. Let z(n) = 0 if n = 0(mod3) and z(n) 3 otherwise. Then for
all n > 3, be (n, 3) = 6p(rc, 3) =
+ z(n).
3. Let z(n) = 0, 3, 2 or 4 according as n = 0, 1, 2 or 3 (mod 4).
Then for all n > 5,
be (n, 4) = bp (n, 4) =
= *()
and
6c (5,4) =4 and 6p(5,4) = 5
There are several things to note about this theorem. First, in the third state-
ment, D(5,4) is the complete digraph on 5 vertices and the values 6c (5,4) = 4
and bp (5,4) = 5 follow from Theorems 3.3.2 and 3.3.3. Second, Brualdi, et al.
[3] obtained similar results for r^(n, 2) and r^(n, 3). Their theorem has been
rephrased to conform to the notation of Gregory et al. [6] in Theorem 3.3.6.
Theorem 3.3.7 (Brualdi, Manber, and Ross [3])
1. For n > 2, rR(n, 2) =
IL
2
+ l + (-l)B+1


33
2. Let z(n) = 0 if n = 0(mod3) and z(n) =3 otherwise. Then for
all n> 3, rB{n, 3) =
+ z(n).
Combining Theorems 3.3.6 and 3.3.7, it follows that
rR(n,2) = rB{n, 2) = rz+(n, 2)
and that
^(w,3) = rB(n, 3) = rz+(n, 3) .
It should be noted here that the proofs of these theorems are extremely difficult
and involve many case-by-case arguments.
Barefoot, Jones, Lundgren, and Maybee [1] determined some interesting
results for (n2)-regular digraphs. First they showed that any (n2)-regular
digraph could be obtained by a particular method of construction. They then
used this to obtain a number of results for (n2)-regular digraphs of which a
selection are presented here. The authors observed that if the arcs of an n-cycle
are removed from D(n,n1), then the resulting digraph is (n 2)-regular. From
this they derived the following theorem which describes a method for construct-
ing any (n2)-regular digraph.
Theorem 3.3.8 (Barefoot, Jones, Lundgren, and Maybee [1])
If D is any (n2)-regular digraph on n points, then D can be obtained
from the complete digraph by removing the arcs of disjoint cycles of size
9l> > Qr where n = q1 + + qr and q, > 2 for all *.
Based on this they develop a number of upper and lower bounds for be (n,n 2)
and bp(n,n 2). The following theorem gives the essential flavor of their work.
The function s (q) is the function of Proposition 3.1.2 and the q^s are the same


34
as in Theorem 3.3.8.
Theorem 3.3.9 (Barefoot, Jones, Lundgren, and Maybee [l])
Let D be an (?i2)-regular digraph with n = q1 + + qr and let
q =
?i
+ +
Qr
. Then
bc{D) > s(g)
bp(D) > q
Using these and other results not detailed here they are able'to find bc(n,n 2)
and bp(n,n 2).
Theorem 3.3.10 (Barefoot, Jones, Lundgren, and Maybee [1])
1. If n = 2k, then bc(n,n 2) = s(k).
2. If n = 2k +1 > 9, then s(fc-|-2) < bc(n,n 2) < s(k1) +2.
3. 6c (3,1) = 3, 6c (5,3) = 4, 6c (7,5) = 5.
4. If n = 2k, k > 2,then bp{n,n 2) = k.
5. If n = 2k + l,k > 1, then bp(n,n 2) = k + 2.
Note that be (n,n2) is determined only for n even. Also, statements 4 and 5
coincide with bp (n, 2) given in Theorem 3.3.6. There
bp(n,2) =
+ l + (-l)+1 .
If n is even, i.e., n = 2k, then
= k and (l)n+1 = 1 so bp[n, 2) reduces
to &. If n is odd
is again k, but (l)re+1 = 1, hence bp [n, 2) reduces to


35
k -f- 2.
Work on fc-regular matrices has produced some interesting similarities in
results. Brualdi, Manber and Ross [3] have shown that r#(re,k) = r%{n,nk)
for all re and k. Hence, results stated for minimum real rank of 1-, 2-, and 3-
regular matrices also hold for (re1)-, (re 2)-, and (re3)-regular matrices.
From the results discussed in this section, it follows that bp{n,k) = bp{n,nk)
for k= 1,2, re 1, and re 2. In addition, Lundgren [7] has proved that
bp (re,re3) = bp (re, 3). The following statement summarizes these results.
Corollary 3.3.11
For k = 1, 2, 3,
rR.{n>k) = rn{n,nk) = r^+(re,/b) = r^+(re,rek)
It should be noted here that r^(n,k) and r^[n,nk) do not conform so nicely.
It has already been shown that
rB{ni 1) ^ r#(n,re1) and r#(re, 2) =t= r£(re,re 2) .
What about rg(re, 3) and rj5(re,re3)? This remains an open question.
3.3.2 Other Regular Digraphs
A variety of other types of regular digraphs have been studied where
more prohibitive restrictions are placed on the values of re and k. For instance,
Barefoot, et al. [l] find an infinite class of digraphs for which the minimum
biclique cover and biclique partition numbers are equal.


36
Theorem 3.3.12 (Barefoot, Jones, Lundgren, and Maybee [1])
If n = qm then bp(n,m) = q = be (n,m).
Jones, et al. [12] looked at digraphs of the form D(qm,2m), D(2m,m) and
D(qm,m). Their results axe summarized in the following theorem.
Theorem 3.3.13 (Jones, Lundgren, and Maybee[l2])
Let q > 2 be an arbitrary integer.
1. If q > 3, for each m > 2, there exists an element D in
D(qm,2m) such that bp{D) = q.
2. If q = 2, for each m >2 there exists an element D in
D(2m,m) such bp(D) = 2.
3. If n = qm, then bp(n,m) = q.
Statements 1 and 2 of this theorem are interesting in that they guarantee the
existence of a digraph that satisfies a certain biclique partition number. The
digraphs jD3 3 and D3 3 3 in Table 4.1, are examples of digraphs that meet their
criteria.
Hefner and Lundgren [8] study minimum nonnegative integer rank and
minimum boolean rank for a variety of ^-regular digraphs. They successfully
extend to other semiring ranks certain results of Brualdi, et al. on real rank.
They also obtain upper bounds for rz+(n,k) and rg(n,k) for n and k of certain
forms.


37
3.3.3. Other Classes of Digraphs
Not all research has concentrated on regular digraphs, though these have
been most often studied. The biclique partition problem proved to be quite
tractable for the class denoted by Jones, Lundgren, and Maybee [12] as
DKn\DKm. To define this class, set
DKn = D(n,n 1)
and
DKm = D(m,m1)
where m < n. Then DKn\DKm is the digraph obtained from D(n,n 1) by
deleting the arcs but not the vertices of a D(m,m1) subgraph. They obtained
the following result.
Theorem 3.3.14 (Jones, Lundgren, and Maybee [12])
For all m satisfying 1 < m < n 1, bp (DKn\DKm) = n m +1.
Hefner, Lundgren, and Maybee [9] have found a class of digraphs for which all
semiring ranks are equal, namely the class of strongly connected unipathic
digraphs. A unipathic digraph is defined as a digraph with at most one simple
path from any vertex to any other vertex. If such a digraph is also strongly con-
nected, then there is exactly one simple path connecting every pair of vertices.
In addition to showing that equality holds for all semiring ranks, they also show
that the value can be any number between 2 and n and that each of these
values can be realized for any n > 2.
A third class of nonregular digraphs was considered by Barefoot, Hefner,
Jones and Lundgren [2]. They defined Dn to be the complete digraph on n ver-
tices minus the arcs of an n-cycle and to be the complete digraph on n


38
vertices minus the axes of an n-path. They obtained a number of lower and
upper bounds for bc(Dn) and bc(Dn). One of their more unusual results gave
logarithmic upper bounds for these numbers and used the function s(n) of Pro-
position 3.1.2 to find a lower bound for be (D^).
Theorem 3.3.15 (Barefoot, Hefner, Jones and Lundgren [2])
1. bc{Dn) > s(rc1) .
2. bc{Dn) < 2 |^log2(n + 2)J n > 14 .
3. bc(D) < 2 ^log2(ra 2)J n > 18
3.4 Open Questions
In this chapter a selection of known results has been presented designed
to highlight those areas in which complete or near-complete results have been
obtained; to illustrate the complexity of the problems involved; and, to demon-
strate the variety of approaches used. Classes of matrices and digraphs have
been found for which semiring and minimum semiring ranks are equal. The
"maverick" among the semiring ranks appears to be boolean rank; the problem
of finding boolean rank appears to be much harder than finding the nonnegative
integer and real ranks, although these are certainly not easy. Boolean rank
behaves in a much less regular way, when compared to real rank and nonnega-
tive integer rank.
It should be clear, from the discussion in this chapter, that many open
questions about biclique numbers and semiring ranks remain. For instance, the
equality of rz+(n,k) and rz+(n,nk), for k = 1, 2, 3, has been noted. The
question arises: Is this result true for all kl if not, for what A: is it true?


39
Several classes of digraphs have been presented in which the semiring
ranks are equal. Other questions, then, are: For what other classes of digraphs
are these semiring ranks equal? Are there classes of digraphs in which strict ine-
quality holds for any of these ranks?
And still to be determined are the minimum semiring ranks of the k-
regular and (rcA;)-regular matrices for k > 5.


CHAPTER IV
A SPECIAL CLASS OF (re3)-REGULAR DIGRAPHS
AND THEIR ADJACENCY MATRICES
In Chapter IH, two examples were presented of strongly connected
digraphs for which the real rank and the nonnegative integer rank differed by
two. Those digraphs are members of the class of (re3)-regular digraphs. The
discovery of those examples prompted a further exploration of the class of
(re3)-regular digraphs and their adjacency matrices. The results of that
research are presented in this chapter. First, the irreducibility of (re3)-regular
matrices for re > 6 is established. Then Section 2 takes a look at a special
(re3)-regular matrix derived from Example 3.4. In Section 3, a method for
constructing a subclass of (re3)-regular digraphs is presented. The basic form
of the adjacency matrices for the digraphs in this subclass is discussed. Sections
3, 4, and 5 explore some of the properties of this subclass, and several theorems
and conjectures resulting from this study are presented.
4.1. Irreducibility of (n-3)-regular Matrices
Since all of this chapter is concerned with (re 3)-regular digraphs and
their adjacency matrices, and in particular, with a subclass of irreducible (n-3)-
regular (0,l)-matrices, it will be useful to establish the irreducibility of this class
before proceeding to the main results. The proof relies on two results from
graph theory. Recall that a hamiltonian cycle in a digraph is a cycle that uses
each vertex once and only once. A digraph is said to be hamiltonian if it has a


41
hamiltonian cycle.
Lemma 4.1.1 [15]
Suppose that D is a digraph with re vertices and for every vertex x
Tt Tt
outdegree(x) > and indegree (x) > .
2 2
Then D has a hamiltonian cycle.
The following theorem is now easily proved.
Theorem 4.1.2
Let D be an (re3)-regular digraph and let re > 6. Then D is strongly
connected.
Proof:
Assume that D is an (n 3)-regular digraph on re > 6 vertices. Then for
every vertex x, indegree(x) = re3 and outdegree(x) = re3. For re > 6,
re3 > Hence, indegree(x) > and outdegree(x) >
By Lemma 4.1.1, D has a hamiltonian cycle. Clearly, then, D is strongly
connected.
From Theorem 4.1.2, it follows that the class of (re 3)-regular matrices
is irreducible for re > 6.


42
4.2 A Class of Singular, Irreducible (n-3)-regular Matrices
For ease of reference, the matrix of Example 3.4 and its digraph are
given in Figure 4.1. .
!
'001110'
0 0 0 1 1 1
1 0 0 0 1 1
1 1 0 0 0 1
1110 0 0
0 1110 0
k )
4
Figure 4.1
This digraph was obtained from an (n l)-regular digraph D (the complete
digraph on 6 vertices) by first finding a hamiltonian cycle in D and then remov-
ing the forward and back arcs of that cycle. For the digraph in Figure 4.1, the
following arcs were removed: (1,2), (2,3), (3,4), (4,5), (5,6), (6,1) and (2,1),
(3,2), (4,3), (5,4), (6,5), (1,6). This technique can be generalized as follows:
Algorithm 4.1
1. Let D = D(n,n1).
2. Let Cn be a hamiltonian cycle in D.
3. Remove arcs from D according to the following rule: If (u,t>) is in
Cn, remove (u,v) and (y,u).
The resulting digraph is an (n 3)-regular digraph. This is because the algo-
rithm, by removing forward and back arcs, reduces both indegree and outdegree


43
by two at each vertex. Clearly if Cn = (1,2, ,n) and C'n = tt(1,2, ,rc),
where 7r(l,2, ,n) denotes a permutation of l,2,...,n, then the digraph
obtained using Algorithm 4.1 and Cn is isomorphic to the digraph obtained
using the algorithm and C'n. Hereafter it will be assumed that
cn = (1,2, ,n) and the resulting digraph will be denoted Dn. The set of all
Dn, n G Z will be designated by Dn.
The adjacency matrix of the digraph constructed by Algorithm 4.1 will
be denoted An and An = {An: n G Z}. Clearly, since Dn is (n 3)-regular, so is
An. Dq and A6 are shown in Figure 4.1. D3, D, and Z)5 and their correspond-
ing adjacency matrices are given in Example 4.1.
Example 4.1:
1) D3 and its adjacency matrix.
'0 0 o'
0 0 0
0 0 0
Hereafter this matrix will be referred to as 03 because it is a 3x3 matrix of all
zeros. Note that this matrix is reducible since its digraph is disconnected.
2) T>4 and its adjacency matrix.
A4
0 0 1 o'
0 0 0 1
10 0 0
0 10 0


44
Like O3, this matrix is also reducible, again because its digraph is disconnected.
3) D5 and its adjacency matrix.
2
\ 0 0 1 1 / 0
0 0 0 1 1
1 0 0 0 1
1 1 0 0 0
0 1 1 0 0
Z?5 is the first case in which the digraph is strongly connected and A 5 is irredu-
cible.
From Theorem 4.1.2 and part 3 of Example 4.1, it follows that for all
n > 5, An is irreducible and Dn is strongly connected. When the vertices of the
cycle Cn are labelled l,2,...,n, then An always has the form
0 0 1 . . 1 o'
0 0 0 1 1 1
1 0 0 0 1 1
1 1 0 0 0 1
1 0 0
0 0 1
0 0 0 1
1 1 1 1 0 0 0
0 \ 1 1 1 1 0 0,
That is, the adjacency matrix will have zeros on the main diagonal, on the first
subdiagonal, on the first superdiagonal, and in the (n, 1) and (l,n) positions,


45
with ones elsewhere.
Theorem 4.2.1
Let An be the adjacency matrix of Dn. For n > 3, the following state-
ments are true.
(1) If n = 0 (mod 3), then r^(AR) = n 2.
(2) If n = 1, 2 (mod 3), then rjt(An) = n.
Proof:
Interchange rows to put An into the form
1 0 0 0 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1
. . 1 1
1 1 . 0 0 1 1
1 1 1 0 0 0 1
1 1 1 0 0 0 ( 3)
0 1 1 0 0 (ra-2)
0 0 1 1 0 (rc-1)
0 0 0 1 1 (n)
Let ~x = [xi, x2? xn]T be such that A^x = 0. Let aj denote the tth row of
A'n. Then
A^x = 0 => A£x = 0 =>
a,- x = 0 for i = 1,2,
,n
Observe that
ax-x = xx + x5 + x6 + x7 + + xn = 0


46
=> *1 = *6 *6
Also,
an x = x4 + x5 + x6 + x7 + + xn = 0
=> = x5 x6 xn .
Therefore
Xi = x4 .
Claim: xy = xy+3 for j = 2,3, ,n3.
Consider the (j l)st and jth rows of A^, for j = 2,3, ,n3:
column
1 0 0 0 1
1 1 0 0 0 1
(j l)strow: 1 1
jthTOw:
1 1
1
1
If A^x = 0, then ~aj-i m~x = 0 and "ay-"x = 0, which implies that
(aj m~x = 0. Now,
ay -ay_i =[ 0 0 0 1 00 -1 0
;tk (i+3)rd
J
column
column
So
(ay_x -"ay) -~x = Xj xj+3 = 0
=> Xj = Xj+3 for j 2,3, ,n-3 .
For rows n2, n1, rc,
(1)
"4-2 '"?= 0 and "4-3 -"x = 0 => (4-2 ~~an-3) ~x = 0
Since "ow_2 "on_3 = [1 0 1 0 0] it follows that
(4-2 "4-3) = 0
=> -X! + xn_2
=> *1 = n-2


47
Similarly, Co_i -~an-2) '~x = 0 and ~an-i -"oB-2 = [0-10 10]
implies that
x2 = xn 1
Finally, (a "an-i) *"i = 0 and ~an ~an-i = [0 01 0 1] implies that
x3 ~ xn
From (1), the components of"x may be subdivided into 3 disjoint sets
Si = {x3k -2}
&2 = {x3k-1} (2)
S3 = {3*}
where all the elements of 5,- are equal.
There are three possibilities:
Case I
If n = 3k + 1, then
xi = xn2 = x3k-i => Sx = S2 by (2)
and x2 = x_i = x3k => S2 = S3 by (2)
Together, these imply that
X1 = x2 = x3 " = xn
So ~x = [xl5 xi, Xi Xi]T and for any "a*, ~ai -~x = 0 = {n3)xi (as "a^ has
n 3 nonzero entries), which implies xx = 0, as n > 3. Therefore
~x = 0
and An is nonsingular for n = 1 (mod 3).


48
Case II
If n = 3k + 2, then
xi = xn-2 = => ^1 = S3 by (2)
and x3 = xn = xn_3 = x3k_x => S3 = S2 by (2) .
Together, these imply that
xt = x2 = x3 = = xn
and as in Case I it follows that ~x = 0. Therefore An is nonsingular for
n = 2 (mod 3) .
Case III
If n = 3k, then
X1 1 x3k-2
x2 = x3fel
x3 = x3k
and ~x must satisfy
xi + £5 + Xq + Xn_2 + xn-1 + xn = 0
as
ax x = xx + x5 + x6 + + xn = 0 .
This equation is equivalent to
(xi + x2 + x3) + + (iCi + x2 + 13) = 0 by (2) .
In this case the number of components in each Sj is k. There are n 3 terms on
the left hand side and since the components are evenly divided into thirds, the
last equation can be written


49
(f-l)*i + (f-1)*2 + (f-l)*8 = 0
which implies that
Xi X2~X3
Therefore ~x must have the form
x =
1 1 H to 1 H CO 1
X2 *3 -1 1 0 -i 0 1
-X2 -x3 -1 -1
x2 1 0
*3 0 1
= X2 + x3
x2 x3 -1 -1
x2 1 0
*3 0 1
.
- x2u + x3v
Since x2 and x3 axe arbitrary, x^u + x^v = 0 iff x2 = x3 = 0. Therefore, ~u
and~v are linearly independent. Hence, dim NS(An) = 2. Therefore
rR(An) = n 2 when n = 0 (mod 3) .
Since tr{A) < r^+ (A) < n and r^+(A) = bp(D), the following corollary is
immediate.
Corollary 4.2.2
1. If n = 1,2 (mod 3), then r^+(An) = n.
2. If n = 1,2 (mod 3), then bp{Dn) = n.


50
An examination of the subclass An of (ft3)-regular matrices has yielded two
results. First, from Theorem 4.2.1 and Corollary 4.2.2, for n = 1,2 (mod 3), An
is yet another example of a class of matrices for which real rank and nonnega-
tive integer rank are equal. Equivalently, for n = 1,2 (mod 3), the subclass Dn
of (n3)-regular matrices is an example of a class of digraphs for which real
rank and the biclique partition number are equal.
Second, Theorem 4.2.1 guarantees the existence of a class of singular,
irreducible (n3)-regular (0,l)-matrices. Other types of (re3)-regular (0,1)-
matrices for which real rank and nonnegative integer rank differ by more than
one are presented in Section 4. Whether this difference holds true for all An,
where n = 0 (mod 3), is unclear at this time. Ag, A12, and A15 have been
examined and, so far, no biclique partition in fewer than n bicliques has been
found for any of these matrices. It is conjectured that r#+ (An) = n for all ft. If
this were true then, for n = 0 (mod 3), n > 3, there would be an infinite class of
(ft3)-regular matrices for which real rank and nonnegative integer rank differ
by two.
4.3. A Subclass of (n3)-regular Digraphs and Their Adjacency Matrices
In this section a method for constructing a subclass of the (ft 3)-
regular digraphs will be presented. This subclass is well-defined for all values of
ft and for n > 5 all digraphs in the subclass are strongly connected. Thus, this
construction produces a subclass of (ft 3)-regular (0,l)-matrices which are
irreducible. It will be seen that these matrices exhibit highly predictable
behavior in form and rank. From this subclass will be drawn those examples for
which nonnegative integer rank and real rank differ by more than one.


51
The construction technique described below was inspired by work done
on {n 2)-regular digraphs by Barefoot, Jones, Lundgren, and Maybee [l].
They showed that any (n 2)-regular digraph can be obtained by removing dis-
joint cycles of length g,- where n qi + + qr and g,- > 2. The following
algorithm is based on that process.
Algorithm 4.2
1. Let D = D(n,n 1).
2. Let Ci,C2, ,Cr be disjoint cycles of length gi,g2, ,gr
r
where g,- > 3 and n = g,- .
*=i
3. Remove arcs from D according to the following rule: If (u,v) is in
C{, remove (u, v) and (v,u) for i = 1,2, ,r .
Clearly, Algorithm 4.1 for constructing Dn is just a special case of this algo-
rithm, with Cn = Ci and qi = n. As with Algorithm 4.1, any digraph con-
structed by this method will be (ra3)-regular and, for n > 5, strongly con-
nected. The following example illustrates the application of this algorithm.
Example 4.2:
Let D = Z>(7,6). A (7,6) is shown on the left below. Let Gx be the
cycle (1,2,3) and C2 the cycle (4,5,6,7). Then Ci and C2 are disjoint cycles of
length three and four respectively. Hence qi 3, g2 = 4, and
gi + g2 = 3 + 4 = 7. Remove the forward and back arcs of Ci and C*2. The
adjacency matrix A of the resulting 4-regular digraph D is shown on the right
below.


52
A (7,6)
/ 0 1 1 1 1 1 1 / 0 0 0 1 1 1 1
1 0 1 1 1 1 1 0 0 0 1 1 1 1
1 1 0 1 1 1 1 0 0 0 1 1 1 1
1 1 1 0 1 1 1 A = 1 1 1 0 0 1 0
1 1 1 1 0 1 1 1 1 1 0 0 0 1
1 1 1 1 1 0 1 1 1 1 1 0 0 0
1 \ 1 1 1 1 1 0 / 1 k 1 1 0 1 0 0 )
In order to distinguish the digraphs constructed by this method from the
general class of [n 3)-regular digraphs, the following notation will be adopted in
this paper. D(n,n3) represents any member of the class of all (rc3)-regular
digraphs. D represents the subclass of ( 3)-regular digraphs constructed by
Algorithm 4.2. Note that Dn CD. A specific member in this subclass will be
denoted Dqu j9A, where 9i, , 316 the sizes of the cycles removed from
D(n,n1) with n = ql + + qk. Thus, _D3 4 5 is a 9-regular digraph on
12 = 3 + 4 + 5 vertices constructed by removing 3 disjoint cycles of lengths
respectively 3, 4, and 5. This notation is rather unwieldy when dealing with
specific examples. However it does indicate the way in which a particular
member of the subclass was constructed. The advantage of knowing this infor-
mation will be apparent when considering the adjacency matrices of the
digraphs in D.
It should be noted here that not every (n3)-regular digraph may be
obtained by using Algorithm 4.2, as the following example shows.


53
Example 4.3:
Consider the 3-regular digraph on six vertices as shown below. This
digraph was obtained from the complete digraph by removing the arcs (1,6),
(1,2), (2,6), (2,3), (3,5), (3,1), (4,2), (4,3), (5,1), (5,4), (6,4), (6,5). This arc set
cannot be partitioned into disjoint cycles of length three or greater. For exam-
ple, the deleted cycles (1,6,5) and (1,2,6,4,3) are not disjoint.
\
6
5
4
The class of (n3)-regular digraphs of course gives rise to a class of
(n 3)-regular (0,l)-matrices which is the class of the adjacency matrices of the
(n3)-regular digraphs. It follows that there is a subclass A of (n 3)-regular
(0,l)-matrices induced by the subclass D and that An C A. In line with the
notation introduced for Dqu .. _; qk, the notation Aqu ..., 9jt will be used to
represent a particular member in the subclass: Thus, A3^5 is the adjacency
matrix of the digraph 113,4,5- Due to the size and complexity of the digraphs
involved, most of the discussion of the subclass D will take place within the con-
text of the adjacency matrix.


54
Since Dqu ... ,9jt is formed by starting with D(n,n1), the vertex set of
each C{, together with all the arcs connecting those vertices in D(n,n 1),
represents a complete subdigraph on ft vertices. So removing the forward and
back arcs of a disjoint cycle of length ft from D(n,n1) is equivalent to con-
structing a (93)-regular subdigraph on ft vertices. If Dqu i qkG D is a
digraph constructed by Algorithm 4.2, then Dqu..., is isomorphic to
Dw(qu ... ,9i) where 7r(?i, ,ftt) is any permutation of the fts. By ordering
the Cf- according to size from smallest to largest and by choosing the vertices of
each Cj in numerical order, starting with 1 in the smallest <7,-, the adjacency
matrix can be presented in a simple, compact form in terms of submatrices
which are (ft 3)-regular. These (ft 3)-regular submatrices will always have the
general form of the matrix An in Section 2. For larger values of n the matrices
03, A4, A5, and A6 frequently appear as submatrices. The adjacency matrices
03, A4 and A 5 with their digraphs were shown in Example 4.1 and the matrix
A6 and its digraph were shown in Figure 4.1.
The following example illustrates the way in which these submatrices
can occur in an Aqu .. qk matrix.
Example 4.4:
The complete adjacency matrix of A3j4)s is shown below. This is the
adjacency matrix of the 9-regular digraph on 12 vertices constructed by remov-
ing the forward and back arcs of the following cycles
9i 3; Ci (1,2,3)
?2 = 4; Ci = (4,5,6,7)
<73 =5; C2 = (8,9,10,11,12)


55
The submatrices corresponding to C4, C2, and C3, are, respectively,
O3, A4, and A§. The vertices of the cycle determine the location of these sub-
matrices as blocks in the adjacency matrix A3,4,5. These blocks are marked by
dashed lines in the matrix.
/ 0 0 0 11 1 1 1 1 1 1 1 \ 1
0 0 0 jl 1 1 1 1 1 1 1 1
0 0 0 ll 1 1 1 1 1 1 1 1
1 1 1 |0 0 1 0.1 1 1 1 1
1 1 1 >0 0 0 1 I1 1 1 1 1
1 1 1 jl 0 0 0 11 1 1 1 1
1 1 1 1 1 0 0 ,h- 1 1 1 1
1 1 1 1 1 1 1 0 T 1 0
1 1 1 1 1 1 1 10 0 0 1 1
1 1 1 1 1 1 1 jl 0 0 0 1
1 1 1 1 1 1 1 'l 1 0 0 0
1 1 1 1 1 1 1 0 1 1 0 0
Note the large blocks of ones that occur. These blocks appear because,
for a given subset of the vertices contained in a g,-cycle, only arcs connecting
those vertices are removed. For example, in C2, only arcs connecting vertices 4,
5, 6, and 7 are removed. These four vertices remain connected to all other ver-
tices, hence for rows 4, 5, 6, and 7, only the entries in columns 4, 5, 6 and 7 are
changed. Hereafter the notation Jp> q will be used to denote the pxq, and Jp the
pxp, matrix of all ones. The above matrix could be written more simply as
o3 *^3,4 *^3,5
*^3,4 a4 ^4,5
^5,3 ^5,4 ^5
In the next section the properties of the matrices in A are explored.


56
4.4 The Subclasses D and A
As a first step in the study of the subclasses D and A, all possible
Dgu ... ,qk from n = 3 to n = 12 and their adjacency matrices were determined.
The results axe summarized in Table 4.1. For each A?1 . )?Jfc, real rank was
calculated using a computer and an attempt was made to determine the boolean
and nonnegative integer ranks. In some cases it was possible to obtain exact
results using Propositions 3.1.2 and 3.1.4, Theorems 4.2.1, 4.4.2, 4.4.4, their
corollaries, and the relationships between the semiring ranks and the biclique
numbers that were established in Chapter II. To illustrate, by Theorem 4.2.1,
tr{At) = 7 so rz+(A7) = 7 as r^{Ag) < r^+(A7) < 7; A7 has 7 isolated
ones, hence rg(A7) = 7 by Proposition 3.1.4. It proved easier to find nonnega-
tive integer rank than boolean rank and in many cases only upper bounds for
these ranks could be established. Examples 4.5, 4.6, and 4.7 are typical of the
types of arguments used to verify the results in Table 4.1 or to determine the
upper bounds on the semiring ranks.
The matrix A91j->)?a contains as submatrices Aqi, Aq2, Aqk
where, for i = l,...,fc, either Aq. = 03 or Aq. = Ay (where Ay is the matrix of
Algorithm 4.1 and Theorem 4.2.1). An examination of the matrices in Table 4.1
and their real ranks suggests there is a connection between the submatrices Aq.,
which occur in a particular Agu ..., ?Jfe and the real rank of Aqu ,. qt- Consider
for example, A4>5. The matrix is
' A4 J4)5'
^5,4 -^5
v /
Now, r£(A4j5) =9 = 4 + 5= rjj(A4) + r^(A5).


TABLE 4.1
Digraph Matrix rR rg+
Dz 03 0 0 0
d4 a4 4 4 4
d5 ^5 5 5 5
D6 ^6 4 6 6
&z,z o3 J3' Jz 03 v / 2 2 2
d7 a7 7 7 7
03,4 > ^3 J 3,4 ^4,3 A4 \ / 5 5 5
Dz ^8 8 8* 8
03,5 / 03 *^3,5 *^5,3 -^5 \ / 6 6* 6
04,4 A4 j4 j4 a4 \ y 8 6* 8
* upper bound


TABLE 4.1 (continued)
Digraph Matrix rR *B r*+
d9 -^9 7 7* 9*
03,6 03 J 3,6 J 6,3 A.6 s / 5 6 7
04,5 A4 ^4,5' A,4 ^5 s, / 9 7* 9
03,3,3 / 03 J3 J3 J 3 03 ^3 ^3 ^ 3 03 \ / 3 3 3
Dio ^10 10 8* 10
03,7 03 J3J J 7,3 A.7 \ j 8 8* 8
04,6 A-4 ^ 4,6 ^6,4 A6 V*- y 8 8* 10*
05,5 A 5 J5 J5 A§ \ / 10 7* 10
D 3,3,4 \ O3 J 3 ^3,4 *^3 ^3 *^3,4 *^4,3 *^4,3 -^4 / 6 6* 6
* upper bound


59
TABLE 4.1 (continued)
Digraph Matrix rR rs rz+
Du An 11 9* 11
D3,8 O3 Jz,8 J&,2 Ag < ) 9 9* 9
^4,7 A4 J4)7' J7,4 A7 k ^ 11 9* 11
£5,6 a5 J5)6' *^6,5 Ag V / 9 8* 11*
D 3,3,5 / \ 0 3 ^3 *^3,5 ^3 J3)5 ^5,3 *^5,3 A 5 k J 9 7* 9
£>3,4,4 / \ Oz *^3,4 *^3,4 ^4,3 A4 J4)4 ^4,3 *^4,4 A4 k / 9 7* 9
Di2 A12 10 10* 12*
£3,9 03 j3,g' ^9,3 Ag k / 8 8* 10*
* upper bound


TABLE 4.1 (continued)
Digraph Matrix rR £? rz+
£>4,8 4 ^4,8 *^8,4 Ag 12 9* 12
£>5,7 A5 *^5,7 ^7,5 -A 7 ) 12 9* 12
^>6,6 A e J61 ^6 Ag \ / 8 8* 12*
£>3,3,6 / \ ^3 J 3 7^6 *^3 ^>3 *^3,6 *^6,3 ^6,3 A6 \ y 6 7 8*
£>3,4,5 / V ^3 ^3,4 ^3,5 *^4,3 A4 ^4,5 A,3 ^5,4 A 5 \ ) 10 8* 10
Da, 4,4 / A ^ J ^ / ^ /" ^ A ^ /^ / 4 J 4 A 4 \ / 12 7 12
£>3,3,3,3 \ 0 3 J3 J3 J3 3 £>3 *^3 3 J 3 3 O3 J3 ^3 ^3 *^3 ^3 \ / 4 4 4
* upper bound


61
Or, consider A3j 4)5, whose matrix is given by
/ \
Oz ^3,4 ^3,5
^4,3 A4 *^4,5
^5,3 ^5,4 ^5
Here, rfl(A34)5) 10 1 + 4 + 5 r^(J3) + rR(A4) + rR(A5).
In every case examined so fax, namely those in Table 4.1, it turns out
that the real rank of Aqu ...,qk may be found by summing over the real ranks of
the submatrices Aq. and then adding one for each occurrence of the matrix 03,
since every time 03 occurs there is a corresponding block J3 which has real
rank 1.
Let Aq. denote a submatrix of Aqu ... ,qk- Set
Si = {A,.: & = 0 (mod 3), q{ =h 3}
Si = {Aq.: q{ = 1,2 (mod 3)} (1)
s3 = {Aqr. qi = 3} .
Observe that if Aq. G Sx, rR(Aq.) = q{ 2; if Aq. G S2, rR(Aq.) = q{. For each
Aqi £ S3, there is a corresponding rank 1 matrix J3.
|Sil
01 = £ rR{Aq,) for a11 Aqi e Si (2)
i=i
I Sa|
02 = £ rR(Aq.) for all Aq. G S2
=1
| £3 |


62
Conjecture 4.1
Let Abeannxn (0,l)-matrix such that A = Aqij. 9 Then
Tr{A) = oi + o2 + 03 .
One case of this conjecture has been verified and is stated in Corollary
4.4.3. The corollary follows easily from Theorem 4.4.2. The technique of the
proof of this theorem is similar to that of Theorem 4.2.1
Theorem 4.4.2
Let re = 3 + k, re > 7.
(1) If re = 0 (mod 3), then rji(A3fk) = re 4.
(2) If re = 1,2 (mod 3), then r^(A3)*) = re2.
Proof:
Az,k
Os J3,k Jk, 3 Ak '
*4,3 Ak \ J O3 J 3,k \ /
by row interchange.
Letx = [xi,X2, ,xn]T be such that A3k~x = 0, which implies that A '~x = 0.
Let Si be the tth row of A'. Then A '~x = 0 implies that Sj-~x = 0 for
i = 1,2, ,re. Observe that
14-2 -In = X4 + x5 + x6 + + = 0 . (1)
Also, Sf ~x = 0 and Sj ~x = 0 imply that (at- Sj) '~x = 0. In particular, con-
sider
(a-2 -~*i) -[-1-1-11110 0]
=> 04-2 -"02) = -Xi-Xi-Xz+X^+Xz+XQ = 0


63
> xi+x2+x3 X4+X5+XQ . (2)
Claim: For = 4, n 3, x, = xi+3 .
Consider "ay for j = 3, ,n 4:
y+ist y+4th
column column
~aj-1 = [ 1 1 000 1 1 1 ]
~ctj =[ 1 1 100 0 1 1 ]
Hence
(ay ay_i) = [0 0 10 0-10 0]
where the 1 is in column j+1 and the -1 is in column j +4. Therefore
(ay -'ay_i)-'l = Iy+1-Iy+4 = 0
=> Xj+1 = Xj+4 => Xi = X{+3 for = 4, ,n-3 . (3)
Additionally,
(% 3 -~2n-4) = [0 0 0 -1 0 0 10 0]
=> (h-3 -~an-4) '~X = *4 + *n-2 = 0 => X4 = Xn_2
(o-3 -^l) = [000010 0-10]
=> (a_3 -"ai)--? = x5 + ir-i = 0 => x5 = n-i
(a^2 "<*1) = [000001 01]
=> (a2 "aj) rx = x6 + xn=0 => x6 = xn .
From (3), for = l,2,...fc1, the components of ~x may be divided into three


64
disjoint sets
x4 = x7 = xio = Sx = {a;3f+1}
x5 = x8 = xn = 6 S2 = {*3,+2}
x6 = x9 = xi2= S3 = {x3i+3}
where all the elements in Sj are equal, j = 1,2,3, and n = 3k or n
n = 3k+2. Also,
x4 xn 2
x5 = xn 1
x6 xn
Case I: n = 3&+1
By (5),
x4 xn 2 ^fc+l2 x3k 1
I3fc-3+2 I3(fc-l)+2 £ S2
> X4
and
xn 1 ^SA+l1 x3k
x3k-3+3 x3(k-l)+3 £ S3
=> X§ Xq .
Therefore
x6 " xn 2 1 xn
By (i),
an_2-x = Xi + xs + x6 + + Xn
(4)
= 3fc+l or
(5)


65
= (re3)z4
as"an_2 has re3 nonzero entries. Since re > 7, re3 > 0, so
<4-2 '~x = (re 3)x4 = 0 => x4 = 0 .
By (2),
+ X2 + X3 X4 + X5 + Xq
= z4 + x4 + x4
= 0
Therefore
=> xx = -x2-x3
xi
x2 x2 X3 -1 -1
xs x2 1 0
x4 x3 0 -1
x5 0 0 0
x6 0 0 0
0 0 0
. = X2 + xs
xn2 0 0 0
xnl 0 0 0
xn 0 0 0

x2 u + x3v .
Since x2 and x3 are arbitrary, x2~u + z3~v = 0 iff x2 = x3 = 0. Therefore ~u and
~v are linearly independent, implying that dim(iVS(A')) = dim(.ZV5(A3)*)) = 2
when re = 1 (mod 3). Therefore
rR[^3,k) = re2 when re = 1 (mod 3) .


66
Case IE: n = 3A;+2
By (5),
x4 ~ xn-2 ~ x3k+2-2 ~ x3k ~ x3k-3+3
£3(*-l)+3 S3
=> X4 = Xq .
By (3) and (5),
x6 ~ xn xn-3 x3k+2-3
x3k 3+2 3(fc-l)+2 ^ S 2
=> Xq = X5 .
Therefore,
x4 x5 ^6 ' xn 2 xn1 xn
By the same argument as in Case I
rR(A3tk) = n 2 when n = 2 (mod 3) .
Case III: n = 3k
By (5),
x4 ~ xn-2 ~ x3k-2 ~ x3k-3+l ~ 3(fc-l)+l £ &1
x5 = xn-1 = x3k-l = x3k-3+2 = ;c3(fc-l)+2 £ &2
x6 xn x3k ~ x3k 3+3 S3(A-l)+3 £ ^3
Therefore the Sj are disjoint for j = 1,2,3, implying
X4 X*j " Xft2
X5 = x8 = = xn-l
X6 = Xg = = Xn .


67
By (l),74-2 = z4 + x5 + xQ + + xn = 0. Thus
{x4+X7+ +XW_2) + (5+8+ +*n-l) + (6+9+ +^n) = 0 .
Since a_2 has n 3 = 3k3 nonzero entries, there are k1 entries in each
group of the last equation. Therefore
(k-1)2:4 + (£-1)2:5 + (A:l)rc6 = 0
= -> 2^4 = 2Jg Xq .
By (2),
X1 + x2 + ^ = X4 + £5 + Xq
= -Z5-X6 + z5+2;6
= 0
=> X1 = -X2-X3 .
Therefore ~x must have the form
' X1 ' -*2-2:3'
*2 x2
*3 2:3
x4 -215-2:6
XS 2:5
x6 = 2:6
xn2 ~x5~x6
xn-l x5
xn x6
- -


68
That is
?= (z2) [-1 1000000 0 0 0]r
+(s3) [-10 1 00000 0 0 0]r
+(i5) [0000-1 10-1 10 -1 1 0]T
+(x6) [0000 -10 1 -10 1 -1 0 l]r
= x^u + x^v + x$!v + x^z .
Since x2, xZi x5> x6 3X6 arbitrary,
+ x^v + x5w + x^z = 0 iff x2 = x3 = x5 = x6 = 0 .
Therefore it, if, Iv, and? are linearly independent and dim(iV5(A3)fc)) = 4.
Therefore
r^(A3)^) = n4 when n = 0(mod 3)
It is interesting to compare the nullspace vectors derived in this proof
with those of Theorem 4.2.1. First of all, it was shown in the proof of Theorem
4.2.1 that, for a matrix of the form An, if 3 did not divide n, then the only
nullspace vector was the zero vector. The nullspace vectors for Cases I and II of
Theorem 4.4.2 are~u = [110 0]r and"w = [1010 0]r. If is one of
rows 1, ..., n 3 of A' (in the proof of Theorem 4.4.2), then the zero components
of both It and 11 correspond precisely to those components of "a; which are from
A*. The nonzero components correspond to the ls in columns 1,2, and 3 of A'.
1 1 l'
of A' formed by any 3 of rows 3 and the
The submatrix J3
111
111
first 3 columns of A' has real rank 1 and hence dim(NS(J3)) = 2. If the first
three components of it and it are used to form the vectors it =[11 0] r and


69
__v' .ni . t _. /
v = [10 1] s it is easy to check that in fact u and v span the nullspace of
J3. In a similar way, the components x^ ,xn which form the zero vector of
length re 3, span the nullspace of Ak.
Turning to Case m of Theorem 4.4.2, these same relationships hold for
vectors ~u and it In addition, for components x4, ,x,the vectors
w = [0 0 0 -1 1 0 -1 1 0 -1 1 0]T
and
~z = [000-10 1 -101 -1 0 1}T
are precisely the same as the nullspace vectors of Case m of Theorem 4.2.1, i.e.,
in components x4,...,xn they axe the nullspace vectors of Ak. It would be
interesting to derive the nullspace vectors for other cases to see if similar pat-
terns emerge. If some predictable behavior for the nullspace vectors could be
established, it might provide a way to prove Conjecture 4.4.1.
Theorem 4.4.2 can be applied to obtain two results. If re = 3+fc, with
re = 0 (mod 3), then k = 0 (mod 3) and
3 ,k
^3 ,k
Ak
Following the notation established in (1) and (2), ^3 = {O3}, hence
i = rR{Ak) = k-2
<73 = 1
Substituting into the conclusion of Theorem 4.4.2,
^(^3,*) = n~4 = S+k-4 = (Ar-2)+l = rR(Ak) + 1


70
0i + <72 + C3
On the other hand, if n = 1,2 (mod 3), then Si = & S2 = {Ak}, S3 = {03},
and Oi = 0, er2 = k, and rRiA3,k) = n-2 = 3 + k2 = k + 1 = r^(AA) + l
= (?i + a2 + <73 .
This proves the following special case of Conjecture 4.4.1, stated here as a Corol-
lary to Theorem 4.4.2.
Corollary 4.4.3
Let 3+k = n > 7. Then
rRiA3,k) = + *2 + = rR(Ak) + 1
In addition to this result, it is possible to obtain an exact value for the nonnega-
tive integer rank of As,k when n = 1,2 (mod 3). Recall that Dqu ... is iso-
morphic to D^qu ..., n). Hence bp (Dqu ..., qt) = bp (Dw(qu ..., 0j), since a
minimum biclique partition of Dqi ., qk is also a minimum biclique partition of
Dir(qu ..., qk) with vertices relabelled. This fact will be used in the proof of
Theorem 4.4.4.
Theorem 4.4.4
Let 3+A; = n > 7, n = 1,2 (mod 3). Then
rZ+(A3,k) = rR{A3,k) = k+1


71
Proof:
Since Dz p. ~ 3, it suffices to show that bp (Dk 3) = fc + 1. Consider
' J*, 3'
\ /
For i = 1,2, k, let Yj = {*+2,*+3, ,i+k2} where addition is modulo
k, and let Xj = {*}. Let Y = {re 2, re 1, re} For i 1,2, ,/:, define the
biclique
Br.XiYiUY.
Define the biclique
Then
Bk+l :{i2, re-1, re} -* {1,2,
B = {B1,B2, ,-BA,Bi+1}
is a biclique partition of 3. Hence bp (D^ 3) < k + 1 .
By Corollary 4.5.3,
**(^3,*) = + l => rR(Akj3) = *+l .
Since (D)) < bp (D), it follows that
bp{Dk,3) = k+1 = bp{D3jk) .
Therefore rz+{A3^k) = k +1. By Theorem 4.3.1 aiid Corollary 4.5.3,
rR[^3,k) = k+1. Therefore
rz+{A3,k) = rR{A3,k) .
Theorem 4.4.4 is not true if re = 0 (mod 3), as the following example shows.


72
Example 4.5: The Matrix A3)6
This matrix was discussed in Example 3.6, where it was stated that
rfl(A3)6) < r^(i43 6) < r^+(A3j6). This assertion is proved here.
-A 3,6
0 0 0 1 1 1 1 1 \ 1
0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
1 1 1 0 0 1 1 1 0
1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1
1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0
1 1 1 0 1 1 1 0 0
By computation, r^(A3j6) = 5. Since A3)6 has six isolated ones (the isolated
ones of the submatrix A6), rg{Az ,6) > 6- A biclique cover in six bicliques is
given by
{1,2,3,7,8} {4,5}
{1,2,3,4,9} -> {6,7}
{1,2,3,5,6} {8,9}
{4,5} {1,2,3,7,8}
{6,7} -> {1,2,3,4,9}
{8,9} -> {1,2,3,5,6} .
Hence = 6. Since rg < r^+ < n, it follows that 6 < r^+(A3j6) < 9.
Claim: r^+(A3j6) = 7.
It takes six bicliques to partition the submatrix A6. Let
B = {-61,-62, j-Bfc} be a set of bicliques that partiton A36, where
6j = A,> 7,-. It is clear that if X{ contains any one of vertices 4,...,9, then 7,-


73
cannot. The matrix
^3,6 Oq'
J&,z -^6
\ /
represents the subdigraph of Dqq induced by the arcs from vertices 4,...,9 to
vertices This matrix has six isolated ones, so it requires six bicliques to
cover the subdigraph. Hence, it takes six bicliques to partition that part of the
digraph corresponding the submatrix [J6)3 A6]. Each in the subpartition
must contain at least one of the vertices 4,...,9. Since no X{ containing 4,...,9
can have arcs to 4,...,9, one more biclique,
{1,2,3} {4,5,6,7,8,9}
is needed to complete the partition. Therefore,
bp{Dz,s) = 7 = r2+(A3j6)
and
ll 0*3,6) = n-4
while
**+(^8,6) = n-2
Recall that Aq was the first example found of an irreducible matrix for
which real rank and nonnegative integer rank differed by more than one. It
appears that Aq exerts a strong influence on any matrix that contains it: For
every entry in Table 4.1 that contains Aq, real rank is at most n 2 and in some
cases less than that, while the difference between real rank and nonnegative
integer rank is two or greater. Example 4.5 and Examples 4.6 and 4.7 below all
illustrate this effect. As is often the case, boolean rank acts in a more indepen-
dent manner. In Example 4.5, it is greater than the real rank, while in


74
Examples 4.6 and 4.7 it is less than the real rank in one case, and appears to be
equal to real rank in the other. Other examples are presented in Table 4.1.
Example 4.6: The Matrix A5j6
For this matrix, r^(A5)6) =9. It is conjectured that = 8 and
rz+{A 5,6) = 11-
-A 5,6
^5,6
^6
The matrix is without row containment and s (11) = 6. Also, no more than 6
isolated ones have been found, so r^(A5 ,6) > 6- The best biclique cover found
so far uses 8 bicliques. Whether a better cover exists remains open. A detailed
argument for the nonnegative integer rank value of 11 is not presented here. It
is in essence the same as the argument given in the example that follows, which
is the more significant example.
Example 4.7: The Matrix A6j6
This matrix has the structure
Aq J 6
J 6 -A 6
\ /
Its real rank has been computed to be 8. Since the matrix is without row con-
tainment, rg(A6)6) > s (12) =6. As in the previous example, the best biclique
cover found so far uses 8 bicliques. Nonnegative integer rank is the more
interesting aspect of this example. It appears that r^+(A6j6) = 12. If this is
true, then here is an example where real rank and nonnegative integer rank
differ by four. This conclusion is based upon attempts to partition this matrix


75
using bicliques. A variety of strategies have been tried and none have succeeded
in bettering the partition number of 12. While these attempts certainly do not
rule out the possibility that r^+(Ae,6) < 12, the problems encountered in trying
to find a biclique partition in fewer than 12 bicliques make it unlikely. So, while
this result remains conjectural, it seems reasonable. And it is believed that in
fact, real rank and nonnegative integer rank differ by 4 for A6 6.
The result of Example 4.7 suggested that further consideration of
matrices with block form

,6 -
'4 6 Je J 6 - . Je
Je Ae Je Je
Je Je
Je -^6 Je
Je . . Je A-6
might prove profitable. This matrix is (n 3)-regular and irreducible. The
dimension of A6)... ,6 is n = 6k where k is the number of A6s in A6j 6.
The following conjecture was derived by combining Example 4.7 with Conjec-
ture 4.4.1 concerning the real rank of Aqu . ^ .
Conjecture 4.4.5
1) rR(A6,...,6) = 4A; = -n .
2) ^+(A6)...,6) = n
A proof of this conjecture has proved elusive. It is difficult to work with
Ae,... e because it is a very full matrix. However, it was possible to prove
Conjecture 4.4.5 for a modified form of this matrix. That proof is the subject of
Section 5.


76
4.5 Semiring Ranks of an Infinite Class
A A
For notational purposes, in this section let D = Dq, A Aq, and
A A jjj A
O = 06. To begin, construct a digraph D by linking together k D's in the fol-
AAA A A
lowing way: Number the D's D2, ,Dk. For i = l,...,fc, connect A to
A A A A A
A+i by directing three arcs from D{ to Z)l+1. Connect Dk to Di by directing
A A A
three arcs from Dk to D. Since each D,- is strongly connected and there is a
A A
chain through all the Dfs, then D is strongly connected. Now let B be the
6x6 matrix
B =
'1 1 1 0 0 O'
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
A £
Construct A in the form
A Z
A =
An
On
B12 013
A
A 22 ^2,3
Oik
o2k
Ok-1,1
Ai Oq
Ak-i,k-i Bk_
A A
A-i,*
A fc A j(j A
D may be labelled so that A is its adjacency matrix. Hence A is irreducible,
A fe
though not (n3)-regular. Observe that A is 6kx6k where k is the number of
A A
As in A The following notation and terminology will be used in the proof of
Lemma 4.5.1.
A
A row block i of A denoted i?,-, is the submatrix
A A A A A
[n ' A, 2i A a B^ Ojjf .


77
In particular
R-i = [-^11 -12 ^13 Oik] 5
A A A
Rk = [Bkl Oki Ok,k-l Okk\ .
A
A column block j of A denoted Cj, is similarly defined.
Lemma 4.5.1 [10]
a a Hi
Let A be as defined in (l). Then A is row equivalent to
A
k
0's
N
O'*
^fcfe
Proof:
/ A All Bi2 bn 3* Oil A A 22 Bis Oik
Ok-1,1 A Ak-i,k-i Bk-i,k
Bki Ok* A a Ok- i,k Akk
1) The ls in row one of Bk\ coincide with the ls in row five of An and all
A
other entries in row five of An are zero. Replace row one of row block Rk by
subtracting row five of row block R i- This elimintes the ls in Bk\, but leaves
A A
all other entries in Rk unchanged. Thus, Rk = [Bki Ok-\,k Akk] is row.


78
equivalent to [0kx A**].
2) For i = 1,1, the ls in row one of coincide with the ls in row
A A
five of A4+1)(+1 and all other entries in row five of Ag-+1)>-+1 are zero. Replace
row one of row block R{ by subtracting row five of row block R(+i. This elim-
inates the ls in but leaves all other entries in J?t- unchanged. Thus
Ri [Oil
Oi,i-1
Mi
i,%+ 2
Oft]
is row equivalent to
A A
[o,-i Mi i,i+i ''' Oft]
A A A J^*
Therefore A is row equivalent to A .
Theorem 4.5.2 follows easily from this result.
Theorem 4.5.2
Let A be as defined.
Then
Proof:
A
By Lemma 4.5.1, A is row equivalent to
/ A
-^11
A
A 22 0's
a block diagonal matrix which is the direct sum of the A^-s. That is


79
Hence
A ~ Ak -An@A22 A-kk .
t=l
k A
*r{A ) = rR(Ak ) = rj($4)
'=i
= E by [11]-
i=l
By Theorem 4.2.1, rR(Atg) = r^(A6) = 4 for = 1,2, ,k. Therefore
Since n = 6 k,
= £ 4 = 4fc .
i=i
(Ak\ 2
rR(A ) = ~n
Recall that A = Aq has six isolated ones, that is, it has six ones no two
of which occur in the same row or column and no two of which occur in a 2x2
submatrix of the form
matrix below.
1 1
1 1
The isolated ones of A are underlined in the
A =
0 0 1110
0 0 0 1 1 1
1 0 0 0 1 1
1 1 0 0 0 1
1110 0 0
0 1110 0
- k
Clearly the set S of all ls of A such that 1 is an isolated one of some A# forms
an independent set containing 6k elements. Take any pair of independent ls
A
from this set. If both ls are entries of A4g-, then they are isolated, so suppose lt-
A A
is an isolated one of An and 1 y is an isolated one of Ajj, i=t=j. Without loss of


80
generality, assume i < j. Then there are three possibilities:
Case I: ji 1
A A
Then the submatrix containing A,-,- and Ayy has the form
s n| B{j
Oji Ayy
and the submatrix containing 1,- and ly has the form
-M
0 1y
where is either 0 or 1 depending on the positions of 1,- and ly in An and Ayy,
respectively.
Case II: j 1 > 1 =*= k1
A A
In this case, the submatrix containing A,-,- and Ayy has the form
'a* Oij
Oji Ayy
and the submatrix containing 1,- and ly has the form
(li 0
0 1,-
Case III: j i = k1
If this happens then must be 1 and j must be k. Then the submatrix contain-
A A
ing A,-; and Ayy is


81
/ A A
^11 Ol k
A
Bkl Akk
\ /
and. the submatrix containing 1?- and ly is
1,- O'
* 1
Lj
\ *
where is as in Case I. It follows that S is a set of isolated ones. By Proposi-
tion 3.1 and (2) of 2.4, r^+(A) = | S | =6k = n. The following result has been
proved:
Theorem 4.5.3
A fc
Let A be as in (1). Then
A jjj
rz+(A ) = Qk = n
Combining Theorems 4.5.2 and 4.5.3, the following corollary is immediate.
Corollary 4.5.4
A fa
Let A be as defined in (1). Then
/Ak\ /Ak\ 2
rz+(A ) rR(A ) = jn.
Thus the set of all matrices A defined by (l) is an infinite class of
irreducible (0,l)-matrices for which real rank and nonnegative integer rank differ
by -^-n. So far as is known, no other examples of irreducible (0,l)-matrices have
been found for which real and nonnegative integer rank differ by more than one.
Based on this result it is reasonable to ask: Are there other classes of irreducible
(0,l)-matrices for which the difference between real rank and nonnegative


82
integer rank is even larger? The method by which this class was produced may
prove useful in developing other examples for which these semiring ranks differ
by a significant amount.
/


CHAPTER V
CONCLUSION
The notion of a biclique has been used to extend to digraphs questions
asked about clique covers and partitions of graphs. The adjacency matrix of the
digraph has proved a useful tool in the investigation of minimum biclique covers
and partitions. The relationship between semiring ranks and these biclique
numbers has made it possible to translate these digraph questions into questions
about the minimum semiring ranks of (0,l)-matrices.
Significant work has been done to determine minimum semiring ranks of
a variety of classes of (0,l)-matrices. Of particular interest are the results
obtained for the classes of (n,k)~ and [n,n A:)-regular (0,l)-matrices. It has
been shown that r^(n,A;) = r^(n,nk) for all k. For k = 1,2,3, it also happens
that r^+(n, k) = r^+(n,nk). It is conjectured that this equality holds for all k.
This regularity of behavior is not shared by boolean rank. In general, the prob-
lem of determining boolean rank seems to be more difficult than that of finding
nonnegative integer rank.
Both boolean rank and real rank are lower bounds on nonnegative
integer rank. It has long been known that there were nontrivial examples in
which boolean rank and nonnegative integer rank could differ significantly in
size. However, in all known instances, whenever the matrix was irreducible, the
real rank and the nonnegative integer rank were either equal or differed by one.
A number of examples and one infinite class of irreducible (0,l)-matrices have
been presented here for which the difference in the two ranks is as great as -i-ra.


84
Thus there is a class of matrices for which real rank is not a good lower bound.
Open to research is the determination of other classes for which this occurs and,
more fundamentally, the determination of why this occurs.
A variety of results have been produced by investigating the subclass A
of (n3)-regular digraphs and (0,l)-matrices. All of the examples for which real
and nonnegative integer rank differ by more than 1 were drawn from this sub-
class. The infinite class of (0,l)-matrices for which the semiring rank numbers
differ by n was derived from this subclass. Some results on the real rank of
matrices in A have also been proved. It has been conjectured that the real rank
of any A.qu...,qk in A may be predicted based on the occurrence of certain sub-
matrices in This has been proven in one case; proofs of other cases of
this conjecture may give insight into the complete proof.
The natural extension of this work would be to consider next the class of
(n4)-regular digraphs and (0,l)-matrices. Little work on this class has been
published. It might be possible to take an approach similar to the one used
here, that is, to define some algorithmically derived subclass and then investi-
gate its properties. Would the members of that subclass exhibit behaviors simi-
lar to those in the subclass A? Might that subclass contain examples or lead to
examples in which real and nonnegative integer rank differ by more than ril
3
The answers to these and other questions await further research.


REFERENCES
C. Baxefoot, K.F. Jones, J.R. Lundgren, and J.S. Maybee, Biclique Cov-
ers of Regular Digraphs, to appear.
C. Baxefoot, K.A.S. Hefner, K.F. Jones, and J.R. Lundgren, Biclique
Covers of the Complements of Cycles and Paths in a Digraph,
Congressus Numerantium, 53 (1986), pp. 133-146.
R.A. Brualdi, R. Manber, and J.A. Ross, On the Minimum Rank of Reg-
ular Classes of Matrices of Zeros and Ones, Journal of Combinatorial
Theory Series A, 41(1) (1986), pp. 32-49.
D. de Caen, D.A. Gregory, and N.J. Pullman, The Boolean Rank of
Zero-one Matrices, Proceedings of the 3rd Car. Conf. Comb, and Comp.
(1983), pp. 169-173.
D.A. Gregory and N.J. Pullman, Semiring Rank: Boolean Rank and
Nonnegative Integer Rank Factorizations, J. Comb. Infor. and System
Sciences, 8(3) (1983), pp. 223-233.
D.A. Gregory, N.J. Pullman, K.F. Jones, and J.R. Lundgren, Biclique
Coverings of Regular Bigraphs and Minimum Semiring Ranks of Regular
Matrices, Journal of Combinatorial Theory Series B, to appear.
K.A.S. Hefner, Directed Biclique Covers and Partitions of Digraphs,
Ph.D. Thesis, University of Colorado at Denver (1988).
K.A.S. Hefner and J.R. Lundgren, Minimum Matrix Rank of k-regular
(0,l)-matrices, to appear.
K.A.S. Hefner, J.R. Lundgren, and J.S. Maybee, Biclique Covers and
Partitions of Unipathic Digraphs, to appear.
K.A.S. Hefner, T.D. Henson, J.R. Lundgren, and J.S. Maybee, Biclique
Coverings of Bigraphs and Digraphs and Minimum Semiring Ranks of
(0,1)-Matrices, to appear.
R.A. Horn and C.A. Johnson, Matrix Analysis, (1985), Cambridge, Eng-
land, Cambridge University Press.
K.F. Jones, J.R. Lundgren, and J.S. Maybee, Clique Covers of Digraphs
II, Congressus Numerantium, 48(1985), pp. 211-218.


86
[13] J.R. Lundgren and J.S. Maybee, Clique Covers of Digraphs, to appear.
[14] D. Pritikin, Applying a Proof of Tverberg to Complete Bipartite Decom-
positions of Digraphs and Multigraphs, to appear.
[15] F.S. Roberts, Applied Combinatorics, (1984), Englewood Cliffs, New Jer-
sey, Prentice-Hall, Inc.