Logical matrix

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a

.

Matrix representation of a relation

If R is a

indexed sets

X and Y (so 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

${\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}}$

In order to designate the row and column numbers of the matrix, the sets X and Y are indexed with positive

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 logical matrix is

${\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},}$

which includes a diagonal of ones, since each number divides itself.

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.
• 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 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 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.^[1]
• The
  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.

Some properties

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

of the matrix representations of these relations. This product can be computed in expected time O(n²).^[2]

Frequently, operations on binary matrices are defined in terms of

${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$. They arise in a variety of representations and have a number of more restricted special forms. They are applied e.g. in .

The number of distinct m-by-n binary matrices is equal to 2^mn, and is thus finite.

Lattice

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

given by

${\displaystyle \forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.}$

In fact, U forms a

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 A = (A_ij) has a transpose A^T = (A_ji). Suppose A is a logical matrix with no columns or rows identically zero. Then the matrix product, using Boolean arithmetic, ${\displaystyle A^{\operatorname {T} }A}$ contains the m × m identity matrix, and the product ${\displaystyle AA^{\operatorname {T} }}$ 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.^[3]

Logical vectors

Group-like structures

	Totalityα	Associativity	Identity	Divisibilityβ	Commutativity
Partial magma	Unneeded	Unneeded	Unneeded	Unneeded	Unneeded
Semigroupoid	Unneeded	Required	Unneeded	Unneeded	Unneeded
Small category	Unneeded	Required	Required	Unneeded	Unneeded
Groupoid	Unneeded	Required	Required	Required	Unneeded
Magma	Required	Unneeded	Unneeded	Unneeded	Unneeded
Quasigroup	Required	Unneeded	Unneeded	Required	Unneeded
Unital magma	Required	Unneeded	Required	Unneeded	Unneeded
Loop	Required	Unneeded	Required	Required	Unneeded
Semigroup	Required	Required	Unneeded	Unneeded	Unneeded
Associative quasigroup	Required	Required	Unneeded	Required	Unneeded
Monoid	Required	Required	Required	Unneeded	Unneeded
Commutative monoid	Required	Required	Required	Unneeded	Required
Group	Required	Required	Required	Required	Unneeded
Abelian group	Required	Required	Required	Required	Required
^α The closure axiom, used by many sources and defined differently, is equivalent. ^β Here, divisibility refers specifically to the quasigroup axioms.

If m or n equals one, then the m × n logical matrix (m_ij) is a logical vector or

. 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 ${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$ and ${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$ are two logical vectors. The

${\displaystyle m_{ij}=P_{i}\land Q_{j}.}$

A reordering of the rows and columns of such a matrix can assemble all the ones into a rectangular part of the matrix.^[4]

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

A particular instance is the universal relation ${\displaystyle hh^{\operatorname {T} }}$.

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

induced concept lattice

.

Consider the table of group-like structures, where "unneeded" can be denoted 0, and "required" denoted by 1, forming a logical matrix ${\displaystyle R.}$ To calculate elements of ${\displaystyle RR^{\operatorname {T} }}$, 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,

. Consequently there are zeros in ${\displaystyle RR^{\operatorname {T} }}$, and it fails to be a

universal relation

.

Row and column sums

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. The sum of point degrees equals the sum of block degrees.^[5]

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".^[5] This problem is solved by the Gale–Ryser theorem.

See also

• List of matrices
• Binatorix (a binary De Bruijn torus)
• Bit array
• Redheffer matrix
• Truth table
• Three-valued logic

Notes

References

• ISBN 978-0-521-86565-4
• Richard A. Brualdi & Herbert J. Ryser (1991), Combinatorial Matrix Theory. Encyclopedia of Mathematics and its Applications, 39. Cambridge University Press, Cambridge, 1991.
  ISBN 0-521-32265-0
• ISBN 978-1-58488-510-8
  , § 31.3, Binary Matrices
• Kim, Ki Hang (1982), Boolean Matrix Theory and Applications,
  ISBN 978-0-8247-1788-9
• H. J. Ryser (1957), "Combinatorial properties of matrices of zeroes and ones", Canadian Journal of Mathematics 9: 371–7.
• H.J. Ryser (1960), "Traces of matrices of zeroes and ones", Canadian Journal of Mathematics 12: 463–76.
• H.J. Ryser (1960), "Matrices of Zeros and Ones", Bulletin of the American Mathematical Society 66: 442–64.
• D. R. Fulkerson (1960) "Zero-one matrices with zero trace", Pacific Journal of Mathematics 10; 831–6
• D. R. Fulkerson & H. J. Ryser (1961), "Widths and heights of (0, 1)-matrices", Canadian Journal of Mathematics 13: 239–55.
• MR0159700

External links

Wikimedia Commons has media related to Binary matrix.

• "Logical matrix", Encyclopedia of Mathematics, EMS Press, 2001 [1994]