Determinants of "almost identity" matrices. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:08:58Z http://mathoverflow.net/feeds/question/50261 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50261/determinants-of-almost-identity-matrices Determinants of "almost identity" matrices. yo 2010-12-23T23:32:28Z 2010-12-25T20:58:34Z <p>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?</p> http://mathoverflow.net/questions/50261/determinants-of-almost-identity-matrices/50270#50270 Answer by Douglas Zare for Determinants of "almost identity" matrices. Douglas Zare 2010-12-24T04:40:36Z 2010-12-24T04:40:36Z <p>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.</p> http://mathoverflow.net/questions/50261/determinants-of-almost-identity-matrices/50330#50330 Answer by zroslav for Determinants of "almost identity" matrices. zroslav 2010-12-25T08:50:53Z 2010-12-25T08:50:53Z <p>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.</p> http://mathoverflow.net/questions/50261/determinants-of-almost-identity-matrices/50331#50331 Answer by drbobmeister for Determinants of "almost identity" matrices. drbobmeister 2010-12-25T08:52:43Z 2010-12-25T08:52:43Z <p>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.</p> <p>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$.)</p> <p>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} &lt; 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} &lt; 1$ for all $j$. In particular since the $b_{ij}$ are finite in number, there exists $K$, $0 &lt; K &lt; 1$, with all $\sum_{i} b_{ij} &lt; 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|| &lt; K &lt; 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|| &lt; 1$, $I - B$ is invertable, an argument often seen in operator theory.</p> <p>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 <em>quite</em> well known. It is an exercise, but, like many exercises in mathematics, one which is not without merit of its own. </p> http://mathoverflow.net/questions/50261/determinants-of-almost-identity-matrices/50374#50374 Answer by Federico Poloni for Determinants of "almost identity" matrices. Federico Poloni 2010-12-25T20:58:34Z 2010-12-25T20:58:34Z <p>I'm answering to the "are these matrices well-known" part. Yes, they belong to at least two classes of widely studied matrices:</p> <ul> <li><p>Diagonally dominant matrices, as has been suggested before, i.e., matrices such that $|A_{ii}|>\sum_{j\neq i}|A_{ij}|$ for each $i$.</p></li> <li><p>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 <em>Nonnegative matrices in the mathematical sciences</em>. They have several interesting properties that "look like" those of symmetric positive definite matrices. </p></li> </ul>