Ordinary Reducer Factorization

Why

In ordinary reduction, we obtain a sequence of row reducers.

Factorization of $A$ from a sequence of reducers

Let $(A \in \R ^{m \times m}, b \in \R ^{m})$ be an ordinarily reducible linear system. The ordinary reducer sequence is a sequence of reducer matrices $L_{1}, \dots L_{m-1}$ with $A_1 = L_1A$ and $A_i = L_iA_{i-1}$ for $2 \leq i \leq m-1$. In other words, $U \in \R ^{m \times m}$ defined by

\begin{equation} U = L_{m-1} \cdots L_2 L_1 A \label{equation:ordinaryreducerfactorization:main} \end{equation}

is the ordinary row reduction of $A$. $U$ is upper triangular.

If $L_{m-1}\cdot s L_2 L_1$ in Equation~\eqref{equation:ordinaryreducerfactorization:main} is invertible, then we have

\[ A = \inv{(L_{m-1}\cdot s L_2 L_1)}U, \]

which is a factorization of $A$. Each $L_i$ is invertible, so

\[ \inv{(L_{m-1} \cdots L_2 L_1)} = \inv{L}_1\inv{L}_2\cdots\inv{L}_{m-1}. \]

So we are interested in the inverse of $L_i$ for $i \leq m-1$. Recall that if $x_1$ is the first column of $A$, and $x_2$ is the second column of $L_1A$ and $x_k$ is the $k$th column of $L_{k-1}\cdot s L_{1}A$ for $k = 2, \dots , m-1$, then

\[ L_k = \barray{ 1 & & & & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & -\ell _{k+1,k} & 1 & &\\ & & \vdots & & \ddots & & \\ & & -\ell _{mk} & & & 1 } \]

where $\ell _{jk} = x_{jk}/x_{kk}$ for $k < j \leq m$.

Properties

The two important properties of the $L_i$ is that they have simple inverses and a simple product. Define

\[ \ell _k = (0,\cdot s, 0,\ell _{k+1,k}, \cdot s, \ell _{m,k}) \]

so that $L_k = L_k - \ell _k\transpose{e}_k$ where $(e_k)_i$ is 1 if $k = i$ and 0 otherwise.

$\inv{L}_i$ is $L_i$ with the subdiagonal entries negated.

From the sparsity pattern of $\ell _k$, we have $e_k^\tp \ell _k = 0$. So

\[ (I - \ell _k e_k^\tp)(I + \ell _k e_k^\tp) = I - \ell _ke^\tp_k\ell _ke^\tp_k = I. \]

$\inv{L}_{k}\inv{L}_{k+1}$ is the unit lower-triangular matrix with the entries of both $\inv{L}_k$ and $\inv{L}_{k+1}$ in their usual places.

From the sparsity pattern of $\ell _{k+1}$ we have $e_k^\tp \ell _{k+1} = 0$ so that

\[ \inv{L}_k \inv{L}_{k+1} = (I + \ell _ke^\tp_{k})(I + \ell _{k+1}e^\tp_{k+1}) = I + \ell _ke^*_k + \ell _{k+1}e^*_{k+1}. \]

Combining these two results, we deduce that

\[ \inv{L}_1\inv{L}_2\cdots\inv{L}_{m-1} = \barray{ 1 & & & & \\ \ell _{21} & 1 &&& \\ \ell _{31} & \ell _{32} & 1 & & \\ \vdots & \vdots & \ddots &\ddots & \\ \ell _{m1} & \ell _{m2} & \cdot s & \ell _{m,m-1} & 1 \\ } \]

If we define $L = L_{1}^{-1} \cdots L_{m-1}^{-1}$ we obtain $A = LU$. In other words, we have a factorization (the ordinary reducer factorization) of $A$ in terms of two matrices. The first, $L$ is unit lower triangular. The second, $U$, is upper triangular.