Vector norm and distance between vectors

When you handle arrays of numerical data, you often need to be able to describe them in terms of their magnitude. In this topic, you will define the concept of norm and see how it relates to the concept of metric, measuring distances, and magnitudes.

Norm

At first, let's focus on vectors on the plane and facts you already know.

Given the vector $\vec{v}=(a,b)$ :

You know that you can use the Pythagorean theorem to determine its length:

$|\vec{v}| = \sqrt{a^2 + b^2}$

For any vector, norm is equal to its length and is denoted by double bars. So, for our vector $\vec{v} = (a, b)^T$:

$\|\vec{v}\| = |\vec{v}|=\sqrt{a^2+b^2}$

There's also a more general definition of the norm as a function that maps a vector of real (or complex) numbers to one non-negative real number. Here's an illustration of this definition of our vector $\vec{v}$.

Can any function be a norm? For sure, not! A function is considered a norm if and only if it satisfies the following properties:

1. Zero only for zero vector: The only vector that has a norm of zero is the zero vector itself. In other words, if the length of a vector is zero, that means it's not pointing anywhere – it's just a point.

2. Scalar multiplication: If you stretch or shrink a vector by a factor, the norm changes by the same factor. So if you have a vector of length $3$ and you double it, the new vector has a length of $6$. Mathematically, you can write it as $\|k \cdot \vec{u}\| = |k| \cdot \|\vec{u}\|$, where $k$ is a scalar and $\vec{u}$ is a vector.

3. Triangle inequality: This property says that the length of one vector plus the length of another vector is always greater than or equal to the length of the vector that you get when you add the two together. This is just like the rule in geometry that says that in any triangle, the length of one side plus the length of another side is always greater than or equal to the length of the third side. Mathematically, you can write it as $\|\vec{u}+\vec{v}\| \leq \|\vec{u}\|+\|\vec{v}\|$, where $\vec{u}, \vec{v}$ are two different vectors.

Different norms

The ancient Greeks were able to formally describe the Euclidean norm by observing the relationship between squares constructed on the sides of a right triangle. They arrived at the idea that the length of the line segment between two points corresponds to the Euclidean distance between them.

You've already used this norm in the previous paragraph for the vector $\vec{v}$ on a plane. If you have a vector in a three-dimensional space, it's still quite easy to understand, how to calculate the norm using the Pythagorean theorem. But what happens if you have vectors in four or even ten-dimensional space? Surprisingly enough, you can still use the Pythagorean theorem, but you'll have to add more squares of vector coordinates.

For an $n$-dimensional space, the Euclidean norm of a vector $\vec{x}=(x_1,x_2,\dotsc,x_n)$ is equal to:

$\|\vec{x}\| = \sqrt{x_1^2 + x_2^2 + x_3^2+\cdots+x_n^2}$

Let's consider an example. Imagine that you have a vector $\vec{x}=(1,2,3,4,0,5)$ in a six-dimensional space. Its Euclidean norm is equal to:

$\|\vec{x}\| = \sqrt{1^2 + 2^2 + 3^2+4^2+0^2+5^2}=\sqrt{1+4+9+16+0+25}=\sqrt{55}\approx7.416$

However, there are times when constraints force us to find new ways to define distances. Picture a city with a rectangular grid, like Manhattan in NYC. Imagine there is a huge skyscraper taking up the entire block on either side. Here, if you tried to find the shortest route between streets using the Euclidean distance, you'd have to go through the skyscraper's walls!

Enter the Manhattan norm: if you measure the distance between two points as the sum of the distances between their coordinates instead, you can find the shortest possible route without running into any walls.

This definition of distance gave way to its own form of geometry – Taxicab geometry.

Formally, the Manhattan norm of a vector $\vec{x}=(x_1,x_2,\dotsc,x_n)$ is defined as:

$\|\vec{x}\|_1 = |x_1| + |x_2| + |x_3|+\cdots+|x_n|$

Let's consider an example. Imagine that you are at the point $(-4,-2)$ and you would like to go to the café at the point $(3,2)$. The shortest route, according to the Manhattan norm, is equal to $|3-(-4)|+|2-(-2)|=7+4=11$.

There's also another type of norm called p-norm. It is defined as:

$\|\vec{x}\|_p = (|x_1|^p + |x_2|^p + |x_3|^p+\cdots+|x_n|^p)^{1/p} \qquad \text{for any } p$

As you can see, we get the Euclidean norm if $p=2$. So, this norm is also referred to as 2-norm. The subscript for it is usually omitted. When $p=1$ you have the Manhattan norm, which we've just discussed.

Mighty metrics

You can use a given norm to define a metric. A metric is a function that maps two elements of a set (like two vectors, for example) to the distance between them.

For a given norm and two vectors $\vec{u}$ and $\vec{v}$, you can define a distance function, or metric, as follows:

$d(\vec{u},\vec{v}) = \|\vec{u} - \vec{v}\|$

Let's consider two points on the plane, $p$ and $q$, with their corresponding point vectors $\vec{p}$ and $\vec{q}$:

You can determine the distance between the two vectors by subtracting one vector from the other and computing the norm of the resulting vector:

A metric must satisfy the following properties:

1. Identity of indiscernibles: The distance between two points is zero if and only if the points are the same. In other words, if two objects are exactly the same, their distance apart is zero. Formally, it can be written as $d(x,y)=0\Leftrightarrow x=y$

2. Symmetry: The distance between point $x$ and point $y$ is the same as the distance between point $y$ and point $x$. This property reflects the idea that the distance between two points doesn't depend on the order in which you consider them. Formally, it can be written as $d(x,y)=d(y,x)$

3. Triangle inequality: If you have three points $x,y$ and $z$, the distance between $x$ and $y$ is always less than or equal to the sum of the distances between $x$ and $z$, and between $z$ and $y$. This property captures the idea that the shortest path between two points is a straight line, or at least not longer than any detour you might take. Formally, you can write it as $d(x,y)\leq d(x,z)+d(z,y)$

Conclusion

In this topic, you have learned that:

• A norm is a function that maps a vector to a non-negative real number

• A norm must satisfy three properties: zero only for zero vector, scalar multiplication, and triangle inequality.

• When you measure distances using the Pythagorean theorem, you are talking about the Euclidean norm.

• When you measure the distance between two points as the sum of the distances between their coordinates, you are talking about the Manhattan norm.

• You can use different types of norms to define metrics.

• All metrics have to satisfy three properties: identity of indiscernibles, symmetry and triangle inequality.