FACTOR RANK OF BOOLEAN MATRICES
by
Eric Bruce Phelps
A. S., Arapahoe Community College, 1989
B. A., University of Colorado at Denver, 1991
M. S., University of Colorado at Denver, 1992
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
1996
1996 by Eric Bruce Phelps
All rights reserved.
This thesis for the Doctor of Philosophy
degree by
Eric Bruce Phelps
has been approved
by
David C. Fisher
51 94
Date
Phelps, Eric Bruce (Ph.D., Applied Mathematics)
Factor Rank of Boolean Matrices
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
The factor rank of an m x n matrix M is the minimum r such that M is
the product of an m x r matrix and an r x n matrix. Classical linear algebra
provides an efficient factorization algorithm whenever elements of M are from a
field. Boolean algebra (with 1 1 = 1) is not a field and matrix factorization over
this algebra is iVPComplete. The boolean rank of M, br(M), is the factor rank
of M under boolean algebra. The isolation number, bi(M), bounds 6r(M) from
below.
In the graph G,(M), a new result shows br(M) equal to the chromatic num
ber and bi(M) equal to the clique number. A hierarchy of matrix classes, where
br(M) = bi(M), is introduced. A known graph coloring algorithm shows br(M)
polynomially computable for every matrix in this hierarchy. The subclass factor
perfect is proven to contain all totally balanced matrices and a simpler polynomial
time factoring algorithm is given for totally balanced matrices.
Membership in another subclass, called graphically factor perfect, requires
Gi(M) be perfect. Often, perfect graphs are characterized by forbidden subgraphs.
Matrix extensions can be obtained directly by forbidding submatrices. Since a very
large number of submatrices might induce a given subgraph, extensions are not
always simply stated and their proofs become tedious. A computer was used to
prove lemmas for particular subgraphs.
IV
New bounds for trr(M) and bi(M) are derived from well known bounding
theorems in graph theory. Unfortunately, these formulas are usually weak and
sometimes difficult to evaluate. Stronger results are also derived from linear pro
gramming.
Isolation polynomials, which count isolated ones in much the same way rook
polynomials count matchings axe introduced. A recursion theorem gives an expo
nential time method for calculating the isolation polynomial and thus a method for
finding bi(M). Results about roots axe derived directly from the graph concept of
dependence polynomials.
Finally, universal boolean matrices are defined and used to prove additional
bounds on 6r(M), new results on regular and circulant matrices axe given, and
estimates of the expected value of br(M) and bi(M) for random M axe found to
diverge.
This abstract accurately represents the content of the candidates thesis. I recom
mend its publication. r
Signed
J. Richard Lundgren
CONTENTS
Chapter
1. Introduction........................................................... 1
1.1 Descriptions of Related Problems................................... 4
1.2 Applications....................................................... 6
1.2.1 Information Distribution........................................... 7
1.2.2 Feature Bounding and Extraction.................................... 8
1.3 Survey of Known Results ........................................... 9
1.4 Summary of New Results ........................................... 10
2. Background and Notation............................................... 13
2.1 Matrices.......................................................... 13
2.2 Linear and Convex Programming..................................... 14
2.3 Graphs and Coloring............................................... 15
2.3.1 Basic Terms....................................................... 15
2.3.2 Coloring.......................................................... 17
2.4 Perfect Graphs.................................................... 18
3. Factor Perfect Matrices............................................... 24
3.1 Block Cover and Isolation Graphs.................................. 24
3.2 Finding the Boolean Rank.......................................... 28
3.3 Submatrices and Subgraphs......................................... 30
3.4 MatrixOriented Constructions..................................... 32
3.5 Fractional Boolean Rank.......................................... 37
4. Results from Graph Theory............................................ 41
4.1 Forbidden Submatrix Theorems..................................... 41
4.2 Simple Bounds.................................................... 56
4.2.1 Isolation Number................................................. 58
4.2.2 Boolean Rank..................................................... 60
5. Totally Balanced Matrices............................................ 64
5.1 Definition and Basics............................................ 65
5.2 Perfect Ones Elimination......................................... 71
5.2.1 Vertex Clique Covers in Chordal Graphs........................... 71
5.2.2 Definition and Existence......................................... 73
5.2.3 Decomposition Algorithm.......................................... 75
5.3 Consecutive Ones Property ....................................... 76
5.4 Comparisons with Other Results .................................. 80
6. Isolation Polynomials................................................ 83
6.1 Root of Isolation Polynomials.................................... 86
6.2 Some Special Matrices............................................ 88
6.2.1 The Matrix In ................................................... 88
6.2.2 The Transitive Tournaments....................................... 92
6.2.3 Circulant Matrices............................................... 96
7. Special Matrices..................................................... 99
7.1 Universal Boolean Matrices....................................... 99
7.2 Regular Matrices................................................ 104
7.3 Circulant Matrices.............................................. 107
vii
7.4 Random Matrices................................................ 110
8. Miscellany......................................................... 113
8.1 The Function s(n).............................................. 113
8.2 Another Bound.................................................. 113
Appendix
A. fsubm.c............................................................ 115
References............................................................ 133
FIGURES
Figure
1.1 Subclasses of weakly factor perfect matrices................... 12
2.1 Subgraphs forbidden in an interval graph....................... 22
3.1 Example of a block cover graph................................. 25
3.2 Example of an isolation graph ................................. 26
3.3 Example of a block cover graph with a 5cycle.................. 32
4.1 Graphs for Lemma 4.1 through Lemma 4.16........................ 43
5.1 Example of a chordal graph with a perfect elimination scheme . 72
5.2 Examples of polyominos......................................... 79
TABLES
Table
6.1 Coefficients for the isolation polynomial of /....................... 93
6.2 Coefficients for the isolation polynomial of T....................... 95
6.3 Coefficients for the isolation polynomial of Bn....................... 96
6.4 Coefficients for the isolation polynomial of Bn....................... 97
6.5 Coefficients for the isolation polynomial of Hn....................... 98
I
t
1
*
I
1

i
i
t
i
x
1. Introduction
Define and on {0,1} as 0 0 = 0 and 10 = 01 = 11 = 1,
00=01=10=0 and 1 1 = 1. Then, extend these definitions to vector
and matrix operations in the natural way. As an example, consider the matrix
equation
M
1 1 0 0 1 0 0
0 1 1 1 0 1 1
1 1 1 1 1 1 1
0 0 1 1 0 0 1
110 0
0 111
0 0 11
LR.
Here, the 4x4 matrix M is factored into the product of a 4 x 3 matrix
L and a 3 x 4 matrix R. The minimum r so that an m x n matrix M can be
factored into the product of an m x r matrix L and anrxn matrix R is called
the factor rank of M. When using ({0,1},,) to define multiplication over
matrices, factor rank is also known as boolean rank and denoted br(M).
Some additional definitions and observations will be needed in the sections to
follow. Let M be a (0, l)matrix, then any submatrix K of M is called a block
when every entry of K is 1. For example, Ki = ({2,3,4}, {3,4}) is a block of the
leftmost matrix above, where {2,3,4} and {3,4} axe respectively sets of row and
column indices. Another block is AT2 = ({2,4}, {3,4}). A block not a submatrix of
another block is called maximal. AT is maximal, but AT is not. A block is said to
cover its entries. For example AT2 covers m23, m24, m42 and m44. The distinction
between a block and a matrix containing exactly that block is sometimes blurred.
1
The (maximal) blocks of a matrix provide an alternative definition of boolean
rank. In the equation
1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1
1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1
0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1
1 0 0
0 r 1 r 1 1 r
110 0 0 111 0 0 11
1 L 1 L 1 L
0 0 1
1 0 0
0 1 1
1 1 1
0 0 1
110 0
0 111,
0 0 11
the first line decomposes M into the sum of three of its blocks. The second line
equates each block with the product of rank one matrices, and the final line gives
a factorization M. We may generalize this example.
Let M be an m x n (0, l)matrix. Given any collection K, = {/v\, K2,..., Kq}
of blocks from M so that each 1 of M is covered by some member of /C, there
exists a factorization of M into an m x <7 matrix L and an q x n matrix R, where
the product of the jth column of L with the jth row of R has exactly Kj as a
maximal block. It is clear that any decomposition of M into L and R defines a
collection of blocks which cover its ls exactly. Therefore, br(M) is the minimum
q such that there exists a collection of q (maximal) blocks covering exactly the ls
0
of M. There is no simple relationship between the boolean rank of M and the real
rank of M.
The following theorem formalizes the difficulty of finding boolean rank.
Theorem 1.1 (Orlin 1977, [44]) Finding br(M) for an arbitrary (0, l)matrix M
is NPComplete.
There is a weak dual to boolean rank. Let M be a (0, l)matrix. A set
S = {m,Ul, m,2j2,..., mtpJp} with = 1 for k {1,..., p} is a set of isolated
ones when 6 S implies mu = 0 or = 0. For a matrix M, let bi(M),
the isolation number of M, be the size of a largest set of isolated ones of M.
The next theorem is based on the observation that every 1 in a set of isolated
ones must be covered by a different block.
Theorem 1.2 (Gregory and Pullman 1983, [25]) Let M be a (0, \)matrix. Then,
br(M) > bi(M).
As an example, let
0 111
M =
10 11
110 1
1110
The Is are a set of isolated ones (there are several other sets all of size 3). However,
it is not possible to cover the ls of M with only 3 blocks. The blocks K\ =
({1,2},{3,4}), Ki = ({3,4}, {1,2}), Ks = ({2,3},{1,4}), Kt = ({1,4},{2,3})
cover M. The blocks corresponding to each row (or column) would also be a block
cover of size 4.
In [10] de Caen, Gregory, and Pullman give a more general result. Let J be
3
the n x n matrix of all ones and let In be Jn /, then br(In) = s(n) where
s(n)
min
k:
k
LfJ
> n
log2 n.
Since the isolation number of / is always 3 for n > 3, we can find matrices for
which br(M) and bi{M) axe arbitrarily far apart. In most of what follows, we will
be concerned primarily with matrices where br(M) = bi(M).
1.1 Descriptions of Related Problems
There are several alternative notations for describing block covers and boolean
rank. These involve viewing M as a matrix associated with some kind of graph.
Various authors have published what can be interpreted as boolean rank results
in each notation.
The matrix M can be viewed as the reduced adjacency matrix of bipartite
graph B = (X, Y, E). Each row of M is a vertex in the X partition of B, and each
column of M is a vertex in the Y partition of B. Two vertices i X and j 6 Y
are adjacent if and only if mtJ = 1. The blocks of M correspond to bicliques of
B. That is a maximally complete bipartite subgraph of B. The minimum number
of bicliques required to cover B is called the biclique cover number of B or
bcc(B). Clearly, br(M) = bcc(B). A set of isolated ones of M corresponds with a
matching in B with the additional requirement that no two edges in the matching
be part of the same 4cycle.
If M is square, it can be viewed as the adjacency matrix of a digraph D. If
M has ls on the diagonal, then D must have loops. It is sometimes possible to
permute M so that no ls occur on the diagonal. Blocks are known as dicliques
and consist of a set of out vertices V and in vertices U and all possible arcs from V
4
to U. The minimum number of dicliques required to cover D is called the diclique
cover number of D or dcc(D). Clearly, br(M) = dcc(B).
The matrix M can also be viewed as a hypergraph with each row a vertex and
each column an edge. There does not seem to be a notation for either blocks or sets
of isolated ones in hypergraph terminology. However, the notion of composition
of hypergraphs is equivalent to the notion of boolean multiplication of matrices.
Given two hypergraphs G = (Fi, E2,. ., Em) and H = (Fi, F2,..., Fm) on a
vertex set X, the composition Gh is the hypergraph whose vertices /, represent
respectively the edges F, E H and whose edge sets Ej = {/, : F{C\Ej ^ 0}. Thus,
the matrix decomposition problem is equivalent to a hypergraph decomposition
problem. There is a class of hypergraphs known as totally balanced for which
the minimum edge hypergraph decomposition problem is shown to be polynomial
later in this thesis.
It is also possible to view the block covering problem as just another general
covering problem and study the associated covering polyhedron in the context of
integer programming. This was actually the path that led to the graphs described
later as block cover graphs and isolation graphs. Rather than study the covering
polyhedron, covering problems can often be described as coloring problems on a
certain graph with integrality of the covering polyhedron equivalent to perfection
of the graph. Finding the largest set of isolated ones is equivalent to finding the
largest cardinality integral point in the dual polyhedron.
Two related problems are also of interest, particularly for distinguishing them
from the block covering problem. First is the block partition problem. All of
the terminology used to describe block covering in its matrix formulation or its
5
bigraph, formulation or its digraph formulation apply to partitioning as well. The
only difference is that blocks in a block partition of M are not permitted to overlap.
That is, no two blocks in the same partition can share the same 1 of M and every
1 of M is covered by some block in the partition. The second related problem is
the edge clique covering problem. In this problem a graph G is covered with
cliques of G in such a way that every edge is in at least one clique. One might
be tempted to think that if M is a symmetric matrix with 0s on the diagonal,
then edge clique covering of the graph with adjacency matrix M is equivalent to
block covering of M + I. However, when covering with edge cliques, only blocks
which are principle submatrices axe allowed. So every edge clique cover of G(M)
produces a block cover M + /, but the converse is not true. The edge clique cover
does provide an upper bound on the boolean rank. As an example, consider the
graph A"i,4. Its edge clique cover number is 4. If M is its adjacency matrix, then
1111
110 1
10 10
10 0 1
and has a boolean rank of 3.
1.2 Applications
When looking for examples of where boolean rank or block covering has ap
plication, it is important to consider the features of the underlying algebra. Par
ticularly important is the property of addition which prevents ({0,1}, , ) from
being a field. That is, 1 1 = 1. Some natural processes follow this rule. For
M + I =
6
example, if you must eat caribou to survive in the Arctic, then if you can find
one caribou it is very much the same as finding two or more (as long as we are
only concerned with today). If you cant find a single caribou, then you have a
starvation problem. General systems that behave in this way have the feature that
the presence or absence of some object is important, but the presence of more
than one object does not change the logical outcome. The object could also be
replaced by an action. Death and destruction are good examples.
While the underlying algebra is very important, the matrix nature of block
covering must also come into play. The next few examples will show how this can
be done.
1.2.1 Information Distribution
Suppose there exists a secretive company that calls its employees agents and
that this company needs to distribute packets of information to these agents so
they can accomplish their jobs or missions. Let M be a (0, l)matrix with a row
for each agent and a column for each packet. It is important that each agent gets
the packets of information required, and it is also important that agents do not
get information they are not supposed to have. So, a 1 of M in row i and column
j says that agent i requires packet j. There is a 0 in the same position if agent i
does not need to know the contents of packet j.
There are two obvious ways to distribute the packets: either call in each agent
separately and hand over the packets required by that agent, or for each packet,
call in the agents that are to receive that packet. Due to cutbacks and budgetary
problems the company may be forced to look for more costeffective methods of
7
distribution. Costs axe directly proportional to the number of meetings.
Notice that a block in the matrix M is a set of agents that ail require the
same set of information. These agents could be called in and given the set of
information packets simultaneously. So, if M can be covered with fewer blocks
than the minimum of the number of agents and the number of packets, then there
is a more costeffective solution. The boolean rank will give an optimal number of
meetings and the block cover will describe exactly what information is given out
at what meeting.
The drawback of this plan is that each agent might need to attend several
meetings and may receive at least some of the same information in different meet
ings. Each meeting will provide each agent with at least one new packet if maximal
blocks are used in the cover.
1.2.2 Feature Bounding and Extraction
A biologist is interested in the mate selection process of ducks and sets up the
following experiment. A sample of m female and n male ducks is collected. Each
pair is observed together in an environment carefully constructed for harmonious
duck interaction, and the observations are carefully timed to correspond to the
natural cycles of the ducks involved. If female i appears to be attracted to male
j during the observation it is so noted with a 1 in position ij of a matrix M. No
attraction is noted with a 0.
A block in the matrix M represents a set of females which axe all attracted
to a set of males. Let us take a blind leap of faith and say that this is because all
of the males in the block share some common feature that is attractive to female
8
ducks. That is, assume that the female ducks are attracted to certain male duck
features, and that each female can have a different set of preferences. If a male
duck has any one of the features she prefers, she will be attracted. Each male duck
has a certain set of features. The features may be sets of overlapping attributes
(orangeness of feet, greenness of head, etc). Each block cover of M gives a possible
female to feature mapping and a possible feature to male mapping. Thus, each
block cover of M gives a possible explanation of the featurebased mateselection
parameters of female ducks. Notice that this is accomplished without knowing
specifically what features or attributes axe important.
The boolean rank of M gives the minimum possible number of features used
by female ducks to determine the suitability of a mate and would give a lower
bound of how complicated the process is for a given species. It would also be
important to compare the matrix M to random matrices of the same size. Some
new results on random matrices axe included later.
1.3 Survey of Known Results
Factor rank over zero sum free semirings, a class including ({0,1}, , ), has
been studied in [4] and [3]. Boolean rank is a specific topic of [10], [11], [31]
and [25]. In [37], Kim mentions boolean rank under the name Schein rank and
attributes the definition to personal communications with B. M. Schein dated 1973.
This seems to be the earliest definition of boolean rank in the literature.
When the matrix M is thought of as the reduced adjacency matrix of a bipart
ite graph B, matrix factorization is equivalent to finding a covering of the edges
9
of B using bicliques. The matrix M is sometimes also taken to represent the ad
jacency matrix of a digraph D. In this case, matrix factorization is equivalent to
finding a covering of the arcs of D using dicliques. Biclique covers were introduced
in [44]. Together with diclique covers, biclique covers are explored in [1], [2], [35],
[45], [30], [29], [36] and [34]. These references are not intended to be exhaustive.
For a survey of results concerning boolean rank and some related topics, see [42].
1.4 Summary of New Results
The overall impression of the research described in this thesis is that the
boolean rank and block cover problems share many similarities with graph color
ing. In several cases, results from the theory of graph coloring provide either a
direct result or an analogy that can be used to produce a new result. This seems
to be a new approach to the boolean rank problem and it is likely that there are
still many new results waiting to be discovered.
Chapter 1 is this introduction and Chapter 2 defines matrix and graph theory
terms. Chapter 2 can be skipped by many readers and referred too only when
notation is in question.
In Chapter 3 two graph constructions are defined for any (0, l)matrix M.
These graphs called the block cover graph or G\,{M) and the isolation graph or
Gi(M) are complements of each other. It is shown that minimum coloring number
of Gi is equal to the size of the largest clique in G, if and only if br(M) = bi(M).
Matrices with this property are named weakly factor perfect. A result by Lovasz
can then be applied to show that block covering of matrices with this property can
be accomplished in polynomial time. Some additional results are also given.
10
In Chapter 4 the block cover and isolation graphs are used to further explore
the class of weakly factor perfect matrices. Several subclasses are identified. Since
each of these corresponds to Gb and G{ being some class of perfect graph, these
subclasses axe grouped together under the name ^factor perfect. Results from
graph theory, bounding chromatic number and the size of the largest clique, axe
also used to find bounds for boolean rank and isolation number.
In Chapter 5 more subclasses of weakly factor perfect matrices are found,
this time without resorting to Gb or These matrices have the property that
every submatrix is also in the class. Such matrices axe named factor perfect. The
development contains analogies to chordal and interval graphs.
The subclass results of Chapters 3, 4 and 5 axe summarized in Figure 1.1.
In Chapter 6 the idea of an isolation polynomial is introduced. This polyno
mial associated with any (0, l)matrix M counts the number of sets of isolated ones
of a given size in M in much the same way rook polynomials count the number of
matching of a given size in a bipaxtite graph. Some properties of the roots of these
polynomials axe briefly discussed and the isolation polynomials for several simple
families of matrices are given.
In Chapter 7 matrices with special forms axe discussed. In several cases, these
lead to fascinating open problems. And finally, in Chapter 8 a few miscellaneous
results are proved.
11
AH (0,l)matrices.
Weakly Factor Perfect
Factor Perfect
gfactor Perfect
GbWeakly
Chordal
GbChordal
Gj Chordal
G. and G. Threshold
0 1
Gj Weakly
Chordal
GbUnit
Interval
Totally Balanced
SemiConvex
Polyomino
Figure 1.1: Subclasses of weakly factor perfect matrices
12
2. Background and Notation
2.1 Matrices
A p x q matrix is a rectangular array A of pq symbols enclosed in square
brackets; the symbols are called elements or entries and are arranged in p ho
rizontal rows and q vertical columns. The (i, j)entry is denoted a,y and equals
the entry in the ith row and jth column, numbering rows from top to bottom and
columns from left to right. A vector is a matrix that is only a single row or
column.
Given a pxr matrix A and a r x q matrix 5, their product is defined to be
the p x q matrix C with entries
r
Cij = ^ \ aikbkj
Jt=l
Matrix products are undefined in all other cases. The sum of two p x q matrices
A and B is defined elementwise and undefined if the rows and columns do not
conform exactly. The transpose of a matrix p x q matrix A, denoted AT is the
q x p matrix with the element a,j in the jth row and tth column. That is, atJ = aj{.
Given a pxq matrix A, any pair of no empty set R and C with R C {1,...,p}
and C C {l,...,q} defines a submatrix or A. This sub matrix is indexed by
applying some ordering to the elements of R and C, but in many cases any ordering
will do and it is not specified. If B is a submatrix of A, then A is said to contain
B.
An eigenvalue of a matrix A is any complex solution A to the equation
13
Ax = Ax, where x is a variable vector paired with A called an eigenvector.
Eigenvalues are extremely important in the study of real and complex matrices,
but will be mentioned here only in passing.
2.2 Linear and Convex Programming
Further information on the material in this section can be found in [41] and
[43]. A general math program is an optimization problem of the from
max /(x)
subject to
g(x) < bi
h(x) = 62
xeAcr.
where bx and 62 are fixed constant vectors. The constraints g(x) and h(x)
are fixed finite dimensional real vector valued functions. The vector x is of fixed
finite dimension n. The real valued function / is called the objective function
and maximizing this function is equivalent to minimizing /, so the direction of
optimization might be min as well. The set X is some easily defined subset of 3?n.
Often X is distinguished from the constraints only for algorithmic reasons. The
set of points x which satisfy all of the constraints, that is g(x) < bi,h(x) = 62
and x X is called the feasible region of the program. Points in the feasible
region are called feasible.
A linear program is a general math program with /, g, and h all linear
functions and X = $Rn. In this case / is specified by a vector c of length n, g by
a p x n matrix G and h by a q x n matrix H (where p is the length of 6j and q is
14
the length of 62). That is,
max cx
subject to
Gx < 61
Hx = b2
x C Un.
A convex program is a general math program with a convex feasible region.
That is, any point z on a line connecting any two feasible points xi and x? is itself
feasible. All linear programs are convex programs. A convex program with a
linear objective function can be thought of as a linear program with an infinite
number of linear constraints.
2.3 Graphs and Coloring
A graph G is a pair of sets (V(G), 5(G)), where V(G) is a finite nonempty
set of elements called vertices and 5(G) is a finite set of distinct unordered pairs
of distinct elements of V'(G) call edges. We call V{G) the vertex set and 5(G)
the edge set. These are sometimes abbreviated V and 5 respectively, when there
is no possibility of confusion.
2.3.1 Basic Terms
If 5 contains the unordered pair {u, u} of vertices u and u, then u and v are
said to be adjacent. If there is an edge connecting a vertex u to a vertex v, it is
denoted by (u,u) or equivalently (u,u). Note, no multiple edges are allowed, and
a vertex may not be adjacent to itself. The neighborhood of a vertex v is the
set of all vertices u connected to v. If two vertices u and v are not connected they
15
axe said to be nonadjacent or independent.
A subgraph of G is a graph G' where V1 C V and E' C E. An induced
subgraph of G G" is a graph where V" C V, and the edges in E" axe the edges
in E connecting vertices in V".
A path in a graph is a sequence of uj, ei, u2, e2,..., Vki, efc_i, Vk, where for
all 1 < i < k, et is an edge from u, to ut+i and where no u, is repeated. Only one
edge is possible between two vertices, so paths will be abbreviated ui, u2,..., ujt
A cycle is a path that begins and ends at the same vertex. The number of
vertices in a path or cycle is called the length of the path or cycle. A cycle of
length 3 is called a triangle. A tree is a connected graph that contains no cycle.
A graph is connected if there is a path between every pair of vertices. A
subgraph is a component if it is a maximal connected subgraph. A graph is
complete whenever there is an edge between every pair of vertices. The complete
graph on n vertices is denoted by Kn\ such a graph is also called a clique of size
n. A vertex v is simplicial if its neighborhood is a clique. A subgraph is an
independent set whenever every pair of vertices is nonadjacent.
The complement of a graph G is a graph with vertex set V and edge set E
which consists of exactly the unordered pairs of elements from V which are not in
E.
A directed graph or digraph D = (V, A) is a set V of vertices and a set A of
arcs connecting vertices in V. If there is an arc starting at a vertex u and ending
at a vertex u, it is denoted (u,v).
16
2.3.2 Coloring
A coloring of a graph G is a partition of the vertices of G into Cx, C2, > Ck
such that if the vertices u and v are both in C, then (u, v) is not an edge of G. The
sets Cx,C2,...,Ck are called color classes. It is always possible to color G with
Vj colors by putting each vertex in its own class. A more interesting problem
is determining the minimum number of color classes required for a given graph.
This minimum number is called the chromatic number of G or x{G).
A quick lower bound on x(G) is given by the size of the largest clique. Since
no two vertices of any clique can belong to the same color class, every vertex in
a clique must be in a unique color class. The size of the largest clique is denoted
u{G). So we have w{G) < x(G). Computing either u>(G) or x(G) is known to be
NPcomplete.
A real number called the fractional chromatic number or Xf(G) always
satisfies u>(G) < Xf(G) < x(G) This number can be defined as a solution to the
following linear program
min lTx
subject to
Ax < 1
x > 0,
where A is the vertex maximal clique incidence matrix of G. Since linear programs
are polynomially solvable, the number x/(G) would seem to be easy to compute (at
least for a computer), but setting up the problem requires finding all of the maximal
cliques of G. Since there is potentially an exponential number of these cliques,
finding Xf(G) by this algorithm is no longer polynomial. There axe heuristic
17
techiniques that find Xf(G) quickly in many cases (see [15]).
Another real number 9(G), defined by Lovasz in [39], satisfies w(G) < 9(G) <
Xf(G) < x(^) Lovasz defines this number to be the solution to a convex program
and that its value can be found to within e in time polynomial in V and loge.
This result means that for graphs where cv(G) = 9(G) = X/(G) = x(G), both
x(G) and u>(G) can be computed in polynomial time. The classes of graphs in the
next section all have this property.
2.4 Perfect Graphs
The following definitions are drawn from [7], [22], and [6]. For a more complete
treatment of perfect graphs consult one of these references. A graph G is called x~
perfect if it satisfies u(H) = x(H) for any H an induced subgraph of G. A graph
G is called aperfect if it satisfies a(H) = k(H) for any H an induced subgraph
of G. The Perfect Graph Theorem connects these two notions, establishing G
as xperfect if and only if G is aperfect. Graphs in this single class are simply
called perfect. If co(G) = x(G), but equality does not hold for every generated
subgraph, then G is called weakly xperfect. Similarly, if a(G) = fc(G), but
equality does not hold for every generated subgraph, then G is called weakly
aperfect. Weak x_Perfection is not equivalent to weak aperfection.
The following theorem is know as the Perfect Graph Theorem.
Theorem 2.1 (Lovasz 1972, [38]) A graph, G is perfect if and only if its comple
ment G is perfect.
We will now catalog several kinds of perfect graphs. Distinguish some graphs
with the following names:
18
Kn the complete graph on n vertices, an rcclique,
Cn the chordless cycle on n vertices, an ncycle,
Pn the chordless path on n vertices, an npath,
Km
vertices in the other; each partition is a independent set.
Ki'n the star graph onn + 1 vertices.
mKn m disjoint copies of Kn.
A graph G is bipartite if its vertices can be partitioned into two independent
sets. An equivalent condition is that G contain no chordless odd cycles of length
three or greater.
Theorem 2.2 (c.f. [6]) Bipartite Graphs are perfect.
Given a graph G = (V, E), the line graph of G, L(G), is a graph H with
vertex set E and two vertices of H connected whenever their corresponding edges
share a vertex of G.
Theorem 2.3 (Konig 1916, c.f. [6]) Line graphs of bipartite graphs are perfect.
A graph is a comparability graph if it can be obtained from a partially
ordered set P by talcing the elements of P as vertices and joining two elements
if and only if they are comparable. The complement of a comparability graph is
called an incomparability graph.
Theorem 2.4 (c.f. [22])Comparability graphs are perfect.
A pseudocycle is a sequence of vertices starting and ending with the same
vertex such that any two consecutive vertices are connected. Any vertex can appear
any number of times in a pseudocycle, but vertices are not considered connected
to themselves.
19
Theorem 2.5 (Gilmore and Hoffman 1964, [1]) A graph G is a comparability
graph if and only if each pseudocycle cq, a2,..., a2q, a2q+l,a\ of odd length con
tains an edge of the form (a,, a,+2) (where addition is modulo 2<7+ 1).
A chord in a cycle or path is an edge connecting to nonconsecutive vertices
of the path. A graph is chordal (or triangulated, or a rigidcircuit graph) if
every cycle of length greater than three has a chord. A chordal graph that contains
no 3sun is called strongly chordal.
A graph G is weakly chordal if neither G nor G contains a chordless cycle
with 5 or more vertices.
Theorem 2.6 (Hayward 1985, [28]) Weakly chordal graphs are perfect.
Corollary 2.1 (Berge I960, c.f. [22]) Chordal graphs are perfect.
The following theorem is of great utility in problems involving chordal graphs
and is used in several of the characterization proofs. A simplicial vertex is a
vertex whose neighborhood is a clique.
Theorem 2.7 (Dirac 1961, [12]) Every chordal graph has a simplicial vertex.
More definitions are required for the next theorem. A perfect vertex elim
ination scheme for a graph G = (V,E) is an ordering vi,v2,...,vm of the ver
tices of G so that in the series of subgraphs G', induced by V {ut,..., u,_i} for
1 < i < m the vertex u, is simplicial in G,. A subset S C V is a vertex separator
for nonadjacent vertices u and v if the removal of S separates u and v into distinct
separate components. If no proper subset of S is a (u, u)separator, then S is a
minimal (u, u)separator.
Theorem 2.8 (Fulkerson and Gross, Dirac, Walter, Gavril, Buneman, Suranyi,
c.f. [22]) Let G = (V, E) be a graph. Then, the following are equivalent.
20
(1) G is chordal,
(2) L(G) is chordal,
(3) G has a perfect vertex elimination scheme,
(4) Every minimal vertex separator induces a complete subgraph of G,
(5) G is the intersection graph of a family of subtrees of a tree, and
(6) There exists an orientation F of the edges E of G such that whenever (x,y)
and (x,z) are in F then either (y,z) or (z,y) must be in F.
Let Ii,..., In be intervals on a line, and define a graph G with vertex set
{/i, by connecting two intervals if and only if they have a point in common.
Graphs constructed in this way are called interval graphs.
Theorem 2.9 (Hajos, Gallai, c.f [22]) Interval graphs are chordal and thus
perfect.
Theorem 2.10 (Gilmore and Hoffman, Lekkerkerker and Boland, Fulkerson and
Gross, c.f. [22]) Let G be a graph. Then, the following are equivalent:
(1) G is an interval graph,
(2) G is both a chordal graph and an incomparability graph,
(3) G contains no C4 and is an incomparability graph,
(4) G does not contain C4, C5,... or any of the graphs in Figure 2.1 as an induced
subgraph,
(5) Any three vertices of G can be ordered in such a way that every path from the
first vertex to the third vertex passes through a neighbor of the second vertex,
and
(6) The maximal cliques of G can be ordered such that, for every vertex x of G,
the maximal cliques containing x occur consecutively.
21
Figure 2.1: Subgraphs forbidden in an interval graph
An interval graph is a unit interval graph if each interval in its construction
is of unit length. An interval graph is a proper interval graph if no interval
used in its construction properly contains another.
Theorem 2.11 (Roberts 1969, c.f. [27]) Let G = (V,E) be a graph. Then, the
following are equivalent:
(1) G is a unit interval graph,
(2) G is a proper unit interval graph,
(3) G is an interval graph and G contains no induced Kitz,
(4) G is a comparability graph and every transitive orientation of G = (V, E) is
a semiorder,
(5) There exists a semiorder (V, P) such that E = P + P~l, and
(6) There exists a realvalued function f : V > 5ft satisfying, for all distinct
vertices u,v V, (u,u) E, if and only if\f(u) f(v)\ < 1.
Let l and m be parallel lines, and let Si,..., Sn be segments connecting points
on l to points on m. Define a graph with vertex set {Si,..., S} by connecting
two segments if and only if they intersect. Suppose Si has endpoints on l and mt
on m. Without loss of generality, assume all 2n points are distinct and that the
segments are labeled so that li < I2 < ... < ln Then for h < k, segments Sh and
22
Sk axe adjacent if and only if my > m^. Thus the graph is uniquely determined
by the ordering of m, on the line m. Such graphs are called permutation graphs.
The complement of a permutation graph is also a permutation graph.
Theorem 2.12 (Pnueli, Lempel, and Even 1972, [13]) A graph is a permutation
graph if and only if it is both a comparability graph and an incomparability graph.
A graph G = (V,E) is a split graph if there is a partition V = / + K of its
vertex set into an independent set / and a clique K. There is no restriction on
the edges between / and K.
Theorem 2.13 (Foldes and Hammer 1977, Hammer and Simeone 1981, c.f [6])
Let G be a graph. Then, the following are all equivalent:
(1) G is a split graph,
(2) G is a split graph,
(3) G does not contain C\, Cs, or 2K2 as an induced subgraph, and
(4) if 81 > 82 > > Sn are the degrees of the vertices of G, then there exists
an integer k with 1 < k < n such that
(Si + + Sk) + Sn) k(k 1).
23
3. Factor Perfect Matrices
3.1 Block Cover and Isolation Graphs
Let M be a (0, l)matrix. Define the block cover graph Gb{M) = (V, E) as:
V = = 1}, and
E = {[(i,j), (M)]m,; = mu = mkj = mM = 1}.
And, define the isolation graph C?,(M) =< V, E > as:
V = {(ij)\mij = 1}, and
E = {[(*,i), (k,l)]\mu = 0 or mkj = 0}.
In the definition of E and E, both i = k and j = l are allowed. In particular, if
two ls of M are in the same row or column then their corresponding vertices are
always adjacent in Gb(M) and never adjacent in G,(M). Loops, however, will be
ignored. Notice that Gb{M) is the complement of G,(M).
As an example of this construction, consider the matrix
0 a 6 c d
0 0 e 0 f
0 0 0 9 h
0 i 0 0 j
0 0 0 0 0
24
g h j
Figure 3.1: Example of a block cover graph
where a,6,...,j axe all ls of the matrix. The block cover graph is given in
Figure 3.1 and the isolation graph is given in Figure 3.2. Notice that the graph in
Figure 3.2 is 3colorable and that the largest clique is also of size 3.
Assume M, V, E, and E are defined as above for the next sequence of lemmas.
Lemma 3.1 If K = {X,Y) is a maximal block of M, then Q = {(x,t/)x E
X and y E Y} is a maximal clique of Gb{M).
Proof: First, let {i,j) and (k,l) be arbitrary elements from Q. Then since K is a
block, mxy = 1 for every x E X and y E Y. So, m,j = mu = = 1. Thus,
[(z, j), (k, /)] E E and Q is a clique of Gh(M). Now, to see that Q is maximal,
suppose (i,j) 6 V is adjacent to every vertex of Q. Then, for every (k,l) E Q we
know m,j = mu = mkj = m*/ = 1. Thus, K' = (X U {z}, Y U {j}) is a block of
M that contains K as a subblock. But since A' is a maximal block, it could only
be that K = K' and so i E X and j E Y. This implies (i,j) E Q and that Q is a
maximal clique.
Lemma 3.2 If Q is a maximal clique of Gb{M), then K = {X,Y) where X =
{i\3j : (i,j) Q} and Y = {j3z : (z, j) E (?} is a maximal block of M.
Proof: First, let x E X and y EY. The adjacency of (x,j) E Q and (z, y) E Q in
Gb(M) implies mxj = m,j = m13, = mxy 1. So, in particular mxy = 1 and K is a
25
a
e
d
Figure 3.2: Example of an isolation graph
block. Now, to see that K is a maximal block, suppose K' = (X U {/:}, Y U {/}) is
also a block of M. Then, = 1 gives (k, l) g V and my = rrikj = m,/ = mtJ = 1
gives [(&, /), (i,j)] E for every i G X and j G K. So we have (fc, /) adjacent to
every vertex of Q. But since Q is maximal, it must be that (k,l) G Q. Therefore,
k G X and l 6 Y. So we have K1 = K and K is maximal.
Lemma 3.3 There exists a block cover of size r of M if and only if there exists
a vertex clique cover of size r ofGb(M).
Proof: Suppose there is a block cover of size r of M with blocks , K'r.
Then, K\,..., Kr can be constructed so that for i = 1,..., r, K{ = (Xi, Y,) is
a maximal block and K[ C K{. Thus, Ki,...,Kr is also a block cover of M.
By the construction of Lemma 3.1, there exists Qi,..., Qr, all maximal cliques of
Gb(M), corresponding to Afi,..., Kr. Now let (i,j) 6 V, so that mtJ = 1. There
must exist k {l,...,r} such that m,j is covered by Kk. This gives, i Xk
and j Yk. And since Qk = {(x,y)x G Xk and y 6 Tfc}, we have (i,j) G Qk
Therefore, Q\,..., Qr is a vertex clique cover of size r of Gb(M).
Now suppose there exists a vertex clique covering of size r of Gb{M) with
cliques Q[,..., Q'r. Then Qi,..., Qr can be constructed so that for i = 1,.... r,
26
Qi is a maximal clique and Q\ C Q,. Thus, Qi,...,Qr is also a vertex clique
cover of Gb(M). By the construction of Lemma 3.2, there exists Ki,..., Kr, all
maximal blocks of M, corresponding to Qi,..., Qr. Now let m,y be a 1 of M, so
that (i,j) V. There must exist k 6 {l,...,r} such that (i,j) Qk And since
Kk = {Xki Yk) where Xk = {i3j : (*, j) Q*} and Yk = {j3i : (i,j) Qt}, we
have m.ij covered by Kk Therefore, K\,..., Kr is a clique cover of size r of M.
Lemma 3.4 If Q is a clique of G,(M), then S = {mtJ(z,j) 6 Q} is a set of
isolated ones of M.
Proof: Let mtJ 6 S and mu S. Then (i,j) Q is adjacent to (k,l) 6 <5 implies
[(ijj), (&,/)] E. Thus, m,7 = 0 or mkj = 0 and 5 is a set of isolated ones.
Lemma 3.5 If S = {m,,^, m,2j2,..., m,pJp} is a set of isolated ones, then Q =
{{ik,jk)\k = 1..p} is a clique ofGi(M).
Proof: Let (z,j) and (k, l) be vertices of Q. Then, mtJ S and mu 6 S. Since
S is a set of isolated ones, m,/ = 0 or mkj = 0. Thus, [(*,./),(&,/)] 6 E and Q is
a clique of G,(M).
Theorem 3.1 For any (0, l)matrix M the following are true:
(1) 6r(M) = k(Gb{M))
(2) br(M) = X(Gi(M))
(3) bi(M) =w(G,(M))
(4) ti(M) = a(Gb(M))
where k is the vertex clique cover number, x w the chromatic number, uj is the
size of the largest clique, and a is the independence number.
Proof: In each case, it is important to observe that G,(M) = Gb(M).
(1) By definition, there exists a vertex clique cover of Gb(M) of size k(Gb(M)).
27
By Lemma 3.2, there exists a block cover of M using k(Gb(M)) block.
Thus, br(M) < k(Gb(M)). Also by definition, there exists a block cover
of M of size br(M). By Lemma 3.1, there exists a vertex clique cover of
size 6r(M). Thus, k(Gb{M)) < br(M).
(2) Follows from x(G0 = k(G).
(3) Given a clique of size a;((7t(M)), Lemma 3.4 guarantees the existence of
a set of isolated ones of the same size. So, u;(G,(M)) < bi(M). Given a
set of isolated ones of size 6z(M), Lemma 3.5 guarantees the existence of
a clique of the same size in G,(A/)). So, bi(M) < k(Gb(M)).
(4) Follows from a(G) = oj(G).
a
3.2 Finding the Boolean Rank
The theorem from the preceding section has a corollary that will be used to
establish the polynomial solvability of the boolean rank problem for a special class
of (0, l)matrices.
Corollary 3.1 Given a (0, l)mafna: M, the following are equivalent:
(1) br(M) = bi(M),
(2) Gb(M) is weakly aperfect, and
(3) Gi(M) is weakly xperfect.
Proof: (1) implies (2): Suppose br(M) = bi(M). Then, k(Gb(M)) = a(Gb(M))
and Gb(M) is weakly aperfect. (2) implies (3): Follows directly from G',(M) =
Gfc(M). (3) implies (1): Suppose G,(M) is weakly xperfect. Then, x(G,(M)) =
u{Gi(M)). So, br{M) = bi(M).
28
Corollary 3.2 IfGb(M) (respectively Gi(M)) is perfect, then br(M) = bi(M).
Proof: If Gb(M) is perfect, then Gb(M) is weakly aperfect. The perfect graph
theorem allows us to restate the result for Gi(M).
Originally in [39] and also in [6], Lovasz defines a real number 9(G) associated
with any graph, and proves ot(G) < 6(G) < k(G). The following theorem shows
that 9(G) can be efficiently approximated.
Theorem 3.2 (Grotschel, Lovasz and Schrijver 1981, [26]) There exists an al
gorithm which, for any graph G and real number e > 0, computes 9(G) with an
error less than e in time which is polynomial in V(G) and loge.
Corollary 3.3 Let M be a p x q (0,1 )matrix such that br(M) = bi(M). Then,
the boolean rank problem for M is solvable in time polynomial in pq.
Proof: It is possible to construct Gb(M) in (pq)2 time. This graph contains at
most pq vertices. Choose e = j in Theorem 3.2. Then we can compute 6(G) to
within  in time polynomial in pq. But since bi(M) = 9(Gb(M)) = br(M) is an
integer, it is the only integer in the range [9(Gb(M)) j, 9(Gb(M)) f ].
A stronger statement is possible when Gb(M) is perfect. Given a vertex clique
cover of Gb(M), it is possible to find a block cover of M. All that is necessary is
to make sure the cliques are maximal. Each clique can be extended to a maximal
clique in time polynomial in pq. Theorem 3.2 can be used to find a vertex clique
cover if G is perfect ([6]).
Corollary 3.4 Let M be a p x q (0, l)maÂ£na: such that Gb(M) is perfect. Then,
a maximum set of isolated ones and a minimum block cover of M can be found in
time polynomial in pq.
29
Unfortunately, the algorithm of Theorem 3.2 is based on the ellipsoid al
gorithm for linear programming, and is not computationally tractable (at least at
the time of this writing; see [43]). There is another number called the fractional
chromatic number associated with G, denoted x/(G). In [6], Lovasz also shows,
a(G) < Xf(G) < 0(G) < k(G). The fractional chromatic number is not known to
be polynomially computable; however, reasonable algorithms for its computation
in small cases do exist. For example in [15], Fisher, Marchant, and Ryan describe
an algorithm for which they have implemented FORTRAN code.
3.3 Submatrices and Subgraphs
Let M be a m x n (0, l)matrix. Let M' be the submatrix of M indexed
by X' C {1,..., m} and Y' C {1,..., n). Define the block cover graph of the
submatrix M', Gb(M') = (V, E) as:
V = {(i,j)e(X',Y')\mij = l}, and
E = {[(,j),(M)](*J)>(M) (X',Y'), and = mt7 = mkj = mki = 1}.
And, define the isolation graph of a submatrix M' as Gi(M') =< V,E> as:
V={(i,j)(X\Y)\mij = l}, and
E = {[(t,i), (fc, /)](, j) (X\ V), (*, l) 6 (X\ Y), and m,7 = 0 or mkj = 0}.
Lemma 3.6 If M' is a submatrix of M, then Gb(M') is an induced subgraph of
Gb(M) and Gi(M') is an induced subgraph of GfM).
Proof: It is clear that the vertices of Gb(M') are a subset of the vertices of Gb(M).
Let (i,j) (X',Y') and (k, l) (X',Y'), then (i,j) and (kj) are vertices of both
30
Gb(M') and Gb(M). If [(i, j), (fc, /)] is an edge of Gb(M'), then m,y = mu = mkj =
mki = 1. Thus, (fc,/)] is also an edge of G&(M). So, Gb{M') is a subgraph
of Gb(M). To see that it is an induced subgraph, suppose [(i,j), (fc, /)] is an edge
of Gb{M). Thus, mij = mu = mkj = mjt/ = 1 and [(i, j), (A;,/)] is also an edge of
Gb{M'). The proof for G,(M') is similar.
Since there exist matrices M such that br(M) and bi(M) are not equal, it is
clear that Gb(M) and G,(M) axe not always perfect. This can also be seen as a
corollary to the next theorem.
Theorem 3.3 Let H be any graph. Then there exists a (0,1 )matrix M such that
H is an induced subgraph of Gb(M).
Proof: Let A be the vertex adjacency matrix of H. Then M = / + A satisfies
the requirements. To see this, identify the vertices of H with the ls on the main
diagonal of M; i.e., for each vertex u, of H the entry m,, will correspond to that
vertex. The claim is that the subgraph of Gj(M) induced by (i, i) for i = 1,..., \H\
is equal to H. If ut and vj are adjacent vertices in //, then atJ = 1 and ay, = 1.
Thus, mu = mij = mji = myy = 1 and [(i, i), (j,j)] is an edge of Gb(M). Similarly,
if V{ and vj are not adjacent in H, then a,y = 0 and ay, = 0. So, [(i, i), (j, j)] is not
an edge of Gb(M). E
Corollary 3.5 Let H be any graph. Then there exists a (0, l)matrix M such
that H is an induced subgraph o/G,(M).
Proof: Just replace H with H. E
31
Figure 3.3: Example of a block cover graph with a 5cycle
As an example of the above construction, let H be a five cycle. Then, the
matrix M given by the theorem is
a 0 0 e
a' v2 b 0 0
0 b' V3 c 0
0 0 d VA d
e 0 0 d' v5
It has the block cover graph in Figure 3.3.
3.4 MatrixOriented Constructions
Recalling the connection made between coloring and boolean rank, it is pos
sible to define a perfect matrix in analog to perfect graphs. A (0, l)matrix
M is called factor perfect if bi(N) = br(N) for every submatrix N of M. If
bi(M) = 6r(M), but equality does not necessarily hold for each submatrix, M is
32
called weakly factor perfect. The matrix
0 1 1 1 1 0 0 0
1 0 1 1 0 1 0 0
1 1 0 1 0 0 1 0
1 1 1 0 0 0 0 1
is an example of a weakly factor perfect matrix, that is not also perfect. The
submatrix on the left has boolean rank 4, but isolation number 3. Since every
submatrix of M induces a subgraph of G,(M), the perfection of G,(M) (or equi
valently Gb(M)) implies the factor perfection of M. The converse is not true. For
example, the matrix
Â£1 a 0 v5
a' V2 b 0
0 b' V3 u4
has boolean rank and isolation number 3 since u4} is a set of isolated
ones, but its block cover graph contains the chordless five cycle V\, u2, v$, u4, U5,
Matrices whose isolation graph is perfect will be called graphically factor per
fect or gfactor perfect. By these definitions, weak factor perfection and weak
gfactor perfection are equivalent.
This section is intended to demonstrate a significant number of weakly factor
perfect matrices. The idea is to first show that some particularly simple matrices
are weakly factor perfect and then show how to use these to build more complicated
examples.
Theorem 3.4 The following matrices are all weakly factor perfect:
(1) An identity / matrix for any n,
33
(2) An all ones matrix Jn for any n,
(3) The vertexedge adjacency matrix of any simple path,
(4) The vertexedge adjacency matrix of any simple cycle,
(5) Any unit upper or unit lower triangular (0,1 )matrix, and
(6) The matrix M+P that satisfies the equation M+MT+P < J (under standard
matrix addition) where M is any (0,1 )matrix and P is any permutation
matrix.
Except for /, each of these matrices has full boolean rank. More examples of
matrices with full boolean rank are given in [25]. There axe weakly factor perfect
matrices that do not have full rank, but they seem to be harder to characterize.
The matrix M used in the introduction has br(M) = bi(M) = 3 and the matrix
1 1 0
N =
1 1 1
0 1 1
has br(N) = bi(N) = 2. Additional examples can be produced using the construc
tion of this section.
It is easy to show that weak factor perfection is invariant under transpose,
and under permutation of rows or columns. There are several simple construc
tions which preserve weak factor perfection. For example, given boolean matrices
Mi,..., Mit, the matrix
Afi 0 0
0 m2 0
\ 1 0
0 0 Mk
34
has br(N) = Â£*=l br(Mk) and bi(N) = 6i(A/*). So, if Mi,..., M/t are each
weakly factor perfect, then so is N.
A slightly more complex construction also preserves weak factor perfection.
Kim makes a series of definitions in [37] that can be compressed into the following.
The boolean column space of a p x q (0, l)matrix M, or BCS(M), is defined
as the set of all vectors obtainable as vjt vjk where j, {1,... ,
i = 1,..., k.
Theorem 3.5 Let M be any px q (0,1 )matrix, v BCS(M) and N = [Mv].
Then, br(N) = br(M) and bi(N) = bi(M).
Proof: Let t = q+1 so N has t columns. Let K\,..., Kr be a block cover of M of
size br(M). Since v = vj, Vjk, there exists a set R of ls from M with exactly
one member for each nonzero entry of v. Choose the ls of R from Vjn..., vjk
only. For any block Ki that covers ma& = 1 of R, construct K[ by adding t to the
column set of K{. Let mxy be a 1 in block K,. Since mst = 1 whenever s is the
index of a nonzero entry of some column Vjz and Vb is such a column, we have
mxy = mxb = may = ma& = 1 implies mxy = mxt = may = mat = 1. Thus, the
Kl's are blocks of N. Since R contains a 1 from every nonzero entry of v, these
A's cover the ls in column t. If Kz is a block that does not cover a 1 of A, let
AT' = Kz. So, K[,..., K'r is a block cover of N and br(N) < br(M). Since M is
a submatrix of N, the reverse inequality is clear.
Every set S of isolated ones of M is also a set of isolated ones of N, thus
bi(M) < bi(N). Suppose there is a set S' of isolated ones of N of size bi(M) + 1.
Then, there exists nJt S' for some i {l,...,p}. Let m,*, be the 1 of A on
the same row as n,t. Clearly n,& is a 1 of iV. Suppose there is a nxy = 1 in
35
S' rtit in a block with mb Then, = nxb = my = nib = 1. But since
v = Vjt & Vjk, nxt also equals 1 and we have = mb = n,t = 1.
This contradicts S' being a set of isolated ones. Therefore, there exists no 1 in
S' mt in a block with n,&. Thus, S' U mb is a set of bi(M) + 1 isolated ones
such that every 1 is also in M. This implies bi(M) = bi(M) + 1, a contradiction.
Corollary 3.6 Let M be any p x q (0, \)matrix, and v a column of M and
N = [Mu]. Then, br(N) = br(M) and bz(N) = bi(M).
Corollary 3.7 Let M be any p x q (0,1 )matrix with no zero rows, and N =
[M\J\. Then, br(N) = br{M) and bi{N) = bi(M).
If M is a n x m (0, l)matrix and N is p x q (0, l)matrix, then M Q N is the
np x mq matrix which can be written in n x m block form, the ijth block being
mij N] M 0 N is the tensor or Kronecker product of M and N. Two strings
of inequalities concerning boolean rank and tensor product were presented in [11]
by de Caen, Gregory, and Pullman. They are
max{bi(M)br(N), br(M)bi(N)} < br(M iV) < br(M)br(N), and
bi(M)bi(N) < bi(M 0 N) < mm{bi(M)br(N),br(M)bi(N)}.
The following is a natural corollary.
Corollary 3.8 Suppose M and N are both weakly factor perfect matrices. Then,
M Q N is weakly factor perfect. In particular, br(M O N) = br(M)br(N) =
bi{MQN).
Proof: By Theorem 1.2, br(M N) > bi(M N). So, we have br(M)br(N) >
br(MQN) > bi(MON) > bi(M)bi(N). Since br(M) = bi(M) and br(N) = bi(N),
36
the string of inequalities collapses.
3.5 Fractional Boolean Rank
It is possible to define a problem whose solution is the fractional chromatic
number of G,(M). Let M be a (0, l)matrix with blocks and sets of isolated
ones defined in the usual way. For each maximal block K{, i = 1,..., n, choose a
nonnegative real weight x, such that
f^XiKi > M.
=i
Then, )) = minÂ£"_i x,. Call this number the fractional boolean rank
of M, or 6r/(M). Of course, by linear programming duality, this problem has the
same value as what could be called the fractional isolation number, or bif(M),
defined as follows. For each 1 in M, choose a nonnegative real weight such that
for each maximal block K,
]C Vij < 1
mijZK
Then, bif(M) =u/(G,(M)) = maxYlij Vij
Trivially we have,
bi{M) < bif(M) = brf(M) < br(M),
and if M is weakly factor perfect then,
bi{M) = bif(M) = brf(M) = br(M).
In the case where a (0, l)matrix M is weakly factor perfect, brj{M) is a
perfect lower bound on br(M). There are example of matrices where this bound
can be made arbitrarily bad. To prove this, we will use the following lemma.
37
Lemma 3.7 For a graph G = (V, E), let q(x) be the number of maximal inde
pendent sets that contain the vertex x and Q(G) = min^ev q(x). Let R(G) be the
number of maximal independent sets of G. Let a(G) be the size of the largest
independent set of G and Xf{G) the fractional chromatic number. Then,
\V\
a(G)
< Xi(G) <
R(G)
Q(G)'
Proof: This is a simple counting argument using linear programming duality.
Consider the matrix M = For G = we have \V\ = n(n 1) and
a(G) = [f J Tf 1 Since each set of one or more rows defines a unique maximal
block, R(G) = 2n 1. Because M is so regular, every 1 is a member of the same
number of maximal blocks. To count these, partition M as follows,
1 o 1 1 1 1 1
1 0 1 1 1 1
1 10 11 1
1 1 1 0 1 1
1 1 1 1 0 1
1 1 1 1 1 1 o
Next, count the number of maximal blocks that contain mi in the upper right
hand corner. Clearly this m\n cannot be adjacent to any 1 in the first row or last
column. So, mln cannot be in any maximal block containing these ones. On the
other hand, mln is in the two maximal blocks defined by the last row and the first
column. Also, if K' is a maximal block in the matrix i at the center of M, then
this block can be expanded to include mi. There are no other maximal blocks
38
that could contain min and thus Q(G) = 2 + (2n 2 1) = 2n 2 + 1. Therefore,
i
n(n 1)
TUT!r
< br/iln)
<
2n 1
2n_2 +1'
And as 72 > oo, 6r/(/n) = 4.
We know that 6r(/) ~ log2 72 and so br(M) brj(M) can be made arbitrarily
large.
For matrices not weakly factor perfect, it is possible to tighten1 the bounds
on Kronecker product given by deCaen, Gregory, and Pullman, in [11].
The disjunctive product of graphs G and H, written G xd H, is defined as:
V{G xd H) = {(g,h)\g V(G) and h 6 V(H)}, and
E(G xd H) = {[(tfi,/h), (02,Mltei,52) 6 E(G) or {huh2) E(H)}.
Theorem 3.6 For (0, l)matn'ces M and N, Gi(M N) = G,(M) xd Gi(N).
Proof: Let 0 n^i represent the entry of M N in the block corresponding to
the ijth entry of M and the kith entry of that block. There is a 1 at mij Q n^i if
and only if there is a 1 at and a 1 at n^i. The vertices of G,(M N) are all
the ones of MON. So there is an exact match between vertices in G,(M N) for
pairs (0, h) where 0 is a vertex of G,(M) and h is a vertex of G,(1V). Thus, there
is an exact match between the vertices of G,(M N) and G,(M) xd G,(iV).
Suppose there is an edge of G,(M N) not in G,(M) xd Gi(N) and call it
[m.u, 72fcti,,m,2j2 nfcj/j]. There is an edge in G,(M N) between vertices
corresponding to and 772,2j2 nk2i2 whenever t72,U2 = 0 or
772{2j1 72^/, = 0. If 772tIj2 72*, j2 = 0 then from the definition of Kronecker product
1 Thanks to Dave Fisher, who initially suspected this tightening was possible.
39
I
m,u2 = 0 or nkii2 = 0. Similarly, if mt2jl nk2ix = 0 then = 0 or nkiix = 0.
There is not an edge in G,(M) xd G,(n) implies [m,un m,2_,2] ^ Z?(G,(M)) and
Â£ Â£(G;(iV)). But then, m,u2 = m,2j2 = nfclz2 = = 1 which
contradicts the previous statements and shows that every edge of G,(M N) is
an edge of G,(M) xd Gi(N).
Now suppose there is an edge of G,(Af) xd G{(N) not in G,(M N) and call
it [mtlj, njfcjfj, mt2y2 njt2/2]. It must be, by definition of disjunctive product,
that mi2J2] is an edge of G,(M) and nfc2/2] is an edge of G{(N). So,
m,u2 = 0 or m,2J1 = 0 and nkli2 = 0 or n/^it = 0. If m,U2 = 0 or m,2J1 = 0,
then milh nklh = 0 or m,2jl = 0 and [midl Q nklh,mhh nfc2/2] is an
edge of G,(M Af). Similarly, If nkdl = 0 or njt2/, = 0, then m,U2 njt,z2 = 0
or m,2J1 nk2ix = 0 and nklll,mi2h njt2z2] is an edge of G,(M iV). In
either case, we have a contradiction and show that every edge of G,(M) xd G{(N)
is an edge of G,(M IV), completing the proof.
Theorem 3.7 (c.f. [47]) Let G and H be graphs, then
max{Xf(G)x(HU(G)xf(H)} < X(G xd H) < X{G)X{H), and
uj(G)u(H) < u{G xd H) < min{u(G)Xf(H),Xf{G)u(H)}.
Let brj(M) = X/(G,(M)). Thus, bi(M) < brj(M) < br(M) and when
bi(M) < br(M), br/(M) is at least sometimes a better lower bound.
Corollary 3.9 Let M and N be (0,1 )matrices, then
max{brj(M)br(N),br(M)brf(N)} < br(M Q N) < br(M)br(N), and
bi(M)bi(N) < bi(M 0 N) < min{bi(M)brj(N),brj(M)bi(N)}.
40
4. Results from Graph Theory
Now that it has been shown that block covering is equivalent to coloring, it is
natural to see what results from the theory of graph coloring can be used to get
new results about boolean rank. Two types of coloring results will be used here.
First, some of the many results about perfect graphs will be exploited. Then,
known formulas for bounding the clique number and chromatic number of a graph
in terms of simple graph properties will be used directly to bound bi(M) and
br(M) respectively.
4.1 Forbidden Submatrix Theorems
Many classes of perfect graphs are characterized by a few forbidden subgraphs
or families of subgraphs. That is, if a graph does not contain any of the forbidden
subgraphs then it is a member of the class and each subgraph is itself not a member
of the class. Weaker results may give a list of forbidden subgraphs some of which
are members of the class. An example of the former is Theorem 2.10. An example
of the latter is the following.
Theorem 4.1 (Seinsche 1974, c.f. [5]) If a graph G does not contain P4 as an
induced subgraph, then G is perfect.
It is shown in Theorem 3.3 that any graph can occur as an induced subgraph
of either Gb or Gt. There are several problems to overcome when translating
forbidden submatrix theorems from graph theory to boolean matrices. First, any
graph we wish to forbid as a subgraph of either Gb or G; can be represented by
41
several possible matrices. For example, the path P4 occurs in the block cover graph
of both of the following matrices with a, 6, c, d indicating the path:
a 1 0 0
Mi =
16 10
0 1 c 1
,M2 =
a 6 0
0 c d
0 0 1 d
Of course, for a given graph there axe only a finite number of ways its vertices can
occur as ls in a matrix. However, it can be a very large finite number. Consider
the path Pn with adjacency matrix An. It occurs an an induced subgraph of
Gb{An /), but it also occurs as an induced subgraph of Gb(Mn) when M =
An In Tn and where Tn is any n xn tournament. The main diagonal and first
sub and super diagonals of T are obscured, but there are still 2^ 2 ) choices of
Tn which produce different Mn's. There are still many matrices containing M not
yet counted.
This sort of explosion in the number of submatrices which must be forbidden
can cause problems. A saving grace, is that for small graphs H, what often happens
is that a small matrix containing H in its block cover graph is often itself contained
in almost every larger matrix also containing H. This is exactly the situation for
P4. The smaller matrix M2 is a submatrix of the larger Mi. This means that if we
are trying to forbid P4 from Gb{M) we dont have to worry about Mi if we forbid
M2.
Where the combinatorial explosion does become a problem is when the graph
we must forbid is large or when there is an infinite family. With large graphs G,
the larger size of the smallest few matrices containing G generally mean that they
42
n <7
Kjj 3sun diamond
Figure 4.1: Graphs for Lemma 4.1 through Lemma 4.16
do not occur as often as submatrices of their larger cousins. In infinite families,
there are some very large members. In some cases it may be possible to find copies
of smaller members of a family in the matrices which contain its laxger members.
This research is yet to be done.
For several classes of perfect graphs there are a few small subgraphs whose
absence either characterizes or is sufficient to prove membership in the class. To
this end, all minimal matrices M with the graphs in Figure 4.1 as induced sub
graphs of Gb(M) or Gi(M) have been found and summarized in the following series
of Lemmas. Unfortunately, the method of proof is not elegant. It boils down to
an exhaustive search of all possible matrices M such that the given graph G is a
subgraph of Gb(M) or G,(M) respectively. This procedure is tedious and best left
to a computer. An outline of the computer algorithm used to prove the lemmas
follows; the complete C program can be found in the Appendix.
43
Let G be a graph. We wish to find all matrices N such that if M contains
any permutation of N as a submatrix then G is an induced subgraph of Gb(M).
During the processing, the algorithm maintains a list of known submatrices of
this type. The algorithm works by recursion and backtracking as described in the
pseudocode below. First order the vertices of G as V\,v2,... up. and initialize
the list L as empty.
Sprout (M, i)
if (any matrix on L is a submatrix of M) then return;
if Ci equals p) then
for each matrix L' on L
if CM is a submatrix of L') the remove L' from L;
add M to L;
for each possible placement of i inside, beside or below M {
Construct M' from M by placing vertex i;
for each possible way to fix the entries of M'
Call Sprout CM',i+l);
>
}
The code block beginning for each possible placement sweeps a great
deal under the rug. First off, there axe only four types of entries that need to be
considered: (1) vertex u, is represented by a 1 of M not used for a previous vertex
of G, (2) V{ is represented by a 1 in a column appended to M, (3) u, is represented
44
by a row appended to M, or (4) V{ is in both a new row and a new column.
We will use the graph C% with vertices a, 6, c, d, e, /, as an example. As the a1
ogrithm proceeds, each vertex is consecutively assigned to a 1 of the matrix M and
that 1 is given the vertex label. Suppose the algorithm has partially constructed a
matrix
M =
a b
Then, the possible positions for vertex c are noted ci and c2 in
M' =
a b Xi
X2 C\ c2
It is not possible to place c at positions xi or x2 without violating the connection
rules of Cq. Also notice that if the position marked as c2 is used, then both ci and
xi must be made 1.
Often, only a few placements of a vertex ut are possible due to these connection
constraints. Whenever a new vertex is placed, there may be several entries of M'
which must be fixed as either 1 or 0, but some entries can be chosen as either 1
or 0. This must be done carefully, because one such entry may force the value of
another entry once the first value is fixed. For example, using the same 6cycle,
a 6 0 1
0 c d *
M' =
0 0 e 1
1 * 1 /
and could be either 0
The entries marked as and could be either 0 or 1, but they cannot be simul
taneously 1.
45
In Lemma 4.1 through Lemma 4.16 M is a (0, l)matrix and G& = Gb{M).
The letters a, 6,... represent the ls of the matrix corresponding to vertices of
the graph. The additional ls are needed to connect these vertices. All Lemmas
are phrased in terms of G&, but similar Lemmas for G, could be produced by
complementing the graphs. Here, define contains to mean contains as a submatrix
in any possible permutation.
In the first two Lemmas, the forbidden submatrices are exactly the same
because P4 is self complementary. However, the order of the vertices is different.
The same is true of C5 and C5.
Lemma 4.1 Gb contains P4 as an induced subgraph if and only if M contains
one of the following submatrices:
Mi = a 0 6 c 11 S a 6 1 0 1 c , m3 = a 6 0
0 d 0 0 d 0 c d
Lemma 4.2 Gb contains P4 as an induced subgraph if and only if M contains
one of the following submatrices:
Mx =
a 0 c
d b 0
1 a d ale
11 0 b II 0 6 0
1 O 1 1 d 0
46
Lemma 4.3 Gb contains P5 as an induced subgraph if and only if M contains
one of the following submatrices:
a 0 1 a 0 0 a 6 1 1
b c 1 b c 1 0 1 c 1
Mi = 0 1 d II s 0 1 d , m3 = 0 0 1 d
0 0 e 0 0 e 0 0 0 e
a 6 0 0 a 6 0 0 a 6 0
M4 = 0 c 1 0 , Ms = 0 c 1 0 , Me = 0 c d
11 d e 0 1 d e 1 0 e
Mr =
a b 0
0 c d
0 0 e
Lemma 4.4 Gb contains P5 as an induced subgraph if and only if M contains
the submatrix:
aid
Mi= 0 6 1
c e 0
Lemma 4.5 Gb contains C4 as an induced subgraph if and only if M contains the
submatrix:
a b 1
Mi =
0 1c
1 0 d
47
Lemma 4.6 G& contains as an induced subgraph if and only if M contains
one of the following submatrices:
Mi =
a 1
0 b
c 1
0 d
a 1 1 ale r
II ST 0 6 d II 0 6 0 II
c 1 1 o o, o 
a 1 c 1
0 6 0 d
Mg =
a 0 a 0
a 0 c a 0 c
0 6 II Â£ 0 6 II Â£ 0 6 1 II * 0 6 1
c 0 c 0 1 d 1 0
1 d 0 d
a 0 c 1 n o o 1 i n o o 1
II S 0 6 1 II O 0 6 0 II 0 6 0
1 d 0 1 d 1 1 d 0
1 R O O 1 II 5? a 0 c 0
O O o 1 d 0 6 0 d
a 0 c
M12 = 0 6 0? M13 =
0 d 0
Lemma 4.7 Gb contains C5 as an induced subgraph if and only if M contains
one of the following submatrices:
My =
a 1 0 0 1
16 10 0
0 1 c 1 0
0 0 1 d 1
1 0 0 1 e
a 6 1 1 a 6 0
II 0 1 c 0 ii 5? 0 c 1
0 0 d 1 1 1 d
1 0 1 e e 0 1
48
m4
a 6 0 1
0 c d 1
1 0 1 e
Lemma 4.8 G& contains C5 as an induced subgraph if and only if M contains
one of the following submatrices:
Mi =
a 1 c 1
0 6 0 1
1 d 0 0
0 1 1 e
, m2 =
a 0 1 1 0
0 6 0 1 1
1 0 c 0 1
1 1 0 d 0
0 1 1 0 e
M3
a 0 1
0 6 1
c e 0
1 1 d
a 0 c 1
M4 = 0 6 e 1
1 1 0 d
Lemma 4.9 (S'& contains C& as an induced subgraph if and only if M contains
one of the following submatrices:
a 6 1 1 1 a 6 1 1 1 a 6 1 1 1
0 1 c 1 1 0 1 c 1 0 0 1 c 0 0
0 0 1 d 0 , M2 = 0 0 1 d 0 11 Â£ 0 0 d 1 0
0 0 0 e 1 0 0 0 e 1 0 0 1 e 1
1 0 0 1 / 1 0 0 1 / 1 0 1 1 /_
49
a b 0 0 a b 0 1 
0 c 1 0 0 c d 1
II 1 1 d e , m5 = 0 0 1 e II Â£
__ 1 0 0 1 1 0 0 / 
a b 0
0 c d
f 0 e
Lemma 4.10 Gb contains C& as an induced subgraph if and only if M contains
one of the following submatrices:
a 1 1 d 1 a 1 c 1
a 1 1 d 1
0 b 1 1 1 0 6 1 1 / 0 6 0 1
1 0 c 0 1 , m2 = , M3 = L 1 0 d
1 0 c 0 1
1 1 1 0 e 1 1 e 0 0 1 e 1 0
0 1 / 1 0 0 1 1 /
a 1 c e a 0 c 1
M4 = 0 b 0 1 II Â£ 0 b 1 /
1 d 0 0 1 1 0 d
0 f 1 0 1 1 e 0
Lemma 4.11 Gb contains Cr as an induced subgraph if and only if M contains
one of the following submatrices:
a 1 1 1 0 a 1 c e 1 a 0 c 1 1
0 b 1 1 1 0 b 0 1 1 0 b 1 1 9
c 1 0 e 1 II 1 d 0 0 1 W II 1 1 0 d 1
1 1 d 1 9 1 f 1 0 0 1 1 e 0 1
1 / 1 0 0 0 1 1 1 9 1 1 1 / 0
50
Lemma 4.12 G& contains 3 as an induced subgraph if and only if M contains
one of the following submatrices:
Mi =
a 1 1 1
16 10
1 0 c 1
110 d
M2
a b 1
c 0 0
1 0 d
Lemma 4.13 Gb contains K 1,3 as an induced subgraph if and only if M contains
one of the following submatrices:
a 0
Mi =
M4 =
1 6
1 c
1 d
a 1
0 6
0 c
0 d
, m2 =
, M5 =
a 0 0
16c
1 d 1
a 1 1
0 6c
0 d 1
, M3 =
a 0 0 0
1 6 c d
, m6 =
a 1 1 1
0 6 c d
a 0 a 0 a 0
0 6 0 6 0 6
II 1 c , Ms  0 c Â§ II 0 c
1 c/ 1 0
a 0 1 r
a 0 1 1
Mu 0 6 c 1 m12 0 6c d
0 d 1 *
, M10 =
a 0 1
0 6c
1 d 1
a 0 0
0 6c
1 d 1
51
a 0 0
M14 =
0 6c
0 d 1
M15 =
a 0 0 1
0 6 c d
, M16 =
a 0 0 0
0 6 c d
Lemma 4.14 Gb contains a 3sun as an induced subgraph if and only if M con
tains one of the following submatrices:
=
a 1 0 / a 6 1 d
a d 0 1
b 1 e 0 II 5S b 1 e 0 ii * 1 1 c 0
1 c 1 1 c 0 1 / 0 e 1 0
d 0 0 0 1 0 1 0
a b c
d 1 0
M4 =
0 e 1
1 0 /
Lemma 4.15 Gb contains the complement of a 3sun as an induced subgraph if
and only if M contains one of the following submatrices:
 a 1 1 1 e a 1 1 1 0
a 1 0 0 0 6 1 1 0 0 6 1 0 1
0 6 1 1
Mi = 1 0 c d , m2 = 0 0 c 1 0 n s 0 0 c 0 0
0 0 1 d 1 0 0 d 1 1
e 1 0 f
0 1 0 f 1 1 1 1 e /
52
ce
p 3 oo
/ 0 9 0
3 0 0
= stw
1 P 0 0
0 3 o 0
/ I 9 0
3 1 0
= un
1
3 0 0
= 1
0 9 0
i o o 1
'311 1
1 p 0 0
o o o 0 II
0 1 9 0
1 1 0 V
/ p t o
o 3 o o
10 9 0
3 10
= cw
3 P 0 1 1 p 1 0 0
0 3 0 1 II 0 1 3 0 1
/ 1 9 0 / 1 1 9 0
1 0 0 V 1 3 0 0 V
= 8/v
/ 0 T 3
P 3 0 I
I I 9 0
0 0 0
TOT3
p 1 / 1
1301
0 19 0
0 0 0
=
__ 2
/V
10/3
p 3 T 1
0 0 9 0
0 0 0
 1 1 0 1 0 / 1 1 1 0
3 1 0 0 1 1 1 p 0 0
II as 1 P 3 1 1 = SW 0 0 3 0 0
1 0 0 9 0 1 0 1 9 0
 1 0 0 0 V 1 3 1 1 V
= *W
Lemma 4.16 Gb contains a diamond as an induced subgraph if and only if M
contains one of the following submatrices:
Mi =
a c
b 1
d 0
, m2
a b c
d 1 0
These Lemmas can now be used to show that requiring G,(M) to be chordal
restricts the form of M severely.
Theorem 4.2 The following are equivalent:
(1) Gi is chordal,
(2) Gi contains no C4,
(3) M contains none of the matrices in Lemma 46,
(4) Gb contains no C4, Cs, or 2Ki,
(5) Gb is a split graph,
(6) Gi is a split graph, and
(7) Gb and Gi are both chordal.
Proof: Suppose Gi is chordal, then G, contains no C4. If Gt contains no C4,
then M contains none of the 14 matrices in Lemma 4.6. Clearly Gb does not
contain 2/G since it is the complement of G,, and G, contains no C4. Also, M
does not contain the matrix M7 of Lemma 4.6 and thus Gj contains no G4 and no
C5 by Lemma 4.5. Thus by Theorem 2.13, Gb is a split graph. And by the same
Theorem, Gi is a split graph and Gb and G, are both chordal. The last statement
contains G, is chordal. O
Theorem 4.3 If Gb (orGi) contains no P4 then
(1) M contains none of the matrices in Lemma 41,
54
(2) Gb is unit interval,
(3) Gi is a comparability graph, and
(4) Gi is weakly chordal.
Proof: The graph G, has no P4 if and only if the graph Gb has no P4, since
P4 is a self complementary graph. The first statement is a direct application of
the Lemma. If M contains none of the matrices in Lemma 4.1, then Gb does not
contain a C4 by Lemma 4.5. Since Gb contains no P4, it is clear that neither Gj
nor Gi contain a chordless cycle of length greater than 5. So, Gb and G, are both
weakly chordal, and since Gb contains no C4, it is chordal. No P4 will eliminate,
as induced subgraphs, two of the graphs in Figure 2.1. The remaining graph, the
3sun, is eliminated by noting that each of the matrices of Lemma 4.14 contain one
of the matrices in Lemma 4.1. The same is true of the matrices of Lemma 4.12.
Therefore, by Theorem 2.10 we have Gb is interval and G, is a comparability graph.
In fact by Theorem 2.11 we have Gb is unit interval.
Theorem 4.4 IfGb contains no C4 then Gi contains no chordless cycle of length
5 or greater.
Proof: If Gb contains no C4, then M cannot contain the matrix of Lemma 4.5 as
a submatrix. Thus by Lemma 4.8, G, cannot contain a G5, and by Lemma 4.4, G,
cannot contain a P5. Since G, cannot contain a P5, it cannot contain any chordless
cycle of length 6 or greater.
Theorem 4.5 IfGb is chordal, then Gb is strongly chordal.
Proof: If Gb is chordal, then it can contain no C4. Thus, M cannot contain the
matrix Mi of Lemma 4.5. Since each of the matrices of Lemma 4.14 contain Mi
as a submatrix, M cannot contain a 3sun as an induced subgraph. Therefore, Gb
55
is strongly chordal.
Because it provides another forbidden submatrix theorem and some insight,
the following is included here. From the definition of the block cover graph, it is
clear that if M contains no blocks which axe not entirely rows or entirely columns,
then Gb{M) = L(B(M)) where L(G) is the line graph of G and B(M) is the
bipartite graph whose reduced adjacency matrix is M. Since the line graph of a
bipartite graph is always perfect (see [6]), we have the following theorem.
Theorem 4.6 Let M be a (0,1)matrix that does not contain
1 1
1 1
as a submatrix. Then M is gfactor perfect.
In fact, in the case where M contains no 2 x 2 block of ls, finding the isolation
number of M is equivalent to finding the largest matching in B{M).
4.2 Simple Bounds
In this section more definitions are needed. Each definition has a direct inter
pretation as a common graph invariant when applied to the block cover graph or
the isolation graph. So, ail that is really going on here is a translation of notation.
For a (0, l)matrix M:
(1) \M\ is the number of ones in M,
(2) bj(M) is the size of the largest block of ones in M,
(3) bs(M) is the size of the smallest covering of M with sets of isolated ones,
(4) Sb{mij) is the degree of the vertex corresponding to m,j = 1 in the block
cover graph of M,
56
(5) 8i{mij) is the degree of the vertex corresponding to rriij = 1 in the isolation
graph of M,
(6) Ab(M) is the maximum of 8b(rriij) taken over ail ones of M,
(7) Ai{M) is the maximum of Si(rriij) taken over ail ones of M,
(8) eb(M) is the number of edges in the block cover graph of M, and
(9) e,(M) is the number of edges in the isolation graph of M.
These definitions axe applied to the following matrices:
1 1 1 1 0 0 1 1 1 1 0 0
1 1 1 0 1 0 1 1 1 1 0 0
1 1 1 0 0 1 , and M2 = 0 0 1 1 0 0
1 0 0 0 0 0 0 0 1 1 0 0
0 1 0 0 0 0 0 0 1 1 1 1
0 0 1 0 0 0 0 0 1 1 1 1
In Mi: br(Mi) = 6, bi{M) = 6, \MX\ = 15, bj{Mx) = 9, bs{Mx) = 9, 8b(Mx)
{10,3} with 9 vertices of degree 10, 8{{MX) 6 {4,11} with 9 vertices of degree 4,
Ab(Mx) = 10, A,(MO = 11, eb{Mx) = 54, and e,(M0 = 51.
In M2: 6r(M2) = 3, bi(M) = 3, M2 = 20, bj{M2) = 12, bs(M2) = 12,
8b(M2) {7,15,11} with 8 vertices of degree 7 and 8 of degree 15, d,(M2)
{12,4,8} with 8 vertices of degree 12 and 8 of degree 4, A&(M2) = 15, A,(M2) =
12, eb(M2) = 110, and e,(M2) = 80.
Notice that the numbers eb, e,, 8b, d,, A&, and A, could all be defined without
reference to the graphs. By Theorem 3.1, and repeated here for easy reference:
(1) Gi(M) is the complement of Gb{M),
(2) bi(M) = u>(Gi(M)) = a(Gb(M)),
57
(3) bj(M) = a{Gi{M)) = w(Gb(M)),
(4) br(M) = X(Gi(M)) = k(Gb(M)), and
(5) bs(M) = x(G6(M)) = k(Gi(M)).
Also note, bj(M) < bs(M) with equality whenever Gb(M) is weakly xperfect.
Since our goal is to determine the numbers bi(M) and br(M), results will usually
be stated with respect to them.
4.2.1 Isolation Number
The following graph theoretic theorems are be used to bound the boolean isol
ation number. The example from the previous section will be used to demonstrate
the new bounds.
Theorem 4.7 (Meyer 1972, c.f. [7]) Let G = (V, E) be a simple graph of order
n with vertices ui,V2.,vn such that
1 < Â£(*>i) < S{v2) < < Â£(un).
If for an integer p, 2 < p < n,
S(vn) + + J(unp+2)
then each independent set with fewer thanp vertices is contained in an independent
set with p vertices.
Corollary 4.1 (Berge 1960, c.f. [7]) In a simple graph G of order n with max
imum degree A(G),
a(G)>
n
A (G) +1
The following corollary easily follows, but because of the characteristics of the
graph Gb it is often not very tight.
58
Corollary 4.2 Let M be a (0,1) matrix. Then,
bi(M) >
m '
Ab(M) + l *
Returning to the example matrices, we have bi(Mi) > [15/11] =2 when in
fact bi(Mi) = 6 and > [20/16] = 2 where 6i(M2) = 3.
Turans theorem and its corollaries give additional bounds on the independ
ence number of a graph that can also be used to bound the boolean isolation
number.
Theorem 4.8 (Turdn 1941, c.f. [7]) If n and k are two integers, n > k > 0, put
9 =
+1;
let r be an integer such that:
n = k(q 1) + r, 0 < r < k.
Let Gn,k be the simple graph that consists of k disjoint cliques, of which r have q
vertices and k r have q 1. Then, every graph G with n vertices and oc(G) < k
that has the minimum possible number of edges is isomorphic to Gn,k
Corollary 4.3 (c.f. [7]) If G is a simple graph with n vertices and m edges, then
,2
q(G)>
n
2m + n
Equality holds if and only if the connected components of G are cliques with the
same cardinality.
Corollary 4.4 (c.f. [7]) If G is a simple graph with n vertices and m edges, then
"2n m~
59
Equality holds if and only if each connected component of G is either a 2clique
or a 3clique.
Now we can restate the last two corollaries in matrix theoretic terms. Each
new corollary will be used immediately on the example matrices.
Corollary 4.5 Let M be a (0,1 )matrix. Then,
\M\2
bi(M) >
2 eb(M) + \M\
For the examples, bi(Mi) > (225/123] = 2 where bi(Mi) = 6 and bi(M2) >
[400/240] = 2 where bi(M2) = 3.
Corollary 4.6 Let M be a (0,1)matrix. Then,
bi(M) >
2\M\eb(M)
3
For the examples, bi(Mi) > [(30 54)/3] = 8 where 6i{Mf) = 6 and
bi{M2) > [(40 80)/3] = 13 where bi(M2) = 3.
4.2.2 Boolean Rank
As in the previous section, the following theorems will provide us with new
bounds and relationships among (0, l)matrix invariants. In this case, the bounds
are usually phrased as boolean rank results. Some of these formulas involve in
variants that may be as difficult to compute as br(M).
Theorem 4.9 (c.f. [7]) If G is a graph of order n, then
(1) x(G)q(G) > n, and
(2) x(G) + a(G)
Corollary 4.7 Let M be a if), \)matrix. Then
(1) br(M)bj(M) > \M\, and
60
(&) br(M) + bj(M) < \M\ + 1.
Part (1) of the corollary could be rephrased as br(M) > \M\ /bj(M) which
[25]. For the examples matrices, we get br(Mi) > [15/9] =2 where br(Mi) = 6
and br(M2) > [20/12] = 2 where br(M2) = 3. Part (2) of the corollary gives
br(Mi) < 15 9 = 6 and br(M2) < 20 12 = 8.
The following theorem and its corollary provide more bounds. Again, these
bounds axe typically not tight.
Theorem 4.10 (Gaddum and Nordhaus 1960, c.f. [7]) LetG be the complement
ary graph of a simple graph G. Then, x(^) + x(^) < n + 1.
Corollary 4.8 (c.f. [7]) If G is the complementary graph of a simple graph G,
Here are the corollaries in matrix theoretic terms.
Corollary 4.9 Let M be a (0,1 )matrix. Then, br(M) + bs(M) < \M\ + 1.
For the example matrices, br(Mi) < 15 9 = 6 and br(M2) < 20 12. In this
case the values are the same as in Corollary 4.7 because both matrices are weakly
factor perfect.
Corollary 4.10 Let M be a (0, l)mafn'x. Then,
Here, br(Mi) < 7 and br(M2) < 9. As expected this corollary is weaker. Co
was discovered without appealing to graph theory by Gregory and Pullman in
then
rollary 4.9 is never weaker because it is derived more directly from Theorem 4.10.
61
The next series of theorems and corollaries require only matrix invariants that
axe easily calculated from M. As a result the bounds here are weaker yet.
Theorem 4.11 (c.f. [7]) IfG is a simple graph with n vertices and m edges, then
,2
X(G)>
n
ri2 2m
Corollary 4.11 Let M be a (0,1 )matrix. Then,
\M\2
br(M) >
Af f 2e,(M)
For the examples, br(Mi) > 2 and br{Mz) > 2.
Theorem 4.12 (c.f. [5]) IfG is a graph with n vertices and m edges, then
X(G) < 1 +
(2m(n 1)
n
Corollary 4.12 Let M be a (0,l)matrix. Then,
br(M) < 1 +
2e,(M)(M 1)
\
\M\
For the examples, br(Ml) < 6 and 6r(A/2) < 8.
Theorem 4.13 (c.f. [5]) If G is a connected graph that is neither an odd cycle
nor a complete graph, then x(C?) < A(G).
Corollary 4.13 Let M be a (0,1 )matrix. If M is not a (sub)permutation matrix,
then
br(M) < Ai(G).
For the examples, br(Mi) < 11 and 6r(M2) < 12.
As we have seen, upper bounds based on bounds for the chromatic number of
the isolation graph are typically quite bad. Additional results that provide such
62
an upper bound axe given by the following theorems. Each requires properties of a
graph which are not elementary, but which can be easily calculated on a computer.
As before, each theorem is useful when G = G,(M) so that br(M) = x(G).
Theorem 4.14 (Hanlin 1967, Szekeres and Wilf 1968, c.f [5]) For every graph
G,
X(G)
where H C G means H is an induced subgraph of G, and 8(H) is the smallest
degree of any node in H.
Theorem 4.15 (Wilf 1967, Hoffman 1970, c.f. [5]) Let G be a graph and let
Ai > > A be the eigenvalues of the adjacency matrix of G. Then,
An
Theorem 4.16 (Welsh and Powell 1967, [5]) Let G be a graph with vertices
vi,...,vn such that
8(vi) > 8(v2) > > 8(vn).
Then,
x(G) < max{min{z,^(ut) + 1}}.
63
5. Totally Balanced Matrices
In this chapter, totally balanced matrices are defined and shown to be factor
perfect. In a certain sense, matrices in this class behave like chordal graphs. An
elimination ordering for totally balanced matrices was first defined by Golumbic
in [22]. Using this ordering, Golumbic showed it was possible to perform Gaussian
elimination with no fillin on (almost) any matrix with a totally balanced pattern
of nonzeros. A more refined elimination order was defined by Johnson and Miller
in [33] in the study of the possible real ranks of matrices with a totally balanced
zero/nonzero pattern. The second elimination ordering, rediscovered by the cur
rent author will be used to prove several results about boolean rank and sets of
isolated ones.
The results of both Golumbic, and Johnson and Miller, shed new light on the
boolean decomposition problem. Both authors worked in the context of bipartite
graphs, but we will begin with a matrix theoretic definition. The definitions here
are a combination of [43] and [8].
64
5.1 Definition and Basics
A (0, l)matrix M has a cycle of length k if it contains for k > 3 a k x k
submatrix
10 0 ....... 0 1
11 0 ....... 0 0
0 1 1 ....... 0 0
Bk =
0
: i o
o ............. Oil
That is, M has a cycle if it contains the nodeedge incidence matrix of a cycle as a
submatrix. A (0, l)matrix is said to be balanced if it has no odd length cycles.
A (0, l)matrix is said to be totally balanced if it has no cycles.
The following are clear from the definition:
(1) A totally balanced matrix is also balanced,
(2) Every submatrix of a (totally) balanced matrix is also (totally) balanced,
and
(3) The transpose of a (totally) balanced matrix is also (totally) balanced.
Balanced and totally balanced matrices have many interesting properties,
particularly in the area of integer programming (see [43]). For this discussion,
the most important properties of totally balanced matrices are provided by the
following definitions, lemmas and theorems.
65
Given two ndimensional vectors, define reverse lexicographic order, de
noted with < as follows:
(t*i, r2, , ^*n) ^2? r n)
if the largest index A: such that ^ Sk satisfies rjt < Sk
Lemma 5.1 (c.f. [43]) In any (0,1) matrix, the rows and columns can be sim
ultaneously arranged in reverse lexicographic order. Furthermore, this reordering
can be accomplished in polynomial time.
Proof: The proof is algorithmic. The idea behind the algorithm is that for any
column k lexicographically greater than a column l the rows of k containing only
ones (only zeros) can be permuted freely without disturbing the lexicographic
relationship between columns k and l. This property is exploited at each step in
the algorithm which works by finding the greatest column and permuting it into
position, permuting the rows into lexicographic order in the columns considered
so far, then finding the next greatest column. This process is repeated until all of
the columns have been checked. Since the rows axe kept ordered at each step the
result is a matrix lexicographically ordered in both its rows and columns.
First, make the following definition. For any partition Mi,M2,..., of the
rows of A, let dj Z\_ be given by
Step 0: Let t = 1, k = 1 and Mi = M = {1,..., m} .
Step 1: Find dj for j = k,...,n. Let p be the index of the lexicographically
largest dj. Exchange columns k and p.
66
Step 2: For each existing partition Ma divide it into M's = {z 6 Ma : dip 1}
and M" = {i Ma : a,p = 0}. Permute the rows of M so that M' occurs
before M".
Step 3: If k = n, stop the matrix is in reverse lexicographic order. Otherwise,
update t and set k = k + 1 and goto Step 1.
Since k is increased by one each time, there axe at most n iterations of the
algorithm. At each step no more than nm comparisons must be made to find
the largest dj and all the work permuting rows can be bounded by a constant.
Therefore, the algorithm runs in 0(n2m) time.
As an example of the algorithm, consider the matrix
Ao
Mi
1 2 3 4 5 6 7 r ]
1 3
0 1 0 0 0 0 1 1 3
0 0 1 I 1 0 0 2 4
1 0 1 0 1 1 1 3 > Mi and Do = 2
1 0 1 0 0 1 1 4 3
0 1 1 0 1 0 0 5 2
1 1 0 1 0 0 0 6
* 3
d\
d2
d$
d
ds
ds
dy
67
Ai
3 2 1 4 5 6 7
1 0 0 1 1 0 0
1 0 1 0 1 1 1
1 0 1 0 0 1 1
1 1 0 0 1 0 0
0 1 1 1 0 0 0
0 1 0 0 0 0 1
Ao
2
3
4
5
6
1
Mi
and Di =
Mi
A3 =
3 5 1 4 2 6 7
1 1 0 1 0 0 0
1 1 1 0 0 1 1
1 1 0 0 1 0 0
1 0 1 0 0 1 1
0 0 1 1 1 0 0
0 0 0 0 1 0 1
3 5 1 4 2 6 7
1 1 1 0 0 1 1 3
1 1 0 1 0 0 0 2
1 1 0 0 1 0 0 5
1 0 1 0 0 1 1 4
0 0 1 1 1 0 0 6
0 0 0 0 1 0 1 1
2
3
5
4
6
1
Mi
M2
* M3
and D2 =
MiM2
1 2
2 1
1 1
3 0
2 0
2 1
M1M2M3
1 1 1
1 0 1
1 0 2
1 1 0
1 1 1
d2
dz
d4
ds
dÂ§
d7
dz
cLi
d$
de
dy
> Mi
>M2
Mz
M4
and Dz =
MiM2M3M4M5
0 1 0 1 0 d4
0 1 0 1 1 dz
1 0 1 0 0 ds
1 0 1 0 1 dT
1 }m5
68
i
I
I
I
I
i
j
i
i
i
i
l
I
I
i
I
j

i
3 5 1 7 2 6 4
1 1 1 1 0 1 1 3 Mi
1 1 0 0 0 0 1 2  m2
1 1 0 0 1 0 0 5 *
1 0 1 1 0 1 0 4) >m3
0 0 1 0 1 0 1 6) m4
0 0 0 1 1 1 0 i] M5
3 5 1 7 6 2 4
1 1 1 1 1 0 0 3 1 Mt
1 1 0 0 0 0 1 J 2 >m2
1 1 0 0 0 1 0 5 4
1 0 1 1 1 0 0 *] >m3
0 0 1 0 0 1 1 6) Mt
0 0 0 1 1 1 0 m5
and D4
and D5
M1M2M3M4M5
0 1 0 1 1 d$
1 0 1 0 1 d6
1 0 1 0 0 dr
M{M2M3M4M5
0 10 11 d6
0 10 10 d7
I
69
3 5 1 7 6 2 4
1 1 1 1 1 0 1 o
1 1 0 0 0 1 0
1 1 0 0 0 0 1
1 0 1 1 1 0 0
0 0 1 0 0 1 1
1 o 0 0 1 1 1 0
3
*; \m2
2 \m3
\m4
6 \m5
\m6
Lemma 5.2 (c.f. [8]) Let M be a (0,1 )matrix with its rows and columns ar
ranged in reverse lexicographic order. If M contains a submatrix equal to

mij mu = 1 1
mkj mki 1 0
with i < k and j < l, thm M has a cycle.
Theorem 5.1 (Hoffman, Sakarovitch and Kolen 1985, [32]) Let M be a (0,1)
matrix and let N be as defined in the previous Lemma. Then, the following are
equivalent.
(1) The matrix M with its rows and columns arranged in reverse lexicographic
order contains no submatrix N.
(2) It is possible to place the rows and columns of M in an order such that M
contains no submatrix N.
(3) The matrix M is totally balanced.
Theorem 5.2 (c.f. [8]) The rows and columns of any (0,1) matrix M can be
70
arranged in reverse lexicographic order in polynomial time. Thus, it can be de
termined if a matrix is totally balanced in polynomial time.
An additional result, while not applied directly, seems of interest. It was not
originally stated in this context.
Theorem 5.3 (Lubiw 1985, [40]) The boolean product of two totally balanced
matrices is a totally balanced matrix.
5.2 Perfect Ones Elimination
In his book [22], Golumbic gives an algorithm for finding vertex clique covers
of chordal graphs in polynomial time. Later in this section this algorithm will be
reapplied in the context of block covers of totally balanced matrices.
5.2.1 Vertex Clique Covers in Chordal Graphs
This section describes an algorithm for finding a minimal vertex clique cover
in a chordal graph. This algorithm will be used as a model for what follows.
Theorem 5.4 (Fulkerson and Gross 1965, [19]) Let G be a chordal graph, and
let a be a perfect elimination scheme for G. Every maximal clique of G is of the
form {u} U Xv where
Xv = {i6 Adj(v)\
Proof: By the definition of a, each [r}Ul is complete. Let w be the first vertex
in cr contained in an arbitrary maximal clique A; then A = {to} U Xw.
Corollary 5.1 (Fulkerson and Gross 1965, [19]) A chordal graph on n vertices
has at most n maximal cliques, with equality if and only the graph has no edges.
Consider the graph in Figure 5.1 with its vertices labeled in a perfect elimin
ation order. The sets Xv are Xi = {3,4}, X2 = {3,4}, X3 = {4}, X4 = {5},
71
1
6
9
Figure 5.1: Example of a chordal graph with a perfect elimination scheme
X5 = {6,7,11}, X6 = {7,11}, X7 = {11}, X8 = {9,10}, X9 = {10,11},
.Xio = {11}, and Xu 0.
The following is due to Gavril [20]. Let a be a perfect elimination scheme
for a graph G = (V, E). Inductively define a sequence of vertices J/i, j/2, , J/t as
follows: t/i =
Xyi U Xm U U Xyi_t. Notice that all vertices after yt in a are in Xyi U U Xyt.
So V = {yi,..., yt} U Xm U U Xyt.
Theorem 5.5 (Gavril 1972, [20]) The set {yi,y2, y} is a maximum inde
pendent set of G and the collection of sets Y,j = {y,} U Xyi for i = 1,2, ...,f
comprises a minimum clique cover of G.
Proof: If (yy, y,) G E for j < i, then y, G XVj. This is a contradiction and
thus the set {yi, y2,.. , yt} is independent and t < a(G). Each of the sets Yi is
a clique. So, {VI,..., Yt} is a vertex clique cover of size t and k(G) < t. Since
t < a(G) < k(G) < t, and we have produced a maximum independent set and a
minimum clique cover.
This theorem can easily be turned into an algorithm for finding a minimal
vertex clique cover. The algorithm would proceed through the elimination sequence
in the manner described above until we are left with Y\ = {1,3,4}, Y2 = {2,3,4},
Y3 = {5,6,7,11}, and finally V4 = {8,9,10} in our example.
72
5.2.2 Definition and Existence
A 1 of a (0, l)matrix M is simplicial if it is contained in a unique maximal
clique. A 1 is removed from M by replacing it with a 0. A perfect ones
elimination scheme is defined analogously to a perfect vertex elimination scheme.
As an example, consider the matrix
1 0 0 1 a 0 0 b
0 1 0 1 0 c 0 d
0 0 1 1 0 0 e f
1 1 1 1 9 h i 3
Then a = (a, 6, c, d, e, /, g, h, i,j) is a perfect ones elimination scheme for Mo, but
(a, d,...) is not.
The following theorem is substantially similar to a series of Lemmas about
bipartite graphs in the paper [33] by Johnson and Miller. They in turn mention
that their results come from Bakonyi as an extension of Golumbic [22], but do
not give a reference. The proof is the current authors and is phrased in matrix
terminology rather than bipartite graph terminology.
Theorem 5.6 Let M be a (0,1) matrix. Then there exists a perfect ones elimin
ation scheme for M if and only if M is totally balanced.
Proof: First suppose M is not totally balanced. Then by Theorem 5.1, M
contains a submatrix Bk for k > 3 such that every 1 is in at least two maximal
blocks. Thus, no 1 of this submatrix can be removed during any perfect ones
elimination scheme. So, no such scheme can exist.
Now suppose M is totally balanced. We will proceed by induction on the
number of ls in M. If M contains only one 1, then it is obvious that a perfect
73
ones elimination scheme exists. Suppose that M has k + 1 ls and its rows and
columns are arranged in reverse lexicographic order.
Let rriij be the left most 1 in the first nonzero row of M. By way of contradic
tion, suppose rriij is contained in two (or more) different maximal blocks Ki and
K2. Since K\ and K2 are different maximal blocks we may assume without loss of
generality that there exists mu = 1 in the block Ki and mkj = 1 in the block K2
so that mu = 0. But then,
"7
rriij mu 1 1
mkj mki 1 0
with i < k and j < l since mtJ is the top left most 1 of M. This is a contradiction
of Theorem 5.1, since M was assumed to be totally balanced. Therefore, m,y is
contained in at most one maximal block.
If rriij is removed from M producing M', no new submatrix N can appear
and M' is totally balanced. Since M' contains k ones, there exists a perfect ones
elimination scheme for M' by induction. When mtJ is prepended to this scheme,
we have a perfect ones elimination scheme for M.
This proof suggests the following method of producing a perfect ones elimin
ation scheme for a totally balanced matrix M. First, put the rows and columns of
M into reverse lexicographic order. Then, list the ls of M from left to right and
from top to bottom. That is, in the same order as a page is read in English.
Corollary 5.2 If M is totally balanced, then a perfect ones elimination scheme
for M can be found in polynomial time.
74
5.2.3 Decomposition Algorithm
Theorem 5.7 Let M be a totally balanced (0, l)matrix with a perfect ones elim
ination scheme a. Then, every maximal block of M is of the form {v}uX where
Xv = {x\x is a 1 of M in a block with v and cr1(u) <
Proof: By the definition of a, each {u} U Xv a block. Let w be the first one in a
contained in an arbitrary maximal block A; then A = {u;} U Xw.
For the example matrix Mq in the previous section, Xa = {b,g,i}, Xb =
{<*,/,j}, X, = {
Xh = {i, j}, Xi = {>}, and Xj 0.
Corollary 5.3 A totally balanced matrix M with n ones has at most n maximal
blocks, with equality if and only if M is a (sub)permutation matrix.
Theorem 5.5 can be used as a model. Let a be a perfect ones elimination
scheme for (0, l)matrix M. Inductively define a sequence of ls ,J/t as
follows: yi = cr(l); y, is the first 1 in a which follows t/,_i and which is not in
Xyi U Xy^ U U Xyi_t. Again notice that all ls after yt in a are in Xyi U UXyt.
So, all ls in M are included in {t/i,..., yt} U Xyi U U Xyt.
Theorem 5.8 The set {yi, y?,..., yt} is a maximum set of isolated ones and the
collection of sets Y{ = {y,} U Xyi for i = 1,2, ...,t comprises a minimum block
cover of M.
Proof: If yj and y, are in a block for j < i, then yt 6 XV]. This is a contradiction
and thus the set {yi, j/2, , yt} is a set of isolated ls and t < bi(M). Each of the
sets Yi is a block. So, {Yi,..., Yt} is a block cover of size t and br(M) < t. Since
t < bi(G) < br(G) < t, and we have produced a maximum independent set and a
minimum clique cover.
75
Continuing with the most recent example, and preceding in the same manner
used to find vertex clique covers of graphs, we are left with Vi = {a,b,g,j},
Y2 = {c,d,h,j}, and V3 = {e, /, i,j}. This gives the decomposition:
1 0 0 1 1 0 1 0 
1 0 0 1
0 1 0 1 0 1 0 0 1 0 1
0 0 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1
Corollary 5.4 Let M be a (0,1 )matrix. If M is totally balanced, then M is
factor perfect.
Notice also that Gb(Mo) contains the chordless four cycle i, h, d, f and G,(Mq)
contains the chordless four cycle g, d, i, c. It is also possible to find longer cycles.
Consider the totally balanced matrix
1 0 0 Xi
0 0 1 x2
0 1 X3 1
*5 X4 1 1
Here, xi,x2,... ,Â£5 is a chordless five cycle in Gb(Mi). Since G,(Mj) is the com
plement of Gb(Mi), it must also contain a chordless five cycle in a different order
on the same vertices. Thus, neither Gb{M\) nor G,(Mi) is a perfect graph and Mi
is not graphically factor perfect. In addition, Gb(Bk) is a chordless 2k cycle. So,
there exist matrices which are gfactor perfect that are not factor perfect.
5.3 Consecutive Ones Property
A (0, l)matrix M is said to have the consecutive ls property for rows
if its columns can be permuted in such a way that the ls in each row occur
76
consecutively. Such matrices are also totally balanced. To see this, suppose M is
a matrix with the consecutive ls property for rows that contains a submatrix of
the form
10 0 ....... 0 1
11 0 ....... 0 0
0 1 1 ....... 0 0
Bk =
: o
: i o
o .............. 0 11
for some k > 3. Order the columns of M so that the 1 of each row can be arranged
consecutively. Now, delete the rows and columns of M that are not part of Bk
This leaves a permutation of Bk with the columns ordered so that the ones in each
row occur consecutively. This is clearly impossible and thus a contradiction. So, a
matrix with the consecutive ls property for rows (or columns) is totally balanced
and we have the following corollary.
Corollary 5.5 Let M be a (0,1 )matrix. If M has the consecutive 1 s property
for rows (columns), then M is factor perfect.
There is an interesting alternative description of matrices with the consecutive
ls property. From Berge [8], a polyomino P is a finite set of unit squares in the
plane arranged like a chess board with some of the squares cut out (see Figure 5.2).
A stable set in P is a choice of unit squares such that no two squares are contained
in the same maximal rectangle. Denote the size of a largest stable set with s(P). A
rectangle covering of a polyomino P is a set of contiguous rectangles formed from
77
the unit squares of P such that every square is contained in at least one rectangle.
Denote the size of the smallest such covering with r(P). Clearly s(P) < r(P).
A polyomino P is said to be semiconvex if every horizontal line of the plane
intersects P in an interval. A matrix M has the consecutive ls property for rows
if and only if the associated polyomino is semiconvex.
Semiconvex polynomials have an addition property similar to weak factor
perfection. Although bi(M) and s(P), and br(M) and r(P) have similar definition,
there values will not always be equal. These relationships will be explored after
the next theorem.
Theorem 5.9 (Gyori 1984, [8]) If P is a semiconvex polyomino, then s(P) =
r(P).
A polyomino P could be constructed from a p x q (0, l)matrix by building
a p x q chess board where a square in the ith row and jth column is included if
= 1 and excluded otherwise. In addition, any polyomino could be described
as a finite (0, l)matrix by reversing this process.
If Ri,..., Rq is a rectangular covering of a polyomino P, then the blocks in
the matrix M associated with P form a block cover of M. Thus, br(M) < r(P).
If 5 is a set of isolated ones from M, then since no two of these ones are contained
in the same block, no two of the unit squares corresponding to these ones in P is
contained in the same rectangle. So, bi(M) < s(P).
78
1
2
3
4 6
5
7
(a) Example of a general polyomino;
the numbers represent a stable set.
(b) Example of a semiconvex polyomino;
the numbers represent a stable set
Figure 5.2: Examples of polyominos
79
An example of a matrix with the consecutive ls property for rows where both
of these inequalities hold is
1 1 1
0 10
1 1 I
Here the .ls represent a stable set in the associated polyomino P. In this case,
bi(M) = br(M) = 2 and s(P) = r(P) = 3.
5.4 Comparisons with Other Results
Golumbic and Goss explore the following in [23]. Let A be a real m x n
matrix. When solving Ax = b by Gaussian elimination, a series of intermediate
forms AkX = 6* until the last Av is in a (partial) permutation matrix. At this point
Apx = bp can be solved trivially. One of the side effects of the common methods
of choosing pivots is that Afc+i can have many more nonzero elements than A*.
Each time a zero of At becomes a nonzero in A*+1 we say fillin has occured. If
A is large and sparse, fillin can lead to a great increase in the amount of space a
computer needs to store data as the elimination proceeds. A perfect Gaussian
elimination scheme for A is a sequence of pivots so that no fillin occurs at any
step of the Gaussian elimination of A.
Together with the work in the preceeding sections, the next theorem indicates
a connection between real factorization of a real matrix A with no fillin and a
boolean factorization of the zero/nonzero pattern of A. An additional definition
is needed. The Golumbic and Goss method of choosing pivots looks only at the
zero/nonzero pattern of A. A pivot chosen in this manner may become 0 during
the progression of the algorithm. Such a bad pivot depends on the values in the
80
matrix A and cannot always be avoided, but axe expected only in raxe cases. Such
a pivot is called an accidental zero.
Theorem 5.10 (Golumbic and Goss 1978, c.f. [22]) Let A be a real matrix and
M be a (0,1 )matrix with exactly the same zero/nonzero pattern as A. Then,
M is totally balanced if and only if every submatrix of A has a perfect Gaussian
elimination scheme (barring accidental zero pivots).
Johnson and Miller look at the following in [33]. A real matrix A is said to
be subordinate to a (0, l)matrix M if a,y is nonzero only where mtJ = 1. The
matrix A is called strongly subordinate if atJ is nonzero exactly where mtJ = 1.
A (0, l)matrix M has property Pjt if any rank k matrix subordinate to M can be
expressed as the sum of k matrices with real rank one.
Theorem 5.11 (Johnson and Miller 1995, [33]) A pxq (0, l)matrix M is totally
balanced if and only if M has the property Pk for each k 1,..., minp, q.
Let mr(M) be the minimum real rank among all matrices strongly subordinate
to M. The following corollary is proved in the same paper.
Corollary 5.6 (Johnson and Miller 1995, [33]) If a (0,1 )matrix M is totally
balanced, then mr(M) = br(M).
Let rr(A) denote the real rank of a matrix A. It is shown in [42] that there
is no simple inequality relationship between rr(M) and br(M) as the following
examples from the paper demonstrate. The real rank of In is n, while by 6r(/) =
s(n) log2 n. Thus for all n > 4, rr(/) > 6r(/n). On the other hand, let A be
the node edge incidence matrix of a ncycle. Then 6r(A) = n. When n is even,
An has 0 as an eigenvalue with the eigenvector [1, 1,1, 1,..., 1]T and thus
rr(An) < n 1. If n is odd, then n = 2k + 1, and the same trick can be applied
81
to the matrix
0
#2Jt+l
1
0 A2k
Thus, for all n > 4, there exists a matrix M such that rr(M) < br(M).
A second corollary, immediate from the work of Johnson and Miller, allows
a little more to be said about the relationship between rr(M) and br(M). The
converse of the following corollary is an interesting open question.
Corollary 5.7 If a (0,1 )matrix M is totally balanced, then rr(M) > br(M).
82
6. Isolation Polynomials
Isolation polynomials count the number of sets of isolated ones of various
sizes in nearly the same way rook polynomials count the number of matching of
various sizes (See [46]). In order to define these polynomials we need to extend
some definitions from (0, l)matrices to (0,1, *)matrices.
Let M be a (0,1, *)matrix. A block of M is a submatrix consisting entirely
of ls or *s. Thus, mtJ = 1 and m/m = 1 are considered to be in a block if
TTiim. {!,*} and G {1,*} The definition of isolated ones does not change.
A set S of isolated ones of M consists of a set of ls such that if m,j G S and
m/m G S then mtm = 0 or mij = 0. Notice that if M is a (0, l)matrix, then these
definitions reduce to the former definitions.
Let Sk(M) be the number of sets of isolated ones of size k in the (0,1, *)matrix
M. The isolation polynomial of M is:
OO
5(x,M) = ^sfc(M)x*.
t=0
If we choose a m,j = 1 of M and fix a size k, then each set of isolated ones of
size k either does not contain m.j or does contain mtJ. For convenience of notation,
name m,j with the label /. If a set of isolated ones S does not contain /, then the
k ls of S' must be among the entries of M not including /. If a set of isolated
ones S contains /, then the remaining k 1 ls of S cannot be in the same block
as /. Therefore we have the following relationship:
Sk(M) = Sk{M/) + Ski(MJ).
83
where Mj is the matrix M with m,j = and Mj is the matrix M with every 1 in
a block with mtJ set equal to (this includes m,y = *).
Now, summing over all k > 1 and multiplying each term by xk we get
E (m> = E *( M,)xk + f; sk,(M,)xk.
fc= l fc=i fc= l
Using the fact that so(M) = 1 for all M and reindexing the third sum we arrive
at the following general recurrence.
Theorem 6.1 Let M be any (0,1,*)matrix and f be any fixed 1 of M. Then,
S(x, M) = S{x, M/) + xS(x, Mj).
It is possible to use this equation to find S(x, M) explicitly, as in the following
example. Note that if M consists of one submatrix of q ls with every other entry
either 0 or *, then S(x, M) = 1 + qx.
1 1 0 * 1 0 * * 0
S{x, 1 1 1 ) = S(x, 1 1 1 ) + xS(x, * * 1
0 1 1 0 1 1 0 1 1
* * 0 * * 0
to II 1 1 1 ) + xS(x, * * 1
0 1 1 0 * 1
i o * 1 1 o * 1
+ x(S(x, * * ) + xS(x, * *
0 1 1 1 * o 1
84
* 0 * 0
* 1 1 ) + x5'(x, * *
0 1 1 0 1 1
+ x(l + 2x) + x((l + 2x) + x))
= (1 + 4x) + x(l + 2x) + x(l + 2x) + x(l + 3x))
= 1 + 7x + 7x2.
Let S(x, M) = ao + aix + a2x2 + + anxn then the following axe simple
observations:
(1) ao = 1,
(2) fll = M,
(3) S(x,M) is invariant under permutations and transposition of M, and
(4) For all 0 < k < /, if a/ ^ 0 then < ajt <
Applying the above, or as a consequence of the next theorem:
S(x,In)
L
k=0
X
k
Theorem 6.2 Let P and Q be (0,1, *) matrices and let
M =
P 0
0 Q
Then, S(x, M) = S(x, P)5(x, Q).
Proof: Let m* be the coefficient of xk in S(x, M) and define pjt and qt similarly.
Since mjt coimts the number of sets of isolated ones of size k from M, consider
how such a set could be formed. Some of the ls, say p of them must come from
P and the remaining q must come from Q. That is, p + q = k with p > 0 and
85
q > 0. Since the entire set of A: ls forms a set of isolated ones, the two subsets
must also be sets of isolated ones. Additionally, it is clear that the union of any
set of p isolated ones from P and q isolated ones from Q is a set of isolated ones
in M. Thus, rrik is the number of unique ways to choose sets of isolated ones from
P and Q with a union of size k. So,
i=0
This is the definition of polynomial multiplication.
6.1 Root of Isolation Polynomials
In [18], Fisher and Solow define the dependence polynomial for a graph G
to be
fG(z) = 1 ciz + c2z2 c3z3 Hb (l)u'cwz",
where c* is the number of A:cliques of G.
Some of their interesting results axe repeated here. Results from [14], [17],
and [16] axe also included. Further results than those mentioned here are possible,
see [18] for details.
Theorem 6.3 (Fisher and Solow 1990, [18]) The smallest root (in absolute value)
of fc{z) is real, positive, and less than one.
Theorem 6.4 (Fisher, Solow, and Nonis, [1]] [18] [16]) Let G be a graph with
clique number u, n be the number of vertices of G, e be the number of edges of G,
and let r denote the reciprocal of the smallest root of fa(z). Then,
(1) r > *
m r >
(3) r > A(G) + 1, (X(G) is the largest eigenvalue of A(G)),
I
86
(4) r > and
(5) r < \/n2 l.oe.
Theorem 6.5 (Fisher and Solow 1990, [18]) If H is an induced subgraph of G,
then r(H) < r((7).
The isolation polynomial of a (0, l)matrix M is the same as the depend
ence polynomial of Gi(M) except for the alternating signs. So, the previous two
theorems apply with only very slight modification to isolation polynomials.
Corollary 6.1 Let M be a (0, l)matnx and let s be the smallest root (in absolute
value) of S(x, M). Then, 1 < s < 0.
As with dependence polynomials, there are matrices M for which the isolation
polynomial has complex roots. For example, let
Then, I{M, x) = 1 + lOx + 21x2 + 13x3 which has roots approximately 0.7401
0.1463i and 0.1351.
Corollary 6.2 Let M be a (0, l)matn'x, \M\ be the number of ones in M, e,(M)
10 0 1
0 10 1
M =
0 0 11
1111
be the number of edges in s be the smallest root (in absolute value) of
S(x, M), and r = 1/s. Then,
(3) r > A(Gb(M)) + 1,
87
(5) r < y/\M\2 1.5e,(M).
Corollary 6.3 If N is a submatrix of M, then r(N) < r(M).
6.2 Some Special Matrices
6.2.1 The Matrix /
Through appropriate use of the recursion in Theorem 6.1 and some initial
observations, it is possible to determine S(x, Jn /) for all values of n. We will
begin with an illustrative example. First notice that for the (0,1, *)matrix
0 * * * *
10 111
1 * 0 * * 5
1 * * 0 *
1***0
the isolation polynomial is 1 + lx + 3x2. And, for the (0,1, *)matrix
0 * * * *
* 0 * * *
* 1 0 * * >
* 1 * 0 *
* 1 * * 0
the isolation polynomial is 1 + 3x. Permutations of these matrices occur several
times in this example.
88
Now we will proceed with the recursion, first across the first row of our ex
ample, and then down the first column.
!
!
\
0 1 1 1 1 0 * 1 1 1 0 * * * *
1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
S(x, 1 1 0 1 1 ) = S(x, 1 1 0 1 1 ) + xS(x, 1 * 0 * *
1 1 1 0 1 1 1 1 0 1 1 * * 0 *
1 1 1 1 0 1 1 1 1 0 1 * * * 0
0 * * 1 1 0 * * * *
1 0 1 1 1 1 0 * * *
II JS) H 1 1 0 1 1 ) + xS(x, 1 1 0 1 *
1 1 1 0 1 1 * * 0 *
1 1 1 1 0 1 * * * 0
f x(l + 7x + 3x2)
0 * * * 1 0 * * * *
1 0 1 1 1 1 0 * * *
II jo H 1 1 0 1 1 ) + xS(x, 1 * 0 * *
1 1 1 0 1 1 1 1 0 1
1 1 1 1 0 1 * * * 0
+ 2x(l + 7x + 3x2)
0 * * * * 0 * * * *
1 0 1 1 1 1 0 * * *
II J~n 1 1 0 1 1 ) + x5(x, 1 * 0 * *
1 1 1 0 1 1 * * 0 *
1 1 1 1 0 1 1 1 1 0
89
+ 3x(l + 7x + 3x2)
0 * * * * 0 * * * *
* 0 1 1 1 * 0 * * *
= S(x, 1 1 0 1 1 ) +xS,(x, * 1 0 * *
1 1 1 0 1 * 1 * 0 *
1 1 1 1 0 * 1 * * 0
+ 4x(l + 7x + 3x2)
0 * * * * 0 * * * *
* 0 1 1 1 * 0 1 * *
= S(x, * 1 0 1 1 ) +xS(x, * * 0 * *
1 1 1 0 1 * * 1 0 *
1 1 1 1 0 * * 1 * 0
+ x(l + 3x) + 4x(l + 7x + 3x2)
0 * * * * 0 * * * *
* 0 1 1 1 * 0 * 1 *
= S{x, * 1 0 1 1 ) +xS(x, * * 0 1 *
* 1 1 0 1 * * * 0 *
1 1 1 1 0 * * * 1 0
+ 2x(l + 3x) + 4x(l + 7 r + 3x2)
0 * * * * 0 * * * *
* 0 1 1 1 * 0 * * 1
= S(x, * 1 0 1 1 ) + xS(x, * * 0 * 1
* 1 1 0 1 * * * 0 1
* 1 1 1 0 * * * * 0
90
