Linear Algebra


By Prof. Seungchul Lee
http://iai.postech.ac.kr/
Industrial AI Lab at POSTECH

Table of Contents

0. Video Lectures

In [1]:
%%html 
<center><iframe src="https://www.youtube.com/embed/ZD-o6sdhNsQ?rel=0" 
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>

1. Linear Equations

  • Set of linear equations (two equations, two unknowns)
$$ \begin{align*} 4x_{1} − 5x_{2} &= −13\\ −2x_{1} + 3x_{2} &= 9 \end{align*} $$

1.1. Solving Linear Equations

  • Two linear equations
$$ \begin{align*} 4x_{1} − 5x_{2} &= −13\\ −2x_{1} + 3x_{2} &= 9 \end{align*} $$
  • In vector form, $Ax = b$, with
$$A = \begin{bmatrix} 4 & -5 \\ -2 & 3 \end{bmatrix} , \quad x = \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} , \quad b = \begin{bmatrix} -13 \\ 9 \end{bmatrix} $$
  • Solution using inverse
$$ \begin{align*} Ax &= b \\ A^{-1}Ax &= A^{-1}b \\ x &= A^{-1}b \end{align*} $$

  • Won’t worry here about how to compute inverse, but it’s very siminp.linargr to the standard method for solving linear equations

  • We will use a numpy to compute

In [1]:
import numpy as np
In [3]:
A = np.array([[4, -5], 
              [-2, 3]])
In [4]:
print(A)

[[ 4 -5]
 [-2  3]]
In [6]:
b = np.array([[-13], [9]])
print(b)

[[-13]
 [  9]]
In [11]:
A = np.asmatrix(A)
b = np.asmatrix(b)

x = A.I*b
print(x)

[[3.]
 [5.]]
In [10]:
np.linalg.inv(A).dot(b)
Out[10]:
array([[3.],
       [5.]])
In [ ]:
In [ ]:
In [1]:
import numpy as np
In [2]:
A = np.array([[4, -5],[-2, 3]])
print(A)

[[ 4 -5]
 [-2  3]]
In [3]:
b = np.array([[-13],[9]])
print(b)

[[-13]
 [  9]]

$A^{-1} b$

In [4]:
x = np.linalg.inv(A).dot(b)
print(x)

[[3.]
 [5.]]
In [5]:
A = np.asmatrix(A)
b = np.asmatrix(b)
In [6]:
x = A.I*b
print(x)

[[3.]
 [5.]]

1.2. System of Linear Equations

  • Consider system of linear equations
$$ \begin{align*} y_1 &= a_{11}x_{1} + a_{12}x_{2} + \cdots + a_{1n}x_{n} \\ y_2 &= a_{21}x_{1} + a_{22}x_{2} + \cdots + a_{2n}x_{n} \\ &\, \vdots \\ y_m &= a_{m1}x_{1} + a_{m2}x_{2} + \cdots + a_{mn}x_{n} \end{align*} $$
  • Can be written in a matrix form as $y = Ax$, where


$$ y= \begin{bmatrix} y_{1} \\ y_{2} \\ \vdots \\ y_{m} \end{bmatrix} \qquad A = \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n} \\ a_{21}&a_{22}&\cdots&a_{2n} \\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn} \\ \end{bmatrix} \qquad x= \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix} $$

  1. well-determined linear systems
  2. under-determined linear systems
  3. over-determined linear systems

1.2.1. Well-Determined Linear Systems

  • System of linear equations
$$\begin{array}{c}\ 2x_1 + 3x_2 & = 7\\ x_1 + 4x_2 & = 6 \end{array} \; \implies \; \begin{array}{l}\begin{align*} x_1^{*} & = 2\\ x_2^{*} & = 1 \end{align*}\end{array}$$
  • Geometric point of view
  • Matrix form
$$\begin{array}{c}\ a_{11}x_1 + a_{12}x_2 = b_1\\ a_{21}x_1 + a_{22}x_2 = b_2 \end{array} \begin{array}{c}\ \quad \text{Matrix form}\\ \implies \end{array} \quad \begin{array}{l} \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2} \end{bmatrix} = \begin{bmatrix} b_{1}\\ b_{2} \end{bmatrix} \end{array}$$


\begin{array}{l} \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \large AX = B \end{array}\begin{array}{l} \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \therefore & X^{*} = A^{-1} B \quad\text{ if } A^{-1} \text{ exists} \end{array}

1.2.2. Under-Determined Linear Systems

  • System of linear equations
$$\begin{array}{c}\ 2x_1 + 3x_2 = 7 \end{array} \; \implies \; \begin{array}{l}\begin{align} \text{Many solutions} \end{align}\end{array}$$
  • Geometric point of view


  • Matrix form


$$\begin{array}{c}\ a_{11}x_1 + a_{12}x_2 = b_1 \end{array} \begin{array}{c}\ \quad \text{Matrix form}\\ \implies \end{array} \quad \begin{array}{l} \begin{bmatrix} a_{11} & a_{12} \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2} \end{bmatrix} = b_{1}\\ \end{array}$$


\begin{array}{l} \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \large AX = B \end{array}

\begin{array}{l} \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \therefore \; \text{ Many Solutions when $A$ is fat} \end{array}

1.2.3. Over-Determined Linear Systems

  • System of linear equations
$$\begin{array}{c}\ 2x_1 + 3x_2 & = 7\\ x_1 + 4x_2 & = 6\\ x_1 + x_2 & = 4 \end{array} \; \implies \; \begin{array}{l}\begin{align} \text{No solutions} \end{align}\end{array}$$
  • Geometric point of view


  • Matrix form
$$\begin{array}{c}\ a_{11}x_1 + a_{12}x_2 = b_1\\ a_{21}x_1 + a_{22}x_2 = b_2\\ a_{31}x_1 + a_{32}x_2 = b_3\\ \end{array} \begin{array}{c}\ \quad \text{Matrix form}\\ \implies \end{array} \quad \begin{array}{l} \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22}\\ a_{31} & a_{32}\\ \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2} \end{bmatrix} = \begin{bmatrix} b_{1}\\ b_{2}\\ b_{3} \end{bmatrix} \end{array}$$


\begin{array}{l} \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \large AX = B \end{array}

\begin{array}{l} \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad & \therefore \; \text{ No Solutions when $A$ is skinny} \end{array}

2. Inner Products

  • Inner product: $x, y \in \mathbb{R}^{n}$
$$x^{T}y = \sum\limits_{i=1}^{n}x_{i}\,y_{i} \quad \in \mathbb{R} $$
In [15]:
x = np.array([[1],
              [1]])

y = np.array([[2],
              [3]])

print(x.T.dot(y))

[[5]]
In [8]:
x = np.asmatrix(x)
y = np.asmatrix(y)

print(x.T*y)

[[5]]

2.1. Norms (strenth or distance in linear space)

  • $l_{2}$ norm
$$\left\lVert x \right\rVert _{2} = \sqrt{\sum\limits_{i=1}^{n}x_{i}^2}$$
  • $\lVert x\rVert$ measures length of vector (from origin)
In [18]:
x = np.array([[4],
              [-3]])

np.linalg.norm(x, 2)
Out[18]:
5.0
In [19]:
np.linalg.norm(x, 1)
Out[19]:
7.0

2.2. Orthogonality

  • Two vectors $x, y \in \mathbb{R}^n$ are orthogonal if

    $$x^Ty = 0$$

  • They are orthonormal if, in addition,

    $$\lVert x \rVert _{2} = \lVert y \rVert _{2} = 1 $$

In [20]:
x = np.matrix([[1],[2]])
y = np.matrix([[2],[-1]])
In [22]:
print(y)

[[ 2]
 [-1]]
In [27]:
z = x.T*y
print(z[0,0])

0

2.3. Angle between Vectors

  • For any $x, y \in \mathbb{R}^n, \lvert x^Ty \rvert \leq \lVert x \rVert \, \lVert y \rVert$
  • (Unsigned) angle between vectors in $\mathbb{R}^n$ defined as
$$ \begin{align*} \theta &= \angle(x,y) = \cos^{-1}\frac{x^Ty}{\lVert x \rVert \lVert y \rVert}\\ \\ \text{thus}\; x^Ty &= \lVert x \rVert \lVert y\rVert \cos\theta \end{align*} $$



  • $\{ x \mid x^Ty \leq 0\} $ defines a halfspace with outward normal vector $y$, and boundary passing through 0



In [13]:
%%javascript
$.getScript('https://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')