Logical matrix: Difference between revisions

Revision as of 16:47, 14 January 2022

Latest revision as of 07:30, 17 June 2025

(45 intermediate revisions by 25 users not shown)

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]] {{nowrapmath|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 {{nowrapmath| ''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_m_{i,j} =

\begin{cases}

1 & (x_i, y_j) \in R, \\

Line 12:

</math>

In order to designate the row and column numbers of the matrix, the sets ''X'' and ''Y'' are indexed with positive integers[[integer]]s: ''i'' ranges from 1 to the [[cardinality]] (size) of ''X'', and ''j'' ranges from 1 to the cardinality of ''Y''. See the entryarticle on [[indexed set]]s for more detail.

The [[transpose]] <math>R^T</math> of the logical matrix <math>R</math> of a binary relation corresponds to the [[converse relation]].<ref>[[Irving Copi|Irving M. Copilowish]] (December 1948) "Matrix development of the calculus of relations", [[Journal of Symbolic Logic]] 13(4): 193–203 [https://www.jstor.org/stable/2267134?seq=1#page_scan_tab_contents Jstor link]</ref>

===Example===

The binary relation ''R'' on the set {{nowrapmath|{1, 2, 3, 4}{{null}}}} is defined so that ''aRb'' holds if and only if ''a'' [[divides]] ''b'' evenly, with no remainder. For example, 2''R''4 holds because 2 divides 4 without leaving a remainder, but 3''R''4 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

Line 30 ⟶ 32:

==Other examples==

* A [[permutation matrix]] is a (0,&nbsp; 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,&nbsp; 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,&nbsp; 1)-matrix, and any (0,&nbsp; 1)-matrix arises in this way.

* The [[prime factorsfactor]]s of a list of ''m'' [[square-free integer|square-free]], [[smooth number|''n''-smooth]] numbers can be described as aan ''m''&nbsp; ×&nbsp; π(''n'') (0,&nbsp; 1)-matrix, where π is the [[prime-counting function]], and ''a''_''ij'' is 1 if and only if the ''j''th prime divides the ''i''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,&nbsp; 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 transitions|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==

[[File:Matrix multiply.png|thumb|Multiplication of two logical matrices using [[Boolean algebra]].]]

The matrix representation of the [[Equality (mathematics)|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 {{nowrapmath|I ⊂⊆ ''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 relations|composition]] of two relations is equal to the [[matrix product]] of the matrix representations of these relations.

This product can be computed in [[Expected value|expected]] time O(''n''²).<ref>{{cite journal| author|first1=Patrick E. |last1=O'Neil | author2first2= Elizabeth J. |last2=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–138132–8| doi=10.1016/s0019-9958(73)90228-3| doi-access=free}} &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.

Line 52 ⟶ 57:

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

:<math>m\forall A,B \in U, \quad A \subsetleq nB \quad \text{when} \quad \forall i,j \quad m_A_{ij} = 1 \implies n_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 {{nowrapmath|1=a''A'' = ( a ''A''_{i j''ij''} )}} has ana '''transpose''' {{nowrapmath|1=a''A''^T = ( a ''A''_{j i''ji''} ).}} Suppose ''aA'' is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, a<supmath>A^{\operatorname{T}}A</supmath> a contains the ''m'' × ''m'' [[identity matrix]], and the product a a<supmath>AA^{\operatorname{T}}</supmath> contains the ''n'' × ''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.

Every logical matrix in ''U'' corresponds to a binary relation. These listed operations on ''U'', and ordering, correspond to a [[algebraic logic#Calculus of relations|calculus of relations]], where the matrix multiplication represents [[composition of relations]].<ref>[[{{cite journal |author-link=Irving Copilowish]] (December|first=Irving 1948).|last=Copilowish "|title=Matrix development of the calculus of relations", |journal=[[Journal of Symbolic Logic]] |volume=13( |issue=4): |pages=193–203 [https://www.jstor|date=December 1948 |doi=10.org/stable2307/2267134?seq |jstor=1#page_scan_tab_contents Jstor link]2267134}}</ref>

==Logical vectors==

{{Group-like structures}}

If ''m'' or ''n'' equals one, then the ''m'' × ''n'' logical matrix (''Mm''_''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 one1 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'' × ''n'' [[rectangular relation]]

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

A re-orderingreordering 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=9780511778810978-0-511-77881-0 | authorfirst=Gunther |last=Schmidt | page=91 | title=Relational Mathematics | chapter=6: Relations and Vectors | publisher=Cambridge University Press | year=2013 | author-link=Gunther Schmidt }}</ref>

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'''.<ref name=GS/> A particular instance is the universal relation ''h h''<supmath>hh^{\operatorname{T}}</supmath>.

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 [[heterogeneous relation#Induced concept lattice|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 ''<math>R'' .</math> To calculate elements of ''R R''<supmath>RR^{\operatorname{T}}</supmath>, 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 (algebra)|magma]]. Consequently there are zeros in ''R R''<supmath>RR^{\operatorname{T}}</supmath>, and it fails to be a [[universal relation]].

{{Group-like structures}}

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 R''^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, semigroup is orthogonal to loop, small category is orthogonal to quasigroup, and groupoid is orthogonal to magma. Consequently there are zeros in ''R R''^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''. PropositionThe 1.6sum inof ''Designpoint Theory''degrees equals the sum of block degrees.<ref name=BJL>E.g., see {{cite bookencyclopedia |first1=Thomas |last1=Beth |first2=Dieter |last2=Jungnickel |author-link2=Dieter Jungnickel |first3=Hanfried |last3=Lenz |author-link3=Hanfried Lenz |chapter=I. Examples and basic definitions |title=Design Theory |encyclopedia=Encyclopedia of Mathematics and its Applications |volume=69 |publisher=[[Cambridge University Press]] |page=18 |year=1999 |edition=2nd |ISBNisbn=978-0-521-44432-3 |doi=10.1017/CBO9780511549533.001 }}</ref> 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; (or in matrix language, for the existence of a (0,&nbsp; 1)-matrix of type ''v''&nbsp;×&nbsp;''b'' with given row and column sums".<ref name=BJL/> SuchThis a structureproblem is asolved by the [[blockGale–Ryser designtheorem]].

==See also==

Line 85 ⟶ 90:

* [[De Bruijn torus|Binatorix]] (a binary De Bruijn torus)

* [[Bit array]]

* [[Disjunct matrix]]

* [[Redheffer matrix]]

* [[Truth table]]

* [[Three-valued logic]]

==Notes==

Line 91 ⟶ 99:

==References==

{{refbegin}}

* {{Citation | last1=Hogben | first1=Leslie|author1-link= Leslie Hogben | title=Handbook of Linear Algebra (Discrete Mathematics and Its Applications) | publisher=Chapman & Hall/CRC | ___location=Boca Raton | isbn=978-1-58488-510-8 | year=2006}}, § 31.3, Binary Matrices

* {{Citationcite |encyclopedia last1|author-link=KimRichard |A. first1Brualdi |first=KiRichard HangA. |last=Brualdi |title=BooleanCombinatorial Matrix TheoryClasses |publisher=Cambridge University Press |encyclopedia=Encyclopedia of Mathematics and its Applications |yearvolume=1982108 |date=2006 |isbn=978-0-8247521-178886565-94 |doi=10.1017/CBO9780511721182}}

* {{cite encyclopedia |first1=Richard A. |last1=Brualdi |first2=Herbert J. |last2=Ryser |title=Combinatorial Matrix Theory |publisher=Cambridge University Press |encyclopedia=Encyclopedia of Mathematics and its Applications |volume=39 |date=1991 |isbn=0-521-32265-0 |doi=10.1017/CBO9781107325708}}

* [[H. J. Ryser]] (1957) "Combinatorial properties of matrices of zeroes and ones", [[Canadian Journal of Mathematics]] 9: 371–7.

* {{Citation |first=J.D. |last=Botha |chapter=31. Matrices over Finite Fields §31.3 Binary Matrices |edition=2nd |editor-last1=Hogben | editor-first1=Leslie|author1-link= Leslie Hogben | title=Handbook of Linear Algebra (Discrete Mathematics and Its Applications) | publisher=Chapman & Hall/CRC | ___location=Boca Raton | isbn=978-10-58488429-51018553-83 | year=2006}},2013 § 31|doi=10.3,1201/b16113 Binary Matrices}}

* Ryser, H.J. (1960) "Traces of matrices of zeroes and ones", ''Canadian Journal of Mathematics'' 12: 463–76.

* {{Citation | last1=Kim | first1=Ki Hang|author-link=Ki-Hang Kim | title=Boolean Matrix Theory and Applications |year=1982| publisher=Dekker| isbn=978-0-8247-1788-9}}

* Ryser, H.J. (1960) "Matrices of Zeros and Ones", [[Bulletin of the American Mathematical Society]] 66: 442–64.

* [[{{cite journal |author-link=H. J. Ryser]] (1957)|first=H.J. |last=Ryser "|title=Combinatorial properties of matrices of zeroes and ones", |journal=[[Canadian Journal of Mathematics]] |volume=9: |issue= |pages=371–7 |date=1957 |doi= 10.4153/CJM-1957-044-3|url=}}

* [[D. R. Fulkerson]] (1960) "Zero-one matrices with zero trace", [[Pacific Journal of Mathematics]] 10; 831–6

* D. R.{{cite Fulkerson &journal |first=H. J. |last=Ryser (1961)|title=Traces "Widthsof and heightsmatrices of (0,zeroes 1)-matrices",and ones ''|journal=Canadian Journal of Mathematics'' 13:|volume=12 239–55|issue= |pages=463–476 |date=1960 |doi=10.4153/CJM-1960-040-0 }}

* {{cite journal |first=H.J. |last=Ryser |title=Matrices of Zeros and Ones |journal=[[Bulletin of the American Mathematical Society]] |volume=66 |issue= 6|pages=442–464 |date=1960 |doi= 10.1090/S0002-9904-1960-10494-6|url=https://www.ams.org/journals/bull/1960-66-06/S0002-9904-1960-10494-6/S0002-9904-1960-10494-6.pdf}}

* [[L. R. Ford Jr.]] & D. R. Fulkerson (1962) § 2.12 "Matrices composed of 0's and 1's", pages 79 to 91 in ''Flows in Networks'', [[Princeton University Press]] {{mr|id=0159700}}

* {{cite journal |author-link=D. R. Fulkerson |first=D.R. |last=Fulkerson |title=Zero-one matrices with zero trace |journal=[[Pacific Journal of Mathematics]] |volume=10 |issue= 3|pages=831–6 |date=1960 |doi= 10.2140/pjm.1960.10.831|url=https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-10/issue-3/Zero-one-matrices-with-zero-trace/pjm/1103038231.pdf}}

* {{cite journal |first1=D.R. |last1=Fulkerson |first2=H.J. |last2=Ryser |title=Widths and heights of (0, 1)-matrices |journal=Canadian Journal of Mathematics |volume=13 |issue= |pages=239–255 |date=1961 |doi=10.4153/CJM-1961-020-3 |url=}}

* {{cite book |author-link=L. R. Ford Jr. |first1=L.R. |last1=Ford Jr. |first2=D.R. |last2=Fulkerson |chapter=II. Feasibility Theorems and Combinatorial Applications §2.12 Matrices composed of 0's and 1's |chapter-url=https://www.degruyter.com/document/doi/10.1515/9781400875184-004/html |title=Flows in Networks |publisher=[[Princeton University Press]] |___location= |date=2016 |orig-year=1962 |isbn=9781400875184 |pages=79–91 |doi=10.1515/9781400875184-004 |mr=0159700}}

{{refend}}

==External links==

Line 108 ⟶ 120:

{{DEFAULTSORT:Logical Matrix}}

[[Category:Boolean algebra]]

[[Category:Matrices (mathematics)]]