Putnam 2008, Problem B-6

Let $n$ and $k$ be positive integers. Say that a permutation $\sigma$ of $\{1, 2, \ldots, n\}$ is $k$-limited if $|\sigma(i) - i| \leq k$ for all $i$. Prove that the number of $k$-limited permutations of $\{1, 2, \ldots, n\}$ is odd if and only if $n \equiv 0$ or $1 \pmod{2k+1}$.


Solution:
In all solutions, let $F_{n,k}$ be the number of $k$-limited permutations of $\{1, \ldots, n\}$.

**First solution:** (by Jacob Tsimerman) Note that any permutation is $k$-limited if and only if its inverse is $k$-limited. Consequently, the number of $k$-limited permutations of $\{1, \ldots, n\}$ is the same as the number of $k$-limited involutions (permutations equal to their inverses) of $\{1, \ldots, n\}$.

We use the following fact several times: the number of involutions of $\{1, \ldots, n\}$ is odd if $n = 0,1$ and even otherwise. This follows from the fact that non-involutions come in pairs, so the number of involutions has the same parity as the number of permutations, namely $n!$.

For $n \leq k+1$, all involutions are $k$-limited. By the previous paragraph, $F_{n,k}$ is odd for $n = 0,1$ and even for $n = 2, \ldots, k+1$.

For $n > k+1$, group the $k$-limited involutions into classes based on their actions on $k+2, \ldots, n$. Note that for $C$ a class and $\sigma \in C$, the set of elements of $A = \{1, \ldots, k+1\}$ which map into $A$ under $\sigma$ depends only on $C$, not on $\sigma$. Call this set $S(C)$; then the size of $C$ is exactly the number of involutions of $S(C)$. Consequently, $|C|$ is even unless $S(C)$ has at most one element. However, the element $1$ cannot map out of $A$ because we are looking at $k$-limited involutions. Hence if $S(C)$ has one element and $\sigma \in C$, we must have $\sigma(1) = 1$. Since $\sigma$ is $k$-limited and $\sigma(2)$ cannot belong to $A$, we must have $\sigma(2) = k+2$. By induction, for $i = 3, \ldots, k+1$, we must have $\sigma(i) = k+i$.

If $n < 2k+1$, this shows that no class $C$ of odd cardinality can exist, so $F_{n,k}$ must be even. If $n \geq 2k+1$, the classes of odd cardinality are in bijection with $k$-limited involutions of $\{2k+2, \ldots, n\}$, so $F_{n,k}$ has the same parity as $F_{n-2k-1,k}$. By induction on $n$, we deduce the desired result.

**Second solution:** (by Yufei Zhao) Let $M_{n,k}$ be the $n \times n$ matrix with
$$(M_{n,k})_{ij} = \begin{cases} 1 & |i-j| \leq k \\ 0 & \text{otherwise}. \end{cases}$$

Write $\det(M_{n,k})$ as the sum over permutations $\sigma$ of $\{1, \ldots, n\}$ of $(M_{n,k})_{1\sigma(1)} \cdots (M_{n,k})_{n\sigma(n)}$ times the sign of $\sigma$. Then $\sigma$ contributes $\pm 1$ to $\det(M_{n,k})$ if $\sigma$ is $k$-limited and $0$ otherwise. We conclude that
$$\det(M_{n,k}) \equiv F_{n,k} \pmod{2}.$$

For the rest of the solution, we interpret $M_{n,k}$ as a matrix over the field of two elements. We compute its determinant using linear algebra modulo $2$.

We first show that for $n \geq 2k+1$,
$$F_{n,k} \equiv F_{n-2k-1,k} \pmod{2},$$
provided that we interpret $F_{0,k} = 1$. We do this by computing $\det(M_{n,k})$ using row and column operations. We will verbally describe these operations for general $k$, while illustrating with the example $k = 3$.

To begin with, $M_{n,k}$ has the following form.
$$\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & | & \emptyset \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & | & \emptyset \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & | & \emptyset \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & | & \emptyset \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & | & ? \\ \hline \emptyset & \emptyset & \emptyset & ? & ? & ? & ? & | & * \end{pmatrix}$$

In this presentation, the first $2k+1$ rows and columns are shown explicitly; the remaining rows and columns are shown in a compressed format. The symbol $\emptyset$ indicates that the unseen entries are all zeroes, while the symbol $?$ indicates that they are not. The symbol $*$ in the lower right corner represents the matrix $F_{n-2k-1,k}$.

We will preserve the unseen structure of the matrix by only adding the first $k+1$ rows or columns to any of the others.

We first add row $1$ to each of rows $2, \ldots, k+1$.
$$\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & | & \emptyset \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ \hline \emptyset & \emptyset & \emptyset & ? & ? & ? & ? & | & * \end{pmatrix}$$

We next add column $1$ to each of columns $2, \ldots, k+1$.
$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & | & \emptyset \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ \hline \emptyset & \emptyset & \emptyset & ? & ? & ? & ? & | & * \end{pmatrix}$$

For $i = 2$, for each of $j = i+1, \ldots, 2k+1$ for which the $(j,k+i)$-entry is nonzero, add row $i$ to row $j$.
$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & | & \emptyset \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & | & ? \\ \hline \emptyset & \emptyset & \emptyset & ? & ? & ? & ? & | & * \end{pmatrix}$$

Repeat the previous step for $i = 3, \ldots, k+1$ in succession.
$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & | & \emptyset \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & | & ? \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & | & ? \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & | & ? \\ \hline \emptyset & \emptyset & \emptyset & ? & ? & ? & ? & | & * \end{pmatrix}$$

Repeat the two previous steps with the roles of the rows and columns reversed. That is, for $i = 2, \ldots, k+1$, for each of $j = i+1, \ldots, 2k+1$ for which the $(j,k+i)$-entry is nonzero, add row $i$ to row $j$.
$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & | & \emptyset \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & | & \emptyset \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & | & ? \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & | & ? \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & | & ? \\ \hline \emptyset & \emptyset & \emptyset & ? & ? & ? & ? & | & * \end{pmatrix}$$

We now have a block diagonal matrix in which the top left block is a $(2k+1) \times (2k+1)$ matrix with nonzero determinant (it results from reordering the rows of the identity matrix), the bottom right block is $M_{n-2k-1,k}$, and the other two blocks are zero. We conclude that
$$\det(M_{n,k}) \equiv \det(M_{n-2k-1,k}) \pmod{2},$$
proving the desired congruence.

To prove the desired result, we must now check that $F_{0,k}, F_{1,k}$ are odd and $F_{2,k}, \ldots, F_{2k,k}$ are even. For $n = 0, \ldots, k+1$, the matrix $M_{n,k}$ consists of all ones, so its determinant is $1$ if $n = 0,1$ and $0$ otherwise. (Alternatively, we have $F_{n,k} = n!$ for $n = 0, \ldots, k+1$, since every permutation of $\{1, \ldots, n\}$ is $k$-limited.) For $n = k+2, \ldots, 2k$, observe that rows $k$ and $k+1$ of $M_{n,k}$ both consist of all ones, so $\det(M_{n,k}) = 0$ as desired.

**Third solution:** (by Tom Belulovich) Define $M_{n,k}$ as in the second solution. We prove $\det(M_{n,k})$ is odd for $n \equiv 0,1 \pmod{2k+1}$ and even otherwise, by directly determining whether or not $M_{n,k}$ is invertible as a matrix over the field of two elements.

Let $r_i$ denote row $i$ of $M_{n,k}$. We first check that if $n \equiv 2, \ldots, 2k \pmod{2k+1}$, then $M_{n,k}$ is not invertible. In this case, we can find integers $0 \leq a < b \leq k$ such that $n + a + b \equiv 0 \pmod{2k+1}$. Put $j = (n + a + b)/(2k+1)$. We can then write the all-ones vector both as
$$\sum_{i=0}^{j-1} r_{k+1-a+(2k+1)i}$$
and as
$$\sum_{i=0}^{j-1} r_{k+1-b+(2k+1)i}.$$

Hence $M_{n,k}$ is not invertible.

We next check that if $n \equiv 0,1 \pmod{2k+1}$, then $M_{n,k}$ is invertible. Suppose that $a_1, \ldots, a_n$ are scalars such that $a_1 r_1 + \cdots + a_n r_n$ is the zero vector. The $m$-th coordinate of this vector equals $a_{m-k} + \cdots + a_{m+k}$, where we regard $a_i$ as zero if $i \notin \{1, \ldots, n\}$. By comparing consecutive coordinates, we obtain
$$a_{m-k} = a_{m+k+1} \quad (1 \leq m < n).$$

In particular, the $a_i$ repeat with period $2k+1$. Taking $m = 1, \ldots, k$ further yields that
$$a_{k+2} = \cdots = a_{2k+1} = 0$$
while taking $m = n-k, \ldots, n-1$ yields
$$a_{n-2k} = \cdots = a_{n-1-k} = 0.$$

For $n \equiv 0 \pmod{2k+1}$, the latter can be rewritten as
$$a_1 = \cdots = a_k = 0$$
whereas for $n \equiv 1 \pmod{2k+1}$, it can be rewritten as
$$a_2 = \cdots = a_{k+1} = 0.$$

In either case, since we also have
$$a_1 + \cdots + a_{2k+1} = 0$$
from the $(k+1)$-st coordinate, we deduce that all of the $a_i$ must be zero, and so $M_{n,k}$ must be invertible.

**Remark:** The matrices $M_{n,k}$ are examples of banded matrices, which occur frequently in numerical applications of linear algebra. They are also examples of Toeplitz matrices.