Logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or matrix is a matrix with entries from the Boolean domain 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, 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: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 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 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.The corresponding representation as a logical matrix is:
Other examples
- A permutation matrix is a -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 and lines of a geometry, blocks of a block design, or edges of a graph
- A design matrix in analysis of variance is a -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 -matrix, and any -matrix arises in this way.
- The prime factors of a list of m square-free, n-smooth numbers can be described as a m×π -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 -matrix in which the 0's represent pixels of one color and the 1's represent pixels of the other color.
- A binary matrix can be used to check the game rules in the game of Go
Some properties
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 relations.
This product can be computed in expected time O.
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. 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.
Lattice
Let n and m be given and let U denote the set of all logical m × n matrices. Then U has a partial order given byIn fact, U forms a Boolean algebra with the operations and & or between two matrices applied component-wise. The complement of a logical matrix is obtained by swapping all zeros and ones for their opposite.
Every logical matrix a = has an transpose aT =. Suppose a is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, aT a contains the m × m identity matrix, and the product a aT contains the n × n identity.
As a mathematical structure, the Boolean algebra U forms a lattice ordered by inclusion; additionally it is a multiplicative lattice due to matrix multiplication.
Every logical matrix in U corresponds to a binary relation. These listed operations on U, and ordering, correspond to a calculus of relations, where the matrix multiplication represents composition of relations.
Logical vectors
If m or n equals one, then the m × n logical matrix is a logical vector. If m = 1 the vector is a row vector, and if n = 1 it is a column vector. In either case the index equaling one is dropped from denotation of the vector.Suppose are two logical vectors. The outer product of P and Q results in an m × n rectangular relation:
Let h be the vector of all ones. Then if v is an arbitrary logical vector, the relation R = v hT has constant rows determined by v. In the calculus of relations such an R is called a vector. A particular instance is the universal relation h hT.
For a given relation R, a maximal, rectangular relation contained in R is called a concept in R. Relations may be studied by decomposing into concepts, and then noting the induced concept lattice.
Consider the table of group-like structures, where "unneeded" can be denoted 0, and "required" denoted by 1, forming a logical matrix R. To calculate elements of R RT it is necessary to use the logical inner product of pairs of logical vectors in rows of this matrix. If this inner product is 0, then the rows are orthogonal. In fact, semigroup is orthogonal to loop, small category is orthogonal to quasigroup, and groupoid is orthogonal to magma. Consequently there are 0's in R RT and it fails to be a universal relation.
Row and column sums
Adding up all the 1’s in a logical matrix may be accomplished in two ways, first summing the rows or first summing the columns. When the row-sums are added, the sum is the same as when the column-sums are added. In incidence geometry, the matrix is interpreted as an incidence matrix with the rows corresponding to "points" and the columns as "blocks". A row-sum is called its point degree and a column-sum is the block degree. Proposition 1.6 in Design Theory says that the sum of point degrees equals the sum of block degrees.An early problem in the area was "to find necessary and sufficient conditions for the existence of an incidence structure with given point degrees and block degrees -matrix of type v × b with given row and column sums." Such a structure is a block design.