Matrices and Row Reduction

Summary

Matrices represent linear maps and store coefficients of linear systems. Elementary row operations implement Gaussian elimination, producing row echelon forms that reveal rank, invertibility, and solution structure.

Prerequisites

Systems of Linear Equations. Hub: Linear Algebra.

Definition / Statement

An $m \times n$ matrix $A$ is a rectangular array of scalars $a_{i j}$ . Matrix–vector multiplication $A x$ defines a map $R^{n} \to R^{m}$ that is linear:

A (u + v) = A u + A v, A (c u) = c A u .

Elementary row operations on a matrix:

Swap two rows.
Multiply a row by a nonzero scalar.
Add a scalar multiple of one row to another row.

These operations do not change the solution set of $A x = b$ when applied to the augmented matrix.

Objects and Dimensions

Object	Meaning	Dimensions
$A$	matrix	$m \times n$
$A x$	linear map applied to $x$	$m \times 1$
$A B$	product (columns of $B$ mapped by $A$ )	$m \times p$ if $B$ is $n \times p$
$I_{n}$	identity	$n \times n$
$rank (A)$	number of pivots / dimension of column space	integer

Notation

Symbol	Meaning
$REF$	row echelon form
$RREF$	reduced row echelon form
pivot	first nonzero entry in a row of REF/RREF
$A^{- 1}$	inverse matrix (square, when it exists)

Conditions / Assumptions

Matrix product $A B$ requires the number of columns of $A$ to equal the number of rows of $B$ .
$A$ is invertible if and only if $A$ is square and $rank (A) = n$ (full pivots), equivalently $A x = b$ has a unique solution for every $b$ .
Row reduction assumes exact arithmetic in theory; numerical practice needs pivoting strategies (see numerical methods notes).

Matrix / Vector Form

Identity and inverse (for invertible $A \in R^{n \times n}$ ):

A A^{- 1} = A^{- 1} A = I_{n} .

Solving via inverse (when $A$ is invertible): $x = A^{- 1} b$ . Prefer row reduction in hand computation.

Rank: $rank (A)$ equals the number of pivot positions after row reduction, and equals the dimension of the column space (and of the row space).

Procedure

Gaussian elimination to REF:

Find the leftmost nonzero column; swap a nonzero entry into the pivot row if needed.
Scale (optional) and eliminate entries below the pivot.
Repeat on the submatrix below and to the right of the pivot.
For RREF, eliminate above pivots and scale pivots to $1$ .

To invert $A$ , row-reduce $[A ∣ I]$ to $[I ∣ A^{- 1}]$ when possible.

Worked Example

A = (\begin{matrix} 1 & 2 & 1 \\ 2 & 4 & 0 \\ 3 & 6 & 1 \end{matrix}) .

$R_{2} \leftarrow R_{2} - 2 R_{1}$ , $R_{3} \leftarrow R_{3} - 3 R_{1}$ :

(\begin{matrix} 1 & 2 & 1 \\ 0 & 0 & - 2 \\ 0 & 0 & - 2 \end{matrix}) .

$R_{3} \leftarrow R_{3} - R_{2}$ , then scale $R_{2}$ : pivots in columns 1 and 3, so $rank (A) = 2$ . The middle column is a free-direction indicator for null-space structure when solving $A x = b$ .

Common Mistakes

Multiplying matrices entrywise instead of using row–column products.
Assuming $A B = B A$ .
Scaling a row by zero (destroys information; not an elementary operation).
Calling $f (x) = A x + b$ linear when $b \neq 0$ .

Connections

Related: Systems of Linear Equations, Determinants, Vector Spaces and Bases
Next: Determinants or Vector Spaces and Bases
Numerical: LU factorization and elimination methods under Numerical Methods

References

Matrix algebra and elimination follow MIT 18.06 (Strang).^[1]

MIT OpenCourseWare, 18.06 Linear Algebra, https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/ ↩︎