Elementary Matrices, Invertibility, and LU Factorization

Identity Matrices and Elementary Matrix Fundamentals

  • The n×nn \times n identity matrix II is defined by standard basis row vectors:   \n  I = \begin{bmatrix} 1 & & O \\ & \ddots & \\ O & & 1 \end{bmatrix} = \begin{bmatrix} \vec{e}_1 \\ \vec{e}_2 \\ \vdots \\ \vec{e}_n \end{bmatrix}\n     where each standard basis vector e⃗i\vec{e}_i has a value of 11 in the ii-th entry and 00 elsewhere:   \n  \vec{e}_i = (0, 0, \dots, 1, 0, \dots, 0)\n  

  • An elementary matrix is defined as a matrix obtained by performing exactly one elementary row operation on the identity matrix II.

  • There are three distinct types of elementary matrices corresponding directly to the three elementary row operations:

    • Type I: Row interchange.
    • Type II: Multiplication of a row by a nonzero scalar.
    • Type III: Addition of a scalar multiple of one row to another row.

Types of Elementary Matrices

  • Type I Elementary Matrix:

    • Constructed by interchanging the ii-th row and the jj-th row of II (I→Ri↔RjEI \xrightarrow{R_i \leftrightarrow R_j} E):     \n    I = \begin{bmatrix} \vec{e}_1 \\ \vdots \\ \vec{e}_i \\ \vdots \\ \vec{e}_j \\ \vdots \\ \vec{e}_n \end{bmatrix} \xrightarrow{R_i \leftrightarrow R_j} \begin{bmatrix} \vec{e}_1 \\ \vdots \\ \vec{e}_j \\ \vdots \\ \vec{e}_i \\ \vdots \\ \vec{e}_n \end{bmatrix} = E\n    
    • Example in 3×33 \times 3 space with R2↔R3R_2 \leftrightarrow R_3:     \n    I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{R_2 \leftrightarrow R_3} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} = E\n    

  • Type II Elementary Matrix:

    • Constructed by multiplying the ii-th row of II by a nonzero scalar α\alpha (I→αRiEI \xrightarrow{\alpha R_i} E, where α≠0\alpha \neq 0):     \n    I = \begin{bmatrix} \vec{e}_1 \\ \vdots \\ \vec{e}_i \\ \vdots \\ \vec{e}_n \end{bmatrix} \xrightarrow{\alpha R_i} \begin{bmatrix} \vec{e}_1 \\ \vdots \\ \alpha\vec{e}_i \\ \vdots \\ \vec{e}_n \end{bmatrix} = E\n    
    • Example in 3×33 \times 3 space with 3R23R_2:     \n    I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{3R_2} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix} = E\n    

  • Type III Elementary Matrix:

    • Constructed by adding α\alpha times the ii-th row of II to the jj-th row of II (I→αRi+RjEI \xrightarrow{\alpha R_i + R_j} E):     \n    I = \begin{bmatrix} \vec{e}_1 \\ \vdots \\ \vec{e}_i \\ \vdots \\ \vec{e}_j \\ \vdots \\ \vec{e}_n \end{bmatrix} \xrightarrow{\alpha R_i + R_j} \begin{bmatrix} \vec{e}_1 \\ \vdots \\ \vec{e}_i \\ \vdots \\ \alpha\vec{e}_i + \vec{e}_j \\ \vdots \\ \vec{e}_n \end{bmatrix} = E\n    
    • Example in 3×33 \times 3 space with 2R1+R32R_1 + R_3:     \n    I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \xrightarrow{2R_1 + R_3} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix} = E\n    

Elementary Matrices and Matrix Multiplication Operations

  • Let EE be an n×nn \times n elementary matrix and let AA be an arbitrary n×nn \times n matrix:

    • Left multiplication (EAEA) performs the corresponding elementary row operation on AA.
    • Right multiplication (AEAE) performs a corresponding column operation on AA.

  • Type I Matrix Multiplication Dynamics:

    • Let EE be defined by I→Ri↔RjEI \xrightarrow{R_i \leftrightarrow R_j} E.
    • Then EA=U1EA = U_1, where A→Ri↔RjU1A \xrightarrow{R_i \leftrightarrow R_j} U_1.
    • Then AE=U2AE = U_2, where A→Ci↔CjU2A \xrightarrow{C_i \leftrightarrow C_j} U_2.
    • The notation Ci↔CjC_i \leftrightarrow C_j denotes the interchange of the ii-th and jj-th columns of AA.
    • Concrete Type I matrix multiplication demonstration:     \n    E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \quad A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\n         \n    EA = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{31} & a_{32} & a_{33} \\ a_{21} & a_{22} & a_{23} \end{bmatrix}\n         \n    AE = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} a_{11} & a_{13} & a_{12} \\ a_{21} & a_{23} & a_{22} \\ a_{31} & a_{33} & a_{32} \end{bmatrix}\n    

  • Type II Matrix Multiplication Dynamics:

    • Let EE be defined by I→αRiEI \xrightarrow{\alpha R_i} E.
    • Then EA=U1EA = U_1, where A→αRiU1A \xrightarrow{\alpha R_i} U_1.
    • Then AE=U2AE = U_2, where A→αCiU2A \xrightarrow{\alpha C_i} U_2.
    • The notation αCi\alpha C_i denotes the multiplication of the ii-th column of AA by a nonzero scalar α\alpha.
    • Concrete Type II matrix multiplication demonstration:     \n    E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\n         \n    EA = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ 3a_{21} & 3a_{22} & 3a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\n         \n    AE = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} a_{11} & 3a_{12} & a_{13} \\ a_{21} & 3a_{22} & a_{23} \\ a_{31} & 3a_{32} & a_{33} \end{bmatrix}\n    

  • Type III Matrix Multiplication Dynamics:

    • Let EE be defined by I→αRi+RjEI \xrightarrow{\alpha R_i + R_j} E.
    • Then EA=U1EA = U_1, where A→αRi+RjU1A \xrightarrow{\alpha R_i + R_j} U_1.
    • Then AE=U2AE = U_2, where A→αCj+CiU2A \xrightarrow{\alpha C_j + C_i} U_2.
    • The notation αCj+Ci\alpha C_j + C_i denotes replacing the ii-th column of AA by its sum with α\alpha times the jj-th column.
    • Concrete Type III matrix multiplication demonstration:     \n    E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix}, \quad A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\n         \n    EA = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ 2a_{11} + a_{31} & 2a_{12} + a_{32} & 2a_{13} + a_{33} \end{bmatrix}\n         \n    AE = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix} = \begin{bmatrix} a_{11} + 2a_{13} & a_{12} & a_{13} \\ a_{21} + 2a_{23} & a_{22} & a_{23} \\ a_{31} + 2a_{33} & a_{32} & a_{33} \end{bmatrix}\n    

Invertibility and Inverses of Elementary Matrices

  • Theorem on Elementary Matrix Invertibility:

    • If EE is an elementary matrix, then EE is nonsingular, and its inverse E−1E^{-1} is an elementary matrix of the exact same type.

  • Proof for Type I Elementary Matrices:

    • If EE is generated by I→Ri↔RjEI \xrightarrow{R_i \leftrightarrow R_j} E, applying the same operation twice restores the identity matrix:     \n    EE = I\n    
    • Consequently, EE is its own inverse:     \n    E^{-1} = E\n    

  • Proof for Type II Elementary Matrices:

    • If EE is generated by I→αRiEI \xrightarrow{\alpha R_i} E, then EE possesses diagonal entries equal to 11 everywhere except at position (i,i)(i, i), which is α\alpha:     \n    E = \begin{bmatrix} 1 & & & & \\ & \ddots & & & \\ & & \alpha & & \\ & & & \ddots & \\ & & & & 1 \end{bmatrix} \rightarrow \text{row } i\n    
    • The operation is inverted by dividing row ii by α\alpha (multiplying by 1α\frac{1}{\alpha}):     \n    E^{-1} = \begin{bmatrix} 1 & & & & \\ & \ddots & & & \\ & & \frac{1}{\alpha} & & \\ & & & \ddots & \\ & & & & 1 \end{bmatrix} \rightarrow \text{row } i\n    
    • Thus, E−1E^{-1} is an elementary matrix of Type II obtained via I→1αRiE−1I \xrightarrow{\frac{1}{\alpha} R_i} E^{-1}.

  • Proof for Type III Elementary Matrices:

    • If EE is generated by I→αRi+RjEI \xrightarrow{\alpha R_i + R_j} E, then EE matches the identity matrix with the single addition of the value α\alpha located at entry (j,i)(j, i), where jj is the row and ii is the column:     \n    E = \begin{bmatrix} 1 & & & & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & \vdots & \ddots & & \\ & & \alpha & \dots & 1 & \\ & & & & & \ddots \end{bmatrix} \begin{matrix} \\ \\ \rightarrow \text{row } i \\ \\ \rightarrow \text{row } j \\ \end{matrix}\n    
    • The inverse operation subtracts α\alpha times row ii from row jj ((−α)Ri+Rj(-\alpha) R_i + R_j):     \n    E^{-1} = \begin{bmatrix} 1 & & & & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & \vdots & \ddots & & \\ & & -\alpha & \dots & 1 & \\ & & & & & \ddots \end{bmatrix} \begin{matrix} \\ \\ \rightarrow \text{row } i \\ \\ \rightarrow \text{row } j \\ \end{matrix}\n    
    • Thus, E−1E^{-1} is an elementary matrix of Type III obtained via I→−αRi+RjE−1I \xrightarrow{-\alpha R_i + R_j} E^{-1}.

Row Equivalence of Matrices

  • Definition of Row Equivalence:

    • A matrix BB is row equivalent to a matrix AA if there exists a finite sequence of elementary matrices E1,E2,…,EkE_1, E_2, \dots, E_k such that:     \n    B = E_k E_{k-1} \cdots E_1 A\n    
    • Conceptually, this states that BB is row equivalent to AA if and only if BB can be obtained from AA by applying a finite sequence of elementary row operations.

  • Equivalence Properties Theorem:

    • Symmetry: If BB is row equivalent to AA, then AA is row equivalent to BB.
    • Proof: Let B=EkEk−1⋯E1AB = E_k E_{k-1} \cdots E_1 A. Taking the inverse of the matrix product:       \n      (E_k E_{k-1} \cdots E_1)^{-1} B = E_1^{-1} \cdots E_{k-1}^{-1} E_k^{-1} B = A\n             Since each Ei−1E_i^{-1} is an elementary matrix, AA is obtained by multiplying BB by a finite sequence of elementary matrices.
    • Transitivity: If BB is row equivalent to AA, and AA is row equivalent to CC, then BB is row equivalent to CC.
    • Proof: Let B=EkEk−1⋯E1AB = E_k E_{k-1} \cdots E_1 A and A=Ek+nEk+n−1⋯Ek+1CA = E_{k+n} E_{k+n-1} \cdots E_{k+1} C. Direct substitution yields:       \n      B = E_k E_{k-1} \cdots E_1 E_{k+n} E_{k+n-1} \cdots E_{k+1} C\n             Because this is a finite sequence of elementary matrices, BB is row equivalent to CC.
    • Consequently, AA and BB are called equivalent matrices whenever such a finite sequence of elementary matrices exists connecting them.

Equivalent Conditions for Nonsingularity

  • Main Equivalence Theorem:

    • Let AA be an n×nn \times n square matrix. The following three statements are logically equivalent:
    • (a) AA is nonsingular (invertible).
    • (b) The homogeneous linear system Ax=0Ax = 0 has only the trivial solution 00.
    • (c) AA is row equivalent to the identity matrix II, meaning there exists a finite sequence of elementary matrices E1,E2,…,EkE_1, E_2, \dots, E_k such that:       \n      E_k E_{k-1} \cdots E_1 A = I\n      

  • Proof of Equivalence ((a)  ⟹  (b)  ⟹  (c)  ⟹  (a)(a) \implies (b) \implies (c) \implies (a)):

    • Proof of (a)  ⟹  (b)(a) \implies (b): Assume AA is nonsingular. Let xˉ\bar{x} be any solution to Ax=0Ax = 0. By multiplying both sides by A−1A^{-1}:     \n    \bar{x} = I\bar{x} = (A^{-1}A)\bar{x} = A^{-1}(A\bar{x}) = A^{-1}0 = 0\n         Therefore, xˉ=0\bar{x} = 0 is the only solution.
    • Proof of (b)  ⟹  (c)(b) \implies (c): Assume Ax=0Ax = 0 has only the trivial solution 00. By row reduction, the system is transformed into Ux=0Ux = 0, where UU is in row echelon form. Matrix UU cannot have a zero row; otherwise, free variables would arise, yielding nontrivial solutions to Ux=0Ux = 0 and thus Ax=0Ax = 0. Therefore, UU must be in strict triangular form with diagonal entries all equal to 11. Further reduction eliminates all entries above the diagonal, yielding the reduced row echelon form of AA as the identity matrix II.
    • Proof of (c)  ⟹  (a)(c) \implies (a): Assume AA is row equivalent to II. There exists a sequence of elementary matrices such that EkEk−1⋯E1A=IE_k E_{k-1} \cdots E_1 A = I. Since each elementary matrix EiE_i is invertible, the product (EkEk−1⋯E1)(E_k E_{k-1} \cdots E_1) is also invertible. Multiplying on the left by the product inverse:     \n    (E_k E_{k-1} \cdots E_1)^{-1} E_k E_{k-1} \cdots E_1 A = (E_k E_{k-1} \cdots E_1)^{-1} I\n         \n    A = E_1^{-1} \cdots E_{k-1}^{-1} E_k^{-1}\n         Because AA is the product of invertible elementary matrices, AA is nonsingular, and its inverse is given by:     \n    A^{-1} = E_k E_{k-1} \cdots E_1\n    

Solvability of Linear Systems and Invertibility

  • Corollary on System Solvability:

    • The linear system Ax=bAx = b of nn equations in nn unknowns has a unique solution if and only if AA is nonsingular.

  • Proof of the Corollary:

    • Forward Direction (  ⟹  \implies): Assume AA is nonsingular. Let xˉ\bar{x} be a solution satisfying Axˉ=bA\bar{x} = b. Multiplying both sides by A−1A^{-1}:     \n    \bar{x} = A^{-1}b\n         Because matrix multiplication is deterministic and A−1A^{-1} is unique, xˉ=A−1b\bar{x} = A^{-1}b is the unique solution.
    • Reverse Direction (⟸\Longleftarrow): Assume Ax=bAx = b has a unique solution xˉ\bar{x}. By way of contradiction, assume AA is singular. If AA is singular, the homogeneous system Ax=0Ax = 0 possesses a nontrivial solution z≠0z \neq 0. Defining a vector y=xˉ+zy = \bar{x} + z:     \n    Ay = A(\bar{x} + z) = A\bar{x} + Az = b + 0 = b\n         This shows that yy is a second, distinct solution to Ax=bAx = b (y≠xˉy \neq \bar{x} because z≠0z \neq 0), contradicting the uniqueness of xˉ\bar{x}. Thus, AA must be nonsingular.

Matrix Inversion Algorithm via Elementary Row Operations

  • Theoretical Foundation of the Inversion Algorithm:
    • If an n×nn \times n matrix AA is nonsingular, it is row equivalent to II, meaning:     \n    E_k E_{k-1} \cdots E_1 A = I\n    
    • Post-multiplying both sides by A−1A^{-1} gives:     \n    E_k E_{k-1} \cdots E_1 A A^{-1} = I A^{-1}\n         \n    E_k E_{k-1} \cdots E_1 I = A^{-1}\n    
    • This establishes that the exact sequence of elementary row operations that reduces AA to the identity matrix II will simultaneously transform II into A−1A^{-1}.
    • Implementation: Form the augmented matrix (A∣I)(A \mid I). Apply row operations until the left block becomes the identity matrix:     \n    (A \mid I) \xrightarrow{\text{Row Operations}} (I \mid A^{-1})\n    

Worked Example: Matrix Inversion

  • Problem Statement:

    • Compute A−1A^{-1} for the matrix:     \n    A = \begin{bmatrix} 1 & 0 & 1 \\ -1 & 1 & 1 \\ -1 & -2 & -3 \end{bmatrix}\n    

  • Step-by-Step Row Reduction of Augmented Matrix (A∣I)(A \mid I).

  • Initial Augmented Matrix:   \n  \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ -1 & 1 & 1 & 0 & 1 & 0 \\ -1 & -2 & -3 & 0 & 0 & 1 \end{bmatrix}\n  

  • Elimination below Pivot in Column 1:

    • Apply row operations R1+R2R_1 + R_2 and R1+R3R_1 + R_3:     \n    \xrightarrow{\begin{matrix} R_1 + R_2 \\ R_1 + R_3 \end{matrix}} \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 \\ 0 & -2 & -2 & 1 & 0 & 1 \end{bmatrix}\n    

  • Elimination below Pivot in Column 2:

    • Apply row operation 2R2+R32R_2 + R_3:     \n    \xrightarrow{2R_2 + R_3} \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 2 & 3 & 2 & 1 \end{bmatrix}\n    

  • Normalization of Pivot in Column 3:

    • Apply row operation 12R3\frac{1}{2} R_3:     \n    \xrightarrow{\frac{1}{2} R_3} \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 1 & \frac{3}{2} & 1 & \frac{1}{2} \end{bmatrix}\n    

  • Back-Substitution / Upward Elimination using Row 3:

    • Apply row operations −2R3+R2-2R_3 + R_2 and −R3+R1-R_3 + R_1:
    • For Row 2: [110]−2[32112]=[−2−1−1]\begin{bmatrix} 1 & 1 & 0 \end{bmatrix} - 2 \begin{bmatrix} \frac{3}{2} & 1 & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} -2 & -1 & -1 \end{bmatrix}
    • For Row 1: [100]−1[32112]=[−12−1−12]\begin{bmatrix} 1 & 0 & 0 \end{bmatrix} - 1 \begin{bmatrix} \frac{3}{2} & 1 & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} -\frac{1}{2} & -1 & -\frac{1}{2} \end{bmatrix}
    • Resulting augmented matrix:     \n    \xrightarrow{\begin{matrix} -2R_3 + R_2 \\ -R_3 + R_1 \end{matrix}} \begin{bmatrix} 1 & 0 & 0 & -\frac{1}{2} & -1 & -\frac{1}{2} \\ 0 & 1 & 0 & -2 & -1 & -1 \\ 0 & 0 & 1 & \frac{3}{2} & 1 & \frac{1}{2} \end{bmatrix} = (I \mid A^{-1})\n    

  • Inverse Matrix Result:   \n  A^{-1} = \begin{bmatrix} -\frac{1}{2} & -1 & -\frac{1}{2} \\ -2 & -1 & -1 \\ \frac{3}{2} & 1 & \frac{1}{2} \end{bmatrix}\n  

    • Inversion Verification: Direct multiplication confirms AA−1=A−1A=IAA^{-1} = A^{-1}A = I.

Special Matrix Classes: Diagonal, Triangular, and Strict Triangular Forms

  • Upper Triangular Matrix:

    • An n×nn \times n matrix A=(aij)A = (a_{ij}) is upper triangular if aij=0a_{ij} = 0 whenever i>ji > j.
    • Example:     \n    \begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & -5 \\ 0 & 0 & 4 \end{bmatrix}\n    

  • Lower Triangular Matrix:

    • An n×nn \times n matrix A=(aij)A = (a_{ij}) is lower triangular if aij=0a_{ij} = 0 whenever i<ji < j.
    • Example:     \n    \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 7 & 8 & 4 \end{bmatrix}\n    

  • Triangular Matrix Criteria:

    • A matrix is called triangular if it is either upper triangular or lower triangular.
    • Note that triangular matrices may contain 00 entries along the main diagonal.

  • Strict Triangular Form:

    • A linear system Ax=bAx = b is in strict triangular form if the coefficient matrix AA is upper triangular with all diagonal entries being strictly nonzero.

  • Diagonal Matrix:

    • An n×nn \times n matrix A=(aij)A = (a_{ij}) is diagonal if aij=0a_{ij} = 0 whenever i≠ji \neq j.
    • Examples:     \n    \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}, \quad \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 4 \end{bmatrix}\n    

  • Unit Lower Triangular Matrix:

    • A lower triangular matrix whose diagonal entries are all identically equal to 11 (aii=1a_{ii} = 1 for all ii).
    • Example:     \n    \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{bmatrix}\n    

The LU Factorization of Matrices

  • Definition of LU Factorization:
    • If an n×nn \times n matrix AA can be reduced to a strict upper triangular matrix UU (an upper triangular matrix with nonzero diagonal entries) using exclusively Type III elementary row operations, then AA can be uniquely factored as:     \n    A = LU\n    
    • In this factorization:
    • LL is a unit lower triangular matrix.
    • UU is a strict upper triangular matrix.

Algorithmic Procedure for LU Factorization

  • Step 1: Forward Elimination using Type III Operations:

    • Apply only row operations of Type III of the form (−α)Ri+Rj(-\alpha)R_i + R_j (where i<ji < j) to reduce matrix AA into a strict upper triangular matrix UU.

  • Step 2: Construction of the Multiplier Matrix LL:

    • The matrix L=(lji)L = (l_{ji}) is a unit lower triangular matrix (lkk=1l_{kk} = 1, ljk=0l_{jk} = 0 for k>jk > j).
    • The lower triangular entries ljil_{ji} (for i<ji < j) are determined directly by the scalars used in Step 1:     \n    l_{ji} = \alpha\n         where α\alpha is the scalar taken from the operation (−α)Ri+Rj(-\alpha)R_i + R_j utilized to eliminate the entry at position (j,i)(j, i).
    • For example, if the operation used to clear the entry in row 22 using row 11 is (−α)R1+R2(-\alpha)R_1 + R_2, then l21=αl_{21} = \alpha.

Worked Example and Algebraic Derivation of LU Factorization

  • Problem Statement:

    • Compute the LU factorization of:     \n    A = \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix}\n    

  • Forward Elimination to form UU:

    • Step 1a: Eliminate entries in column 1 below the pivot using row 1:
    • To eliminate a21=3a_{21} = 3: use −3R1+R2-3R_1 + R_2.
    • To eliminate a31=−2a_{31} = -2: use 2R1+R32R_1 + R_3.     \n    \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix} \xrightarrow{\begin{matrix} -3R_1 + R_2 \\ 2R_1 + R_3 \end{matrix}} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{bmatrix}\n    
    • Step 1b: Eliminate entries in column 2 below the pivot using row 2:
    • To eliminate entry 44 in row 3: use −2R2+R3-2R_2 + R_3.     \n    \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{bmatrix} \xrightarrow{-2R_2 + R_3} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix} = U\n    

  • Construction of Matrix LL via Multipliers:

    • Multipliers extracted from (−α)Ri+Rj(-\alpha)R_i + R_j:
    • From −3R1+R2=(−(3))R1+R2  ⟹  l21=3-3R_1 + R_2 = (-(3))R_1 + R_2 \implies l_{21} = 3.
    • From 2R1+R3=(−(−2))R1+R3  ⟹  l31=−22R_1 + R_3 = (-(-2))R_1 + R_3 \implies l_{31} = -2.
    • From −2R2+R3=(−(2))R2+R3  ⟹  l32=2-2R_2 + R_3 = (-(2))R_2 + R_3 \implies l_{32} = 2.
    • Assembling the unit lower triangular matrix LL:     \n    L = \begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}\n    
    • Verification of factorization product:     \n    A = \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix} = LU\n    

  • Algebraic Derivation via Elementary Matrices:

    • The row reduction operations in order were:
    1. −3R1+R2-3R_1 + R_2
    2. 2R1+R32R_1 + R_3
    3. −2R2+R3-2R_2 + R_3
    • The corresponding elementary matrices generated from II are:     \n    E_1 = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad E_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix}, \quad E_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}\n    
    • The reduction to strict upper triangular form is represented by:     \n    E_3 E_2 E_1 A = U\n    
    • Multiplying both sides on the left by (E3E2E1)−1(E_3 E_2 E_1)^{-1}:     \n    (E_3 E_2 E_1)^{-1} (E_3 E_2 E_1) A = (E_3 E_2 E_1)^{-1} U\n         \n    I A = E_1^{-1} E_2^{-1} E_3^{-1} U\n         \n    A = (E_1^{-1} E_2^{-1} E_3^{-1}) U = L U\n    
    • Inverting each Type III elementary matrix:     \n    E_1^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad E_2^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix}, \quad E_3^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}\n    
    • Direct matrix multiplication confirms that the inverse product equals LL without cross-term interference:     \n    E_1^{-1} E_2^{-1} E_3^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}\n         \n    = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} = L\n