Conditions on Coefficients that a Matrix is Nonsingular
Problem 72
(a) Let $A=(a_{ij})$ be an $n\times n$ matrix. Suppose that the entries of the matrix $A$ satisfy the following relation.
\[|a_{ii}|>|a_{i1}|+\cdots +|a_{i\,i-1}|+|a_{i \, i+1}|+\cdots +|a_{in}|\]
for all $1 \leq i \leq n$.
Show that the matrix $A$ is nonsingular.
(b) Let $B=(b_{ij})$ be an $n \times n$ matrix whose entries satisfy the relation
\[ |b_{i\,i}|=1 \hspace{0.5cm} \text{ and }\hspace{0.5cm} |b_{ij}|<\frac{1}{n-1}\]
for all $i$ and $j$ with $i \neq j$.
Prove that the matrix $B$ is nonsingular.
(c)
Determine whether the following matrix is nonsingular or not.
\[C=\begin{bmatrix}
\pi & e & e^2/2\pi^2 \\[5 pt]
e^2/2\pi^2 &\pi &e \\[5pt]
e & e^2/2\pi^2 & \pi
\end{bmatrix},\]
where $\pi=3.14159\dots$, and $e=2.71828\dots$ is Euler’s number (or Napier’s constant).
Sponsored Links
Contents
Hint.
- For (a), assume that the matrix $A$ is singular.
Then the system of linear equation $A\mathbf{x}=\mathbf{0}$ has nonzero solution. - For (b), apply (a).
- For(c), use part (a). Note $e^2/2\pi^2=0.37433 \dots$.
Proof.
(a) Show that the matrix $A$ is nonsingular.
Suppose that the matrix $A$ is singular. Then the system of linear equations
\begin{align*}
a_{11}x_1+\cdots +a_{1n}x_n &=0 \\
\vdots \hspace{1.5cm}\vdots \hspace{0.5cm} &\hspace{0.5cm} \vdots \\
a_{n1}x_1+\cdots +a_{nn}x_n &=0 \\
\end{align*}
has nontrivial solution $(x_1,\dots, x_n) \neq (0, \dots, 0)$.
Since not all of $x_i$ are zero, let $x_k$ be the nonzero number such that $|x_k|$ is the largest among $|x_i|$.
That is,
\[|x_k|=\max_{1\leq i \leq n}{|x_i|}>0.\]
Then from the $k$-th equation in the system, we have
\[-a_{kk}x_k=a_{k1}x_1+\cdots+a_{k \, k-1}x_{k-1}+a_{k\, k+1}x_{k+1}+\cdots+a_{kn}x_n.\]
Taking the absolute values of both sides and by the triangle inequality, we have
\begin{align*}
|a_{kk}||x_k|&=|a_{k1}x_1+\cdots+a_{k \, k-1}x_{k-1}+a_{k\, k+1}x_{k+1}+\cdots+a_{kn}x_n|\\
& \leq |a_{k1}||x_1|+\cdots+|a_{k \, k-1}||x_{k-1}|+|a_{k\, k+1}||x_{k+1}|+\cdots+|a_{kn}||x_n|.
\end{align*}
Since $x_k$ is nonzero, we divide by $|x_k|$ and we have
\begin{align*}
|a_{kk}| & \leq |a_{k1}|\frac{|x_1|}{|x_k|}+\cdots+|a_{k \, k-1}|\frac{|x_{k-1}|}{|x_k|}+|a_{k\, k+1}|\frac{|x_{k+1}|}{|x_k|}+\cdots+|a_{kn}|\frac{|x_n|}{|x_k|}.
\end{align*}
By the choice of $x_k$, the absolute value of $x_k$ is maximal, hence $|x_i|/|x_k|\leq 1$ for all $i$.
Therefore we have
\[|a_{kk}| \leq |a_{i1}|+\cdots +|a_{i\,i-1}|+|a_{i \, i+1}|+\cdots +|a_{in}|.\]
However this contradicts the given condition. Therefore the matrix $A$ is nonsingular.
(b) Prove that the matrix $B$ is nonsingular.
Note that
\begin{align*}
&|b_{i1}|+\cdots +|b_{i\,i-1}|+|b_{i \, i+1}|+\cdots +|b_{in}|\\
& <\frac{1}{n-1}+\cdots+ \frac{1}{n-1}=\frac{n-1}{n-1}=1=|b_{ii}|.
\end{align*}
Therefore the matrix $B$ satisfy the condition of part (a). Therefore from the result of (a), the matrix $B$ is nonsingular.
(c) Determine whether the matrix is nonsingular or not.
Let us apply part (a) to the matrix $C$.
We have
\[\frac{e^2}{2\pi^2}=0.37433 \dots. \]
Thus we calculate
\[e+\frac{e^2}{2\pi^2}=3.09262\dots <\pi=3.14159\dots\]
Thus the sum of the (absolute value of) off-diagonal entries are less than the diagonal entry. Hence by part (a), the matrix $C$ is nonsingular.
Comment.
These are simple and interesting criteria for the non singularity of a matrix.
You may easily cook up matrices satisfying (or not satisfying) the conditions.
Why don’t you make one and give it to your friend for a math quiz?
Add to solve later
Sponsored Links
Hello.
I believe that in the proof “Suppose that the matrix A is [non]singular. Then the system of linear equations …
has nontrivial solution …”. must be replaced with “Suppose that the matrix A is singular…”
Dear Pavel,
Thank you for catching the mistake. I modified the text. Thanks!