7
$\begingroup$

This question arises from my research in finite regular semigroups but I've shown it is equivalent to a purely combinatorial question about binary arrays.

Let M be a finite m x n table with binary entries. We shall call a specific position (i,j) in M a member. We identify M with its set of members. Each member then has an entry, which is either 0 or 1.

Two members (i,j) and (k,l) are related if the entries at (i,l) and (k,j) are both 1, in which case we write (i,j) R (k,l).

A permutation f on M is called a (permutation) matching if (i,j) R f(i,j) for all (i,j) in M.

My question is, if M has a permutation matching, is it necessarily the case that M has a matching that is an involution?

$\endgroup$
8
  • $\begingroup$ It is unclear how the matrix arrangement applies. I could use a similar structure involving a set N (=M) and a subset P of N and consider all permutations of N which fix P. In this role, your question boils down to: if P is even, can I permute N and fix P with an involution, in which case the answer is yes. (Actually, I see a problem. If (k,l) has value 0, what matching exists that acts on (k,l)?) Gerhard "Did You Mean Something Else?" Paseman, 2019.02.26. $\endgroup$ Feb 26, 2019 at 19:00
  • $\begingroup$ What if $m=n=3$, and there are exactly 3 members on diagonal, diagonal elements are equal to 0 and other entries equal to 1? $\endgroup$ Feb 26, 2019 at 21:14
  • $\begingroup$ @MaxAlekseyev: No, in group theory an involution is an element of order $2$, while in other fields of mathematics, it may be the identity too. $\endgroup$ Feb 27, 2019 at 21:28
  • 1
    $\begingroup$ I think what I have written is unambiguous but may not be easy to digest. Take two members, (i,j) and (k,l). Their rows and columns define a rectangle (which could degenerate to a line or even a point it the two members are equal). These two members are related iff the entries in the other two corners of the rectangle are both 1. The question is not whether or not there is a permutation that maps each member to a related member (I can answer that) but IF there is such a permutation, can we find such a permutation that is an involution. $\endgroup$ Feb 27, 2019 at 21:42
  • 1
    $\begingroup$ Do you understand why the corresponding graph can not contain an odd connected component consisting only of zeroes? It would be an obvious violation of the existence of an involution. I can prove this only when $mn$ is odd (which is quite annoying): consider the multigraph which joins by an edge the vertices $(x_1,(f(y))_2)$ and $(y_1,(f(x))_2)$ for any two entries $x,y$ (indices correspond to the first and second coordinate, respectively). Degree of each vertex equals $mn$, thus if $mn$ is odd, any loopless connected component must be even. Maybe this graph is useful in general case. $\endgroup$ Mar 7, 2019 at 9:30

1 Answer 1

2
$\begingroup$

Not an answer, but a nice sufficient condition for existence of an involution when $m=n$:

If $m=n$ and $\operatorname{perm}(M)>0$, then $M$ has a matching that is an involution.

Proof. Since $\operatorname{perm}(M)>0$, there exists a permutation $\pi$ such that $$M_{1,\pi(1)}=M_{2,\pi(2)}=\dots=M_{n,\pi(n)}=1.$$ Then $f((i,j)):=(\pi^{-1}(j),\pi(i))$ is a matching and an involution.

$\endgroup$
1
  • $\begingroup$ And also if the whole array is partitioned onto direct products of the form $\{a_1,\dots,a_k\}\times \{b_1,\dots,b_k\} $ with $M_{a_i, b_i}=1$. $\endgroup$ Mar 5, 2019 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.