Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric).

Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix.

Case $1$: $M+W\in\{0,1\}^{n\times n}$.

Could there be tight upper, lower bounds on $rank(M+W)-rank(M)$ depending on only $r$?

Case $2$: $M-W\in\{0,1\}^{n\times n}$.

Could there be tight upper, lower bounds on $rank(M-W)-rank(M)$ depending on only $r$?

Above can be reduced to rank $2$ matrices $W$ with symmetric cases.

Matrix $$0\mbox{ }M'$$$$M\mbox{ }0$$ is symmetric and has rank $2r$.

Matrix $$0\mbox{ }W'$$$$W\mbox{ }0$$ is symmetric and has rank $2$.

  • $\begingroup$ Btw, why the extremal-combinatorics tag? Is there an interesting application you have in mind? $\endgroup$ – Felix Goldberg Feb 3 '15 at 6:33
  • $\begingroup$ Motivation comes from combinatorics. All 0-1 objects as far as I know have connections there. $\endgroup$ – 1.. Feb 3 '15 at 6:34

THe interlacing theorem tells us that for rank 1 $W$ the eigenvalues of $M \pm W$ are sandwiched between those of $M$ (see Corollary 4.3.9 here). Therefore $null(M)-1 \leq nullity(M \pm W) \leq null(M)+1$ and this is equivalent to $r(M)-1 \leq r(M \pm W) \leq r(M)+1$.

These bounds are tight. For the case of graphs there are some detailed studies of when the different cases obtain.

| cite | improve this answer | |
  • $\begingroup$ @Turbo It's proved in the reference I gave (the standard one on the subject). $\endgroup$ – Felix Goldberg Feb 3 '15 at 6:34
  • $\begingroup$ @Turbo The magic works because it's a rank 1 update. It's possible to use interlacing for rank $k$ updates, but the bounds get progressively weaker, of course. The proof for rank $k$ is just an inductive application of Corollary 4.3.9 $k$ times (decompose $W$ as the sum of $k$ matrices of rank $1$). $\endgroup$ – Felix Goldberg Feb 3 '15 at 6:36
  • $\begingroup$ @Turbo Yes, all you need is Hermitianness of $M$ and $W$. But as I said, having $\{0,1\}$ helps to perhaps pinpoint precisely which of the three cases occurs. $\endgroup$ – Felix Goldberg Feb 3 '15 at 6:37
  • $\begingroup$ @Turbo In that case, things are open again.... :( If you want to discuss the specific case, feel free to email me. $\endgroup$ – Felix Goldberg Feb 3 '15 at 6:39
  • $\begingroup$ Problem reduces to rank $2$ in symmetric case. $\endgroup$ – 1.. Feb 3 '15 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.