practical uses of matrix multiplication

The use of matrix multiplication is usually given with graphics initially (scalings, translations, rotations, etc). Then there are more in-depth examples such as counting the number of walks between nodes in a graph using the adjacency graph's power.

What are other good examples of using matrix multiplication in various contexts?

-
Edited tags to remove "examples" and add "big-list", which this question promises to become. This probably also should be community-wiki. –  Niel de Beaudrap May 27 '11 at 20:12
Isn't this question equivalent to "What are good examples of compositions of finite-dimensional linear operators in various contexts?" –  Rahul May 28 '11 at 3:44
No, matrices and finite-dimensional linear operators are not the same. They are the same only after choosing a basis, which is an important distinction. –  the L May 28 '11 at 7:25

Linear discrete dynamical systems, aka recurrence relations, are best studied in a matrix formulation $x_{n+1} = A x_n$. The solution of course is $x_n = A^n x_0$, but the point is to exploit the properties of $A$ to allow the computation of $A^n$ without performing all multiplications. As an example, take the Fibonacci numbers. The formula for them comes directly from this matrix formulation (plus diagonalization).

Don't forget the origins of matrix multiplication: linear change of coordinates. See, for instance, section 3.4 of Meyers's book (page 93) at http://www.matrixanalysis.com/Chapter3.pdf.

-
Very nice, thank you –  Vass May 28 '11 at 16:25

A fundamental example is the multivariate chain rule. A basic principle in mathematics is that if a problem is hard, you should try to linearize it so that you can reduce as much of it as possible to linear algebra. Often this means replacing a function with a linear approximation (its Jacobian), and then composition of functions becomes multiplication of Jacobians. But of course there are many other ways to reduce a problem to linear algebra.

-
could you take the time to put some examples? –  Vass May 28 '11 at 16:22

Matrix multiplication — more specifically, powers of a given matrix A — are a useful tool in graph theory, where the matrix in question is the adjacency matrix of a graph or a directed graph.

More generally, one can interpret matrices as representing (possibly weighted) edges in a directed graph which may or may not have loops, and products of matrices as specifying the total number (or total weight) of all the walks with a given structure, between pairs of vertices.

-
Floyd-Warshall algorithm for finding all pair shortest-path in a weighted graph can be viewed as computing powers of the adjacency matrix of the graph, where the multiplication $A^2 = A \otimes A$ is defined over the semiring $(\mathbb{R}, min, +, \infty).$ –  user2468 May 28 '11 at 0:48

Matrix multiplcation plays an important role in quantum mechanics, and all throughout physics. Examples include the moment of inertia tensor, continuous-time descriptions of the evolution of physical systems using Hamiltonians (especially in systems with a finite number of basis states), and the most general formulation of the Lorentz transformation from special relativity.

General relativity also makes use of tensors, which are a generalization of the sorts of objects which row-vectors, column-vectors, and matrices all are. Very roughly speaking, row- and column-vectors are 'one dimensional' tensors, having only one index for its coefficients, and matrices are 'two dimensional' tensors, having two indices for its coefficients, of two different 'kinds' representing rows and columns — input and output, if you prefer. Tensors allow three or more indices, and to allow more than one index to have the same 'kind'.

-
I don't understand what you mean by row and column indices being comparable to "input" and "output". –  Brennan Vincent May 29 '11 at 7:37
Consider the convention (common in physics) of representing vectors by columns. We then often identify linear transformations T : ℝⁿ¹ → ℝⁿ² using a matrix of dimensions n₂×n₁ matrix: multiplying such a matrix T by a column-vector x ∈ ℝⁿ¹ yields another column vector T x ∈ ℝⁿ². The column space of T defines the output, and the row-space defines the input. Furthermore, fixing a column index 'a' of T (identifying a single column) determines the output given the standard basis vector eₐ as input; the row-index then describes the coefficients of the vector which is output. –  Niel de Beaudrap May 29 '11 at 8:59

High-dimensional problems in statistical physics can sometimes be solved directly using matrix multiplication, see http://en.wikipedia.org/wiki/Transfer_matrix_method. The best-known example of this trick is the one-dimensional Ising model http://en.wikipedia.org/wiki/Ising_model, where an $N$-particle system can be 'solved' by calculating the $N$-th power of a 2x2-matrix, which is (almost) trivial; otherwise, one would have to compute a sum over $2^N$ terms to get the same result.

-

Hey Alex, a central theme of Machine Learning is about finding structures (preferably linear ones) in the data space; the intrinsic dimentionalities of your observations if you may (see Eigenfaces).

I understand this may not be about matrix multiplication per se; instead, this is about what, many times, happens right before it. It begins with the spectral theorem: A = SΛS' (inverse when A is non-symmetric); it is Literally the basis of so many things (see what I did there?).

-

Matrices are heavily used in mathematical finance in various ways. One specific example is a correlation matrix where an entry (i,j) specifies the degree to which price movements in instrument i and instrument j are correlated over a specified time period. A huge number of computer cycles is spent daily on computing these sorts of matrices and applying further analysis to them in order to, in part, attempt to quantify the amount of risk associated with a portfolio of instruments.

-