# An invertible sparse matrix?

I'm not entirely certain about how to tackle this problem.... I hope you ladies and gents can help :)

If $M\in M_{n\times n}(\mathbb{R})$ be such that every row has precisely tow non-zero entries, one is precisely equal to $1$ and the other is found in the diagonal and is strictly greater than one. Must $M$ be invertible?

## My thoughts to date :)

I believe the answer to be yes; reasoning: Intuition: for $n\leq 2$ $M$ can be readily calculated directly.

Proof sketch idea: For arbitrary large $n$, I was thinking using the mini-max theorem to obtain a lower-bound on the smallest eigenvalue; and since all the non-zero entries are sufficiently large (at least 1); I would be done since then all eigenvalues must be strictly positive.... (But is the matrix Hermitian and how can I calculate this explicitly?)

Yes it is. Apply Gershgorin's Theorem.

• Thanks I'll post my solution :) – AIM_BLB May 30 '15 at 3:27
• Very pretty theorem :) – muaddib May 30 '15 at 3:37
• I agree! Its one of the coolest an most visual I've every seen in linear algebra :) Thanks for the link :D – AIM_BLB May 30 '15 at 3:45

A corollary to Gershgorin's theorem states:

More generally: let $M\in M_{n\times n}(\mathbb{R})$ be such that: $$(\forall i\in {1,..,n}) (\sum_{j\neq i} a_{i,j}) < a_{i,i}.$$

However, Gershgorin's theorem implies that each eigenvalue $\lambda$ of $M$ satisfies: $$\lambda \in \cup_{i=1}^n Ball_{(\sum_{j\neq i} a_{i,j})}( a_{i,i}).$$ However the first equation implies that $0\notin \cup_{i=1}^n Ball_{(\sum_{j\neq i} a_{i,j})}( a_{i,i})$ and in particular the disc in question lies in the first quadrant of the complex plain.

Therefore every eigenvalue $\lambda$ of $M$ satisfies: $min\{Re(\lambda),Im(\lambda)\} >0$ and in particular $M$ is in $GL_n(\mathbb{R})$.