Proof of Criteria for Invertibility of a Square Real Matrix

Each result cited is universally quantified over the data in its own statement. The rules of Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes are used with $m=n=p=q$. We prove (a)$\Leftrightarrow$(b), (a)$\Rightarrow$(c)$\Rightarrow$(d)$\Rightarrow$(e)$\Rightarrow$(a), and (d)$\Leftrightarrow$(f). Points of $\mathbb{R}^{n}$ are compared componentwise by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §equality, the origin having all components $0$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §origin. For $X\in\mathcal{M}_{n}(\mathbb{R})$, $X$ satisfies (a), respectively (c), means that (a), respectively (c), holds with $X$ in place of $A$.

Claim. Let $X\in\mathcal{M}_{n}(\mathbb{R})$. (i) If $X$ satisfies (a), then $X$ satisfies (c). (ii) If $X$ satisfies (c), then $XD=I_{n}$ for some $D\in\mathcal{M}_{n}(\mathbb{R})$. So if $X$ satisfies (a), then $X$ satisfies (c) and $XD=I_{n}$ for some $D\in\mathcal{M}_{n}(\mathbb{R})$. For $X=A$, (i) and (ii) are (a)$\Rightarrow$(c) and (c)$\Rightarrow$(d).

(a)$\Rightarrow$(b). Let $x,y\in\mathbb{R}^{n}$ with $Ax=Ay$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $A(x-y)=Ax-Ay=0$ since $Ax=Ay$; so $x-y=0$ by (a). For $k\in[n]$, then $x_{k}-y_{k}=(x-y)_{k}=0$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §operations, that is, $(-y_{k})+x_{k}=0$, so $x_{k}=-(-y_{k})=y_{k}$ by Negatives, Differences, Reciprocals and Quotients §negative and Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §signs. Hence $x=y$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §equality.

(b)$\Rightarrow$(a). If $Ax=0$, then $Ax=A0$ since $A0=0$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, so $x=0$ by (b).

Proof of the claim, (i). Let $X\in\mathcal{M}_{n}(\mathbb{R})$ satisfy (a), and let $b\in\mathbb{R}^{n}$. The set $[n]\times[n+1]$ is a set by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §set; $[n]\subseteq[n+1]$, $n+1\notin[n]$, and every element of $[n+1]$ lies in $[n]$ or equals $n+1$, by Arithmetic and Order of the Natural Numbers §successor, Arithmetic and Order of the Natural Numbers §partial-order and Arithmetic and Order of the Natural Numbers §trichotomy. By Maps and Relations Given by Formulas §binary there is exactly one map $\pi:[n]\times[n+1]\to[n]$ with $\pi((i,j))=i$. By Maps Defined by Cases §cases, on the set $[n]\times[n+1]$ with the property $p\in[n]\times[n]$ (predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols §closure) and the expressions $X(p)$ (used properly when $p\in[n]\times[n]$) and $b(\pi(p))$, there is exactly one map $M:[n]\times[n+1]\to\mathbb{R}$ with $M(p)=X(p)$ for $p\in[n]\times[n]$ and $M(p)=b(\pi(p))$ otherwise. Thus $M\in\mathcal{M}_{n\times(n+1)}(\mathbb{R})$ by Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §matrices, and, by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership and Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §entries, $M_{ij}=X_{ij}$ for $i,j\in[n]$ and $M_{i,n+1}=b_{i}$ for $i\in[n]$. Since $n<n+1$ by Arithmetic and Order of the Natural Numbers §successor, A Homogeneous Linear System with More Unknowns than Equations Has a Nonzero Solution §nontrivial gives $w\in\mathbb{R}^{n+1}$ with $w\neq0$ and $Mw=0$. By Maps and Relations Given by Formulas §map there is exactly one map $z:[n]\to\mathbb{R}$ with $z_{j}=w_{j}$ for $j\in[n]$, so $z\in\mathbb{R}^{n}$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §membership; let $t=w_{n+1}$. For $i\in[n]$, Matrix-Vector Product §product and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §interval-recursion (with $m=1$) give

$$(\dagger)\qquad 0=(Mw)_{i}=\sum_{j=1}^{n}M_{ij}w_{j}+M_{i,n+1}w_{n+1}=(Xz)_{i}+t\,b_{i}.$$

If $t=0$, then $(\dagger)$ gives $(Xz)_{i}=0$ for every $i\in[n]$, so $Xz=0$ and, as $X$ satisfies (a), $z=0$; then $w_{j}=z_{j}=0$ for $j\in[n]$ and $w_{n+1}=t=0$, so $w=0$, a contradiction. Hence $t\neq0$. Let $s=-t^{-1}$, the negative, by Negatives, Differences, Reciprocals and Quotients §negative, of the reciprocal $t^{-1}$ of $t\neq0$ in the field $\mathbb{R}$, by Negatives, Differences, Reciprocals and Quotients §reciprocal; and let $x=sz\in\mathbb{R}^{n}$. Let $i\in[n]$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector and Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §operations, $(Xx)_{i}=(s(Xz))_{i}=s\,(Xz)_{i}$. By $(\dagger)$, $t\,b_{i}+(Xz)_{i}=0$, so $(Xz)_{i}=-(t\,b_{i})$ by Negatives, Differences, Reciprocals and Quotients §negative; hence

$$s\,(Xz)_{i}=(-t^{-1})(-(t\,b_{i}))=t^{-1}(t\,b_{i})=(t^{-1}t)\,b_{i}=b_{i}$$

by Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §signs, associativity and commutativity of multiplication in $\mathbb{R}$, and $t\,t^{-1}=1$ from Negatives, Differences, Reciprocals and Quotients §reciprocal. So $(Xx)_{i}=b_{i}$ for every $i\in[n]$, and $Xx=b$.

Proof of the claim, (ii). Let $X\in\mathcal{M}_{n}(\mathbb{R})$ satisfy (c). By Maps and Relations Given by Formulas §map there is exactly one map $\psi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ with $\psi(x)=Xx$. For $k\in[n]$ let $C_{k}=\psi^{-1}[\{e_{k}\}]$, the preimage, with $e_{k}$ as in Identity Matrix and Standard Basis Vectors §basis. By The Image and the Preimage of a Class under a Class §image, Relations, Domain, Range, Inverse and Composition §inverse and Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols §value, a set $x$ lies in $C_{k}$ if and only if $x\in\mathbb{R}^{n}$ and $Xx=e_{k}$; so $C_{k}$ is a subclass of $\mathbb{R}^{n}$, hence a set by Subclasses of Sets Are Sets, the Union and Power Set of a Set Exist Uniquely, Binary Unions of Sets Are Sets, and the Universal Class Is Proper §subclass, and an element of the power set $\mathcal{P}(\mathbb{R}^{n})$, a set by Subclasses of Sets Are Sets, the Union and Power Set of a Set Exist Uniquely, Binary Unions of Sets Are Sets, and the Universal Class Is Proper §power. As the formula of the preimage quantifies over sets only (The Image and the Preimage of a Class under a Class §image), Maps and Relations Given by Formulas §map gives exactly one map $C:[n]\to\mathcal{P}(\mathbb{R}^{n})$ with $C(k)=C_{k}$, a family $(C_{k})_{k\in[n]}$. By (c) for $X$ with $b=e_{k}$, $C_{k}\neq\emptyset$ for every $k\in[n]$, and $[n]$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §naturals. By Sets of Maps between Finite Sets, Finite Unions of Finite Sets, and Finite Choice §choice there is a map $f$ on $[n]$ with $f(k)\in C_{k}$, that is, $f(k)\in\mathbb{R}^{n}$ and $Xf(k)=e_{k}$, for every $k\in[n]$. Each $f(k)$ is a map $[n]\to\mathbb{R}$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §membership, so Maps and Relations Given by Formulas §binary gives exactly one map $B:[n]\times[n]\to\mathbb{R}$ with $B((j,k))=f(k)(j)$; thus $B\in\mathcal{M}_{n}(\mathbb{R})$ and $B_{jk}=f(k)_{j}$. For $i,k\in[n]$, Product of Real Matrices §product, Matrix-Vector Product §product, Identity Matrix and Standard Basis Vectors §basis and Identity Matrix and Standard Basis Vectors §identity give

$$(XB)_{ik}=\sum_{j=1}^{n}X_{ij}f(k)_{j}=(Xf(k))_{i}=(e_{k})_{i}=\delta_{ik}=(I_{n})_{ik},$$

so $XB=I_{n}$ by Real Matrices: the Set of Real m x n Matrices with Their Entrywise Operations §equality, and (ii) holds with $D=B$.

(d)$\Rightarrow$(e) and (d)$\Rightarrow$(f). Let $AB=I_{n}$. First, $B$ satisfies (a): if $x\in\mathbb{R}^{n}$ and $Bx=0$, then by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $x=I_{n}x=(AB)x=A(Bx)=A0=0$. By the claim with $X=B$, there is $D\in\mathcal{M}_{n}(\mathbb{R})$ with $BD=I_{n}$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §identity and Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §associative,

$$A=AI_{n}=A(BD)=(AB)D=I_{n}D=D,$$

so $BA=BD=I_{n}$. Thus (e) holds with $C=B$; and since $AB=I_{n}$ and $BA=I_{n}$, $B$ is an inverse of $A$, so $A$ is invertible by Inverse Matrix and Invertible Real Square Matrix §invertible, which is (f).

(e)$\Rightarrow$(a). Let $CA=I_{n}$ and $x\in\mathbb{R}^{n}$ with $Ax=0$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $x=I_{n}x=(CA)x=C(Ax)=C0=0$.

(f)$\Rightarrow$(d). If $A$ is invertible, it has an inverse $B\in\mathcal{M}_{n}(\mathbb{R})$ by Inverse Matrix and Invertible Real Square Matrix §invertible, and $AB=I_{n}$ by Inverse Matrix and Invertible Real Square Matrix §inverse.