LA-4.4

Available

Elementary Matrices

Elementary matrices are the building blocks that make Gaussian elimination work. Each row operation corresponds to multiplication by an elementary matrix.

Learning Objectives

Define the three types of elementary matrices
Understand left multiplication as row operations
Understand right multiplication as column operations
Prove that elementary matrices are invertible
Express invertible matrices as products of elementary matrices
Use elementary matrices to compute inverses
Connect elementary matrices to Gaussian elimination
Apply elementary matrices to matrix factorizations

Prerequisites

Matrix multiplication (LA-4.2)
Matrix inverse (LA-4.3)
Gaussian elimination basics
Row echelon form

1. Definition of Elementary Matrices

Elementary matrices provide the algebraic foundation for row operations. They transform Gaussian elimination from an algorithm into pure matrix multiplication.

Definition 4.15: Elementary Matrix

An elementary matrix is a matrix obtained from the identity matrix $I$ by performing exactly one elementary row operation.

Definition 4.16: Three Types of Elementary Matrices

The three types correspond to the three types of row operations:

Type I (Swap): $E_{ij}$ — Swap rows $i$ and $j$
Type II (Scale): $E_i(c)$ — Multiply row $i$ by scalar $c \neq 0$
Type III (Add): $E_{ij}(c)$ — Add $c$ times row $i$ to row $j$

Example 4.12: Elementary Matrices in 3×3

Here are examples of each type for $3 \times 3$ matrices:

E_{12} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad E_2(5) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 1 \end{pmatrix}

E_{21}(3) = \begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}

$E_{12}$ swaps rows 1 and 2; $E_2(5)$ multiplies row 2 by 5; $E_{21}(3)$ adds 3 times row 1 to row 2.

2. The Fundamental Property

Theorem 4.28: Elementary Matrices and Row Operations

Left-multiplying a matrix $A$ by an elementary matrix $E$ performs the corresponding row operation on $A$ :

EA = \text{result of applying the row operation to } A

Proof:

Consider $E_{ij}(c)$ which adds $c$ times row $i$ to row $j$ . The product $E_{ij}(c) A$ :

Row $k$ of $E_{ij}(c)$ is $e_k$ if $k \neq j$
Row $j$ of $E_{ij}(c)$ is $e_j + c e_i$

So row $k$ of $E_{ij}(c) A$ is row $k$ of $A$ when $k \neq j$ , and row $j$ of $E_{ij}(c) A$ is $(\text{row } j \text{ of } A) + c \cdot (\text{row } i \text{ of } A)$ .

∎

Corollary 4.9: Right Multiplication for Column Operations

Right-multiplying by an elementary matrix performs the corresponding column operation:

AE = \text{result of applying the column operation to } A

Remark 4.21: Why Left = Row, Right = Column

In $EA$ , each row of the result is a linear combination of rows of $A$ (determined by $E$ ). In $AE$ , each column of the result is a linear combination of columns of $A$ .

3. Inverses of Elementary Matrices

Theorem 4.29: Elementary Matrices are Invertible

Every elementary matrix is invertible, and its inverse is also an elementary matrix:

$E_{ij}^{-1} = E_{ij}$ (swap twice returns to original)
$E_i(c)^{-1} = E_i(1/c)$ (undo scaling by $c$ by scaling by $1/c$ )
$E_{ij}(c)^{-1} = E_{ij}(-c)$ (undo adding $c$ times by subtracting)

Proof:

Each row operation is reversible:

Swap: $E_{ij} E_{ij} = I$ since swapping twice returns to the original
Scale: $E_i(c) E_i(1/c) = I$ since multiplying by $c$ then $1/c$ gives 1
Add: $E_{ij}(c) E_{ij}(-c) = I$ since adding then subtracting cancels

∎

Remark 4.22: The Key Insight

Since elementary matrices are invertible, products of elementary matrices are invertible. This is crucial for the next theorem.

4. Invertible Matrices as Products of Elementary Matrices

Theorem 4.30: Fundamental Factorization Theorem

A square matrix $A$ is invertible if and only if $A$ is a product of elementary matrices:

A \text{ invertible} \iff A = E_1 E_2 \cdots E_k

Proof:

(⇐): Products of invertible matrices are invertible.

(⇒): If $A$ is invertible, Gaussian elimination reduces $A$ to $I$ :

E_k \cdots E_2 E_1 A = I

Therefore:

A = E_1^{-1} E_2^{-1} \cdots E_k^{-1}

Since inverses of elementary matrices are elementary, $A$ is a product of elementary matrices.

∎

Corollary 4.10: Computing the Inverse

If $E_k \cdots E_1 A = I$ , then:

A^{-1} = E_k \cdots E_1

This is why row-reducing $[A|I]$ to $[I|A^{-1}]$ works!

5. Gaussian Elimination as Matrix Multiplication

Gaussian elimination is not just an algorithm—it's matrix multiplication by a product of elementary matrices.

Theorem 4.31: Gaussian Elimination as Matrix Product

If Gaussian elimination transforms $A$ to row echelon form $U$ via row operations $E_1, E_2, \ldots, E_k$ , then:

E_k \cdots E_2 E_1 A = U

Letting $P = E_k \cdots E_1$ , we have $PA = U$ .

Example 4.13: Elimination as Matrix Product

Consider reducing $A = \begin{pmatrix} 2 & 4 \\ 1 & 3 \end{pmatrix}$ :

Step 1: Swap rows: $E_{12} A = \begin{pmatrix} 1 & 3 \\ 2 & 4 \end{pmatrix}$

Step 2: Subtract 2×row 1 from row 2: $E_{12}(-2) E_{12} A = \begin{pmatrix} 1 & 3 \\ 0 & -2 \end{pmatrix}$

So $P = E_{12}(-2) E_{12}$ and $PA = U$ .

6. Introduction to LU Decomposition

When Gaussian elimination requires no row swaps, we get a beautiful factorization.

Theorem 4.32: LU Decomposition

If $A$ can be reduced to row echelon form $U$ using only Type III operations (no row swaps), then:

A = LU

where $L$ is lower triangular and $U$ is upper triangular.

Proof:

If $E_k \cdots E_1 A = U$ with each $E_j$ of Type III, then:

A = E_1^{-1} \cdots E_k^{-1} U = LU

where $L = E_1^{-1} \cdots E_k^{-1}$ . Since inverses of lower triangular Type III matrices are lower triangular, $L$ is lower triangular.

∎

Remark 4.23: Why LU is Useful

To solve $Ax = b$ with $A = LU$ :

Solve $Ly = b$ (forward substitution)
Solve $Ux = y$ (back substitution)

Each step is $O(n^2)$ . For multiple right-hand sides, compute $LU$ once and solve quickly each time.

7. Worked Examples

Example 1: Express as Product of Elementary Matrices

Problem: Express $A = \begin{pmatrix} 1 & 2 \\ 3 & 8 \end{pmatrix}$ as a product of elementary matrices.

Solution: Row reduce to $I$ :

\begin{pmatrix} 1 & 2 \\ 3 & 8 \end{pmatrix} \xrightarrow{R_2 - 3R_1} \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix} \xrightarrow{R_2/2} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} \xrightarrow{R_1 - 2R_2} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}

So $E_{12}(-2) E_2(1/2) E_{21}(-3) A = I$ .

Therefore: $A = E_{21}(3) E_2(2) E_{12}(2)$

Example 2: Finding LU

Problem: Find the LU decomposition of $A = \begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix}$ .

Solution: Eliminate using $R_2 - 3R_1$ :

U = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}

The multiplier was 3, so:

L = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}

Verify: $LU = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix} = A$ ✓

8. Common Mistakes

Mistake 1: Order of Multiplication

If operations are $E_1, E_2, \ldots, E_k$ in order, the product is $E_k \cdots E_2 E_1$ (reversed!). The LAST operation is on the LEFT.

Mistake 2: Confusing Left and Right

Left multiplication = row operations. Right multiplication = column operations. $EA$ changes rows; $AE$ changes columns.

Mistake 3: Type III Inverse

$E_{ij}(c)^{-1} = E_{ij}(-c)$ , not $E_{ji}(-c)$ . The indices stay the same; only the scalar changes sign.

9. Key Takeaways

Three Types

Swap ( $E_{ij}$ ), Scale ( $E_i(c)$ ), Add ( $E_{ij}(c)$ )

Always Invertible

Elementary matrices are invertible, and inverses are also elementary.

Fundamental Theorem

$A$ invertible ⟺ $A$ = product of elementary matrices.

Gaussian = Matrix Mult

$E_k \cdots E_1 A = U$ encodes entire elimination process.

10. Determinants of Elementary Matrices

Theorem 4.33: Determinants of Elementary Matrices

The determinants of elementary matrices are:

$\det(E_{ij}) = -1$ (swap changes sign)
$\det(E_i(c)) = c$ (scaling multiplies determinant by $c$ )
$\det(E_{ij}(c)) = 1$ (adding doesn't change determinant)

Proof:

Type I (Swap): $E_{ij}$ is obtained from $I$ by swapping two rows. Since swapping rows changes the sign of the determinant, $\det(E_{ij}) = -\det(I) = -1$ .

Type II (Scale): $E_i(c)$ multiplies one row by $c$ . This multiplies the determinant by $c$ , so $\det(E_i(c)) = c \cdot \det(I) = c$ .

Type III (Add): $E_{ij}(c)$ adds a multiple of one row to another. This doesn't change the determinant, so $\det(E_{ij}(c)) = \det(I) = 1$ .

∎

Corollary 4.11: Determinant of Product

Since $\det(EA) = \det(E) \cdot \det(A)$ , we can compute how row operations affect determinants:

Swapping rows multiplies $\det(A)$ by $-1$
Scaling row $i$ by $c$ multiplies $\det(A)$ by $c$
Adding a multiple of one row to another doesn't change $\det(A)$

11. Additional Practice Problems

Problem 1

Write down the elementary matrix that multiplies row 3 by 7 for a $4 \times 4$ matrix.

Problem 2

If $E_1 E_2 A = I$ , express $A^{-1}$ in terms of $E_1$ and $E_2$ .

Problem 3

Prove that $(E_{ij})^T = E_{ij}$ for swap matrices.

Problem 4

Express $\begin{pmatrix} 2 & 3 \\ 4 & 7 \end{pmatrix}$ as a product of elementary matrices.

Problem 5

Show that $(E_i(c))^T = E_i(c)$ for scaling matrices.

12. Transpose of Elementary Matrices

Theorem 4.34: Transpose Properties

The transpose of each elementary matrix type:

$E_{ij}^T = E_{ij}$ (swap is symmetric)
$E_i(c)^T = E_i(c)$ (scale is symmetric)
$E_{ij}(c)^T = E_{ji}(c)$ (add transposes indices)

Remark 4.24: Row vs Column Operations

This means that if $E$ performs a row operation when left-multiplied, then $E^T$ performs the "same" column operation when right-multiplied. Specifically:

$EA$ : row operation on $A$
$AE^T$ : corresponding column operation on $A$

13. Block Elementary Matrices

The concept of elementary matrices extends to block matrices, where we perform operations on block rows/columns.

Definition 4.17: Block Row Operations

For a block matrix, block elementary operations are:

Swap two block rows
Multiply a block row by an invertible matrix (on the left)
Add a matrix multiple of one block row to another

Example 4.14: Block Elimination

For $\begin{pmatrix} A & B \\ C & D \end{pmatrix}$ with $A$ invertible:

\begin{pmatrix} I & 0 \\ -CA^{-1} & I \end{pmatrix}\begin{pmatrix} A & B \\ C & D \end{pmatrix} = \begin{pmatrix} A & B \\ 0 & D - CA^{-1}B \end{pmatrix}

The matrix $D - CA^{-1}B$ is called the Schur complement of $A$ .

14. Connections to Other Topics

Matrix Rank

Elementary row/column operations don't change the rank. This is because elementary matrices are invertible:

\text{rank}(EA) = \text{rank}(A)

Equivalent Standard Form

Using both row and column operations, any matrix can be reduced to:

PAQ = \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix}

where $r$ is the rank and $P$ , $Q$ are products of elementary matrices.

Change of Basis

Elementary operations on the matrix of a linear map correspond to changing the basis. This is the foundation for canonical forms like Jordan form.

15. Theoretical Insights

Theorem 4.35: Generation of General Linear Group

The set of $n \times n$ elementary matrices generates $GL_n(F)$ (the group of invertible matrices):

GL_n(F) = \langle E_{ij}, E_i(c), E_{ij}(c) \rangle

Remark 4.25: Finite vs Infinite Generation

While there are infinitely many elementary matrices, only finitely many are needed to generate any particular invertible matrix. This is the content of the factorization theorem.

Theorem 4.36: Permutation Matrices

Products of swap matrices $E_{ij}$ form the symmetric group $S_n$ (permutation matrices). Every permutation can be written as a product of transpositions.

16. Study Tips

Visualize the Operation

Before computing, think about what each elementary matrix does to the identity. That same operation happens to any matrix you multiply.

Remember the Order

Operations $E_1, E_2, E_3$ in that order become $E_3 E_2 E_1 A$ . The LAST operation is LEFTMOST.

Verify with Small Cases

Check your understanding with $2 \times 2$ matrices where you can easily verify $EA$ does the expected row operation.

Think Algorithmically

Gaussian elimination is just multiplication by elementary matrices. This connects theory to computation.

17. Historical Notes

Origins of Gaussian Elimination: While Carl Friedrich Gauss popularized the elimination method in the early 1800s for astronomical calculations, the algorithm was known in ancient China nearly 2000 years earlier.

Matrix Formulation: The idea of expressing row operations as matrix multiplication came with the development of matrix algebra by Cayley and Sylvester in the mid-1800s. This unified algorithm and algebra.

LU Decomposition: Alan Turing and others developed practical algorithms for LU decomposition in the 1940s for early computers. The method remains central to numerical linear algebra today.

Modern Impact: Elementary matrices connect abstract algebra (group generation) with practical computation (Gaussian elimination), showing the deep unity of mathematics.

18. More Worked Examples

Example: Finding the Inverse via Elementary Matrices

Problem: Find $A^{-1}$ for $A = \begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & 2 \\ 2 & -1 & -1 \end{pmatrix}$ .

Solution: Row reduce $[A|I]$ to $[I|A^{-1}]$ :

\begin{pmatrix} 0 & 1 & 2 & | & 1 & 0 & 0 \\ 1 & 0 & 2 & | & 0 & 1 & 0 \\ 2 & -1 & -1 & | & 0 & 0 & 1 \end{pmatrix}

Step 1: Swap $R_1 \leftrightarrow R_2$ (using $E_{12}$ )

Step 2: $R_3 - 2R_1$ (using $E_{31}(-2)$ )

Step 3: Continue to reach $I$ on the left

The sequence of operations $E_k \cdots E_1$ applied to $I$ gives $A^{-1}$ .

Example: PLU Decomposition

Problem: When row swaps are needed, we get $PA = LU$ .

Setup: If $A = \begin{pmatrix} 0 & 1 \\ 2 & 3 \end{pmatrix}$ , we need to swap rows first.

P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad PA = \begin{pmatrix} 2 & 3 \\ 0 & 1 \end{pmatrix}

Now $PA = LU$ where $L = I$ and $U = PA$ (no further elimination needed).

Example: Product Verification

Problem: Verify that $E_{12}(-3) E_{12} = \begin{pmatrix} 1 & -3 \\ 0 & 1 \end{pmatrix}$ .

Solution:

E_{12}(-3) = \begin{pmatrix} 1 & -3 \\ 0 & 1 \end{pmatrix}, \quad E_{12} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}

E_{12}(-3) E_{12} = \begin{pmatrix} 1 & -3 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} -3 & 1 \\ 1 & 0 \end{pmatrix}

Note: This is NOT what was stated—always verify your computations!

19. Applications of Elementary Matrices

Solving Linear Systems

Gaussian elimination on $Ax = b$ is equivalent to computing $E_k \cdots E_1 A x = E_k \cdots E_1 b$ . This transforms the system to $Ux = c$ where $U$ is upper triangular.

Computing Determinants

Row reduce to upper triangular form, tracking the effect on the determinant:

\det(A) = \frac{\det(U)}{\det(E_1) \cdots \det(E_k)}

For triangular $U$ , the determinant is the product of diagonal entries.

Matrix Factorizations

Elementary matrices are the building blocks for:

LU: $A = LU$ from elimination without row swaps
PLU: $PA = LU$ with permutation matrix $P$
QR: Different elementary matrices (Householder reflections)

20. Quick Reference Summary

Type	Notation	Inverse	Determinant	Transpose
Swap	$E_{ij}$	$E_{ij}$	$-1$	$E_{ij}$
Scale	$E_i(c)$	$E_i(1/c)$	$c$	$E_i(c)$
Add	$E_{ij}(c)$	$E_{ij}(-c)$	$1$	$E_{ji}(c)$

21. Challenge Problems

Challenge 1: Minimum Number of Operations

What is the minimum number of elementary row operations needed to reduce $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$ to row echelon form?

Challenge 2: Commuting Elementary Matrices

For which pairs of elementary matrices $E$ and $F$ is $EF = FE$ ? Characterize all commuting pairs.

Challenge 3: Order of Operations

Prove that the set of Type III elementary matrices forms a subgroup of $GL_n(F)$ (it's actually a normal subgroup!).

22. Geometric Interpretation

Type I: Reflections

Row swap matrices $E_{ij}$ are reflections across certain hyperplanes. In 2D, $E_{12}$ reflects across the line $y = x$ .

Type II: Scaling

Scale matrices $E_i(c)$ stretch or compress along one axis by factor $c$ . They change volumes by factor $|c|$ .

Type III: Shears

Add matrices $E_{ij}(c)$ are shear transformations. They preserve volumes (determinant = 1) but change angles.

Key Takeaways

• Three types: swap (det=-1), scale (det=c), add (det=1)
• All invertible matrices are products of elementary matrices
• Row operations = left multiplication by elementary matrices
• Foundation for LU decomposition and Gaussian elimination
• Geometric view: reflections, scalings, and shears
• Every invertible matrix can be written as product of elementary matrices
• Inverse of elementary matrix is also elementary of same type

Applications of Elementary Matrices

LU Decomposition

Factor $A = LU$ where $L$ is product of Type III inverses and $U$ is upper triangular.

Gauss-Jordan Method

Compute $A^{-1}$ by applying elementary operations to reduce $[A|I]$ to $[I|A^{-1}]$ .

Determinant Computation

Track determinant changes: swap (×−1), scale (×c), add (×1). Get det from upper triangular form.

Numerical Stability

Pivoting strategies (row swaps) improve numerical stability in floating-point computation.

Historical Notes

Carl Friedrich Gauss (1777-1855): Developed the systematic elimination method, though he didn't express it in matrix form.

Camille Jordan (1838-1922): Formalized reduction to canonical form and elementary operations in his work on group theory.

Modern Computing: Elementary matrices form the theoretical basis for LAPACK, BLAS, and all numerical linear algebra libraries.

Pivoting Strategies: Partial and complete pivoting (row swaps) were developed in the 1960s to ensure numerical stability.

These algorithms are now implemented in every scientific computing platform.

💡 Remember

Elementary matrices are the "atoms" of matrix theory. Every matrix operation can be decomposed into a sequence of these simple building blocks.

Mastering elementary matrices gives you deep insight into all matrix algorithms!

Foundation for: LU, QR, SVD decompositions

What's Next?

Now that you understand elementary matrices, the next topics apply these concepts:

Matrix Rank: The fundamental dimension that determines solvability
Determinants: A scalar that detects invertibility
Eigenvalues: The next major topic in linear algebra

Elementary matrices provide the computational foundation for nearly all matrix algorithms.

Elementary Matrices Practice

Questions

Correct

Accuracy

Elementary matrices are always:

Easy

Not attempted

Left-multiplying by an elementary matrix performs a:

Easy

Not attempted

The inverse of a row-swap elementary matrix is:

Medium

Not attempted

E_i(c)

multiplies row

i

c \neq 0

, then

E_i(c)^{-1} =

Medium

Not attempted

E_{ij}(c)

adds

c

times row

i

to row

j

, then

E_{ij}(c)^{-1} =

Medium

Not attempted

Every invertible matrix is a product of:

Medium

Not attempted

The determinant of a row-swap elementary matrix is:

Medium

Not attempted

Right-multiplying by an elementary matrix performs a:

Easy

Not attempted

Elementary matrices are obtained from

I

by:

Easy

Not attempted

PA = U

where

U

is row echelon form, then

P

is:

Hard

Not attempted

Elementary Matrices

1. Definition of Elementary Matrices

2. The Fundamental Property

3. Inverses of Elementary Matrices

4. Invertible Matrices as Products of Elementary Matrices

5. Gaussian Elimination as Matrix Multiplication

6. Introduction to LU Decomposition

7. Worked Examples

8. Common Mistakes

Mistake 1: Order of Multiplication

Mistake 2: Confusing Left and Right

Mistake 3: Type III Inverse

9. Key Takeaways

Three Types

Always Invertible

Fundamental Theorem

Gaussian = Matrix Mult

10. Determinants of Elementary Matrices

11. Additional Practice Problems

12. Transpose of Elementary Matrices

13. Block Elementary Matrices

14. Connections to Other Topics

15. Theoretical Insights

16. Study Tips

Visualize the Operation

Remember the Order

Verify with Small Cases

Think Algorithmically

17. Historical Notes

18. More Worked Examples

19. Applications of Elementary Matrices

20. Quick Reference Summary

21. Challenge Problems

Challenge 1: Minimum Number of Operations

Challenge 2: Commuting Elementary Matrices

Challenge 3: Order of Operations

22. Geometric Interpretation

Type I: Reflections

Type II: Scaling

Type III: Shears

Key Takeaways

Related Topics

Applications of Elementary Matrices

LU Decomposition

Gauss-Jordan Method

Determinant Computation

Numerical Stability

Historical Notes

💡 Remember

What's Next?