Basic Operations

Vector Equality

Let $x \isin \mathbb{R}^{n}$ ​and $y \isin \mathbb{R}^{n}$ ​with:

$$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 = y$, if and only if:

$$x_0 = y_0; \\ x_1 = y_1; \\ ... \\ x_{n-1} = y_{n-1};$$

That is, the corresponding elements of $x$​ and $y$​ are equal.

Vector Addition

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

$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 $x \isin \mathbb{R}^{n}$ and $y \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 + y$. If lay the vectors "heel to toe" , e.g. if we lay vector $y$ 's heel (where $y$ starts) to toe of $x$ (where $x$ ends), $x + y$ can be given by going from heel of $x$ to toe of $y$. Vice-versa is also true.

Another geometric interpretation is, if we lay $y$​'s heel to toe of $x$ or we lay $x$'s heel to toe of $y$, this would create a parallelogram. The result of $x + 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 $x \isin \mathbb{R}^{n}$​ and $\alpha \isin \mathbb{R}$​. Then, vector scaling is given by:

$$\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 $x \isin \mathbb{R}^n$ and ​$y \isin \mathbb{R}^n$​. Then, vector subtraction can be given by:

$$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 $y$​ means it points in the opposite direction. Now, we have two vectors $x$​ and $-y$ that are heel to toe. $x - y$​ can be given by going from heel of $x$​ to toe of $-y$​.

Same as for Vector Addition, the parallelogram method can be applied here as well. $x - 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 $x \isin \mathbb{R}^n$​ and $y \isin \mathbb{R}^n$​)computes to:

$$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 := \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 $x$ and one element from $y$​, we need to read these elements and write the result back to $y$. That means 2 memops for reading, 1 more for writing.

Finally, for each pair of elements from $x$ and $y$, 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+1$memops and $2n$​ 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(\alpha, \beta) = \begin{pmatrix} \alpha + \beta \\ \alpha - \beta \end{pmatrix}$$

Another example can be,

$$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: \mathbb{R}^n \rightarrow \mathbb{R}^m$$

For example,

$$f\begin{pmatrix} \alpha \\ \beta \end{pmatrix} = \begin{pmatrix} \alpha + \beta \\ \alpha - \beta \end{pmatrix}$$

Another example can be,

$$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:\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(\lambda x) = \lambda f(x)$happens sometimes.
• $f:\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)$ happens sometimes.

Matrix Product

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

$$C = 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 = 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:

$$\vec{a}.\vec{b} = \alpha = a^Tb = b^Ta \\ \alpha := \sum_ia_ib_i$$

Alternatively,

$$\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 $n$ is $2n$ memops and $2n$​ flops.

​Transpose

The transpose of a matrix A is given by:

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

​Inverse

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

$$I = A^{-1}A = AA^{-1}$$

Not all square matrices have an inverse​.

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