Proof of An Injective Nondegenerate Square Matrix is Invertible

We use the notation of the statement. Throughout, $A(\lambda v+\mu w)=\lambda\,Av+\mu\,Aw$ is claim 1 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product, and by claim 3 of that lemma there is $C\in\mathbb{R}$ with $0\le C$ such that

$$\lVert Av\rVert\le C\,\lVert v\rVert\qquad\text{for every }v\in\mathbb{R}^{n}. \tag{C}$$

In particular $A0=0$. We write $e_{1},\dots,e_{n}$ for the standard basis vectors of $\mathbb{R}^{n}$. If $(p_{l})_{l\in\mathbb{N}}$ is a strictly increasing sequence in $\mathbb{N}$ then $l\le p_{l}$ for every $l$, by Principle of Induction for the Natural Numbers.

Claim 1. Suppose no such $c$ exists. Then for every $m\in\mathbb{N}$, the number $1/m$ being positive, there is $h_{m}\in\mathbb{R}^{n}$ with $\lVert Ah_{m}\rVert<\tfrac{1}{m}\lVert h_{m}\rVert$; necessarily $h_{m}\neq0$, since for $h_{m}=0$ both sides would be $0$. Put $u_{m}=h_{m}/\lVert h_{m}\rVert$; by claim 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, $\lVert u_{m}\rVert=1$ and

$$\lVert Au_{m}\rVert=\tfrac{1}{\lVert h_{m}\rVert}\lVert Ah_{m}\rVert<\tfrac{1}{m}.$$

The points $u_{m}$ lie in the bounded set $\bar{B}(0,1)$, so The Bolzano-Weierstrass Theorem in $\mathbb{R}^n$ provides $u\in\mathbb{R}^{n}$ and a strictly increasing sequence $(p_{l})_{l\in\mathbb{N}}$ in $\mathbb{N}$ with $(u_{p_{l}})_{l\in\mathbb{N}}$ converging to $u$. By claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square applied to $u_{p_{l}}=u+(u_{p_{l}}-u)$ and to $u=u_{p_{l}}+(u-u_{p_{l}})$, together with $\lVert u-u_{p_{l}}\rVert=\lVert u_{p_{l}}-u\rVert$, which is claim 5 of that lemma with the scalar $-1$,

$$1-\lVert u_{p_{l}}-u\rVert\le\lVert u\rVert\le1+\lVert u_{p_{l}}-u\rVert ,$$

and letting $l$ increase, Arithmetic of Limits of Real Sequences and Order Properties of Limits of Real Sequences give $\lVert u\rVert=1$; in particular $u\neq0$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. Moreover, by claim 6 of that lemma and (C),

$$\lVert Au\rVert\le\lVert A(u-u_{p_{l}})\rVert+\lVert Au_{p_{l}}\rVert\le C\,\lVert u-u_{p_{l}}\rVert+\tfrac{1}{p_{l}}\le C\,\lVert u-u_{p_{l}}\rVert+\tfrac{1}{l},$$

whose right-hand side can be made smaller than any prescribed positive real by taking $l$ large, using The Archimedean Property of the Real Numbers. Hence $\lVert Au\rVert=0$ and $Au=0$. Since also $A0=0$ and $u\neq0$, the map $h\mapsto Ah$ is not injective, contrary to hypothesis.

Claim 2. If $Ah,Ah'\in A(\mathbb{R}^{n})$ and $\theta\in\mathbb{R}$ with $0\le\theta\le1$, then $\theta\,Ah+(1-\theta)Ah'=A(\theta h+(1-\theta)h')\in A(\mathbb{R}^{n})$, so $A(\mathbb{R}^{n})$ is convex by Segments and Convex Subsets of $\mathbb{R}^n$; and $0=A0\in A(\mathbb{R}^{n})$.

Now suppose $h\mapsto Ah$ is injective and let $c$ be as in claim 1. We verify the criterion of Sequential Characterization of Closed Subsets of a Metric Space. Let $(z_{m})_{m\in\mathbb{N}}$ be a sequence in $A(\mathbb{R}^{n})$ converging to $z\in\mathbb{R}^{n}$; by injectivity each $z_{m}$ is $Ah_{m}$ for a uniquely determined $h_{m}$, so no choice is involved. Since $(z_{m})$ converges there is $m_{0}$ with $\lVert z_{m}-z\rVert\le1$, hence $\lVert z_{m}\rVert\le\lVert z\rVert+1$, for $m_{0}\le m$; letting $R$ be the largest of the finitely many numbers $\lVert z\rVert+1$ and $\lVert z_{1}\rVert,\dots,\lVert z_{m_{0}}\rVert$, we get $\lVert z_{m}\rVert\le R$ for every $m$, and therefore $\lVert h_{m}\rVert\le c^{-1}\lVert Ah_{m}\rVert\le c^{-1}R$ by claim 1. The points $h_{m}$ thus lie in the bounded set $\bar{B}(0,c^{-1}R)$, and The Bolzano-Weierstrass Theorem in $\mathbb{R}^n$ provides $h\in\mathbb{R}^{n}$ and a strictly increasing $(p_{l})_{l\in\mathbb{N}}$ with $(h_{p_{l}})$ converging to $h$. By claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square and (C),

$$\lVert Ah-z\rVert\le\lVert A(h-h_{p_{l}})\rVert+\lVert z_{p_{l}}-z\rVert\le C\,\lVert h-h_{p_{l}}\rVert+\lVert z_{p_{l}}-z\rVert ,$$

which can be made smaller than any prescribed positive real; hence $\lVert Ah-z\rVert=0$ and $z=Ah\in A(\mathbb{R}^{n})$. So $A(\mathbb{R}^{n})$ is closed.

Claim 3. Suppose $A(\mathbb{R}^{n})\neq\mathbb{R}^{n}$ and pick $b\in\mathbb{R}^{n}\setminus A(\mathbb{R}^{n})$. By claim 2 the set $A(\mathbb{R}^{n})$ is nonempty, convex and closed, so claim 1 of Nearest-Point Projection onto a Nonempty Closed Convex Subset of Euclidean Space defines the nearest point $\pi(b)\in A(\mathbb{R}^{n})$ and claim 2 of that lemma gives

$$\bigl(b-\pi(b)\bigr)\cdot\bigl(w-\pi(b)\bigr)\le0\qquad\text{for every }w\in A(\mathbb{R}^{n}).$$

Put $\nu_{0}=b-\pi(b)$; then $\nu_{0}\neq0$, since $\pi(b)$ lies in $A(\mathbb{R}^{n})$ and $b$ does not. Write $\pi(b)=Ag$. For $h\in\mathbb{R}^{n}$ and $t\in\mathbb{R}$ the point $w=A(g+th)=\pi(b)+t\,Ah$ lies in $A(\mathbb{R}^{n})$, so the displayed inequality gives $t\,\bigl(\nu_{0}\cdot(Ah)\bigr)\le0$ for every $t\in\mathbb{R}$, using The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite. Taking $t$ of either sign forces $\nu_{0}\cdot(Ah)=0$. Hence $\nu=\nu_{0}/\lVert\nu_{0}\rVert$, which has norm $1$ by claim 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, satisfies $\nu\cdot(Ah)=0$ for every $h$, contrary to hypothesis. Therefore $A(\mathbb{R}^{n})=\mathbb{R}^{n}$.

Claim 4. By claim 3, for each $i\in\{1,\dots,n\}$ there is $b_{i}\in\mathbb{R}^{n}$ with $Ab_{i}=e_{i}$, and it is unique by injectivity. Let $B$ be the real $n\times n$ matrix with $B_{ji}=(b_{i})_{j}$. For $k\in\mathbb{R}^{n}$, Matrix-Vector Product gives $(Bk)_{j}=\sum_{i=1}^{n}B_{ji}k_{i}=\sum_{i=1}^{n}k_{i}(b_{i})_{j}$, that is $Bk=\sum_{i=1}^{n}k_{i}b_{i}$. Claim 1 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product gives $A(v+w)=Av+Aw$ and $A(\mu v)=\mu\,Av$ for two summands, and hence, by Principle of Induction for the Natural Numbers on the number of summands, $A\bigl(\sum_{i=1}^{r}\mu_{i}v_{i}\bigr)=\sum_{i=1}^{r}\mu_{i}\,Av_{i}$ for every $r\in\mathbb{N}$. Therefore

$$A(Bk)=\sum_{i=1}^{n}k_{i}\,Ab_{i}=\sum_{i=1}^{n}k_{i}e_{i}=k ,$$

the last equality because the $j$th coordinate of $\sum_{i}k_{i}e_{i}$ is $k_{j}$, by the description of the standard basis vectors in Orthonormal Families, Standard Basis Vectors, and Plane Rotations of Euclidean Space. By claim 2 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product, $(AB)k=A(Bk)=k$ for every $k$. Taking $k=e_{\beta}$ and using $(Me_{\beta})_{\alpha}=\sum_{i}M_{\alpha i}(e_{\beta})_{i}=M_{\alpha\beta}$ for any real $n\times n$ matrix $M$, which is Matrix-Vector Product, we get $(AB)_{\alpha\beta}=(e_{\beta})_{\alpha}=(I_{n})_{\alpha\beta}$ for all $\alpha,\beta$, where $I_{n}$ is the identity matrix; that is, $AB=I_{n}$.

For the other side, let $h\in\mathbb{R}^{n}$. Then $A\bigl(B(Ah)\bigr)=Ah$ by what was just proved applied to $k=Ah$, so $B(Ah)=h$ by injectivity, that is $(BA)h=h=I_{n}h$ for every $h$ by claim 2 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product and claim 2 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum. Reading off entries as before gives $BA=I_{n}$. Hence $B$ is an inverse of $A$ in the sense of Inverse Matrix and Invertible Real Square Matrix, so $A$ is invertible and $A^{-1}=B$ by Uniqueness of the Matrix Inverse.

Finally, let $k\in\mathbb{R}^{n}$ and put $h=A^{-1}k$, so that $Ah=k$. Claim 1 gives $\lVert k\rVert=\lVert Ah\rVert\ge c\lVert h\rVert$, and dividing by the positive number $c$ gives $\lVert A^{-1}k\rVert\le c^{-1}\lVert k\rVert$.