## Unit1.6.2Summary

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{.}$

###### Definition1.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*}
###### Definition1.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.

###### Definition1.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*}
###### Definition1.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 n \| 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*}
###### Definition1.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.

###### Definition1.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{.}$

###### Definition1.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*}
###### Definition1.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{.}$