2
$\begingroup$

Note: sorry for the long post. My question is in the second quote.

A few years ago, I saw the following problem on Facebook. I would like to ask a generalised version of this problem. Here is the original problem:

A number of people sits at a roundtable. Each of them puts a coin in front of them with either head or tail facing up. Each of them is going to flip the coin in front of them (or not flip the coin) according to the following rules:

Each of them checks the coin in front of the person to the right. If the coin to the right is tail up, flip the coin in front to the other side; if the coin to the right is head up, do not flip the coin in front. This flipping is done simultaneously, that is, they simultaneously check the coin to the right, and simultaneously flip (or not flip) the coin in front.

After flipping the coins, they can repeat the above checking and flipping again, and again, until possibly all coins end up with head up, which no more flipping will happen, or maybe they cannot end up with all coins head up at all.

For what number of people $n$ would it happen that no matter initially the people put the coins tail up or head up, they will always end up with all coins head up after those flipping?

The answer is when $n$ is a power of $2$ (except $2^0$). Here is how a found it:

The simultaneous state of the coins (whether they are head up or tail up) is modelled by a column vector of $n$ entries, with each entry being $0$ or $1$. Say we index each person as $1,2,\dots,n$ (a certain person is number $1$, and the guy to the left is number $2$, and the guy to the left of number $2$ is number $3$, and so on, with the guy to the right of number $1$ is number $n$). The $i$-th entry of the vector being $0$ means the coin in front of the $i$-th guy is head up, while being $1$ means the coin is tail up.

As a note, the entries are to be interpreted as elements in $\Bbb Z/2\Bbb Z$.

The checking and flipping process is modelled by the matrix $I+P$, where $I$ is the $n\times n$ identity matrix, and $P$ is the $n\times n$ permutation matrix where the sub-diagonal entries are $1$, the top-right entry is $1$, and all else entries are $0$. Again, $I+P$ is a matrix whose entries are elements in $\Bbb Z/2\Bbb Z$. A round of checking and flipping is modelled by multiplying the matrix $I+P$ to the column vector modelling the states of coins.

It takes some effort to realise that any initial vectors will end up becoming zero vector after multiplying $I+P$ enough of times, if and only if $I+P$ is nilpotent. So we are to find out for what $n$ is $I+P$ nilpotent.

We try to square the matrix $I+P$, and see that $(I+P)^2=I+2P+P^2=I+P^2$ because $2P$ is the zero matrix (the entries are from $\Bbb Z/2\Bbb Z$). We keep squaring to see $(I+P)^{2^m}=I+P^{2^m}$. So we want $I+P^{2^m}=0$ for large enough $m$, or equivalently $P^{2^m}=I$ ($I=-I$ in $\Bbb Z/2\Bbb Z$).

We know that this is possible if and only if $n$ is a power of $2$, because the order of $P$ is $n$, so that $n$ must divide $2^m$ if we want $P^{2^m}=I$. So $I+P$ is nilpotent if and only if $n$ is a power of $2$.

Now I generalise the problem to the following:

Consider the $n\times n$ matrix $I-P$ whose entries are elements in $\Bbb Z/k\Bbb Z$ for some integer $k\ge3$, where $I$ is the identity matrix, and $P$ is the permutation matrix whose sub-diagonal entries are $1$, top-right entry is $1$, and all else are $0$. Find necessary and sufficient conditions on $n$ such that $I-P$ is nilpotent.

When $k$ is a prime, the above method easily generalises to show that necessary and sufficient condition is that $n$ is a power of $k$.

Raise $I-P$ to the power of the prime number $k$ consecutively to see that $$(I-P)^k=I+C_1^k(-P)+C_2^k(-P)^2+\cdots+C_{k-1}^k(-P)^{k-1}+(-P)^k=I-P^k,$$$$(I-P)^{k^m}=I-P^{k^m},$$ because $C_r^k=0$ in $\Bbb Z/k\Bbb Z$ for each of $r=1,2,\dots,k-1$ due to $k$ being prime (the prime factor $k$ in the numerator $k!$ is not cancelled by any factor in $(k-r)!r!$).

We want $I-P^{k^m}=0$ for large enough $m$, and this is possible if and only if $n$ is a power of $k$.

When $k$ is composite, the above trick does not work. I only made a few conjectures on what $n$ and $k$ works. Before that, note the following observation: if for a standard basis vector $e_i$, $(I-P)^me_i=0$ for large enough $m$, then $I-P$ is nilpotent. This is due to that $I-P$ is self-similar by $P$: $P^{-1}(I-P)P=I-P$, so that $(I-P)^me_i=0$ means $$(I-P)^me_{i+1}=(I-P)^mPe_i=PP^{-1}(I-P)^mPe_i=P(I-P)^me_i=0$$ as well, and $(I-P)^me_{i+2}=0$, and so on.

With this, we can do some faster checking whether $I-P$ is nilpotent. I checked that when $k=4$, $n=2$ and $n=4$ are solutions (that $I-P$ is nilpotent would be nilpotent), and when $k=9$, $n=3$ is a solution. I conjecture that when $k$ is a square of a prime, $n$ being a power of the prime is a necessary and sufficient condition for $I-P$ to be nilpotent. But I don't have any idea about other composite numbers.

$\endgroup$
1
$\begingroup$

Suppose $k = p^{e}$ is a prime power. If $I - P$ is nilpotent modulo $k$, then it is nilpotent modulo $p$, so that $n$ has to be a power of $p$. Now if $(I - P)^{p^{s}} = 0$ modulo $p$ for some $s$, this means all entries of $(I - P)^{p^{s}}$ are multiples of $p$, and thus $(I - P)^{p^{s e}} = 0$ modulo $k$.

Suppose now $k$ is not a prime power, and $p$ and $q$ are two different primes dividing $k$. If $I - P$ is nilpotent modulo $k$, then it is nilpotent modulo $p$, and nilpotent modulo $q$, so $n$ would have to be a power of both $p$ and $q$...

$\endgroup$
  • $\begingroup$ So I can work with integer entries first and then take modulo entry-wise, and the result would be the same? $\endgroup$ – edm Apr 5 at 5:29
  • $\begingroup$ Yes, because reduction modulo $k$ is a homomorphism of rings. $\endgroup$ – Andreas Caranti Apr 5 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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