2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ekkilop Aug 24 '16 at 7:47
  • $\begingroup$ 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? $\endgroup$ – dyrAnd Aug 24 '16 at 9:55
  • $\begingroup$ Pardon me, that was a misunderstanding on my part. I'll update my answer shortly. $\endgroup$ – ekkilop Aug 24 '16 at 11:05
  • $\begingroup$ 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 $\endgroup$ – dyrAnd Aug 25 '16 at 14:16
  • $\begingroup$ 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. $\endgroup$ – ekkilop Aug 26 '16 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.