Let $A$ be an $n \times n$ matrix with real entries and let $B$ be the random matrix whose $(i,j)$ entry is $$B_{i,j}=v_{i,j}A_{i,j}$$ where the $v_{i,j}$ are i.i.d Bernoulli random variables with $P(v_{i,j} = 1 ) =\rho$ and $P(v_{i,j} = 0) = 1-\rho$.

That is, $B$ is formed by setting each entry of $A$ to 0 with probability $1-\rho$.

Is there any result about how the norm of $B$ compares with the norm of $A$ in expectation? I'm particularly interested in the maximum row sum norm $\|B\|_{\infty} = \max_{i}\{\sum_{j}|B_{i,j}|\}$

It seems obvious that $\mathbb{E}(\|B\|_{\infty}) < \|A\|_{\infty}$ as long as $\rho > 0$, and I'm looking for some references which attempt quantify this.

  • 1
    $\begingroup$ I don't think you can say a whole lot for general $A$. For example, if there's a single column with $1$'s only and all other entries are zero, then $\|B\|=\|A\|$ with prob $1-(1-\rho)^n$, so the expectation doesn't go down by much. $\endgroup$ Mar 12, 2015 at 4:50
  • $\begingroup$ Thanks for this example. It seems that you can use the same argument for the identity matrix, and then you can conclude that $P(\|A\| = \|B\|)$ is going to be high for other matrix norms which specialize to the the largest absolute element on diagonal matrices. $\endgroup$
    – ttb
    Mar 14, 2015 at 7:45

1 Answer 1


There is a recent paper related to your question: Bandeira, Afonso S., and Ramon van Handel. "Sharp nonasymptotic bounds on the norm of random matrices with independent entries." arXiv preprint arXiv:1408.6185 (2014). In your question, the random matrix has independent entries, where each entry is a two-point distribution with different means. The special case that each entry has the same distribution (i.e. i.i.d. case) is rather well-understood; but as argued in the paper above, when the entries are independent but not identical, all previous bounds are loose. They derive an (almost) tight bound. That paper only deals with the spectral norm, not the maximum row sum norm. Nevertheless, some ideas might be applicable to other norms.


You must log in to answer this question.

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