Logical matrix

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

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

M_{i,j} =
 \begin{cases}
   1 & (x_i, y_j) \in R \\
   0 & (x_i, y_j) \not\in R 
 \end{cases}

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

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 Boolean matrix is:

\begin{pmatrix}
   1 & 1 & 1 & 1 \\
   0 & 1 & 0 & 1 \\
   0 & 0 & 1 & 0 \\
   0 & 0 & 0 & 1
 \end{pmatrix}.

Other examples

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. This product can be computed in expected time O(n2).[1]

Frequently operations on binary matrices are defined in terms of modular arithmetic mod 2that 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.

See also

Wikimedia Commons has media related to Binary matrix.

Notes

  1. Patrick E. O'Neil, Elizabeth J. O'Neil (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure". 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).

References

External links