# Rank changes with matrix edits

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$.

• Btw, why the extremal-combinatorics tag? Is there an interesting application you have in mind? – Felix Goldberg Feb 3 '15 at 6:33
• Motivation comes from combinatorics. All 0-1 objects as far as I know have connections there. – 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$.
• @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$). – Felix Goldberg Feb 3 '15 at 6:36
• @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. – Felix Goldberg Feb 3 '15 at 6:37
• Problem reduces to rank $2$ in symmetric case. – 1.. Feb 3 '15 at 7:03