An Introduction to Linear Algebra

Linear algebra was already used to solve problems involving systems of linear equations thousands of years ago, and it remains widely applicable today.

Linear algebra arose from people's observations. People noticed that many objects have similar properties, such as:

• Forces can be decomposed and combined.

• For arbitrary $k,x_0$, $k \sin (x-x_0)$ can be decomposed into $k_1\sin x + k_2\cos x$.

These properties are related to the scaling, decomposition, and superposition of the objects being described. Linear algebra abstracts these properties from concrete objects and studies them as an independent subject. In OI, linear algebra can be used directly to solve problems, and it can also be used to optimize algorithms, data structures, and so on. For example:

• Maintain a linear basis with heavy-light decomposition to find the maximum xor sum on a path.

• Use the matrix-tree theorem to transform the problem of counting spanning trees of a graph into finding a matrix determinant.

• Use matrix exponentiation to optimize recurrences.