Wir zeigen, dass nach dem $k$--ten Eliminationsschritt gilt
$\max_{i\leqslant k+1,j}|a_{ij}^{(k)}|\leqslant (k+1) \max_{i,j}|a_{i,j}|$;
$a_{ij}^{(k)}=a_{ij}$, $i>k+1$; $a^{(k)}_{i+1,i}=0$, $i=1,\dots,k$.

F\"ur $k=0$ ist nichts zu zeigen.
Bei der Elimination machen wir eine wichtige Beobachtung: Die 
Hessenbergstruktur wird durch die Pivotisierung nicht zerst\"ort, da maximal
die $k$--te und $(k+1)$--te Zeile getauscht werden. Beide Zeilen haben 
aber in den
Spalten $1,\dots,k-1$ nur Nullen. 
Wir haben also ein $A^{(k)}$ folgender Struktur
\[
A^{(k)}=
\left(
 \begin{array}{ccc|cccc}
  a^{(k)}_{11}&\cdots&a^{(k)}_{1k}&a^{(k)}_{1,k+1}  &\cdots&\cdots   &a^{(k)}_{1n}\\
       0      &\ddots&\vdots      & \vdots          &      &         &\vdots \\
              &\ddots&a^{(k)}_{kk}&a^{(k)}_{k,k+1}  &\cdots&\cdots   &a^{(k)}_{kn}\\ \hline
              &      &0           &a^{(k)}_{k+1,k+1}&\cdots&\cdots   &a^{(k)}_{k+1,n}\\ 
              &      & 0          &a_{k+2,k+1}      &\cdots&\cdots   &a_{k+2,n}\\ \hline
              &      &            &                 &\ddots&         &\vdots \\ 
              &      &            &                 &      &a_{n,n-1}&a_{nn}
 \end{array}
\right)
\]
Wir haben jetzt im $(k+1)$ Eliminationsschritt ggf. die $(k+1)$--te mit der
$(k+2)$--ten Zeile zu vertauschen und bekommen $a^{(k+1)}_{k+2,k+1}=0$,

\[
a^{(k+1)}_{k+1,j}=\left\{ \begin{array}{cl}
                            a^{(k)}_{k+1,j} & \mbox{ohne Vertauschung}\\
                                  a_{k+2,j} & \mbox{mit Vertauschung}
                           \end{array}\right., \; j\geqslant k+1
\]
sowie
\[
a^{(k+1)}_{k+2,j}=\left\{ \begin{array}{cl}
                            a_{k+2,j}-ta^{(k)}_{k+1,j} & \mbox{ohne Vertauschung}\\
                            a^{(k)}_{k+1,j}-ta_{k+2,j} & \mbox{mit Vertauschung}
                           \end{array}\right., \; j> k+1
\]
Dabei ist $t$ entweder $a^{(k)}_{k+1,k+1}/a_{k+2,k+1}$ oder der Kehrwert.
In jedem Fall aber ist $|t|\leqslant 1$.
Die Zeilen $1,\dots,k,k+3,\dots,n$ bleiben unber\"uhrt.

F\"ur die neue $(k+1)$--te Zeile
k\"onnen wir die alte Absch\"atzung f\"ur Zeile $k+1$ \"ubernehmen.
F\"ur die neue $(k+2)$--te Zeile bekommen wir
\[
|a^{(k+1)}_{k+2,j}|\leqslant\left\{ \begin{array}{c}
                            |a_{k+2,j}|+|t|\cdot |a^{(k)}_{k+1,j}|\\
                            |a^{(k)}_{k+1,j}| + |t|\cdot |a_{k+2,j}|
                           \end{array}\right\}
\leqslant (k+1) \max_{i,j}|a_{i,j}| + \max_{i,j}|a_{i,j}|.
\]
Daraus folgt die Behauptung.
F\"ur den Wachstumsfaktor $\rho$ bedeutet dies, dass
\[
\rho=\max_{i,j,k}\frac{|a_{ij}^{(k)}|}{\|A\|_{\infty}}
\leqslant n \max_{i,j}\frac{|a_{ij}|}{\|A\|_{\infty}}
\leqslant n
\]
ist.
