I Linear mapping of a binary vector based on its decimal value

smehdi
Messages
16
Reaction score
0
Given an ##N## dimensional binary vector ##\mathbf{v}## whose conversion to decimal is equal to ##j##, is there a way to linearly map the vector ##\mathbf{v}## to an ##{2^N}## dimensional binary vector ##\mathbf{e}## whose ##(j+1)##-th element is equal to ##1## (assuming the index starts from zero)?

For instance if ##\mathbf{v} = [1 \quad 0 \quad1]## or ##\mathbf{v} = [0 \quad 1 \quad1]## (that represent 5 and 3 in decimal, respectively), how ##\mathbf{v}## can be linearly mapped (with a unique mapper of course) to ##\mathbf{e}^\mathrm{T} = [0\quad 0\quad 0\quad 0\quad 0\quad 1 \quad 0 \quad 0]## and ##\mathbf{e}^\mathrm{T} = [0\quad 0\quad 0\quad 1 \quad 0\quad 0 \quad 0 \quad 0]##, respectively.

This is a part of an objective function of a MILP. I guess such a mapper does not exist but hopefully, I am wrong!
 
Last edited:
Physics news on Phys.org
smehdi said:
(that represent 5 and 3 in decimal, respectively)
Have you reversed the respectively ?
v = [ 1 0 1 ] = 5 → 25 → 32 ≠ [ 0 0 0 0 0 1 0 0 ]
v = [ 0 1 1 ] = 3 → 23 → 8 ≠ [ 0 0 0 1 0 0 0 0 ]
 
Baluncore said:
Have you reversed the respectively ?
v = [ 1 0 1 ] = 5 → 25 → 32 ≠ [ 0 0 0 0 0 1 0 0 ]
v = [ 0 1 1 ] = 3 → 23 → 8 ≠ [ 0 0 0 1 0 0 0 0 ]
Depends on the index of the elements in ##\mathbf{e}##.
If we start the index from left and from zeor then,
v = [ 1 0 1 ] = 5 → (make the (5+1)-th element of ##\mathbf{e}## equal to 1 where the index starts from zero and from left) → ##\mathbf{e} = [0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 1 \quad 0 \quad 0 \quad]##

Very much similar to what you told but the other way around. Actually a column vector ##\mathbf{e}^\mathrm{T}## would avoid confusion. I changed the ##\mathbf{e}## vectors in the first post to ##\mathbf{e}^\mathrm{T}##.
 
The difficulty here is, that there are no vector spaces around, only different ways of writing the same number. Binary as the usual 2-adic number, i.e. a polynomial over ##\mathbb{F}_2##, which could be seen as a vector space (of infinite dimension), and then by counting indices, which isn't even decimal, more a tally stick.
 
The worse thing is that I even do not know if a linear mapping for such a problem exists or not.
If one can prove that it exists, then half of the problem is solved. Even if I know that such a map does not exist I will start modeling my problem from scratch in a different way.

Using matrix shift and multiple transformations one can get the result but in this way, the number of shifts required for an ##N## bit number is ##2^N## shifts while the size of my problem is about ##N=20##.
 
smehdi said:
Using matrix shift and multiple transformations one can get the result but in this way, the number of shifts required for an NNN bit number is 2N2N2^N shifts while the size of my problem is about N=20N=20N=20.

You are computing an exponential; [result] = 2^[input].
For N=20 you will need a mega_bit sized variable for the result.
What do you do with the result?
Why must you expand it out to only 1 bit set in 2^N elements before it is used.

There is a binary O(N) solution that does not require 2^N single bit shifts.
Start with a [ 1 ]. Work along and up the input, if an element is set, concatenate 2^N more zero elements onto the end of the result .
Update the 2^N by doubling it in each of the N loops.
 
  • Like
Likes smehdi and fresh_42
Baluncore said:
You are computing an exponential; [result] = 2^[input].
For N=20 you will need a mega_bit sized variable for the result.
What do you do with the result?
Why must you expand it out to only 1 bit set in 2^N elements before it is used.

There is a binary O(N) solution that does not require 2^N single bit shifts.
Start with a [ 1 ]. Work along and up the input, if an element is set, concatenate 2^N more zero elements onto the end of the result .
Update the 2^N by doubling it in each of the N loops.

Well, I found the solution by shifting.
Actually, the result has ##2^N## cases equivalent to the number of combinations of ##N## binary variables. Instead of using ##2^N## binary variables for each of the ##2^N## cases, I want to use ##N## binary variables and map them to the results and find the best one.
Assuming ##\mathbf{v} = [v_N \dots v_1]## that represents the value of ##d## in decimal, the ##(d+1)##-th row of ##\mathbf{a}## is one if:
$$\mathbf{a} = \mathbf{B} \left( \prod_{i = 1}^N ( v_i \mathbf{W}_i + (1-v_i)\mathbf{I}_N ) \right)$$
in which ##\mathbf{I}_N## is an identitiy matrix with size ##N##, ##\mathbf{B}## is a matrix similar to ##\mathbf{I}_N## except its first row of the first column is zero, i.e., ##\mathbf{B} (1,1) = 0##, and ##\mathbf{W}_i## is a shifted version of ##\mathbf{I}_N## with ##2^{(i-1)}## rows down shift.
 

Similar threads

Back
Top