# Permuting the columns of a 0/1-matrix to avoid short segments

Consider an $$n \times n$$ table with $$n$$ stars such that each row contains at most $$\log n$$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment short if its length is at most $$\log n$$. It is not difficult to show that under a random permutation of the columns, the number of short segments is at most $$O(\log^4n)$$. Can you design a deterministic $$O(n)$$ time algorithm that takes the positions of $$n$$ stars as an input and outputs a permutation of the columns such that the number of short segments is at most $$O(n/\log n)$$?

The algorithm below runs in time $$O(n\log n)$$, but not $$O(n)$$. On the other hand, it permutes the columns in such a way that there are only $$O(\log^2n \cdot\log\log n)$$ short segments in the end.

Let us at first describe $$O(n\log n)$$-time algorithm for the case when $$n + 1$$ is prime. Then we may identify columns $$\{1, 2, \ldots, n\}$$ with elements of $$(\mathbb{F}_{n + 1})^*$$. The idea is to consider permutations of the form $$x\mapsto \gamma x$$ for $$\gamma\in(\mathbb{F}_{n + 1})^*$$. We will show that at least one $$\gamma$$ is good for us and how to find such $$\gamma$$ in $$O(n\log n)$$ time.

We start by finding $$x^{-1}$$ for every $$x\in(\mathbb{F}_{n + 1})^*$$. For each $$x$$ this takes $$O(\log n)$$ time by Euclidean algorithm, in total $$O(n\log n)$$.

Then assume that positions of stars are $$(a_1, b_1), \ldots, (a_n, b_n).$$ Let $$L$$ be the list of all $$(i, j)$$ such that $$i\neq j$$ and $$a_i = a_j$$ (pairs of stars which are from the same row). The size of $$L$$ is $$O(t_1^2 + \ldots + t_n^2)$$, where $$t_i$$ is the number of stars from the $$i^{th}$$ row. Since $$t_i\le\log n$$, we have $$|L| = O(t_1^2 + \ldots + t_n^2) = O((t_1 + \ldots + t_n)\cdot \log n) = O(n\log n).$$

We then create an array $$M$$ of size $$n$$, where $$M[\rho]$$ is equal to the number of $$(i, j)\in L$$ s.t. $$\rho = b_i - b_j \pmod{n + 1}$$. Clearly, computing $$M$$ takes $$O(|L|) =O(n\log n)$$ time.

Then we define another array $$W$$ of size $$n$$. Namely, $$W[\gamma]$$ is defined as follows $$W[\gamma] = \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho].$$

Now let us prove that $$W[\gamma]$$ is an upper bound on the number of short segments after permuting columns according to $$x\mapsto \gamma x$$. Indeed, the number of short segments is at most the number of $$(i, j)\in L$$ such that for some $$u, v\in\{1, 2, \ldots, n\}, u\neq v, |u - v| \le \log n$$ it holds that $$\gamma b_i = u\pmod{n + 1}, \gamma b_j = v\pmod{n + 1}$$. In turn, this is at most the number of $$(i, j) \in L$$ s.t. for some $$k\in [-\log n, \log n], k\neq 0$$ it holds that $$\gamma(b_i - b_j) = k \pmod{n + 1}$$. This is exactly $$\sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} \sum\limits_{\substack{\rho:\, \gamma\rho = k\\\pmod{n + 1}}} M[\rho]$$.

Now it only remains to note that $$W[\gamma] = \sum\limits_{\substack{k = -\log n \\ k\neq 0}}^{\log n} M[\gamma^{-1} k]$$ Here we use the fact that $$n + 1$$ is prime. Since we have all $$\gamma^{-1}$$ precomputed, it takes only $$O(n\log n)$$ time to compute $$W$$. On the other hand for fixed $$k$$ all $$\gamma^{-1} k$$ are different, i.e. $$\sum\limits_{\gamma} W[\gamma] \le 2\log n \sum\limits_{\rho} M[\rho] = 2\log n \cdot |L| = O(n\log^2 n)$$. Hence there exists $$\gamma$$ such that $$W[\gamma] = O(n\log^2 n/n) = O(\log^2 n)$$. We find any such $$\gamma$$ and permute columns according to $$x\mapsto \gamma x$$.

The problem in general case is that now not all $$\gamma$$'s from $$\mathbb{Z}_{n + 1}\setminus \{0\}$$ are reversible. However, there are $$\Omega(n/\log\log n)$$ of them, so we start our algorithm by finding all reversible $$\gamma\in\mathbb{Z}_{n + 1}\setminus \{0\}$$ in $$O(n\log n)$$ time (once again, Euclidean algorithm helps). We then do exactly the same thing but only for reversible $$\gamma$$'s. In the end we will have a slightly worse upper bound on the smallest $$W[\gamma]$$, namely $$O(\log^2(n)\log\log n)$$ (because we take into account only $$\Omega(n/\log\log n)$$ of $$\gamma$$'s).

• Sasha, the bit-size of the input is $n\log n$, yes, but we assume implicitly a RAM model (roughly, basic arithmetic operations with $O(\log n)$-length numbers cost $O(1)$). – Alexander S. Kulikov Dec 28 '18 at 11:53