A logical matrix or Boolean matrix is a matrix (a rectangular table) 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.
If R is a binary relation between the finite sets X and Y (so R ⊆ X×Y), then R can be represented by the matrix M whose row and column indices are given by the sets X and Y, respectively, where the entries of M are defined by:
Note. In the above definition it is assumed that the matrix indices may be taken from any finite set. If the indices are required to be integers from some set {1, 2, ..., n}, a bijection (oneone correspondence) between a finite set of size n and the set {1, 2, ..., n} must be used to represent the elements of the original set as integers.
The binary relation divides on the set of natural numbers {1, 2, 3, 4} consists of the set of pairs
The corresponding representation as a Boolean matrix is:
The matrix representation of the equality relation on a finite set is an identity matrix, that is, one whose entries on the diagonal are all 1, while the others are all 0.
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.
