6

Let $A$ be a $n\times n$ matrix over the reals such that the diagonal entries are all positive, the off-diagonal entries are all negative, and the row sums are all positive. Show that $\det A \neq 0$.

To show that $\det A\neq 0$, it would be sufficient to show that the system $AX = 0$ does not have a nontrivial solution. Then I suppose that to show that, one could assume that it has a nontrivial solution and then obtain a contradiction. But I'm stuck on actually doing that part.

Any suggestions? I'm also interested in where I can find questions similar to this one to practice.

measuresproblem
  • 171

3 Answers3

6

Suppose there exists a vector $x \in \mathbb{R}^n \setminus \{\vec{0}\}$ such that $Ax = \vec{0}$.

Pick an index $k$ such that $|x_k| = \displaystyle\max_{j = 1,\ldots,n}|x_j|$. So we have $|x_j| \le |x_k|$ for all $j = 1,\ldots,n$.

If $x_k = 0$, then we would have $x_j = 0$ for all $j = 1,\ldots,n$, i.e. $x = \vec{0}$, which isn't possible.

If $x_k > 0$, then $x_j \le |x_j| \le |x_k| = x_k$ for all $j$. Then, since $A_{k,k} > 0$, $A_{k,j} < 0$ for all $j \neq k$, and $\displaystyle\sum_{j = 1}^{n}A_{k,j} > 0$, we have $$0 = (Ax)_k = \sum_{j = 1}^{n}A_{k,j}x_j = A_{k,k}x_k + \sum_{j \neq k}A_{k,j}x_j \ge A_{k,k}x_k + \sum_{j \neq k}A_{k,j}x_k = x_k\sum_{j = 1}^{n}A_{k,j} > 0,$$ a contradiction.

Similarly, if $x_k < 0$, then $x_j \ge -|x_j| \ge -|x_k| = x_k$ for all $j$. Then, since $A_{k,k} > 0$, $A_{k,j} < 0$ for all $j \neq k$, and $\displaystyle\sum_{j = 1}^{n}A_{k,j} > 0$, we have $$0 = (Ax)_k = \sum_{j = 1}^{n}A_{k,j}x_j = A_{k,k}x_k + \sum_{j \neq k}A_{k,j}x_j \le A_{k,k}x_k + \sum_{j \neq k}A_{k,j}x_k = x_k\sum_{j = 1}^{n}A_{k,j} < 0,$$ a contradiction.

Therefore, there is no nonzero vector $x$ such that $Ax = \vec{0}$. Hence, $A$ is invertible, and thus, $\det A \neq 0$.

JimmyK4542
  • 54,331
4

Since the $i$-th diagonal entry is positive and the other entries in the $i$-th row are negative, and since the $i$-th row sum is positive, it must be the case that the matrix is strictly diagonally dominant. Use Gershgorin's circle theorem to conclude that $0$ is not an eigenvalue of the matrix.

Dave
  • 13,568
  • Interesting suggestion. Do you have any other suggestion for how to do it? This is a practice test I'm studying from and the question is supposed to be solved without that theorem. – measuresproblem May 12 '19 at 00:47
  • I don't have a more elementary solution to this problem as of now, but if I think of one I will add it to my answer here. Also, since you requested questions similar to this, here is one: https://math.stackexchange.com/questions/285953/how-to-show-that-the-determinant-of-a-is-non-zero – Dave May 12 '19 at 00:49
1

Use induction on the size of the matrix.

Assuming for matrices of size $(n-1)^2$ this is true, consider the determinant of a matrix of $n^2$:

$$ \left|\begin{matrix}a_{11}&\cdots&a_{1n}\\ \vdots&&\vdots\\ a_{n1}&\cdots&a_{nn}\\ \end{matrix}\right| $$

with $a_{ii}>0,\ a_{ij}<0(i\neq j),\ \sum_{j=1}^na_{ij}>0$. First use $a_{nn}>0$ to cancel other elements on the $n$-th row and you re left with a $(n-1)^2$ determinant. Verify that it satisfies all the requirements for the induction hypothesis and apply the hypothesis.

trisct
  • 5,221