The conjecture that Theorem MainTechnical covers all rank-deficient permutations

About 1 year old · traced to

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 0≤t≤d20\leq t\leq\frac{d}{2} such that

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

or there exists an integer −d2≤t<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 d≤5d\leq5, while a complete answer remains elusive.

References

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.