Invertible square matrices form an open and dense set

In this post, we'll prove some properties of the set \(\mathrm{Mat}_\mathbb{R}(m,m) = \mathbb{R}^{m\times m}\) the space of square matrices. As all norms are equivalent in finite dimensions, we equip the space with the frobenius norm:

$$ \lVert \mathrm{A} \rVert_F^2 \triangleq \sum_{i=1}^m\sum_{j=1}^m a_{ij}^2 $$ where \(\mathrm{A} =[a_{ij}]_{i,j}\) are the entries of the matrix.

Basic properties

It is trivial to prove that a sequence of matrices \((\mathrm{A}^{(n)})_n\) converges to a limit \(\mathrm{A}\) if the entry sequences \((a_{ij}^{(n)})_n\) converge to \(a_{ij}\) for all \(i,j\). We also obviously have that the sum of convergent matrix sequences converge to the sum of limits. Another easy to prove fact is that if two sequences of matrices \((\mathrm{A}^{(n)})_n\) and \((\mathrm{B}^{(n)})_n\) converge each to limits \(\mathrm{A}, \mathrm{B}\), then the product sequence converges to the product of limits \(\mathrm{AB}\). This can be proven by showing the \(i,j\)-th entry of the product is

$$ \left[\mathrm{A}^{(n)}\mathrm{B}^{(n)}\right]_{ij} = \sum_{k=1}^{m} a^{(n)}_{ik}b^{(n)}_{kj} $$ which converges as a finite sum of products of convergent sequences \(a^{(n)}_{ik} \to a_{ik}\) and \(b^{(n)}_{kj} \to b_{kj}\).

Using this fact, we can prove a useful lemma: denote \(S_n \triangleq \sum_{k=0}^n \mathrm{A}^k\) the partial sum of matrix powers, we get that

$$ (\mathrm{I} – \mathrm{A})S_n = \mathrm{I} – \mathrm{A}^{n+1}$$

therefore \(S_n\) converges if and only if \(\mathrm{I} – \mathrm{A}^{n+1}\) does, which converges if and only if \(\mathrm{A}^{n+1}\) does. This geometric sequence converges whenever \(\lVert \mathrm{A} \rVert_F < 1\). Thus we have that \(\lVert \mathrm{A} \rVert_F < 1 \implies (\mathrm{I} – \mathrm{A})^{-1}\) exists and

$$ (\mathrm{I} – \mathrm{A})^{-1} = \sum_{k=0}^\infty \mathrm{A}^k$$

Another easy to prove property of the matrix norm is that it is submultiplicative: \(\lVert \mathrm{AB}\rVert \leq \lVert \mathrm{A}\rVert \lVert \mathrm{B}\rVert \).

Invertible linear maps form an open set

We can prove this for any matrix norm, so we'll pick the one defined above. Suppose the matrix \(\mathrm{A}\) is invertible. We have to show that for some \(\delta > 0\), and any perturbation \(\mathrm{H}\) with small amplitude (\(\lVert \mathrm{H} \rVert < \delta$), the perturbed matrix $\mathrm{A} + \mathrm{H}\) is still invertible.

The first step is to use our lemma above, noticing that

$$ \left(\mathrm{A} + \mathrm{H}\right)^{-1} = \left(\mathrm{I} + \mathrm{A}^{-1}\mathrm{H}\right)^{-1}\mathrm{A}^{-1}$$

therefore, we can always pick \(\delta = 1 / {2\lVert \mathrm{A}^{-1} \rVert}\) which yields that \(\mathrm{A}^{-1}\mathrm{H}\) has a norm less than \(\frac12\) and thus the inverse exists. We just proved that the set of invertible matrices is open

Invertible linear maps form a dense set

A fairly basic result is that any matrix can be reduced to a RREF (Row Reduced Echelon Form) matrix which are defined by four properties:

Further, this RREF is obtain through a product of elementary matrices \(\mathrm{E}_k\mathrm{E}_{k-1}\dots\mathrm{E}_2\mathrm{E}_1\mathrm{A}\) which are invertible. Thus, singular matrix \(\mathrm{M}\) can be written as \(\mathrm{E}_k\mathrm{E}_{k-1}\dots\mathrm{E}_2\mathrm{E}_1\mathrm{A}\) with \(\mathrm{A}\) in RREF.

To construct a sequence of invertible matrices that tend to \(\mathrm{M}\) in the limit, observe that the only non invertible in the product is \(\mathrm{A}\), because \(p > 0\) rows have zero in their diagonal entry. If we replace those zeroes by \(1/n\) we obtain a sequence \(\mathrm{A}_n\) of matrices which are invertible and

$$\lim_{n\to\infty}\mathrm{E}_k\mathrm{E}_{k-1}\dots\mathrm{E}_2\mathrm{E}_1\mathrm{A}_n = \mathrm{E}_k\mathrm{E}_{k-1}\dots\mathrm{E}_2\mathrm{E}_1\lim_{n\to\infty}\mathrm{A}_n = \mathrm{M}$$

which proves that invertible matrices are dense.