1
$\begingroup$

Suppose $A$ is an $n \times n$ matrix with all 1 on the diagonal. What is the sharp bound $\epsilon(n)$ so that $A$ is invertible if all off-diagonal entries of $A$ have absolute value less than $\epsilon(n)$? Obviously $\epsilon(n) > 0$ exists, because as all off-diagonal elements go to zero, $A$ approaches the identity matrix which is invertible.

$\endgroup$
1
$\begingroup$

Let $S$ be the set of non-negative real numbers $r$ for which if $|a_{i,j}|\lt r$ for all $i\neq j$, then $A$ is invertible. We have that $S\supset \left(0,\frac 1{n-1}\right]$ (because in this case $A$ is diagonal dominant, hence invertible). We can't hope more (take $a_{i,j}:=\frac 1{n-1}$; then $A$ is not invertible).

$\endgroup$
  • $\begingroup$ Thanks, I guess what I'm missing is how this notion of "diagonal dominant" implies invertibility. Otherwise the question would be fairly obvious, as soon as we realize $A$ is not invertible when $a_{i,j} = 1/(n-1)$ for $i \neq j$. $\endgroup$ – user2566092 Sep 27 '13 at 18:02
  • $\begingroup$ I also tried setting off-diagonal elements to $1/2$ for a $3 \times 3$ matrix with 1 on the diagonal, and I got that the matrix was invertible? (determinant = $1/2$) I think maybe the off-diagonal elements should be set to $-1/(n-1)$? Then the sum of the rows is $0$ so $A$ is not invertible. $\endgroup$ – user2566092 Sep 27 '13 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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