C14008 Lesson 2: Linear Algebra

What's poppin class! Welcome to Julia (pt. 2). Today we are learnin' all about linear algebra and matricies. Julia (and machine learning, for those of you that are intrested) is built around linear algebra, so this is a pretty important one.

Warm up

Euler 16

You will (probably) need the following:

  • the sum() function
  • the digits() function
  • BigInts
In [3]:
# Euler 16 code goes here

sum(digits(BigInt(2)^1000))
Out[3]:
1366

Questions from last week? New questions?

Presentations

Who did the homework? We want to see your solutions and hear about any road blocks y'all may have run into.

Problems to present:

  • Euler 1
  • Euler 2
  • Euler 4
  • Euler 6
  • Euler 8
  • Euler 9

Introduction to Linear Algebra (with Julia)

To talk about Linear Algebra, we first need to talk about matrices. A matrix is a series of numbers, arranged in a grid of rows and columns, like so.

In [3]:
# generating matrices with Julia
a = [1 2
     3 4]

a = [1 2 6; 3 4 5]
Out[3]:
2×3 Array{Int64,2}:
 1  2  6
 3  4  5

The following operations are defined for matrices: addition, subtraction, and multiplication.

In [9]:
# matrix operations in Julia
a = [5 6; 7 8]
b = [1 2; 3 4]

# two types of multiplication
# multiplying elements w/broadcast
a .* b

# multiplying properly, rows by columns
a * b
Out[9]:
2×2 Array{Int64,2}:
 23  34
 31  46

That's right, we can multiply matrices in two ways. Typical matrix multiplication (the kind from linear algebra) involves multiplying rows by columns, like so: $$ \begin{bmatrix} \color{red}{1} & \color{red}{4} \\ 3 & 1 \end{bmatrix} \begin{bmatrix} \color{red}{3} \\ \color{red}{2} \end{bmatrix} = \begin{bmatrix} \color{red}{11} \\ 11 \end{bmatrix} $$ We can do matrix multiplication as long as the number of columns of the first matrix matches the number of rows of the second matrix.

2x2 2x1 # matching dimensions for matrix multiplication

Accessing matrices

To access the values of a matrix, we access one dimension at a time. : allows us to select the entire range, while 1 refers to the first index and end refers to the last index.

In [6]:
m = [1 2 3
     4 5 6
     7 8 9]

# accessing a matrix
m[2,2]
m[2:3,2:end]
m[2,end-1]
m[1,end:-1:1]
Out[6]:
3-element Array{Int64,1}:
 3
 2
 1

Representing Vectors

$n$-dimensional vectors in Linear Algebra are typically a matrix of $n$ rows by one column. This is called a column vector. An 1 by $n$ matrix is called a row vector. Julia represents all arrays as column vectors.

In [7]:
# arrays as column vectors
[1,2,3]
Out[7]:
3-element Array{Int64,1}:
 1
 2
 3

Take the following series of linear equations: $$ \begin{align} 3x + y &= 8 \\ x - 2y &= -2 \end{align} $$

We can represent these equations as a matrix-vector product (a matrix multiplied by a column vector), using the method of multplication shown above:

$$ \begin{bmatrix} 3 & 1 \\ 1 & -2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 8 \\ -2 \end{bmatrix} $$

To solve this equation, we can use Julia to find the "inverse" of this matrix and multiply it by (8, 2).

In [1]:
# solve eqn with Julia inv

B = [3 1 ; 1 -2]

inv(B)

inv(B) * [8,-2]

# solve eqn with Julia \ operator

B\[8, -2]
Out[1]:
2-element Array{Float64,1}:
 2.0
 1.9999999999999996

Eigenvalues and Eigenvectors

Let matrix $A$ be the matrix below:

In [12]:
A = [1 -1
     2  4]
Out[12]:
2×2 Array{Int64,2}:
 1  -1
 2   4

Notice that if we multiply $A$ by certain vectors (specifically (1, -1) and (1, -2)), we get scaled versions of these vectors back. Eigenvalues and eigenvectors have the property that: $$ A\vec{v} = \lambda\vec{v} $$ where $\lambda$ is an eigenvalue and $\vec{v}$ is its corresponding eigenvector.

Julia gives us eigenvalues and their eigenvectors for a given matrix with the function eigen() in the LinearAlgebra package.

In [13]:
using LinearAlgebra # how to import a package in Julia

# Using eigen with A

eigen(A)
Out[13]:
Eigen{Float64,Float64,Array{Float64,2},Array{Float64,1}}
values:
2-element Array{Float64,1}:
 2.0
 3.0
vectors:
2×2 Array{Float64,2}:
 -0.707107   0.447214
  0.707107  -0.894427
In [17]:
# Demonstrating eigenvectors with A

A * [1,-2]
Out[17]:
2-element Array{Int64,1}:
  3
 -6

Transpose Operator

Julia supplies the ' as a adjoint operator. For real numbers this is simply a transpose operator. Transposing a matrix switches its rows and columns. For imaginary numbers this also replaces each number with its complex conjugate. Alternatively you can use transpose.

In [21]:
# Demonstrate transpose

A = [1 2 3 ; 4 5 6]

A'
Out[21]:
3×2 Adjoint{Int64,Array{Int64,2}}:
 1  4
 2  5
 3  6

Dot and Cross Product

The LinearAlgebra package also provides dot and cross product operators for you to use at your convenience.

In [25]:
# Using dot and cross

dot([1 2 3], [4 5 6])
Out[25]:
32

Matrices With Julia

Remember we can initialize vectors and matricies with Julia using array comprehension. For a 2-D matrix, you just need two variables.

In [27]:
# Vector created from array comprehension
[n for n in 1:10]

# Matrix created from array comprehension
[x+2y for x in 1:2, y in 0:1]
Out[27]:
2×2 Array{Int64,2}:
 1  3
 2  4

Definitely something to get the hang of, it comes in very handy.

Map & Broadcast

What if I want to add 5 to every element in the array [1,2,3]?

In [28]:
B = [n for n in 1:3] # Array comprehension ;)

# Try (notice the error)

5 + B
MethodError: no method matching +(::Int64, ::Array{Int64,1})
Closest candidates are:
  +(::Any, ::Any, !Matched::Any, !Matched::Any...) at operators.jl:529
  +(::T, !Matched::T) where T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8} at int.jl:53
  +(::Union{Int16, Int32, Int64, Int8}, !Matched::BigInt) at gmp.jl:528
  ...

Stacktrace:
 [1] top-level scope at In[28]:2
In [29]:
# Using broadcast(operator, thing to add, matrix)
broadcast(+, 5, B)
Out[29]:
3-element Array{Int64,1}:
 6
 7
 8

Broadcast can conveniently be represented by a ..

In [36]:
# Using . as broadcast
5 .+ B

5 .+ [1 2 ; 3 4]
Out[36]:
2×2 Array{Int64,2}:
 6  7
 8  9

The other similar function is map. map takes in three inputs like broadcast but it converts everything to the dimension of the second input. For example

In [37]:
# Try to use map like broadcast

map(+, 5, B)
Out[37]:
1-element Array{Int64,1}:
 6
In [39]:
C = [2 for n in 4:6]

# Lets add the elements of B to C using map
map(+, B, C)
Out[39]:
3-element Array{Int64,1}:
 3
 4
 5

These functions also work on matrices

In [40]:
# Broadcast in 2 dimensions
5 .+ [1 2 3 ; 4 5 6]
Out[40]:
2×3 Array{Int64,2}:
 6   7   8
 9  10  11
In [41]:
# Map in 2 dimensions
map(+, [5 5 5 ; 5 5 5], [1 2 3 ; 4 5 6])
Out[41]:
2×3 Array{Int64,2}:
 6   7   8
 9  10  11

push!, pop!, and pushfirst!

We (Cameron) went over some of these last time, but it is worth a recap. Remember that ! means the function alters its input vector.

  • push!(vector, element) pushes an element to the back of a vector
  • pop!(vector) removes the first element from a vector
  • pushfirst!(vector, element) pushes an element to the front of a vector
In [43]:
pushPop = [n for n in 2:7]

# push 8 to pushPop
push!(pushPop, 8)
Out[43]:
7-element Array{Int64,1}:
 2
 3
 4
 5
 6
 7
 8
In [45]:
# pop pushPop
pop!(pushPop)
pushPop
Out[45]:
6-element Array{Int64,1}:
 2
 3
 4
 5
 6
 7
In [46]:
# put 1 at the front of pushPop
pushfirst!(pushPop, 1)
Out[46]:
7-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
 7

Other Very Useful Operations

Remember, if you think an matrix function should exist in Julia, it probably does. These next three functions are three of my most used and favorites (cough cough they will be useful on the homework).

  • digits(int) converts an integer to a vector made up of its digits
  • circshift(vector, times to shift) rotates a vector, rotating the back elements to the front
  • diag(matrix) returns the diagonal of the matrix
In [48]:
n = 987654321

# Demonstrate digits() on n, notice how the least signifigant digit is at the [1] position
digs = digits(n)
Out[48]:
9-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
 7
 8
 9
In [49]:
# Demonstrate circshift on the digits() vector
circshift(digs, 3)
Out[49]:
9-element Array{Int64,1}:
 7
 8
 9
 1
 2
 3
 4
 5
 6
In [50]:
A = [1 2 3 ; 4 5 6 ; 7 8 9] # Array to demonstrate diag on
Out[50]:
3×3 Array{Int64,2}:
 1  2  3
 4  5  6
 7  8  9
In [54]:
using LinearAlgebra # diag is a LinearAlgebra thing
# Demonstrate diag(A) and diag(A, 1) and diag(A, -1)
diag(A, -1)
Out[54]:
2-element Array{Int64,1}:
 4
 8

What if I want to access the opposite diagonal (the one running from the top right to the bottom left)?

Well, we can do this. The part before the comma is how we want to read the rows. Writing end:-1:1 reverses the order the rows appear (the last one will appear on top, etc). The part after the comma is how we want to read the columns, and we want those to stay the same so : will work. A single colon just means 1:end.

Not going to lie, this is a little complicated and it is ok if you cannot wrap your head around it, I am only presenting it to you because it us important when you will need to read an array's backwards diagonal in the homework.

In [57]:
diag(A[end:-1:1,:]) # grabs the reverse diagonal from A
Out[57]:
3-element Array{Int64,1}:
 7
 5
 3

vcat and hcat

Ok one last set of functions before we go. vcat stands for vertical concatenate and hcat is horizontal concatenate. They can take in vectors or matrices and concatenate them, given the dimensions match (number of rows must be the same for hcat and number of columns must be the same for vcat).

In [59]:
peanutButter = [1 2 ; 3 4]
jelly = [5 6 ; 7 8]

# hcat peanutButter and jelly
hcat(peanutButter, jelly)
Out[59]:
2×4 Array{Int64,2}:
 1  2  5  6
 3  4  7  8
In [60]:
# vcat peanutButter and jelly
vcat(peanutButter, jelly)
Out[60]:
4×2 Array{Int64,2}:
 1  2
 3  4
 5  6
 7  8

Homework

Enough Lecture! Good luck on the homework!

Euler 35 (Circular Primes)

https://projecteuler.net/problem=35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

In [ ]:
using Primes
prime = primes(1000000) # prime is now a vector of all the primes below 1,000,000... we will teach you how to use the Primes package later :)

# Euler 35 code goes here

Euler 30 (5th Power Digits)

https://projecteuler.net/problem=30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

$$1634 = 1^4 + 6^4 + 3^4 + 4^4$$$$8208 = 8^4 + 2^4 + 0^4 + 8^4$$$$9474 = 9^4 + 4^4 + 7^4 + 4^4$$

As $1 = 1^{4}$ is not a sum it is not included.

The sum of these numbers is $1634 + 8208 + 9474 = 19316$.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

In [ ]:
# Euler 30 code goes here

Euler 11

https://projecteuler.net/problem=11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

We will be spending a good portion of next week's class on this problem, so we strongly suggest you at least attempt it. Feel free to email us with any and all questions. Go get that sweet, sweet checkmark!

Requirement: Y'all's solution should look through every possible product and then return the largest one.

Hint: the "Other Very Useful Operations" section should be very useful for this problem

In [62]:
# Euler 11 code goes here