Logical matrix: Difference between revisions

Revision as of 03:02, 14 September 2024

Revision as of 20:40, 11 November 2024

Line 47:

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 |firstfirst1=Patrick E. |lastlast1=O'Neil |first2= 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–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:

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 |first=Irving |last=Copilowish |title=Matrix development of the calculus of relations |journal=[[Journal of Symbolic Logic]] |volume=13 |issue=4 |pages=193–203 |date=December 1948 |doi=10.2307/2267134 |jstor=2267134}}</ref>

==Logical vectors==

Line 99:

{{refbegin}}

* {{cite encyclopedia |author-link=Richard A. Brualdi |first=Richard A. |last=Brualdi |title=Combinatorial Matrix Classes |publisher=Cambridge University Press |encyclopedia=Encyclopedia of Mathematics and its Applications |volume=108 |date=2006 |isbn=978-0-521-86565-4 |doi=10.1017/CBO9780511721182}}

* {{cite encyclopedia |firstfirst1=Richard A. |lastlast1=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}}

* {{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 |isbn=978-0-429-18553-3 | 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}}

* {{cite journal |author-link=H. J. Ryser |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= |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 }}

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

* {{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= |pages=831–6 |date=1960 |doi= |url=https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-10/issue-3/Zero-one-matrices-with-zero-trace/pjm/1103038231.pdf}}

* {{cite journal |firstfirst1=D.R. |lastlast1=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. |firstfirst1=L.R. |lastlast1=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 |MRmr=0159700}}

{{refend}}