Content deleted Content added
→cite journal, encyc, book, tweak cites |
|||
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''<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:
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:
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:
==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:
==References==
{{refbegin}}
* {{cite encyclopedia |author-link=Richard A. Brualdi
* {{cite encyclopedia |first=Richard A. |last=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 |
* {{Citation | last1=Kim | first1=Ki Hang|author-link=Ki-Hang Kim | title=Boolean Matrix Theory and Applications |year=1982| isbn=978-0-8247-1788-9}}
*
* {{cite journal |first=H.J. |last=Ryser
* {{cite journal |first=H.J. |last=Ryser
*
* {{cite journal |first=D.
*
{{refend}}
==External links==
| |||