I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For example, knowing how to efficiently solve systems of linear equations doesn't seem very useful unless you're trying to program a new equation solver. Additionally, the book has talked a lot about span, linear dependence and independence, when a matrix has an inverse, and the relationships between these, but I can't think of any application of this in CS. So, what parts of linear algebra are used in CS?
$\begingroup$
$\endgroup$
8
-
2$\begingroup$ Are you asking for your own benefit, or are you a teacher looking for strategies for motivating your students? $\endgroup$– RaphaelCommented Mar 2, 2015 at 11:52
-
$\begingroup$ Linear algebra is useful in many parts of computer graphics (you can find a lot of related information googling). $\endgroup$– JuhoCommented Mar 2, 2015 at 15:54
-
1$\begingroup$ Solving systems of linear equations is incredibly useful in computer science. For example: en.m.wikipedia.org/wiki/Combinatorial_optimization $\endgroup$– Ant PCommented Mar 2, 2015 at 16:12
-
2$\begingroup$ Matrices are used heavily in game development, IE for projections, rotations, and quaternion math. $\endgroup$– PaulCommented Mar 2, 2015 at 16:49
-
$\begingroup$ @Paulpro The question is for applications of linear algebra (a body of work), not matrices (a set of objects). $\endgroup$– RaphaelCommented Mar 2, 2015 at 17:42
|
Show 3 more comments
6 Answers
$\begingroup$
$\endgroup$
3
The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra.
Some algorithms only work with full rank matrices – Do you know what that means? Do you know what can make a matrix not full rank? How to handle this? You will have no clue if you don't know what linear independence is.
The Gaussian elimination algorithm that is used to solve linear equations can actually be numerically unstable if implemented improperly, and this is something that you might have to worry about in some cases. Without understanding the algorithm you won't know where the problem comes from and whether there's anything you can do about it – not at the level of algorithms for solving linear equations, but at the level of coming up with the correct linear equations to solve.
In short, don't be lazy, and take it on faith that these things are useful.
answered Mar 2, 2015 at 7:01
-
7$\begingroup$ "take it on faith that these things are useful" -- well, don't we all know teachers that load their lectures with their darlings without caring about overall usefulness? Student's can't really tell the difference, but neither should they trust blindly. "What will I need this for?" is a fair question, but "It's just for training your mind" is also a fair answer. $\endgroup$– RaphaelCommented Mar 2, 2015 at 11:54
-
10$\begingroup$ "don't be lazy" sets a tone that isn't constructive. I've had wonderfully inquisitive, engaged, and not at all lazy students ask me this very question. I think a large population of CS students find the traditional Linear Algebra class to be worlds apart from what they think they need. Their interests are computing and programming and not necessarily mathematics. Needing or wanting some context and motivation is not a sign of laziness. Let's not paint it as such. $\endgroup$ Commented Mar 2, 2015 at 13:45
-
$\begingroup$ @Raphael, Logan Mayfield, do you guys even know how machine learning relates to linear algebra? Although a little specific, Yuval is pretty on-point here on the examples he has mentioned. The OP's question cannot be fully answered in just one Internet post. $\endgroup$– laketunaCommented Mar 2, 2015 at 17:20
$\begingroup$
$\endgroup$
2
Linear algebra is sometimes extremely useful and powerful in graph algorithms. With the matrix-tree theorem you can efficiently count the number of spanning trees a graph has (you need to understand eigenvalues). A more challenging application, where you need an even firmer grasp of linear algebra is the FKT algorithm for computing the number of perfect matchings in a planar graph in polynomial time.
There are many more exciting examples of uses of linear algebra in algebraic graph theory and spectral graph theory. The algorithms that arise are not only for counting problems like the two examples I gave. For instance, you can also check for connectivity, or compute the diameter of a graph.
-
$\begingroup$ One wonders why one would ever want to count the number of spanning trees or of perfect matchings. What is this good for? Do you have a real-world application in mind? $\endgroup$ Commented Mar 2, 2015 at 15:29
-
$\begingroup$ @YuvalFilmus I don't, and it's maybe harder to come up with applications of counting problems to begin with. I think both are interesting mostly from a theoretical perspective, although the wiki entry of FKT gives some history and motivation. Anyway, the main point is that linear algebra is useful for developing graph algorithms, and thus has applications in computer science. $\endgroup$– JuhoCommented Mar 2, 2015 at 15:50
$\begingroup$
$\endgroup$
One of the most well known uses of linear algebra is in Google's Pagerank algorithm:
The PageRank values are the entries of the dominant left eigenvector of the modified adjacency matrix.
answered Mar 2, 2015 at 18:43
$\begingroup$
$\endgroup$
Almost anything involving computer graphics, animation, computer vision, image processing, scientific computing, or simulation of physical phenomena will involve extensive use of vectors and matrices (linear algebra) from simple things like representing spatial transformations and orientations, to very complex algorithms. These things used to be the domain of supercomputing, but now these very same fields are the core of all the coolest apps on your desktop, phones, and everywhere else, from video games to computational photography to self-driving cars. Linear algebra is everywhere.
$\begingroup$
$\endgroup$
There are plenty of matrix algebra based algorithms and techniques out there. And that's great. Principal component analysis is an example of some fairly useful applied linear algebra. The same can be said about Fourier analysis, which also has its roots in orthogonality and inner products. So there are direct applications.
BUT, even more importantly, taking a linear algebra class is valuable because it teaches you to think in a certain way. Most good linear algebra classes place emphasis on generalisation, logic and proofs. Is something true in general, or just certain specific, common cases? How can you be certain? Being able to think about how to prove your assumptions is good because it helps you keep yourself from making bad assumptions and writing code that doesn't generalise in the way you're assuming it does. It also helps you think about how to generalise things which might otherwise be difficult to generalise, and that let's you solve bigger problems.
In summary, it's good to keep in mind that linear algebra is good because it's weight lifting for the part of your brain that is useful in computer science.
$\begingroup$
$\endgroup$
Solving a system of linear equations (which can be done with the Gaussian elimination method), linear programming (which can be solved with the simplex method), least squares, and compressed sensing (see the Wikipedia article) are practical problems that arise in many application areas. Linear algebra helps with developing correct and efficient algorithms for these problems.
See the text [Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms, Third Edition"], where Chapter 28 is on matrix operations and Chapter 29 is on linear programming.
