# 4.8 Partial Pivoting

If a partial pivoting strategy is observed (pivoting is restricted to row interchanges), factorization produces matrices L and U which satisfy the following equation.

 $$\mathbf{LU=PA}$$ (54)

P is a permutation matrix that is derived as follows:

• P is initialized to I.

• Each row interchange that occurs during the decomposition of A causes a corresponding row swap in P.

Recalling the definition of a linear system of equations

 $$\mathbf{Ax=b}$$

and premultiplying both sides by P

 $$\mathbf{PAx=Pb}$$

Using Equation 54 to substitute for PA yields

 $$\mathbf{LUx=Pb}$$ (55)

Following the same train of logic used to derive equations Equation 40 and Equation 41 implies that a solution for A can be achieved by the sequential solution of two triangular systems.

 $$\displaystyle\mathbf{y}\displaystyle=\mathbf{Pb}$$ $$\displaystyle\mathbf{Lc}\displaystyle=\mathbf{y}$$ $$\displaystyle\mathbf{Ux}\displaystyle=\mathbf{c}$$ (56)

Observe that the product Pb is computed before forward substitution begins. Computationally, this implies that P can be implemented as a mapping that is applied to b before substitution.