Logical matrix

Last updated November 12, 2024

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 \subseteq X \times 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 article 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 logical matrix is

{\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 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 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.^[1]
The four valued logic of two bits, transformed by 2x2 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

The matrix representation of the equality relation on a finite set is the identity matrix I, that is, the matrix whose entries on the diagonal are all 1, while the others are all 0. More generally, if relation R satisfies $I \subseteq R,$ then R is a reflexive relation.

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(n²).^[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 ${\mathbf {GF}}(2)=\mathbb {Z} _{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.

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 by

\forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.

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.

Every logical matrix $A = (A ij)$ has a transpose $A T = (A ji).$ Suppose A is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, $A^{\operatorname {T} }A$ contains the m × m identity matrix, and the product $AA^{\operatorname {T} }$ 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.^[3]

Logical vectors

Group-like structures
	Total	Associative	Identity	Cancellation	Commutative
Partial magma	Unneeded	Unneeded	Unneeded	Unneeded	Unneeded
Semigroupoid	Unneeded	Required	Unneeded	Unneeded	Unneeded
Small category	Unneeded	Required	Required	Unneeded	Unneeded
Groupoid	Unneeded	Required	Required	Required	Unneeded
Commutative Groupoid	Unneeded	Required	Required	Required	Required
Magma	Required	Unneeded	Unneeded	Unneeded	Unneeded
Commutative magma	Required	Unneeded	Unneeded	Unneeded	Required
Quasigroup	Required	Unneeded	Unneeded	Required	Unneeded
Commutative quasigroup	Required	Unneeded	Unneeded	Required	Required
Unital magma	Required	Unneeded	Required	Unneeded	Unneeded
Commutative unital magma	Required	Unneeded	Required	Unneeded	Required
Loop	Required	Unneeded	Required	Required	Unneeded
Commutative loop	Required	Unneeded	Required	Required	Required
Semigroup	Required	Required	Unneeded	Unneeded	Unneeded
Commutative semigroup	Required	Required	Unneeded	Unneeded	Required
Associative quasigroup	Required	Required	Unneeded	Required	Unneeded
Commutative-and-associative quasigroup	Required	Required	Unneeded	Required	Required
Monoid	Required	Required	Required	Unneeded	Unneeded
Commutative monoid	Required	Required	Required	Unneeded	Required
Group	Required	Required	Required	Required	Unneeded
Abelian group	Required	Required	Required	Required	Required

If m or n equals one, then the m × n logical matrix (m_ij) is a logical vector or bit string. If m = 1, the vector is a row vector, and if n = 1, it is a column vector. In either case the index equaling 1 is dropped from denotation of the vector.

Suppose $(P_{i}),\,i=1,2,\ldots ,m$ and $(Q_{j}),\,j=1,2,\ldots ,n$ are two logical vectors. The outer product of P and Q results in an m × n rectangular relation

m_{ij}=P_{i}\land Q_{j}.

A reordering of the rows and columns of such a matrix can assemble all the ones into a rectangular part of the matrix.^[4]

Let h be the vector of all ones. Then if v is an arbitrary logical vector, the relation R = v h^T has constant rows determined by v. In the calculus of relations such an R is called a vector.^[4] A particular instance is the universal relation $hh^{\operatorname {T} }$ .

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 $RR^{\operatorname {T} }$ , 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, small category is orthogonal to quasigroup, and groupoid is orthogonal to magma. Consequently there are zeros in $RR^{\operatorname {T} }$ , and it fails to be a universal relation.

Row and column sums

Adding up all the ones 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" (generalizing lines made of points). A row sum is called its point degree, and a column sum is the block degree. The sum of point degrees equals the sum of block degrees.^[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".^[5] This problem is solved by the Gale–Ryser theorem.

Notes

↑ Petersen, Kjeld (February 8, 2013). "Binmatrix" . Retrieved August 11, 2017.
↑ O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure". Information and Control . 22 (2): 132–8. doi:10.1016/s0019-9958(73)90228-3.— The algorithm relies on addition being idempotent, cf. p.134 (bottom).
↑ Copilowish, Irving (December 1948). "Matrix development of the calculus of relations". Journal of Symbolic Logic . 13 (4): 193–203. doi:10.2307/2267134. JSTOR 2267134.
1 2 Schmidt, Gunther (2013). "6: Relations and Vectors". Relational Mathematics. Cambridge University Press. p. 91. doi:10.1017/CBO9780511778810. ISBN 978-0-511-77881-0.
1 2 E.g., see Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). "I. Examples and basic definitions". Design Theory. Encyclopedia of Mathematics and its Applications. Vol. 69 (2nd ed.). Cambridge University Press. p. 18. doi:10.1017/CBO9780511549533.001. ISBN 978-0-521-44432-3.

Related Research Articles

In mathematics, the determinant is a scalar-valued function of the entries of a square matrix. The determinant of a matrix $A$ is commonly denoted $det(A)$ , $det A$ , or $| A |$ . Its value characterizes some properties of the matrix and the linear map represented, on a given basis, by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the corresponding linear map is an isomorphism.

In linear algebra, the identity matrix of size $is the square matrix with ones on the main diagonal and zeros elsewhere. It has unique properties, for example when the identity matrix represents a geometric transformation, the object remains unchanged by the transformation. In other contexts, it is analogous to multiplying by the number 1.$

In linear algebra, the outer product of two coordinate vectors is the matrix whose entries are all products of an element in the first vector with an element in the second vector. If the two coordinate vectors have dimensions n and m, then their outer product is an n × m matrix. More generally, given two tensors, their outer product is a tensor. The outer product of tensors is also referred to as their tensor product, and can be used to define the tensor algebra.

In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices $A$ and $B$ is denoted as $AB$ .

In mathematics, a square matrix is a matrix with the same number of rows and columns. An n-by-n matrix is known as a square matrix of order $.$ Any two square matrices of the same order can be added and multiplied.

<span class="mw-page-title-main">Transpose</span> Matrix operation which flips a matrix over its diagonal

In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix $A$ by producing another matrix, often denoted by $A T$ .

In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagonal matrix is $, while an example of a 3\times3 diagonal matrix is . An identity matrix of any size, or any multiple of it is a diagonal matrix called a scalar matrix, for example, . In geometry, a diagonal matrix may be used as a scaling matrix, since matrix multiplication with it results in changing scale (size) and possibly also shape; only a scalar matrix results in uniform change in scale.$

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function of a matrix called the immanant.

In linear algebra, an invertible matrix is a square matrix which has an inverse. In other words, if some other matrix is multiplied by the invertible matrix, the result can be multiplied by an inverse to undo the operation. Invertible matrices are the same size as their inverse.

In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related and 0 if they are not. There are variations; see below.

In abstract algebra, a matrix ring is a set of matrices with entries in a ring R that form a ring under matrix addition and matrix multiplication. The set of all n × n matrices with entries in R is a matrix ring denoted M_n(R) (alternative notations: Mat_n(R) and R^n×n). Some sets of infinite matrices form infinite matrix rings. A subring of a matrix ring is again a matrix ring. Over a rng, one can form matrix rngs.

In mathematics, a unimodular matrixM is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse. Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The n × n unimodular matrices form a group called the n × n general linear group over $, which is denoted .$

In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix) is a square matrix $of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,$

In mathematics, especially in linear algebra and matrix theory, the vectorization of a matrix is a linear transformation which converts the matrix into a vector. Specifically, the vectorization of a m × n matrix A, denoted vec(A), is the mn × 1 column vector obtained by stacking the columns of the matrix A on top of one another: $Here, represents the element in the i -th row and j -th column of A, and the superscript denotes the transpose. Vectorization expresses, through coordinates, the isomorphism between these (i.e., of matrices and vectors) as vector spaces.$

In the mathematics of binary relations, the composition of relations is the forming of a new binary relation R ; S from two given binary relations R and S. In the calculus of relations, the composition of relations is called relative multiplication, and its result is called a relative product. Function composition is the special case of composition of relations where all relations involved are functions.

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

<span class="mw-page-title-main">Matrix (mathematics)</span> Array of numbers

In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, with elements or entries arranged in rows and columns, which is used to represent a mathematical object or property of such an object.

In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions.

The Gale–Ryser theorem is a result in graph theory and combinatorial matrix theory, two branches of combinatorics. It provides one of two known approaches to solving the bipartite realization problem, i.e. it gives a necessary and sufficient condition for two finite sequences of natural numbers to be the degree sequence of a labeled simple bipartite graph; a sequence obeying these conditions is called "bigraphic". It is an analog of the Erdős–Gallai theorem for simple graphs. The theorem was published independently in 1957 by H. J. Ryser and David Gale.

In discrete mathematics, the Bregman–Minc inequality, or Bregman's theorem, allows one to estimate the permanent of a binary matrix via its row or column sums. The inequality was conjectured in 1963 by Henryk Minc and first proved in 1973 by Lev M. Bregman. Further entropy-based proofs have been given by Alexander Schrijver and Jaikumar Radhakrishnan. The Bregman–Minc inequality is used, for example, in graph theory to obtain upper bounds for the number of perfect matchings in a bipartite graph.

References

Brualdi, Richard A. (2006). "Combinatorial Matrix Classes". Encyclopedia of Mathematics and its Applications. Vol. 108. Cambridge University Press. doi:10.1017/CBO9780511721182. ISBN 978-0-521-86565-4.
Brualdi, Richard A.; Ryser, Herbert J. (1991). "Combinatorial Matrix Theory". Encyclopedia of Mathematics and its Applications. Vol. 39. Cambridge University Press. doi:10.1017/CBO9781107325708. ISBN 0-521-32265-0.
Botha, J.D. (2013), "31. Matrices over Finite Fields §31.3 Binary Matrices", in Hogben, Leslie (ed.), Handbook of Linear Algebra (Discrete Mathematics and Its Applications) (2nd ed.), Chapman & Hall/CRC, doi:10.1201/b16113, ISBN 978-0-429-18553-3
Kim, Ki Hang (1982), Boolean Matrix Theory and Applications, Dekker, ISBN 978-0-8247-1788-9
Ryser, H.J. (1957). "Combinatorial properties of matrices of zeroes and ones". Canadian Journal of Mathematics . 9: 371–7.
Ryser, H.J. (1960). "Traces of matrices of zeroes and ones". Canadian Journal of Mathematics. 12: 463–476. doi:10.4153/CJM-1960-040-0.
Ryser, H.J. (1960). "Matrices of Zeros and Ones" (PDF). Bulletin of the American Mathematical Society . 66: 442–464.
Fulkerson, D.R. (1960). "Zero-one matrices with zero trace" (PDF). Pacific Journal of Mathematics . 10: 831–6.
Fulkerson, D.R.; Ryser, H.J. (1961). "Widths and heights of (0, 1)-matrices". Canadian Journal of Mathematics. 13: 239–255. doi:10.4153/CJM-1961-020-3.
Ford Jr., L.R.; Fulkerson, D.R. (2016) [1962]. "II. Feasibility Theorems and Combinatorial Applications §2.12 Matrices composed of 0's and 1's". Flows in Networks. Princeton University Press. pp. 79–91. doi:10.1515/9781400875184-004. ISBN 9781400875184. MR 0159700.

External links

"Logical matrix", Encyclopedia of Mathematics , EMS Press, 2001 [1994]

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Petersen, Kjeld (February 8, 2013). "Binmatrix" . Retrieved August 11, 2017.

[2] O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure". Information and Control . 22 (2): 132–8. doi:10.1016/s0019-9958(73)90228-3.— The algorithm relies on addition being idempotent, cf. p.134 (bottom).

[3] Copilowish, Irving (December 1948). "Matrix development of the calculus of relations". Journal of Symbolic Logic . 13 (4): 193–203. doi:10.2307/2267134. JSTOR 2267134.

[GS-4] 1 2 Schmidt, Gunther (2013). "6: Relations and Vectors". Relational Mathematics. Cambridge University Press. p. 91. doi:10.1017/CBO9780511778810. ISBN 978-0-511-77881-0.

[BJL-5] 1 2 E.g., see Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). "I. Examples and basic definitions". Design Theory. Encyclopedia of Mathematics and its Applications. Vol. 69 (2nd ed.). Cambridge University Press. p. 18. doi:10.1017/CBO9780511549533.001. ISBN 978-0-521-44432-3.

[1]

[2]

[3]

[4]

[5]

v t e Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz-stable Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Routh-Hurwitz Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematicsportal List of matrices Category:Matrices