The Full Wiki

• Wikis

Logical matrix: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

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.

Matrix representation of a relation

If R is a binary relation between the finite sets X and Y (so RX×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: $M_{i,j} = \begin{cases} 1 & (i, j) \in R \ 0 & (i, j) \not\in R \end{cases}$

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 (one-one 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.

Example

The binary relation divides on the set of natural numbers {1, 2, 3, 4} consists of the set of pairs

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

The corresponding representation as a Boolean matrix is: $\begin{pmatrix} 1 & 1 & 1 & 1 \ 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \end{pmatrix}.$

Some properties

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.