Binary matrix

From Wikipedia, the free encyclopedia

In mathematics, particularly matrix theory, a binary matrix or (0,1)-matrix is a matrix in which each entry is either zero or one. For example:

$\begin{pmatrix} 0 & 1\\ 1 & 0\\ \end{pmatrix}$ is a 2 × 2 binary matrix.

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) = $\mathbb{Z}_2$ . They arise in a variety of representations and have a number of more restricted special forms.

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

[edit] Examples

Examples of binary matrices are numerous:

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 square-free, n-smooth numbers can be described as a 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.