Logical matrix: Difference between revisions

Revision as of 03:25, 26 January 2024

Latest revision as of 07:30, 17 June 2025

(14 intermediate revisions by 11 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_{i,j} =

Line 13:

In order to designate the row and column numbers of the matrix, the sets ''X'' and ''Y'' are indexed with positive [[integer]]s: ''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 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 39 ⟶ 41:

* A [[Raster graphics|bitmap image]] containing [[pixel]]s 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 (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 machinetransitions|four valued logic]] of two bits, transformed by 2x2 logical matrices, forms a [[finitetransition state machinesystem]].

* 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 [[booleanBoolean 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=}} &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{GF}(2) = \mathbb{Z}_2</math>. 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--->

Line 58 ⟶ 61:

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''_''ij'')}} has a transpose {{nowrapmath|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'' × ''m'' [[identity matrix]], and the product <math>AA^{\operatorname{T}}</math> 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==

Line 70 ⟶ 73:

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_{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=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 <math>hh^{\operatorname{T}}</math>.

Line 79 ⟶ 82:

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

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

Line 87 ⟶ 90:

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

* [[Bit array]]

* [[Disjunct matrix]]

* [[Redheffer matrix]]

* [[Truth table]]

Line 95 ⟶ 99:

==References==

{{refbegin}}

* [[Richard A. Brualdi]] (2006), ''Combinatorial Matrix Classes.'' Encyclopedia of Mathematics and its Applications, 108. Cambridge University Press, Cambridge, 2006. {{ISBN|978-0-521-86565-4}}

* {{cite encyclopedia |author-link=Richard A. Brualdi &|first=Richard Herbert JA. Ryser (1991),|last=Brualdi ''|title=Combinatorial Matrix Theory''.Classes |publisher=Cambridge University Press |encyclopedia=Encyclopedia of Mathematics and its Applications, 39.|volume=108 Cambridge University Press,|date=2006 Cambridge, 1991. {{ISBN|isbn=978-0-521-3226586565-04 |doi=10.1017/CBO9780511721182}}

* {{Citationcite encyclopedia |first1=Richard A. |last1=HogbenBrualdi |first2=Herbert J. first1|last2=LeslieRyser |author1-linktitle=Combinatorial LeslieMatrix HogbenTheory | titlepublisher=HandbookCambridge ofUniversity LinearPress Algebra|encyclopedia=Encyclopedia (Discreteof Mathematics and Itsits Applications) | publishervolume=Chapman & Hall/CRC39 | ___locationdate=Boca Raton1991 | isbn=9780-1521-5848832265-510-80 | yeardoi=200610.1017/CBO9781107325708}}, § 31.3, Binary Matrices

* {{Citation |first=J.D. last1|last=KimBotha |chapter=31. Matrices over Finite Fields §31.3 Binary Matrices |edition=2nd |editor-last1=Hogben |editor-first1=KiLeslie|author1-link= Leslie HangHogben | title=BooleanHandbook Matrixof TheoryLinear Algebra (Discrete Mathematics and Its Applications) |year publisher=1982|Chapman & Hall/CRC |isbn=978-0-8247429-178818553-93 | year=2013 |doi=10.1201/b16113 }}

* {{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}}

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

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

* {{cite journal |first=H.J. |last=Ryser |title=Traces of matrices of zeroes and ones |journal=Canadian Journal of Mathematics |volume=12 |issue= |pages=463–476 |date=1960 |doi=10.4153/CJM-1960-040-0 }}

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

* {{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}}

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

* {{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 (1961), "|title=Widths and heights of (0, 1)-matrices", ''|journal=Canadian Journal of Mathematics'' |volume=13: 239–55|issue= |pages=239–255 |date=1961 |doi=10.4153/CJM-1961-020-3 |url=}}

* [[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 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 114 ⟶ 120:

{{DEFAULTSORT:Logical Matrix}}

[[Category:Boolean algebra]]

[[Category:Matrices (mathematics)]]