The conjecture that Theorem MainTechnical covers all rank-deficient permutations

Let VV be a generic Toeplitz matrix and let PP be a permutation matrix. Theorem MainTechnical applies to permutations satisfying one of the following conditions: there exists an integer 0td20\leq t\leq\frac{d}{2} such that

rt:=rank((PJt)t+1:n,1:n)d2t,r_t:=\operatorname{rank}\big((P-J^t)_{t+1:n,1:n}\big)\leq d-2t,

or there exists an integer d2t<0-\frac{d}{2}\leq t<0 such that

rt:=rank((P(J)t)1:n+t,1:n)d+2t.r_t:=\operatorname{rank}\big((P-(J^\top)^{-t})_{1:n+t,1:n}\big)\leq d+2t.

Rank-deficient permutation coverage conjecture. For VV generic Toeplitz, every permutation PP for which

rank[V,PV]<2d\operatorname{rank}\left[V,\,PV\right]<2d

is covered by Theorem MainTechnical, that is, satisfies one of these conditions. The conjecture concerns the unresolved characterization of the permutations relevant to Question rank-P; it was verified by exhaustive computation for n=2dn=2d and d5d\leq5, while a complete answer remains elusive.

Sources & referencesView supporting material

Primary source

Xin Hong and Manolis C. Tsakiris, “Toeplitz Unlabeled Sensing”, arXiv:2502.12778 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.