Page cover

Basic Operations

Vector Equality

Let xRnx \isin \mathbb{R}^{n} ​and yRny \isin \mathbb{R}^{n} ​with:

x=(x0x1...xn1),y=(y0y1...yn1)x = \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \end{pmatrix}, y = \begin{pmatrix} y_0 \\ y_1 \\ ... \\ y_{n-1} \end{pmatrix}

Then x=yx = y, if and only if:

x0=y0;x1=y1;...xn1=yn1;x_0 = y_0; \\ x_1 = y_1; \\ ... \\ x_{n-1} = y_{n-1};

That is, the corresponding elements of xx​ and yy​ are equal.

Vector Addition

Vector addition x+yx+y (sum of vectors) is defined by:

x+y=(x0x1...xn1)+(y0y1...yn1)=(x0+y0x1+y1...xn1+yn1)x+y = \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \\ \end{pmatrix} + \begin{pmatrix} y_0 \\ y_1 \\ ... \\ y_{n-1} \\ \end{pmatrix} = \begin{pmatrix} x_0 + y_0 \\ x_1 + y_1 \\ ... \\ x_{n-1} + y_{n-1} \end{pmatrix}

In other words, the vectors are added element-wise, yielding a new vector of the same size.

Geometric Interpretation

In this interpretation, let xRnx \isin \mathbb{R}^{n} and yRny \isin \mathbb{R}^{n}. These 2 vectors actually lie in a plane and if we view them in that plane, we can observe the result of doing x+yx + y. If lay the vectors "heel to toe" , e.g. if we lay vector yy 's heel (where yy starts) to toe of xx (where xx ends), x+yx + y can be given by going from heel of xx to toe of yy. Vice-versa is also true.

Another geometric interpretation is, if we lay yy​'s heel to toe of xx or we lay xx's heel to toe of yy, this would create a parallelogram. The result of x+yx + y​is given by the diagonal of the parallelogram. This is known as the parallelogram method.

Vector Scaling

Scaling a vector is same as stretching the vector. Let xRnx \isin \mathbb{R}^{n}​ and αR\alpha \isin \mathbb{R}​. Then, vector scaling is given by:

αx=α(x0x1...xn1)=(αx0αx1...αxn1)\alpha x = \alpha \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \end{pmatrix} = \begin{pmatrix} \alpha x_0 \\ \alpha x_1 \\ ... \\ \alpha x_{n-1} \\ \end{pmatrix}

Vector Subtraction

Let xRnx \isin \mathbb{R}^n and ​yRny \isin \mathbb{R}^n​. Then, vector subtraction can be given by:

xy=x+(y)=(x0x1...xn1)(y0y1...yn1)=(x0y0x1y1...xn1yn1)x - y = x + (-y) = \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \\ \end{pmatrix} - \begin{pmatrix} y_0 \\ y_1 \\ ... \\ y_{n-1} \\ \end{pmatrix} = \begin{pmatrix} x_0 - y_0 \\ x_1 - y_1 \\ ... \\ x_{n-1} - y_{n-1} \\ \end{pmatrix}

Geometric Interpretation

Taking the negative of yy​ means it points in the opposite direction. Now, we have two vectors xx​ and y-y that are heel to toe. xyx - y​ can be given by going from heel of xx​ to toe of y-y​.

Same as for Vector Addition, the parallelogram method can be applied here as well. xyx - y​ is the other diagonal of the parallelogram.

Scaled Vector Addition

One of the most commonly encountered operations when implementing more complex linear algebra operations is the scaled vector addition, which (given xRnx \isin \mathbb{R}^n​ and yRny \isin \mathbb{R}^n​)computes to:

y:=αx+y=α(x0x1...xn1)+(y0y1...yn1)=(αx0+y0αx1+y1...αxn1+yn1)y := \alpha x + y = \alpha \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \\ \end{pmatrix} + \begin{pmatrix} y_0 \\ y_1 \\ ... \\ y_{n-1} \\ \end{pmatrix} = \begin{pmatrix} \alpha x_0 + y_0 \\ \alpha x_1 + y_1 \\ ... \\ \alpha x_{n-1} + y_{n-1} \\ \end{pmatrix}

It is often referred to as the AXPY operation, which stands for alpha times x plus y. We emphasize that it is typically used in situations where the output vector overwrites the input vector y.

Counting Flops & Memops

Consider the following scaled vector addition:

y:=αx+y=2(123)+(121)y := \alpha x + y \\ = 2 \begin{pmatrix} 1 \\ -2 \\ 3 \end{pmatrix} + \begin{pmatrix} -1 \\ 2 \\ 1 \end{pmatrix}

Now, imagine all the data for this scaled vector addition starts by being stored in the main memory of a computer. Further, in order to compute, data must be brought into registers and there are only a few registers available.

Now, we know that the scaling factor 2 in the above example is going to be used many times. So, we store it in a register and keep it there during the entire computation. This costs us 1 memory operation (memops).

Further, for each pair of one element from xx and one element from yy​, we need to read these elements and write the result back to yy. That means 2 memops for reading, 1 more for writing.

Finally, for each pair of elements from xx and yy, we perform a multiplication and then an addition. That would be 2 floating point operations (flops).

Now, if the size of the vectors is n, then we would have to do 3n+13n+1memops and 2n2n​ flops.

Vector Function

A vector (valued) function is a mathematical function of one or more scalars and/or vectors whose output is a vector.

For example,

f(α,β)=(α+βαβ)f(\alpha, \beta) = \begin{pmatrix} \alpha + \beta \\ \alpha - \beta \end{pmatrix}

Another example can be,

f(α,(χ0χ1χ2))=(χ0+αχ1+αχ2+α)f(\alpha, \begin{pmatrix} \chi_0 \\ \chi_1 \\ \chi_2 \end{pmatrix}) = \begin{pmatrix} \chi_0 + \alpha \\ \chi_1 + \alpha \\ \chi_2 + \alpha \\ \end{pmatrix}

The AXPY and DOT operations are also examples of vector functions.

Vector Functions That Map a Vector to a Vector

We will now focus on vector functions as functions that map a vector to another vector:

f:RnRmf: \mathbb{R}^n \rightarrow \mathbb{R}^m

For example,

f(αβ)=(α+βαβ)f\begin{pmatrix} \alpha \\ \beta \end{pmatrix} = \begin{pmatrix} \alpha + \beta \\ \alpha - \beta \end{pmatrix}

Another example can be,

f(α(χ0χ1χ2))=g(αχ0χ1χ2)=(χ0+αχ1+αχ2+α)f\begin{pmatrix} \alpha \\ \begin{pmatrix} \chi_0 \\ \chi_1 \\ \chi_2 \end{pmatrix} \end{pmatrix} = g \begin{pmatrix} \alpha \\ \chi_0 \\ \chi_1 \\ \chi_2 \end{pmatrix} = \begin{pmatrix} \chi_0 + \alpha \\ \chi_1 + \alpha \\ \chi_2 + \alpha \end{pmatrix}

Do note the following:

  • f:RnRm,λRandxRnf:\mathbb{R}^n \rightarrow \mathbb{R}^m, \lambda \isin \mathbb{R} \hspace{1.5mm} and \hspace{1.5mm} x \isin \mathbb{R}^n, then f(λx)=λf(x)f(\lambda x) = \lambda f(x)happens sometimes.

  • f:RnRmandx,yRnf:\mathbb{R}^n \rightarrow \mathbb{R}^m \hspace{1.5mm} and \hspace{1.5mm} x,y \isin \mathbb{R}^n, then f(x+y)=f(x)+f(y)f(x+y) = f(x) + f(y) happens sometimes.

Matrix Product

For given matrices A and B, their product is given by:

C=A×BCij=kAikBkjC = A \times B \\ C_{ij} = \sum_k A_{ik}B_{kj}

​Hadamard Product

Hadamard product is element-wise multiplication. Following equations provide details of how the this product operation is calculated for given matrices A and B:

C=ABCij=AijBijC = A \odot B \\ C_{ij} = A_{ij}B_{ij}

​Dot (Inner) Product

The dot (inner) product between two vectors a and b is given by:

a.b=α=aTb=bTaα:=iaibi\vec{a}.\vec{b} = \alpha = a^Tb = b^Ta \\ \alpha := \sum_ia_ib_i

Alternatively,

α:=(((0+a0b0)+a1b1)+...)+an1bn1\alpha : = (((0 + a_0b_0) + a_1b_1) + ...) + a_{n-1}b_{n-1}

Cost

The cost of a dot product with vectors of size nn is 2n2n memops and 2n2n​ flops.

​Transpose

The transpose of a matrix A is given by:

B=ATBji=AijB = A^T \\ B_{ji} = A_{ij}

​Inverse

The following equation provides the deifnition of inverse of a matrix:

I=A1A=AA1I = A^{-1}A = AA^{-1}

Not all square matrices have an inverse​.

For such cases, and non-square matrices, "pseudoinverse" is defined.

Last updated