Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and recover the low-rank structure? As follow-ups, what about with sparsity assumptions on the matrix or when $k$ is very small ($1$ or $2$, for instance)?

As a simple example, take a matrix where every column is the standard basis vector $e_1$. An adversary could then permute the entries of this matrix into the identity, which has full rank.

Note that the low-rank solution could be highly non-unique, so any minimal rank structure would suffice.

  • $\begingroup$ Might be easier to permute rows and columns rather than entries $\endgroup$ Commented Feb 18, 2023 at 16:16
  • $\begingroup$ Do you have typical values of $m,n,k$ for the instances you want to solve in practice? $\endgroup$
    – D.W.
    Commented Feb 18, 2023 at 23:47
  • $\begingroup$ @D.W. The instances I'm considering are skew-symmetric (so m = n) with minimal rank 2. $\endgroup$ Commented Feb 19, 2023 at 19:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.