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<n 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

Leave a comment

Filed under Linear algebra