Logical matrix: Difference between revisions

Revision as of 03:25, 26 January 2024

Revision as of 03:26, 26 January 2024

Line 1:

{{Short description|Matrix of binary truth values}}

A '''logical matrix''', '''binary matrix''', '''relation matrix''', '''Boolean matrix''', or '''(0, 1)-matrix''' is a [[matrix (mathematics)|matrix]] with entries from the [[Boolean ___domain]] {{nowrapmath|1='''B''' = {0, 1}.}} Such a matrix can be used to represent a [[binary relation]] between a pair of [[finite set]]s. It is an important tool in [[combinatorial mathematics]] and [[theoretical computer science]].

==Matrix representation of a relation==

If ''R'' is a [[binary relation]] between the finite [[indexed set]]s ''X'' and ''Y'' (so {{nowrapmath| ''R'' ⊆ ''X'' ×''Y''}}), then ''R'' can be represented by the logical matrix ''M'' whose row and column indices index the elements of ''X'' and ''Y'', respectively, such that the entries of ''M'' are defined by

:<math>m_{i,j} =

Line 15:

===Example===

The binary relation ''R'' on the set {{nowrapmath|{1, 2, 3, 4}{{null}}}} is defined so that ''aRb'' holds if and only if ''a'' [[divides]] ''b'' evenly, with no remainder. For example, 2''R''4 holds because 2 divides 4 without leaving a remainder, but 3''R''4 does not hold because when 3 divides 4, there is a remainder of 1. The following set is the set of pairs for which the relation ''R'' holds.

:{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

The corresponding representation as a logical matrix is

Line 43:

==Some properties==

[[File:Matrix multiply.png|thumb|Multiplication of two logical matrices using [[boolean algebra]].]]

The matrix representation of the [[Equality (mathematics)|equality relation]] on a finite set is the [[identity matrix]] ''I'', that is, the matrix whose entries on the diagonal are all 1, while the others are all 0. More generally, if relation ''R'' satisfies {{nowrapmath|I ⊆ ''R'',}} then ''R'' is a [[reflexive relation]].

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.

Line 58:

In fact, ''U'' forms a [[Boolean algebra]] with the operations [[and (logic)|and]] & [[or (logic)|or]] between two matrices applied component-wise. The complement of a logical matrix is obtained by swapping all zeros and ones for their opposite.

Every logical matrix {{nowrapmath|1=''A'' = (''A''_''ij'')}} has a transpose {{nowrapmath|1=''A''^T = (''A''_''ji'').}} Suppose ''A'' is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, <math>A^{\operatorname{T}}A</math> contains the ''m'' × ''m'' [[identity matrix]], and the product <math>AA^{\operatorname{T}}</math> contains the ''n'' × ''n'' identity.

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.