bitmatrix

A bitmatrix is a matrix whose entries are bits, i.e., elements of {0,1}. In many mathematical and computational contexts it is treated as a matrix over the binary field GF(2).

Operations on a bitmatrix are performed modulo 2: addition is XOR, and multiplication is performed modulo 2 as well. Consequently, Gaussian elimination, row echelon form, and rank computations are carried out over GF(2).

Bitmatrices arise as adjacency matrices of graphs, and as generator or parity-check matrices in coding theory. They provide compact representations of binary linear transformations and are used in image and signal processing for binary data, as well as in certain cryptographic linear layers.

Storage and performance: dense bitmatrices store entries as bits; sparse representations save memory for matrices with many zeros. Modern implementations pack bits into machine words and use bitwise operations to accelerate arithmetic. The asymptotic cost of Gaussian elimination over GF(2) is O(n^3) in the worst case, with practical improvements from bitset techniques.

Example: a small bitmatrix can represent a binary linear transformation or a graph’s adjacency structure; for instance, a 3x3 matrix with a specific pattern of ones and zeros encodes a particular mapping or connectivity.

See also: Boolean matrix; GF(2); binary matrix; generator matrix; parity-check matrix; adjacency matrix.