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.

Post a comment or leave a trackback: Trackback URL.


  • Paul  On August 2, 2011 at 1:04 pm

    Wow I didn’t realize you constantly updated this site. Awesome job! Your site has helped me greatly in studying for my exams so thank you!

    • nbloomf  On August 5, 2011 at 8:41 am

      I’m glad to hear that!

  • meng  On February 24, 2012 at 2:37 pm

    very useful website, thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: