**Theorem:** The following are equivalent for an $n \times n$ matrix $A$:
1. $A$ is nonsingular
2. $Ax = 0$ has only the trivial solution
3. $A$ row-reduces to $I$
4. $A$ is a product of elementary matrices

**Proof sketch:**
- (1) => (2): If $A^{-1}$ exists, multiply $Ax=0$ by $A^{-1}$ to get $x=0$.
- (2) => (3): If only trivial solution, RREF has no free variables, hence $n$ pivots, so RREF is $I$.
- (3) => (4): Row reduction means $E_k \cdots E_1 A = I$, so $A = E_1^{-1} \cdots E_k^{-1}$.
- (4) => (1): Product of invertible (elementary) matrices is invertible.