A logical matrix, also known as a binary matrix, relation matrix, or Boolean matrix, is a rectangular array whose entries are limited to the Boolean domain {0, 1}. Logical matrices are used to represent binary relations between elements of two finite sets. They form a fundamental concept in combinatorial mathematics, graph theory, and theoretical computer science, serving as a bridge between algebraic logic and set relations.
Matrix Representation of a Relation
Let R be a binary relation between two finite sets X and Y. The corresponding logical matrix M represents whether each pair (xᵢ, yⱼ) belongs to the relation R.
Formally: mi,j={1,if (xi,yj)∈R0,if (xi,yj)∉Rm_{i,j} = \begin{cases} 1, & \text{if } (x_i, y_j) \in R \\ 0, & \text{if } (x_i, y_j) \notin R \end{cases}mi,j={1,0,if (xi,yj)∈Rif (xi,yj)∈/R
Rows index elements of X, while columns index elements of Y. The transpose of the matrix, denoted Rᵀ, corresponds to the converse relation, reversing the direction of association between sets.
Example
Consider the relation R on the set {1, 2, 3, 4}, defined such that aRb holds if and only if a divides b evenly. The pairs satisfying this condition are:
{(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}.
The corresponding logical matrix is: (1111010100100001)\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}1000110010101101
This matrix includes a diagonal of ones, showing that each number divides itself.
Applications and Examples
Logical matrices appear in diverse mathematical and computational structures:
- Permutation Matrix: A (0,1)-matrix with exactly one “1” per row and column.
- Costas Array: A special permutation matrix used in radar and sonar applications.
- Incidence Matrix: Represents incidence relations in combinatorics and graph theory.
- Design Matrix: Used in statistics and experimental design with constant row sums.
- Adjacency Matrix: Represents graphs — symmetric for undirected and asymmetric for directed graphs.
- Biadjacency Matrix: Represents bipartite graphs, where any (0,1)-matrix can model such a structure.
- Binary Image Representation: Bitmaps with two colors can be represented as (0,1)-matrices.
- Prime Factorization Matrix: Used in the quadratic sieve algorithm to represent divisibility of numbers by primes.
Logical matrices also model game rules (as in the game of Go), recurrence plots in dynamical systems, and transition systems in multi-valued logic.
Operations and Algebraic Properties
Logical matrices support operations under Boolean algebra, where addition corresponds to logical OR and multiplication corresponds to logical AND. When viewed over the semiring GF(2) (the Galois Field of order 2), their arithmetic is performed modulo 2.
Key properties include:
- The identity matrix (I) represents the equality relation.
- Reflexive relations correspond to matrices with all ones on the diagonal.
- Matrix multiplication (in Boolean terms) represents composition of relations.
The number of distinct m × n binary matrices is 2^(mn), a finite but exponentially growing quantity.
Lattice and Boolean Algebra
Let U be the set of all logical m×n matrices. It forms a Boolean algebra ordered by inclusion, where A ≤ B if every 1 in A corresponds to a 1 in B. The complement of a matrix swaps 0s and 1s.
Each matrix has a transpose (Aᵀ), and Boolean matrix multiplication defines a lattice structure. The product AᵀA contains the identity matrix if A has no all-zero rows or columns. This structure underlies the calculus of relations, in which matrix multiplication represents relation composition.
Logical Vectors
When one of the dimensions (m or n) equals one, the logical matrix becomes a logical vector (or bit string).
- For m = 1, it is a row vector.
- For n = 1, it is a column vector.
The outer product of two logical vectors P and Q forms a matrix defined by mᵢⱼ = Pᵢ ∧ Qⱼ, assembling ones into a rectangular pattern.
If v is a logical vector and h is a vector of all ones, then R = v hᵀ forms a matrix with constant rows. The universal relation hhᵀ represents complete connectivity between all elements.
Concept Lattices and Relation Analysis
Relations can be decomposed into concepts, which are maximal rectangular relations contained within a matrix. These form the basis for concept lattice theory, which explores hierarchical structures in relations — a method used in formal concept analysis (FCA) and knowledge representation.
Row and Column Sums
The total number of ones in a logical matrix can be computed by summing rows or columns.
- Row sums represent point degrees (the number of relations each element participates in).
- Column sums represent block degrees.
In incidence geometry, these correspond to points and lines (blocks). The equality of total row and column sums reflects the Gale–Ryser theorem, which provides necessary and sufficient conditions for the existence of a (0,1)-matrix with specified row and column totals.
Mathematical and Computational Importance
Logical matrices are central in combinatorial design, graph theory, cryptography, and matrix algebra. They provide a discrete representation of logical relations, supporting efficient algorithms for network modeling, Boolean satisfiability, signal processing, and pattern recognition.
By combining simplicity with mathematical rigor, the logical matrix continues to serve as a versatile framework across pure and applied mathematics, enabling formal representation of relational systems and logical operations.
