Elementary Operations, RREF & Block Matrices

1. The Three Elementary Row Operations

For a matrix $A \in M_{m \times n}(\mathbb{F})$, the elementary row operations are:

1. Type I (Row Interchange): $R_i \leftrightarrow R_j$ (swap rows $i$ and $j$).
2. Type II (Row Scaling): $R_i \to c R_i$ with $c \ne 0$ (multiply row $i$ by a non-zero scalar).
3. Type III (Row Addition): $R_i \to R_i + c R_j$ with $i \ne j$ (add a scalar multiple of row $j$ to row $i$).

2. Elementary Matrices

An elementary matrix $E$ is obtained by applying a single elementary row operation to the identity matrix $I_m$.
Fundamental Principle: Performing a row operation on $A$ is algebraically identical to pre-multiplying $A$ by the corresponding elementary matrix: $$\mathbf{A \xrightarrow{\text{Row Op}} B \iff B = E A}$$ Since each elementary matrix is invertible, two matrices $A$ and $B$ are row equivalent ($A \sim B$) if and only if there exist elementary matrices $E_1, \dots, E_k$ such that: $$B = E_k \cdots E_2 E_1 A = P A, \quad \text{where } P \text{ is invertible}$$

1. Row Echelon Form (REF)

A matrix is in Row Echelon Form if:

• All rows consisting entirely of zeros are at the bottom.
• The leading entry (first non-zero entry from the left, called the pivot) of each non-zero row is strictly to the right of the leading entry of the row above it.
• All entries in a column below a leading pivot are zero.

2. Reduced Row Echelon Form (RREF)

A matrix is in Reduced Row Echelon Form (RREF) if it satisfies REF and additionally:

1. Every leading pivot entry is equal to $1$.
2. Each leading pivot $1$ is the sole non-zero entry in its column (all entries above and below the pivot are zero).

1. Row Rank, Column Rank & Matrix Rank

• The row space $\text{Row}(A) \subseteq \mathbb{F}^n$ is the subspace spanned by the row vectors of $A$. Its dimension is the row rank.
• The column space $\text{Col}(A) \subseteq \mathbb{F}^m$ is the subspace spanned by the column vectors of $A$. Its dimension is the column rank.

2. The Rank-Nullity Theorem

The nullspace (kernel) of $A$ is $\text{Null}(A) = \{X \in \mathbb{F}^n \mid AX = 0\}$. Its dimension is the nullity of $A$, which equals the number of free variables (non-pivot columns) in $\text{rref}(A)$.
Theorem (Rank-Nullity): For any $m \times n$ matrix $A$: $$\mathbf{\text{rank}(A) + \text{nullity}(A) = n \quad (\text{number of columns})}$$

1. The Augmented Matrix

A system of $m$ linear equations in $n$ variables $AX = B$ is represented by the augmented matrix $[A \mid B] \in M_{m \times (n+1)}$. Applying Gauss-Jordan elimination transforms $[A \mid B]$ into $[R \mid B']$ in RREF without altering the solution set.

2. The Rouché–Capelli Consistency Theorem

Theorem: The linear system $AX = B$ is consistent (possesses at least one solution) if and only if the rank of the coefficient matrix equals the rank of the augmented matrix: $$\mathbf{\text{rank}(A) = \text{rank}([A \mid B])}$$ Classification of Solution Sets:

• Inconsistent (No Solutions): $\text{rank}(A) < \text{rank}([A \mid B])$. This occurs if and only if $\text{rref}([A \mid B])$ contains a row of the form $[0, 0, \dots, 0 \mid 1]$.
• Unique Solution: $\text{rank}(A) = \text{rank}([A \mid B]) = n$ (every column has a pivot, nullity = 0).
• Infinitely Many Solutions: $\text{rank}(A) = \text{rank}([A \mid B]) = r < n$. The general solution depends on $k = n - r$ arbitrary parameters (free variables).

1. Gauss-Jordan Inversion Algorithm

To invert an $n \times n$ matrix $A$, form the partitioned augmented matrix $[A \mid I_n]$. Apply elementary row operations to reduce $A$ to $I_n$: $$\mathbf{[A \mid I_n] \xrightarrow{\text{Gauss-Jordan}} [I_n \mid A^{-1}]}$$ If $\text{rref}(A)$ has fewer than $n$ pivots, $A$ is singular and has no inverse.

2. Block Matrices and the Schur Complement

Let $M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$ be a partitioned block matrix with $A$ invertible.
The Schur complement of $A$ in $M$ is defined by: $$\mathbf{S \equiv D - C A^{-1} B}$$ We factor $M$ via block Gaussian elimination: $$\begin{pmatrix} A & B \\ C & D \end{pmatrix} = \begin{pmatrix} I & 0 \\ C A^{-1} & I \end{pmatrix} \begin{pmatrix} A & 0 \\ 0 & S \end{pmatrix} \begin{pmatrix} I & A^{-1} B \\ 0 & I \end{pmatrix}$$ Consequently: $$\det(M) = \det(A) \det(S) = \det(A) \det(D - C A^{-1} B)$$ If $S$ is also invertible, the explicit block inverse is: $$\mathbf{M^{-1} = \begin{pmatrix} A^{-1} + A^{-1} B S^{-1} C A^{-1} & -A^{-1} B S^{-1} \\ -S^{-1} C A^{-1} & S^{-1} \end{pmatrix}}$$