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

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.

• I realise this became more than just a hint. Nonetheless, there are details to fill in regarding the elements $b_j$ appearing in $U$, and why $|l_j| \leq 1$. Anyway, hope it will help. – ekkilop Aug 24 '16 at 7:47
• One question - $A$ is band matrix but $PA$ may look different. If we have fragment like this: \begin{pmatrix} 1 & 1 & & \\ 1 & 2 & 1 & \\ & 1 & 1 & \ddots \\ & & \ddots & \ddots \end{pmatrix} then it will be rearranged to \begin{pmatrix} 1 & 2 & 1 & \\ 1 & 1 & & \\ & 1 & 1 & \ddots \\ & & \ddots & \ddots \end{pmatrix} which is no longer band matrix. So why $L$,$U$ still look like in your answer? – dyrAnd Aug 24 '16 at 9:55
• Pardon me, that was a misunderstanding on my part. I'll update my answer shortly. – ekkilop Aug 24 '16 at 11:05
• Ok, I am too stupid to understand it. Let's take example (numbers from Octave): $$\begin{pmatrix} & 1 & & \\ 1 & & & \\ & & & 1 \\ & & 1 & \end{pmatrix} \cdot \begin{pmatrix} 1 & 9 & 0 & 0\\ 7 & 4 & 3& 0\\ 0 & 6 & 5 & 9 \\ 0 & 0 & 7 & 3 \end{pmatrix} = \begin{pmatrix} 1 & & & \\ 0.14286 & 1 & & \\ 0 & 0 & 1 & \\0 & 0.71186 & 0.75787 & 1 \end{pmatrix} \cdot \begin{pmatrix} 7 & 4 & 3 & 0\\ & 8.42857 & \mathbf{-0.42857} & 0\\ & & 7 & 3\\ & & & 6.72639 \end{pmatrix}$$ How can we assure that -0.42.. not become something larger in different example?PA super-d is 4 0 3, sub-d is 1 0 5 – dyrAnd Aug 25 '16 at 14:16
• It's not you being stupid; it's me being unclear (and mistaken on a few points). I'll change my answer and leave a few pieces for you to fill in. – ekkilop Aug 26 '16 at 13:27