Trying to establish a norm inequality Let $A$ be $n $ by $n$ matrix and say $A = LU $ is the LU factorization of $A$. Suppose $|l_{ij}| \leq 1 $, show that $||U||_{\infty} \leq 2^{n-1} ||A||_{\infty} $. Where $\|A\|_{\infty} =\max_{1 \leq i \leq n}\sum_{j=1}^{n}|a_{ij}|.$
TRY:
Suppose $a_i^T$ and $u_i^T$ are the ith rows of $A$ and $U$. If we compute $LU$, we obtain that
$$ u_i^T = a_i^T - \sum_{j=1}^{i-1} l_{ij} u_j^T$$
With this, I tried the following. We know $||U||_{\infty} = \max_{1 \leq k \leq n} | \sum u_k^T | $. Suppose $||U||_{\infty} = | \sum u_k^T | $. Then
$$ | \sum u_k^T | \leq \sum |u_k^T | = \sum \left|a_k^T - \sum_{j=1}^{k-1} l_{kj} u_j^T \right| \leq \sum |a_k^T| + \left| \sum_{j=1}^{k-1} l_{kj}u_j^T \right|$$
by hypthesis, last term is less than
$$ \sum \left( |a_k^T| + \sum_{j=1}^{k-1} |u_j^T| \right) $$
but, then here I am stuck. Perhaps I am on the wrong track on proving this? Any help would be greatly appreciated.
 A: Note that $A=LU$ with $L=I-N$ where $N=[n_{i,j}]$ is nilpotent. Let $J$ be the lower triangular nilpotent Jordan block of dimension $n$ (the false diagonal under the true one is $1,\cdots,1$). Then $U=L^{-1}A=(\sum_{k=0}^{n-1}N^k)A$. It remains to prove that $||\sum_{k=0}^{n-1}N^k||_{\infty}\leq 2^{n-1}$. Recall that, for every $i,j$, $|n_{i,j}|\leq 1$. It is not difficult to see that the maximum of the previous expression is reached when $N=\sum_{k=1}^{n-1}J^k$ (a lower triangular matrix with $ones$ -that is, a "Att" (half of Attila) matrix-).
For this example, to obtain the norm of $\sum_{k=0}^{n-1}N^k$, it suffices to consider the last line of each matrix of the previous sum, and, finally, $||\sum_{k=0}^{n-1}N^k||=\sum_{k=0}^{n-1}||N^k||$. By a recurrence reasoning, we obtain that $||N^k||=\binom{n-1}{k}$ and, therefore, $||\sum_{k=0}^{n-1}N^k||=2^{n-1}$.
A: Let $A$ be an $n\times n$ matrix and suppose that $A$ has an LU factorization $A = LU$. Since $L$ is invertible and $\|\cdot\|_\infty$ is submultiplicative it follows that
$$
\|L^{-1}A\|_\infty = \|U\|_\infty \implies \|U\|_\infty \leq \|L^{-1}\|_\infty\|A\|_\infty
$$
By the process of Gaussian elimination $L^{-1} = L_{n-1}\cdots L_1$, where
$$
L_i = \left[
\begin{array}{cccccc}
1 & & & & & 0\\
  & \ddots & & & &\\
  & & 1 & & &\\
  & & l_{i+1,i} & \ddots & &\\
  & & \vdots & & \ddots &\\
0 & & l_{n,i} & & & 1\\
\end{array}
\right]
$$
for $i = 1,\ldots,n-1$. By properties of the matrices $L_i$ and by the assumption that all elements of $L$ are at most $1$ in magnitude, it follows that $\|L_i\|_\infty \leq 2$. Again using the submultiplicative property of  $\|\cdot\|_\infty$ we have
$$
\|L^{-1}\|_\infty \leq \|L_{n-1}\|_\infty\cdots\|L_1\|_\infty \leq 2^{n-1}
$$
Therefore, we may conclude that $\|U\|_\infty \leq 2^{n-1}\|A\|_\infty$, as desired.
