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 R ⊆ X×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:

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

A permutation matrix is a (0,1)-matrix, all of whose columns and rows each have exactly one nonzero element.
- A Costas array is a special case of a permutation matrix
An incidence matrix in combinatorics and finite geometry has ones to indicate incidence between points (or vertices) and lines of a geometry, blocks of a block design, or edges of a graph (discrete mathematics)
A design matrix in analysis of variance is a (0,1)-matrix with constant row sums.
An adjacency matrix in graph theory is a matrix whose rows and columns represent the vertices and whose entries represent the edges of the graph. The adjacency matrix of a simple, undirected graph is a binary symmetric matrix with zero diagonal.
The biadjacency matrix of a simple, undirected bipartite graph is a (0,1)-matrix, and any (0,1)-matrix arises in this way.
The prime factors of a list of m square-free, n-smooth numbers can be described as a m×π(n) (0,1)-matrix, where π is the prime-counting function and a_ij is 1 if and only if the jth prime divides the ith number. This representation is useful in the quadratic sieve factoring algorithm.
A bitmap image containing pixels in only two colors can be represented as a (0,1)-matrix in which the 0's represent pixels of one color and the 1's represent pixels of the other color.
Using binary matrix to check the game rules in the game of Go

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(n²).^[1]

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) = ℤ₂. 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 2^mn, and is thus finite.

Notes

↑ 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).

References

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, Boolean Matrix Theory and Applications, ISBN 0-8247-1788-0

External links

Hazewinkel, Michiel, ed. (2001), "Logical matrix", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

This article is issued from Wikipedia - version of the 10/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.