> For the complete documentation index, see [llms.txt](https://amanalok.gitbook.io/linear-algebra/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://amanalok.gitbook.io/linear-algebra/vector-properties.md).

# 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$$​.