{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# C14008 Lesson 2: Linear Algebra" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Warm up\n", "### Euler 16\n", "You will (probably) need the following:\n", "- the sum() function\n", "- the digits() function\n", "- BigInts" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Euler 16 code goes here\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Questions from last week? New questions?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Presentations\n", "Who did the homework? We want to see your solutions and hear about any road blocks y'all may have run into.\n", "\n", "Problems to present:\n", "- Euler 1\n", "- Euler 2\n", "- Euler 4\n", "- Euler 6\n", "- Euler 8\n", "- Euler 9" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction to Linear Algebra (with Julia)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# generating matrices with Julia\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following operations are defined for matrices: addition, subtraction, and multiplication." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# matrix operations in Julia\n", "\n", "# two types of multiplication\n", "# multiplying elements w/broadcast\n", "\n", "\n", "# multiplying properly, rows by columns\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:\n", "$$\n", "\\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}\n", "$$\n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Accessing matrices\n", "To access the values of a matrix, we access one dimension at a time. : allows us to select the entire range, while start refers to the first index and end refers to the last index." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m = [1 2 3\n", " 4 5 6\n", " 7 8 9]\n", "\n", "# accessing a matrix" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Representing Vectors\n", "\n", "$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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# arrays as column vectors\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Take the following series of linear equations:\n", "\n", "\\begin{align}\n", "3x + y &= 8 \\\\\n", "x - 2y &= -2\n", "\\end{align}\n", "\n", "\n", "We can represent these equations as a _matrix-vector product_ (a matrix multiplied by a column vector), using the method of multplication shown above:\n", "\n", "$$\n", "\\begin{bmatrix} 3 & 1 \\\\ 1 & -2 \\end{bmatrix} \\begin{bmatrix} x \\\\ y \\end{bmatrix} = \\begin{bmatrix} 8 \\\\ -2 \\end{bmatrix}\n", "$$\n", "\n", "To solve this equation, we can use Julia to find the \"inverse\" of this matrix and multiply it by (8, 2)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# solve eqn with Julia inv\n", "\n", "# solve eqn with Julia \\ operator" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Eigenvalues and Eigenvectors\n", "Let matrix $A$ be the matrix below:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "A = [1 -1\n", " 2 4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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}$$\n", "where $\\lambda$ is an **eigenvalue** and $\\vec{v}$ is its corresponding **eigenvector**.\n", "\n", "Julia gives us eigenvalues and their eigenvectors for a given matrix with the function eigen() in the LinearAlgebra package." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "using LinearAlgebra # how to import a package in Julia\n", "\n", "# Using eigen with A" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Demonstrating eigenvectors with A\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Transpose Operator\n", "Julia supplies the ' as a _transpose_ operator. Transposing a matrix switches its rows and columns." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Demonstrate transpose" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dot and Cross Product\n", "The LinearAlgebra package also provides dot and cross product operators for you to use at your convenience." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Using dot and cross" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Matrices With Julia\n", "Remember we can initialize vectors and matricies with Julia using _array comprehension_. For a 2-D matrix, you just need two variables." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Vector created from array comprehension\n", "\n", "\n", "# Matrix created from array comprehension\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Definitely something to get the hang of, it comes in _very_ handy." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Map & Broadcast\n", "What if I want to add 5 to every element in the array [1,2,3]?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "B = [n for n in 1:3] # Array comprehension ;)\n", "\n", "# Try (notice the error)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Using broadcast(operator, thing to add, matrix)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Broadcast can conveniently be represented by a .. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Using . as broadcast" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Try to use map like broadcast\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "C = [2 for n in 4:6]\n", "\n", "# Lets add the elements of B to C using map" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These functions also work on matrices" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Broadcast in 2 dimensions\n", "5 .+ [1 2 3 ; 4 5 6]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Map in 2 dimensions\n", "map(+, [5 5 5 ; 5 5 5], [1 2 3 ; 4 5 6])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## push!, pop!, and pushfirst!\n", "We (Cameron) went over some of these last time, but it is worth a recap. Remember that ! means the function alters its input vector.\n", "- push!(vector, element) pushes an element to the back of a vector\n", "- pop!(vector) removes the first element from a vector\n", "- pushfirst!(vector, element) pushes an element to the front of a vector " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "pushPop = [n for n in 2:7]\n", "\n", "# push 8 to pushPop\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# pop pushPop\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# put 1 at the front of pushPop\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Other Very Useful Operations\n", "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).\n", "\n", "- digits(int) converts an integer to a vector made up of its digits\n", "- circshift(vector, times to shift) rotates a vector, rotating the back elements to the front\n", "- diag(matrix) returns the diagonal of the matrix" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n = 987654321\n", "\n", "# Demonstrate digits() on num, notice how the least signifigant digit is at the  position\n", "digits(n)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Demonstrate circshift on the digits() vector\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "A = [1 2 3 ; 4 5 6 ; 7 8 9] # Array to demonstrate diag on" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "using LinearAlgebra # diag is a LinearAlgebra thing\n", "# Demonstrate diag(A) and diag(A, 1) and diag(A, -1)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What if I want to access the opposite diagonal (the one running from the top right to the bottom left)?\n", "\n", "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.\n", "\n", "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. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "diag(A[end:-1:1,:]) # grabs the reverse diagonal from A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## vcat and hcat\n", "\n", "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)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "peanutButter = [1 2 ; 3 4]\n", "jelly = [5 6 ; 7 8]\n", "\n", "# hcat peanutButter and jelly\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# vcat peanutButter and jelly\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercises\n", "Enough Lecture!\n", "\n", "### Euler 35 (Circular Primes)\n", "> https://projecteuler.net/problem=35\n", "\n", ">The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.\n", ">\n", ">There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.\n", ">\n", ">How many circular primes are there below one million?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "using Primes\n", "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 :)\n", "\n", "# Euler 35 code goes here\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Euler 30 (5th Power Digits)\n", "> https://projecteuler.net/problem=30\n", "\n", ">Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:\n", ">\n", ">$$1634 = 1^4 + 6^4 + 3^4 + 4^4$$\n", "$$8208 = 8^4 + 2^4 + 0^4 + 8^4$$\n", "$$9474 = 9^4 + 4^4 + 7^4 + 4^4$$\n", ">As $1 = 1^{4}$ is not a sum it is not included.\n", ">\n", ">The sum of these numbers is $1634 + 8208 + 9474 = 19316$.\n", ">\n", ">Find the sum of all the numbers that can be written as the sum of fifth powers of their digits." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Euler 30 code goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Homework\n", "\n", "### Euler 11\n", "> https://projecteuler.net/problem=11\n", "\n", "> In the 20×20 grid below, four numbers along a diagonal line have been marked in red.\n", ">\n", ">
\n",
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n",
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n",
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n",
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n",
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n",
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n",
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n",
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n",
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n",
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n",
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n",
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n",
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n",
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n",
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n",
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n",
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n",
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n",
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n",
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48\n",
"
\n", ">\n", "> The product of these numbers is 26 × 63 × 78 × 14 = 1788696.\n", ">\n", "> What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?\n", "\n", "\n", "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!\n", "\n", "Requirement: Y'all's solution should look through every possible product and then return the largest one.\n", "\n", "Hint: the \"Other Very Useful Operations\" section should be _very useful_ for this problem\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Euler 11 code goes here" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.4.2", "language": "julia", "name": "julia-1.4" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.4.2" } }, "nbformat": 4, "nbformat_minor": 4 }