We are, by now, quite used to relational interpretations of program semantics. Such interpretations live in a rich algebraic world. What if we wanted to use a probabilistic interpretation instead? Well, it turns out that this is a conservative extension of the relational setting, and the algebraic formalism smoothly extends. Unsurprisingly, given the title, the key is linear algebra.

After a brief review of typed linear algebra, relation algebra, and their interrelation, the author introduces a crisp formalism for doing elementary probability theory with linear algebra. This formalism is then leveraged to develop an elegant (point-free) calculus for probabilistic functions, well illustrated with relevant examples. Lastly, this is applied to finding faults in certain programs, namely those expressible as folds. This gives a method to evaluate the quantitative impact of faults in such programs.

This paper is superbly written. Given the amount of mathematics involved, including many full proofs, one expects leaden, dense text. But no, the author goes to great lengths to motivate and illustrate everything, without ever being imprecise or overly verbose.