Skip to main content

Subsection 1.6.2 Summary

If \(\alpha, \beta \in \mathbb C \) with \(\alpha = \alpha_r + \alpha_c i \) and \(\beta = \beta_r + i \beta_c \text{,}\) where \(\alpha_r, \alpha_c, \beta_r, \beta_c \in \mathbb R \text{,}\) then

  • Conjugate: \(\overline \alpha = \alpha_r - \alpha_c i \text{.}\)

  • Product: \(\alpha \beta = (\alpha_r \beta_r - \alpha_c \beta_c ) + ( \alpha_r \beta_c + \alpha_c \beta_r ) i \text{.}\)

  • Absolute value: \(\vert \alpha \vert = \sqrt{ \alpha_r^2 + \alpha_c^2 } = \sqrt{ \overline \alpha \alpha } \text{.}\)

Let \(x, y \in \Cm \) with \(x = \left( \begin{array}{c} \chi_0 \\ \vdots \\ \chi_{m-1} \end{array} \right) \mbox{ and } y = \left( \begin{array}{c} \psi_0 \\ \vdots \\ \psi_{m-1} \end{array} \right). \) Then

  • Conjugate:

    \begin{equation*} \overline x = \left( \begin{array}{c} \overline \chi_0 \\ \vdots \\ \overline \chi_{m-1} \end{array} \right). \end{equation*}
  • Transpose of vector:

    \begin{equation*} x^T = \left( \begin{array}{c c c} \chi_0 \amp \cdots \amp \chi_{m-1} \end{array} \right) \end{equation*}
  • Hermitian transpose (conjugate transpose) of vector:

    \begin{equation*} x^H = \overline x^T = \overline {x^T} = \left( \begin{array}{c c c} \overline \chi_0 \amp \cdots \amp \overline \chi_{m-1} \end{array} \right). \end{equation*}
  • Dot product (inner product): \(x^H y = \overline x^T y = \overline {x^T} y = \overline \chi_0 \psi_0 + \cdots + \overline \chi_{m-1} \psi_{m-1} = \sum_{i=0}^{m-1} \overline \chi_i \psi_i \text{.}\)

Definition 1.6.2.1. Vector norm.

Let \(\| \cdot \|: \Cm \rightarrow \mathbb R \text{.}\) Then \(\| \cdot \|\) is a (vector) norm if for all \(x, y \in \Cm \) and all \(\alpha \in \mathbb C \)

  • \(x \neq 0 \Rightarrow \| x \| > 0 \) (\(\| \cdot \| \) is positive definite),
  • \(\| \alpha x \| = \vert \alpha \vert \| x \|\) (\(\| \cdot \| \) is homogeneous), and
  • \(\| x + y \| \leq \| x \| + \| y \| \) (\(\| \cdot \| \) obeys the triangle inequality).

  • 2-norm (Euclidean length): \(\| x \|_2 = \sqrt{ x^H x } = \sqrt{ \vert \chi_0 \vert^2 + \cdots + \vert \chi_{m-1} \vert^2 } = \sqrt{ \overline \chi_0 \chi_0 + \cdots + \overline \chi_{m-1} \chi_{m-1} } \) \(= \sqrt{ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 } \text{.}\)

  • \(p \)-norm: \(\| x \|_p = \sqrt[p]{ \vert \chi_0 \vert^p + \cdots + \vert \chi_{m-1} \vert^p } = \sqrt[p]{\sum_{i=0}^{m-1} \vert \chi_i \vert^p } \text{.}\)

  • 1-norm: \(\| x \|_1 = \vert \chi_0 \vert + \cdots + \vert \chi_{m-1} \vert = \sum_{i=0}^{m-1} \vert \chi_i \vert \text{.}\)

  • \(\infty \)-norm: \(\| x \|_\infty = \max( \vert \chi_0 \vert, \ldots , \chi_{m-1} \vert ) = \max_{i=0}^{m-1} \vert \chi_i \vert = \lim_{p \rightarrow \infty} \| x \|_p \text{.}\)

  • Unit ball: Set of all vectors with norm equal to one. Notation: \(\| x \| = 1. \)

\begin{equation*} \begin{array}{c | c | c } \amp \| x \|_1 \leq \sqrt{m} \| x \|_2 \amp {\color{black} {\| x \|_1 \leq m \| x \|_\infty}} \\ \hline \| x \|_2 \leq \| x \|_1 \amp \amp \| x \|_2 \leq \sqrt{m} \| x \|_\infty \\ \hline \| x \|_\infty \leq \| x \|_1 \amp \| x \|_\infty \leq \| x \|_2 \amp \end{array} \end{equation*}
Definition 1.6.2.3. Linear transformations and matrices.

Let \(L : \Cn \rightarrow \Cm \text{.}\) Then \(L \) is said to be a linear transformation if for all \(\alpha \in \mathbb C \) and \(x, y \in \Cn \)

  • \(L( \alpha x ) = \alpha L( x ) \text{.}\) That is, scaling first and then transforming yields the same result as transforming first and then scaling.

  • \(L( x + y ) = L( x ) + L( y ) \text{.}\) That is, adding first and then transforming yields the same result as transforming first and then adding.

Definition 1.6.2.4. Standard basis vector.

In this course, we will use \(e_j \in \Cm \) to denote the standard basis vector with a "1" in the position indexed with \(j \text{.}\) So,

\begin{equation*} e_j = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) \begin{array}{c} \phantom{0} \\ \phantom{\vdots} \\ \phantom{0} \\ \longleftarrow j \\ \phantom{0} \\ \phantom{\vdots} \\ \phantom{0} \end{array} \end{equation*}

If \(L \) is a linear transformation and we let \(a_j = L( e_j ) \) then

\begin{equation*} A = \left( \begin{array}{c | c | c | c} a_0 \amp a_1 \amp \cdots \amp a_{n-1} \end{array} \right) \end{equation*}

is the matrix that represents \(L \) in the sense that \(A x = L( x ) \text{.}\)

Partition \(C \text{,}\) \(A \text{,}\) and \(B \) by rows and columns

\begin{equation*} C = \left( \begin{array}{c | c | c} c_0 \amp \cdots \amp c_{n-1} \end{array} \right) = \left( \begin{array}{c} \widetilde c_0^T \\ \hline \vdots \\ \hline \widetilde c_{m-1}^T \end{array} \right), A = \left( \begin{array}{c | c | c} a_0 \amp \cdots \amp a_{k-1} \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right), \end{equation*}

and

\begin{equation*} B = \left( \begin{array}{c | c | c} b_0 \amp \cdots \amp b_{n-1} \end{array} \right) = \left( \begin{array}{c} \widetilde b_0^T \\ \hline \vdots \\ \hline \widetilde b_{k-1}^T \end{array} \right), \end{equation*}

then \(C := A B \) can be computed in the following ways:

  1. By columns:

    \begin{equation*} \left( \begin{array}{c | c | c} c_0 \amp \cdots \amp c_{n-1} \end{array} \right) := A \left( \begin{array}{c | c | c} b_0 \amp \cdots \amp b_{n-1} \end{array} \right) = \left( \begin{array}{c | c | c} A b_0 \amp \cdots \amp A b_{n-1} \end{array} \right). \end{equation*}

    In other words, \(c_j := A b_j \) for all columns of \(C \text{.}\)

  2. By rows:

    \begin{equation*} \left( \begin{array}{c} \widetilde c_0^T \\ \hline \vdots \\ \hline \widetilde c_{m-1}^T \end{array} \right) := \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) B = \left( \begin{array}{c} \widetilde a_0^T B \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T B \end{array} \right). \end{equation*}

    In other words, \(\widetilde c_i^T = \widetilde a_i^T B\) for all rows of \(C \text{.}\)

  3. As the sum of outer products:

    \begin{equation*} C := \left( \begin{array}{c | c | c} a_0 \amp \cdots \amp a_{k-1} \end{array} \right) \left( \begin{array}{c} \widetilde b_0^T \\ \hline \vdots \\ \hline \widetilde b_{k-1}^T \end{array} \right) = a_0 \widetilde b_0^T + \cdots + a_{k-1} \widetilde b_{k-1} ^T, \end{equation*}

    which should be thought of as a sequence of rank-1 updates, since each term is an outer product and an outer product has rank of at most one.

Partition \(C \text{,}\) \(A \text{,}\) and \(B \) by blocks (submatrices),

\begin{equation*} C = \left( \begin{array}{c | c | c} C_{0,0} \amp \cdots \amp C_{0,N-1} \\ \hline \vdots \amp \amp \vdots \\ \hline C_{M-1,0} \amp \cdots \amp C_{M-1,N-1} \end{array} \right), \left( \begin{array}{c | c | c} A_{0,0} \amp \cdots \amp A_{0,K-1} \\ \hline \vdots \amp \amp \vdots \\ \hline A_{M-1,0} \amp \cdots \amp A_{M-1,K-1} \end{array} \right), \end{equation*}

and

\begin{equation*} \left( \begin{array}{c | c | c} B_{0,0} \amp \cdots \amp B_{0,N-1} \\ \hline \vdots \amp \amp \vdots \\ \hline B_{K-1,0} \amp \cdots \amp B_{K-1,N-1} \end{array} \right), \end{equation*}

where the partitionings are "conformal." Then

\begin{equation*} C_{i,j} = \sum_{p=0}^{K-1} A_{i,p} B_{p,j} . \end{equation*}
Definition 1.6.2.5. Matrix norm.

Let \(\| \cdot \|: \mathbb C^{m \times n} \rightarrow \mathbb R \text{.}\) Then \(\| \cdot \| \) is a (matrix) norm if for all \(A, B \in \mathbb C^{m \times n} \) and all \(\alpha \in \mathbb C \)

  • \(A \neq 0 \Rightarrow \| A \| > 0 \) (\(\| \cdot \| \) is positive definite),
  • \(\| \alpha A \| = \vert \alpha \vert \| A \|\) (\(\| \cdot \| \) is homogeneous), and
  • \(\| A + B \| \leq \| A \| + \| B \| \) (\(\| \cdot \| \) obeys the triangle inequality).

Let \(A \in \mathbb C^{m \times n} \) and

\begin{equation*} A = \left( \begin{array}{c c c} \alpha_{0,0} \amp \cdots \alpha_{0,n-1} \\ \vdots \amp \vdots \\ \alpha_{m-1,0} \amp \cdots \alpha_{m-1,n-1} \\ \end{array} \right) = \left( \begin{array}{c | c | c} a_0 \amp \cdots \amp a_{n-1} \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T \\ \hline \vdots \\ \hline \widetilde a_{m-1}^T \end{array} \right) . \end{equation*}

Then

  • Conjugate of matrix:

    \begin{equation*} \overline A = \left( \begin{array}{cc c } \overline \alpha_{0,0} \amp \cdots \amp \overline \alpha_{0,n-1} \\ \vdots \amp \vdots \\ \overline \alpha_{m-1,0} \amp \cdots \amp \overline \alpha_{m-1,n-1} \end{array} \right). \end{equation*}
  • Transpose of matrix:

    \begin{equation*} A^T = \left( \begin{array}{c c c} \alpha_{0,0} \amp \cdots \amp \alpha_{m-1,0} \\ \vdots \amp \vdots \\ \alpha_{0,n-1} \amp \cdots \amp \alpha_{m-1,n-1} \\ \end{array} \right). \end{equation*}
  • Conjugate transpose (Hermitian transpose) of matrix:

    \begin{equation*} A^H = \overline A^T = {\overline A^T} = \left( \begin{array}{c c c} \overline \alpha_{0,0} \amp \cdots \amp \overline \alpha_{m-1,0} \\ \vdots \amp \vdots \\ \overline \alpha_{0,n-1} \amp \cdots \amp \overline \alpha_{m-1,n-1} \\ \end{array} \right). \end{equation*}
  • Frobenius norm: \(\| A \|_F = \sqrt{\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} \vert \alpha_{i,j} \vert^2} = \sqrt{ \sum_{j=0}^{n-1} \| a_j \|_2^2 } = \sqrt{ \sum_{i=0}^{m-1} \| \widetilde a_i \|_2^2 } \)

  • matrix p-norm: \(\| A \|_p = \max_{x \neq 0} \frac{\| A x \|_p}{\| x \|_p} = \max_{\| x \|_p =1} \| A x \|_p .\)

  • matrix 2-norm: \(\| A \|_2 = \max_{x \neq 0} \frac{\| A x \|_2}{\| x \|_2} = \max_{\| x \|_2 =1} \| A x \|_2 = \| A^H \|_2.\)

  • matrix 1-norm: \(\| A \|_1 = \max_{x \neq 0} \frac{\| A x \|_1}{\| x \|_1} = \max_{\| x \|_1 =1} \| A x \|_1 = \max_{0 \leq j \lt n} \| a_j \|_1 = \| A^H \|_\infty. \)

  • matrix \(\infty \)-norm: \(\| A \|_\infty = \max_{x \neq 0} \frac{\| A x \|_\infty}{\| x \|_\infty} = \max_{\| x \|_\infty =1} \| A x \|_\infty = \max_{0 \leq i \lt m} \| \widetilde a_i \|_1 = \| A^H \|_1.\)

\begin{equation*} \begin{array}{c | c | c | c } \amp \| A \|_1 \leq \sqrt m \| A \|_2 \amp {\color{black} {\| A \|_1 \leq m \| A \|_\infty}} \amp {\color{black} {\| A \|_1 \leq \sqrt m \| A \|_F}} \\ \hline \| A \|_2 \leq \sqrt n \| A \|_1 \amp \amp \| A \|_2 \leq \sqrt m \| A \|_\infty \amp \| A \|_2 \leq \| A \|_F \\ \hline \| A \|_\infty \leq n \| A \|_1 \amp \| A \|_\infty \leq \sqrt n \| A \|_2 \amp \amp \| A \|_\infty \leq \sqrt m \| A \|_F \\ \hline \| A \|_F \leq \sqrt n \| A \|_1 \amp \| A \|_F \leq {\rm rank}( A ) \| A \|_2 \amp \| A \|_F \leq \sqrt m \| A \|_\infty \amp \end{array} \end{equation*}
Definition 1.6.2.7. Subordinate matrix norm.

A matrix norm \(\| \cdot \|: \C^{m \times n} \rightarrow \mathbb R \) is said to be subordinate to vector norms \(\| \cdot \|_\mu: \Cm \rightarrow \mathbb R \) and \(\| \cdot \|_\nu: \Cn \rightarrow \mathbb R \) if, for all \(x \in \Cn \text{,}\)

\begin{equation*} \| A x \|_\mu \leq \| A \| \| x \|_\nu . \end{equation*}

If \(\| \cdot \|_\mu \) and \(\| \cdot \|_\nu \) are the same norm (but perhaps for different \(m \) and \(n \)), then \(\| \cdot \| \) is said to be subordinate to the given vector norm.

Definition 1.6.2.8. Consistent matrix norm.

A matrix norm \(\| \cdot \|: \C^{m \times n} \rightarrow \mathbb R \) is said to be a consistent matrix norm if it is defined for all \(m \) and \(n \text{,}\) using the same formula for all \(m \) and \(n \text{.}\)

Definition 1.6.2.9. Submultiplicative matrix norm.

A consistent matrix norm \(\| \cdot \|: \C^{m \times n} \rightarrow \mathbb R \) is said to be submultiplicative if it satisfies

\begin{equation*} \| A B \| \leq \| A \| \| B \| . \end{equation*}

Let \(A, \Delta\!A \in \mathbb C^{m \times m} \text{,}\) \(x, \delta\!x, b, \delta\!b \in \Cm \text{,}\) \(A \) be nonsingular, and \(\| \cdot \| \) be a vector norm and corresponding subordinate matrix norm. Then

\begin{equation*} \frac{\| \delta\!x \|}{\| x \|} \leq \begin{array}[t]{c} \underbrace{ \| A \| \| A^{-1} \| } \\ \kappa( A ) \end{array} \frac{\| \delta\!b \|}{\| b \|}. \end{equation*}
Definition 1.6.2.10. Condition number of a nonsingular matrix.

The value \(\kappa( A ) = \| A \| \| A^{-1} \| \) is called the condition number of a nonsingular matrix \(A \text{.}\)