5
$\begingroup$

We say that an order $n$ permutation matrix $P$ has distance $d$ if the Hamming distance between any two $1$-elements of $P$ is at least $d$. For example, the following matrix has distance 2: $$ \begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} $$ I am interested in the following question: For which values of $d$ and $n$ do there exist such matrices? More generally, what is the (approximate) number of order $n$ permutation matrices of distance $d$?

I am absolutely sure that these objects have been studied before - there are, after all, a natural variation of error correcting codes. But under what name? Are the answers to my questions already known? I would appreciate any reference. Thank you!

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Not clear to me what the Hamming distance between a pair of ones is. $\endgroup$
    – Gerry Myerson
    Commented Jul 26, 2021 at 9:13
  • 3
    $\begingroup$ To me the Hamming distance between vectors $x$ and $y$ is the number of indices $i$ such that $x_i \neq y_i$. So here is $d \in \{0, 1, 2\}$? And for any nontrivial permutation matrix $d = 2$? $\endgroup$
    – Sean Eberhard
    Commented Jul 26, 2021 at 9:15
  • 1
    $\begingroup$ I think I understand what the OP is asking: they mean minimum taxicab distance between two cells containing 1's. Although I would say this example has distance 3. $\endgroup$
    – Sam Hopkins
    Commented Jul 26, 2021 at 13:56
  • 3
    $\begingroup$ With the interpretation from my comment above, I believe this is an interesting question, and so I want to record that I am against closing it. $\endgroup$
    – Sam Hopkins
    Commented Jul 26, 2021 at 18:01
  • 3
    $\begingroup$ @SamHopkins I think your interpretation is correct, except the OP is probably taking the $\ell_\infty$ distance instead of the taxi cab distance (this would give $d=2$). If this is what is intended, I agree the question is interesting. $\endgroup$
    – Tony Huynh
    Commented Jul 27, 2021 at 0:28

1 Answer 1

Reset to default
7
$\begingroup$

I assume that the interpretation with $\ell_\infty$-distance is correct, I.e., the distance between entries $(i,j)$ and $(i’,j’)$ is $\max\{|i-i’|,|j-j’|\}$.

If $n=k^2$, you may achieve $d=k$ but not more.

To achieve $d=k$, enumerate rows and columns from $1$ through $n$ and put ones in all cells of the form $(i, ik\mod (n+1))$, where $i=1,2,\dots,n$.

To see this is optimal, assume that $d=k+1$ is achieved. Consider ones in the first $d$ columns; they must be spread vertically at distances at least $d$ from each other, so we should have $n-1\geq d(d-1)$ which is wrong.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you explicitly define the distance you are using for completeness sake? Thanks $\endgroup$
    – kodlu
    Commented Jul 28, 2021 at 23:37
  • 2
    $\begingroup$ @kodlu I think the idea is that the distance between matrix entry $a_{ij}$ and entry $a_{rs}$ is the larger of $|i-r|$ and $|j-s|$. $\endgroup$
    – Gerry Myerson
    Commented Jul 29, 2021 at 0:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .