What are some applications of elementary linear algebra outside of math?
I was a teaching assistant in Linear Algebra previous semester and I collected a few applications to present to my students. This is one of them:
Google's PageRank algorithm
This algorithm is the "heart" of the search engine and sorts documents of the world-wide-web by their "importance" in decreasing order. For the sake of simplicity, let us look at a system only containing of four different websites. We draw an arrow from $i$ to $j$ if there is a link from $i$ to $j$.
The goal is to compute a vector $\underline{x} \in \mathbb{R}^4$, where each entry $x_i$ represents the website's importance. A bigger value means the website is more important. There are three criteria contributing to the $x_i$:
- The more websites contain a link to $i$, the bigger $x_i$ gets.
- Links from more important websites have a more relevant weight than those of less important websites.
- Links from a website which contains many links to other websites (outlinks) have less weight.
Each website has exactly one "vote". This vote is distributed uniformly to each of the website's outlinks. This is known as Web-Democracy. It leads to a system of linear equations for $\underline{x}$. In our case, for
$$P = \begin{pmatrix} 0&0&1&1/2\\ 1/3&0&0&0\\ 1/3& 1/2&0&1/2\\ 1/3&1/2&0&0 \end{pmatrix}$$
the system of linear equations reads $\underline{x} = P \underline{x}$. The matrix $P$ is a stochastical matrix, hence $1$ is an eigenvalue of $P$. One of the corresponding eigenvectors is
$$\underline{x} = \begin{pmatrix} 12\\4\\9\\6 \end{pmatrix},$$
hence $x_1 > x_3 > x_4 > x_2$. Let
$$G = \alpha P + (1-\alpha)S,$$
where $S$ is a matrix corresponding to purely randomised browsing without links, i.e. all entries are $\frac{1}{N}$ if there are $N$ websites. The matrix $G$ is called the Google-matrix. The inventors of the PageRank algorithm, Sergey Brin and Larry Page, chose $\alpha = 0.85$. Note that $G$ is still a stochastical matrix. An eigenvector for the eigenvalue $1$ of $\underline{x} = G \underline{x}$ in our example would be (rounded)
$$\underline{x} = \begin{pmatrix} 18\\7\\14\\10 \end{pmatrix},$$
leading to the same ranking.
Another very useful application of Linear algebra is
Image Compression (Using the SVD)
Any real matrix $A$ can be written as
$$A = U \Sigma V^T = \sum_{i=1}^{\operatorname{rank}(A)} u_i \sigma_i v_i^T,$$
where $U$ and $V$ are orthogonal matrices and $\Sigma$ is a diagonal matrix. Every greyscale image can be represented as a matrix of the intensity values of its pixels, where each element of the matrix is a number between zero and one. For images of higher resolution, we have to store more numbers in the intensity matrix, e.g. a 720p greyscale photo (1280 x 720), we have 921'600 elements in its intensity matrix. Instead of using up storage by saving all those elements, the singular value decomposition of this matrix leads to a simpler matrix that requires much less storage.
You can create a rank $J$ approximation of the original image by using the first $J$ singular values of its intensity matrix, i.e. only looking at
$$\sum_{i=1}^J u_i \sigma_i v_i^T .$$
This saves a large amount of disk space, but also causes the image to lose some of its visual clarity. Therefore, you must choose a number $J$ such that the loss of visual quality is minimal but there are significant memory savings. Example:
The image on the RHS is an approximation of the image on the LHS by keeping $\approx 10\%$ of the singular values. It takes up $\approx 18\%$ of the original image's storage. (Source)
This is a simpler example, but maybe that'll be good for undergraduate students:
Linear algebra is a central tool in 3-d graphics. If you want to use a computer to represent, say, a spaceship spinning around in space, then you take the initial vertices of the space ship in $\mathbb{R}^3$ and hit them by some rotation matrix every $.02$ seconds or so. Then you have to render the 3-d image onto a 2-d screen, which also involves linear algebra (and stuff with colors and lighting probably)
There are probably graphics packages that do a lot of that work for you these days (I actually don't know that much programming), but the linear algebra is still a pretty good first-order approximation for what the computer is doing.
We can also use Linear Algebra to solve
Ordinary Differential Equations
An ODE is of the form
$$\underline{u}'(t) = A \underline{u}(t) + \underline{b}(t)$$
with $A \in \mathbb{C}^{n \times n}$ and $\underline{b}(t) \in \mathbb{C}^{n \times 1}$. If we have an initial condition
$$\underline{u}(t_0) = \underline{u_0}$$
this is an initial value problem. Assuming the entries of $\underline{b}(t)$ are continuous on $[t_0,T]$ for some $T > t_0$, Picard-Lindelöf provides a unique solution on that interval. If $A$ is diagonalisable, the solution of the homogeneous initial value problem is easy to compute.
Let
$$P^{-1} A P = \Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n),$$
where $P = \begin{pmatrix} x_1 & \dots & x_n \end{pmatrix}$. Defining $\tilde{\underline{u}}:= P^{-1} \underline{u}(t)$ and $\tilde{\underline{u_0}} = P^{-1} \underline{u_0}$, the IVP reads
$$\tilde{\underline{u}}'(t) = \Lambda \tilde{\underline{u}}(t), \; \tilde{\underline{u}}(t_0) = \tilde{\underline{u_0}} =: \begin{pmatrix} c_1 & \dots & c_n \end{pmatrix}^T.$$
These are simply $n$ ordinary, linear differential equations
$$\tilde{u_j}'(t) = \lambda_j \tilde{u_j}(t), \; \tilde{u_j}(t_0) = c_j$$
for $j = 1, \dots, n$ with solutions $\tilde{u_j}(t) = c_j e^{\lambda_j(t-t_0)}$. We eventually retrieve $\underline{u}(t) = P \tilde{\underline{u}}(t)$.
Example: We can write
$$x''(t) = -\omega^2 x(t), \; x(0) = x_0, \; x'(0) = v_0$$
as $\underline{u}'(t) = A \underline{u}(t), \; \underline{u}(0) = \underline{u_0}$, where $\underline{u}(t) = \begin{pmatrix} x(t)&x'(t) \end{pmatrix}^T$ and
$$A = \begin{pmatrix} 0&1\\ -\omega^2&0 \end{pmatrix} \text{ and } \underline{u_0} = \begin{pmatrix} x_0\\ v_0 \end{pmatrix}.$$
Computing eigenvalues and eigenvectors, we find
$$\underline{u}(t) = c_1 e^{i \omega t} \begin{pmatrix} 1\\ i \omega \end{pmatrix} + c_2 e^{-i \omega t} \begin{pmatrix} 1 \\ -i \omega \end{pmatrix}.$$
Using the initial condition, we find $x(t) = x_0 \cos(\omega t) + \frac{v_0}{\omega} \sin(\omega t)$.
Matrix exponential: I don't know if your students already are familiar with the matrix exponential, but using it we find a solution of the homogeneous initial value problem to be given by
$$\underline{u}(t) = e^{(t-t_0)A} \underline{u_0}.$$
To solve the inhomogeneous differential equation, we use can vary the constants. Since every solution of the homogeneous system $\underline{u}'(t) = A \underline{u}(t)$ is of the form $\underline{u}(t) = e^{tA} \underline{c}$ for some constant vector $\underline{c}$, we set $\underline{u_p}(t) = e^{tA} \underline{c}(t)$ and find by plugging in
$$\underline{c}'(t) = e^{-tA} \underline{b}(t).$$
Thus,
$$\underline{u}(t) = e^{(t-t_0)A} \underline{u_0} + \int_{t_0}^t e^{(t-s)A} \underline{b}(s) \, \mathrm ds.$$
The restricted isometry property (RIP) of matrices is something not too hard for undergraduates to understand: it means that a (rectangular) matrix $A$ satisfies $$ (1-\delta) \|x\| \le \|Ax\|\le (1+\delta)\|x\| \tag{1}$$ for all vectors $x$ with at most $s$ nonzero components. The constant $\delta$ should be small, and of course independent of $x$. The number $s$ is strictly less than the dimension of the domain of $A$ (its number of columns). This means that $A$ encodes sparse vectors with little distortion to their norm.
The fact that "fat" RIP matrices exist (with the number of their rows less than the number of columns) is not obvious, and there is no easy deterministic algorithm to construct them. But suitably random matrices are known to satisfy RIP with high probability. The use of such matrices is essential in the work of Candes and Tao from about 10 years ago, which formed the mathematical foundations of compressed sensing, a novel signal processing technique now applied in MRI and other areas where making a large number of measurements is expensive.