# Permuting matrix entries to lower rank

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.

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