Linear Algebra 2.4 - 2.5 Partitioned Matrix & Factorization

Section 2.4 Partitioned Matrix

• Addition and Scalar Multiplication

  If matrices $A,B$ are the same size and are partitioned in exactly the same way, then $A+B$ and $cA$ holds.

• Multiplication

  the partitions of $A$ and $B$ are conformable for block multiplication.

  

Theorem : Column-Row Expansion of AB

Section 2.5 Matrix Factorization

A factorization of a matrix $A$ is an equation that expresses $A$ as a product of two or more matrices.

The LU factorization :

$A$ is an $m\times n$ matrix, where $L$ is an $m\times m$ lower triangular matrix with $1$’s on the diagonal and $U$ is an $m\times n$ echelon form of $A$. (Assume $A$ can be row reduced to echelon form without row interchanges)

Why it is useful?

If $A=LU$, then $Ax=b$ can be written in $L(Ux)=b$, let $y=Ux$, it is equals to calculate:

$$Ly=b\\ Ux=y$$

This two equations are easy to solve as $L$ and $U$ are triangular.

An LU Factorization Algorithm

Suppose $A$ can be reduced to an echelon form $U$ using only row replacements that add a multiple of one row to another row below it. In this case, there exist unit lower triangular elementary matrices $E_1,\dots,E_p$ such that:

$$E_p\cdots E_1A=U$$

Then:

$$A=(E_p\cdots E_1)^{-1}U=LU$$

where

$$L=(E_p\cdots E_1)^{-1}$$

It can be shown that products and inverse of unit lower triangular matrices are also unit lower triangular. Thus $L$ is unit lower triangular.

Note that the row operations in equation above, which reduce $A$ to $U$, also reduce the $L$ to $I$, because $E_p\cdots E_1L=(E_p\cdots E_1)(E_p\cdots E_1)^{-1}=I$. This observation is the key to constructing $L$.

Conclusion:

1. Reduce $A$ to an echelon form $U$ by a sequence of row replacement operations, if possible.
2. Place entries in $L$ such that the same sequence of row operations reduces $L$ to $I$.