15
$\begingroup$

Consider the matrix $2\times2$ symmetric matrix: $$ A_2=\begin{pmatrix} 1 & a_1 \\ a_1 & 1\end{pmatrix}. $$ It's clear that the restriction $|a_1|<1$ implies that $\det(A_2)>0$. Moreover, this is the best restriction on the modulus of $a_1$ with this property, for $\det\begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}=0$.

Now, consider the $3\times3$ symmetric matrix: $$ A_3= \begin{pmatrix} 1 & a_1 & a_2\\ a_1 & 1 & a_3 \\ a_2 & a_3 & 1\end{pmatrix} $$ We have $\det(A_3)=1+2a_1a_2a_3-a_1^2-a_2^2-a_3^2$. Then, the restriction $|a_i|<1/2$ implies that $$ \det(A_3)>1-2(1/8)-3(1/4)=0. $$ Moreover, this is the best restriction on the modulus of the $a_i$'s with this property, for $$ \det\begin{pmatrix} 1 & -1/2 & -1/2\\ -1/2 & 1 & -1/2 \\ -1/2 & -1/2 & 1\end{pmatrix}=0. $$

Now we consider the general case. Let $A_n=[a_{i,j}]_{1\leq 1,j\leq n}$ be a matrix such that $a_{i,j}=a_{j,i}$ for every $1\leq i,j\leq n$ and $a_{i,i}=1$ for every $1\leq i\leq n$. What is the greatest number $\alpha_n$ satisfying $$ \max_{i\neq j}|a_{i,j}| < \alpha_n\ \ \Rightarrow\ \ \det A_n>0? $$

I was able to prove that $\alpha_n\leq 1/(n-1)$, by showing that the determinant of the following $n\times n$ matrix is $0$: $$ M_n=\begin{pmatrix} 1 & -\dfrac{1}{n-1} & -\dfrac{1}{n-1} & \dots & -\dfrac{1}{n-1} \\ -\dfrac{1}{n-1} & 1 & -\dfrac{1}{n-1} & \cdots & -\dfrac{1}{n-1} \\ -\dfrac{1}{n-1} &-\dfrac{1}{n-1}& 1 &\dots & -\dfrac{1}{n-1} \\ \vdots & \vdots & \vdots &\ddots & \vdots \\ -\dfrac{1}{n-1} & -\dfrac{1}{n-1}& -\dfrac{1}{n-1}&\dots & 1\end{pmatrix}. $$

One way to see that $\det(M_n)=0$ is to pick $v_1,...,v_n\in\mathbb R^n$ such that $\|v_i\|=1$ for every $i\in\{1,...,n\}$ and $\{v_1,...,v_n\}$ is the set of vertices of a regular $(n-1)$-symplex. One may se by induction that $\langle v_i, v_j \rangle=-1/(n-1)$ for every $i\neq j$. Therefore, $$ M_n=\left[\langle v_i, v_j \rangle\right]_{1\leq i, j \leq n}. $$ Since $v_1,...,v_n$ are the vertices of an $(n-1)$-symplex, they are linearly dependent, so $$ \det\left(\left[\langle v_i, v_j \rangle\right]_{1\leq i, j \leq n}\right)=0. $$

My intuition says that $\alpha_n=1/(n-1)$. However, I'm not able to prove that $\alpha_n \geq 1/(n-1)$. Any suggestions would be very helpful. Thanks in advice.

$\endgroup$
1
  • 6
    $\begingroup$ It's easier to note that the all ones vector is an eigenvector of $M_{n}$ with eigenvalue $0.$ $\endgroup$ Jun 4, 2017 at 9:03

1 Answer 1

17
$\begingroup$

Your guess is correct. If the elements outside the diagonal have absolute values less than $1/(n-1)$, the matrix has 'diagonal dominance', thus it is nonsingular.

To make the answer self-contained, I give a proof. If $x=(x_1,\dots,x_n)^t$ satisfies $Ax=0$, take $k$ such that $|x_k|$ is maximal and look at $\sum a_{ki}x_i$. The summand $a_{kk}x_k$ has greater absolute value than all other summands altogether, thus the total sum is non-zero. A contradiction.

So, determinant of $A$ is non-zero. And it is non-zero if we multiply all elements outside diagonal by $t\in [0,1]$, call such a new matrix $A(t)$. Since $f(t)=\det A(t)$ is continuous, does not vanish on $[0,1]$ and $f(0)=1$, we get $f(1)>0$ as desired.

$\endgroup$
3
  • $\begingroup$ I'm sorry I can't follow the argument. Could you be more specific? $\endgroup$ Jun 4, 2017 at 7:26
  • $\begingroup$ Ok, I did some research on the term diagonal dominance, then I found out the concept of strictly diagonal dominant matrix and the Levy–Desplanques theorem. Thank you very much. $\endgroup$ Jun 4, 2017 at 7:35
  • $\begingroup$ @AndréPorto , can you say something about these concepts in your OP or in a new answer? It seems interesting. $\endgroup$
    – Amir Sagiv
    Jun 4, 2017 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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