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.
# Euler 16 code goes here
sum(digits(BigInt(2)^1000))
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:
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.
# generating matrices with Julia
a = [1 2
3 4]
a = [1 2 6; 3 4 5]
The following operations are defined for matrices: addition, subtraction, and multiplication.
# 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
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.
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.
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]
$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.
# arrays as column vectors
[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).
# solve eqn with Julia inv
B = [3 1 ; 1 -2]
inv(B)
inv(B) * [8,-2]
# solve eqn with Julia \ operator
B\[8, -2]
Let matrix $A$ be the matrix below:
A = [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.
using LinearAlgebra # how to import a package in Julia
# Using eigen with A
eigen(A)
# Demonstrating eigenvectors with A
A * [1,-2]
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.
# Demonstrate transpose
A = [1 2 3 ; 4 5 6]
A'
The LinearAlgebra package also provides dot and cross product operators for you to use at your convenience.
# Using dot and cross
dot([1 2 3], [4 5 6])
Remember we can initialize vectors and matricies with Julia using array comprehension. For a 2-D matrix, you just need two variables.
# 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]
Definitely something to get the hang of, it comes in very handy.
What if I want to add 5 to every element in the array [1,2,3]?
B = [n for n in 1:3] # Array comprehension ;)
# Try (notice the error)
5 + B
# Using broadcast(operator, thing to add, matrix)
broadcast(+, 5, B)
Broadcast can conveniently be represented by a ..
# Using . as broadcast
5 .+ B
5 .+ [1 2 ; 3 4]
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
# Try to use map like broadcast
map(+, 5, B)
C = [2 for n in 4:6]
# Lets add the elements of B to C using map
map(+, B, C)
These functions also work on matrices
# Broadcast in 2 dimensions
5 .+ [1 2 3 ; 4 5 6]
# Map in 2 dimensions
map(+, [5 5 5 ; 5 5 5], [1 2 3 ; 4 5 6])
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 vectorpop!(vector) removes the first element from a vectorpushfirst!(vector, element) pushes an element to the front of a vector pushPop = [n for n in 2:7]
# push 8 to pushPop
push!(pushPop, 8)
# pop pushPop
pop!(pushPop)
pushPop
# put 1 at the front of pushPop
pushfirst!(pushPop, 1)
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 digitscircshift(vector, times to shift) rotates a vector, rotating the back elements to the frontdiag(matrix) returns the diagonal of the matrixn = 987654321
# Demonstrate digits() on n, notice how the least signifigant digit is at the [1] position
digs = digits(n)
# Demonstrate circshift on the digits() vector
circshift(digs, 3)
A = [1 2 3 ; 4 5 6 ; 7 8 9] # Array to demonstrate diag on
using LinearAlgebra # diag is a LinearAlgebra thing
# Demonstrate diag(A) and diag(A, 1) and diag(A, -1)
diag(A, -1)
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.
diag(A[end:-1:1,:]) # grabs the reverse diagonal from A
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).
peanutButter = [1 2 ; 3 4]
jelly = [5 6 ; 7 8]
# hcat peanutButter and jelly
hcat(peanutButter, jelly)
# vcat peanutButter and jelly
vcat(peanutButter, jelly)
Enough Lecture! Good luck on the homework!
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?
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
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.
# Euler 30 code goes here
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 48The 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
# Euler 11 code goes here