Flame Logo

Bottom of Form

Top of Form

Bottom of Form

Top of Form

Bottom of Form

Top of Form

Bottom of Form

Theorem: Partition $ A \in \Smxn $by rows and columns:

o    \[
A = 
\left( \begin{array}{c}
\hat{a}_0^T \\ \hline
\hat{a}_1^T \\ \hline
\vdots \\ \hline
\hat{a}_{m-1}^T 
\end{array}
\right)
=
\left( \begin{array}{c | c | c | c }
a_0 & a_1 & \cdots & a_{n-1}
\end{array}
\right).
\]

Then

o    \begin{eqnarray}
\| A \|_1 &=& \max_{0\leq j<n} \| a_j \|_1 =
\max_{0 \leq j < n} \sum_{i=0}^{m-1} | \alpha_{ij} |
,  \\
\| A \|_\infty & = & \max_{0\leq i<m} \| \hat{a}_i \|_1 =
\max_{0 \leq i < m} \sum_{j=0}^{n-1} | \alpha_{ij} |
, \mbox{ and } \\
\| A^T \|_1 &=& \| A \|_\infty. 
\end{eqnarray}

See proof


Proof: We will prove (\ref{eqn:nrm1inf1}), leaving the other results as an exercise.

The proof strategy will be to show that

\[
\begin{array}{l  c  l  @{\hspace{0.25in}} p{2in} }
\| A \|_1 &=& \max_{\| x \|_1 = 1} \| A x \|_1  & \mbox{(definition of matrix 1-norm)} \\
& = &
\max_{\| x \|_1 = 1} \left\| \left( \begin{array}{ c | c | c }
a_0 & \cdots & a_{n-1} 
\end{array}
\right)
\left(
\begin{array}{c}
\chi_0 \\ \hline
\vdots \\ \hline
\chi_{n-1} 
\end{array}
\right) \right\|_1
& \\
& = & 
\max_{\| x \|_1 = 1} \left\| \sum_{p=0}^{n-1} 
\chi_p a_p  \right\|_1 & \\
& \leq & 
\max_{\| x \|_1 = 1} \sum_{p=0}^{n-1} 
\| \chi_p a_p  \|_1 & \mbox{(triangle inequality)} \\
& = & 
\max_{\| x \|_1 = 1} \sum_{p=0}^{n-1} 
( | \chi_p | \| a_p  \|_1 ) & \mbox{(positive definite property of vectors)} \\
& \leq & 
\max_{\| x \|_1 = 1} \sum_{p=0}^{n-1} 
( | \chi_p | \max_{0 \leq j < n} \| a_j  \|_1 ) & \\
& = & 
\max_{0 \leq j < n} \| a_j  \|_1
\max_{\| x \|_1 = 1} 
\sum_{p=0}^{n-1} 
| \chi_p |  & 
\mbox{(since [[latex($ \max_{0 \leq j < n } \| a_j \|_1 $)]] is independent 
[[latex($ x $)]])} \\
& = &\max_{0 \leq j < n} \| a_j  \|_1 & \mbox{(since [[latex($ \| x \| = 1 $)]])}.
\end{array}
\]

This shows that $\| A \|_1 \leq \max_{0\leq j<n} \| a_j \|_1 $.

Now, let $ k $equal the index such that $ \| a_k \|_1 = \max_{0 \leq j < n} \| a_j \|_1 $and let $ z = e_k $equal the $ k $th unit basis vector. Recall that $ a_k = A e_k $. Then

This shows that $\| A \|_1 \geq \max_{0\leq j<n} \| a_j \|_1 $.

LinearAlgebraWiki: Norm/Theorem3/proof (last edited 2008-01-28 04:52:46 by MarthaGanser)