Logical matrix: Difference between revisions

Revision as of 02:58, 14 September 2024

Latest revision as of 07:30, 17 June 2025

(6 intermediate revisions by 4 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 47 ⟶ 49:

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 ⟶ 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 |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 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={{Format ISBN|9780511778810}}978-0-511-77881-0 |first=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 99 ⟶ 101:

{{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={{Format ISBN|9780429185533}}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= 10.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 }}

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

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

Line 118 ⟶ 120:

{{DEFAULTSORT:Logical Matrix}}

[[Category:Boolean algebra]]

[[Category:Matrices (mathematics)]]