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

[smehdi]

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!

 

[Baluncore]

(that represent 5 and 3 in decimal, respectively)

Have you reversed the respectively ?
v = [ 1 0 1 ] = 5 → 2⁵ → 32 ≠ [ 0 0 0 0 0 1 0 0 ]
v = [ 0 1 1 ] = 3 → 2³ → 8 ≠ [ 0 0 0 1 0 0 0 0 ]

 

[smehdi]

Have you reversed the respectively ?
v = [ 1 0 1 ] = 5 → 2⁵ → 32 ≠ [ 0 0 0 0 0 1 0 0 ]
v = [ 0 1 1 ] = 3 → 2³ → 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}$.

 

[fresh_42]

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.

 

[smehdi]

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$.

 

[Baluncore]

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.

 

[smehdi]

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.