Content deleted Content added
Citation bot (talk | contribs) Alter: doi, issue. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Matrices (mathematics) | #UCB_Category 107/234 |
|||
| (7 intermediate revisions by 5 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''<sup>2</sup>).<ref>{{cite journal
Frequently, operations on binary matrices are defined in terms of [[modular arithmetic]] mod 2—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>
==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=
Let ''h'' be the vector of all ones. Then if ''v'' is an arbitrary logical vector, the relation ''R'' = ''v h''<sup>T</sup> 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
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'' × ''b'' with given row and column sums".<ref name=BJL/> This problem is solved by the [[Gale–Ryser theorem]].
Line 97 ⟶ 99:
==References==
{{refbegin}}
* {{cite encyclopedia |author-link=Richard A. Brualdi
* {{
* {{Citation |first=J.D.
* {{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
* {{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 |first1=D.
* {{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 116 ⟶ 120:
{{DEFAULTSORT:Logical Matrix}}
[[Category:Boolean algebra]]
[[Category:Matrices (mathematics)]]
| |||