Matrix Norms

Before we continue on analyzing the error in solving a linear system of equations of the form $Ax = b$, we will need to define what exactly a matrix norm is.

Definition: A Matrix Norm on the set of all $n \times n$, $M_{nn}$, whose entries are real numbers is a function that maps each matrix $A \in M_{nn}$ to a number $\| A \| \in \mathbb{R}$ that has the following properties: a) $\| A \| ≥ 0$ for all $A \in M_{nn}$ and $\| A \| = 0$ if and only if $A$ is the $n \times n$ zero matrix. b) $\| \alpha A \| = \mid \alpha \mid \| A \|$ for all $\alpha \in \mathbb{R}$ and $A \in M_{nn}$. c) $\| A + B \| ≤ \| A \| + \| B \|$ for all $A, B \in M_{nn}$. d) $\| AB \| ≤ \| A \| \| B \|$ for all $A, B \in M_{nn}$.

There are many different matrix norms that can be defined on $M_{nn}$. The following norms will be of most importance to us.

(1)

\begin{align} \quad \| A \|_1 = \max_{1≤j≤n} \sum_{i=1}^{n} \mid a_{ij} \mid = \max \left \{ \sum_{i=1}^{n} \mid a_{i1} \mid , \sum_{i=1}^{n} \mid a_{i2} \mid, ..., \sum_{i=1}^{n} \mid a_{n1} \mid \right \} \end{align}

Note that $\| A \|_{1}$ is equal to the maximum of the sum of the absolute values of the entries for the columns of $A$.

(2)

\begin{align} \quad \| A \|_{\infty} = \max_{1≤i≤n} \sum_{j=1}^{n} \mid a_{ij} \mid = \max \left \{ \sum_{j=1}^{n} \mid a_{1j} \mid , \sum_{j=1}^{n} \mid a_{2j} \mid , ..., \sum_{j=1}^{n} \mid a_{nj} \mid \right \} \end{align}

Note that $\| A \|_{\infty}$ is equal to the maximum of the sum of the absolute values of the entries for the rows of $A$.

As an example, we will now show that the norm $\| A \|_{\infty}$ is indeed a matrix norm.

Note though for each $i, j = 1, 2, ..., n$ we have that $\mid a_{ij} \mid ≥ 0$ and so each sum, $\sum_{j=1}^{n} \mid a_{ij} \mid = \mid a_{i1} \mid + \mid a_{i2} \mid + ... + \mid a_{in} \mid ≥ 0$, and thus $\| A \|_{\infty} = \max_{1≤i≤n} \sum_{j=1}^{n} \mid a_{ij} \mid ≥ 0$.

Now suppose that $\| A \|_{\infty} 0$. This implies that each $a_{ij} = 0$ for $i, j = 1, 2, ..., n$, and so $A$ is the $n \times n$ zero matrix. Conversely, suppose that $A$ is the $n \times n$ zero matrix. Then all entries in $A$ are zero, and the sum of the absolute values of the rows of $A$ will all be zero, so $\| A \|_{\infty} = 0$. Therefore property 1 holds.

Now let $\alpha \in \mathbb{R}$. Then:

(3)

\begin{align} \quad \| \alpha A \|_{\infty} = \max_{1≤i≤n} \sum_{j=1}^{n} \mid \alpha a_{ij} \mid = \max \left \{ \sum_{j=1}^{n} \mid \alpha a_{1j} \mid , \sum_{j=1}^{n} \mid \alpha a_{2j} \mid , ..., \sum_{j=1}^{n} \mid \alpha a_{nj} \mid \right \} \\ \quad \quad = \max \left \{ \mid \alpha \mid \sum_{j=1}^{n} \mid a_{1j} \mid , \mid \alpha \mid \sum_{j=1}^{n} \mid a_{2j} \mid , ..., \mid \alpha \mid \sum_{j=1}^{n} \mid a_{nj} \mid \right \} = \mid \alpha \mid \max \left \{ \sum_{j=1}^{n} \mid a_{1j} \mid , \sum_{j=1}^{n} \mid a_{2j} \mid , ..., \sum_{j=1}^{n} \mid a_{nj} \mid \right \} = \mid \alpha \mid \| A \|_{\infty} \end{align}

Therefore property 2 holds. Let $A, B \in M_{nn}$. Now for verifying property 3, we can apply the triangle inequality for the absolute value of two real numbers and we have that:

(4)

\begin{align} \quad \| A + B \|_{\infty} = \max_{1≤i≤n} \sum_{j=1}^{n} \mid a_{ij} + b_{ij} \mid = \max \left \{ \sum_{j=1}^{n} \mid a_{1j} + b_{1j} \mid , \sum_{j=1}^{n} \mid a_{2j} + b_{2j} \mid , ..., \sum_{j=1}^{n} \mid a_{nj} + b_{nj} \mid \right \} \\ \quad ≤ \max \left \{ \sum_{j=1}^{n} \left ( \mid a_{1j} \mid + \mid b_{1j} \mid \right ), \sum_{j=1}^{n} \left ( \mid a_{2j} \mid + \mid b_{2j} \mid \right ), ..., \sum_{j=1}^{n} \left ( \mid a_{nj} \mid + \mid b_{nj} \mid \right ) \right \} \\ \quad = \max \left \{ \sum_{j=1}^{n} \mid a_{1j} \mid + \sum_{j=1}^{n} \mid b_{1j} \mid, \sum_{j=1}^{n} \mid a_{2j} \mid + \sum_{j=1}^{n} \mid b_{2j} \mid, ..., \sum_{j=1}^{n} \mid a_{nj} \mid + \sum_{j=1}^{n} \mid b_{nj} \mid \right \} \\ \quad \quad ≤ \max \left \{ \sum_{j=1}^{n} \mid a_{1j} \mid , \sum_{j=1}^{n} \mid a_{2j} \mid , ..., \sum_{j=1}^{n} \mid a_{nj} \mid \right \} + \max \left \{ \sum_{j=1}^{n} \mid b_{1j} \mid , \sum_{j=1}^{n} \mid b_{2j} \mid , ..., \sum_{j=1}^{n} \mid b_{nj} \mid \right \} = \| A \|_{\infty} + \| B \|_{\infty} \end{align}

Thus property 3 holds. Showing property 4 holds can be done in a similar manner, but we will omit showing this here and leave it as an exercise to the reader.