# Small Deviations

## 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:

• In every row, the first non-zero entry is $1$ (called pivotal $1$)
• The pivotal $1$ of a lower row is always to the right of the pivotal $1$ of a higher row
• Every column which contains a pivotal $1$ has only zeros as other entries
• Rows consisting only of $0$'s are on the bottom

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.