2
$\begingroup$

Let $X$ be a finite set. A bijective map $f: X\to X$ can be represented by a subset $A$ of $X\times X$, such that for every element $a\in X$ there is only one element $b$ so that $(a,b)\in A$, and similarly the other way around.

Now we want to generalize this, and look at subsets of multiple products of the set $X$, and considering different ways of how a subset can represent a bijective map.

The simplest new case is when we have $X^4$, and we want to get bijective maps $X^2\to X^2$. The problem to solve is to find all subsets $A\in X^4$, so that it describes bijective maps in two ways. If we denote variables as $(a,b,c,d)\in X^4$ then the subset $A$ should be such that it gives bijective maps in the directions $(a,b)\to (c,d)$ but also $(a,d)\to (c,b)$.

What is the name for such a subset and the different ways of organizing it into bijective maps? I don't really know where to look for such solutions.

The more difficult problem is when we want to go to even bigger products. A problem which came up is to look at subsets of $X^6$ and consider three ways of organizing the subset into a bijective map $X^3\to X^3$. Using variables $(a_1,a_2,a_3,b_1,b_2,b_3)$ we would want to have a bijective map in the directions $(a_1,a_2,a_3)\to (b_1,b_2,b_3)$, $(b_1,a_2,a_3)\to (a_1,b_2,b_3)$ and $(a_1,b_2,a_3)\to (b_1,a_2,b_3)$. If you wish, these are ``partial transpose'' operations, and we would want to have a bijective map in all directions.

A trivial solution is when the map $(a_1,a_2,a_3)\to (b_1,b_2,b_3)$ is the identity on $X^3$, this map satisfies also the other requirements. Are there any other solutions? Is this known, perhaps in some other disguise?

Update: If we know solution to the problem on $X^4$, then it can be used to get a trivial solution on $X^6$: the map $(a_1,a_2,a_3)\to (b_1,b_2,b_3)$ should be for example identity on the first variable, and the non-trivial bijective map on the second and third. But how to construct solutions that are not of this form?

Improve this question
$\endgroup$
4
  • $\begingroup$ What would be an example of a subset of $X^4$ or $X^6$, say with $X=\{u,v\}$ or $\{u,v,w\}$, representing a bijection on $X^2$ (or $X^3$) but one of the partial transpositions is not a bijection? $\endgroup$ Commented Nov 18, 2021 at 16:04
  • 1
    $\begingroup$ The simplest counter-example is the permutation map on $X^2$. So for any pair $(a,b)$ the map gives $(b,a)$. It is clearly a bijection. But if you do the partial transpose like I wrote, you don't even get a well-defined map! $\endgroup$ Commented Nov 18, 2021 at 17:09
  • $\begingroup$ If I understand correctly, with $X = \{u,v\}$, a map on $X^2$ that does work is the cyclic map on $X^2$ given by $(u,u) \mapsto (u,v) \mapsto (v,u) \mapsto (v,v) \mapsto (u,u)$. Transposing $(a,b) \mapsto (c,d)$ into $(a,d) \mapsto (c,b)$ gives $(u,v) \mapsto (u,u) \mapsto (v,v) \mapsto (v,u) \mapsto (u,v)$, the inverse of the original map. Another one that doesn't work is $(u,u) \mapsto (u,u)$, $(u,v) \mapsto (v,u) \mapsto (v,v) \mapsto (u,v)$. $\endgroup$ Commented Nov 18, 2021 at 20:14
  • $\begingroup$ Yes, I agree! Let $N$ be the cardinality of $X$. An other example for $N=2$ is $(u,v)\leftrightarrow (v,u)$ and $(u,u)\leftrightarrow (v,v)$ So we have two 2-cycles. I have more examples for $N=3$ and $N=4$, obviously there are more possibilities there. So far I have no non-trivial examples for the problem on $X^3$, perhaps I will just write a brute force code first, for $N=2$. $\endgroup$ Commented Nov 19, 2021 at 6:13

1 Answer 1

Reset to default
2
$\begingroup$

You might want to check out the concept of an orthogonal array Specifically a $t-(v,k,1)$ orthogonal array which has $k$ columns and $v^t$ rows filled with $v$ symbols in such a way that any $t$ columns contain each ordered $t$-tuple once. That article gives a $2- (4,5,1)$ example.

In your setup that is a $16$ element subset of $X^5$ with $X=\{1,2,3,4\}$ so that you can read it $120$ ways to get a bijection from $X^2$ to $X^2$ such as by interpreting $(a,b,c,d,e)$ as $(e,c)\rightarrow (a,d)$.

LATER

Here are a couple of solutions for $X^6$ , The first might satisfy you or you might feel it is just your identity example in disguise:

Take three permutations $\alpha,\beta,\gamma$ of $X$ and then these sextuples $$(u,v,w,\alpha u,\beta v, \gamma w)$$ This gives what you want and one more:
Using variables $(a_1,a_2,a_3,b_1,b_2,b_3)$ we would have a bijective map in the directions $(a_1,a_2,a_3)\to (b_1,b_2,b_3)$, $(b_1,a_2,a_3)\to (a_1,b_2,b_3)$ and $(a_1,b_2,a_3)\to (b_1,a_2,b_3)$. And also $(a_1,a_2,b_3)\to (b_1,b_2,a_3)$.

In the case that $\alpha,\beta$ and $\gamma$ are the identity map, all four of these are the identity map on $X^3.$

If you take odd $n$ and the sextuples $$(u,v,w,u+v,v+w,w+u) \mod n$$ for $X=\{0,1,\dots,n-1\}.$ You get less than a full orthogonal array but $17$ of the $20$ ways to pick three positions work, including the ones you want.

This is essentially multiplying vectors $\left( \begin{array}{c} u\\ v\\ w \end{array} \right)$in $X^3$ by the matrix $$M=\left(\begin{array}{cccccc} 1&0&0\\ 0&1&0 \\0&0&1\\ 1&1&0\\ 0&1&1\\ 1&0&1 \end{array}\right)$$

The choices which work correspond to the triples of rows giving a matrix with an inverse $\mod n.$ That should generalize.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, but how is this a bijection? Or even a single valued map? In your example, a given pair $(e,c)$ would appear many times. $\endgroup$ Commented Nov 19, 2021 at 8:34
  • $\begingroup$ @BalázsPozsgay No, there are 16 $5$-tuples and and if you look at positions $5$ and $3$ , in other words , $(e,c)$, each of the $16$ possibilities appears exactly once. $\endgroup$ Commented Nov 19, 2021 at 9:03
  • $\begingroup$ Yes, I see now! This is great now, such tables would give examples also for my more complicated case with 3+3 elements. Do you know a good reference for how to construct such solutions? $\endgroup$ Commented Nov 19, 2021 at 9:55
  • $\begingroup$ I think these arrays will give many good solutions for my problem. But not all. The condition for the orthogonal array is more restrictive than what I need. I just have a selection for possible sets of collumns for which the property should hold. I don't require that it holds for any pair or any triplet of column. Thanks in any case this is very useful!! $\endgroup$ Commented Nov 19, 2021 at 10:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.