Logical matrix: Difference between revisions

Revision as of 08:10, 18 August 2023

Revision as of 03:25, 26 January 2024

Line 1:

{{Short description|Matrix of binary truth values}}

A '''logical matrix''', '''binary matrix''', '''relation matrix''', '''Boolean matrix''', or '''(0,  1)-matrix''' is a [[matrix (mathematics)|matrix]] with entries from the [[Boolean ___domain]] {{nowrap|1='''B''' = {0,  1}.}} Such a matrix can be used to represent a [[binary relation]] between a pair of [[finite set]]s. 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 set]]s ''X'' and ''Y'' (so {{nowrap| ''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

:<math>m_{i,j} =

Line 30:

==Other examples==

* A [[permutation matrix]] is a (0,&thinsp; 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 (discrete mathematics)|graph]].

* A [[design matrix]] in [[analysis of variance]] is a (0,&thinsp; 1)-matrix with constant row sums.

* A logical matrix may represent an [[adjacency matrix]] in [[graph theory]]: non-[[symmetric matrix|symmetric]] matrices correspond to [[directed graph]]s, symmetric matrices to ordinary [[graph (discrete mathematics)|graph]]s, and a 1 on the diagonal corresponds to a [[loop (graph theory)|loop]] at the corresponding vertex.

* The [[biadjacency matrix]] of a simple, undirected [[bipartite graph]] is a (0,&thinsp; 1)-matrix, and any (0,&thinsp; 1)-matrix arises in this way.

* The [[prime factor]]s of a list of ''m'' [[square-free integer|square-free]], [[smooth number|''n''-smooth]] numbers can be described as an ''m''&thinsp; ×&thinsp; π(''n'') (0,&thinsp; 1)-matrix, where π is the [[prime-counting function]], and ''a''_''ij'' is 1 if and only if the ''j''&hairsp;th prime divides the ''i''&hairsp;th number. This representation is useful in the [[quadratic sieve]] factoring algorithm.

* A [[Raster graphics|bitmap image]] containing [[pixel]]s in only two colors can be represented as a (0,&thinsp; 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 (game)|Go]].<ref>{{cite web |url=http://senseis.xmp.net/?BinMatrix |title=Binmatrix |date=February 8, 2013 |access-date=August 11, 2017 |first=Kjeld |last=Petersen}}</ref>

* The [[four-valued logic#Matrix machine|four valued logic]] of two bits, transformed by 2x2 logical matrices, forms a [[finite state machine]].

Line 48:

This product can be computed in [[Expected value|expected]] time O(''n''²).<ref>{{cite journal| author=Patrick E. O'Neil | author2= Elizabeth J. O'Neil|author2-link=Elizabeth O'Neil| title=A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure| journal=[[Information and Control]]| year=1973| volume=22| issue=2 |pages=132–138| doi=10.1016/s0019-9958(73)90228-3| doi-access=}} &mdash; The algorithm relies on addition being [[idempotent]], cf. p.134 (bottom).</ref>

Frequently, operations on binary matrices are defined in terms of [[modular arithmetic]] mod 2&mdash;that is, the elements are treated as elements of the [[Galois field]] <math>\bold{{nowrap|1='''GF'''}(2) = ℤ<sub>2\mathbb{Z}_2</submath>}}. They arise in a variety of representations and have a number of more restricted special forms. They are applied e.g. in [[XOR-satisfiability]].<!---more links to applications should go here--->

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''&thinsp; ×&thinsp; ''n'' matrices. Then ''U'' has a [[partial order]] given by

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

In fact, ''U'' forms a [[Boolean algebra]] with the operations [[and (logic)|and]] & [[or (logic)|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 {{nowrap|1=''A'' = (''A''_''ij'')}} has a transpose {{nowrap|1=''A''^T = (''A''_''ji'').}} Suppose ''A'' is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, <math>A^{\operatorname{T}}A</math> contains the ''m''&thinsp; ×&thinsp; ''m'' [[identity matrix]], and the product <math>AA^{\operatorname{T}}</math> contains the ''n''&thinsp; ×&thinsp; ''n'' identity.

As a mathematical structure, the Boolean algebra ''U'' forms a [[lattice (order)|lattice]] ordered by [[inclusion (logic)|inclusion]]; additionally it is a multiplicative lattice due to matrix multiplication.

Line 66:

==Logical vectors==

{{Group-like structures}}

If ''m'' or ''n'' equals one, then the ''m''&thinsp; ×&thinsp; ''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 <math>(P_i),\, i=1,2,\ldots,m</math> and <math>(Q_j),\, j=1,2,\ldots,n</math> are two logical vectors. The [[outer product]] of ''P'' and ''Q'' results in an ''m''&thinsp; ×&thinsp; ''n'' [[rectangular relation]]

:<math>m_{ij} = P_i \land Q_j.</math>

A reordering of the rows and columns of such a matrix can assemble all the ones into a rectangular part of the matrix.<ref name=GS>{{cite book | doi=10.1017/CBO9780511778810 | isbn=9780511778810 | author=Gunther Schmidt | page=91 | title=Relational Mathematics | chapter=6: Relations and Vectors | publisher=Cambridge University Press | year=2013 | author-link=Gunther Schmidt }}</ref>

Line 81:

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.<ref name=BJL>E.g., see {{cite book |first1=Thomas |last1=Beth |first2=Dieter |last2=Jungnickel |author-link2=Dieter Jungnickel |first3=Hanfried |last3=Lenz |author-link3=Hanfried Lenz |title=Design Theory |publisher=[[Cambridge University Press]] |page=18 |year=1999 |edition=2nd |ISBN=978-0-521-44432-3}}</ref>

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,&thinsp; 1)-matrix of type ''v''&nbsp;×&nbsp;''b'' with given row and column sums".<ref name=BJL/> This problem is solved by the [[Gale–Ryser theorem]].

==See also==