51
$\begingroup$

Edit: the original poster is Menny, but the question is CW; the first-person pronoun refers to Menny, not to the most recent editor.


I'm doing an introductory talk on linear algebra with the following aim: I want to give the students a concrete example through which they will be able to see how many notions arise "naturally". Notions such as vector spaces, the zero vector, span, linear dependency and independency, basis, dimension, "good" bases, solving linear equations, and even linear maps and eigenvectors. A related MO question is Linear algebra proofs in combinatorics.

The aim of this post is to find some more "concrete","real" and "natural" examples in this spirit that can interest everyone who loves what we do (and give them motivation to learn new definitions and formalisms). So if you have some ideas - please post them! Thanks, Menny

$\endgroup$
3
  • 2
    $\begingroup$ I have started a discussion over on meta that mentions this question, although it is not currently focused solely on this one: tea.mathoverflow.net/discussion/566 The short version: as this question is CW, any user may edit it to improve it, and I think that the question would be improved if OP's original suggestion were moved to an answer. So I will do that. $\endgroup$ Commented Jul 30, 2010 at 23:40
  • 1
    $\begingroup$ Per earlier discussion at meta, I state my objection to closing this question. Please, consider me as voting against closing. $\endgroup$ Commented Jul 31, 2010 at 21:38
  • $\begingroup$ A practial application of linear algebra: mathoverflow.net/questions/11784/… $\endgroup$
    – Anweshi
    Commented Aug 1, 2010 at 19:20

22 Answers 22

53
$\begingroup$

An example that my last class loved was lossy image compression using the singular value decomposition.

The SVD says that the transformation corresponding to any real matrix (not necessarily square) can be decomposed into three steps: a rotation that forgets some dimensions, a stretch along the coordinate axes, and finally a rotation. In other words, every matrix can be written the form HDA, with the rows of A being orthonormal, the columns of H being orthonormal, and D being a square diagonal matrix with nonnegative nonincreasing entries on the diagonal.

Consider a photograph that is an $768\times 1024$ array of $(red,green,blue)$ triples, which we can just as well store as 3 matrices $R$, $G$, and $B$ of real numbers. Now even though the matrix $R$ has nothing to do with transforming space, we can consider it as such, and using SVD write $R=HDA$. Call the numbers on the diagonal of $D$ by $\lambda_1\geq \lambda_2 \geq \cdots \geq \lambda_s\geq 0$, and let $D_k'$ be $diag(\lambda_1,\dots,\lambda_k,0,0,\dots)$, an $s\times s$ diagonal matrix, and let $D_k$ be $diag(\lambda_1,\dots,\lambda_k)$. Let $H_k$ be the $768\times k$ matrix formed from the first $k$ columns of $H$, and similarly let $A_k$ be the $k\times 1024$ matrix formed from the first $k$ rows of $A$. Then $$R = HDA \approx HD_k' A = H_k D_k A_k,$$ where $\approx$ is because of continuity, which is appropriate if the $\lambda$'s that were replaced with zeros were small.

Now for the punch-line. We need $3\cdot 768 \cdot 1024$ (about 2 megabytes) real numbers initially to store the photograph. But to store $H_k$, $D_k$, and $A_k$ for each of the three colors, we need only $3(768\cdot k+k+k\cdot 1024)=5379 k$ real numbers. With $k=25$, that gives a compression ratio of about 18. That is, file size goes from around 2 mb to around 130 kb. That is, it is faster by a factor of 20 to transmit the three matrices $H_{25}, D_{25}, A_{25}$ than it is to transmit their product.

SVD is fast enough to compute that you can do this instantly (using Mathematica, say) with a picture of the audience, and they can marvel at their own blurry (but quite recognizable) faces. Also, showing the actual file sizes on disk of the original bitmap and the compressed image is quite impressive. At least, it is if your calculations come out extremely close.

What's really impressive about this example (to me, at least) is that the matrix that we start with is just a table of data and not a transformation. But by considering it as if it were a transform, we gain power over it anyway. This is great motivation for linear algebra; students find it much easier to imagine encountering a table of data than a linear transformation.

$\endgroup$
3
  • 4
    $\begingroup$ This of course works with any orthogonal transform. Adaptive transforms like the SVD have the disadvantage that you either need to transmit the basis separately from the coefficients or you need to multiply everything out as you did, in the process destroying much of the sparsity introduced by the zero truncations. The discrete cosine transform is surprisingly close to the KLT in practice and is based on a fixed basis, so you only need to transmit the coefficients; this is what is used in JPEG. $\endgroup$ Commented Jul 31, 2010 at 8:20
  • 1
    $\begingroup$ @Per: I don't understand what you mean by needing to transmit the basis. In this case, the matrix starts as a table of numbers, so the `obvious' basis is the correct one. I've rewritten some of what's above to make this more transparent. One thing to be cautious of with arbitrary transforms is that you may need to handle complex numbers, which can take up space and lecture time (and be hard to motivate, depending on the audience). On the up side, if you get to say, "and this is how JPEG works," then you have your finale written for you. $\endgroup$ Commented Jul 31, 2010 at 16:52
  • $\begingroup$ He is referring to the basis of $\mathbb R^{n^2}$, not the basis of $\mathbb R^n$. The basis, in your case, consists of rank $1$ matrices of the form [column of first matrix]*[row of second]. $\endgroup$
    – Will Sawin
    Commented Nov 14, 2011 at 21:44
46
$\begingroup$

My favorite elementary application of linear algebra is proving that the decomposition used in Calculus of rational functions into partial fractions works.

Start with a polynomial $Q(x)=(x-r_1)(x-r_2)\cdots(x-r_n)$. Then the space of $P(x)/Q(x)$ with $deg P < deg Q$ is $n$-dimensional since it has a basis {$\frac{1}{Q(x)}, \frac{x}{Q(x)}, \frac{x^2}{Q(x)}, \dots, \frac{x^{n-1}}{Q(x)}$}. But {$\frac{1}{(x-r_1)},\frac{1}{(x-r_2)},\dots,\frac{1}{(x-r_n)}$} are linearly independent vectors in the space and thus form a basis.

Hence, $\frac{P(x)}{Q(x)}=\frac{A_1}{(x-r_1)}+\frac{A_2}{(x-r_2)}+\dots+\frac{A_n}{(x-r_n)}$ for some constants {$A_1,\dots,A_n$}, which then we can furthermore find by taking the limit of $(x-r_i)\frac{P(x)}{Q(x)}$ as $x$ goes to $r_i$.

$\endgroup$
4
  • 2
    $\begingroup$ Along similar lines, the Gram-Schmidt algorithm applied to the standard polynomial basis $1, x, x^2, \ldots$ with respect to the $\int_{[-1,1]} w(x) p(x) {\bar q}(x) dx$ inner product constructs the family of orthogonal polynomials defined by the weight function $w(x)$. $\endgroup$ Commented Jul 31, 2010 at 8:27
  • $\begingroup$ @Vladimir,Per: Hey,those are 2 great and simple ones!I got to remember those for when I teach linear algebra the first time! $\endgroup$ Commented Jul 31, 2010 at 20:11
  • 3
    $\begingroup$ This of course works with polynomials with repeated roots, where you just throw 1/(x-r_i)^j for 1 <= j <= k with k the degree of repetition. Asking students to extend the case for Q with distinct roots to arbitrary Q might be a fun exercise. $\endgroup$ Commented Aug 1, 2010 at 20:24
  • 2
    $\begingroup$ Since this question was on the front page anyway, I took the liberty to texify this answer. I hope no one minds. $\endgroup$ Commented Nov 14, 2011 at 14:10
30
$\begingroup$

Menny's original version of the above question included the following example, which is better placed in an answer, so that it can be voted up and down. Like all answers to any CW question, this one is community wiki. The remainder of this post, unless someone else edit's it, consists of Menny's writing, so the first-person pronoun is Menny, not Theo.


My example - the Fibonacci Sequence! I'll write it in the way I intend to present it; I hope it won't bore you and give you an idea for the type of example I'm looking for.

  • start by defining it. To them to wonder what is the general term.
  • Define $F_{a,b}$ to be the Fibonacci Sequence that starts with (a,b,a+b,...). Emphasize they know the first two, determines the other terms (but not explicitly! (yet))
  • Ask them if there exists a sequence that they "really know", i.e., they can give me the general term. (someone will come up with the zero sequence (zero vector!)).

    • Tell them: if I give you the general term of, say $F_{2,3}$ can you use this information to find the general terms of other sequences? (hopefully, we will discover that we can multiply by scalars)
    • emphasize this great discovery - a scalar multiple of Fib seq is another Fib seq!
    • Well, assume they are given $F_{2,3}$ explicitly, can they get to any other seq. by scalar multiples?
    • No? OK, So I'll give you another sequence, which one do you want? (linear dependency...)
    • Get to the fact that you can also add them!!!
    • Take $F_{2,4}$ Is this enough? Yes? Well how do you get to $F_{0,1}$? and to $F_{\sqrt{2},1.5}$ (solving linear equations !!!)
    • Well, these $F_{2,4}$, $F_{2,3}$ must by special, if we work hard and find their general terms, we would find any general term of any given Fib. seq!!!!!
    • What are their main properties? you can't get to one from the other, with both you can get to everyone (this is almost the definition of a basis...!)
    • Can we find three seq. like the last too with similar properties? how would we phrase the property "you can't get to one from the other" for 3 seq?
    • Well, let them show\give as an exercise\ show it yourself that this cannot be.
    • Ask: any two seq with the property that you can't get to one from the other, also have the property that you can get to everything with them (using scalar multi. and addition)?
    • Ask: the reverse question?
    • Summarize: We've seen a vector space, the fact that one vector cannot span 2-dim space, the fact the 3 are linearly dependent, the fact that 2 lin.indep. span and vice-versa.... and (I didn't write) that the zero vector does not help to span and you can always get to it.
    • BUT.....this is becoming boring! we didn't find any general term yet and we are just assuming we did. BUT we can redefine a very glorious aim: find two linearly dependent sequences with their general term!
    • We only "know" two sequences from High school - let's try arithmetic progressions. Well... it doesn't work.
    • Let's try geometric sequence! ...work it out... It works! with q that satisfies q^2=q+1. At last, a "real" motivation for solving a quadratic equation!
    • find a "basis"
    • give the formula for $F_{0,1}$!

    • Summarize - this time dividing the board into "formal part" which will have words like vector space etc. and a part with seq and "bad definition" as above.

If you also wish to talk about eigenvectors and give a more "natural" reason for using the geometric sequence - tell them that there is another "symmetry"/operation for the seq- The Shifting map. - Well, a sequence is geometric if and only if it is an eigenvector. Also, you can talk about larger recurrence laws, i.e. $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ and get 3-dim space...

I also found such examples in the first chapter of Newman's Analytic number theory book (which is amazing leisure-time reading!!)

$\endgroup$
2
  • $\begingroup$ Here's how I motivate "let's try the geometric sequence," at least for the classical Fibonacci sequence. List the first 10 or 15 terms. It's natural to ask "how fast do they grow"? From there, it's natural to compute the successive ratios to see how fast the terms grow. This makes it clear that $F_{n}/F_{n-1}$ seems to be getting very close to some number that's roughly $1.618\ldots$. So whatever that number is, call it $q$, it looks like $$F_n\approx qF_{n-1}\approx q^2F_{n-2}\approx\cdots\approx q^n.$$ So suppose we pretend that $F_n=q^n$, could it satisfy the Fibonaccii recurrence? Etc. $\endgroup$ Commented Dec 18, 2018 at 3:20
  • $\begingroup$ @JoeSilverman: Indeed! this is exactly how I did it last time I taught this. But since then I found a different way to motivate it which is even more "pedagogical": Since you are looking at the space of Fib. seq. you might ask, what are the symmetries of this space. Thinking for a bit, you realized that it has a natural shift operator. So you look for fixed points. You find none b/c of growth reasons. So you relax fixed to being the same up to multiplication.et voila: you get to eigenvectors! and then you calculate to find two eigenvectors, which are exactly the ones you were looking for. $\endgroup$
    – Menny
    Commented Dec 2, 2019 at 15:38
22
$\begingroup$

Google's page rank algorithm makes use of many concepts and ideas from linear algebra.

$\endgroup$
4
  • 2
    $\begingroup$ This is indeed a very good example. I taught Linear Algebra to Informatics students for a couple of years in the past and one of the tutorial questions was about the page rank algorithm and I dare say it was the most popular. $\endgroup$ Commented Jul 30, 2010 at 14:15
  • 16
    $\begingroup$ Well, "linear algebra makes you rich" is a great punchline for a linear algebra class :) $\endgroup$ Commented Jul 30, 2010 at 14:28
  • $\begingroup$ I'm not sure how much that article simplifies things, but last time I checked PageRank was based off algoriths involving (spectral) graph theory. This does of course relate to linear algebra, but is a bit more involved. $\endgroup$
    – Noldorin
    Commented Jul 30, 2010 at 15:00
  • 1
    $\begingroup$ @Noldorin: that's true, but fundamentally it's just an eigenvector problem. $\endgroup$ Commented Jul 30, 2010 at 15:30
22
$\begingroup$

My favorite application of linear algebra, as introduced to me by Fan Chung, is Oddtown (which I learned about from a manuscript of Lovasz, but may not be due to him).

The $n$ residents of Oddtown love to form clubs; call the family of these $\mathcal{F}$. If $F_1$ and $F_2$ ($F_1 \neq F_2$) are in $\mathcal{F}$, then $|F_1|$ must be odd (this is Oddtown!) and $|F_1 \cap F_2|$ must be even ($\scriptsize{go\;Oddtown?}$). The question is, how many clubs may these $n$ people form?

The answer (taken from Tibor Szabó's lecture notes) is this:

Let $\mathcal{F} = \{F_1,\ldots,F_m\} \subseteq 2^{[n]}$ be a set of clubs in Oddtown. Let $\mathbf{v}_i \in \{0,1\}^n$ be the characteristic vector of $F_i$; the $j$th coordinate is 1 iff $j \in F_i$.

Note that $\mathbf{v}_i^T v_j = |F_i \cap F_j|$.

Now, $\mathbf{v}_1,\ldots,\mathbf{v}_m$ is independent over $\mathbb{F}^n_2$: if $\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m = 0$, then for each $i$ we have $$0 \;=\; (\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m)^T\mathbf{v}_i \;=\; \lambda_1\mathbf{v}_1^T\mathbf{v}_i + \cdots + \lambda_i\mathbf{v}_i^T\mathbf{v}_i + \ldots + \lambda_m\mathbf{v}_m^T\mathbf{v}_i \;=\; \lambda_i $$

Since $\mathbf{v}_1,\ldots,\mathbf{v}_m$ are linearly independent vectors over $\mathbb{F}^n_2$, $m \leq n$, and Oddtown can have at most $n$ clubs.

$\endgroup$
3
  • 3
    $\begingroup$ and the upper bound is obviously achieved. $\endgroup$
    – Alekk
    Commented Jul 31, 2010 at 2:27
  • 4
    $\begingroup$ Yes, but whether we prefer n singleton clubs or (for n even) n clubs each omitting one person, depends upon how odd the residents are. I would like to see the minutes from a meeting of a club with only one person. Particularly any objections. $\endgroup$ Commented Jul 31, 2010 at 16:49
  • 1
    $\begingroup$ You should post this over at mathoverflow.net/questions/17006/… , too. Beautiful. $\endgroup$ Commented Jul 31, 2010 at 21:38
13
$\begingroup$

The theory of error correcting codes is a very nice and elementary context for introducing linear algebra, assuming the students know $\mathbb{F}_2$. The notion that each message of bit-length $n$ can coded as a "vector" over $\mathbb{F}_2$ of dimension $m > n$, using some linear conditions ("linear subspace") so as to provide easy error-checking conditions, should be quite motivating. Concepts such as "linear transforms" (matrices) and "null-spaces" show up naturally when considering the parity check matrix of the code. Etc., Etc.

$\endgroup$
10
$\begingroup$

I like using the example of magic squares when starting to go over linear algebra, usually starting with $3\times 3$ squares. They're a nice recreational maths thing that everyone has seen before, but usually not thought about.

When asked for an example, most students come up with something like $\pmatrix{6&1&8\cr 7&5&3\cr 2&9&4}$, remembering a construction from before. When prodded for a second example, someone might suggest rotating or reflecting this example. Once it's suggest that we just want the rows, columns and diagonals to sum to the same thing, and that the numbers don't have to be distinct, someone usually thinks of $\pmatrix{1&1&1\cr 1&1&1\cr 1&1&1}$.

It then usually becomes clear that linear combinations of what we have so far will also work, and this leads naturally into asking how many squares we need in a basis, and so on. (I then ask them to work out the dimension of the space of $n\times n$ magic squares as homework.)

Another "unexpected" use of linear algebra is when they're asked to prove that things like $\sqrt2+\sqrt3$ or $\sqrt2 + \sqrt[3]2$ are algebraic. Many fiddle around until they chance upon an arrangement that works, but they all like it when we show that it's sufficient to take a few powers and say "oh, some combination of those will do". This usually goes down well, as people often like playing with numbers.

$\endgroup$
9
$\begingroup$

I believe that determinants are worth special attention not only because they are good indicators on whether a given matrix has full rank. The famous example is the Vandermonde determinant (with application, for example, to the Lagrange interpolation) but please make a brief look at the Advanced Determinant Calculus and Advanced Determinant Calculus: A Complement by Christian Krattenthaler. The methods of computing determinants as well as their numerious applications all over maths belong to Arts....

$\endgroup$
3
  • 1
    $\begingroup$ Seconded. Determinants and minors can be treated very effectively and intuitively from the dual combinatorial and geometric perspective of exterior algebra. It's a shame this isn't done more often in introductory courses. $\endgroup$ Commented Jul 31, 2010 at 12:54
  • 2
    $\begingroup$ I think that interpolation is a great application to present! $\endgroup$ Commented Jul 31, 2010 at 21:42
  • 1
    $\begingroup$ For interpolation, one great and underappreciated method in linear algebra is polarization of forms. The algorithm of de Casteljau for Bezier interpolation and de Boor's algorithm for B-spline interpolation are special cases. It gives you a numerically robust and geometrically intuitive evaluation algorithm that proceeds directly from the control points by iterated linear interpolation. $\endgroup$ Commented Aug 1, 2010 at 4:42
8
$\begingroup$

Here's a fun problem from a recent linear algebra exam at my university.

While at university, all students are either in class, in the library, or at the bar. Detailed research by university management has shown that if a student is in class one minute, then after five minutes the student has a 60% chance of still being in class, a 20% chance of being in the library, and a 20% chance of being at the bar. Similarly, if the student is in the library at a certain time, then he or she has a 30% chance of being in class in five minutes' time, a 40% chance of remaining in the library, and a 30% chance of being in the bar. Finally, if the student is in the bar, then there is a 10% chance that he or she will be in class in five minutes' time, a 10% chance of being in the library, and an 80% chance of staying in the bar. What percentage of students do you expect to be in the bar after a long time?

So it's a Markov chain problem, which can be used to motivate matrices, vectors, matrix multiplication, eigenvalues and eigenvectors.

$\endgroup$
4
  • 1
    $\begingroup$ Unless the bar/pub/establishment has lock-ins, I would say zero percent... $\endgroup$
    – Yemon Choi
    Commented Nov 15, 2011 at 1:43
  • 5
    $\begingroup$ Do these students ever sleep??? $\endgroup$ Commented Nov 15, 2011 at 2:30
  • 22
    $\begingroup$ @Victor, it says the students are in class, it doesn't say they are awake. $\endgroup$ Commented Nov 15, 2011 at 4:24
  • $\begingroup$ David Lay's text (which was recommended in the accepted answer to the MO question mathoverflow.net/questions/16994/linear-algebra-texts) has a whole chapter on application of linear algebra to Markov chains and many problems like this. The bar setting is fun indeed... $\endgroup$ Commented Nov 15, 2011 at 16:23
7
$\begingroup$

Yesterday Only I learned about Fisher's inequality and I think it is good example to show application of rank calculations.

The problem is following:

Fisher, a population geneticist and statistician, was concerned with the design of experiments studying the differences among several different varieties of plants, under each of a number of different growing conditions, called "blocks".

Let:

 v be the number of varieties of plants;
 b be the number of blocks.

It was required that:

1 k different varieties are in each block, k < v; no variety occurs twice in any one block;

2 any two varieties occur together in exactly λ blocks;

3 each variety occurs in exactly r blocks.

Fisher's inequality states simply that $v \leq b$.

And its proof (given below) involves basic linear algebra.

Let the incidence matrix $M$ be a $v×b$ matrix defined so that $M_{i,j}$ is 1 if element $i$ is in block $j$ and $0$ otherwise. Then $B=MM^T$ is a $v×v$ matrix such that $B_{i,i}=r$ and $B_{i,j}=λ$ for $i \neq j$. Since $r\neq \lambda$, $det(B) \neq 0$, so $rank(B) = v$; on the other hand, $ rank(B) \leq rank(M) \leq b$, so $v \leq b$.

I have not been to able to link directly to Wikipedia page, so had to paste the question and answer here. Apologies for that.

$\endgroup$
1
  • $\begingroup$ Actually assumption 3 is not necessary; if we drop it we get $B_{ii}=r_i$ non-constant, as it was in the MO question in your link. (The conclusion is the same; check my answer there, and the subsequent comments). $\endgroup$ Commented Jul 30, 2010 at 20:22
6
$\begingroup$

An abstract but still elementary application is that every field is a vector space over any of its subfields. In particular, every finite field $F$ is a vector space over its prime field, and so $|F| = p^n$ for some $n$ where $p$ is the characteristic of $F$. The same style of reasoning applied to finite extensions of $\mathbb{Q}$ gives negative solutions to the ancient problems of duplicating the cube and trisecting the angle with ruler and compass.

Galois theory has plenty of deeper applications of linear algebra to the study of field extensions. But the ones I mentioned are easily enough accessible that they could serve as motivation for the abstract approach to linear algebra.

$\endgroup$
5
$\begingroup$

I recommend the use of examples from linear geometry applied to computer graphics. All the basical notions of linear algebra can be easily visualized (in fact I recommend starting with Euclidean affine geometry). See the series "Graphics Gems" for specific examples http://books.google.com/books?id=fvA7zLEFWZgC (there are also a lot of texts books). In my opinion it is the best option to see linear algebra in action.

$\endgroup$
4
$\begingroup$

A beautiful example of applications of linear algebra in linear PDEs is the theory of harmonic functions. With linear algebra and very few analysis one completely characterizes e.g. the space of "spherical harmonics", the eigenfunctions of the spherical Laplacian, which are the n-dimensional analogue of the trigonometric functions sin and cos.

$\endgroup$
1
  • 1
    $\begingroup$ A more elementary application along these lines is the use of linear algebra to express sin and cos of multiple angles as trigonometric polynomials (this can be further adjusted depending on the sophistication level of the audience). $\endgroup$ Commented Jul 31, 2010 at 21:44
4
$\begingroup$

A bit rubbish and easy, but amusing if you haven't seen it before.

Let $G$ be a finite group such that $g^2=e$ for all $g \in G$, i.e. every element (except the identity $e$) has order 2. Then $G$ has size $2^n$ for some $n$.

This is not too hard to prove directly; but it becomes totally obvious (once you've proved that $G$ is abelian) when you realise that $G$ is a finite-dimensional vector space over $F_2$.

$\endgroup$
5
  • 1
    $\begingroup$ It's already totally obvious by Cauchy's theorem. I usually hear this problem stated differently, although I can't quite remember exactly what is supposed to be shown. $\endgroup$ Commented Aug 1, 2010 at 1:41
  • 1
    $\begingroup$ Zen,how exactly is this example obvious to a general audience of beginners with only the barest essentials of linear algebra?Particularly one that hasn't seen group theory yet? Mathematicans often have trouble remembering what it was like to be a rank beginner without many tools yet in thier box.I got the idea those were the kinds of audiences Menny originally had in mind and this one will go way over thier heads. $\endgroup$ Commented Aug 1, 2010 at 4:41
  • 2
    $\begingroup$ Cauchy's theorem is harder than the LA proof, however... $\endgroup$ Commented Aug 1, 2010 at 19:48
  • $\begingroup$ I did say it was rubbish! If not to your taste, just ignore. $\endgroup$
    – Zen Harper
    Commented Aug 4, 2010 at 13:37
  • $\begingroup$ This is not rubbish! It is the basis of the analysis of two-level fractional factorial designs in Design of Experiments, in Statistics! $\endgroup$ Commented Jul 1, 2012 at 19:24
4
$\begingroup$

A handout from my vector calculus class and this Math.SE answer.

Consider the social network of seven individuals

A social network of seven individuals.

with the unimaginative names $A,B,C,D,E,F$ and $G$. An edge connects each pair of friends. This network or graph consists of two smaller, distinct graphs or components.

Question: How to write an algorithm to suggest that person $B$ befriend $D$?

The computer program should analyze the two components $\{A,B,C,D\}$ and $\{E,F,G\}$, identify that person $B$ is in the first component and then step through that list to find people to whom person $B$ is not currently linked. To do this, the computer will be fed the graph Laplacian, a matrix defined via the formula: \begin{equation*} L = (a_{ij}) = \begin{cases} \text{degree of vertex $i$ along the diagonal} \\ \text{$-1$ when an edge connects vertices $i$ and $j$}. \end{cases} \end{equation*} For the network of seven friends, the Laplacian matrix looks like: \begin{equation} L = \begin{bmatrix} 3 & -1 & -1 & -1 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 & 0 & 0 \\ -1 & -1 & 3 & -1 & 0 & 0 & 0 \\ -1 & 0 & -1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 & -1 & 1 \end{bmatrix} \end{equation} where rows and columns are in alphabetical order.

Question: How to determine the components of the graph using this matrix?

Note that the vector $\begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{bmatrix}^T$ is in the nullspace of $L$ and this vector corresponds to the first component. Can you find a second vector in the nullspace? In general, these vectors associated with the components form a basis for the nullspace (and this isn't difficult to prove). So if you find the basis for $N(L)$, you've found the components of the original graph.

In real life, graphs aren't as simple as the one pictured above. In fact, the graph may consist of one giant component with tightly clustered "approximate components" embedded within. (See any of the images in this search.) And if the graph does have a lot of components, there are more computationally efficient methods of finding them. So why introduce the graph Laplacian? It turns out that the graph Laplacian is a basic object in the field of spectral clustering, which has numerous "real life" applications. (I get to tell the students that I actually used the technique at a previous job while analyzing a large dataset.) This discussion can lead to spectral graph theory.

$\endgroup$
2
  • 1
    $\begingroup$ The question, though, is: Is this really better or simpler than defining a (0,1)-vector containing the neighbors of each person, and choosing pairs of non-neighbors whose neighbor vectors have sufficiently high dot products? In practice, I doubt you are really looking for connected components (and if you are, then Dijkstra's algorithm should do the trick more easily). $\endgroup$ Commented Nov 10, 2016 at 16:35
  • 1
    $\begingroup$ The (pedagogical) point of the example is that it's very easy to believe without proof that the eigenspaces corresponding to small eigenvalues are important for detecting approximate clusters. See my last paragraph, or: cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf It's my personal belief that mathematics education avoids heuristic reasoning to great detriment. $\endgroup$
    – dls
    Commented Nov 11, 2016 at 11:16
4
$\begingroup$

Since you are going to address undergraduates, there's a book Linear algebra gems that might give you lots of simple, cool stuff to present. It is also available at amazon.

$\endgroup$
3
$\begingroup$

One of my favorite elementary applications is the classification of projective conics by invoking the spectral theorem on a polarized quadratic form. It makes short work of what would at first glance seem like a messy problem.

$\endgroup$
2
  • $\begingroup$ Can you give more details? Thanks. $\endgroup$
    – Menny
    Commented Jul 31, 2010 at 17:50
  • $\begingroup$ You write the real projective conic via a homogeneous quadratic form and polarize it to get a $3 \times 3$ symmetric matrix. The spectral theorem puts that into the form $Q^T\ D\ Q$ for an orthogonal matrix $Q$ and diagonal matrix $D$. You then absorb the square root of the nonzero diagonal magnitudes into the $Q$ factors (which generally makes them non-orthogonal but still invertible). That leaves diagonal entries that are either -1, 0 or +1. Now you just have to analyze the possible combinations of signs. $\endgroup$ Commented Jul 31, 2010 at 18:22
3
$\begingroup$

Rubik's clock can be solved using linear algebra.

The only reservation I have about this example is that the Rubik's clock puzzle is unfortunately nowhere near as fun as Rubik's cube. Not only is it obscure, but it's basically impossible to look at both sides of the clock at once. Also, the specimens I've seen are not very well constructed and it's hard to turn the wheels.

Despite all that, I personally enjoyed solving Rubik's clock a lot, and a significant part of the fun was discovering that it was a linear algebra problem. (This was back when the puzzle first came out; I was still an undergraduate, and linear algebra was still relatively new to me.)

$\endgroup$
3
$\begingroup$

This article gives a nice connection between linear algebra and calculus, i.e. explains how the fundamental calculus operations of differentiation and integration can be understood instead as a linear transformation. - it should be easy to follow and gives some fascinating insights:

The ideashop: The linear algebra view of calculus

$\endgroup$
1
  • $\begingroup$ The link is not working anymore. $\endgroup$
    – user14875
    Commented Nov 9, 2016 at 21:51
2
$\begingroup$

As important as the Fibonacci sequence and its related sequences are in the overall hierarchy of functions, it just doesn't come naturally to most beginners and the depth of its many interconnections with diverse areas of mathematics will be lost on most of them. Your examples are clever, but I seriously doubt unless your audience is made up of very strong undergraduates with math competition experience and therefore quite bit of familiarity with counting problems, your examples are likely to be met with chirping crickets being heard clearly...

Geometry and physics are much more familiar to a general mathematical audience and linear algebra has so many connections with these topics, it’s really much more natural to start with those. These are my favorite examples to give. Describe planes in R3 as linear subspaces of R3, add vectors displaying their parallel lines, give isometries as examples of linear transformations and then construct matrices for them with respect to several possible bases. Show the fundamental theorem of systems of linear equations geometrically (i.e. that the corresponding systems of lines can be parallel, perpendicular or coincident). And then discuss similarities and their corresponding row vectors as eigenvectors of the corresponding eigenspaces. And then you can solve systems of differential equations as your last magic trick.

To prepare for the lecture, I'd look at Linear Algebra Through Geometry by Thomas Banchoff and John Wermer as well as the classic Linear Algebra With Applications by Gilbert Strang. Lots of good ideas and examples in these books to guide you in preparing this talk.

If you want a lot of very nice specific examples to use in your talk, there’s a terrific discussion and application of convergent sequences of diagonalizable stochastic matrices to solve problems such as the likelihood of graduation of students at a community college and the proportion at any given time of city and rural dwellers in a populated area undergoing mass migrations in the 4th edition of Steven H. Friedberg, Arnold J. Insel and Lawrence E. Spence’s Linear Algebra. It’s in section 5.3.

$\endgroup$
18
  • 12
    $\begingroup$ I downvoted the response because it led with the first paragraph, which is all unjustified opinion, much of it dismissive of the OP. What followed didn't change my mind. Moreover (since you asked), I find all the spelling and punctuation mistakes unhelpful, and I wonder why you can't take a little extra time to fix these. $\endgroup$ Commented Jul 31, 2010 at 1:04
  • 8
    $\begingroup$ @Andrew: Why don't you fix the spelling and punctuation mistakes this time? By not doing so, you are creating the impression that you don't take the process very seriously. $\endgroup$ Commented Jul 31, 2010 at 5:57
  • 5
    $\begingroup$ @Andrew L: Even in your repentant comments regarding your spelling and punctuation, you are not putting spaces after your dots or commas. $\endgroup$
    – Anweshi
    Commented Jul 31, 2010 at 9:47
  • 4
    $\begingroup$ C'mon, Anweshi, SPACES after dots and commas in a COMMENT? Is this for real? I recently complained about the title of a question not being capitalized or grammatical, and a highly upvoted response from Tom Goodwillie pointed out that most people don't expect to see full sentences in a title. Do you ever confront authors of the questions (other than Andrew L) for writing below the 6th grade level? $\endgroup$ Commented Jul 31, 2010 at 20:03
  • 6
    $\begingroup$ @Victor P: I had edited many lots of Andrew L's answers to fix his spelling and punctuation. I was disappointed that he was not putting in effort. The authors of the other questions with poor writing habits stop after very few questions and such occasional instances are not worth spending effort for reform. $\endgroup$
    – Anweshi
    Commented Jul 31, 2010 at 20:17
2
$\begingroup$

One nice application of linear algebra (mainly dimension theory) is the impossibility of the duplication of the cube (problem that dates back to the Greeks and was solved only in 1837 by Wantzel).

$\endgroup$
-1
$\begingroup$

I've heard some people mistakenly claim that the Moon does not rotate around an axis (further claiming that this is the reason we always see the same hemisphere; evidently it's not), but here is a purely mathematical argument that it almost certainly does rotate around an axis (i.e. with probability one) using only linear algebra:

Step 1: First let's make the reasonable simplifying assumptions that the Moon is a perfect $3$-dimensional ball $B^3$ of unit radius ($1$ unit $=$ radius of the moon), and that the space it's moving in is Euclidean 3-space.

Step 2: Next let's make sure to distinguish between tranlational motion in which the ball's center actually changes its position in space, and stationary motion where the position of the center point remains fixed while the rest of the points on the ball may change position--the latter is the type of motion we are interested in. It seems to me at this point before going through any argument and with all things being equally likely, the probability that the Moon is undergoing some stationary motion is equal to one (there's only one way to be still, but there are infinitely many ways to move). It only remains to decide what that stationary motion is.

Step 3: Next let's argue that we may use linear transformations to model the sphere's stationary motion: Neglecting any translational motion, if we imagine taking snapshots of our ball at time $t_0$ and again at time $t_1>t_0$, then the transformation of the $t_0$ points of our ball to the $t_1$ points defines a function $$F\colon B^3\rightarrow B^3.$$ Further this function should satisfy the following properties:

  1. It fixes the center point, which we may identify as the origin, $0$, i.e. $$F(0)=0.$$

  2. It fixes distances which we may express in terms of inner products on $\mathbb{R}^3$ as $$(F(v),F(w))=(v,w), \ \forall \ v,w\in B^3.$$

  3. If fixes orientations, which we may express in terms of determinants on $\mathbb{R}^3$ as $$F(\mathbf{e_1})\wedge F(\mathbf{e_2})\wedge F(\mathbf{e_3})>0$$ where $\mathbf{e_1},\mathbf{e_2},\mathbf{e_3}$ is the standard basis in $\mathbb{R}^3$.

To justify items 2. and 3., imagine fixing three rigid rods (of some fixed lengths, all less than $1$ unit) to the center of the Moon pointing in linearly independent directions--say the standard basis directions--at time $t_0$. Then at time $t_1$ the rods may be pointing in different directions, but they should still have the same lengths, and they should still satisfy the same right hand rule, i.e. have same orientation.

First note that we can always extend $F\colon B^3\rightarrow B^3$ to a function $$\hat{F}\colon\mathbb{R}^3\rightarrow\mathbb{R}^3$$ by $$\hat{F}(v)=\begin{cases} F(v) & \text{if $v\in B^3$}\\ |v|\cdot F\left(\frac{v}{|v|}\right) & \text{if $v\notin B^3$}\\ \end{cases}.$$ One can further check that $\hat{F}$ also satisfies conditions 1, 2, and 3 above.

Exercise: Show that $\hat{F}\colon {\mathbb{R}}^3\rightarrow\mathbb{R}^3$ is actually a linear transformation.

Hint: Compute the inner products $$(\hat{F}(v_1+v_2)-\hat{F}(v_1)-\hat{F}(v_2),\hat{F}(v_1+v_2)-\hat{F}(v_1)-\hat{F}(v_2))$$

$$(\hat{F}(cv)-c\hat{F}(v),\hat{F}(cv)-c\hat{F}(v))$$ and use property 2.

Step 4: Now that we have a linear function $\hat{F}\colon\mathbb{R}^3\rightarrow\mathbb{R}^3$ modeling the stationary motion of the Moon from time $t_0$ to $t_1$, we can compute its standard matrix $A$. This will be a $3\times 3$ real orthogonal matrix (from Property 2) with $\det(A)=1$ (by Property 3). Its characteristic polynomial $c_A(\lambda)$ will be a cubic polynomial with real coefficients. Since such polynomials always have at least one real root, we find that $A$ must have at least one real eigenvalue.

Exercise: Show that one of these real eigenvalues must equal $1$.

(Of course the eigenspace for $\lambda=1$ will turn out to be exactly the axis of rotation for our Moon)

Step 5: If $\ell\in \mathbb{R}^3$ is the $A$-eigenspace for $\lambda=1$, let $W\subset\mathbb{R}^3$ be its orthogonal compliment. Then of course $\hat{F}$ restricts to give a linear transformation $$\hat{F}'\colon W\rightarrow W.$$ Choosing any basis $\mathcal{B}'$ for $W$, we can compute the $\mathcal{B}'$-matrix for $\hat{F}'$, say $A'$. Then of course $A'$ will be a real $2\times 2$ orthogonal matrix with $\det(A')=1$.

Exercise: Show that every real $2\times 2$ orthogonal matrix $A'$ with $\det(A')=1$ is a rotation through some angle $\theta$, i.e. is similar to a matrix of the form $$A'=\left(\begin{array}{rr} \cos(\theta) & -\sin(\theta)\\ \sin(\theta) & \cos(\theta)\\ \end{array}\right).$$

Now of course this means that we can represent our function $\hat{F}\colon\mathbb{R}^3\rightarrow\mathbb{R}^3$ by a $3\times 3$ matrix in block diagonal form as $$A=\left(\begin{array}{rrr} 1 & 0 & 0\\ 0 & \cos(\theta) & -\sin(\theta)\\ 0 & \sin(\theta) & \cos(\theta)\\ \end{array}\right).$$

In particular the stationary motion taking $B^3$ at time $t_0$ into $B^3$ at time $t_1$ was rotation through an angle $\theta$ around the axis $\ell$.

Step 6: I suppose that if we make the additional simplifying assumption that the stationary motion of the moon is also continuous as a function of time, then fixing $t_0$ and letting $t_1=t$ vary over the time interval $[t_0,\infty)$ we get a continuous $1$-parameter family of linear transformations $$t\mapsto\left\{\hat{F}_t\colon \mathbb{R}^3\rightarrow\mathbb{R}^3\right\}.$$ Then since the roots of a (characteristic) polynomial are continuous in its coefficients, we could deduce that the axis $\ell=\ell_t$ (i.e. eigenspace for $\lambda(t)\equiv 1$) remains fixed for all time and hence so does its perp space $W=W_t$, so our continuous motion can really be modeled by the $1$-parameter family of matrices $$t\mapsto A_t=\left(\begin{array}{rrr} 1 & 0 & 0\\ 0 & \cos(\theta(t)) & -\sin(\theta(t))\\ 0 & \sin(\theta(t)) & \cos(\theta(t))\\ \end{array}\right)$$ presumably where the $\theta(t)$ is a continuous function in $t$.

I presented this argument (which I think is due to the French mathematician Chasles) to my linear algebra students last year, and I think they found it interesting :-)

$\endgroup$
1
  • $\begingroup$ Why the downvote? $\endgroup$ Commented Dec 18, 2018 at 23:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .