B Operator that returns unique number of binary matrix

[Mayhem]

If we have an arbitrary square matrix populated randomly with 1s and 0s, is there an operator which will return a unique number for each configuration of 1s and 0s in the matrix?
i.e. an operation on
$$ \begin{pmatrix}
1 &0 &0 \\
1 & 0 & 1\\
0 & 1 & 0
\end{pmatrix} $$

would return something different than

$$ \begin{pmatrix}
1 &0 &0 \\
0 & 1 & 1\\
0 & 0 & 0
\end{pmatrix} $$
or any configuration, an ideally for an arbitrary square matrix.

 

[PeroK]

What do you mean by operator? The set of matrices do not form a vector space, so you can't define a linear operator on them.

You could just map the entries to the digits of a 9-digit number (including leading zeroes).

 

[Mayhem]

What do you mean by operator? The set of matrices do not form a vector space, so you can't define a linear operator on them.

You could just map the entries to the digits of a 9-digit number (including leading zeroes).

Function was maybe a better word (the real word, really). So if me get $M_{B,i}$ denote an arbitrary binary matrix of dimensions n x n, then $f(M_{B,i}) = k$ where $k$ is unique for all $i$.

 

[PeroK]

Function was maybe a better word (the real word, really). So if me get $M_{B,i}$ denote an arbitrary binary matrix of dimensions n x n, then $f(M_{B,i}) = k$ where $k$ is unique for all $i$.

Just write the digits out in a given order.
$$ f: \begin{pmatrix}
1 &0 &0 \\
1 & 0 & 1\\
0 & 1 & 0
\end{pmatrix} \rightarrow 100101010$$

 

[Mayhem]

Just write the digits out in a given order.
$$ f: \begin{pmatrix}
1 &0 &0 \\
1 & 0 & 1\\
0 & 1 & 0
\end{pmatrix} \rightarrow 100101010$$

Yes, I thought of that. and it's good for small matrices, but becomes very tricky when you are dealing with large matrices (think, you'll need n² digits to represent one matrix) and that's not to mention leading zeroes.

So thank you, there is a way. But is there a more elegant way?

 

[Mayhem]

Actually, I'm stupid. We can just represent the output in a different base than base 2, which would generate a unique number and can be easily converted to give information about the matrix.
My bad, thanks!

 

[berkeman]

So thank you, there is a way. But is there a more elegant way?

We can just represent the output in a different base than base 2, which would generate a unique number and can be easily converted to give information about the matrix.

That sounds like it should work. We do something similar to compress medium-length binary strings into Base-33 notation, for example.

One other technique I was going to suggest is to use a Linear Feedback Shift Register (LFBSR) to compress the long binary string into a shorter binary string (say 16b or 32b long). This technique is used in communications encoding to generate a Cyclic Redundancy Check (CRC) word that is appended to the communication string and used for error detection purposes. With the CRC technique, though, there is a very small chance that the CRC could be generated by two different communication strings. So if you don't need to limit the length of your "compressed" version of the binary matrix, your idea would be more reliable.

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Base-33 info here: https://en.wikipedia.org/wiki/List_of_numeral_systems#By_type_of_notation

 

[Mayhem]

That sounds like it should work. We do something similar to compress medium-length binary strings into Base-33 notation, for example.

One other technique I was going to suggest is to use a Linear Feedback Shift Register (LFBSR) to compress the long binary string into a shorter binary string (say 16b or 32b long). This technique is used in communications encoding to generate a Cyclic Redundancy Check (CRC) word that is appended to the communication string and used for error detection purposes. With the CRC technique, though, there is a very small chance that the CRC could be generated by two different communication strings. So if you don't need to limit the length of your "compressed" version of the binary matrix, your idea would be more reliable.

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Base-33 info here: https://en.wikipedia.org/wiki/List_of_numeral_systems#By_type_of_notation

To be honest, I was just looking for inspiration on cool mathematical ways to program a snake game lol

 

[Mark44]

The set of matrices do not form a vector space, so you can't define a linear operator on them.

Unless there's something I'm forgetting, the matrices in this thread do form a vector space, provided that the field is the set {0, 1}, element-wise addition is done modulo 2, and scalar multiplication is also done modulo 2.

 

[Office_Shredder]

There are $2^{n^2}$ distinct choices of matrix. So you need to use at least the numbers 1 through $2^{n^2}$ which the binary representation does. Any smaller representation will have collisions

 

[Mayhem]

There are $2^{n^2}$ distinct choices of matrix. So you need to use at least the numbers 1 through $2^{n^2}$ which the binary representation does. Any smaller representation will have collisions

I'll take your word on that. That said, the fact that mapping it to digits and converting to decimal gives a unique number is quite cool!

 

[Svein]

Or you could use Gödel numbering: Number the elements in the matrice in a unique way, then form the product \prod_{j=1}^{N}p_{j}^{aj}where p_j is the j'th prime and aj is the j'th number in the matrix.

 

[jbriggs444]

I'll take your word on that. That said, the fact that mapping it to digits and converting to decimal gives a unique number is quite cool!

It is a unique number even before mapping it to decimal. The conversion to decimal makes it a numeral.

 

[Mark44]

The conversion to decimal makes it a numeral.

I don't believe that a number has to be in decimal form to be a numeral. E.g., 0x12, 18, 10010₂, and XVIII are all numerals that are different representations of decimal 18.

 

[jbriggs444]

I don't believe that a number has to be in decimal form to be a numeral. E.g., 0x12, 18, 10010₂, and XVIII are all numerals that are different representations of decimal 18.

Right. But the value that results from taking the set of bits in the 3 x 3 matrix as a sequence and interpreting them in place value notation is a number. The result of converting that result to a decimal string is a numeral.