Vector Properties

Linear Combination

For a set of vectors { $v^{(1)}, v^{(2)},..., v^{(n)}$} and a set of scalars {$\alpha_{1}, \alpha_{2}, ... , \alpha_{n}$}, where $v^i \isin \mathbb{R}^m$ and $\alpha_{i} \isin \mathbb{A}$ , linear combination is given by:

$$\sum_i\alpha_iv^{(i)},\hspace{1cm}\alpha_i \hspace{0.1cm} is \hspace{0.1cm} scalar \\ = \alpha_1v^{1}+\alpha_2v^{2}+...+ \alpha_nv^{n}$$

​For example

$$v_3 = v_1+2v_2 \\ => v_3 = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 1\\ 2 \end{bmatrix}$$

Matrix multiplications can be interpreted in terms of linear combinations of columns. For example,

$$v = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \hspace{1cm} A = \begin{bmatrix} 1 & 3\\ 2 & 4 \end{bmatrix} \\ v \times A = \begin{bmatrix} v_1+2v_2 & 3v_1+4v_2 \end{bmatrix}$$

Cost

An AXPY opeartion is a linear combination:

$$w := \alpha_1v^1 + \alpha_2v^2 + ... + \alpha_nv^n$$

We note that the linear combination can implemented as $n$​ AXPY operations. This suggests that the cost is $n$ times the cost of an AXPY operation with vectors of size $m$​: $n \times 2m = 2mn$ flops and approximately $n \times 3m = 3mn$ memops.

However, one can actually do better. The vector $w$ in the above equation is updated repeatedly. If this vector stays in the L1 cache of a computer, then it need not be repeatedly loaded from memory, and the cost becomes $m$ memops (to load $w$into cache), and then for each AXPY operation approximately $m$ memops (to read $v^j$, ignoring the cost of reading $\alpha_j$). Then, once $w$ has been completely updated, it can be written back to memory. So, the total cost related to accessing memory becomes $m + n \times m + m = (n + 2)m \approx mn$ memops.

Linear Combination of Unit Basis Vector

Given any $x \isin \mathbb{R}^n$, this vector can always be written as the linear combination of the unit basis vectors.

$$x = \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \end{pmatrix}$$

Then,

$$x = \begin{pmatrix} x_0 \\ x_1 \\ ... \\ x_{n-1} \end{pmatrix} = x_0 \begin{pmatrix} 1 \\ 0 \\ ... \\ 0 \end{pmatrix} + x_1 \begin{pmatrix} 0 \\ 1 \\ ... \\ 0 \end{pmatrix} + ... + x_{n-1} \begin{pmatrix} 0 \\ 0 \\ ... \\ 1 \end{pmatrix} \\ = x_0e_0 + x_1e_1 + ... + x_{n-1}e_{n-1} = \sum^{n-1}_{i=0} x_ie_i$$

Slicing & Dicing: AXPY Operation

Let $\alpha \isin \mathbb{R}$ and $x, y \isin \mathbb{R}^n$. We partition (slice & dice) these vectors as:

$$x = \begin{pmatrix} x_0 \\ \hline \\ x_1 \\ \hline \\ ... \\ \hline \\ x_{N-1} \end{pmatrix}, y = \begin{pmatrix} y_0 \\ \hline \\ y_1 \\ \hline \\ ... \\ \hline \\ y_{N-1} \end{pmatrix}$$

Then,

$$\alpha x + y = \alpha \begin{pmatrix} x_0 \\ \hline \\ x_1 \\ \hline \\ ... \\ \hline \\ x_{N-1} \end{pmatrix} + \begin{pmatrix} y_0 \\ \hline \\ y_1 \\ \hline \\ ... \\ \hline \\ y_{N-1} \end{pmatrix} = \begin{pmatrix} \alpha x_0 + y_0 \\ \hline \\ \alpha x_1 + y_1 \\ \hline \\ ... \\ \hline \\ \alpha x_{N-1} + y_{N-1} \\ \end{pmatrix}$$

Algorithm: AXPY Operation

Following details the algorithm for AXPY operation using slicing & dicing:

$$Partition \hspace{1.5mm} x \rightarrow \begin{pmatrix} x_T \\ \hline \\ x_B \end{pmatrix}, y \rightarrow \begin{pmatrix} y_T \\ \hline \\ y_B \end{pmatrix} \\ where \hspace{1.5mm} x_T \hspace{1.5mm} and \hspace{1.5mm} y_T \hspace{1.5mm} have \hspace{1.5mm} 0 \hspace{1.5mm} elements \\ while \hspace{1.5mm} m(x_T) < m(x) \hspace{1.5mm} do \\ Repartition \\ \begin{pmatrix} x_T \\ \cdots \\ x_B \end{pmatrix} \rightarrow \begin{pmatrix} x_0 \\ \cdots \\ \chi_1 \\ \hline \\ x_2 \end{pmatrix}, \begin{pmatrix} y_T\\ \cdots \\ y_B \end{pmatrix} \rightarrow \begin{pmatrix} y_0\\ \cdots \\ \psi_1 \\ \hline \\ y_2 \end{pmatrix} \\ \psi_1 := \alpha \chi_1 + \psi_1 \\ Continue \hspace{1.5mm} with \\ \begin{pmatrix} x_T \\ \cdots \\ x_B \end{pmatrix} \leftarrow \begin{pmatrix} x_0\\ \hline \\ \chi_1 \\ \cdots \\ x_2 \end{pmatrix} , \begin{pmatrix} y_T \\ \cdots \\ y_B \end{pmatrix} \leftarrow \begin{pmatrix} y_0 \\ \hline \\ \psi_1 \\ \cdots \\ y_2 \end{pmatrix} \\ end \hspace{1.5mm} while$$

Summary

A linear combination of vectors scales the individual vectors and then adds them. Linear combinations are foundational to linear algebra.

​Span

Span of a set of vectors is the set of all vectors obtainable by a linear combination of the original vectors. For example, for $v_1 = (1, 0)\hspace{0.1cm}\&\hspace{0.1cm} v_2 = (0, 1)$, span is given by $\alpha_1v_1+\alpha_2v_2$​.

The span of all the columns of a matrix is called the columns space. For example,

$$\begin{bmatrix} 1 & 2\\ 2 & 0\\ 3 & 3 \end{bmatrix} \longrightarrow \alpha_1(1,2,3) + \alpha_2(2,0,3)$$

​Further, note that, for the equation $Ax = b$​ has a solution only if b lies in the columns space of A.

Linear Independence

A set of vectors is linearly independent if none of these vectors can be written as a linear combination of the other vectors.

For example,

• $v_1=(1,0), v_2 = (0,1)$​ are linearly independent.

• $v_1 = (1,0), v_2 = (0, 1), v_3 = (3, 4)$ are linearly dependent as $v_3=3v_1+4v_2$.

Mathematically, $S = \begin{Bmatrix} v_1, v_2,..., v_n \end{Bmatrix}$​is linearly independent if for the following linear combination:

$$\alpha_1v_1+\alpha_2v_2+...+\alpha_kv_k = 0$$

​which means that all the $\alpha_i = 0$​.