Showing that $A=B+\alpha \cdot I$ is an invertible matrix Let $B$ be a non-zero random $n\times n$ matrix generated using the matlab command $B=rand(n,n)$. I need to show that $A=B+\alpha \cdot I$ is an invertible matrix, where $\alpha=\|B\|_{\infty}$. 
I am trying to show that there are no zero eigenvalues for $A$, and therefore it is invertible. 
It is clear that $\|A\|_{\infty}=2\|B\|_{\infty}$. If $\lambda$ is any eigenvalue of $B$, they using Gershgorin Theorem, we have for some $i$: $|\lambda-a_{ii}| \leq \sum_{j \neq i}|a_{ij}|<\sum_{j=1}^{n}|a_{ij}| \leq \|A\|_{\infty}=2\|B\|_{\infty}\\$.
On the other hand $|\lambda-a_{ii}|=|\lambda-b_{ii}-\|B\|_{\infty}|$. So, I obtain the inequality:$b_{ii}-\|B\|_{\infty} <\lambda < b_{ii}+3\|B\|_{\infty}$. The issue here is that $b_{ii}-\|B\|_{\infty} <0$,so the eigenvalue $\lambda$ can be equal to zero as well. I appreciate if anyone shows me another way of proving this problem or how to modify my proof . Thanks! 
 A: This is generally true provided that 


*

*$B$ is irreducible, 

*for at least one row (say $i$) of $B$ we have
$$
\sum_{j=1}^n\left|b_{ij}\right|<\alpha=\|B\|_{\infty}
$$
(obviously, it is necessary that $n\geq 2$).


Then you can use my answer to this question to show that the spectral radius of $B$ is strictly bounded by $\alpha$ from which it already easily follows that $B+\alpha I$ is nonsingular. You can find the proof of Taussky theorem required to prove the result, e.g., in her paper from 1948 (O. Taussky, "Bounds for the characteristic roots of matrices" Duke Math. J. , 15 (1948) pp. 1043–1044) or in Matrix Iterative Analysis by Varga (I think you can't find its proof in the Google Books preview though).
Condition (1) is necessary: consider $B=-\alpha I$ and $n\geq 2$ ($B$ is clearly reducible), then $B+\alpha I=0$ is obviously singular. You can of course construct a diagonal matrix which is reducible and satisfies the second condition, take, e.g., $B=\mathrm{diag}(1,2,3,4,-5)$.
Condition (2) is necessary: consider $B$ to be an $n\times n$ matrix with $-1$ in each entry. Such a $B$ is irreducible, $\alpha=\|B\|_{\infty}=n$ and we have $\sum_{j=1}^n\left|b_{ij}\right|=\alpha$ for all rows $i$. The matrix $A=B+\alpha I$ is singular (its rank is $n-1$).
If $B$ is random, you can expect both conditions to be true with a probability very close to one (I don't know how to quantify that though exactly).
A: $\|B\|_\infty$ is the maximum of the sum of each row.  Let $x$ be an eigenvector with eigenvalue $-\lambda = -\|B\|_\infty$.  Let $i = \text{arg max} |x_j|$.  Since
$$ |\lambda x_i| = |\sum_j b_{ij} x_j| \le \|B\|_\infty |x_i| $$
the inequality must be equality.  The only way this can happen is if all the $x_j$s have the same size and sign.  But then the eigenvalue must be positive.
