# The Algorithm for Gaussian Elimination with Partial Pivoting

We will now present the algorithm for Gaussian elimination with using the partial pivoting technique assuming that a unique solution to the system $Ax = b$ exists.

For input, obtain an $n \times n$ matrix $A$ and an $n \times 1$ column matrix $b$. Check to see if the matrices $A$ and $b$ are of the appropriate size. Let $\tilde{A} = (A | b)$ be the $n \times n +1$ matrix obtained by attaching the column $b$ to the right side of $A$.

For each $k = 1, 2, ..., n$:

**Step 1:** Find the row index $P_k ≥ k$ for which $\mid a_{p_k, k} \mid = \max_{k≤i≤n} \mid a_{i, k} \mid$. This finds the index of the largest (when absolute valued) entry in each row.

**Step 2:** If $a_{p_k, k} = 0$, then stop. An entire column consists of zeros which implies that the matrix $A$ is singular and has no solution. If $a_{p_k, k} \neq 0$, then interchange row $k$ and row $p_k$. This brings the largest (when absolute valued) entry to the main diagonal each time.

**Step 3:** For $i = k+1, k+2, ..., n$, let $a_{i,k} = a_{i, k} \div a_{k, k}$, and for $j = k+1, k+2, ..., n+1$, let $a_{i, j} = a_{i, j} - a_{i, k} a_{k, j}$.

**Step 4:** For $i = n, n-1, ..., 1$, we have that the solution is given by