Determinants of "almost identity" matrices. - MathOverflow

Determinants of "almost identity" matrices.

2010-12-23T23:32:28Z

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?

Answer by Douglas Zare for Determinants of "almost identity" matrices.

2010-12-24T04:40:36Z

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.

Answer by zroslav for Determinants of "almost identity" matrices.

2010-12-25T08:50:53Z

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.

Answer by drbobmeister for Determinants of "almost identity" matrices.

2010-12-25T08:52:43Z

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.

Answer by Federico Poloni for Determinants of "almost identity" matrices.

2010-12-25T20:58:34Z

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.