# 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). Add to solve later

## Hint.

1. For (a), assume that the matrix $A$ is singular.
Then the system of linear equation $A\mathbf{x}=\mathbf{0}$ has nonzero solution.
2. For (b), apply (a).
3. 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

### 2 Responses

1. Pavel says:

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…”

• Yu says:

Dear Pavel,

Thank you for catching the mistake. I modified the text. Thanks!

This site uses Akismet to reduce spam. Learn how your comment data is processed.

###### More in Linear Algebra ##### Matrix Representations for Linear Transformations of the Vector Space of Polynomials

Let $P_2(\R)$ be the vector space over $\R$ consisting of all polynomials with real coefficients of degree $2$ or less....

Close