Row Reducer Matrices

Why

Can we represent the function associating a linear system with its row reduction by matrix multiplication?

Main observation

The following proposition affirmatively answers the question.

Let $(A \in \R ^{m \times m}, b \in \R ^{m})$ be a linear system with $A_{kk} \neq 0$ and $(C, d)$ the $k$th reduction of $(A, b)$. Then there exists a matrix $L \in \R ^{m \times m}$ so that $C = LA$ and $d = Lb$.

Define $L \in \R ^{m \times m}$ by $L_{st} = 1$ if $s = t$, $-A_{sj}/A_{ij}$ if $k < s \leq m$ and zero otherwise.

For this reason, we call $L$ in the above proposition a row reducer matrix or row reducing matrix or row reducer. The row reducer matrix for the $k$th reduction of $(A, b)$ has the form

\[ L_k = \barray{ 1 & & & & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & A_{ik}/A_{kk} & 1 & &\\ & & \vdots & & \ddots & & \\ & & A_{mk}/A_{kk} & & & 1 } \]

So the following is immediate

Row reducing matrices are unit lower triangular.

Example

For example, the $(1,1)$-reduction of $(A, b)$ in which

\[ A = \barray{ 2 & 1 & 1 & 0 \\ 4 & 3 & 3 & 1 \\ 6 & 7 & 9 & 5 \\ 8 & 7 & 9 & 8 \\ } \text{ and } b = \barray{ 1 \\ 2 \\ 3 \\ 4 \\ }. \]

is the linear system

\[ A' = \barray{ 2 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 3 & 5 & 5 \\ 0 & 4 & 6 & 8 \\ } \text{ and } b' = \barray{ 1 \\ 0 \\ -1 \\ 1\\ }. \]

The row reducer is $L \in R^{4 \times 4}$ defined by

\[ L = \barray{ 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -4 & 0 & 1 & 0 \\ -3 & 0 & 0 & 1 }. \]

One can check that $A' = LA$ and $b' = Lb$, and clearly $L$ is unit lower triangular.