Permutation matrices, partial pivoting, and the pivot-growth factor

Let $n\ge 1$, let $F=\mathbb{R}$ or $\mathbb{C}$, and let $\sigma$ be a permutation of $\{0,\dots ,n-1\}$. The corresponding permutation matrix $P_{\sigma }$ is the matrix whose $i$-th row is the $\sigma (i)$-th row of $I_n$. Thus left multiplication by $P_{\sigma }$ permutes the rows of a matrix.

In Gaussian elimination with partial pivoting, ties are resolved by a fixed deterministic rule. At stage $k$ one inspects the entries in column $k$ from rows $k$ through $n-1$, swaps a row with maximal entry modulus into row $k$, and then eliminates the entries below that pivot.

If $PA=LU$ is the resulting factorisation, its pivot-growth factor is

$\rho (A):=\frac{{\max }_{i,j}\mathrm{\mid }{u}_{ij}\mathrm{\mid }}{{\max }_{i,j}\mathrm{\mid }{a}_{ij}\mathrm{\mid }},$

provided $A\mathrm{\ne }0$; when $A=0$ one declares $\rho (A)=1$. The absolute value or modulus is the one from Absolute value in an ordered field on real entries and its standard complex analogue on complex entries.