Linear algebra tutorial in four pages

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-...

And matrix mult ~= function composition. I had a long ahaa moment reading this.

Well, it's not an analogy! There's a 1-1 correspondence between matrices and linear maps over a vector space with a fixed basis. "A matrix represents a function" is no more an analogy than "The symbols 'V', '5', and '五' represent the number five" is an analogy.

It's more like matrices are a useful way of representing certain functions, just like tally marks are a more useful way of representing numbers when you're counting the number of guests as they arrive but arabic numerals are more useful when you're doing arithmetic. Because these functions — linear maps — have a special structure to them, we can define matrix "multiplication" in a way that corresponds to the composition of linear maps.

In other words, it's not a happy accident. We invented matrices as a way to reason about and compute with linear maps more effectively. For example, "diagonal matrices" and "upper-triangular matrices" (among others) play important roles throughout linear algebra, but without the matrix representation of linear maps it'd be hard to talk about these things.

Here's the man you have to thank for putting all this together: http://en.wikipedia.org/wiki/Arthur_Cayley

Thanks, i have been doing a lot of machine learning hacks lately and almost everything involves "vector spaces", 249 pages should be fun, just finishing up "Think Bayes" by Alan Downey.

I read Axler's book quite recently, after pouring through reviews of linear algebra books. I did like it quite a lot -- it has a very clean, approachable narrative style. Having completed it, though, I feel there's maybe not enough operational knowledge gained from it. Meaning, it explains the theory, the motivations, well, but one might augment it with Schaum's[1], or some such guided exercises.

[1]:http://www.amazon.com/Schaums-Outline-Algebra-Edition-Outlin...

Axler is not a text in applied linear algebra, it is a book you should read after you are already familiar with both basic abstract algebra and basic linear algebra (i.e. you know how to multiply matrices etc.), it then provides a nice motivation for linear algebra as a subfield of abstract algebra. You may still, however, not find the ideas of determinant, trace and other practical concepts very intuitive after reading Axler.

Wow, I just read that entire paper. Thank you for linking, it was super helpful!

maybe bump it to two different handouts?

> Each time you want to find the coordinate of a vector you have solve a system of linear equations.

This is wrong, unless I'm misreading you. The first time you want the coordinates of a vector in a nonstandard basis you need to construct the matrix that does the change of basis, which requires inverting a matrix (same cost as solving a LSE), but after that, it's just plain matrix-vector multiplication.

Computer graphics is full of fun topics that answer these questions in accessible and visible/tangible ways!

Skeletal character rigging in particular motivates a nice understanding of orthonormal bases and why a basis other than the identity matrix is very useful.

Even simple 2d conversions between screen space & pixel space, for example, can be useful motivational examples- its the thing your web browser did to render what you're reading. :)

Not that anyone would want to cover those topics in a 4 page linear algebra primer, but maybe there is some inspiration there for ways to include pictures that explain, instead of more math notation... ;)

The last 2 questions there are interesting and worthwhile topics for the interested student, but I'd say, just my $0.02, don't ruin a good thing by stuffing too much into it...

I knew the answers to these questions :) I'm just saying they belong in a discussion of the topics. Maybe I just like to take math slower than a 4-page summary.

we do matrix inversion by hand in mathematics :D

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)?

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).

Well, that depends on whether you want the exact eigenvalues.

I agree, his lecture deriving the determinant from a few desirable properties is a classic in my mind.

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.

I'll take a crack at being as pedantic as possible. I'm just doing this to play along.

1) "Linear algebra is the math of vectors and matrices" - I think this would be better phrased as "the math of vectors and linear transformations." Matrices are a convenient way to represent finite dimensional linear transformations, but I think it's putting the cart before the horse to say that linear algebra is the math of matrices. This is a minor problem, though.

2) "A vector ⃗v ∈ R^n is an array of n real numbers" - In general vectors are not arrays of numbers, real or otherwise. This kind of definition will run into problems when you get into Hilbert/Banach spaces.

3) "the function f(x) = ln(x) has the inverse f^−1(x) = e^x" - this is only true for x > 0 if we're talking about the real-valued logarithm function, since it's not defined for x <= 0.

(1) In R^n, none of n, R, or R^n has been defined.

Better: Let n be a positive integer, and let R be the set of real numbers. Then R^n is the set of all n-tuples over the real numbers. Such an n-tuple is a list of n numbers; e.g., (1, 3, 2.6, 1, 7) is an n-tuple for n = 5.

For positive integers m and n, an m x n (read "m by n") (real) 'matrix' as a rectangular array of real numbers with m rows and n columns. Typically for integer i = 1, 2, ..., m and integer j = 1, 2, ..., n, in m x n matrix A = [a_{ij}] a_{ij} is the number, 'component', in row i and column j. An example of a 2 x 3 matrix is

     1 9  4
     4 0 -1

(typically surrounded with square brackets not easy to type without, say, TeX).

Typically an n-tuple x in R^n is regarded as an n x 1 matrix. In this way, with m x n matrix A, n x 1 vector b, and matrix multiplication (we have yet to define) Ax, we can write Ax = b as a system of m linear equations in n unknowns x, and this is the most important foundation and application of linear algebra.

(2) Similarly for positive integer n and the set of complex numbers C, C^n is the set of all n-tuples of complex numbers. And, we can have an m x n matrix of complex numbers.

Once get very far in linear algebra, complex numbers become essential if only from the fundamental theorem of algebra (that is, from factoring a polynomial). In particular, eigenvalues are important, and they are often complex numbers.

(3) R^n and C^n are examples of 'vector spaces', but there are also many other examples.

For a 'vector space', we have a non-empty set V of 'vectors' and a 'field' F. Note: A 'field' is defined carefully in courses in abstract algebra, but the two leading examples in practice are R and C. Most commonly F = R or F = C, but there is also interest in other fields, e.g., the integers modulo a prime number. Here we assume that F = R or F = C.

On V we have an operation 'addition' denoted by +. So, for vectors x in V and y in V, there is a vector x + y in V. Addition is commutative so that x + y = y + x. Vector addition is also associative, that is, for x, y, z in V,

(x + y) + z = x + (y + z)

Also there is a vector 0 in V so that for any x in V we have 0 + x = x.

Also for x in V, there is -x in V so that x + (-x) = x - x = 0.

Or set V with operation + forms a commutative group (defined carefully in courses in abstract algebra).

On V with F we have an operation 'multiplication'. Then for x in V and a in F, with this 'multiplication' the 'product' ax in V.

For x, y in V and a, b in F, we have two distributive laws, (a + b)x = ax + bx and a(x + y) = ax + ay. Also, for 0 in F, 0x is the vector 0. For the vector 0, a0 is also the vector 0.

We have that (-1)x = -x.

For some examples of vector spaces, (A) let F = R and let V be the set of all monophonic audio signals exactly 10 seconds long, (B) let F = R and let V be the set of all real valued random variables X where E[X^2] is finite, and (C) let F = R and for m x n matrix A and n x 1 vector x and m x 1 vector b, let V be the set of all x such so that Ax = b (so far the matrix product Ax has not been defined, but it will be defined so that Ax = b is a system of m linear equations in n unknowns, the components of x).

(3) For set S, x in S means that x is an 'element' of S.

(4) The notation (R, R, R) = R^3 is neither good nor standard.

The notation R^3 = R X R X R as the set theory Cartesian product is standard.

Actually, we already know just what (R, R, R) is -- a 3-tuple and not a set of all 3-tuples of real numbers.

(5) R^{m x n} is questionable notation and, anyway, needs a definition.

(6) For the "power" of that mathematics, might illustrate that with some applications. One of the most important is solving systems of linear equations. For more, a matrix can describe a linear transformation, and linearity is a powerful assumption that commonly holds with good accuracy in practice. So, vectors and matricies become powerful means of working with linear systems where a matrix describes the system and the inputs and outputs of that system are vectors.

From G. F. Simmons, the two pillars of analysis in mathematics are continuity and linearity, and linear algebra emphsizes both, especially linearity.

More examples of linearity include both differentiation and integration in calculus and the Fourier transform.

(6) The definition of inverse function is wrong. That definition holds only when the given function f is 1-1. Even if f is not 1-1, the inverse function is still useful, but its values can be a set of values, that is, the inverse function is multiply valued. E.g., just take f(x) = x^2. Then the f^{-1}(1) = {-1, 1}.

As English, there's nothing wrong with what I wrote.

You could make a Dropbox file public with little effort, or create a Scribd account and post it there. Thank you in advance.

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 :)

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 ).

Uh, so you think this varies significantly from person to person? I don't know about you, but I think

> The determinant of a matrix is the product of its eigenvalues, and calculating it allows you to check if the matrix is invertible or not.

is a heck of a lot better than

> The determinant of a matrix is "a special way" to combine the entries of a matrix that serves to check if a matrix is invertible or not.

to pretty much any person.

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.

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_(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}.

Can you please post the tex associated with the pdf? Thanks in advance.