A Boolean matrix is a matrix with elements from the Boolean semiring ({0, 1}, +, x), where the addition and multiplication are as usual with the exception that 1 + 1 = 1. In this thesis we study eight classes of monoids whose elements are Boolean matrices. Green's relations are five equivalence relations and three pre-orders which are defined on an arbitrary monoid M and describe much of its structure. In the monoids we consider the equivalence relations are uninteresting - and in most cases completely trivial - but the pre-orders are not and play a vital part in understanding the structure of the monoids. Each of the three pre-orders in each of the eight classes of monoids can be viewed as a computational decision problem: given two elements of the monoid, are they related by the pre-order? The main focus of this thesis is determining the computational complexity of each of these twenty-four decision problems, which we successfully do for all but one.

Sign pattern theory examines what can be said about a matrix if one knows the signs of all or some of its entries but not the exact values. Since all we know is the sign of each entry, we can write these sign patterns as matrices whose entries come from the set {+1, -1, 0, #}, where # is used for an unknown sign. Semirings satisfy all properties of rings with unity except the existence of additive inverses. The set {+1, -1, 0, #} can be viewed as a commutative semiring in natural way. In the thesis, we give a semiring version of the Cayley-Dickson construction which allows one to construct the sign pattern semiring from the Boolean semiring. We use tools from Boolean matrices to study sign nonsingular (SNS) matrices. We also investigate different notions of rank of matrices over semirings. For these rank functions we simplify proofs of classical inequalities for the sum and the product of matrices using the semiring versions of the Cauchy-Binet and Laplace theorems. For matrices over the sign pattern semiring, the minimum rank of the sign pattern is compared with the other versions of the rank. We also characterize irreducible powerful sign pattern matrices and investigate the period and base of an SNS matrix.

Thesis (M.S.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Systems Science and Industrial Engineering, 2009. / Includes bibliographical references.

El trabajo de investigación tuvo como objetivo el diseño de un modelo matricial para la construcción del diagrama de Hasse de un Conjunto Parcialmente Ordenado (CPO), que permita su implementación en un lenguaje de programación. Para lograrlo se utilizó la teoría de Relaciones de Orden Parcial, sus propiedades; matrices booleanas, sus operaciones. Este trabajo permitió determinar el diagrama de Hasse de Relaciones de Orden Parcial sin importar la cantidad de elementos del CPO, y lo más importante, permitió automatizar el modelo. / The research work was aimed at the design of a matrix model for the construction of the Hasse diagram of a Partially Ordained Set (CPO), which allows its implementation in a programming language. To achieve this, we used the theory of partial order relations, their properties; Boolean matrices, their operations. This work allowed to determine the Hasse diagram of Partial Order Relations regardless of the number of elements of the CPO, and most importantly, allowed to automate the model.