Logical matrix

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.

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

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.

The corresponding representation as a logical matrix is which includes a diagonal of ones, since each number divides itself.

[2] 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.

The number of distinct m-by-n binary matrices is equal to 2mn, and is thus finite.

Then U has a partial order given by In 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.

Suppose A is a logical matrix with no columns or rows identically zero.

As a mathematical structure, the Boolean algebra U forms a lattice ordered by inclusion; additionally it is a multiplicative lattice due to matrix multiplication.

In either case the index equaling 1 is dropped from denotation of the vector.

In incidence geometry, the matrix is interpreted as an incidence matrix with the rows corresponding to "points" and the columns as "blocks" (generalizing lines made of points).

[5] 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; or in matrix language, for the existence of a (0, 1)-matrix of type v × b with given row and column sums".