Logical matrix: Difference between revisions

Revision as of 06:59, 31 May 2024

Latest revision as of 07:30, 17 June 2025

(10 intermediate revisions by 8 users not shown)

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

Line 43 ⟶ 45:

==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 {{math|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 63 ⟶ 65:

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 71 ⟶ 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 80 ⟶ 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 88 ⟶ 90:

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

* [[Bit array]]

* [[Disjunct matrix]]

* [[Redheffer matrix]]

* [[Truth table]]

Line 96 ⟶ 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. first1Matrices over Finite Fields §31.3 Binary Matrices |edition=Ki2nd Hang|authoreditor-linklast1=KiHogben |editor-Hangfirst1=Leslie|author1-link= KimLeslie Hogben | 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 115 ⟶ 120:

{{DEFAULTSORT:Logical Matrix}}

[[Category:Boolean algebra]]

[[Category:Matrices (mathematics)]]