Қос мәндік матрицалар және олардың қолданылуы

Matrix of binary truth values
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain 1='B' = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

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. 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 graphs, symmetric matrices to ordinary graphs, and a 1 on the diagonal corresponds to a loop at the corresponding vertex. 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 square free, n smooth numbers can be described as an m × π(n) (0, 1) matrix, where π is the prime counting function, and aij 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 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. The four valued logic of two bits, transformed by 2x2 logical matrices, forms a finite state machine. A recurrence plot and its variants are matrices that shows which pairs of points are closer than a certain vicinity threshold in a phase space.

The matrix representation of the 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 I ⊆ R, then R is a reflexive relation. 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 relations. This product can be computed in expected time O(n2). 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 They arise in a variety of representations and have a number of more restricted special forms. They are applied e. g. in XOR satisfiability. The number of distinct m by n binary matrices is equal to 2mn, and is thus finite.

Let n and m be given and let U denote the set of all logical m × n matrices. Then U has a partial order given by

In fact, U forms a Boolean algebra with the operations and & 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 1=A = (Aij) has a transpose 1=A^(T) = (Aji). Suppose A is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, contains the m × m identity matrix, and the product contains the n × n identity. As a mathematical structure, the Boolean algebra U forms a lattice ordered by inclusion; additionally it is a multiplicative lattice due to matrix multiplication. Every logical matrix in U corresponds to a binary relation. These listed operations on U, and ordering, correspond to a calculus of relations, where the matrix multiplication represents composition of relations.

If m or n equals one, then the m × n logical matrix (mij) is a logical vector or bit string. If m = 1, the vector is a row vector, and if n = 1, it is a column vector. In either case the index equaling 1 is dropped from denotation of the vector. Suppose and are two logical vectors. The outer product of P and Q results in an m × n rectangular relation

A reordering of the rows and columns of such a matrix can assemble all the ones into a rectangular part of the matrix. Let h be the vector of all ones. Then if v is an arbitrary logical vector, the relation R = v hT has constant rows determined by v. In the calculus of relations such an R is called a vector. 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, 1) matrix of type v × b with given row and column sums". This problem is solved by the Gale–Ryser theorem.