Logical matrix: Difference between revisions

Revision as of 21:27, 13 January 2022

Revision as of 21:33, 13 January 2022

Line 2:

==Matrix representation of a relation==

If ''R'' is a [[binary relation]] between the finite [[indexed set]]s ''X'' and ''Y'' (so {{nowrap| ''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} =

\begin{cases}

1 & (x_i, y_j) \in R, \\

0 & (x_i, y_j) \not\in R.

\end{cases}

</math>

In order to designate the row and column numbers of the matrix, the sets ''X'' and ''Y'' are indexed with positive integers: ''i'' ranges from 1 to the [[cardinality]] (size) of ''X'', and ''j'' ranges from 1 to the cardinality of ''Y''. See the entry on [[indexed set]]s for more detail.

===Example===

The binary relation ''R'' on the set {{nowrap|{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:

:<math>\begin{pmatrix}

Line 23:

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1

\end{pmatrix},</math>

which includes a diagonal of ones, since each number divides itself.

==Other examples==