Logical matrix: Difference between revisions

Revision as of 07:47, 16 January 2023

Revision as of 07:52, 16 January 2023

Line 5:

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_m_{i,j} =

\begin{cases}

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

Line 36:

* A logical matrix may represent an [[adjacency matrix]] in [[graph theory]]: non-[[symmetric matrix|symmetric]] matrices correspond to [[directed graph]]s, symmetric matrices to ordinary [[graph (discrete mathematics)|graph]]s, and a 1 on the diagonal corresponds to a [[loop (graph theory)|loop]] at the corresponding vertex.

* The [[biadjacency matrix]] of a simple, undirected [[bipartite graph]] is a (0,&thinsp;1)-matrix, and any (0,&thinsp;1)-matrix arises in this way.

* The [[prime factor]]s of a list of ''m'' [[square-free integer|square-free]], [[smooth number|''n''-smooth]] numbers can be described as aan ''m''&thinsp;×&thinsp;π(''n'') (0,&thinsp;1)-matrix, where π is the [[prime-counting function]], and ''a''_''ij'' is 1 if and only if the ''j''&hairsp;th prime divides the ''i''&hairsp;th number. This representation is useful in the [[quadratic sieve]] factoring algorithm.

* A [[Raster graphics|bitmap image]] containing [[pixel]]s in only two colors can be represented as a (0,&thinsp;1)-matrix in which the zeros represent pixels of one color and the ones represent pixels of the other color.

* A binary matrix can be used to check the game rules in the game of [[Go (game)|Go]].<ref>{{cite web |url=http://senseis.xmp.net/?BinMatrix |title=Binmatrix |date=February 8, 2013 |access-date=August 11, 2017 |first=Kjeld |last=Petersen}}</ref>

Line 63:

==Logical vectors==

If ''m'' or ''n'' equals one, then the ''m''&thinsp;×&thinsp;''n'' logical matrix (''Mm''_''ij'') is a logical vector. If ''m'' = 1, the vector is a row vector, and if ''n'' = 1, it is a column vector. In either case the index equaling one1 is dropped from denotation of the vector.

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''&thinsp;×&thinsp;''n'' [[rectangular relation]]

:<math>M_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=9780511778810 | author=Gunther Schmidt | page=91 | title=Relational Mathematics | chapter=6: Relations and Vectors | publisher=Cambridge University Press | year=2013 | author-link=Gunther Schmidt }}</ref>