## Subsection5.3.4Solving A x = y via LU factorization with pivoting

Given nonsingular matrix $A \in \C^{m \times n} \text{,}$ the above discussions have yielded an algorithm for computing permutation matrix $P \text{,}$ unit lower triangular matrix $L$ and upper triangular matrix $U$ such that $P A = L U \text{.}$ We now discuss how these can be used to solve the system of linear equations $A x = y \text{.}$

Starting with

\begin{equation*} A x = b \end{equation*}

where nonsingular matrix $A$ is $n \times n$ (and hence square),

• Overwrite $A$ with its LU factorization, accumulating the pivot information in vector $p \text{:}$

\begin{equation*} [ A, p ] :=\mbox{LUpiv}( A ). \end{equation*}

$A$ now contains $L$ and $U$ and $\widetilde P( p ) A = L U \text{.}$

• We notice that $A x = b$ is equivalent to $\widetilde P( p ) A x = \widetilde b \text{.}$ Thus, we compute $y := \widetilde P( p ) b.$ Usually, $y$ overwrites $b \text{.}$

• Next, we recognize that $\widetilde P( p ) A x = y$ is equivalent to $L \begin{array}[t]{c} \underbrace{(U x)}\\ z \end{array} = y \text{.}$ Hence, we can compute $z$ by solving the unit lower triangular system

\begin{equation*} L z = y \end{equation*}

and next compute $x$ by solving the upper triangular system

\begin{equation*} U x = z. \end{equation*}