Linear mapping of a binary vector to a decimal-based binary vector

Question

Given a binary vector $\mathbf{v}$, where $\mathbf{v} \in \{0,1\}^N$ and the binary-to-decimal conversion of $\mathbf{v}$ is equal to $j$, is there a way to linearly map the vector $\mathbf{v}$ to a binary vector $\mathbf{e}_j$ with $\mathbf{e} \in \{0,1\}^{2^N}$, and its $(j+1)$-th element as $1$ (starting the index from zero)?

For example if $\mathbf{v} = [1 \quad 0]$ (that represents 2 in decimal) how $\mathbf{v}$ can be linearly mapped to $\mathbf{e}_3$, that is, $\mathbf{e}^\mathrm{T} = [0\quad 0 \quad 1 \quad 0]$.

The use case is in the objective function of an ILP.

Answer 1

If by "linearly map" you mean a real matrix $H$ such that $\mathbf{e} = H \mathbf{v}$ yields what you want, the answer is no. If $$\left(\begin{array}{c} 0\\ 0\\ 1\\ 0 \end{array}\right)=H \left( \begin{array}{c} 0\\ 1 \end{array}\right)$$ (encoding of 2) and $$\left(\begin{array}{c} 0\\ 1\\ 0\\ 0 \end{array}\right)=H \left( \begin{array}{c} 1\\ 0 \end{array}\right) $$(encoding of 1), then what you get for the encoding of 3 is$$\left(\begin{array}{c} 0\\ 1\\ 1\\ 0 \end{array}\right)=H \left( \begin{array}{c} 1\\ 1 \end{array}\right) = H \left( \begin{array}{c} 1\\ 0 \end{array}\right) + H \left( \begin{array}{c} 0\\ 1 \end{array}\right),$$whereas you want$$\left( \begin{array}{c} 0\\ 0\\ 0\\ 1 \end{array}\right).$$

That said, the conversion from $\mathbf{v}$ to $\mathbf{e}$ can be handled by linear constraints. Treating the components of both vectors as binary variables, you just need$$\sum_{i=1}^{2^N}e_i \le 1$$and $$\sum_{i=1}^{2^N} i \cdot e_i = \sum_{j=1}^N 2^{j-1} \cdot v_j.$$

Answer 2

The answer can be found by shifting.

Let $\mathbf{v}=[v_1 \dots v_N]$ be a binary vector whose conversion to decimal is equal to $j$. Vector $\mathbf{e}_{j+1}$ is all zero vector except at $(j+1)$-th position if $$ \mathbf{e}_{j+1} = \mathbf{A} \left( \prod_{i=1}^{N} \left( v_i \mathbf{S}_i + (1-v_i)\mathbf{I} \right) \right) \mathbf{e_1} $$

In which $\mathbf{e}_j$ is a binary column vector with length $2^N$ with the $j$-th element equal to $1$, $\mathbf{I}$ is an identity matrix with size $2^N$, and $\mathbf{A}$ is a $2^N \times 2^N$ matrix and all its are elements equal to $\mathbf{I}$ except the first row and the first column as $\mathbf{A}(1,1) = 0$. Matrix $\mathbf{S}_i$ is a $2^N \times 2^N$ shift matrix with subdiagonal $2^{N-i}$ level down-shifted. More precisely, $\mathbf{S}_i(j+2^{N-i},j)=1$ for $1\leq j \leq 2^N-2^{N-i}$.

In the equation above, $\mathbf{S}_i$ shifts the ones in $\mathbf{A}$ to left if $v_i =1$, otherwise $\mathbf{A}$ is multiplied by $\mathbf{I}$ and remains unchanged. By a proper number of shifts, the first column of $\mathbf{A}$ will have $1$ at its $(j+1)$-position and finally $\mathbf{e_1}$ extracts it.

P.S: It cannot be used in an ILP if the $v_{i(1\leq i \leq N)}$ in $\mathbf{v}$ are the variables as the multiplication of $\mathbf{S}_{i(1\leq i \leq N)}$ makes the problem non-linear.