Applied Linear Algebra

In this lesson we are going to define the concept of a basis and see how vectors can be represented by coordinates in such a bases.

We are also going to study how to transform a representation from one basis to another. But first the notions of

Linear Combination, Linear Independence and Linear Dependence

Linear Combination

A vector $\mathbf{v}$ is said to be a linear combination of vectors $\mathbf{v}_1,\mathbf{v}_2 \dots ,\mathbf{v}_n$ if for some scalars $c_1,c_2 \dots ,c_n$

$$\mathbf{v}=c_1\mathbf{v}_1+c_2\mathbf{v}_2 \dots +c_n\mathbf{v}_n$$

Linear Independence

Let $V$ be a vector space. A subset $U\subset V$ is said to be linear independent if

For all finite subsets $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}\subset V$

$$c_1 \mathbf{v}_1 + c_2\mathbf{v}_2 \dots + c_n \mathbf{v}_n = \mathbf{0} \Rightarrow c_1=c_2= \dots = c_n =0$$ We saw earlier that this implied uniqueness of coordinates!!

Linear Dependence

Let $V$ be a vector space. A subset $U \subset V$ is said to be linear dependent if it is not independent

That is there exist a finite set of vectors $\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_n$

and scalars $c_1,c_2,\dots, c_n$ not all 0 such that

$c_1\mathbf{v}_1,c_2\mathbf{v}_2,\dots,c_n\mathbf{v}_n=\mathbf{0}$

Which means that one of the vectors can be written as a linear combination of the others. Say that $c_k\neq 0$ then

$\mathbf{v}_k= \frac{c_1}{c_k}\mathbf{v}_1+\frac{c_2}{c_k}\mathbf{v}_2+\dots +\frac{c_{k-1}}{c_k}\mathbf{v}_{k-1}+\dots +\frac{c_{k+1}}{c_k}\mathbf{v}_{k+1}+\dots + \frac{c_{n}}{c_k}\mathbf{v}_{n}$

Span of a set

Let $V$ be a vector space let $U\subset V$ be a subset of $V$

The span of the set $U$, $\operatorname{span}(U)$ is defined as the intersection of all subspaces of V that contain U

Or equivalently the more operational statement.

$\operatorname{span}(U)=$ the set of all finite linear combinations from the set $U$

This set $\operatorname{span}(U)$ is itself a subspace of the vector space $V$.

Try to convince yourselves that this is correct.

Hamel Basis

Let $V$ be a vector space. Then the set $B\subset V$ is a basis of $V$ if

1. $B$ is independent
2. $\operatorname{span} (B)=V$, or equivalently every vector $\mathbf{v}\in V$ can be expressed as a linear combination of the vectors in $B$

This definition calls for some examples

Remark:

The term Hamel basis is useful to know when reading mathematical literature. It is used to distinguish the usual concept of a basis in a vector space from the concept of a Schauder basis, which is used in topological vector spaces.

The term Schauder basis is a more specialized concept that additionally involves the topology of the vector space and allows infinite convergent expansions. It will not be discussed in this course.

Let $\mathbb{P}$ be the vector space of all real polynomials of one variable.

That this is a vector space is easy to check.

Then the claim is that the set $B=\{t^0,t^1,t^2,t^3,t^4\dots \}$ is a basis

First notice that the set $B$ is not finite.

B is linear independent

Pick any finite set say $\{ t^{k_1},t^{k_2} \dots t^{k_n} \}$ where $k_i\neq k_{j}$ for $i\neq j$ Consider $$c_1t^{k_1}+c_2t^{k_2}+ \dots +c_nt^{k_n} =0$$ Since a polynomial of finite degree can at most have finite many zeroes all coefficients must be zero.

$\mathbb{P}=\textbf{Span}(\textbf{B})$

To prove this fact, pick any $v\in \mathbb{P}$. By definition a polynomial is finite in degree. And therefore is a linear combination of $n$ of the basis elements

Consider the vector space $\mathbb{R}^n$. The set $$B=\{ \mathbf{e}_1=(1,0,0\dots 0), \mathbf{e}_2=(0,1,0,\dots ,0 ),\dots , \mathbf{e}_n=(0,0,\dots ,1)\}$$ is a basis. Notice it is finite

B is linear independent

$$c_1\mathbf{e}_1+c_2+ \dots + c_n\mathbf{e}_n=\mathbf{0}$$

$$(c_1,c_2, \dots ,c_n)=\mathbf{0} \Rightarrow c_1=c_2= \dots =c_n=0$$

$\mathbb{R}^n=\textbf{Span}(\textbf{B})$

Fo any $$\mathbf{x}=(x_1,x_2,\dots ,x_n) \in \mathbb{R}^n$$

$$x=x_1\mathbf{e}_1+x_2\mathbf{e}_2 \dots +x_n\mathbf{e}_n$$

This is called the standard basis

We are now ready to define the dimension of a vector space

Vector Space Dimension

1. If a vector space has a basis that is infinite: It is said to be infinite dimensional
2. If a vector space has a finite basis it is finite dimensional and the dimension is the size of the basis.

At this point two theorems should be observed

1. Any vector space has a basis
2. Any two basis of a vector space have the same size

We have seen one example of an infinite dimensional vector space but as stated earlier we will concentrate on the vector space $\mathbb{R}^n$, which is as we saw is finite dimensional.

In this case we have further theorems

1. Any linear independent set of size $n$ is a basis
2. Any set of linear independent vectors can be extended to a basis of size $n$

We saw an example of theorem 2 in an earlier exercise

Now that we have established that several basis can be used on the same space, how do we calculate the coordinates of a vector in one basis if we have the coordinates in another basis?

Say we have two different basis in $\mathbb{R}^n$ $$\begin{aligned} \mathbf{e}_1,\mathbf{e}_2 \dots ,\mathbf{e}_n\\ \mathbf{f}_1,\mathbf{f}_2 \dots ,\mathbf{f}_n \end{aligned}$$

And we know the coordinates of some vector $\mathbf{v}$ in the first basis. That is

$$\mathbf{v}= c_1\mathbf{e}_1+c_2\mathbf{e}_2 \dots +c_n\mathbf{e}_n$$ How can we calculate the coordinates $d_i$ in

$$\mathbf{v}= d_1\mathbf{f}_1+d_2\mathbf{f}_2 \dots +d_n\mathbf{f}_n$$

We have the known coordinates $c_j$

$$v=\sum_{j=1}^n c_j\mathbf{e}_j$$

But any of the basis vectors $\mathbf{e}_j$ can be expressed as a linear combination in the basis $\mathbf{f}_i$. That is

$$\mathbf{e}_j=\sum_{i=1}^n a_{ij}\mathbf{f}_i$$

Which implies

$$v=\sum_{j=1}^n c_j\mathbf{e}_j=\sum_{j=1}^n c_j \sum_{i=1}^n a_{ij}\mathbf{f}_i= \sum_{i=1}^n (\sum_{j=1}^n a_{ij}c_j) \mathbf{f}_i=\sum_{i=1}^n d_i \mathbf{f}_i$$

Where the i'th coordinate $d_i$ in the basis $\mathbf{f}_i$ is

$$d_i= \sum_{j=1}^n a_{ij}c_j$$

Now this seems overwhelming! But let us look at it in steps

First of all the calculation is simple.

• From old coordinates the new coordinates are calculated by some multiplication of numbers summed up.

But what are the numbers $a_{ij}$

• For a fixed $j$ it is simply the coordinates of the initial basis vector $\mathbf{e}_j$ in the target basis $\mathbf{f}_i$.

So let us carefully take an example we have seen before in $\mathbb{R}^2$

Consider two bases of $\mathbb{R}^2$:

$$\begin{aligned} \mathbf{e}_1=(1,0),\quad \mathbf{e}_2=(0,1)\\ \mathbf{f}_1=(1,1),\quad \mathbf{f}_2=(-1,1) \end{aligned}$$ And a vector

$$\mathbf{v}=c_1\mathbf{e}_1+c_2\mathbf{e}_2$$

We know that the coordinates in the new basis $\mathbf{f}_1, \mathbf{f}_2$ are calculated by

$$d_i=\sum_{j=1}^2 a_{ij}c_j$$

And that for fixed $j$ the $a_{1j},a_{2j}$ are the coordinates of the vector $\mathbf{e}_j$ in the basis $\mathbf{f}_i$

Or formulated in words:

The new coordinate for $\mathbf{v}$ in the basis $\mathbf{f}_i$ is calculated by

Calculating the sum of the old coordinates times every coordinate of that index $i$ of the old basis in the target basis summed up.

So, we need the initial basis expressed in the target basis $$\begin{aligned} (1,0)&=a (1,1)+b (-1,1)\\ (0,1)&=c (1,1)+d (-1,1) \end{aligned}$$

$$\begin{aligned} a-b=1, a+b=0\\ c-d=0, c+d=1 \end{aligned}$$ producing $$\begin{aligned} a=\frac{1}{2}, b=-\frac{1}{2}, c=\frac{1}{2}, d=\frac{1}{2} \end{aligned}$$ That is $$a_{11}=\frac{1}{2}, a_{21}=-\frac{1}{2}, a_{12}=\frac{1}{2}, a_{22}=\frac{1}{2}$$

So to move from representation in initial coordinates $c_i$ in basis $\mathbf{e}_i$ to a representation in new coordinates $d_i$ in basis $\mathbf{f}_i$ we have $$d_i=\sum_{j=1}^2 a_{ij}c_j$$ that is $$\begin{aligned} d_1=a_{11}c_1+a_{12}c_2=\frac{1}{2}c_1+\frac{1}{2}c_2\\ d_2=a_{21}c_1+a_{22}c_2=-\frac{1}{2}c_1+\frac{1}{2}c_2 \end{aligned}$$

We have to get used to this so in $\mathbb{R}^3$ consider the basis

$$\begin{aligned} \mathbf{e}_1= (1,0,0),\quad \mathbf{e}_2 = (0,1,0),\quad \mathbf{e}_3= (0,0,1)\\ \mathbf{f}_1= (1,1,1), \quad \mathbf{f}_2 = (1,-1,1), \quad \mathbf{f}_3= (1,1,-1) \end{aligned}$$

First of all is the set $\mathbf{f}_i$ linearly independent?

You can show this easily and since there are three of them it is a basis of the three-dimensional vector space $\mathbb{R}^3$

If a vector $\mathbf{v}$ has coordinates $(c_1,c_2,c_3)$ in the $\mathbf{e}_i$ basis what are the coordinates in the $\mathbf{f}_i$ basis?

So we have to express the initial basis vectors in the target basis

$$\begin{aligned} (1,0,0)=a_{11} (1,1,1)+a_{21} (1,-1,1)+a_{31} (1,1,-1)\\ (0,1,0)=a_{12} (1,1,1)+a_{22} (1,-1,1)+a_{32} (1,1,-1)\\ (0,0,1)=a_{13} (1,1,1)+a_{23} (1,-1,1)+a_{33} (1,1,-1) \end{aligned}$$

These are three linear systems of three equations in three unknowns. Let us write them down explicitly

$$\begin{aligned} 1 &= a_{11}+a_{21}+a_{31} &\qquad 0 &= a_{12}+a_{22}+a_{32} &\qquad 0 &= a_{13}+a_{23}+a_{33}\\ 0 &= a_{11}-a_{21}+a_{31} &\qquad 1 &= a_{12}-a_{22}+a_{32} &\qquad 0 &= a_{13}-a_{23}+a_{33}\\ 0 &= a_{11}+a_{21}-a_{31} &\qquad 0 &= a_{12}+a_{22}-a_{32} &\qquad 1 &= a_{13}+a_{23}-a_{33} \end{aligned}$$

Which can be solved to $$\begin{aligned} a_{11}=0,a_{21}=\frac{1}{2},a_{31}=\frac{1}{2}\\ a_{12}=\frac{1}{2},a_{22}=-\frac{1}{2},a_{32}=0\\ a_{13}=\frac{1}{2},a_{23}=0,a_{33}=-\frac{1}{2} \end{aligned}$$ That is

$$\begin{aligned} (1,0,0)=0(1,1,1)+\frac{1}{2}(1,-1,1)+\frac{1}{2}(1,1,-1)\\ (0,1,0)=\frac{1}{2}(1,1,1)-\frac{1}{2}(1,-1,1)+0(1,1,-1)\\ (0,0,1)=\frac{1}{2}(1,1,1)+0(1,-1,1)-\frac{1}{2}(1,1,-1) \end{aligned}$$

So following the rule we deduce $$\begin{aligned} d_1=0c_1+\frac{1}{2}c_2+\frac{1}{2}c_3=\frac{1}{2}(c_2+c_3)\\ d_2=\frac{1}{2}c_1-\frac{1}{2}c_2+0c_3=\frac{1}{2}(c_1-c_2)\\ d_3=\frac{1}{2}c_1+0c_2-\frac{1}{2}c_3=\frac{1}{2}(c_1-c_3) \end{aligned}$$

This general calculational procedure can be organized into a special scheme which involves matrices.

Matrices are simply data organized in two-dimensional arrays.

If we organize the coefficients $aij$ into a table and the coordinates into a column $$\begin{bmatrix} d_{1}\\ d_{2}\\ \vdots\\ d_n \end{bmatrix} = \begin{bmatrix} a_{11}& a_{12}&\dots& a_{1n}\\ a_{21}& a_{22}&\dots& a_{2n}\\ \vdots & \vdots& \ddots& \vdots \\ a_{n1}& a_{n2}&\dots& a_{nn} \end{bmatrix} \begin{bmatrix} c_{1}\\ c_{2}\\ \vdots\\ c_n \end{bmatrix}$$

And we introduce a special operation called matrix multiplication we will see that this replicates the previous calculation

First of all we observe that the columns in the matrix are the coordinates of the initial basis in the target basis. $a_{1k},a_{2k},\dots,a_{nk}$ are the coordinates of $\mathbf{e}_k$ in the target basis $\mathbf{f}_i$

The way to conduct this operation in accordance with the sum formula is easiest shown by hand

Let us pick up the example in $\mathbb{R}^3$ The expansion of the old basis $\mathbf{e}_i$ in the new basis $\mathbf{f}_i$ was

$$\begin{aligned} (1,0,0)=0(1,1,1)+\frac{1}{2}(1,-1,1)+\frac{1}{2}(1,1,-1)\\ (0,1,0)=\frac{1}{2}(1,1,1)-\frac{1}{2}(1,-1,1)+0(1,1,-1)\\ (0,0,1)=\frac{1}{2}(1,1,1)+0(1,-1,1)-\frac{1}{2}(1,1,-1) \end{aligned}$$

Matrix formulation

We construct the coordinate change matrix by making the the expansion coefficients columns like

$$\begin{bmatrix} d_1 \\ d_2\\ d_3 \end{bmatrix} = \begin{bmatrix} 0 & \frac{1}{2} &\frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2}& 0\\ \frac{1}{2} & 0 &-\frac{1}{2} \end{bmatrix} \, \begin{bmatrix} c_1 \\ c_2\\ c_3 \end{bmatrix}$$

And using the matrix multiplication we obtain $$d_1=\frac{1}{2}(c_2+c_3),d_2=\frac{1}{2}(c_1-c_2), d_3=\frac{1}{2}(c_1-c_3)$$

We have now seen how to convert coordinates from one arbitrary basis to another arbitrary basis.

But it should be recognized that converting from some arbitrary basis to the standard basis is much simpler!

Why because we immediately know the coordinates of the initial basis in the standard basis.

This has an impact on practical calculations.

Consider some initial basis

$$\mathbf{f}_1,\mathbf{f}_2,\dots ,\mathbf{f}_n$$

and let the target basis be the standard basis.

$$\mathbf{e}_1=\mathbf{ (1,0,0,\dots ,0)},\mathbf{e}_2=\mathbf{ (0,1,0,\dots ,0)},\dots ,\mathbf{e}_n=\mathbf{ (0,0,0,\dots ,1)}$$

Let's assume we know the coordinates $c_j$ in the basis $\mathbf{f}_j$ and want coordinates $d_i$ in the standard basis $\mathbf{e}_i$.

Then we can immediately write the coefficients $a_{ij}$

$a_{1k},a_{2k},\dots a_{nk}$, are the coordinates of the k'th basis vector in the target basis which is the standard basis which in turn is simply the vector components of the k'th initial basis vector

Change from $(1,1), (-1,1)$ to $(1,0)$ to $(0,1)$ then we have

$$\begin{aligned} (1,1)=1(1,0)+1(0,1)\\ (-1,1)=-1(1,0)+1(0,1) \end{aligned}$$

And as we discussed before the new coordinates $(d_1,d_2)$ are calculated by the old coordinates by

$$\begin{aligned} d_1&=1c_1+ -1c_2=c_1-c_2\\ d_2&=1c_1+ 1c_2=c_1+c_2 \end{aligned}$$

Or put in matrix form

$$\begin{bmatrix} d_1 \\ d_2 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} \, \begin{bmatrix} c_1 \\ c_2 \end{bmatrix}$$

which implies new coefficients are $$\begin{aligned} d_1=c_1-c_2,d_2=c_1+c_2 \end{aligned}$$

A very important fact is if we use the transformation in the other direction we should get back the same coordinates.

In matrix formulation the transformation from basis $(1,0),(0,1)$ to $(1,1),(-1,1)$ is

$$\begin{bmatrix} d_1\\ d_2 \end{bmatrix} = \begin{bmatrix} \frac{1}{2}& \frac{1}{2}\\ -\frac{1}{2}& \frac{1}{2} \end{bmatrix} \begin{bmatrix} c_1\\ c_2 \end{bmatrix}$$

And in matrix formulation the transformation from basis $(1,1),(-1,1)$ to $(1,0),(0,1)$ is $$\begin{bmatrix} c_1\\ c_2 \end{bmatrix} = \begin{bmatrix} 1& -1\\ 1& 1 \end{bmatrix} \begin{bmatrix} d_1\\ d_2 \end{bmatrix}$$ This must imply that $$\begin{bmatrix} 1& -1\\ 1& 1 \end{bmatrix} \begin{bmatrix} \frac{1}{2}& \frac{1}{2}\\ -\frac{1}{2}& \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 1& 0\\ 0& 1 \end{bmatrix}$$ Which is the case indeed.

This is a very important property of basis transformations, and it is called invertibility.

The transformation from one basis to another is invertible, and the inverse transformation is the transformation in the other direction.

So, given a matrix $A$ that maps coordinates the inverse matrix $A^{-1}$ maps the other way, which is not surprising.

This can be exploited in general coordinate changes between any two bases.

Consider the vector space $\mathbb{R}^n$ with bases

$$\begin{aligned} \mathbf{b}_1,\mathbf{b}_2,\dots \mathbf{b}_n\\ \mathbf{f}_1,\mathbf{f}_2,\dots \mathbf{f}_n \end{aligned}$$

And remember we have the standard basis $$\mathbf{e}_1,\mathbf{e}_2,\dots \mathbf{e}_n$$ Let's say we are given coordinates in basis $\mathbf{b}_i$ and we want to change to coordinates in basis $\mathbf{f}_i$

It was very easy to construct the basis change matrix $B_{b\rightarrow e}$ from a general basis $\mathbf{b}_i$ to the standard basis, and likewise from $F_{f\rightarrow e}$ from $\mathbf{f}_i$ to the standard basis.

So, we have now simply construct

$$F_{f\rightarrow e}^{-1}B_{b\rightarrow e}$$

First we transform from the $\mathbf{b}_i$ coordinates to the standard coordinates and the transform from standard coordinates to $\mathbf{f}_i$ coordinates by the inverse of $F_{f\rightarrow e}$.

This of course forces us to calculate the inverse of a matrix but that can easily be done in calculational tools.

At this juncture we state some facts about coordinate transformation matrices.

1. A coordinate transformation matrix is always square
2. A coordinate transformation matrix obviously has an inverse
3. A coordinate transformation matrix inverse is denoted $A^{-1}$ with property $AA^{-1}=A^{-1}A=Id$

Where $Id$ is the identity matrix which has one's on the diagonal and zeros elsewhere. As this example of a $3x3$ matrix indicates

$$Id= \, \begin{bmatrix} 1& 0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}$$ So if the matrix $A$ transforms from one set of coordinates to another the inverse transforms the other way.

The matrix has an inverse if the determinant is non-zero

The determinant has a general formula

$$\det (A) = \sum_{\sigma \in S_n} \operatorname{sgn} (\sigma)\, a_{1,\sigma (1)} a_{2,\sigma (2)} \cdots a_{n,\sigma (n)}$$

where

$S_n$ is the set of all permutations of $\{ (1,2,\dots ,n)\}$

$sign (\sigma)$ is the sign of the permutation $+1$ or $-1$

This is a very unpractical formula but is can be calculated in other ways. But for now we will use numpy to calculate it.

An intuitive understanding of the determinant is that the determinant gives the signed volume of the parallelepiped spanned by the column vectors

A very relevant use of the determinant is when we want to examine a set of vectors for linear independence.

We will exemplify in $\mathbb{R}^3$, but the technique generalized immediately.

Consider the set of vectors under test for linear independence $$\begin{aligned} \mathbf{b}_1&= (1,-1,1)\\ \mathbf{b}_2&= (1,1,0)\\ \mathbf{b}_3&= (1,-1,-1) \end{aligned}$$

The condition for linear independence is stated by

$$c_1\mathbf{b}_1+c_2\mathbf{b}_2+c_3\mathbf{b}_3=\mathbf{0}\Rightarrow c_1=c_2=c_3=0$$

This is equivalently stated in matrix formulation as $$\begin{bmatrix} 1 & 1& 1\\ -1& 1& -1\\ 1 & 0& -1 \end{bmatrix} \, \begin{bmatrix} c_1\\ c_2\\ c_3 \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix}$$

And if we are to be sure that the only solution is $c_1=c_2=c_3=0$ the matrix has to be invertible. And then the determinant must be non-zero

We can calculate this in numpy

A_1=np.array([1,-1,1])
A_2=np.array([1,1,0])
A_3=np.array([1,-1,-1])
A=np.column_stack((A_1,A_2,A_3))
print(np.linalg.det(A))
# -4