$PA = LU$ descomposition. Prove that $\max_{1\leq i,j\leq n}|u_{i,j}| \leq 2\max_{1\leq i,j\leq n}|a_{i,j}|$ I am stuck on this problem:

Let $A = (a_{ij}) \in \mathbb{C}^{n\times n}$ be nonsingular matrix.
$a_{i,j} = 0$ for $|i −j| ≥ 2$ so matrix looks like this
  \begin{bmatrix}  a_{11} & a_{12} & 0      & \cdots & \cdots & 0 \\ 
 a_{21} & a_{22} & a_{23} & 0 & \ddots & \vdots \\   0     & a_{32} &
 a_{33} & \ddots & \ddots & \vdots \\  \vdots & 0 & \ddots & \ddots &
 \ddots & 0 \\  \vdots & \ddots & \ddots & \ddots & a_{n-1,n-1} &
 a_{n-1,n} \\  0      & \cdots & \cdots & 0      & a_{n,n-1} & a_{nn}
 \end{bmatrix} We apply the Gaussian elmination with pivoting to the
  matrix $A$. So we have $PA = LU$ where $P$ is permutation matrix. $L$
  is lower triangular matrix and $l_{i,j}\leq1$, $l_{i,i}=1$. $U$ is
  upper triangular matrix. Prove that  $$\max_{1\leq i,j\leq n}|u_{i,j}|
 \leq 2\max_{1\leq i,j\leq n}|a_{i,j}|$$

$P$ matrix do not change $\max$ so $\max(PA) = \max(A)$
Rows of $A$ can be rearranged but we know that they have at most 3 nonzero values (same for columns).
Let choose one column (any) of $U$, $U_k =  \left(\begin{array}{c}
      u_{1,k} \\
      u_{2,k} \\
\vdots  \\
     u_{n,k}
    \end{array}\right)$.
$LU_k$ is column of $PA$ so there are at most 3 nonzero elements. 
Then there is system of equations:
\begin{cases}
u_{1,k} = PA_{1,k}\\
u_{2,k} = PA_{2,k} - u_{1,k}\cdot l_{2,1}\\
\vdots  \\
u_{n,k} = PA_{n,k} - (u_{1,k}\cdot l_{n,1}+ u_{2,k}\cdot l_{n,2} + \dots + u_{n-1,k}\cdot l_{n,n-1} )
\end{cases}
and most of them are zeros.
Please give me a hint or a clue what to do next. Thanks in advance.
 A: As you say, $P$ does not change the magnitude of any elements. Let us for convenience call the elements of the matrices involved
$$
PA = \begin{pmatrix}
a_1 & b_1 & & \\
c_1 & a_2 & b_2 & \\
& c_2 & a_3 & \ddots \\
& & \ddots & \ddots
\end{pmatrix}
=
\begin{pmatrix}
1 & & & \\
l_1 & 1 & & \\
& l_2 & 1 & \\
& & \ddots & \ddots
\end{pmatrix}
\begin{pmatrix}
u_1 & b_1 & & \\
& u_2 & b_2 & \\
& & u_3 & \ddots \\
& & & \ddots
\end{pmatrix}
= LU.
$$
Then, the recursion you have mentioned in your question becomes
\begin{align}
u_1 &= a_1 \\
l_j &= c_j / u_j \\
u_{j+1} &= a_{j+1} - l_j b_j.
\end{align}
Note first that if $\max_{i,j}|u_{i,j}| = |b_k|$, for any $k$, then the statement holds, since $b_k$ is an element of $PA$ (hence of $A$) as well as of $U$. So assume instead that $\max_{i,j}|u_{i,j}| = |u_k|$ for some $k$. Note further that, since pivoting is being used, we have $|l_j| \leq 1$ for all $j$.
Now, if $\max_{i,j}|u_{i,j}| = |u_1|$, then by the recursion above, the statement holds, since $u_1 = a_1$ is an element of $PA$. So assume not. That means $\max_{i,j}|u_{i,j}| = |u_k|$ for some $k \neq 1$. However, for any $j$ we have
$$
|u_{j+1}| = |a_{j+1} - l_j b_j| \leq |a_{j+1}| + |l_j b_j| \leq |a_{j+1}| + |b_j| \leq 2 \max_{i,j} |a_{i,j}|
$$
since both $a_{j+1}$ and $b_j$ are elements of $PA$, hence of $A$.
Update: As was pointed out in a comment, $PA$ must not necessarily be tridiagonal, and so the above argument might be invalid. However, note the following two things:
i) Let the elements of $PA$ be denoted $pa_{i,j}$. Above the main diagonal, the only non-zero elements of $PA$ are of the form $pa_{j-1,j}$ and $pa_{j-2,j}$
ii) $PA$ has at most one non-zero sub-diagonal element in each column. Therefore, $L$ has at most one non-zero sub-diagonal element in each column.
Let the elements of $U$ and $L$ be $u_{i,j}$ and $l_{i,j}$ respectively. The recursion written in the question takes the form
$$
(1) \qquad u_{i,j} = pa_{i,j} - \sum_{k=1}^{i-1} l_{i,k} u_{k,j}.
$$
Now, note that $U$ only has non-zero elements of the form $u_{j,j}$, $u_{j-1,j}$ and $u_{j-2,j}$. Using (1), this, together with $|l_{i,j}| \leq 1$, gives
\begin{align}
u_{j-2,j} &= pa_{j-2,j} \leq 2 \max_{i,j} |pa_{i,j}| \\
u_{j-1,j} &= pa_{j-1,j} - l_{j,j-2} u_{j-2,j} \\
&= pa_{j-1,j} - l_{j,j-2} pa_{j-2,j} \\
& \leq 2 \max_{i,j} |pa_{i,j}|
\end{align}
and finally
\begin{align}
u_{j,j} &= pa_{j,j} - l_{j,j-1} u_{j-1,j} - l_{j,j-2} u_{j-2,j} \\
&= pa_{j,j} - l_{j,j-1} pa_{j-1,j} - l_{j,j-2} pa_{j-2,j} (1 - l_{j,j-1}).
\end{align}
Note:
(i) If $pa_{j-2,j} = 0$ we are done.
(ii) If $l_{j,j-2}=0$ we are done.
(iii) If $l_{j,j-1}=0$ we are done (or $l_{j,j-1}=1$).
Left to consider is therefore $u_{j,j}$ when $pa_{j-2,j} \neq 0$, $l_{j,j-1} \neq 0$ and $l_{j,j-2} \neq 0$. I will leave the details for you to fill in, but you can proceed as follows:
(i) Show that $pa_{j,j} = 0$ in this case. Hint: consider the permutations necessary for this to happen.
(ii) Show that $u_{j-2,j} = pa_{j-2,j}$. Hint: This follows from (1).
(iii) Show that $u_{j-1,j} = pa_{j-1,j}$. Hint: Consider (1) for $u_{j-1,j}$ and use the fact that $L$ only has one non-zero sub-diagonal element.
All in all this should reduce the formula for $u_{j,j}$ to
$$
u_{j,j} = -l_{j,j-1} pa_{j-1,j} - l_{j,j-2} pa_{j-2,j} \leq 2 \max_{i,j} |pa_{i,j}|,
$$
and we are done.
