4.7. The Euclidean Space

This section consolidates major results for the real Euclidean space ${\mathbb{R}}^n$ as a ready reference. ${\mathbb{R}}^2$ (the 2-dimensional plane) and ${\mathbb{R}}^3$ the 3-dimensional space are the most familiar spaces to us.

${\mathbb{R}}^n$ is a generalization in $n$ dimensions.

Definition 4.89 (${\mathbb{R}}^n$ and Euclidean space)

For any positive integer $n$, the set of all $n$-tuples of real numbers forms an $n$-dimensional vector space over $\mathbb{R}$ which is denoted as ${\mathbb{R}}^n$. It is sometimes called real coordinate space.

An element $\mathbf{x}$ in ${\mathbb{R}}^n$ is written as

$$\mathbf{x}=(x_1,x_2,\dots ,x_n),$$

where each $x_i$ is a real number.

Vector space operations on ${\mathbb{R}}^n$ are defined by:

$$\begin{array}{rl}& \mathbf{x}+\mathbf{y}=(x_1+y_1,x_2+y_2,\dots ,x_n+y_n),\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n.\\ & \alpha \mathbf{x}=(\alpha x_1,\alpha x_2,\dots ,\alpha x_n)\mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n,\alpha \in \mathbb{R}.\end{array}$$

When equipped with the standard inner product and standard norm (defined below), ${\mathbb{R}}^n$ becomes the Euclidean space.

Definition 4.90 (Standard basis)

${\mathbb{R}}^n$ comes with the standard ordered basis $\mathcal{B}=\{{\mathbf{e}}_1,{\mathbf{e}}_2,\dots ,{\mathbf{e}}_n\}$:

$$\begin{array}{r}\begin{array}{rl}& {\mathbf{e}}_1=(1,0,\dots ,0),\\ & {\mathbf{e}}_2=(0,1,\dots ,0),\\ & ⋮\\ & {\mathbf{e}}_n=(0,0,\dots ,1)\end{array}\end{array}$$

An arbitrary vector $\mathbf{x}\in {\mathbb{R}}^n$ can be written as

$$\mathbf{x}=\sum _{i=1}^n{x}_i{\mathbf{e}}_i.$$

4.7.1. Inner Products

Definition 4.91 (Standard inner product/ dot product)

The standard inner product (a.k.a. dot product) on ${\mathbb{R}}^n$ is defined as:

$$⟨\mathbf{x},\mathbf{y}⟩=\sum _{i=1}^n{x}_i{y}_i=x_1{y}_1+x_2{y}_2+\cdots +x_n{y}_n\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n.$$

This makes ${\mathbb{R}}^n$ an inner product space.

Remark 4.10

The dot product is always a real number. Hence we have symmetry:

$$⟨x,y⟩=⟨y,x⟩$$

It is a real inner product.

Definition 4.92 ($\mathbf{Q}$ inner product)

Let $\mathbf{Q}$ be an $n\times n$ real symmetric positive definite matrix. The $\mathbf{Q}$ inner product is defined as:

$$⟨\mathbf{x},\mathbf{y}{⟩}_Q\triangleq {\mathbf{x}}^T\mathbf{Q}\mathbf{y}.$$

$\mathbf{Q}$ inner product reduces to standard dot product when $\mathbf{Q}=\mathbf{I}$.

4.7.2. Norms

We use norms as a measure of strength of a signal or size of an error. Different norms signify different aspects of the signal.

Definition 4.93 (Euclidean norm)

The length of the vector (a.k.a. Euclidean norm or ${\ell }_2$ norm) is defined as:

$$\Vert \mathbf{x}\Vert =\sqrt{⟨\mathbf{x},\mathbf{x}⟩}=\sqrt{\sum _{i=1}^n{x}_i^2}\mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n.$$

This makes ${\mathbb{R}}^n$ a normed linear space.

4.7.2.1. Angles

Definition 4.94 (Angle)

The angle $\theta$ between two vectors is given by:

$$\theta ={\cos }^{-1}\frac{⟨\mathbf{x},\mathbf{y}⟩}{\Vert \mathbf{x}\Vert \Vert \mathbf{y}\Vert }.$$

4.7.2.2. ${\ell }_p$ Norms

In addition to standard Euclidean norm, we define a family of norms indexed by $p\in [1,\mathrm{\infty }]$ known as ${\ell }_p$ norms over ${\mathbb{R}}^n$.

Definition 4.95 (${\ell }_p$ norm)

Let $p\in [1,\mathrm{\infty }]$. For any $n\in \mathbb{N}$, the $l_p$ norm denoted as $\Vert \cdot {\Vert }_p:{\mathbb{R}}^n\to \mathbb{R}$ mapping any vector $\mathbf{x}\in {\mathbb{R}}^n$ to a non-negative number is defined as:

$$\begin{array}{r}\Vert \mathbf{x}{\Vert }_p=\{\begin{array}{lll}{\left(\sum _{i=1}^n|x_i{|}^p\right)}^{\frac{1}{p}}& \text{ if }& p\in [1,\mathrm{\infty })\\ \underset{1\le i\le n}{max}|x_i|& \text{ if }& p=\mathrm{\infty }\end{array}.\end{array}$$

We mention the special cases. $p=1$ gives us:

$$\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^n|x_i|=|x_1|+|x_2|+\cdots +|x_n|.$$

$p=2$ gives us:

$$\Vert \mathbf{x}{\Vert }_2={\left(\sum _{i=1}^n|x_i{|}^2\right)}^{\frac{1}{2}}$$

which is same as the standard Euclidean norm.

$p=\mathrm{\infty }$ gives us:

$$\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}=\underset{1\le i\le n}{max}|x_i|.$$

We need to justify that ${\ell }_p$ norm defined as above is indeed a norm. Before that, we state the Hölder’s inequality for the Euclidean space.

Theorem 4.110 (Hölder’s inequality)

Let $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^n$. Let $p\in [1,\mathrm{\infty }]$ and let $q$ be its conjugate exponent.

We have:

(4.4)$$\Vert \mathbf{u}\mathbf{v}{\Vert }_1\le \Vert \mathbf{u}{\Vert }_p\Vert \mathbf{v}{\Vert }_q$$

where $\mathbf{u}\mathbf{v}$ denotes the element-wise multiplication given by:

$$\mathbf{u}\mathbf{v}=(u_1{v}_1,\dots ,u_n{v}_n).$$

Proof. If $\mathbf{u}=\mathbf{0}$ or $\mathbf{v}=\mathbf{0}$, then (4.4) follows immediately.

Now, consider the case where $\mathbf{u}\ne \mathbf{0}$ and $\mathbf{v}\ne \mathbf{0}$.

If $p=1$, then $q=\mathrm{\infty }$. We have:

$$\Vert \mathbf{u}\mathbf{v}{\Vert }_1=\sum _{i=1}^n|u_i{v}_i|\le \underset{1\le j\le n}{max}|v_j|\sum _{i=1}^n|u_i|=\Vert \mathbf{u}{\Vert }_1\Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}.$$

The same argument applies for the case of $p=\mathrm{\infty }$ and $q=1$ too. For the case of $p,q\in (1,\mathrm{\infty })$, we have:

$$\Vert \mathbf{u}{\Vert }_p={\left(\sum _{k=1}^n|u_k{|}^p\right)}^{\frac{1}{p}}\text{and }\Vert \mathbf{v}{\Vert }_q={\left(\sum _{k=1}^n|v_k{|}^q\right)}^{\frac{1}{q}}.$$

We recall the Hölder's inequality for real numbers. For any $n\in \mathbb{N}$, $a_1,\dots ,a_n\ge 0$, $b_1,\dots ,b_n\ge 0$, $p,q$ being conjugate exponents, we have:

$$\sum _{k=1}^n{a}_k{b}_k\le {\left(\sum _{k=1}^n{a}_k^p\right)}^{\frac{1}{p}}{\left(\sum _{k=1}^n{b}_k^q\right)}^{\frac{1}{q}}.$$

Let $a_k=|u_k|$ and $b_k=|v_k|$. Then

$$\Vert \mathbf{u}\mathbf{v}{\Vert }_1=\sum _{k=1}^n|u_k{v}_k|\le \sum _{k=1}^n|u_k||v_k|\le {\left(\sum _{k=1}^n|u_k{|}^p\right)}^{\frac{1}{p}}{\left(\sum _{k=1}^n|v_k{|}^q\right)}^{\frac{1}{q}}=\Vert \mathbf{u}{\Vert }_p\Vert \mathbf{v}{\Vert }_q.$$

We are now ready to prove that ${\ell }_p$ norm is indeed a norm.

Theorem 4.111 (${\ell }_p$ norms are norms)

For any $n\in \mathbb{N}$ and any $p\in [1,\mathrm{\infty }]$, the function $\Vert \cdot {\Vert }_p$ as defined in Definition 4.95 is a norm.

Proof. [Positive definiteness] By definition, if $\mathbf{u}\ne \mathbf{0}$, then $\Vert \mathbf{u}{\Vert }_p>0$. Similarly, $\Vert \mathbf{u}{\Vert }_p=0$ implies $\mathbf{u}=\mathbf{0}$.

[Positive homogeneity] Let $\alpha \in \mathbb{R}$. If $p<\mathrm{\infty }$, then

$$\Vert \alpha \mathbf{u}{\Vert }_p={\left(\sum _{k=1}^n|\alpha u_k{|}^p\right)}^{\frac{1}{p}}=|\alpha |{\left(\sum _{k=1}^n|u_k{|}^p\right)}^{\frac{1}{p}}=|\alpha |\Vert \mathbf{u}{\Vert }_p.$$

For $p=\mathrm{\infty }$,

$$\Vert \alpha \mathbf{u}{\Vert }_{\mathrm{\infty }}=\underset{1\le i\le n}{max}|\alpha u_i|=|\alpha |\underset{1\le i\le n}{max}|u_i|=|\alpha |\Vert \mathbf{u}{\Vert }_{\mathrm{\infty }}.$$

[Triangle inequality] Let $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^n$. If $p=1$, then

$$\Vert \mathbf{u}+\mathbf{v}{\Vert }_1=\sum _{i=1}^n|u_i+v_i|\le \sum _{i=1}^n|u_i|+|v_i|=\Vert \mathbf{u}{\Vert }_1+\Vert \mathbf{v}{\Vert }_1.$$

If $p=\mathrm{\infty }$, then:

$$\Vert \mathbf{u}+\mathbf{v}{\Vert }_{\mathrm{\infty }}=\underset{1\le i\le n}{max}|u_i+v_i|\le \underset{1\le i\le n}{max}(|u_i|+|v_i|)\le \underset{1\le i\le n}{max}|u_i|+\underset{1\le i\le n}{max}|v_i|=\Vert \mathbf{u}{\Vert }_{\mathrm{\infty }}+\Vert \mathbf{v}{\Vert }_{\mathrm{\infty }}.$$

We are left with the case $p\in (1,\mathrm{\infty })$.

$$\begin{array}{r}\begin{array}{rl}\Vert \mathbf{u}+\mathbf{v}{\Vert }_p^p& =\sum _{i=1}^n|u_i+v_i{|}^p\\ & =\sum _{i=1}^n|u_i+v_i||u_i+v_i{|}^{p-1}\\ & \le \sum _{i=1}^n|u_i||u_i+v_i{|}^{p-1}+\sum _{i=1}^n|v_i||u_i+v_i{|}^{p-1}.\end{array}\end{array}$$

By Hölder’s inequality:

$$\begin{array}{r}\begin{array}{rl}\sum _{i=1}^n|u_i||u_i+v_i{|}^{p-1}& \le {\left(\sum _{i=1}^n|u_i{|}^p\right)}^{\frac{1}{p}}{(\sum _{i=1}^n|u_i+v_i{|}^{(p-1)q})}^{\frac{1}{q}}\\ & =\Vert \mathbf{u}{\Vert }_p{(\sum _{i=1}^n|u_i+v_i{|}^p)}^{\frac{1}{q}}\\ & =\Vert \mathbf{u}{\Vert }_p\Vert \mathbf{u}+\mathbf{v}{\Vert }_p^{\frac{p}{q}}.\end{array}\end{array}$$

Note that $(p-1)q=p$ since $p,q$ are conjugate exponents.

Similarly:

$$\sum _{i=1}^n|v_i||u_i+v_i{|}^{p-1}\le \Vert \mathbf{v}{\Vert }_p\Vert \mathbf{u}+\mathbf{v}{\Vert }_p^{\frac{p}{q}}.$$

Combining, we get:

$$\Vert \mathbf{u}+\mathbf{v}{\Vert }_p^p\le (\Vert \mathbf{u}{\Vert }_p+\Vert \mathbf{v}{\Vert }_p)\Vert \mathbf{u}+\mathbf{v}{\Vert }_p^{\frac{p}{q}}.$$

Note that:

$$p-\frac{p}{q}=p(1-\frac{1}{q})=p\frac{1}{p}=1.$$

Thus, dividing both sides by $\Vert \mathbf{u}+\mathbf{v}{\Vert }_p^{\frac{p}{q}}$, we get:

$$\Vert \mathbf{u}+\mathbf{v}{\Vert }_p\le \Vert \mathbf{u}{\Vert }_p+\Vert \mathbf{v}{\Vert }_p$$

as desired.

4.7.2.3. ${\ell }_2$ Norm

As we can see from definition, ${\ell }_2$ norm is same as the Euclidean norm.

So we have:

$$\Vert \mathbf{x}\Vert =\Vert \mathbf{x}{\Vert }_2.$$

4.7.2.4. ${\ell }_1$ Norm

From above definition, we have

$$\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^n|x_i|=|x_1|+|x_2|+\cdots +|x_n|.$$

4.7.2.5. Quasi-norms

In some cases it is useful to extend the notion of ${\ell }_p$ norms to the case where $0<p<1$.

In such cases norm as defined in Definition 4.95 doesn’t satisfy triangle inequality. Hence it is not a proper norm function. We call such functions as quasi-norms.

4.7.2.6. ${\ell }_0$ “norm”

Of specific mention is ${\ell }_0$ “norm”. It isn’t even a quasi-norm. Note the use of quotes around the word norm to distinguish $l_0$ “norm” from usual norms.

Definition 4.96 (${\ell }_0$ “norm”)

${\ell }_0$ “norm” is defined as:

$$\Vert \mathbf{x}{\Vert }_0=|\mathrm{supp}(\mathbf{x})|$$

where $\mathrm{supp}(\mathbf{x})=\{i:x_i\ne 0\}$ denotes the support of $\mathbf{x}$.

Note that $\Vert \mathbf{x}{\Vert }_0$ defined above doesn’t follow the definition in Definition 4.95.

Yet we can show that:

$$\underset{p\to 0}{lim}\Vert \mathbf{x}{\Vert }_p^p=|\mathrm{supp}(\mathbf{x})|.$$

which justifies the notation.

Definition 4.97 ($\mathbf{Q}$ norm)

The $\mathbf{Q}$ norm induced by $\mathbf{Q}$ inner product is given by

$$\Vert \mathbf{x}{\Vert }_Q=\sqrt{{\mathbf{x}}^T\mathbf{Q}\mathbf{x}}.$$

4.7.2.7. Equivalence of Norms

${\mathbb{R}}^n$ is a finite dimensional vector space and all norms on ${\mathbb{R}}^n$ are equivalent. However, reaching this conclusion requires some hoofs to go through. Here is the roadmap.

1. We first establish that ${\ell }_1$ and ${\ell }_2$ norms are equivalent.

2. We then establish that ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms are equivalent.

3. We recall the Heine-Borel theorem for Euclidean metric and show that closed and bounded sets of $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$ are compact.

4. We then take advantage of the fact that equivalent norms lead to same topologies (open, closed and compact sets) as well as bounded sets and show that closed and bounded sets of $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ are also compact.

5. We are then in a position to demonstrate that all norms on ${\mathbb{R}}^n$ are indeed equivalent.

Theorem 4.112 (Equivalence of ${\ell }_1$ and ${\ell }_2$ norms)

The ${\ell }_1$ and ${\ell }_2$ norms on ${\mathbb{R}}^n$ are equivalent. In particular, for any $\mathbf{x}\in {\mathbb{R}}^n$

$$\frac{1}{\sqrt{n}}\Vert \mathbf{x}{\Vert }_1\le \Vert \mathbf{x}{\Vert }_2\le \Vert \mathbf{x}{\Vert }_1.$$

Alternatively,

$$\Vert \mathbf{x}{\Vert }_2\le \Vert \mathbf{x}{\Vert }_1\le \sqrt{n}\Vert \mathbf{x}{\Vert }_2.$$

Proof. By Cauchy-Schwarz inequality

$$\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^n|x_i|=\sum _{i=1}^n|x_i|.1\le \Vert \mathbf{x}{\Vert }_2\Vert \mathbf{1}{\Vert }_2=\sqrt{n}\Vert \mathbf{x}{\Vert }_2$$

where $\mathbf{1}$ is the vector of all ones. Thus,

$$\frac{1}{\sqrt{n}}\Vert \mathbf{x}{\Vert }_1\le \Vert {\mathbf{x}}_2\Vert .$$

Also,

$$\Vert \mathbf{x}{\Vert }_2^2=\sum _{i=1}^n|x_i{|}^2\le {\left(\sum _{i=1}^n|x_i|\right)}^2=\Vert \mathbf{x}{\Vert }_1^2.$$

Thus,

$$\Vert \mathbf{x}{\Vert }_2\le \Vert \mathbf{x}{\Vert }_1.$$

Thus, the two norms are equivalent.

Theorem 4.113 (Equivalence of ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms)

The ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms on ${\mathbb{R}}^n$ are equivalent. In particular, for any $\mathbf{x}\in {\mathbb{R}}^n$

$$\frac{1}{\sqrt{n}}\Vert \mathbf{x}{\Vert }_2\le \Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}\le \Vert \mathbf{x}{\Vert }_2.$$

Alternatively,

$$\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}\le \Vert \mathbf{x}{\Vert }_2\le \sqrt{n}\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}.$$

Proof. Let $\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}=sup\{|x_i|\}$.

1. Then, $|x_i|\le \Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}$.

2. Thus, $|x_i{|}^2\le \Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}^2$.

3. Taking the sum $\Vert \mathbf{x}{\Vert }_2^2\le n\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}^2$.

4. Taking the square root $\Vert \mathbf{x}{\Vert }_2\le \sqrt{n}\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}$.

For the other side, we note that

$$\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}^2={(sup\{|x_i|\})}^2\le \sum _{i=1}^n|x_i{|}^2=\Vert \mathbf{x}{\Vert }_2^2.$$

Thus, $\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}\le \Vert \mathbf{x}{\Vert }_2$. Thus, the two norms are equivalent.

Theorem 4.114 (Equivalence of ${\ell }_1$, ${\ell }_2$, and ${\ell }_{|infty}$ norms)

The ${\ell }_1$, ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms on ${\mathbb{R}}^n$ are equivalent.

Proof. We proceed as follows:

1. By Theorem 4.112, ${\ell }_1$ and ${\ell }_2$ norms are equivalent.

2. By Theorem 4.113, ${\ell }_2$ and ${\ell }_{\mathrm{\infty }}$ norms are equivalent.

3. By Theorem 4.58, equivalence of norms is an equivalence relation.

4. Hence, by transitivity, ${\ell }_1$ and ${\ell }_{\mathrm{\infty }}$ norms are equivalent.

Theorem 4.115 (Heine Borel theorem)

A subset of the normed linear space $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$ is compact if and only if it is a closed and bounded set.

Proof. The distance metric induced by $\Vert \cdot {\Vert }_2$ is the Euclidean distance.

This result is follows directly from Theorem 3.84.

Theorem 4.116 (Closed and bounded sets under ${\ell }_1$ norm)

A subset of the normed linear space $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ is compact if and only if it is a closed and bounded set.

Proof. We just need to show that if a set is closed and bounded in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$, then it is compact in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$.

1. The norms $\Vert \cdot {\Vert }_1$ and $\Vert \cdot {\Vert }_2$ are equivalent (Theorem 4.114).

2. Hence, the metrics induced by them are (strongly) equivalent (Theorem 4.59).

3. Thus, the open sets and closed sets in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ and $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$ are identical.

4. Hence, the compact sets in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ and $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$ are identical (Theorem 3.90).

5. Also the bounded sets in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ and $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$ are identical due to Theorem 4.57.

6. Now, let $A$ be a closed and bounded set in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$.

7. Then, $A$ is closed and bounded in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$.

8. But then by Heine Borel theorem, $A$ is compact in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_2)$.

9. But then, $A$ is compact in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ also.

Theorem 4.117 (Equivalence of norms on the Euclidean space)

Let $n\in \mathbb{N}$. All norms on ${\mathbb{R}}^n$ are equivalent.

Proof. The ${\ell }_1$ norm $\Vert \cdot {\Vert }_1:{\mathbb{R}}^n\to \mathbb{R}$ is given by:

$$\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^n|x_i|.$$

We shall show that any norm $\Vert \cdot \Vert :{\mathbb{R}}^n\to \mathbb{R}$ is equivalent to $\Vert \cdot {\Vert }_1:{\mathbb{R}}^n\to \mathbb{R}$. Then, since norm equivalence is an equivalence relation (Theorem 4.59), hence all norms are equivalent.

In particular, if $\Vert \cdot {\Vert }_a$ and $\Vert \cdot {\Vert }_b$ are two different norms on ${\mathbb{R}}^n$, then $\Vert \cdot {\Vert }_a\sim \Vert \cdot {\Vert }_1$ and $\Vert \cdot {\Vert }_b\sim \Vert \cdot {\Vert }_1$ implies that $\Vert \cdot {\Vert }_a\sim \Vert \cdot {\Vert }_b$ due to Theorem 4.59.

Towards this end, let’s show that any norm $\Vert \cdot \Vert$ is indeed equivalent to $\Vert \cdot {\Vert }_1$.

We first show that there exists a constant $c_1>0$ such that

$$\Vert \mathbf{x}\Vert \le c_1\Vert \mathbf{x}{\Vert }_1\mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n.$$

1. Let $\{{\mathbf{e}}_i\}$ be the standard basis for ${\mathbb{R}}^n$.

2. Let $c=max\{\Vert {\mathbf{e}}_i\Vert ,i=1,\dots ,n\}$.

3. Then, for any $\mathbf{x}\in {\mathbb{R}}^n$, we have

   $$\begin{array}{rl}\Vert \mathbf{x}\Vert & =\Vert \sum _{i=1}^n{x}_i{\mathbf{e}}_i\Vert \\ & \le \sum _{i=1}^n\Vert x_i{\mathbf{e}}_i\Vert \\ & =\sum _{i=1}^n|x_i|\Vert {\mathbf{e}}_i\Vert \\ & \le \sum _{i=1}^n|x_i|c\\ & =c\Vert \mathbf{x}{\Vert }_1.\end{array}$$

We now show that there exists a constant $c_2>0$ such that

$$\Vert \mathbf{x}{\Vert }_1\le c_2\Vert \mathbf{x}\Vert \mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n.$$

1. Define a function $g:({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)\to \mathbb{R}$ as

   $$g(\mathbf{x})=\Vert \mathbf{x}\Vert \mathrm{\forall }\mathbf{x}\in {\mathbb{R}}^n.$$

2. Then, for any $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$,

   $$|g(\mathbf{x})-g(\mathbf{y})|=|\Vert \mathbf{x}\Vert -\Vert \mathbf{y}\Vert |\le \Vert \mathbf{x}-\mathbf{y}\Vert \le c\Vert \mathbf{x}-\mathbf{y}{\Vert }_1.$$

3. Thus, $g$ is Lipschitz continuous on the normed linear space $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$.

4. Therefore, $g$ is continuous.

5. Now, let $S=\{\mathbf{y}\in {\mathbb{R}}^n|\Vert \mathbf{y}{\Vert }_1=1\}$.

6. $S$ is a closed set in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$ since it is the boundary of the unit ball.

7. $S$ is also bounded since $\Vert \mathbf{y}{\Vert }_1\le 1$ for every $\mathbf{y}\in S$.

8. Then, by Theorem 4.116 $S$ is compact in $({\mathbb{R}}^n,\Vert \cdot {\Vert }_1)$.

9. Hence, due to Theorem 3.85 $g$ attains a minimum value at some $\mathbf{y}\in S$ over the compact set $S$.

10. Let the minimum value of $g$ over $S$ be say $m$ at some ${\mathbf{y}}_0\in S$.

11. Note that $\mathbf{0}\notin S$ by definition since $\Vert \mathbf{0}\Vert \ne 1$.

12. Thus,

    $$m=g({\mathbf{y}}_0)=\Vert {\mathbf{y}}_0\Vert >0.$$

13. Thus, for all $\mathbf{y}\in S$, we have $\Vert \mathbf{y}\Vert \ge m>0$.

14. Now, for any nonzero $\mathbf{x}\in {\mathbb{R}}^n$, the ${\ell }_1$ normalized vector, $\mathbf{y}=\frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_1}\in S$.

15. But then

    $$\begin{array}{rl}& \Vert \mathbf{y}\Vert \ge m\\ & ⟹\Vert \frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_1}\Vert \ge m\\ & ⟹\Vert \mathbf{x}\Vert \ge m\Vert \mathbf{x}{\Vert }_1\\ & ⟹\Vert \mathbf{x}{\Vert }_1\le \frac{1}{m}\Vert \mathbf{x}\Vert \end{array}$$

    holds for every nonzero $\mathbf{x}\in {\mathbb{R}}^n$.

16. Also, the inequality $\Vert \mathbf{x}{\Vert }_1\le \frac{1}{m}\Vert \mathbf{x}\Vert$ is satisfied trivially by $\mathbf{0}$.

We have shown that for $c_1=c>0$ and $c_2=\frac{1}{m}>0$

$$\Vert \mathbf{v}\Vert \le c_1\Vert \mathbf{v}{\Vert }_1\text{ and }\Vert \mathbf{v}{\Vert }_1\le c_2\Vert \mathbf{v}\Vert$$

holds true for every $\mathbf{v}\in {\mathbb{R}}^n$.

Thus, the two norms $\Vert \cdot \Vert$ and $\Vert \cdot {\Vert }_1$ are indeed equivalent.

4.7.3. Distances

Definition 4.98 (Euclidean distance)

Distance between two vectors is defined as:

$$d(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}\Vert =\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}.$$

This distance function is known as Euclidean metric.

This makes ${\mathbb{R}}^n$ a metric space.

4.7.4. General Euclidean Space

We can generalize the definition of a Euclidean space to a more abstract case.

Definition 4.99 (General Euclidean space)

A finite dimensional real vector space $\mathbb{V}$ equipped with an inner product $⟨\cdot ,\cdot ⟩$ is called a Euclidean space if it is endowed with the norm $\Vert \cdot \Vert :\mathbb{V}\to \mathbb{R}$ given by

$$\Vert \mathbf{x}\Vert =\sqrt{⟨\mathbf{x},\mathbf{x}⟩}.$$

The norm induced by the inner product is known as the Euclidean norm.

There are several properties emerging from this definition.

1. Let $\mathbb{V}$ be a Euclidean space.

2. The field of scalars is $\mathbb{R}$.

3. Assume that $n=\dim \mathbb{V}$.

4. The inner product is a real inner product.

5. $\mathbb{V}$ is isomorphic to ${\mathbb{R}}^n$.

6. If we choose a basis $\mathcal{B}=\{{\mathbf{e}}_1,\dots ,{\mathbf{e}}_n\}$ for $\mathbb{V}$, then the coordinates for each vector $\mathbf{v}\in \mathbb{V}$ form an element of ${\mathbb{R}}^n$.

7. This forms a direct bijective mapping between $\mathbb{V}$ and ${\mathbb{R}}^n$.

8. $\Vert \mathbf{x}{\Vert }^2=⟨\mathbf{x},\mathbf{x}⟩$.

9. The Euclidean norm makes it a normed linear space.

10. Recall from Theorem 4.65 that a finite dimensional normed linear space is complete.

11. Thus, $\mathbb{V}$ is a Banach space.

12. $\mathbb{V}$ is an inner product space which is complete.

13. Hence $\mathbb{V}$ is also a Hilbert space.

14. ${\mathbb{R}}^n$ provides additional features like ${\ell }_p$ norms. Corresponding norms can be induced on $\mathbb{V}$ by a coordinate mapping.

4.7.5. Complex Coordinate Space

In this section we review important features of $n$-dimensional complex coordinate space ${\mathbb{C}}^n$ defined over a field of complex numbers.

Definition 4.100 (Complex coordinate space)

Let $\mathbb{C}$ denote the field of complex numbers. For any positive integer $n$, the set of all $n$-tuples of complex numbers forms an $n$-dimensional vector space over $\mathbb{C}$ which is denoted as ${\mathbb{C}}^n$ or $({\mathbb{C}}^n,\mathbb{C})$ and sometimes called complex coordinate space or “complex vector space*.

An element $\mathbf{x}$ in ${\mathbb{C}}^n$ is written as

$$\mathbf{x}=(x_1,x_2,\dots ,x_n),$$

where each $x_i$ is a complex number.

Vector space operations on ${\mathbb{C}}^n$ are defined by:

$$\begin{array}{rl}& \mathbf{x}+\mathbf{y}=(x_1+y_1,x_2+y_2,\dots ,x_n+y_n),\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{C}}^n.\\ & \alpha \mathbf{x}=(\alpha x_1,\alpha x_2,\dots ,\alpha x_n)\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n,\alpha \in \mathbb{C}.\end{array}$$

${\mathbb{C}}^n$ comes with the standard ordered basis $\mathcal{B}=\{{\mathbf{e}}_1,{\mathbf{e}}_2,\dots ,{\mathbf{e}}_n\}$:

(4.5)$$\begin{array}{rl}& {\mathbf{e}}_1=(1,0,\dots ,0),\\ & {\mathbf{e}}_2=(0,1,\dots ,0),\\ & ⋮\\ & {\mathbf{e}}_n=(0,0,\dots ,1).\end{array}$$

We note that the basis is same as the basis for $n$ dimensional real vector space (the Euclidean space).

An arbitrary vector $\mathbf{x}\in {\mathbb{C}}^n$ can be written as

$$\mathbf{x}=\sum _{i=1}^n{x}_i{\mathbf{e}}_i.$$

4.7.5.1. Sesquilinear Inner Product

Definition 4.101 (Standard inner product)

Standard inner product on ${\mathbb{C}}^n$ is defined as:

$$⟨\mathbf{x},\mathbf{y}⟩=\sum _{i=1}^n{x}_i\overline{y_i}=x_1\overline{y_1}+x_2\overline{y_2}+\cdots +x_n\overline{y_n}\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{C}}^n$$

where $\overline{y_i}$ denotes the complex conjugate. It is also known as the sesquilinear inner product.

This makes ${\mathbb{C}}^n$ an inner product space. This satisfies the inner product rule:

$$⟨\mathbf{x},\mathbf{y}⟩=\overline{⟨\mathbf{y},\mathbf{x}⟩}.$$

4.7.5.2. Standard Norm

Definition 4.102 (Norm)

The length of the vector (a.k.a. ${\ell }_2$ norm) is defined as:

$$\Vert \mathbf{x}\Vert =\sqrt{⟨\mathbf{x},\mathbf{x}⟩}=\sqrt{\sum _{i=1}^n{x}_i\overline{x_i}}=\sqrt{\sum _{i=1}^n|x_i{|}^2}\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n.$$

This makes ${\mathbb{C}}^n$ a normed linear space.

4.7.5.3. Standard Distance

Definition 4.103 (Distance)

The standard distance between two vectors is defined as:

$$d(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}\Vert =\sqrt{\sum _{i=1}^n|x_i-y_i{|}^2}.$$

This makes ${\mathbb{C}}^n$ a metric space. It reduces to the standard Euclidean distance between real vectors.

4.7.5.4. Norms

In addition to standard norm, we define a family of norms indexed by $p\in [1,\mathrm{\infty }]$ known as ${\ell }_p$ norms over ${\mathbb{C}}^n$.

Definition 4.104

${\ell }_p$ norm is defined as:

(4.6)$$\begin{array}{r}\Vert \mathbf{x}{\Vert }_p=\{\begin{array}{ll}{\left(\sum _{i=1}^n|x{|}_i^p\right)}^{\frac{1}{p}}& p\in [1,\mathrm{\infty })\\ \underset{1\le i\le n}{max}|x_i|& p=\mathrm{\infty }\end{array}\end{array}$$

We can see that:

$$\Vert \mathbf{x}\Vert =\Vert \mathbf{x}{\Vert }_2.$$

4.7.5.5. ${\ell }_1$ Norm

From the general definition of ${\ell }_p$ norms, we have

$$\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^n|x_i|=|x_1|+|x_2|+\cdots +|x_n|.$$

We use norms as a measure of strength of a signal or size of an error. Different norms signify different aspects of the signal.

4.7.5.6. Quasi-Norms

In some cases it is useful to extend the notion of ${\ell }_p$ norms to the case where $0<p<1$.

In such cases norm as defined in (4.6) doesn’t satisfy triangle inequality, hence it is not a proper norm function. We call such functions as quasi-norms.

4.7.5.7. ${\ell }_0$ “norm”

Of specific mention is ${\ell }_0$ “norm”. It isn’t even a quasi-norm. Note the use of quotes around the word norm to distinguish ${\ell }_0$ “norm” from usual norms.

Definition 4.105

The ${\ell }_0$ “norm” is defined as:

(4.7)$$\Vert \mathbf{x}{\Vert }_0=|\mathrm{supp}(\mathbf{x})|$$

where $\mathrm{supp}(\mathbf{x})=\{i|x_i\ne 0\}$ denotes the support of $\mathbf{x}$.

Note that $\Vert \mathbf{x}{\Vert }_0$ defined above doesn’t follow the definition in (4.6). Yet we can show that:

$$\underset{p\to 0}{lim}\Vert \mathbf{x}{\Vert }_p^p=|\mathrm{supp}(\mathbf{x})|$$

which justifies the notation.

4.7.6. ${\mathbb{C}}^n$ over $\mathbb{R}$

We next consider the real vector space of complex coordinates.

Definition 4.106 (Real vector space of complex coordinates)

For any positive integer $n$, the set of all $n$-tuples of complex numbers forms an $n$-dimensional vector space over $\mathbb{R}$ which is denoted as $({\mathbb{C}}^n,\mathbb{R})$

An element $\mathbf{x}$ in $({\mathbb{C}}^n,\mathbb{R})$ is written as

$$\mathbf{x}=(x_1,x_2,\dots ,x_n),$$

where each $x_i$ is a complex number.

Vector space operations on $({\mathbb{C}}^n,\mathbb{R})$ are defined by:

$$\begin{array}{rl}& \mathbf{x}+\mathbf{y}=(x_1+y_1,x_2+y_2,\dots ,x_n+y_n),\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{C}}^n.\\ & \alpha \mathbf{x}=(\alpha x_1,\alpha x_2,\dots ,\alpha x_n)\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n,\alpha \in \mathbb{R}.\end{array}$$

Theorem 4.118 (Standard basis and dimension)

The standard basis for $({\mathbb{C}}^n,\mathbb{R})$ is given by $\mathcal{B}=\{{\mathbf{e}}_1,{\mathbf{e}}_2,\dots ,{\mathbf{e}}_n,{\mathbf{e}}_{n+1},\dots ,{\mathbf{e}}_{2n}\}$:

(4.8)$$\begin{array}{rl}& {\mathbf{e}}_1=(1,0,\dots ,0),\\ & {\mathbf{e}}_2=(0,1,\dots ,0),\\ & ⋮\\ & {\mathbf{e}}_n=(0,0,\dots ,1),\\ & {\mathbf{e}}_{n+1}=(i,0,\dots ,0),\\ & {\mathbf{e}}_{n+2}=(0,i,\dots ,0),\\ & ⋮\\ & {\mathbf{e}}_{2n}=(0,0,\dots ,i).\end{array}$$

The dimension of $({\mathbb{C}}^n,\mathbb{R})$ is $2n$.

It is easy to see that $({\mathbb{C}}^n,\mathbb{R})$ is isomorphic to ${\mathbb{R}}^{2n}$.

4.7.6.1. Bilinear Inner Product

Definition 4.107 (Bilinear inner product)

The bilinear inner product on $({\mathbb{C}}^n,\mathbb{R})$ is defined as:

$$⟨\mathbf{x},\mathbf{y}{⟩}_B=\mathrm{Re}(⟨\mathbf{x},\mathbf{y}⟩)=\sum _{i=1}^n\mathrm{Re}(x_i\overline{y_i})=\sum _{i=1}^n\mathrm{Re}(x_i)\mathrm{Re}(y_i)+\mathrm{Im}(x_i)\mathrm{Im}(y_i)\mathrm{\forall }\mathbf{x},\mathbf{y}\in {\mathbb{C}}^n.$$

This inner product satisfies all the requirements of a real inner product (Definition 4.72) as shown in Example 4.25. This makes $({\mathbb{C}}^n,\mathbb{R})$ a real inner product space.

4.7.6.2. Standard Norm

Definition 4.108 (Norm on $({\mathbb{C}}^n,\mathbb{R})$)

The length of the vector (a.k.a. ${\ell }_2$ norm) is defined as:

$$\Vert \mathbf{x}\Vert =\sqrt{⟨\mathbf{x},\mathbf{x}{⟩}_B}=\sqrt{\sum _{i=1}^n\mathrm{Re}(x_i{)}^2+\mathrm{Im}(x_i{)}^2}=\sqrt{\sum _{i=1}^n|x_i{|}^2}\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^n.$$

This makes $({\mathbb{C}}^n,\mathbb{R})$ a normed linear space. We note that the definition of the norm for both $({\mathbb{C}}^n,\mathbb{R})$ and $({\mathbb{C}}^n,\mathbb{C})$ is identical.