Logical matrix: Difference between revisions

Revision as of 22:21, 6 August 2023

Revision as of 08:10, 18 August 2023

Line 46:

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=Patrick E. O'Neil | author2= Elizabeth J. 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–138| doi=10.1016/s0019-9958(73)90228-3| doi-access=free}} &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]] {{nowrap|1='''GF'''(2) = ℤ₂}}. 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--->