I like using the example of magic squares when starting to go over linear algebra, usually starting with $3\times 3$ squares. They're a nice recreational maths thing that everyone has seen before, but usually not thought about.
When asked for an example, most students come up with something like $\pmatrix{6&1&8\cr 7&5&3\cr 2&9&4}$, remembering a construction from before. When prodded for a second example, someone might suggest rotating or reflecting this example. Once it's suggest that we just want the rows, columns and diagonals to sum to the same thing, and that the numbers don't have to be distinct, someone usually thinks of $\pmatrix{1&1&1\cr 1&1&1\cr 1&1&1}$.
It then usually becomes clear that linear combinations of what we have so far will also work, and this leads naturally into asking how many squares we need in a basis, and so on. (I then ask them to work out the dimension of the space of $n\times n$ magic squares as homework.)
Another "unexpected" use of linear algebra is when they're asked to prove that things like $\sqrt2+\sqrt3$ or $\sqrt2 + \sqrt[3]2$ are algebraic. Many fiddle around until they chance upon an arrangement that works, but they all like it when we show that it's sufficient to take a few powers and say "oh, some combination of those will do". This usually goes down well, as people often like playing with numbers.
