Content deleted Content added
Raphaelreyna (talk | contribs) m →Lattice: Removes overloading to improve readability. |
No edit summary |
||
Line 32:
* A [[permutation matrix]] is a (0, 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, 1)-matrix with constant row sums.
* A logical matrix may represent an [[adjacency matrix]] in [[graph theory]]: non-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.
Line 38:
* The prime factors of a list of ''m'' [[square-free integer|square-free]], [[smooth number|''n''-smooth]] numbers can be described as a ''m'' × π(''n'') (0, 1)-matrix, where π is the [[prime-counting function]], and ''a''<sub>''ij''</sub> is 1 if and only if the ''j''th prime divides the ''i''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, 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>
==Some properties==
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 {{nowrap|I
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''<sup>2</sup>).<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}} — 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—that is, the elements are treated as elements of the [[Galois field]] {{nowrap|1='''GF'''(2) = ℤ<sub>2</sub>}}. 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--->
The number of distinct ''m''-by-''n'' binary matrices is equal to 2<sup>''mn''</sup>, and is thus finite.
Line 56:
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'' <sub>''i'' ''j''</sub> )}} has a transpose {{nowrap|1=''A''<sup>T</sup> = ( ''A'' <sub>''j'' ''i''</sub> ).}} 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.
Line 63:
==Logical vectors==
If ''m'' or ''n'' equals one, then the ''m'' × ''n'' logical matrix (''M''<sub>''ij''</sub>) 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'' × ''n'' [[rectangular relation]]
Line 71:
Let ''h'' be the vector of all ones. Then if ''v'' is an arbitrary logical vector, the relation ''R'' = ''v h''<sup>T</sup> 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>.
For a given relation ''R'', a maximal rectangular relation contained in ''R'' is called a concept in ''R''. Relations may be studied by decomposing into concepts, and then noting the [[heterogeneous relation#Induced concept lattice|induced concept lattice]].
{{Group-like structures}}
Consider the table of group-like structures, where "unneeded" can be denoted 0, and "required" denoted by 1, forming a logical matrix ''R''. To calculate elements of <math>RR^{\operatorname{T}}</math>, it is necessary to use the logical inner product of pairs of logical vectors in rows of this matrix. If this inner product is 0, then the rows are orthogonal. In fact, [[semigroup]] is orthogonal to [[loop (algebra)|loop]], [[small category]] is orthogonal to [[quasigroup]], and [[groupoid]] is orthogonal to [[magma]]. Consequently there are zeros in <math>RR^{\operatorname{T}}</math>, and it fails to be a [[universal relation]].
==Row and column sums==
| |||