0
$\begingroup$

Given real matrix $M\in\{0,1\}^{n\times n}$ of rank $r$. How many $M_i\in\{0,1\}^{n\times n}$ of rank $s$ does one need to write $M'=\sum_{i=1}^ta_iM_i$ for some $a_i\in\Bbb R$ where maximum absolute value entry of $M'-M$ is $\frac{1}{4}$? We know $t=n^2$ suffices. However can we do better (say in a number as a function of $r,s$)?

For instance consider $M$ to be block diagonal matrix with $2$ blocks of $1$. $r=2$ here and $M$ can indeed be given as sum of $2$ rank $s=1$ matrices.

$\endgroup$
5
  • $\begingroup$ You can use matrices that have at most s rows nonzero. You can probably get close to r/s many summands. $\endgroup$ Feb 1, 2015 at 2:06
  • $\begingroup$ remember I have error 1/4. we probably can do better? $\endgroup$
    – Turbo
    Feb 1, 2015 at 2:14
  • $\begingroup$ Try it with a rank r identity matrix first. I think you will not be able to keep the error bound. $\endgroup$ Feb 1, 2015 at 2:36
  • $\begingroup$ Sorry I am misunderstanding. Could you explain better? $\endgroup$
    – Turbo
    Feb 1, 2015 at 2:39
  • $\begingroup$ Let M be the zero matrix except having ones in entries a_ii for i from 1 to r. Any matrix M' with entries within 1/4 of the entries of M should also have rank r or close to it. $\endgroup$ Feb 1, 2015 at 2:57

0

Your Answer

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

Browse other questions tagged or ask your own question.