Elementary Matrices

Definition

An elementary matrix is a matrix that differs from the identity matrix by a single elementary row operation. Left-multiplying a matrix $\mathrm{A}$ by an elementary matrix applies that row operation to $\mathrm{A}$.

Intuition

Every row operation is secretly a matrix multiplication. Writing elimination as ${\mathrm{M}}_{\mathrm{k}}\cdots {\mathrm{M}}_1\mathrm{A}=\mathrm{U}$ turns the algorithmic sequence of steps into an algebraic identity, which then immediately yields the LU factorisation by inverting each ${\mathrm{M}}_{\mathrm{i}}$.

Formal Description

Each step of Gaussian Elimination can be expressed as left-multiplication by an elementary matrix. For the matrix

$$\mathrm{A}=\left(\begin{array}{ccc}-3& 2& -1\\ 6& -6& 7\\ 3& -4& 4\end{array}\right),$$

the three elimination steps give ${\mathrm{M}}_3{\mathrm{M}}_2{\mathrm{M}}_1\mathrm{A}=\mathrm{U}$, where:

$${\mathrm{M}}_1=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1\end{array}\right),{\mathrm{M}}_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right),{\mathrm{M}}_3=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -1& 1\end{array}\right),$$

and $\mathrm{U}$ is the resulting upper-triangular matrix. ${\mathrm{M}}_1$ adds twice row 1 to row 2; ${\mathrm{M}}_2$ adds row 1 to row 3; ${\mathrm{M}}_3$ subtracts row 2 from row 3.

Elementary matrices are always invertible; the inverse reverses the row operation (e.g., if $\mathrm{M}$ adds $c$ times row $i$ to row $j$, then ${\mathrm{M}}^{-1}$ adds $-c$ times row $i$ to row $j$). The factorisation ${\mathrm{M}}_{\mathrm{k}}\cdots {\mathrm{M}}_1\mathrm{A}=\mathrm{U}$ is the foundation of LU Decomposition.

Applications

• Provides the algebraic proof that Gaussian elimination produces an LU factorisation.
• Used to derive properties of determinants under row operations.

Trade-offs

• Elementary matrices are conceptually useful but are rarely formed explicitly in practice; storing and multiplying $n$ separate $n\times n$ matrices costs far more than simply recording the multipliers.
• Only applicable when row operations suffice; column operations require right-multiplication, which is distinct.

Links

• Gaussian Elimination
• LU Decomposition