Applications of linear algebra
Jiřı́ Matoušek, Jaroslav Nešetřil · 1998
Abstract Linear algebra is a part of algebra dealing with systems of linear equations, matrices, determinants, vector spaces, and similar things. We have already seen several proofs using linear algebra in previous chapters, most notably in Section 7,5. Here we will demonstrate few more methods and applications. First, we present two problems, one concerning the existence of so-called block designs and the other about covering a complete graph by complete bipartite graphs. Hardly anyone would suspect that these problems are related to matrices, and yet an elegant solution can be given based on the notion of rank of a matrix. An interested reader can find much more about similar proofs in the very vividly written textbook by Babai and Frankl [12]. In the subsequent two sections of this chapter, we assign several vector spaces to each graph; this leads to a com pact and insightful description of seemingly very complicated sets. Finally in Section 11.6, we consider two elegant algorithms where linear algebra blends with a probabilistic method.