OK, I really don't know much about the LLL since it was invented at the time I was studying LinAlg and never got as far as our course work. It was being used by Conway, Norton and Parker when I was doing my PhD, so I heard something of it, but never implemented it, as I was working in a different area.
However ...
Here's (some/most of) my understanding.
We're working in R^n, and suppose you have n linearly independent vectors b_1 to b_n with integer coefficients in the obvious basis. These vectors span R^n, but you need to use real numbers as coefficients to do that. If you only take linear combinations using integer coefficients then you get a lattice in R^n.
Exercise: Prove that (1,5) and (2,3) are linearly independent in R^2
Exercise: plot a portion of the lattice spanned by (1,5) and (2,3) in R^2.
The same lattice might also be spanned by different vectors, and in particular, you may be able to find a collection of shorter vectors that span the same space.
Exercise: Find two shorter vectors v1 and v2 that span the same lattice as the one above.
The new vectors must also be in the same lattice, and so must be representable as an integer linear combination of the original vectors.
Exercise: Represent v1 and v2 as linear combinations of (1,5) and (2,3)
Basically LLL consists of a measurement of how well you're doing so far, and a way of replacing one of your existing vectors with a linear combination so as to make your collection improve.
I'll stop there - ask more questions if anything is unclear.
So then my next question is, relative to the whole of linear algebra, how advanced/deep/engaged-with-the-field is the LLL algorithm? Is this first-course-in-linear-algebra stuff? Is this "barely linear algebra" stuff?
As I understand it, the actual algorithm is very straight-forward. There were several clever things that had to come together to have it work:
* Define some concept of how good you can expect things to get
* Find some way of improving what you've got
* Prove that you get to within some distance of "the best"
* Prove that it terminates in polynomial time.
I've not see the details of the proofs - they're likely to be mildly difficult, with a very nasty details. But I don't think they're especially deep. The really deep bit was getting the exact formulation right to make it work.
Things like the spectral theorems, diagonalization, eigenvalues and eigenvectors, these are all deeper results that have far-reaching implications. For example, the reason that when you tap the rim of a coffee-cup you get two different notes, blends of those notes, and no other notes is to do with eigenvectors.
Similarly for why Fourier transforms work (in part) the way they do. The reasons that the Sine and Cosine functions form an infinite-dimensional basis for the linear space of non-pathological functions, for example, let us then deal with frequency space as a dual space of function space.
Your coffee cup example - if math were taught more that way rather than a dry list of mechanical actions I think less people would dread it. I have nothing but hatred and horrible memories towards my grade school maths education.
I can only study this stuff in my spare time so my knowledge is very patchy. But when I see stuff like eigenvectors I associate them towards a much more powerful concept of invariance - which I see everywhere. Recursion, programming, Machine Learning, dynamical systems, physics. And I feel on the edge of an epiphany but do not have sufficient knowledge to fully grasp it.
But it makes me think that all these things that appear over and over again in different guises, the subject is taught far too inefficiently. I feel there is a much simpler way to teach maths and have it flow and be holistic rather than a replay of history: disjointed and disconnected.
This is one of the reasons I'm creating a web site intended to show the connections between topics, and through that, how wide-spread the applications of the mathematical ideas are. Math should be taught with connections, applications, examples, demonstrations and, above all, by knowledgeable and enthusiastic teachers. Most high-school teachers don't know more than they have to teach, don't know the connections between topics, and don't have time to deviate from the prescribed curriculum.
The LLL algorithm seems pretty straight-forward looking at it on Wikipedia. It’s possible that proving things about it is tricky, but understanding the steps is pretty “first-course”.
However ...
Here's (some/most of) my understanding.
We're working in R^n, and suppose you have n linearly independent vectors b_1 to b_n with integer coefficients in the obvious basis. These vectors span R^n, but you need to use real numbers as coefficients to do that. If you only take linear combinations using integer coefficients then you get a lattice in R^n.
Exercise: Prove that (1,5) and (2,3) are linearly independent in R^2
Exercise: plot a portion of the lattice spanned by (1,5) and (2,3) in R^2.
The same lattice might also be spanned by different vectors, and in particular, you may be able to find a collection of shorter vectors that span the same space.
Exercise: Find two shorter vectors v1 and v2 that span the same lattice as the one above.
The new vectors must also be in the same lattice, and so must be representable as an integer linear combination of the original vectors.
Exercise: Represent v1 and v2 as linear combinations of (1,5) and (2,3)
Basically LLL consists of a measurement of how well you're doing so far, and a way of replacing one of your existing vectors with a linear combination so as to make your collection improve.
I'll stop there - ask more questions if anything is unclear.