Logical matrix: Difference between revisions

Revision as of 18:03, 30 December 2022

Revision as of 00:29, 9 January 2023

Line 1:

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

A '''logical matrix''', '''binary matrix''', '''relation matrix''', '''Boolean matrix''', or '''(0,&nbspthinsp;1) matrix''' is a [[matrix (mathematics)|matrix]] with entries from the [[Boolean ___domain]] {{nowrap|1='''B''' = {0,  1}.}} Such a matrix can be used to represent a [[binary relation]] between a pair of [[finite set]]s.

==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} =

Line 12:

</math>

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

===Example===

Line 30:

==Other examples==

* A [[permutation matrix]] is a (0,&nbspthinsp;1)-matrix, all of whose columns and rows each have exactly one nonzero element.

** A [[Costas array]] is a special case of a permutation matrix.

* An [[incidence matrix]] in [[combinatorics]] and [[finite geometry]] has ones to indicate incidence between points (or vertices) and lines of a geometry, blocks of a [[block design]], or edges of a [[graph (discrete mathematics)|graph]].

* A [[design matrix]] in [[analysis of variance]] is a (0,&nbspthinsp;1)-matrix with constant row sums.

* 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,&nbspthinsp;1)-matrix, and any (0,&nbspthinsp;1)-matrix arises in this way.

* The [[prime factorsfactor]]s of a list of ''m'' [[square-free integer|square-free]], [[smooth number|''n''-smooth]] numbers can be described as a ''m''&nbspthinsp;×&nbspthinsp;π(''n'') (0,&nbspthinsp;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,&nbspthinsp;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 51:

==Lattice==

Let ''n'' and ''m'' be given and let ''U'' denote the set of all logical ''m'' &thinsp;× &thinsp;''n'' matrices. Then ''U'' has a [[partial order]] given by

:<math>\forall A,B \in U, \quad A \leq B \quad \text{when} \quad \forall i,j \quad A_{ij} = 1 \implies B_{ij} = 1 .</math>

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 {{nowrap|1=''A'' = ( ''A'' _{''i'' ''jij''} )}} has a transpose {{nowrap|1=''A''^T = ( ''A'' _{''j'' ''iji''} ).}} 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'' &thinsp;× &thinsp;''m'' [[identity matrix]], and the product <math>AA^{\operatorname{T}}</math> contains the ''n'' &thinsp;× &thinsp;''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.

Line 63:

==Logical vectors==

If ''m'' or ''n'' equals one, then the ''m'' &thinsp;× &thinsp;''n'' logical matrix (''M''_''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 one 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_{ij} = P_i \land Q_j.</math>

A re-orderingreordering 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>

Let ''h'' be the vector of all ones. Then if ''v'' is an arbitrary logical vector, the relation ''R'' = ''v h''^T 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 79:

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''. Proposition 1.6 in ''Design Theory''<ref name=BJL>{{cite book |first1=Thomas |last1=Beth |first2=Dieter |last2=Jungnickel |author-link2=Dieter Jungnickel |first3=Hanfried |last3=Lenz |author-link3=Hanfried Lenz |title=Design Theory |publisher=[[Cambridge University Press]] |page=18 |year=1999 |edition=2nd |ISBN=978-0-521-44432-3}}</ref> says that the sum of point degrees equals the sum of block degrees.

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,&nbspthinsp;1)-matrix of type ''v''&nbsp;×&nbsp;''b'' with given row and column sums".<ref name=BJL/> Such a structure is a [[block design]].

==See also==