Binatorix

In mathematics, a binatorix is a special , related to the logical matrix; the binatorix contains only 0s and 1s and has the topology of a torus, i.e. opposite edges are identified in both dimensions. A special case is that of the universal binatorix, <math>B_n</math>, which contains <u>all</u> binary submatrices of dimension n×n - there are 2 such matrices, but each will contribute only 1 'bit' to the <math>B_n</math> binatorix, which is a square m×m matrix, where m = 2 .
<math>B_2</math> has been explicitly constructed, it is a 4×4 matrix. The next candidate for an universal binatorix, <math>B_4</math>, would have 256×256 entries but it is not known if it exists.
Motivation
In the short story "Library of Babel" by Jorge Luis Borges a "universal" library is described, which contains all possible 410-page books of a certain format. This story is actually based on an earlier story by Kurd Lasswitz, called , published in German in 1901.
Reducing this to binary of a certain length, say 4 bits, there are 16 such (sub)sequences, from 0000 to 1111. To store all these (sub)sequences separately would take 6×4 = 64 bits. It is however possible to store the (sub)sequences more effectively by partially overlapping them, giving the much shorter following 16 bit sequence:
0000100110101111, identifying the beginning and end, effectively creating a ring. Such a sequence shall be called universal sequence. The universal binatorix is the 2-dimensional analogon to this kind of sequence. The universal sequences are closely related to and can be generated e.g. using linear feedback shift register.
Connection to Galois theory
How these sequences can be generated using Galois fields and linear shift registers is described in detail in
.

Main Menu

See Also

Main Menu