How is linear algebra used in algorithms?

Question

Several of my peers have mentioned that "linear algebra" is very important when studying algorithms. I've studied a variety of algorithms and taken a few linear algebra courses and I don't see the connection. So how is linear algebra used in algorithms?

For example what interesting things can one with a connectivity matrix for a graph?

Answer 1

It depends what type of "algorithms".

Some examples:

• Machine-Learning/Statistics algorithms: Linear Regressions (least-squares, ridge, lasso).
• Lossy compression of signals and other processing (face recognition, etc). See Eigenfaces

Answer 2

Many signal processing algorithms are based on matrix operations, e.g. Fourier transform, Laplace transform, ...

Optimization problems can often be reduced to solving linear equation systems.

Answer 3

I don't know if I'd phrase it as 'linear algebra is very important when studying algorithms". I'd almost put it the other way around. Many, many, many, real world problems end up requiring you to solve a set of linear equations. If you end up having to tackle one of those problems you are going to need to know about some of the many algorithms for dealing with linear equations. Many of those algorithms were developed when computers was a job title, not a machine. Consider gaussian elimination and the various matrix decomposition algorithms for example. There is a lot of very sophisticated theory on how to solve those problems for very large matrices for example.

Most common methods in machine learning end up having an optimization step which requires solving a set of simultaneous equations. If you don't know linear algebra you'll be completely lost.