Given a permutation matrix 'the question is to decide if there is a permutation matrix representing a cycle within Hamming distance $d$ from given matrix'. Is there an efficient algorithm for it?
Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Hamming distance $O(1)$ from given matrix? If not what is the worst case Hamming distance?
Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Euclidean distance $O(1)$ per row and per column from given matrix? If not what is the worst case Euclidean distance $O(1)$ per row and per column?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ What's a "cycle matrix"? Is that a permutation matrix, where the permutation is a cycle? Also, what does "it" refer to? Grammatically, it must refer to "permutation matrix", but I don't know how to interpret "efficient algorithm for a permutation matrix". $\endgroup$– Gerry MyersonCommented Aug 23, 2021 at 2:37
-
$\begingroup$ You're more likely to get an answer if you interact with users trying to help you. $\endgroup$– Gerry MyersonCommented Aug 27, 2021 at 12:40
-
$\begingroup$ I corrected based on the comment. $\endgroup$– TurboCommented Aug 27, 2021 at 14:53
-
$\begingroup$ Concerning (3), a permutation matrix has a single $1$ in each row and in each column, so the Euclidean distance per row and per column between two permutation matrices is always either zero or $\sqrt2$. Concerning (2), it seems to me that the $n\times n$ identity matrix has Hamming distance $2n$ from any cycle matrix, and that's the worst case. Concerning (1), if the cycle representation of a given permutation matrix has $k$ disjoint cycles, then I think the (Hamming-) nearest cycle is at distance $2(k-1)$. $\endgroup$– Gerry MyersonCommented Aug 29, 2021 at 12:36
Add a comment
|