Algorithm (LU Factorization with Partial Pivoting)
Initialize $U = A, L = I, P = I $
FOR $k = 1 : m − 1$
$⠀ ⠀ ⠀ $Select $i ≥ k$ to maximize $|U(i,k)|$
$⠀ ⠀ ⠀ $$U ( k , k : m ) ←→ U ( i , k : m )$
$⠀ ⠀ ⠀ $$L(k, 1 : k − 1) ←→ L(i, 1 : k − 1)$
$⠀ ⠀ ⠀ $$P(k,:) ←→ P(i,:)$
$⠀ ⠀ ⠀ $FOR $ j = k + 1 : m$
$⠀ ⠀ ⠀ ⠀ ⠀ ⠀ $$L(j,k) = \frac{U(j,k)}{U(k,k)}$
$⠀ ⠀ ⠀ $END
END
I am confused about what happens when the first FOR loop runs, i.e. k=1 and the maximum value of $|U(i,1)|$ is at $|U(1,1)|$ so i=1.
In that case, we have that $L(1, 1 : 0) ←→ L(1, 1 : 0)$ however the index 1:0 doesn't make sense, so does that mean no rows are interchanged?
I found this algorithm on page 66 of http://www.math.iit.edu/~fass/477577_Chapter_7.pdf
Best Answer
The index set $1:0$ makes perfect sense, it is simply the empty set. Hence, no elements are moved, which is exactly what is required here. We only swap rows, when the swap gives us a pivot which is strictly larger in absolute value than the initial candidate.