Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that $A$ is a real square matrix with all diagonal entries $1$, all off-diagonal entries non-positive, and all column sums positive and non-zero. Does it follow that $\det(A)\neq0$? Is this just an exercise? Are these matrices well-known?

share|improve this question
10  
Your matrix $A$ is strictly diagonally dominant, and it is a known fact that the determinant of a strictly diagonally dominant matrix is nonzero (to prove this, show that the corresponding system of linear equations has no solution besides the real one, OR use Gershgorin's circle theorem, OR use the stronger fact that the determinant of a diagonally strictly dominant matrix is positive - which is harder to prove, however). –  darij grinberg Dec 23 '10 at 23:39
3  
Oh, and I'm not voting to close because I'd like to hear everyone's proofs that the determinant of a diagonally strictly dominant matrix is positive. Here is mine: artofproblemsolving.com/Forum/viewtopic.php?p=1201606#p1201606 –  darij grinberg Dec 23 '10 at 23:43
10  
"I'd like to hear everyone's proofs that the determinant of a diagonally strictly dominant matrix is positive." ------ Show it is not zero in any of the ways you suggested and then observe that it couldn't change sign when moving from a purely diagonal matrix to the given one along a straight line. –  fedja Dec 24 '10 at 1:39
    
To fedja: why are the eigenvalues real? –  Zsbán Ambrus Dec 25 '10 at 13:42
add comment

4 Answers

up vote 14 down vote accepted

A nonzero row vector $v$ has a nonzero coordinate of greatest magnitude. $vA$ has a nonzero entry in that coordinate by the triangle inequality, hence is not the $0$ vector.

share|improve this answer
3  
Very nice indeed. –  Aaron Meyerowitz Dec 24 '10 at 4:48
    
Yes, very elegant, concise and elementary. Indeed, very nice! –  drbobmeister Dec 24 '10 at 23:53
add comment

I'm answering to the "are these matrices well-known" part. Yes, they belong to at least two classes of widely studied matrices:

  • Diagonally dominant matrices, as has been suggested before, i.e., matrices such that $|A_{ii}|>\sum_{j\neq i}|A_{ij}|$ for each $i$.

  • M-matrices. There are several equivalent definitions of M-matrices, such as matrices in the form $sI-P$, where $P$ is an elementwise nonnegative matrix and $s>\rho(P)$ ($\rho$=spectral radius), or matrices with nonpositive off-diagonal elements and all their eigenvalues in the right half-plane. You can find a comprehensive exposition, including an impressive list of 50 conditions equivalent to "$A$ is a nonsingular M-matrix", on Berman, Plemmons Nonnegative matrices in the mathematical sciences. They have several interesting properties that "look like" those of symmetric positive definite matrices.

share|improve this answer
add comment

First of all, it's hard to beat Douglas Zane's one-liner resolving yo's main question. Very short, sweet, and to the point. But, since darij grinberg wants to see "everyone's proofs", I'll add mine to his collection.

Upon first reading this question the first thing which popped into my mind was the following argument, based on Gershgorin's Circle Theorem: $A$ is real; therefore the characteristic polynomial of $A$ has real coefficients; therefore the eigenvalues of $A$ are either real or occur in complex conjugate pairs $\lambda$, $\bar \lambda$. $\lambda \bar \lambda$, however, is nonnegative. Indeed, by Gershgorin's theorem, all such $\lambda$ have positive real part, whence $\lambda \bar \lambda > 0$ for all complex eigenvalues $\lambda$. Again by Gershgorin's theorem, the real eigenvalues must be positive as well; thus the product of all the eigenvalues of $A$, i.e. its determinant, must be positive, establishing the nonsingularity of $A$ and a little more, viz. $det(A) > 0$. (Of course, Gershgorin's theorem directly shows no eigenvalue can be zero, thus directly establishing the fact that $det(A) \ne 0$.)

Then after reading the comments I realized the Gershgorin Circle Theorem approach was old hat, so I mulled it over for a few minutes to see if I could come up with a proof which didn't use Gershgorin's result, at least not directly. Here's what I got: set $B = I - A$; then the entries $b_{ij}$ of $B$ satisfy $b_{ii} =0$, $b_{ij} \ge 0$, and $\sum_{i}b_{ij} < 1$ for all $j$; these statements follow directly from the assumptions placed upon $A$ in the stated question. We thus have $0 \le \sum_{i} b_{ij} < 1$ for all $j$. In particular since the $b_{ij}$ are finite in number, there exists $K$, $0 < K < 1$, with all $\sum_{i} b_{ij} < K$. From these remarks it is easy to see that, considering $B$ as a linear map on row vectors $v$ by multiplication on the right, i.e. $v \to vB$, the operator norm of $||B||$ of $B$ satisfies $||B|| \le K$ if we use the $sup$ or $max$ norm on $R^{n}$, where $v$ lives: $||v|| = max\{|v_{i}|\}$. Then as is well-known we have the existence of$A^{-1}$, viz. $A^{-1} = (I - B)^{-1} = I - B + B^{2} - B^{3} + . . . $; this latter series converges since $||B|| < K < 1$. Thus we have $det(A) \ne 0$. A little more work allows us to incorporate the idea expressed in fedja's comment: for $s \in [0, 1]$ the matrix $sB$ exhibits all the properties which have been shown to hold for $B$, so $s \to (I - sB)$ is a continuous path from $I$ to $A$ through nonsingular matrices on which the determinant cannot change sign; thus in fact $det(A) > 0$. This approach replaces reliance on Gershgorin's Circle Theorem with with the notion that, for $||B|| < 1$, $I - B$ is invertable, an argument often seen in operator theory.

Now I must confess that, after having worked this out, I found essentially the same tack on the web page cited by darij in his comment; but darij wanted to see different people's proofs, and so here is mine. Finally, I guess yo can see from what has been posted here that such matrices are quite well known. It is an exercise, but, like many exercises in mathematics, one which is not without merit of its own.

share|improve this answer
add comment

If $\sum_i \lambda_i (a_{ij})_i=0$ is a linear dependence of the rows of your matrice with $\lambda_i\in\mathbb R$ then find the maximal $|\lambda_i|$. Then you have $0=|\sum_i \lambda_j a_{ij}|\geq |\lambda_i|-\sum_{i\ne j}|\lambda_j| |a_{ij}|\geq |\lambda_i| - \sum_{i\ne j} |\lambda_i||a_{ij}|>0$. Contradiction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.