Skip to main content

Subsection 6.2.6 Absolute value of vectors and matrices

In the above discussion of error, the vague notions of "near" and "slightly perturbed" are used. Making these notions exact usually requires the introduction of measures of size for vectors and matrices, i.e., norms. When analyzing the stability of algorithms, we instead give all bounds in terms of the absolute values of the individual elements of the vectors and/or matrices. While it is easy to convert such bounds to bounds involving norms, the converse is not true.

Definition 6.2.6.1. Absolute value of vector and matrix.

Given \(x \in \Rn \) and \(A \in \Rmxn \text{,}\)

\begin{equation*} \vert x \vert = \left( \begin{array}{c} \vert \chi_0 \vert \\ \vert \chi_1 \vert \\ \vdots \\ \vert \chi_{n-1} \vert \end{array} \right) \quad \mbox{and} \quad \vert A \vert = \left( \begin{array}{c c c c} \vert \alpha_{0,0} \vert \amp \vert \alpha_{0,1} \vert \amp \dots \amp \vert \alpha_{0,n-1} \vert \\ \vert \alpha_{1,0} \vert \amp \vert \alpha_{1,1} \vert \amp \dots \amp \vert \alpha_{1,n-1} \vert \\ \vdots \amp \vdots \amp \ddots \amp \vdots \\ \vert \alpha_{m-1,0} \vert \amp \vert \alpha_{m-1,1} \vert \amp \dots \amp \vert \alpha_{m-1,n-1} \vert \end{array} \right)\!. \end{equation*}
Definition 6.2.6.2.

Let \(\vartriangle \in\!\{\lt, \leq, =, \geq, >\}\) and \(x, y \in \Rn \text{.}\) Then

\begin{equation*} \vert x \vert \! \vartriangle \! \vert y \vert \quad \mbox{iff} \quad \vert \chi_i \vert \! \vartriangle \! \vert \psi_i \vert, \end{equation*}

for all \(i = 0, \ldots, n-1 \text{.}\) Similarly, given \(A\) and \(B \in \Rmxn \text{,}\)

\begin{equation*} \vert A \vert \! \vartriangle \! \vert B \vert \quad \mbox{iff} \quad \vert \alpha_{ij} \vert\!\vartriangle\!\vert \beta_{ij} \vert , \end{equation*}

for all \(i = 0, \ldots, m-1 \) and \(j = 0, \ldots, n-1 \text{.}\)

The next Lemma is exploited in later sections:

Homework 6.2.6.1.

Let \(A \in \R^{m \times k} \) and \(B \in \R^{k \times n} \text{.}\)

ALWAYS/SOMETIMES/NEVER: \(\vert A B \vert \leq \vert A \vert \vert B \vert \text{.}\)

Answer

ALWAYS

Now prove it.

Solution

Let \(C = A B \text{.}\) Then the \((i,j) \) entry in \(\vert C \vert \) is given by

\begin{equation*} \vert \gamma_{i,j} \vert = \left\vert \sum_{p=0}^{k-1}\alpha_{i,p} \beta_{p,j} \right\vert \leq \sum_{p=0}^{k-1} \vert \alpha_{i,p} \beta_{p,j} \vert = \sum_{p=0}^{k-1} \vert \alpha_{i,p} \vert \vert \beta_{p,j} \vert \end{equation*}

which equals the \((i,j) \) entry of \(\vert A \vert \vert B \vert \text{.}\) Thus \(\vert A B \vert \leq \vert A \vert \vert B \vert \text{.}\)

The fact that the bounds that we establish can be easily converted into bounds involving norms is a consequence of the following theorem, where \(\| \ \|_F \) indicates the Frobenius matrix norm.

Homework 6.2.6.2.

Prove Theorem 6.2.6.3

Solution

  • Show that if \(\vert A \vert \leq \vert B \vert \) then \(\| A \|_F \leq \| B \|_F \text{:}\)

    \begin{equation*} \| A \|_F^2 = \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \vert \alpha_{i,j}\vert^2 \leq \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \vert \beta_{i,j}\vert ^2 = \| B \|_F^2. \end{equation*}

    Hence \(\| A \|_F \leq \| B \|_F \text{.}\)

  • Show that if \(\vert A \vert \leq \vert B \vert \) then \(\| A \|_1 \leq \| B \|_1 \text{:}\)

    Let

    \begin{equation*} A = \left( \begin{array}{c | c | c } a_0 \amp \cdots \amp a_{n-1} \end{array} \right) \quad \mbox{and} \quad B = \left( \begin{array}{c | c | c } b_0 \amp \cdots \amp b_{n-1} \end{array} \right) . \end{equation*}

    Then

    \begin{equation*} \begin{array}{l} \| A \|_1 \\ ~~~ = ~~~~ \lt \mbox{ alternate way of computing 1-norm } \gt \\ \max_{0 \leq j \lt n } \| a_j \|_1 \\ ~~~ = ~~~~ \lt \mbox{ expose individual entries of } a_j \gt \\ \max_{0 \leq j \lt n } \left( \sum_{i=0}^{m-1} \vert \alpha_{i,j} \vert \right) \\ ~~~ = ~~~~ \lt \mbox{ choose } k \mbox{ to be the index that maximizes} \gt \\ \left( \sum_{i=0}^{m-1} \vert \alpha_{i,k} \vert \right) \\ ~~~ \leq ~~~~ \lt \mbox{ entries of } B \mbox{ bound corresponding entries of } A \gt \\ \left( \sum_{i=0}^{m-1} \vert \beta_{i,k} \vert \right) \\\ ~~~ = ~~~~ \lt \mbox{ express sum as 1-norm of column indexed with } k \gt \\ \| b_k \|_1 \\ ~~~ \leq ~~~~ \lt \mbox{ take max over all columns } \gt\\ \max_{0 \leq j \lt n } \| b_j \|_1 \\ ~~~ = ~~~~ \lt \mbox{ definition of 1-norm } \gt \\ \| B \|_1. \end{array} \end{equation*}

  • Show that if \(\vert A \vert \leq \vert B \vert \) then \(\| A \|_\infty \leq \| B \|_\infty \text{:}\)

    Note:

    • \(\| A \|_\infty = \| A^T \|_1 \) and \(\| B \|_\infty = \| B^T \|_1 \text{.}\)

    • If \(\vert A \vert \leq \vert B \vert \) then, clearly, \(\vert A^T \vert \leq \vert B^T \vert \text{.}\)

    Hence

    \begin{equation*} \| A \|_\infty = \| A^T \|_1 \leq \| B^T \|_1 = \| B \|_\infty. \end{equation*}
login