Logical matrix

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets.

Matrix representation of a relation[edit]

If R is a binary relation between the finite indexed sets X and Y (so RX×Y), then R can be represented by the logical matrix M whose row and column indices index the elements of X and Y, respectively, such that the entries of M are defined by:

In order to designate the row and column numbers of the matrix, the sets X and Y are indexed with positive integers: i ranges from 1 to the cardinality (size) of X and j ranges from 1 to the cardinality of Y. See the entry on indexed sets for more detail.

Example[edit]

The binary relation R on the set {1, 2, 3, 4} is defined so that aRb holds if and only if a divides b evenly, with no remainder. For example, 2R4 holds because 2 divides 4 without leaving a remainder, but 3R4 does not hold because when 3 divides 4 there is a remainder of 1. The following set is the set of pairs for which the relation R holds.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

The corresponding representation as a logical matrix is:

Other examples[edit]

Some properties[edit]

The matrix representation of the equality relation on a finite set is the identity matrix I, that is, the matrix whose entries on the diagonal are all 1, while the others are all 0. More generally, if relation R satisfies I ⊂ R, then R is a reflexive relation.

If the Boolean domain is viewed as a semiring, where addition corresponds to logical OR and multiplication to logical AND, the matrix representation of the composition of two relations is equal to the matrix product of the matrix representations of these relation. This product can be computed in expected time O(n2).[2]

Frequently operations on binary matrices are defined in terms of modular arithmetic mod 2—that is, the elements are treated as elements of the Galois field GF(2) = ℤ2. They arise in a variety of representations and have a number of more restricted special forms. They are applied e.g. in XOR-satisfiability.

The number of distinct m-by-n binary matrices is equal to 2mn, and is thus finite.

Lattice[edit]

Let n and m be given and let U denote the set of all logical m × n matrices. Then U has a partial order given by

In fact, U forms a Boolean algebra with the operations and and or between two matrices applied component-wise. The complement of a logical matrix is obtained by swapping all zeros and ones for their opposite.

Every logical matrix a = ( a i j ) has an transpose aT = ( a j i ). Suppose a is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, aT a is the m × m identity matrix, and the product a aT is the n × n identity.

As a mathematical structure, the Boolean algebra U forms a lattice ordered by inclusion; additionally it is a multiplicative lattice due to matrix multiplication.

Every logical matrix in U corresponds to a binary relation. These listed operations on U, and ordering, correspond to a calculus of relations, where the matrix multiplication represents composition of relations.[3]

Logical vectors[edit]

If m or n equals one, then the m × n logical matrix (Mi j) is a logical vector. If m = 1 the vector is a row vector, and if n = 1 it is a column vector. In either case the index equaling one is dropped from denotation of the vector.

Suppose are two logical vectors. The outer product of P and Q results in an m × n rectangular relation:

A re-ordering of the rows and columns of such a matrix can assemble all the ones into a rectangular part of the matrix. [4]

In concept analysis a relation is studied by determining the maximal rectangular relations contained in it.

See also[edit]

Notes[edit]

  1. ^ Petersen, Kjeld (February 8, 2013). "Binmatrix". Retrieved August 11, 2017. 
  2. ^ Patrick E. O'Neil, Elizabeth J. O'Neil (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure" (PDF). Information and Control. 22 (2): 132–138. doi:10.1016/s0019-9958(73)90228-3.  — The algorithm relies on addition being idempotent, cf. p.134 (bottom).
  3. ^ Irving Copilowish (December 1948) "Matrix development of the calculus of relations", Journal of Symbolic Logic 13(4): 193–203 Jstor link
  4. ^ Gunther Schmidt (2013). Relational Mathematics. Cambridge University Press. p. 95. doi:10.1017/CBO9780511778810. ISBN 9780511778810. 

References[edit]

  • Hogben, Leslie (2006), Handbook of Linear Algebra (Discrete Mathematics and Its Applications), Boca Raton: Chapman & Hall/CRC, ISBN 978-1-58488-510-8 , section 31.3, Binary Matrices
  • Kim, Ki Hang (1982), Boolean Matrix Theory and Applications, ISBN 0-8247-1788-0 

External links[edit]