# Lecture 13

## Linear Algebra II:

### Eigenvalues and Eigenvectors


```python
import numpy as np
import sympy as sp
import scipy.integrate
sp.init_printing()
##################################################
##### Matplotlib boilerplate for consistency #####
##################################################
from ipywidgets import interact
from ipywidgets import FloatSlider
from matplotlib import pyplot as plt

%matplotlib inline

from IPython.display import set_matplotlib_formats
set_matplotlib_formats('svg')

global_fig_width = 10
global_fig_height = global_fig_width / 1.61803399
font_size = 12

plt.rcParams['axes.axisbelow'] = True
plt.rcParams['axes.edgecolor'] = '0.8'
plt.rcParams['axes.grid'] = True
plt.rcParams['axes.labelpad'] = 8
plt.rcParams['axes.linewidth'] = 2
plt.rcParams['axes.titlepad'] = 16.0
plt.rcParams['axes.titlesize'] = font_size * 1.4
plt.rcParams['figure.figsize'] = (global_fig_width, global_fig_height)
plt.rcParams['font.sans-serif'] = ['Computer Modern Sans Serif', 'DejaVu Sans', 'sans-serif']
plt.rcParams['font.size'] = font_size
plt.rcParams['grid.color'] = '0.8'
plt.rcParams['grid.linestyle'] = 'dashed'
plt.rcParams['grid.linewidth'] = 2
plt.rcParams['lines.dash_capstyle'] = 'round'
plt.rcParams['lines.dashed_pattern'] = [1, 4]
plt.rcParams['xtick.labelsize'] = font_size
plt.rcParams['xtick.major.pad'] = 4
plt.rcParams['xtick.major.size'] = 0
plt.rcParams['ytick.labelsize'] = font_size
plt.rcParams['ytick.major.pad'] = 4
plt.rcParams['ytick.major.size'] = 0
##################################################
```

## Recap from Part I

- Matrix representation of simultaneous equations
- Matrix-vector multiplication
- Matrix-matrix multiplication
- Determinant ($2\times2$ matrices)
- Inverting matrices
- Transpose
- Python

## Using Python to calculate the inverse
To find $A^{-1}$ for 
$$A = \left(\begin{matrix}3&0&2\\ 3&0&-3\\ 0&1&1\end{matrix}\right).$$


```python
A = np.array([[3, 0, 2], [3, 0, -3], [0, 1, 1]])
np.linalg.inv(A)

```


```python
A = sp.Matrix([[3, 0, 2], [3, 0, -3], [0, 1, 1]])
A.inv()

```

## It doesn't always work

Consider the following system 

$$\begin{array}{cccccccc}
eq1: &  x & + & y & + & z & =  & a \\
eq2: & 2x & + & 5y & + &  2z &  = & b \\
eq3: & 7x & +&  10y  & + & 7z &  = &  c 
\end{array} $$ 


```python
A = np.array([[1, 1, 1], [2, 5, 2], [7, 10, 7]])
np.linalg.inv(A)

```

## Singular matrices

The **rank** of an $\;n\,\times\,n\;$ matrix $\;A\;$ is the number of linearly independent rows in $\;A\;$ (rows not combinations of other rows).

When $\;\mbox{rank}(A) < n\;$ then

- The system $\;A\textbf{x} = \textbf{b}\;$ has *fewer* equations than unknowns
- The matrix is said to be singular
- $A\;$ has no inverse
- The determinant of $\;A\;$ is 0
- The equation $\;A\textbf{u} = \textbf{0}\;$ has non-trivial solutions (solutions where $\textbf{u} \neq \textbf{0}$)

## Singular matrix example

An underdetermined system (fewer equations than unknowns) may mean that there are **many solutions** or that there are **no solutions**.

An example  with many solutions is
\begin{eqnarray*} x+y &=& 1,\\ 2x+2y &=& 2,\end{eqnarray*}


has infinitely many solutions (x=0, y=1; x=-89.3, y=90.3...)

An example with no solutions is

\begin{eqnarray*} x+y &=& 1,\\ 2x+2y &=& 0,\end{eqnarray*}

where the second equation is inconsistent with the first.

 These examples use the matrix 
$$ \left(\begin{matrix}1&1\\ 2&2\end{matrix}\right),$$
 which has rank 1. 

## Null space
When a matrix is singular we can find non-trivial solutions to $\;A\textbf{u} = \textbf{0}$.

These are vectors which form the **null space** for $\;A$.

Any vector in the null space makes no difference to the effect that $A$ is having:

$$
 A(\textbf{x} + \textbf{u}) =  A\textbf{x} + A\textbf{u} =
 A\textbf{x} + \textbf{0} =   A\textbf{x}.
$$ 

Note that any combination or scaling of vectors in the null space is also in the null space.
That is, if $\;A\textbf{u} = \textbf{0}\;$ and $\;A\textbf{v} = \textbf{0}\;$ then

$$ A(\alpha\textbf{u} + \beta\textbf{v}) = \textbf{0} $$

The number of linearly independent vectors in the null space is denoted $~\mbox{null}(A)~$ and

$$\mbox{null}(A)  + \mbox{rank}(A) = \mbox{order}(A).$$

## Null space example

Previous example of a singular system:
$$A = \left(\begin{matrix} 1& 1& 1\\ 2& 5& 2\\ 7& 10&7 \end{matrix}\right)$$ 


```python
A = np.array([[1, 1, 1], [2, 5, 2], [7, 10, 7]])
np.linalg.matrix_rank(A)

```


```python
import scipy.linalg
scipy.linalg.null_space(A)

```

remember, scaled vectors in the null space are also in the null space, for example, $\;x=1, y=0, z=-1\;$ is in the null space. 

Try it:

 $\left(\begin{matrix} 1& 1& 1\\ 2& 5& 2\\ 7& 11&7 \end{matrix}\right)
  \left(\begin{matrix} -1000\\ 0 \\ 1000 \end{matrix}\right) = \quad ?$


```python
np.matmul(A,np.array([-1000,0,1000]))

```

## Eigenvectors: motivation

The **eigenvalues** and **eigenvectors** give an indication of how much effect the matrix has, and in what direction. 

$$A=\left(\begin{matrix} \cos(45)&-\sin(45)\\ \sin(45)&\cos(45)\\\end{matrix}\right)\qquad\mbox{has no scaling effect.}$$

$$B=\left(\begin{matrix} 2& 0 \\ 0&\frac{1}{2}\\\end{matrix}\right)\qquad\qquad\mbox{doubles in }x\mbox{, but halves in }y\mbox{.}$$


Repeated applications of $\;A\;$ stay the same distance from the origin, but repeated applications of $\;B\;$ move towards $\;(\infty, 0).$

- Transitions with probability
- Markov chains
- Designing bridges
- Solution of systems of linear ODEs
- Stability of systems of nonlinear ODEs

## Eigenvectors and Eigenvalues

$A\;$ is a matrix, $\;\textbf{v}\;$ is a **non-zero** vector, 
$\;\lambda\;$ is a scalar, 

If

$$A \textbf{v} = \lambda \textbf{v}$$

then $\;\textbf{v}\;$ is called an **eigenvector** and $\;\lambda\;$ is the corresponding **eigenvalue**.

Note that if $\;\textbf{v}\;$ is a solution, then so is a scaling $\;a\textbf{v}$:

$$A (a \textbf{v}) = \lambda (a \textbf{v}).$$

## Finding Eigenvalues
Another way to write previous equation:

\begin{eqnarray*}
A \textbf{v} &=& \lambda \textbf{v},\\
A \textbf{v} -  \lambda I \textbf{v}&=& \textbf{0},\\
(A  -  \lambda I) \textbf{v}&=& \textbf{0}.
\end{eqnarray*}

Consider the equation:
$$B\textbf{x}=\textbf{0}$$

where $\;B\;$ is a matrix and $\;\textbf{x}\;$ is a non-zero column vector.

Assume $\;B\;$ is nonsingular:
$$B^{-1}(B\textbf{x})=B^{-1}\textbf{0}=\textbf{0}$$

But:
$$B^{-1}(B\textbf{x})=(B^{-1}B)\textbf{x}=I\textbf{x}=\textbf{x}$$

This means that:
$$B^{-1}(B\textbf{x})=\textbf{0}=\textbf{x}$$

but we stated above that $\;\textbf{x}\neq\textbf{0}\;$ so our assumption that $\;B\;$ is nonsingular must be false: $\;B\;$ is singular.

We can state that:

$$(A-\lambda I)\textbf{v} = \textbf{0}  \quad \mbox{with} \quad \textbf{v}\neq \textbf{0},$$

so $(A-\lambda I)$ must be singular:

$$|A-\lambda I|=0.$$

## Example
What are the eigenvalues for this matrix?

$$A=\left(\begin{matrix}-2&-2\\ 1&-5\\\end{matrix}\right)$$

$$|A-\lambda I|=\left\vert\begin{matrix}-2-\lambda&-2\\ 1&-5-\lambda\end{matrix}\right\vert=(-2-\lambda)(-5-\lambda)-(-2)$$

$$=10+5\lambda+\lambda^2+2\lambda+2=\lambda^2+7\lambda+12=(\lambda+3)(\lambda+4)=0$$

So the eigenvalues are $\lambda_1=-3$ and $\lambda_2=-4$.

## Eigenvalues using Python

Numpy:


```python
A = np.array([[-2, -2], [1, -5]])
np.linalg.eig(A)[0]

```

SymPy:


```python
A2 = sp.Matrix([[-2, -2], [1, -5]])
A2.eigenvals()

```

## Finding Eigenvectors

For an eigenvalue, the corresponding vector comes from substitution into $\;A \textbf{v} = \lambda \textbf{v}$:


### Example
What are the eigenvectors for

$$A=\left(\begin{matrix}-2&-2\\ 1&-5\\\end{matrix}\right)?$$

The eigenvalues are $\;\lambda_1=-3\;$ and $\;\lambda_2=-4.\;$
The eigenvectors are $\;\textbf{v}_1\;$ and $\;\textbf{v}_2\;$ where:

$$A\textbf{v}_1=\lambda_1 \textbf{v}_1.$$

$$\begin{eqnarray*}
\left(\begin{matrix}-2&-2\\ 1&-5\\\end{matrix}\right)
\left(\begin{matrix}u_1\\ v_1\\\end{matrix}\right)
&=&
\left(\begin{matrix}-3u_1\\ -3v_1\\\end{matrix}\right),\\
u_1 &=& 2v_1.  \mbox{  (from the top or bottom equation)}\\
\left(\begin{matrix}u_1\\ v_1\\\end{matrix}\right)
&=&
\left(\begin{matrix}2 \\ 1\\\end{matrix}\right),
\left(\begin{matrix}1 \\ 0.5\\\end{matrix}\right),
\left(\begin{matrix}-4.4 \\ -2.2\\\end{matrix}\right),
\left(\begin{matrix}2\alpha \\ \alpha\\\end{matrix}\right)\ldots
\end{eqnarray*}$$

## Eigenvectors in Python

Numpy:


```python
A = np.array([[-2, -2], [1, -5]])
np.linalg.eig(A)[1]

```

SymPy:


```python
c = sp.symbols('c')
A2 = sp.Matrix([[-2, c], [1, -5]])
A2.eigenvects()

```

## Diagonalising matrices

Any nonsingular matrix $A$ can be rewritten as a product of eigenvectors and eigenvalues.  

If $\;A\;$ has eigenvalues $\;\lambda_1\;$ and $\;\lambda_2\;$ with corresponding eigenvectors  $\;\left(\begin{matrix}u_1\\ v_1\\\end{matrix}\right)\;$ and
$\left(\begin{matrix}u_2\\ v_2\\\end{matrix}\right)$ then

$$\begin{eqnarray}
A =
\left(\begin{matrix}u_1 & u_2\\v_1 & v_2\\\end{matrix}\right)
\left(\begin{matrix}\lambda_1 & 0\\0 & \lambda_2\\\end{matrix}\right)
\left(\begin{matrix}u_1 & u_2\\v_1 & v_2\\\end{matrix}\right)^{-1}. \label{eq:diag}
\end{eqnarray}$$

This is like a scaling surrounded by rotations and separates how much effect the matrix has $\;(\lambda_i)\;$ from the directions $\;(\textbf{v}_i).$


## For example

$$A=\left(\begin{matrix}-2&-2\\ 1&-5\\\end{matrix}\right)$$


```python
A = np.array([[-2, -2], [1, -5]])
w, v = np.linalg.eig(A)
inv_v = np.linalg.inv(v)

np.matmul( np.matmul(v, np.diag(w)) , inv_v )

```

## Orthogonal eigenvectors
If $\;\textbf{x}_1\;$ and $\;\textbf{x}_2\;$ are perpendicular or **orthogonal** vectors, then the scalar/dot product is zero.

$$\textbf{x}_1.\textbf{x}_2=0$$

e.g.

$$\textbf{x}_1.\textbf{x}_2=\left(\begin{matrix}2\\ -1\\ 3\end{matrix}\right).\left(\begin{matrix}2\\ 7\\ 1\end{matrix}\right)=2\times 2+(-1\times 7)+(3\times1)=4-7+3=0.$$

Since this dot product is zero, the vectors $\textbf{x}_1$ and $\textbf{x}_2$ are orthogonal.

## Symmetric matricies

Symmetric matricies have orthogonal eigenvectors, e.g.

$$A=\left(\begin{matrix}19&20&-16\\ 20&13&4 \\ -16&4&31\\\end{matrix}\right)$$


```python
A = np.array([[19, 20, -16], [20, 13, 4], [-16, 4, 31]])
w, v = np.linalg.eig(A)
print(v)
print('\ndot products of eigenvectors:\n')
print(np.dot(v[:,0],v[:,1]))
print(np.dot(v[:,0],v[:,2]))
print(np.dot(v[:,1],v[:,2]))

```

## Normalised eigenvectors
If

$$\left(\begin{matrix}x\\ y\\ z\\\end{matrix}\right),$$

is an eigenvector, then

$$\left(\begin{matrix}\frac{x}{\sqrt{x^2+y^2+z^2}}\\ \frac{y}{\sqrt{x^2+y^2+z^2} }\\ \frac{z}{\sqrt{x^2+y^2+z^2} }\end{matrix}\right)$$

is the corresponding normalised vector: a vector of unit length (magnitude).

## Orthogonal matrices
A matrix is orthogonal if its columns are normalised orthogonal vectors.
One can prove that if $\;M\;$ is orthogonal then:

  $$M^TM=I\qquad M^T=M^{-1}$$


Note that if the eigenvectors are written in orthogonal form then the diagonalising equation
is simplified:

\begin{eqnarray*}
A 
&=&
\left(\begin{matrix}u_1 & u_2\\v_1 & v_2\\\end{matrix}\right)
\left(\begin{matrix}\lambda_1 & 0\\0 & \lambda_2\\\end{matrix}\right)
\left(\begin{matrix}u_1 & u_2\\v_1 & v_2\\\end{matrix}\right)^{-1}
\\
&=&
\left(\begin{matrix}u_1 & u_2\\v_1 & v_2\\\end{matrix}\right)
\left(\begin{matrix}\lambda_1 & 0\\0 & \lambda_2\\\end{matrix}\right)
\left(\begin{matrix}u_1 & v_1\\u_2 & v_2\\\end{matrix}\right).
\end{eqnarray*}



## Summary

- Matrix representation of simultaneous equations
- Matrix-vector and matrix-matrix multiplication
- Determinant, inverse and transpose
- Null space of singular matrices
- Finding eigenvalues and eigenvectors
- Python for solving systems, finding inverse, null space and eigenvalues/vectors
- Diagonalising matrices (we will use this for systems of differential equations)

32c0f30457296178dad8e300e27edf013b4a17c5
ipynb
Jupyter Notebook
lectures/lecture-13-linear-algebra-2.ipynb
SABS-R3/2020-essential-maths
5a53d60f1e8fdc04b7bb097ec15800a89f67a047
Apache-2.0
2021-11-27T12:07:13.000Z
2021-11-27T12:07:13.000Z
lectures/lecture-13-linear-algebra-2.ipynb
SABS-R3/2021-essential-maths
8a81449928e602b51a4a4172afbcd70a02e468b8
Apache-2.0
lectures/lecture-13-linear-algebra-2.ipynb
SABS-R3/2021-essential-maths
8a81449928e602b51a4a4172afbcd70a02e468b8
Apache-2.0
2020-10-30T17:34:52.000Z
2020-10-30T17:34:52.000Z
Qwen/Qwen-72B
1. YES
2. YES