Matrix Norms | Logan Nielsen

Norms map mathematical objects to scalars. These scalars represent the size of the transformation. Induced norms are often of interest because they are the most natural way to discuss the size of a transformation.

First we’ll show the $l_1$ norm of a matrix is is the largest absolute column sum.

\begin{align*} \sup_{\pmb x} \frac{\lVert A \pmb x \rVert_1}{\lVert \pmb x \rVert_1} \end{align*}

Upper bound

Write $A = \begin{bmatrix} \pmb a_1 & \dots & \pmb a _n\end{bmatrix}$

\begin{align*} \lVert A \pmb x \rVert_1 &= \left\lVert \begin{bmatrix} \pmb a_1 & \dots & \pmb a _n\end{bmatrix} \begin{bmatrix}x_1 \\ \vdots \\ x_n \end{bmatrix} \right\rVert_1 \\ &= \left\lVert \sum_{j=1}^n \pmb a_j x_j \right\rVert_1 \\ &\leq \sum_{j=1}^n \left\lVert \pmb a_j x_j \right\rVert_1 && \text{Triangle Inequality}\\ &= \sum_{j=1}^n \left\lVert \pmb a_j \right\rVert_1 | x_j| \\ &\leq \sum_{j=1}^n \max_J (\lVert \pmb a_J \rVert_1) | x_j| \\ &= \max_J (\lVert \pmb a_J \rVert_1) \sum_{i=1}^n | x_j| \\ &= \max_J (\lVert \pmb a_J \rVert_1) \rVert \pmb x \lVert_1 \\ \end{align*}

Therefore

\begin{align*} \sup_{\pmb x} \frac{\lVert A \pmb x \rVert_1}{\lVert \pmb x \rVert_1} \leq \frac{ \max_J (\lVert \pmb a_J \rVert_1) \rVert \pmb x \lVert_1}{\lVert \pmb x \rVert_1} &= \max_J (\lVert \pmb a_J \rVert_1) \end{align*}

Achieving the Upper Bound

If $J$ is the value of $j$ that satisfies $\max_J (\lVert \pmb a_J \rVert_1)$ then let $\pmb x = \pmb e_J$ . Since $\pmb e_J$ reaches this upper bound and $\rVert\pmb a_J\rVert_1$ is the maximum column sum of $A$ , this is the definition of the $l_1$ -norm of a matrix.