Monthly Archives: December 2016

Minkowski’s criterion

Here is a related post that I find interesting.

In linear algebra, Minkowski‘s criterion states the following.

Theorem (Minkowski’s Criterion). Let $A$ be 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. Then $\det(A)\neq 0$.

This is a nice criterion and is not very difficult to prove, but for a random matrix it is asking too much. To decide whether a matrix is singular one usually looks for a row/column consisting of zeros or adding up to zero. The following result gives sufficient conditions for this to work. Unfortunately, it does not generalise Minkowski’s result.

Theorem. Let $A$ be a $n\times n$ matrix with real entries such that its row sums are all $\ge 0$, its lower diagonal entries are $\ge 0$ and its upper diagonal entries are $\le 0$. Then $\det(A)=0$ if and only if $A$ has either a row consisting entirely of zeros or all the row sums equal to zero.

Proof. Suppose that $Ab=0$, where $b=(b_1,\dots,b_n)^T\neq 0$. Assume that $b_1\ge\cdots\ge b_n$. Then there exists $1\le m such that $a_{1,1}',\dots,a_{1,m}'\ge 0$ and $a_{1,m+1}',\dots,a_{1,n}'\le 0$. Hence

\begin{aligned}0=\sum_{j=1}^na_{1,j}'b_j&\ge b_m\sum_{j=1}^ma_{1,j}'+b_{m+1}\sum_{j=m+1}^na_{1,j}\\&\ge (b_m-b_{m+1})\sum_{j=1}^ma_{1,j}'\ge 0.\end{aligned}

So we must have (i) $b_1=\cdots=b_m$, (ii) $b_{m+1}=\cdots=b_n$, (iii) $a_{1,1}'+\cdots+a_{1,n}'=0$ and (iv) either $b_m=b_{m+1}$ or $a_{1,1}'+\cdots+a_{1,m}'=0$. These boil down to having either $b_1=\cdots=b_n$ or $a_{1,1}'=\cdots=a_{1,n}'=0$. Apply this argument to each row of $A$ to obtain the desired conclusion. $\square$