A question about the paper "The Condition Number of a Randomly Perturbed Matrix"

Question

My question pertains to this paper by Terence Tao and Van Vu, https://arxiv.org/abs/math/0703307

Both my questions pertain to the argument presented in this paper in its section 6 (page 5). We are looking at a $n-$dimensional square random matrix $M_n$ satisfying the conditions stated through Definitions 2.15, Definition 2.17 and Theorem 2.18 on page 3.

Now we are saying that lets assume the existence of a unit vector $v \in \mathbb{R}^n$ such that for some $B >10$ we have, $\Vert M_n v\Vert < n^{-B}$. The vector $\tilde{v}$ is created by truncating each coordinate of $v$ to the nearest multiple of $n^{-B-2}$. So if I understand this correctly then we have that for each coordinate $i$, $\vert v_i - \tilde{v}_i\vert \leq \frac{1}{2n^{B+2}}$. This is now supposed to imply a number of things which arent clear to me,

• The paper claims, $0.9 \leq \Vert \tilde{v}\Vert \leq 1.1$. Why?

  If I just think directly then we have, $\Vert \tilde{v}\Vert \leq \Vert v + (\tilde{v}-v)\Vert \leq \Vert v\Vert + \sqrt{n} \frac{1}{2n^{B+2}} = 1 + \frac{n^{-B-\frac{3}{2}}}{2}$.For this to match the claim we need, $\frac{n^{-B-\frac{3}{2}}}{2} = 0.1$. But this is now incompatible with the initial statement that we need $B>10$. What am I missing?

• The paper claims that the following is also true that, $\Vert M_n \tilde{v}\Vert \leq 2n^{-B}$. Why?

  Just as above if I again think just directly then we have, that $\Vert M_n \tilde{v}\Vert = \Vert M_n(v+(\tilde{v}-v))\Vert \leq \Vert M_n v \Vert + \Vert M_n (\tilde{v}-v)\Vert \leq n^{-B} + \Vert M_n \Vert \frac{n^{-B-\frac{3}{2}}}{2}$. One way this can be compatible with the claim is if we have, $\Vert M_n \Vert \leq 2n^{1.5}$.

  One might now go back to the ``boundedness" part of Definition 2.15 and the first bullet point of Theorem 2.18 on page 3 to see that with probability $1$ the entries of the matrix $M_n$ are integers bounded as $n^C$ for some constant $C>0$. This gives by Frobenius norms, $\Vert M_n \Vert \leq \Vert M_n \Vert_F \leq n^{1+C}$. So for compatibility with the previous bound we need, $n^{1+C} \leq 2n^{1.5}$. But then such an equation is now an upperbound on the constant $C$ and that is not something that Theorem 2.18 enforced. What am I missing?

Answer 1

1. One does not need to have $n^{-B-3/2}/2$ to be equal to $0.1$, it is enough for it to be less than or equal to $0.1$, which is certainly the case for $n$ large enough.

2. Thanks for pointing out this typo (or more precisely, set of typos) in this paper. As you point out, the exponents here are adapted to the case of small $C$ (in particular $C=0$, which is the most frequent case in applications) and require some adjustment for large $C$. [We do remark several times in the paper that the precise exponents are not to be taken too seriously.] Basically, if one replaces all occurrences of $n^2$ in this argument with, say, $n^{2(1+C)}$ (and makes some similar adjustments to some other similar factors such as $n^{-4}$) then this issue will be avoided.

It is also worth mentioning that the results in this paper have been superseded by subsequent stronger results, e.g.

Tao, Terence; Vu, Van, Smooth analysis of the condition number and the least singular value, Math. Comput. 79, No. 272, 2333-2352 (2010). ZBL1253.65067.