## Minkowski’s Criterion

Suppose $A$ is an $n \times n$ matrix with real entries such that the diagonal entries are all positive, off diagonal entries are all negative, and the row sums are all positive. Prove that $\mathsf{det}(A) \neq 0$.

Suppose to the contrary that $\mathsf{det}(A) = 0$. Then there must exist a nonzero solution $X$ to the matrix equation $AX = 0$. Let $X = [x_1\ \cdots\ x_n]^\mathsf{T}$ be such a solution, and choose $k$ such that $|x_k|$ is maximized. Using the triangle inequality, we have $|\sum_j |a_{i,j}|x_j| \leq \sum_j |a_{i,j}||x_j| \leq \sum_j|a_{i,j}||x_k|$. Recall that a consequence of the triangle inequality is that $|a|-|b| \leq |a-b|$ for all $a$ and $b$. Here, we have $|a_{k,k}x_k| - \sum_{j \neq k} |a_{k,j}||x_k| \leq |a_{k,k}x_k| - |\sum_{j \neq k} |a_{k,j}|x_j| \leq |a_{k,k}x_k - \sum_{j \neq k} |a_{k,j}|x_j| = \sum_j a_{k,j}x_j$. On the other hand, $|a_{k,k}x_k| - \sum_{j \neq k} |a_{k,j}||x_k| = |x_k|(\sum_j a_{k,j}) > 0$. Thus $\sum_j a_{k,j}x_j > 0$, a contradiction since $AX = 0$.

Thus $\mathsf{det}(A) \neq 0$.