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.
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.