3
$\begingroup$

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

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ @Turbo It's proved in the reference I gave (the standard one on the subject). $\endgroup$ Feb 3, 2015 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$ Feb 3, 2015 at 6:36
  • 1
    $\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$ Feb 3, 2015 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$ Feb 3, 2015 at 6:39
  • $\begingroup$ Problem reduces to rank $2$ in symmetric case. $\endgroup$
    – Turbo
    Feb 3, 2015 at 7:03
0
$\begingroup$

There are similar interlacing theorems for singular values, so the bound is $\pm1$ even for the non-symmetric case. For a more elementary proof, $range(M+W) \subseteq range(M)+range(W)$, so comparing dimensions $rk(M+W)\leq rk(M) + 1$. Switching the roles of $M$ and $M+W$ yields the reverse inequality.

$\endgroup$

Your Answer

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

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