Skip to main content
10 of 10
deleted 44 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times n}\}?$$

What is a good upper bound to $$\max_{M\in\Bbb\{0,1\}^{n\times n},\mathsf{rank}(M)=r}\min_{Q\in\mathscr{D}[M]}\mathsf{rank}(Q)?$$

Turbo
  • 13.9k
  • 1
  • 27
  • 76