198812 Session 1: Vector algebra

Math to code mapping.

Author

The purpose of the document it to show how mathematical conpects learned in the Computer Programming Prerequisites course could be implemented in a programming language. This supplementary material should help you to transfer theoretical concepts to programming. If you have programming skills you may use the material during the course. If not, just come back to it, once you are advanced enough in programming.

This document is basesd on the lecture notes by Sébastien Court. It structured in the same way as the lecture notes. It consists only of sections, where numeric examples were given.
It provides code in Python and R for examples used there. The code serves only demonstration purposes to show a possible implementation. We assumed the correctness of input data.
For multiple examples of the same calculation, only one is taken. You can easily adapt code for missing calculations.

For this session, code in basic Python, Python with NumPy package and in R is given. Vector and matrix algebra is relatively easy to implement using numpy (some courses from module 3) or R (198803). In most of the cases just by calling dedicated functions. In basic Python (198801), the required functionality in many cases must be implemented from scratch.

Vectors in R

Detailed description on how to work with vectors in R is provided in our textbook.

1 Definitions and basic operations

1.1 Definitions

Defining example vectors v (a column vector) and w (a row vector).

v = (1, 6, 0, 3)

w = (3, 1, 4, 8, 2)

We define them as lists.

v = [1, 6, 0, 3]
w = [3, 1, 4, 8, 2]

Orientation: column/vector.

For simplicity, we will ignore the orientation. It would be possible to define the column vector as a list of single-element lists.

[[1], [6], [0], [3]]

[[1], [6], [0], [3]]

If we use numpy, we define them as arrays.

import numpy 
 
V = numpy.array([3, 1, 4, 8, 2])
W = numpy.array([1, 6, 0, 3])

Orientation: column/vector.

Let us analyse vector V, which is an one-dimensional array. We will use list v to initialise it.

V = numpy.array(v)     # one-dimensional array

V = [1 6 0 3]   shape = (4,)

If we want to have row and column vectors, we have to use a list of lists. We will get a two-dimensional array with one row only.

V = numpy.array([v])   # two-dimensional array, a row

V = [[1 6 0 3]]     shape = (1, 4)

It should actually be a column vector, so we may use transposition. Now, it is a two-dimensional array with one column only.

V = numpy.array([v]).T # two-dimensional array, a column

V = [[1]
 [6]
 [0]
 [3]]   shape = (4, 1)

We define them as vectors.

v <- c(1, 6, 0, 3)    
w <- c(3, 1, 4, 8, 2)

Orientation: column/vector.

We may use the t() function to switch between a column and a row.

w <- t(w)

     [,1] [,2] [,3] [,4] [,5]
[1,]    3    1    4    8    2

     [,1]
[1,]    3
[2,]    1
[3,]    4
[4,]    8
[5,]    2

1.2 Basic operations

* Multiplication by scalar

3 * v = 3 * (1, 6, 0, 3) = (3, 18, 0, 9)

We have to define a for-loop to create a new list with results.

result = []
for n in v:
    result.append(3*n)
print(result)

[3, 18, 0, 9]

Compact syntax

Alternatively, we may use a list comprehension.

[3*n for n in v]

[3, 18, 0, 9]

Do not use *

Let us try to just use the multiplication operator *.

3*v

[1, 6, 0, 3, 1, 6, 0, 3, 1, 6, 0, 3]

As you can see, using * on number and the list is resulting in a series of list concatenations. This is wrong!

Simplified syntax

For simplification, whenever possible, assignments and print statements are skipped.

For example, instead of

result = 3*v
print(result)

[1, 6, 0, 3, 1, 6, 0, 3, 1, 6, 0, 3]

we will just use

3*v

[1, 6, 0, 3, 1, 6, 0, 3, 1, 6, 0, 3]

We may use the multiplication operator *.

3*V

array([[ 3],
       [18],
       [ 0],
       [ 9]])

We may use the multiplication operator *.

3*v

[1]  3 18  0  9

* Sum of two vectors

v + w = (3, 2, 7, 9) + (1, 4, 2, 12) = (4, 6, 9, 21)

We have to use a for-loop.

number_of_elements = len(v)
result = []
for i in range(number_of_elements):
    result.append(v[i] + w[i])
print(result)

[4, 6, 9, 21]

Compact syntax

Alternatively, we may use a list comprehension and the zip() function.

[vv + ww for vv, ww in zip(v, w)]

[4, 6, 9, 21]

We may use the addition operator + or the numpy.add() function.

V + W

array([ 4,  6,  9, 21])

numpy.add(V, W)

array([ 4,  6,  9, 21])

We may use the addition operator +.

v + w

[1]  4  6  9 21

* The subtraction

Let us subtract the same, two vectors, v and w.

v - w = (3, 2, 7, 9) - (1, 4, 2, 12) = (2, -2, 5, -3)

We have to use a for-loop.

number_of_elements = len(v)
result = []
for i in range(number_of_elements):
    result.append(v[i] - w[i])
print(result)

[2, -2, 5, -3]

We may use the subtraction operator - or the subtract() function.

V - W

array([ 2, -2,  5, -3])

numpy.subtract(V, W)

array([ 2, -2,  5, -3])

We may use the subtraction operator -.

v - w

[1]  2 -2  5 -3

* Componentwise product of two vectors

For the same two vectors, we will get.

v * w = (3, 2, 7, 9) * (1, 4, 2, 12) = (3, 8, 14, 108)

We have to use a for-loop.

number_of_elements = len(v)
result = []
for i in range(number_of_elements):
    result.append(v[i] * w[i])
print(result)

[3, 8, 14, 108]

We may use the multiplication operator * or the numpy.multiply() function.

V * W

array([  3,   8,  14, 108])

numpy.multiply(V, W)

array([  3,   8,  14, 108])

We may use the multiplication operator *.

v * w

[1]   3   8  14 108

2 Subsetting and notation

2.1 When numbering starts at 0

The convention of indexing is notation/language-dependent.

Numbering starts from 1.

v = (1, 6, 0, 6)

For v, we have the following indices.

1, 2, 3, 4

For example, the first element we get with v[1] and obtain 1. In general, we have

v[1] = 1
v[2] = 6
v[3] = 0
v[4] = 6

Numbering starts from 0.

v = [1, 6, 0, 6]

For v, we have the following indices.

0, 1, 2, 3

We may also count backward with negative indices.

-4, -3, -2, -1

Thus, we may access elements as follows.

v[0] = v[-4] = 1
v[1] = v[-3] = 6
v[2] = v[-2] = 0
v[3] = v[-1] = 6

For arrays, it is just analogues as for lists (see the previous tab).

We may access elements as follows.

V[0] = V[-4] = 1
V[1] = V[-3] = 6
V[2] = V[-2] = 0
V[3] = V[-1] = 6

Numbering starts from 1, like in math.

v <- c( 1, 6, 0, 6 )

For v, we have the following indices.

1, 2, 3, 4

We may access elements as follows.

v[1] = 1
v[2] = 6
v[3] = 0
v[4] = 6

2.2 Subsetting several elements

We may pick up several elements using indices.

w          = (3, 1, 4, 8, 2)

w[1:3]     = (3, 1, 4)

w[(1,3,5)] = [3, 4, 2]

For our list

[3, 1, 4, 8, 2]

we may use slicing.

w[0:3] # for indices 0, 1, 2

[3, 1, 4]

To select a discontinuous list the elements from the original list, we need to construct a new list explicitly.

[w[0], w[2], w[4]]

[3, 4, 2]

For our array

array([3, 1, 4, 8, 2])

we may use slicing.

W[0:3] # for indices 0, 1, 2

array([3, 1, 4])

We may also select a discontinuous list of the elements from the original array.

W[[0, 2, 4]]

array([3, 4, 2])

For our vector

[1] 3 1 4 8 2

we may use slicing.

w[1:3] # for indices 1, 2, 3

[1] 3 1 4

We may also select a discontinuous list of the elements from the original vector.

w[c(1, 3, 5)]

[1] 3 4 2

Negative indices might be used to exclude elements.

w[-1]          # all but the first

[1] 1 4 8 2

w[-c(1, 3, 5)] # all but listed

[1] 1 8

2.3 Notation of summation

We may sum all elements of a vector.

v = (1, 6, 0, 6)

sum(v) = 13

We may use the built-in sum() function.

sum(v)

We may use the numpy.sum() function or just built-in sum() function.

numpy.sum(V)

sum(V)

We may use the built-in sum() function.

sum(v)

[1] 13

3 Scalar product and norm

3.1 The scalar product

We may calculate the scalar product of two vectors.

v · w   = (-2, 6, 9, 2) · (4, -1, 3, 7) =
        = (-2) x 4 + 6 x (-1) + 9 x 3 + 2 x 7 =
        = 27

We need to use a for-loop.

number_of_elements = len(v)
result = 0
for i in range(number_of_elements):
    result = result + v[i] * w[i]
result

We have the dot() function.

numpy.dot(V, W)

Alternatively, we may use multiplication and summation.

numpy.sum(V*W)

We use %*% operator.

v %*% w

     [,1]
[1,]   27

3.2 The Euclidean norm

Let us calculate the Euclidean norm for the following vector.

norm(v) = norm((1, 2)) =
        = sqrt(1^2 + 2^2) =
        = sqrt(5) =
        = 2.23606797749979

We have to use a for-loop.

result = 0
for n in v:
    result = result + n**2
result ** 0.5

2.23606797749979

We use the norm() function from numpy.linalg subpackage.

numpy.linalg.norm(V)

2.23606797749979

Default value of a parameter

The ord has a default value equal to 2. This is why without this parameter, we got the Euclidean distance. This is equivalent to using ord explicitly.

numpy.linalg.norm(V, ord=2)

2.23606797749979

We have to use the sqrt() (square root) function and the sum() function.

sqrt(sum(v^2))

[1] 2.236068

3.3 Other norms

The p values and meaning of the norms.

p = 0 for the number of non-zero components.
p = 1 for the sum of absolute values.
p = 2 for the Euclidean distance (earlier example).
p = infinity for the maximal absolute value.

We would need to use for-loops, but let us calculate different norms using list comprehension to make the code shorter.

sum([n > 0 for n in v])     # p = 0

sum([abs(n) for n in v])    # p = 1

max([abs(n) for n in v])    # p = infinity

The other norms may be calculated using different values for p. The numpy.linalg.norm() function has a named parameter ord - order of the norm (p).

numpy.linalg.norm(V, ord=0)

2.0

numpy.linalg.norm(V, ord=1)

3.0

numpy.linalg.norm(V, ord=numpy.Inf)

2.0

We use the built-in sum(), abs(), and max() function.

sum(v > 0)     # p = 0

[1] 2

sum(abs(v))    # p = 1

[1] 3

max(abs(v))    # p = infinity

[1] 2

5 Geometric aspects

5.3 Determining the position of a point with respect to a straight line

Given are three points.

A = (0, 1)

B = (0, 4)

M = (-2, 1)

The task is to determine on which side the point M is located, with respect to this directed by the vector v = AB.

We calculate (geometrical) vectors AB and AM.

ab = [b[i] - a[i] for i in range(len(a))]; ab

[0, 3]

am = [m[i] - a[i] for i in range(len(a))]; am

[-2, 0]

Next, we calculate their 2D cross product.

p = ab[0] * am[1] - ab[1] * am[0]; p

The final step is to determine the sign.

sign = 0
if p > 0:
    sign = 1
elif p < 0:
    sign = -1 
sign

For the last step, optionally, we may use the copysign() function from the math package.

import math
 
math.copysign(1, p)

1.0

We calculate (geometrical) vectors AB and AM.

AB = B - A; AB

array([0, 3])

AM = M - A; AM

array([-2,  0])

Next, we determine the sign of their cross product.

numpy.sign(numpy.cross(AB, AM))

We calculate (geometrical) vectors AB and AM.

AB = B - A; AB

     [,1] [,2]
[1,]    0    3

AM = M - A; AM

     [,1] [,2]
[1,]   -2    0

Next, we determine the sign of their cross product.

sign(crossprod(AB, AM))

     [,1] [,2]
[1,]    0    0
[2,]   -1    0