03: Linear Algebra - Review

Matrices - overview

Rectangular array of numbers written between square brackets
- 2D array
- Named as capital letters (A,B,X,Y)
Dimension of a matrix are [Rows x Columns]
- Start at top left
- To bottom left
- To bottom right
- R^{[r x c]} means a matrix which has r rows and c columns
  $A = [\begin{matrix} 1402 & 191 \\ 1371 & 821 \\ 949 & 1437 \\ 147 & 1448 \end{matrix}]$
```
import numpy as np

A = np.array([[1402,  191],
              [1371,  821],
              [ 949, 1437],
              [ 147, 1448]])

A.shape          # (4, 2)  -> rows, columns
```
  - Is a [4 x 2] matrix
Matrix elements
- A_(i,j) = entry in i^th row and jth column

A = [\begin{matrix} 1402 & 191 \\ 1371 & 821 \\ 949 & 1437 \\ 147 & 1448 \end{matrix}]

A_{11} = 1402 A_{12} = 191

A_{32} = 1437 A_{41} = 147

A_ij is the entry in the i^th row and j^th column.

A[0, 0]          # 1402   the notes' A11
A[0, 1]          # 191    the notes' A12
A[2, 1]          # 1437   the notes' A32
A[3, 0]          # 147    the notes' A41

NumPy indexes from 0, so the notes' A₃₂ is A[2, 1] — subtract one from each index.

Provides a way to organize, index and access a lot of data

Vectors - overview

Is an n by 1 matrix
- Usually referred to as a lower case letter
- n rows
- 1 column
- e.g.

y = [\begin{matrix} 460 \\ 232 \\ 315 \\ 178 \end{matrix}]

y = np.array([460, 232, 315, 178])
y.shape          # (4,)    a 1-D array, not a column

y_col = y.reshape(4, 1)
y_col.shape      # (4, 1)  an explicit column vector

A 1-D array has no orientation — it is neither a row nor a column. Reshape when the distinction matters.

Is a 4 dimensional vector
- Refer to this as a vector R4
Vector elements
- v_i = i^thelement of the vector
- Vectors can be 0-indexed (Python, C++) or 1-indexed (maths notation)
- In math 1-indexed is most common
  - But in machine learning 0-index is useful
- Normally assume using 1-index vectors, but be aware sometimes these will (explicitly) be 0 index ones

Matrix manipulation

Addition
- Add up elements one at a time
- Can only add matrices of the same dimensions
  - Creates a new matrix of the same dimensions of the ones added

[\begin{matrix} 1 & 0 \\ 2 & 5 \\ 3 & 1 \end{matrix}] + [\begin{matrix} 4 & 0.5 \\ 2 & 5 \\ 0 & 1 \end{matrix}] = [\begin{matrix} 5 & 0.5 \\ 4 & 10 \\ 3 & 2 \end{matrix}]

M = np.array([[1, 0], [2, 5], [3, 1]])
N = np.array([[4, 0.5], [2, 5], [0, 1]])

M + N            # [[5, 0.5], [4, 10], [3, 2]]

Multiplication by scalar
- Scalar = real number
- Multiply each element by the scalar
- Generates a matrix of the same size as the original matrix

3 \times [\begin{matrix} 1 & 0 \\ 2 & 5 \\ 3 & 1 \end{matrix}] = [\begin{matrix} 3 & 0 \\ 6 & 15 \\ 9 & 3 \end{matrix}]

3 * M            # [[3, 0], [6, 15], [9, 3]]

Division by a scalar
- Same as multiplying a matrix by 1/4
- Each element is divided by the scalar
Combination of operands
- Evaluate multiplications first

3 \times [\begin{matrix} 1 \\ 4 \\ 2 \end{matrix}] + [\begin{matrix} 0 \\ 0 \\ 5 \end{matrix}] - [\begin{matrix} 3 \\ 0 \\ 2 \end{matrix}] / 3

a = np.array([1, 4, 2])
b = np.array([0, 0, 5])
c = np.array([3, 0, 2])

3 * a + b - c / 3    # [2.,  12.,  10.33333333]

Multiplication and division bind tighter than addition, so this evaluates in the order the maths above shows.

Matrix by vector multiplication
- [3 x 2] matrix * [2 x 1] vector
  - New matrix is [3 x 1]
    - More generally if [a x b] * [b x c]
      - Then new matrix is [a x c]
  - How do you do it?
    - Take the two vector numbers and multiply them with the first row of the matrix
      - Then add results together - this number is the first number in the new vector
    - Then multiply second row by vector and add the results together
    - Then multiply final row by vector and add them together

[\begin{matrix} 1 & 3 \\ 4 & 0 \\ 2 & 1 \end{matrix}] \times [\begin{matrix} 1 \\ 5 \end{matrix}] = [\begin{matrix} 16 \\ 4 \\ 7 \end{matrix}]

1 \times 1 + 3 \times 5 = 16

4 \times 1 + 0 \times 5 = 4

2 \times 1 + 1 \times 5 = 7

A [3 x 2] matrix times a [2 x 1] vector gives a [3 x 1] vector.

P = np.array([[1, 3], [4, 0], [2, 1]])   # [3 x 2]
v = np.array([[1], [5]])                 # [2 x 1]

P @ v            # [[16], [4], [7]]

@ is matrix multiplication. * multiplies element by element and is not the same thing.

Detailed explanation
- A * x = y
  - A is m x n matrix
  - x is n x 1 matrix
  - n must match between vector and matrix
    - i.e. inner dimensions must match
  - Result is an m-dimensional vector
- To get y_i - multiply A's i^throw with all the elements of vector x and add them up
Neat trick
- Say we have a data set with four values
- Say we also have a hypothesis h_θ(x) = -40 + 0.25x
  - Create your data as a matrix which can be multiplied by a vector
  - Have the parameters in a vector which your matrix can be multiplied by
- Means we can do
  - Prediction = Data Matrix * Parameters
    $h_{θ} (x) = - 40 + 0.25 x$ $[\begin{matrix} 1 & 2104 \\ 1 & 1416 \\ 1 & 1534 \\ 1 & 852 \end{matrix}] \times [\begin{matrix} - 40 \\ 0.25 \end{matrix}] = [\begin{matrix} - 40 \times 1 + 0.25 \times 2104 \\ - 40 \times 1 + 0.25 \times 1416 \\ - 40 \times 1 + 0.25 \times 1534 \\ - 40 \times 1 + 0.25 \times 852 \end{matrix}]$ Prediction = data matrix × parameters. A [4 x 2] matrix times a [2 x 1] vector gives the four predictions as a [4 x 1] vector.
```
X = np.array([[1, 2104],
              [1, 1416],
              [1, 1534],
              [1,  852]])          # data, with a column of 1s for theta_0
theta = np.array([[-40], [0.25]])  # parameters

X @ theta        # [[486.], [314.], [343.5], [173.]]
```
    The column of 1s is what lets θ₀ be carried through the multiplication.
  - Here we add an extra column to the data with 1s - this means our θ₀values can be calculated and expressed
The diagram above shows how this works
- This can be far more efficient computationally than lots of for loops
- This is also easier and cleaner to code (assuming you have appropriate libraries to do matrix multiplication)
Matrix-matrix multiplication
- General idea
  - Step through the second matrix one column at a time
  - Multiply each column vector from second matrix by the entire first matrix, each time generating a vector
  - The final product is these vectors combined (not added or summed, but literally just put together)
- Details
  - A x B = C
    - A = [m x n]
    - B = [n x o]
    - C = [m x o]
      - With vector multiplications o = 1
  - Can only multiply matrix where columns in A match rows in B
- Mechanism
  - Take column 1 of B, treat as a vector
  - Multiply A by that column - generates an [m x 1] vector
  - Repeat for each column in B
    - There are o columns in B, so we get o columns in C
- Summary
  - The i ^thcolumn of matrix C is obtained by multiplying A with the i ^thcolumn of B
- Start with an example
- A x B

[\begin{matrix} 1 & 3 & 2 \\ 4 & 0 & 1 \end{matrix}] [\begin{matrix} 1 & 3 \\ 0 & 1 \\ 5 & 2 \end{matrix}]

A2 = np.array([[1, 3, 2], [4, 0, 1]])    # [2 x 3]
B2 = np.array([[1, 3], [0, 1], [5, 2]])  # [3 x 2]

A2 @ B2          # [[11, 10], [9, 14]]   a [2 x 2]

Initially
- Take matrix A and multiply by the first column vector from B
- Take the matrix A and multiply by the second column vector from B

[\begin{matrix} 1 & 3 & 2 \\ 4 & 0 & 1 \end{matrix}] \times [\begin{matrix} 1 \\ 0 \\ 5 \end{matrix}] = [\begin{matrix} 11 \\ 9 \end{matrix}]

[\begin{matrix} 1 & 3 & 2 \\ 4 & 0 & 1 \end{matrix}] \times [\begin{matrix} 3 \\ 1 \\ 2 \end{matrix}] = [\begin{matrix} 10 \\ 14 \end{matrix}]

Each column of the result comes from multiplying A by the corresponding column of B.

A2 @ B2[:, [0]]  # [[11], [9]]   first column of B
A2 @ B2[:, [1]]  # [[10], [14]]  second column of B

Each column of the product is A times the corresponding column of B, exactly as above.

2 x 3 times 3 x 2 gives you a 2 x 2 matrix

Implementation/use

House prices, but now we have three hypotheses and the same data set
To apply all three hypotheses to all data we can do this efficiently using matrix-matrix multiplication
- Have
  - Data matrix
  - Parameter matrix
- Example
  - Four houses, where we want to predict the price
  - Three competing hypotheses
  - Because our hypotheses are one variable, to make the matrices match up we make our data (house sizes) vector into a 4x2 matrix by adding an extra column of 1s

1. h_{θ} (x) = - 40 + 0.25 x

2. h_{θ} (x) = 200 + 0.1 x

3. h_{θ} (x) = - 150 + 0.4 x

[\begin{matrix} 1 & 2104 \\ 1 & 1416 \\ 1 & 1534 \\ 1 & 852 \end{matrix}] \times [\begin{matrix} - 40 & 200 & - 150 \\ 0.25 & 0.1 & 0.4 \end{matrix}] = [\begin{matrix} 486 & 410 & 692 \\ 314 & 342 & 416 \\ 344 & 353 & 464 \\ 173 & 285 & 191 \end{matrix}]

One column of predictions per hypothesis — twelve predictions from a single matrix multiplication. Values are rounded to whole numbers, as on the original slide.

thetas = np.array([[-40, 200, -150],
                   [0.25, 0.1,  0.4]])   # one column per hypothesis

np.round(X @ thetas)
# [[486., 410., 692.],
#  [314., 342., 416.],
#  [344., 353., 464.],
#  [173., 285., 191.]]

Twelve predictions from one call — this is why the vectorized form matters.

What does this mean
- Can quickly apply three hypotheses at once, making 12 predictions
- Lots of good linear algebra libraries to do this kind of thing very efficiently

Matrix multiplication properties

Can pack a lot into one operation
- However, should be careful of how you use those operations
- Some interesting properties
Commutativity
- When working with raw numbers/scalars multiplication is commutative
  - 3 * 5 == 5 * 3
- This is not true for matrices
  - A x B != B x A
  - Matrix multiplication is not commutative
Associativity
- 3 x 5 x 2 == 3 x 10 = 15 x 2
  - Associative property
- Matrix multiplications is associative
  - A x (B x C) == (A x B) x C
Identity matrix
- 1 is the identity for any scalar
  - i.e. 1 x z = z
    - for any real number
- In matrices we have an identity matrix called I
  - Sometimes called I_{{n x n}}
    $I_{2 \times 2} = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}]$ $I_{3 \times 3} = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]$ $I_{4 \times 4} = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}]$ A different identity matrix for each set of dimensions: 1s down the diagonal, 0s everywhere else.
```
np.eye(2)        # [[1., 0.], [0., 1.]]
np.eye(3)        # 3 x 3 identity
np.eye(4)        # 4 x 4 identity

A2 @ np.eye(3)   # unchanged: [[1., 3., 2.], [4., 0., 1.]]
```
See some identity matrices above
- Different identity matrix for each set of dimensions
- Has
  - 1s along the diagonals
  - 0s everywhere else
- 1x1 matrix is just "1"
Has the property that any matrix A which can be multiplied by an identity matrix gives you matrix A back
- So if A is [m x n] then
  - A * I
    - I = n x n
  - I * A
    - I = m x m
  - (To make inside dimensions match to allow multiplication)
Identity matrix dimensions are implicit
Remember that matrices are not commutative AB != BA
- Except when B is the identity matrix
- Then AB == BA

Inverse and transpose operations

Matrix inverse
- How does the concept of "the inverse" relate to real numbers?
  - 1 = "identity element" (as mentioned above)
    - Each number has an inverse
      - This is the number you multiply a number by to get the identity element
      - i.e. if you have x, x * 1/x = 1
  - e.g. given the number 3
    - 3 * 3^-1 = 1 (the identity number/matrix)
  - In the space of real numbers not everything has an inverse
    - e.g. 0 does not have an inverse
- What is the inverse of a matrix
  - If A is an m x m matrix, then A inverse = A^-1
  - So A*A^-1 = I
  - Only matrices which are m x m have inverses
    - Square matrices only!
- Example
  - 2 x 2 matrix
    $[\begin{matrix} 3 & 4 \\ 2 & 16 \end{matrix}] [\begin{matrix} 0.4 & - 0.1 \\ - 0.05 & 0.075 \end{matrix}] = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] = I_{2 \times 2}$ A × A⁻¹ = I
```
C = np.array([[3, 4], [2, 16]])
C_inv = np.linalg.inv(C)

np.round(C_inv, 3)     # [[ 0.4  , -0.1  ], [-0.05 ,  0.075]]
np.round(C @ C_inv)    # [[1., 0.], [0., 1.]]  -> the identity
```
    In practice prefer np.linalg.solve(C, b) to inv(C) @ b — it is faster and numerically better behaved. A singular matrix raises LinAlgError.
  - How did you find the inverse
    - Turns out that you can sometimes do it by hand, although this is very hard
    - Numerical software for computing a matrix's inverse
      - Lots of open source libraries
- If A is all zeros then there is no inverse matrix
  - Some others don't, intuition should be matrices that don't have an inverse are a singular matrix or a degenerate matrix (i.e. when it's too close to 0)
  - So if all the values of a matrix reach zero, this can be described as reaching singularity
Matrix transpose
- Have matrix A (which is [n x m]) how do you change it to become [m x n] while keeping the same values
  - i.e. swap rows and columns!
- How you do it;
  - Take first row of A - becomes 1st column of A^T
  - Second row of A - becomes 2nd column...
- A is an m x n matrix
  - B is a transpose of A
  - Then B is an n x m matrix
  - A_(i,j) = B_(j,i)

A = [\begin{matrix} 1 & 2 & 0 \\ 3 & 5 & 9 \end{matrix}] A^{T} = [\begin{matrix} 1 & 3 \\ 2 & 5 \\ 0 & 9 \end{matrix}]

The first row of A becomes the first column of A^T, and so on.

D = np.array([[1, 2, 0], [3, 5, 9]])

D.T              # [[1, 3], [2, 5], [0, 9]]
D.shape, D.T.shape   # ((2, 3), (3, 2))