De Bruijn torus
Encyclopedia
In combinatorial
mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn
, is an array
of symbols from an alphabet (often just 0 and 1) that contains every m-by-n matrix
exactly once. It is a torus
because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence
, which can be considered a special case where n is 1 (one dimension).
One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given m and n. It is known that these always exist when n = 1, since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever m = n.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn
Nicolaas Govert de Bruijn
Nicolaas Govert de Bruijn is a Dutch mathematician, affiliated as professor emeritus with the Eindhoven University of Technology. He received his Ph.D. in 1943 from Vrije Universiteit Amsterdam....
, is an array
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of symbols from an alphabet (often just 0 and 1) that contains every m-by-n matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
exactly once. It is a torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence
De Bruijn sequence
In combinatorial mathematics, a k-ary De Bruijn sequence B of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly...
, which can be considered a special case where n is 1 (one dimension).
One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given m and n. It is known that these always exist when n = 1, since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever m = n.