# Affine images of sets in $\mathbb{F}_2^n$ in connection with permutations of coordinates

$$\textbf{Preliminaries:}$$ Let $$\mathbb{F}_2=\{0,1\}$$ be the binary field and $$\mathbb{F}_2^n$$ be the vector space of all $$n$$-tuples $$\{(x_1,x_2,\dots,x_n)~|~ x_i\in \mathbb{F}_2,1\leq i\leq n\}$$ over $$\mathbb{F}_2$$. For any $$x\in\mathbb{F}_2^n$$ we define Hamming weight $$wt(x)$$ as the number of non zero components in $$x$$ (i.e., the size of supp(x) =$$\{i \in \{1,2\dots, n\}; x_i \neq 0\}$$, the support of vector x). Let $$S_n$$ denote the set of all permutations on $$\{1,2,\dots,n\}$$. If $$\pi \in S_n$$ and $$x=(x_1,x_2,\dots,x_n)\in \mathbb{F}_2^n$$ then we define $$\pi(x)=(x_{\pi(1)},x_{\pi(2)},\dots,x_{\pi(n)})$$. Let $$GL(n,\mathbb{F}_2)$$ denotes the set of all non-singular matrices over $$\mathbb{F}_2$$.

$$\textbf{Problem}$$. Let $$T_1$$ and $$T_2$$ be any two subsets of $$\mathbb{F}_2^n$$ such that $$\lvert T_1\rvert=\lvert T_2\rvert$$ (i.e., both have the same cardinality) and has the same number of elements of weight $$t$$, $$1\leq t\leq n$$ (this also imply $$\lvert T_1\rvert=\lvert T_2\rvert$$). Suppose there does not exist any $$\pi \in S_n$$ such that $$\pi(T_{1})=\{\pi(x)~|~x\in T_{1}\}=T_{2}$$. Then prove or disprove that there does not exist any $$A\in GL(n,\mathbb{F}_2)$$ and $$b\in \mathbb{F}_2^n$$ (considering all vectors of $$\mathbb{F}_2^n$$ as column vectors) such that $$\{Ax+b~|~ x\in T_{1}\}=T_2$$.

Thanks in advance for any help, please.

• I have taken the liberty to change your "title" "interesting problem in linear algebra" into the present one. This is important to attract people now and in the future. Do you agree ? Commented Mar 24, 2023 at 19:26

The problem can be disproved by taking the following example.

Consider $$n=3$$ and $$T_1=\{(1,0,0),(1,0,1)\}$$, $$T_2=\{(0,1,0),(1,0,1)\}$$. There is no $$\pi$$ with $$\pi(T_1)=T_2$$, but for $$A=\left(\begin{matrix}0&0&1\\1&0&1\\0&1&1\end{matrix}\right)$$ we have $$AT_1=T_2.$$

• This matrix is not invertible.
– JBL
Commented Mar 25, 2023 at 0:48
• On the other hand, since $T_1$ and $T_2$ are linearly independent then there certainly is an invertible matrix that sends $T_1$ to $T_2$, so the counter-example can be rescued.
– JBL
Commented Mar 25, 2023 at 0:49
• Good catch! I will modify the example accordingly :)
– C614
Commented Mar 25, 2023 at 0:52
• I wonder if the problem will be correct under additional assumptions, maybe that every weight is present in $T_i$, or that $|T_i|\geq n$.
– C614
Commented Mar 25, 2023 at 0:57
• Thanks a lot for giving solution. Now I have changed the problem accordingly. Commented Mar 25, 2023 at 3:35