Equivalent Characterizations of Nonsingular Matrix

== Theorem ==
Let $\mathbf A$ be a square matrix of order $n$ over a field $K$.
:$(1):\quad$ $\mathbf A$ is nonsingular
:$(2):\quad$ The transpose of $\mathbf A$ is nonsingular
:$(3):\quad$ $\mathbf A$ row-reduces to the identity matrix $\mathbf I_n$
:$(4):\quad$ The null space of $\mathbf A$ contains only the zero vector $\mathbf 0$
:$(5):\quad$ The homogeneous linear system $\mathbf A \mathbf x = \mathbf 0$ has only the trivial solution $\mathbf 0$
:$(6):\quad$ The linear system $\mathbf A \mathbf x = \mathbf b$ has a unique solution for every possible choice of $\mathbf b$
:$(7):\quad$ The columns of $\mathbf A$ are linearly independent
:$(8):\quad$ The column space of $\mathbf A$ is $K^n$
:$(9):\quad$ The columns of $\mathbf A$ are a basis for $K^n$
:$(10):\quad$ The rows of $\mathbf A$ are linearly independent
:$(11):\quad$ The row space of $\mathbf A$ is $K^n$
:$(12):\quad$ The rows of $\mathbf A$ are a basis for $K^n$
:$(13):\quad$ The rank of $\mathbf A$ is $n$
:$(14):\quad$ The nullity of $\mathbf A$ is zero
:$(15):\quad$ The determinant of $\mathbf A$ is not zero
:$(16):\quad$ $0_K$ is not an eigenvalue of $\mathbf A$
== Proof ==
=== $(3)$ iff $(5)$ ===
See Elementary Row Operation on Augmented Matrix leads to Equivalent System of Simultaneous Linear Equations/Corollary 5.
=== $(1)$ iff $(3)$ ===
See Matrix Inverse Algorithm.
=== $(4)$ iff $(5)$ ===
Follows directly from the definition of a null space.
=== $(3)$ implies $(6)$ ===
Suppose that $\mathbf A$ row-reduces to the identity matrix $\mathbf I_n$.
Let $\mathbf b$ be arbitrary.
Let $\begin {pmatrix} \mathbf I_n & \mathbf s \end {pmatrix}$ be a reduced echelon matrix derived from $\begin {pmatrix} \mathbf A & \mathbf b \end {pmatrix}$.
By Elementary Row Operation on Augmented Matrix leads to Equivalent System of Simultaneous Linear Equations, the linear system $\mathbf A \mathbf x = \mathbf b$ has the same solutions as $\mathbf I_n \mathbf x = \mathbf s$.
But $\mathbf I_n \mathbf x = \mathbf x$, so $\mathbf x = \mathbf s$ is the unique solution to $\mathbf I_n \mathbf x = \mathbf s$.
Thus $\mathbf x = \mathbf s$ is the also the unique solution to $\mathbf A \mathbf x = \mathbf b$.
As $\mathbf b$ is arbitrary, the result follows.
=== $(6)$ implies $(5)$ ===
The result follows from setting $\mathbf b = \mathbf 0$.
=== $(4)$ iff $(7)$ ===
See Null Space Contains Only Zero Vector iff Columns are Independent.
=== $(7)$ iff $(8)$ iff $(9)$ ===
Follows directly from Sufficient Conditions for Basis of Finite Dimensional Vector Space.
=== $(3)$ iff $(10)$ ===
=== $(10)$ iff $(11)$ iff $(12)$ ===
Follows directly from Sufficient Conditions for Basis of Finite Dimensional Vector Space.
=== $(8)$ iff $(13)$ ===
Follows from the definition of rank of matrix and $\map \dim {K^n} = n$.
=== $(4)$ iff $(14)$ ===
Follows from the definition of nullity and $\map \dim {\set {\mathbf 0} } = 0$.
=== $(1)$ iff $(15)$ ===
See Matrix is Nonsingular iff Determinant has Multiplicative Inverse.
=== $(5)$ iff $(16)$ ===
From the definition of an eigenvalue:
:$0_K$ is an eigenvalue of $\mathbf A$ there exists a non-zero vector $\mathbf v$ such that $\mathbf {A v} = 0_K \mathbf v = \mathbf 0$
Therefore $\mathbf A \mathbf v = \mathbf 0$ has only the trivial solution $\mathbf 0$ $0_K$ is not an eigenvalue of $\mathbf A$.
=== $(1)$ iff $(2)$ ===
By Matrix is Nonsingular iff Determinant has Multiplicative Inverse:
:$\mathbf A$ is nonsingular the determinant of $\mathbf A$ is not zero
By Determinant of Transpose:
:$\map \det {\mathbf A} = \map \det {\mathbf A^\intercal}$
where $\map \det {\mathbf A}$ is the determinant of $\mathbf A$ and $\mathbf A^\intercal$ is the transpose of $\mathbf A$.
Therefore the determinant of $\mathbf A$ is not zero the determinant of $\mathbf A^\intercal$ is not zero.
By Matrix is Nonsingular iff Determinant has Multiplicative Inverse again:
:$\mathbf A^\intercal$ is nonsingular the determinant of $\mathbf A^\intercal$ is not zero
Hence $\mathbf A$ is nonsingular $\mathbf A^\intercal$ is nonsingular.
Hence all sixteen statements are logically equivalent.
Category:Nonsingular Matrices