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

Improve this question
$\endgroup$
2
  • $\begingroup$ Btw, why the extremal-combinatorics tag? Is there an interesting application you have in mind? $\endgroup$
    – Felix Goldberg
    Commented 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
    Commented Feb 3, 2015 at 6:34

2 Answers 2

Reset to default
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.

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .