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. It is an important tool in combinatorial mathematics and theoretical computer science.
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 = { 1 ( x i , y j ) ∈ R , 0 ( x i , y j ) ∉ R . {\displaystyle 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 article on indexed sets for more detail. The transpose R T {\displaystyle R^{T}} of the logical matrix R {\displaystyle R} of a binary relation corresponds to the converse relation.
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 logical matrix is
( 1 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1 ) , {\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},}
which includes a diagonal of ones, since each number divides itself.
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. A design matrix in analysis of variance is a (0, 1)-matrix with constant row sums. A logical matrix may represent an adjacency matrix in graph theory: non-symmetric matrices correspond to directed graphs, symmetric matrices to ordinary graphs, and a 1 on the diagonal corresponds to a loop at the corresponding vertex. 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 an m × π(n) (0, 1)-matrix, where π is the prime-counting function, and aij 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 zeros represent pixels of one color and the ones represent pixels of the other color. A binary matrix can be used to check the game rules in the game of Go. The four valued logic of two bits, transformed by 2 × 2 logical matrices, forms a transition system. A recurrence plot and its variants are matrices that shows which pairs of points are closer than a certain vicinity threshold in a phase space.
Some properties
… excerpt ends here. Continue reading the full article.
