 Logical matrix

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0,1) matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets.
Contents
Matrix representation of a relation
If R is a binary relation between the finite indexed sets X and Y (so R ⊆ X×Y), then R can be represented by the adjacency matrix M whose row and column indices index the elements of X and Y, respectively, such that the entries of M are defined by:
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 of X and j ranges from 1 to the cardinality of Y. (See the entry on indexed sets for more detail.)
Example
The binary relation R on the set {1, 2, 3, 4} is defined so that aRb holds if and only if a divides b evenly, with no remainder. For example, 2R4 holds because 2 divides 4 without leaving a remainder, but 3R4 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 Boolean matrix is:
Other examples
 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 (mathematics)
 A design matrix in analysis of variance is a (0,1)matrix with constant row sums.
 An adjacency matrix in graph theory is a matrix whose rows and columns represent the vertices and whose entries represent the edges of the graph. The adjacency matrix of a simple, undirected graph is a binary symmetric matrix with zero diagonal.
 The biadjacency matrix of a simple, undirected bipartite graph is a (0,1)matrix, and any (0,1)matrix arises in this way.
 The prime factors of a list of m squarefree, nsmooth numbers can be described as a m×π(n) (0,1)matrix, where π is the primecounting function and a_{ij} is 1 if and only if the jth prime divides the ith number. This representation is useful in the quadratic sieve factoring algorithm.
 A bitmap image containing pixels in only two colors can be represented as a (0,1)matrix in which the 0's represent pixels of one color and the 1's represent pixels of the other color.
Some properties
The matrix representation of the equality relation on a finite set is an identity matrix, that is, one whose entries on the diagonal are all 1, while the others are all 0.
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 two relations is equal to the matrix product of the matrix representations of these relation.
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 GF(2) = ℤ_{2}. They arise in a variety of representations and have a number of more restricted special forms.
The number of distinct mbyn binary matrices is equal to 2^{mn}, and is thus finite.
See also
 List of matrices
 Redheffer matrix
References
Categories: Boolean algebra
 Matrices
Wikimedia Foundation. 2010.
Look at other dictionaries:
Matrix  получить на Академике рабочий купон на скидку Строительный Двор или выгодно matrix купить с бесплатной доставкой на распродаже в Строительный Двор
Matrix multiplication — In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n by m matrix and B is an m by p matrix, the result AB of their multiplication is an n by p matrix defined only if… … Wikipedia
Logical graph — A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic.In his papers on qualitative logic , entitative graphs , and existential graphs , Peirce… … Wikipedia
matrix — (n.) late 14c., uterus, womb, from O.Fr. matrice womb, uterus, from L. matrix (gen. matricis) pregnant animal, in L.L. womb, also source, origin, from mater (gen. matris) mother (see MOTHER (Cf. mother) (n.1)). Sense … Etymology dictionary
Logical equality — For the corresponding concept in combinational logic, see XNOR gate. XNOR Logic Gate Symbol Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus. It… … Wikipedia
Logical implication — In logic and mathematics, logical implication is a logical relation that holds between a set T of formulae and a formula B when every model (or interpretation or valuation) of T is also a model of B . In symbols,# T models B, # T Rightarrow B # T … Wikipedia
Logical biconditional — In logic and mathematics, the logical biconditional (sometimes known as the material biconditional) is the logical connective of two statements asserting p if and only if q , where q is a hypothesis (or antecedent) and p is a conclusion (or… … Wikipedia
Matrix (mathematics) — Specific elements of a matrix are often denoted by a variable with two subscripts. For instance, a2,1 represents the element at the second row and first column of a matrix A. In mathematics, a matrix (plural matrices, or less commonly matrixes)… … Wikipedia
Logical framework approach — This article is about the management tool. For the automated theorem proving approach, see logical framework. The Logical Framework Approach (LFA) is a management tool mainly used in the design, monitoring and evaluation of international… … Wikipedia
Logical Disk Manager — The Logical Disk Manager (diskmgmt.msc) is an implementation of a logical volume manager for Microsoft Windows NT, developed by Microsoft and Veritas Software. It was introduced with the Windows 2000 operating system, and is supported in Windows… … Wikipedia
Logical clock — A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system.Logical clock algorithms of note are: * Lamport timestamps, which are monotonically increasing software counters * Vector clocks, that… … Wikipedia