13 ms·

Linear algebra tutorial in four pages

256 points by ivan_ah 13y ago

ivan_ah 13y ago
Good luck to anyone who has a linear algebra exam coming up! I also have a similar short tutorial for Newtonian mechanics here: http://cnd.mcgill.ca/~ivan/miniref/mech_in_7_pages.pdf http://cnd.mcgill.ca/~ivan/miniref/mech_in_7_pages.pdf
- whitewhim 13y ago
  LinAlg 2 coming up in two days. Its a fun course!
nathan-wailes 13y ago
thanks for the post, i've been trying to learn linear algebra for a long time but keep getting stuck / bored.
- dergachev 13y ago
  For me what makes it really interesting is the realization that all of linear regression (think y = mx + b) is based on linear algebra, specifically the notion that figuring out a best-fit line (in the case of a single-dimensional input variable) is projection of the N-dimensional vector space of observations (where you have N data points) onto the best-fitting 2 dimensional vector spaces (assuming you're fitting a slope and an intercept). When thought of this way, a lot of linear algebra has geometric interpretations and for me this makes it a lot less abstract.
  - graycat 13y ago
    Nearly everything in linear algebra has important geometric interpretations. In addition, a lot that works in the 3-space we live in (for the non-relativistic approximation) generalizes to linear algebra, vector spaces more generally, and, in particular, both Hilbert space and Banach space.
  - ivan_ah 13y ago
    Yeah, dergachev is pointing to one of the cool direct applications of linear algebra to machine learning. Suppose you are given the data D = (r_1; r_2; r_3) where each row r_i is an n-vector r_i=(a_i1, a_i2, ..., a_in, b_i). Each row consists of some observation data. We want to predict future b_j given the future \vec{a}_j, given that we have seen {r_i}_{i=1...N} (The data set consists of N data rows r_i where both \vec{a}_i and b_i are known). One simple model for b_j given \vec{a}_i = \vec{a}_i = (a_i1, a_i2, ..., a_in) is a linear model with $n$ parameters m_1,m_2,...,m_n: y_m(x_1,...x_n) = m_1x_1 + m_2x_2 + ... + m_nx^n = \vec{m} · \vec{x} If the model is good then y_m(\vec{a}_i) approximates b_i well. But startup wisdom dictates that we should measure everything! Enter error term: e_i(\vec{m}) = |y_m(\vec{a}_i) - b_i|², the squared absolute-value of the difference between the model's prediction and the actual output---hence the name error term. Our goal is to make the sum $S$ of all the error terms as small as possible. S(\vec{m}) = \sum_{i=1}^{i=M} e_i(\vec{m}) Note that the "total squared error" is a function of the model parameters \vec{m}. At this point we have reached a level of complexity that becomes difficult to follow. Linear algebra to the rescue! We can express the "vector prediction" of the model y_m in "one shot" in terms of the following matrix equation: A\vec{m} = \vec{b} where A is an N by n matrix (contains the a_:: part of the data) \vec{m} is an n by 1 vector (model parameters---the unknown) \vec{b} is an N by 1 vector (contains the b_: part of the data) To find \vec{m}, we must solve this matrix equation, however A is not a square matrix: A is a tall skinny matrix N >> n, so there is no A^{-1}. Okay so we don't have a A^{-1} to throw at the equation A\vec{m}=\vec{b} to cancel the A, but what else could we throw at it. Let's throw A^T at it! A^T A \vec{m} = A^T \vec{b} \ / N (an n by n matrix) N \vec{m} = A^T \vec{b} Now the thing to observe is that if N is invertible, then we can find \vec{m} using \vec{m} = N^{-1} A^T \vec{b} This solution to the problem is known as the "least squares fit" solution (i.e. choice of parameters for the model m_1, m_2, ..., m_n). This name comes from the fact that the vector \vec{m} is equal to the output of the following optimization problem \vec{m} = minimize S(\vec{m}) over all \vec{m} Proof: http://en.wikipedia.org/wiki/Linear_least_squares_(mathematics)#Derivation_directly_in_terms_of_matrices http://en.wikipedia.org/wiki/Linear_least_squares_(mathemati... Technical detail: the matrix N=A^T*A is invertible if and only if the columns of A are linearly independent. TL;DR. When you have to do a "linear regression" model of data matrix X and labels \vec{y}, the best (in the sense of least squared error) linear model is \vec{m} = (X^T X)^{-1} X^T \vec{y}.
  - LateNightCoder 13y ago
    Can you please post the tex associated with the pdf? Thanks in advance.
dergachev 13y ago
I really enjoyed the Gilbert Strang videos on linear algebra back when I was taking the course at McGill: http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/ http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-...
- aet 13y ago
  Yes, very entertaining and enlightening (even if you already know the subject). Love Strang's teaching style.
  - blt 13y ago
    I agree, his lecture deriving the determinant from a few desirable properties is a classic in my mind.
- clebio 13y ago
  He has an exceedingly dry sense of humor. It's quite nice, when you're 40 minutes into an involved lecture. The series is indeed worth the watch.
graycat 13y ago
Roger Horn is one of the best linear algebra and matrix guys around, and I was, by wide margins, the star student in his class, effortlessly. For the notes, I found serious problems in just the first half of the first column on the first page. F'get about the four pages. If enough people want an outline in a few pages, then I'll consider knocking one out and putting up somewhere as a PDF file.
- yagibear 13y ago
  I'd be keen to see your outline.
- recuter 13y ago
  Please do.
- eskimo87 13y ago
  interested!
- Arnor 13y ago
  I'd appreciate that. My linear algebra is extremely basic (all picked up as needed for an AI course). Any well-rounded ground up resources would be awesome.
- AceJohnny2 13y ago
  Adding a request.
- glomph 13y ago
  And modest too.
  - graycat 13y ago
    Horn wrote about my work, "Best performance in the course throughout the semester. Knows this material cold." It was just true. Why? It was an 'advanced' course in linear algebra and matrix theory, and I'd never had even a first course in the subject. But long before the course, in total I'd done much more than just such a course. I had had two good courses in abstract algebra, each of which had provided a good foundation for linear algebra and also touched on the subject. I had taken a reading course in theoretical physics based heavily on matrix theory. And I had written my undergraduate honors paper on group representation theory, essentially in linear algebra. I'd worked carefully through two of the best books on linear algebra, one by E. Nearing and the other by P. Halmos. The Halmos book is famous as the crown jewel of books on linear algebra. Why? It can be good to look at linear algebra as a baby version of Hilbert space theory, heavily from von Neumann, and Halmos wrote his book when he was an assistant to von Neumann at the Institute for Advanced Study. So, deliberately, the Halmos book is an introduction to Hilbert space theory. It also has the profound perspective of one of the best mathematicians of all time and the elegance of thought of von Neumann. For applications, in my career and in my own study, I'd worked through stacks of books and papers on applications in numerical linear algebra, multivariate statistics, optimization, curve fitting, signal processing, especially around the fast Fourier transform, differential equations, advanced calculus, deterministic optimal control theory, exterior algebra, etc. At one point I wrote my own notes on much of linear algebra, with black ink on white paper, 100% cotton I got especially for the notes. My work was very careful although not elegant. For review, just before the course, I wrote out from memory 80 pages covering about 2/3rds of the course. As Horn wrote, I knew the subject cold, long before I took his course. Horn's homework, tests, and final exam were all challenging for the other students, and I effortlessly blew them away, by large margins on all three. E.g., I never studied for the tests or either the mid-term or final exam. When doing the homework, I nearly never looked at my notes from class and, instead, just wrote out the solutions based on what I already knew. I didn't belong in the course and had told the department that at the beginning. The department's reaction was to smile and say "Take the course anyway.". So, I did. For me, the course was a huge waste: From a long commute to campus and taking care of my wife, I was short on time, but the Horn homework had me up nearly all night and then exhausted the next day once a week and, thus, ate into a big fraction of the best time I had each week. Some of my other, more important work suffered. When I did the Horn homework, I was usually just exhausted. I'd get the papers back, graded, in about two weeks, recognize my handwriting, but, from having been so tired, actually had no memory of having done the work. Bummer. It was a trial by fire and exhaustion, not education. I was being asked to 'prove myself', not learn something. In the program, I only wanted to learn some good material and had no desire at all to 'compete', certainly not in that linear algebra course beneath me. I didn't know I was blowing away the other students until the grader showed me the scores on homework and tests, all except the final exam. In many ways Horn was a very good teacher, but, in total, he blew away nearly all the students. If I hadn't already known the material coming into the course, then I couldn't have learned it in the course. The way I had learned the material was from some slow, careful, thoughtful study and a lot of work with applications, and the course offered neither.
j2kun 13y ago
A few minor mistakes (perhaps just in my eyes), but overall pretty good. The hardest part about teaching linear algebra is that nobody explains the big picture. I teach mathematics and computer science and regularly tutor linear algebra students, and I encounter students all the time who ask me "What are vectors good for? I thought all we cared about were matrices and doing RREF and stuff." For this reason, I deemphasize computations and emphasize the connection between linear maps and matrices. It can be summed up as follows: if you fix a basis, every linear map is a matrix and every matrix is a linear map, and operations on functions (like composition, inversion, whatever) correspond to operations on the corresponding matrices. It's definitely not an analogy or anything in "scare quotes" that would imply something different is going on behind the scenes. It's exactly the same thing. Other questions usually left out of discussions about linear algebra (and these notes): what are orthogonal vectors good for? Why would we ever want a basis besides the standard basis in real Euclidean space? Is Euclidean space the only vector space out there? Do vectors have to be lists of numbers?
- infogulch 13y ago
  So... are you going to answer them?
  - dominotw 13y ago
    Gilbert Strang explains clearly why we need change of basis with an example of image compression here, http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-31-change-of-basis-image-compression/ http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-...
    - infogulch 13y ago
      How about "Is Euclidean space the only vector space out there?" And "Do vectors have to be lists of numbers?" Perhaps with some examples?
      - mej10 13y ago
nilkn 13y ago
As someone with a math degree, I love this. However, I think the author over-estimates the familiarity of a typical high school student with mathematical notation: > The only prerequisite for this tutorial is a basic understanding of high school math concepts I think fundamentally the material in these four pages is accessible to many high school graduates, but perhaps not in this concise rendering (which is awesome for me, but probably overwhelming for someone not familiar with set-theoretic notation, summation notation, etc.).
- ivan_ah 13y ago
  You are right. I am totally trying to sneak in the \in and the \mathbb{R}'s in there to see if people will notice. Previously I had \forall in there too, but went over and removed things. On the TODO list is to introduce the { obj | obj description } notation for defining sets (in this case vector spaces).
  - Steuard 13y ago
    Well, I noticed! It stood out pretty clearly, I'd say. I really don't think that the intended audience of this sort of ground-up summary is going to be comfortable with \mathbb{R}^{m\times n} notation all over the place. Yes, you explain what the notation means, but there's zero chance that a reader who didn't already know that notation will become fluent in it right away: they're going to be flipping back to the definition every time. That might be okay if you're trying to teach all of math, but a person reading "Linear Algebra in Four Pages" presumably neither wants nor needs that full skill set. (I'd say that {obj|obj description} notation would make the text even more opaque to novices, no matter how cleanly introduced.) Why not just make a less precise reference to a table of "numbers" (which, as an added bonus, would leave the door open to complex matrices without having to start from scratch)?
- 001sky 13y ago
  Twist: This is a great argument to teach notation earlier !
starstart 13y ago
In page 3, section B. Using elementary matrices: To remember what matrix correspond to a row operation just apply that operation to the identity matrix and you obtain the elementary associated matrix.
tdicola 13y ago
Very cool, I like title of the associated book "No Bullshit Guide To Linear Algebra" too. Does anyone know of a nice, short summary of discrete mathematics to go along with this?
starstart 13y ago
Suppose that you want to project a vector of data (x1,x2,x3,...,xn) into the one dimensional subspace generated by the vector (1,1,...,1). What's the projection in this case? Hint: You obtain the most important concept of statistics.
starstart 13y ago
Suppose that you are driving a car and you are hit with a big tree. The main eigenvector is in the direction from the car to the tree, the eigenvalue measures the deformation of the car produced by this accident. If the car is a half shorter after the accident then the eigenvalue is 1/2.
mrcactu5 13y ago
Courses would benefit from "quick-reference guides like the end of Dror Bar Natan's paper on Khovanov homology http://arxiv.org/abs/math/0201043 http://arxiv.org/abs/math/0201043 He says "It can fit inside your wallet." See: http://www.math.toronto.edu/drorbn/Talks/HUJI-011104/cube.gif http://www.math.toronto.edu/drorbn/Talks/HUJI-011104/cube.gi...
elvinmelvin 13y ago
Just to throw this out there in the hope it is useful, I have been using this book as a review of linear algebra: http://linear.ups.edu/html/fcla.html http://linear.ups.edu/html/fcla.html
- ivan_ah 13y ago
  +1 This book is awesome! The entire text is interspersed with collapsable examples and exercises.
michaelchum 13y ago
Wow amazing stuff here, I agree with you that most math textbooks in our education system fail to explain concepts which are supposed to be very simple. Thank you so much for making things simpler. I'm having MATH 270 final next week at McGill, this is going to help a lot in studying :)
baby 13y ago
erk, I don't think condensing much information in the smallest place possible is the best way to learn something (or even review it). I'm all for a no bullshit and quick way to get something. That's why I sometimes check learnXinYminutes.com or some random cheatsheets on Google. But this doesn't make it for me. Btw, if you really want to get a good grasp on Linear Algebra you should check Gilbert Strang's video courses on MIT OpenCourseWare. They are amazing and soooo easy to understand you don't even need to like mathematics to watch them. I haven't come across a better support to start with Linear Algebra.
- luuse 13y ago
  Course codes 18.06SC and 18.06 i think if anyone else was looking. Thanks for the pointer, really appreciated!
  - udit99 13y ago
    Got excited for a moment...then did some prerequisites digging and ended up with a prerequisites dependency chain: 18.06 -> 18.02 -> 18.01 Where 18.02 = Multi Variable Calc 18-01 = Single Variable Calc Considering that my whole point of learning linear algebra was to clear it as a roadblock for Machine Learning, this is what my whole Dependency chain looks like: Machine Learning -> Linear Algebra -> Multivariable Calc -> Single Variable Calc -> high school algebra and trigonometry. I have a feeling I'll end up sticking to being a web developer :)
    - blt 13y ago
      You don't really need those calc courses to learn linear algebra. It's more about "mathematical maturity": familiarity with vectors, functions, inverse functions, a general intuition about multidimensional coordinates, and so on. A programming background would probably go a long way (although I don't speak from experience; I learned a lot of math before I started programming). It's hard to overstate the importance of linear algebra in software. It's really worth learning.
      - 13y ago
aves 13y ago
Does anyone have a recommendation for an equally good and concise guide for Discrete Mathematics by any chance?
dmlorenzetti 13y ago
It's a little surprising, in a "no-bullshit" discussion of "theoretical and computational aspects of linear algebra," to see matrix inversion touted as the way to solve linear equations. The guide literally introduces the examples by saying "Dude, enough with the theory talk, let's see some calculations." Yet standard numerical practice avoids literal inversion, in favor of factorization methods. E.g., It is common practice to write the form A^{-1}b for economy of notation in mathematical formulas... The trouble is that a reader unfamiliar with numerical computation might assume that we actually compute A^{-1}... On most computers it is always more effective to calculate A^{-1}b by solving the linear system Ax = b using matrix factorization methods... (Dennis & Schnabel, "Numerical Methods for Unconstrained Optimization and Nonlinear Equations", section 3.2). E.g., As a final example we show how to avoid the pitfall of explicit inverse computation... The point of this example is to stress that when a matrix inverse is encountered in a formula, we must think in terms of solving equations rather than in terms of explicit inverse formation. (Golub and Van Loan, "Matrix Computations", section 3.4.11).
- greeneggs 13y ago
  Yes, one almost never inverts a matrix using a computer, and one never inverts a matrix by hand. What does that teach you? I was pretty surprised to see trivialities like this in a four-page summary. But, unfortunately, this is just a poor summary. It also barely covers the spectral decomposition, and has no mention at all of the singular-value decomposition.
  - baby 13y ago
    we do matrix inversion by hand in mathematics :D
dblarons 13y ago
Literally just finished this exam. Too bad I didn't see this summary 4 hours ago!
source99 13y ago
I love a lesson that doesn't include ANY real world examples. What's the purpose of this document? Does it accomplish that purpose?
- ivan_ah 13y ago
  I'll have to add some examples, yes >> TODO.txt purpose = to give a quick intro to the subject (the most important idea at least, namely, that matrix-vector product can represent linear transformations).
ggchappell 13y ago
A little observation: You repeatedly use language that fails to distinguish definitions & properties vs. effective computational methods. For example, in section G: > To find the eigenvalue of a matrix we start from the eigenvalue equation .... Solving the resulting equation is one way of computing eigenvalues. But it might not be the one you want to use in some practical situation. Just before that, in section F: > The determinant of a matrix, ... serves to check if a matrix is invertible or not. It is true that a square matrix is invertible iff is has nonzero determinant. It certainly is not true that, for a matrix of any size, computing the determinant is a good method for checking whether a matrix is invertible.
- shitlord 13y ago
  > It certainly is not true that, for a matrix of any size, computing the determinant is a good method for checking whether a matrix is invertible. Can you explain this part? I don't understand what you mean, and I have an Advanced Linear Algebra final in a few days, so I should probably know this stuff. I thought the determinant was not defined for non-square matrices. Also, I thought that inverses only existed for square matrices (implying that the determinant check is a good way of testing invertability).
  - Steuard 13y ago
    It's a valid way to test whether a (square) matrix has an inverse, but computing big determinants is a lot of effort (both from a "student work" perspective and from a "computational cost" perspective). The point is that in many cases, there are enormously more efficient ways to find an inverse (or, more generally, to solve matrix problems with inverses in them).
    - shitlord 13y ago
      Oh, okay. Thanks for the clarification.
- Steuard 13y ago
  > Solving the resulting equation is one way of computing eigenvalues. But it might not be the one you want to use in some practical situation. Related fun fact: Solving the eigenvalue equation is (in general) impossible in closed form for matrices 5x5 or larger, because there's no closed form solution to the quintic. So some other algorithm for finding eigenvectors and eigenvalues is often absolutely required in practice.
Perseids 13y ago
Studying at a university where all this and more is part of the first year education of computer scientists, I - probably foolishly - assumed basic linear algebra was common knowledge in the community. Now my interest is piqued: Which educational path / career path did you take ending up in IT and (more specifically) how much mathematical education did it include? What is your educational background and which route
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]
af3 13y ago
Linear algebra class in one abbreviation: LAPACK.
wfunction 13y ago
Why do linear algebra teaching materials never mention what a determinant is? (It's the product of the eigenvalues.)
- waqf 13y ago
  > It's the product of the eigenvalues. It sure is (provided you count multiplicities correctly), but that's not the one-sentence explanation I would have gone with, even to someone with much more intuition about eigenvalues than you'd get from this document. I would say the determinant is the volume scale factor (or hypervolume scale factor, in the general case). Actually, what's really interesting to me is your general point: why do <teaching materials for mathematics subject X> never mention <the key insights that made subject X clear to me>? And why does this question not get asked more often? The nearest I've been able to come to a plausible answer is a mixture of (i) the key insight varies from person to person more than you'd think, combined with the closely related (ii) you can't teach key insights just by saying a few words.
  - ivan_ah 13y ago
    Thank you for your comment! First off the explanation regarding det(A) = the volume scaling of the transformation T_A associated with the matrix A. I've been stuck for over a week now trying to word this any other way possible because, in the current ordering of the sections, I'm covering determinants before linear transformations. Perhaps there is no better once sentence than talking about the volume and I should reorder the sections... You've raised a very important point regarding "routes to concepts" which really should be asked more often! > (ii) you can't teach key insights just by saying a few words. Generally true, though we have to say that the key difficulty in communicating insights is lacking prerequisites. Therefore, if you think very carefully about the prerequisite structure (i.e. model of the reader's previous knowledge) you can do lot's of interesting stuff in very few words. > (i) the key insight varies from person to person more than you'd think, Let G=(V,E) where V is the set of math concepts, and E are the links between them. Then there are as many ways to click on a concept x, as there there are in-links for x! In this case we have at least three routes: Route 1: geometric lin. trans T_A = {matrix:A, B_in:{e1,..,en}, B_out:{f1,..,fn}} ---> what happens to a unit cube 1x1x1, represented (1,...1) w.r.t. B_in, after going through T_A? ---> output will be (1,..,1) w.r.t. B_out ---> observe that cols of A are f1..fn therefore det(A) = (hyper)volume of (hyper)parallelepiped formed by vectors f1..fn Route 2: computational det(A) = { formula for 2x2, formula for 3x3, ... } ---> a easy test for invertibility of an n by n matrix sidenote: see Cramer's rule for another application of dets Route 3: algebraic given a 2x2 matrix A, find a coefficients A T D that satisfy the following matrix equation: B*A^2 + T*A + D = 0, the linear term is the trace T = sum_i a_ii, the constant term is D = det(A). sidenote: B*λ^2 + T*λ + D = {characteristic poly. of A} = det(A-λI) So perhaps the task of teaching math is not so much to try to find "the right" or "the best" route to a concept, but to collect many explanations of routes (edges in G), then come up with a coherent narrative that covers as many edges as possible (while respecting the partial-sorted-order of prerequisites ).
dionyziz 13y ago
I bought this guy's previous book and the print quality was crap. I hope he improves this on his next book.
jakab922 13y ago
This is really basic. Noone(who uses the subject) should need a cheat sheet for this... Also there are really good books out there and linalg is a must nowdays. As for textbook: http://www.amazon.com/Linear-Algebra-Right-Undergraduate-Mathematics/dp/0387982582/ref=sr_1_1?ie=UTF8&qid=1386775556&sr=8-1&keywords=linear+algebra+done+right http://www.amazon.com/Linear-Algebra-Right-Undergraduate-Mat... As for reference: http://www.amazon.com/Matrix-Analysis-Roger-Horn/dp/0521386322/ref=sr_1_3?s=books&ie=UTF8&qid=1386775486&sr=1-3&keywords=matrix http://www.amazon.com/Matrix-Analysis-Roger-Horn/dp/05213863...
anoncow 13y ago
Here is a 1914 book on calculus. Calculus made easy by Thompson Silvanus Philip http://www.gutenberg.org/ebooks/33283 http://www.gutenberg.org/ebooks/33283
gaelow 13y ago
No pseudo-inverse, no singular value decomposition, no least squares regression, no k-nearest neighbors and I'm sure I'm leaving many other things, all fundamental algebra very much needed for understanding and developing of computer science (e.g. machine learning, data storage and compression), telecommunications (e.g. queueing theory, multimedia coding and streaming) and many other fields related to engineering. I lovehate maths (I really struggle with them), but I honestly think our linear algebra book back in grad school was 600 pages for a good reason, you just can't do proper engineering without it. (Also I have another really thick book on the most important numerical methods for implementing that algebra on a computer, so, come on! :-))
mathattack 13y ago
I wish I had this in grad school when I had forgotten all my undergrad Linear Algebra. It's not a very hard or deep aspect of math if you understand the fundamentals, so this is very useful.

256 points by ivan_ah 13y ago

Good luck to anyone who has a linear algebra exam coming up! I also have a similar short tutorial for Newtonian mechanics here: http://cnd.mcgill.ca/~ivan/miniref/mech_in_7_pages.pdf http://cnd.mcgill.ca/~ivan/miniref/mech_in_7_pages.pdf

whitewhim 13y ago
LinAlg 2 coming up in two days. Its a fun course!

nathan-wailes 13y ago

thanks for the post, i've been trying to learn linear algebra for a long time but keep getting stuck / bored.

dergachev 13y ago
For me what makes it really interesting is the realization that all of linear regression (think y = mx + b) is based on linear algebra, specifically the notion that figuring out a best-fit line (in the case of a single-dimensional input variable) is projection of the N-dimensional vector space of observations (where you have N data points) onto the best-fitting 2 dimensional vector spaces (assuming you're fitting a slope and an intercept). When thought of this way, a lot of linear algebra has geometric interpretations and for me this makes it a lot less abstract.
- graycat 13y ago
  Nearly everything in linear algebra has important geometric interpretations. In addition, a lot that works in the 3-space we live in (for the non-relativistic approximation) generalizes to linear algebra, vector spaces more generally, and, in particular, both Hilbert space and Banach space.
- ivan_ah 13y ago
  Yeah, dergachev is pointing to one of the cool direct applications of linear algebra to machine learning. Suppose you are given the data D = (r_1; r_2; r_3) where each row r_i is an n-vector r_i=(a_i1, a_i2, ..., a_in, b_i). Each row consists of some observation data. We want to predict future b_j given the future \vec{a}_j, given that we have seen {r_i}_{i=1...N} (The data set consists of N data rows r_i where both \vec{a}_i and b_i are known). One simple model for b_j given \vec{a}_i = \vec{a}_i = (a_i1, a_i2, ..., a_in) is a linear model with $n$ parameters m_1,m_2,...,m_n: y_m(x_1,...x_n) = m_1x_1 + m_2x_2 + ... + m_nx^n = \vec{m} · \vec{x} If the model is good then y_m(\vec{a}_i) approximates b_i well. But startup wisdom dictates that we should measure everything! Enter error term: e_i(\vec{m}) = |y_m(\vec{a}_i) - b_i|², the squared absolute-value of the difference between the model's prediction and the actual output---hence the name error term. Our goal is to make the sum $S$ of all the error terms as small as possible. S(\vec{m}) = \sum_{i=1}^{i=M} e_i(\vec{m}) Note that the "total squared error" is a function of the model parameters \vec{m}. At this point we have reached a level of complexity that becomes difficult to follow. Linear algebra to the rescue! We can express the "vector prediction" of the model y_m in "one shot" in terms of the following matrix equation: A\vec{m} = \vec{b} where A is an N by n matrix (contains the a_:: part of the data) \vec{m} is an n by 1 vector (model parameters---the unknown) \vec{b} is an N by 1 vector (contains the b_: part of the data) To find \vec{m}, we must solve this matrix equation, however A is not a square matrix: A is a tall skinny matrix N >> n, so there is no A^{-1}. Okay so we don't have a A^{-1} to throw at the equation A\vec{m}=\vec{b} to cancel the A, but what else could we throw at it. Let's throw A^T at it! A^T A \vec{m} = A^T \vec{b} \ / N (an n by n matrix) N \vec{m} = A^T \vec{b} Now the thing to observe is that if N is invertible, then we can find \vec{m} using \vec{m} = N^{-1} A^T \vec{b} This solution to the problem is known as the "least squares fit" solution (i.e. choice of parameters for the model m_1, m_2, ..., m_n). This name comes from the fact that the vector \vec{m} is equal to the output of the following optimization problem \vec{m} = minimize S(\vec{m}) over all \vec{m} Proof: http://en.wikipedia.org/wiki/Linear_least_squares_(mathematics)#Derivation_directly_in_terms_of_matrices http://en.wikipedia.org/wiki/Linear_least_squares_(mathemati... Technical detail: the matrix N=A^T*A is invertible if and only if the columns of A are linearly independent. TL;DR. When you have to do a "linear regression" model of data matrix X and labels \vec{y}, the best (in the sense of least squared error) linear model is \vec{m} = (X^T X)^{-1} X^T \vec{y}.
- LateNightCoder 13y ago
  Can you please post the tex associated with the pdf? Thanks in advance.

dergachev 13y ago

I really enjoyed the Gilbert Strang videos on linear algebra back when I was taking the course at McGill: http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/ http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-...

aet 13y ago
Yes, very entertaining and enlightening (even if you already know the subject). Love Strang's teaching style.
- blt 13y ago
  I agree, his lecture deriving the determinant from a few desirable properties is a classic in my mind.
clebio 13y ago
He has an exceedingly dry sense of humor. It's quite nice, when you're 40 minutes into an involved lecture. The series is indeed worth the watch.

graycat 13y ago

Roger Horn is one of the best linear algebra and matrix guys around, and I was, by wide margins, the star student in his class, effortlessly. For the notes, I found serious problems in just the first half of the first column on the first page. F'get about the four pages. If enough people want an outline in a few pages, then I'll consider knocking one out and putting up somewhere as a PDF file.

yagibear 13y ago
I'd be keen to see your outline.
recuter 13y ago
Please do.
eskimo87 13y ago
interested!
Arnor 13y ago
I'd appreciate that. My linear algebra is extremely basic (all picked up as needed for an AI course). Any well-rounded ground up resources would be awesome.
AceJohnny2 13y ago
Adding a request.
glomph 13y ago
And modest too.
- graycat 13y ago
  Horn wrote about my work, "Best performance in the course throughout the semester. Knows this material cold." It was just true. Why? It was an 'advanced' course in linear algebra and matrix theory, and I'd never had even a first course in the subject. But long before the course, in total I'd done much more than just such a course. I had had two good courses in abstract algebra, each of which had provided a good foundation for linear algebra and also touched on the subject. I had taken a reading course in theoretical physics based heavily on matrix theory. And I had written my undergraduate honors paper on group representation theory, essentially in linear algebra. I'd worked carefully through two of the best books on linear algebra, one by E. Nearing and the other by P. Halmos. The Halmos book is famous as the crown jewel of books on linear algebra. Why? It can be good to look at linear algebra as a baby version of Hilbert space theory, heavily from von Neumann, and Halmos wrote his book when he was an assistant to von Neumann at the Institute for Advanced Study. So, deliberately, the Halmos book is an introduction to Hilbert space theory. It also has the profound perspective of one of the best mathematicians of all time and the elegance of thought of von Neumann. For applications, in my career and in my own study, I'd worked through stacks of books and papers on applications in numerical linear algebra, multivariate statistics, optimization, curve fitting, signal processing, especially around the fast Fourier transform, differential equations, advanced calculus, deterministic optimal control theory, exterior algebra, etc. At one point I wrote my own notes on much of linear algebra, with black ink on white paper, 100% cotton I got especially for the notes. My work was very careful although not elegant. For review, just before the course, I wrote out from memory 80 pages covering about 2/3rds of the course. As Horn wrote, I knew the subject cold, long before I took his course. Horn's homework, tests, and final exam were all challenging for the other students, and I effortlessly blew them away, by large margins on all three. E.g., I never studied for the tests or either the mid-term or final exam. When doing the homework, I nearly never looked at my notes from class and, instead, just wrote out the solutions based on what I already knew. I didn't belong in the course and had told the department that at the beginning. The department's reaction was to smile and say "Take the course anyway.". So, I did. For me, the course was a huge waste: From a long commute to campus and taking care of my wife, I was short on time, but the Horn homework had me up nearly all night and then exhausted the next day once a week and, thus, ate into a big fraction of the best time I had each week. Some of my other, more important work suffered. When I did the Horn homework, I was usually just exhausted. I'd get the papers back, graded, in about two weeks, recognize my handwriting, but, from having been so tired, actually had no memory of having done the work. Bummer. It was a trial by fire and exhaustion, not education. I was being asked to 'prove myself', not learn something. In the program, I only wanted to learn some good material and had no desire at all to 'compete', certainly not in that linear algebra course beneath me. I didn't know I was blowing away the other students until the grader showed me the scores on homework and tests, all except the final exam. In many ways Horn was a very good teacher, but, in total, he blew away nearly all the students. If I hadn't already known the material coming into the course, then I couldn't have learned it in the course. The way I had learned the material was from some slow, careful, thoughtful study and a lot of work with applications, and the course offered neither.

j2kun 13y ago

A few minor mistakes (perhaps just in my eyes), but overall pretty good. The hardest part about teaching linear algebra is that nobody explains the big picture. I teach mathematics and computer science and regularly tutor linear algebra students, and I encounter students all the time who ask me "What are vectors good for? I thought all we cared about were matrices and doing RREF and stuff." For this reason, I deemphasize computations and emphasize the connection between linear maps and matrices. It can be summed up as follows: if you fix a basis, every linear map is a matrix and every matrix is a linear map, and operations on functions (like composition, inversion, whatever) correspond to operations on the corresponding matrices. It's definitely not an analogy or anything in "scare quotes" that would imply something different is going on behind the scenes. It's exactly the same thing. Other questions usually left out of discussions about linear algebra (and these notes): what are orthogonal vectors good for? Why would we ever want a basis besides the standard basis in real Euclidean space? Is Euclidean space the only vector space out there? Do vectors have to be lists of numbers?

infogulch 13y ago
So... are you going to answer them?
- dominotw 13y ago
  Gilbert Strang explains clearly why we need change of basis with an example of image compression here, http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-31-change-of-basis-image-compression/ http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-...
  - infogulch 13y ago
    How about "Is Euclidean space the only vector space out there?" And "Do vectors have to be lists of numbers?" Perhaps with some examples?
    - mej10 13y ago

nilkn 13y ago

As someone with a math degree, I love this. However, I think the author over-estimates the familiarity of a typical high school student with mathematical notation: > The only prerequisite for this tutorial is a basic understanding of high school math concepts I think fundamentally the material in these four pages is accessible to many high school graduates, but perhaps not in this concise rendering (which is awesome for me, but probably overwhelming for someone not familiar with set-theoretic notation, summation notation, etc.).

ivan_ah 13y ago
You are right. I am totally trying to sneak in the \in and the \mathbb{R}'s in there to see if people will notice. Previously I had \forall in there too, but went over and removed things. On the TODO list is to introduce the { obj | obj description } notation for defining sets (in this case vector spaces).
- Steuard 13y ago
  Well, I noticed! It stood out pretty clearly, I'd say. I really don't think that the intended audience of this sort of ground-up summary is going to be comfortable with \mathbb{R}^{m\times n} notation all over the place. Yes, you explain what the notation means, but there's zero chance that a reader who didn't already know that notation will become fluent in it right away: they're going to be flipping back to the definition every time. That might be okay if you're trying to teach all of math, but a person reading "Linear Algebra in Four Pages" presumably neither wants nor needs that full skill set. (I'd say that {obj|obj description} notation would make the text even more opaque to novices, no matter how cleanly introduced.) Why not just make a less precise reference to a table of "numbers" (which, as an added bonus, would leave the door open to complex matrices without having to start from scratch)?
001sky 13y ago
Twist: This is a great argument to teach notation earlier !

starstart 13y ago

In page 3, section B. Using elementary matrices: To remember what matrix correspond to a row operation just apply that operation to the identity matrix and you obtain the elementary associated matrix.

tdicola 13y ago

Very cool, I like title of the associated book "No Bullshit Guide To Linear Algebra" too. Does anyone know of a nice, short summary of discrete mathematics to go along with this?

starstart 13y ago

Suppose that you want to project a vector of data (x1,x2,x3,...,xn) into the one dimensional subspace generated by the vector (1,1,...,1). What's the projection in this case? Hint: You obtain the most important concept of statistics.

starstart 13y ago

Suppose that you are driving a car and you are hit with a big tree. The main eigenvector is in the direction from the car to the tree, the eigenvalue measures the deformation of the car produced by this accident. If the car is a half shorter after the accident then the eigenvalue is 1/2.

mrcactu5 13y ago

Courses would benefit from "quick-reference guides like the end of Dror Bar Natan's paper on Khovanov homology http://arxiv.org/abs/math/0201043 http://arxiv.org/abs/math/0201043 He says "It can fit inside your wallet." See: http://www.math.toronto.edu/drorbn/Talks/HUJI-011104/cube.gif http://www.math.toronto.edu/drorbn/Talks/HUJI-011104/cube.gi...

elvinmelvin 13y ago

Just to throw this out there in the hope it is useful, I have been using this book as a review of linear algebra: http://linear.ups.edu/html/fcla.html http://linear.ups.edu/html/fcla.html

ivan_ah 13y ago
+1 This book is awesome! The entire text is interspersed with collapsable examples and exercises.

michaelchum 13y ago

Wow amazing stuff here, I agree with you that most math textbooks in our education system fail to explain concepts which are supposed to be very simple. Thank you so much for making things simpler. I'm having MATH 270 final next week at McGill, this is going to help a lot in studying :)

baby 13y ago

erk, I don't think condensing much information in the smallest place possible is the best way to learn something (or even review it). I'm all for a no bullshit and quick way to get something. That's why I sometimes check learnXinYminutes.com or some random cheatsheets on Google. But this doesn't make it for me. Btw, if you really want to get a good grasp on Linear Algebra you should check Gilbert Strang's video courses on MIT OpenCourseWare. They are amazing and soooo easy to understand you don't even need to like mathematics to watch them. I haven't come across a better support to start with Linear Algebra.

luuse 13y ago
Course codes 18.06SC and 18.06 i think if anyone else was looking. Thanks for the pointer, really appreciated!
- udit99 13y ago
  Got excited for a moment...then did some prerequisites digging and ended up with a prerequisites dependency chain: 18.06 -> 18.02 -> 18.01 Where 18.02 = Multi Variable Calc 18-01 = Single Variable Calc Considering that my whole point of learning linear algebra was to clear it as a roadblock for Machine Learning, this is what my whole Dependency chain looks like: Machine Learning -> Linear Algebra -> Multivariable Calc -> Single Variable Calc -> high school algebra and trigonometry. I have a feeling I'll end up sticking to being a web developer :)
  - blt 13y ago
    You don't really need those calc courses to learn linear algebra. It's more about "mathematical maturity": familiarity with vectors, functions, inverse functions, a general intuition about multidimensional coordinates, and so on. A programming background would probably go a long way (although I don't speak from experience; I learned a lot of math before I started programming). It's hard to overstate the importance of linear algebra in software. It's really worth learning.
    - 13y ago

aves 13y ago

Does anyone have a recommendation for an equally good and concise guide for Discrete Mathematics by any chance?

dmlorenzetti 13y ago

It's a little surprising, in a "no-bullshit" discussion of "theoretical and computational aspects of linear algebra," to see matrix inversion touted as the way to solve linear equations. The guide literally introduces the examples by saying "Dude, enough with the theory talk, let's see some calculations." Yet standard numerical practice avoids literal inversion, in favor of factorization methods. E.g., It is common practice to write the form A^{-1}b for economy of notation in mathematical formulas... The trouble is that a reader unfamiliar with numerical computation might assume that we actually compute A^{-1}... On most computers it is always more effective to calculate A^{-1}b by solving the linear system Ax = b using matrix factorization methods... (Dennis & Schnabel, "Numerical Methods for Unconstrained Optimization and Nonlinear Equations", section 3.2). E.g., As a final example we show how to avoid the pitfall of explicit inverse computation... The point of this example is to stress that when a matrix inverse is encountered in a formula, we must think in terms of solving equations rather than in terms of explicit inverse formation. (Golub and Van Loan, "Matrix Computations", section 3.4.11).

greeneggs 13y ago
Yes, one almost never inverts a matrix using a computer, and one never inverts a matrix by hand. What does that teach you? I was pretty surprised to see trivialities like this in a four-page summary. But, unfortunately, this is just a poor summary. It also barely covers the spectral decomposition, and has no mention at all of the singular-value decomposition.
- baby 13y ago
  we do matrix inversion by hand in mathematics :D

dblarons 13y ago

Literally just finished this exam. Too bad I didn't see this summary 4 hours ago!

source99 13y ago

I love a lesson that doesn't include ANY real world examples. What's the purpose of this document? Does it accomplish that purpose?

ivan_ah 13y ago
I'll have to add some examples, yes >> TODO.txt purpose = to give a quick intro to the subject (the most important idea at least, namely, that matrix-vector product can represent linear transformations).

ggchappell 13y ago

A little observation: You repeatedly use language that fails to distinguish definitions & properties vs. effective computational methods. For example, in section G: > To find the eigenvalue of a matrix we start from the eigenvalue equation .... Solving the resulting equation is one way of computing eigenvalues. But it might not be the one you want to use in some practical situation. Just before that, in section F: > The determinant of a matrix, ... serves to check if a matrix is invertible or not. It is true that a square matrix is invertible iff is has nonzero determinant. It certainly is not true that, for a matrix of any size, computing the determinant is a good method for checking whether a matrix is invertible.

shitlord 13y ago
> It certainly is not true that, for a matrix of any size, computing the determinant is a good method for checking whether a matrix is invertible. Can you explain this part? I don't understand what you mean, and I have an Advanced Linear Algebra final in a few days, so I should probably know this stuff. I thought the determinant was not defined for non-square matrices. Also, I thought that inverses only existed for square matrices (implying that the determinant check is a good way of testing invertability).
- Steuard 13y ago
  It's a valid way to test whether a (square) matrix has an inverse, but computing big determinants is a lot of effort (both from a "student work" perspective and from a "computational cost" perspective). The point is that in many cases, there are enormously more efficient ways to find an inverse (or, more generally, to solve matrix problems with inverses in them).
  - shitlord 13y ago
    Oh, okay. Thanks for the clarification.
Steuard 13y ago
> Solving the resulting equation is one way of computing eigenvalues. But it might not be the one you want to use in some practical situation. Related fun fact: Solving the eigenvalue equation is (in general) impossible in closed form for matrices 5x5 or larger, because there's no closed form solution to the quintic. So some other algorithm for finding eigenvectors and eigenvalues is often absolutely required in practice.

Perseids 13y ago

Studying at a university where all this and more is part of the first year education of computer scientists, I - probably foolishly - assumed basic linear algebra was common knowledge in the community. Now my interest is piqued: Which educational path / career path did you take ending up in IT and (more specifically) how much mathematical education did it include? What is your educational background and which route

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]

af3 13y ago

Linear algebra class in one abbreviation: LAPACK.

wfunction 13y ago

Why do linear algebra teaching materials never mention what a determinant is? (It's the product of the eigenvalues.)

waqf 13y ago
> It's the product of the eigenvalues. It sure is (provided you count multiplicities correctly), but that's not the one-sentence explanation I would have gone with, even to someone with much more intuition about eigenvalues than you'd get from this document. I would say the determinant is the volume scale factor (or hypervolume scale factor, in the general case). Actually, what's really interesting to me is your general point: why do <teaching materials for mathematics subject X> never mention <the key insights that made subject X clear to me>? And why does this question not get asked more often? The nearest I've been able to come to a plausible answer is a mixture of (i) the key insight varies from person to person more than you'd think, combined with the closely related (ii) you can't teach key insights just by saying a few words.
- ivan_ah 13y ago
  Thank you for your comment! First off the explanation regarding det(A) = the volume scaling of the transformation T_A associated with the matrix A. I've been stuck for over a week now trying to word this any other way possible because, in the current ordering of the sections, I'm covering determinants before linear transformations. Perhaps there is no better once sentence than talking about the volume and I should reorder the sections... You've raised a very important point regarding "routes to concepts" which really should be asked more often! > (ii) you can't teach key insights just by saying a few words. Generally true, though we have to say that the key difficulty in communicating insights is lacking prerequisites. Therefore, if you think very carefully about the prerequisite structure (i.e. model of the reader's previous knowledge) you can do lot's of interesting stuff in very few words. > (i) the key insight varies from person to person more than you'd think, Let G=(V,E) where V is the set of math concepts, and E are the links between them. Then there are as many ways to click on a concept x, as there there are in-links for x! In this case we have at least three routes: Route 1: geometric lin. trans T_A = {matrix:A, B_in:{e1,..,en}, B_out:{f1,..,fn}} ---> what happens to a unit cube 1x1x1, represented (1,...1) w.r.t. B_in, after going through T_A? ---> output will be (1,..,1) w.r.t. B_out ---> observe that cols of A are f1..fn therefore det(A) = (hyper)volume of (hyper)parallelepiped formed by vectors f1..fn Route 2: computational det(A) = { formula for 2x2, formula for 3x3, ... } ---> a easy test for invertibility of an n by n matrix sidenote: see Cramer's rule for another application of dets Route 3: algebraic given a 2x2 matrix A, find a coefficients A T D that satisfy the following matrix equation: B*A^2 + T*A + D = 0, the linear term is the trace T = sum_i a_ii, the constant term is D = det(A). sidenote: B*λ^2 + T*λ + D = {characteristic poly. of A} = det(A-λI) So perhaps the task of teaching math is not so much to try to find "the right" or "the best" route to a concept, but to collect many explanations of routes (edges in G), then come up with a coherent narrative that covers as many edges as possible (while respecting the partial-sorted-order of prerequisites ).

dionyziz 13y ago

I bought this guy's previous book and the print quality was crap. I hope he improves this on his next book.

jakab922 13y ago

This is really basic. Noone(who uses the subject) should need a cheat sheet for this... Also there are really good books out there and linalg is a must nowdays. As for textbook: http://www.amazon.com/Linear-Algebra-Right-Undergraduate-Mathematics/dp/0387982582/ref=sr_1_1?ie=UTF8&qid=1386775556&sr=8-1&keywords=linear+algebra+done+right http://www.amazon.com/Linear-Algebra-Right-Undergraduate-Mat... As for reference: http://www.amazon.com/Matrix-Analysis-Roger-Horn/dp/0521386322/ref=sr_1_3?s=books&ie=UTF8&qid=1386775486&sr=1-3&keywords=matrix http://www.amazon.com/Matrix-Analysis-Roger-Horn/dp/05213863...

anoncow 13y ago

Here is a 1914 book on calculus. Calculus made easy by Thompson Silvanus Philip http://www.gutenberg.org/ebooks/33283 http://www.gutenberg.org/ebooks/33283

gaelow 13y ago

No pseudo-inverse, no singular value decomposition, no least squares regression, no k-nearest neighbors and I'm sure I'm leaving many other things, all fundamental algebra very much needed for understanding and developing of computer science (e.g. machine learning, data storage and compression), telecommunications (e.g. queueing theory, multimedia coding and streaming) and many other fields related to engineering. I lovehate maths (I really struggle with them), but I honestly think our linear algebra book back in grad school was 600 pages for a good reason, you just can't do proper engineering without it. (Also I have another really thick book on the most important numerical methods for implementing that algebra on a computer, so, come on! :-))

mathattack 13y ago

I wish I had this in grad school when I had forgotten all my undergrad Linear Algebra. It's not a very hard or deep aspect of math if you understand the fundamentals, so this is very useful.