Matrices map between biproducts — LessWrong

Matrices map between biproducts — LessWrong

Why are linear functions between finite-dimensional vector spaces representable by matrices? And why does matrix multiplication compose the corresponding linear maps? There's geometric intuition for this, e.g. presented by 3Blue1Brown. I will alternatively present a category-theoretic analysis. The short version is that, in the category of vector spaces and linear maps, products are also coproducts (hence biproducts); and in categories with biproducts, maps between biproducts decompose as (generalized) matrices. These generalized matrices align with traditional numeric matrices and matrix multiplication in the category of vector spaces. The category-theoretic lens reveals matrices as an elegant abstraction, contra The New Yorker.

I'll use a standard notion of a vector space over the field . A vector space has addition, zero, and scalar multiplication defined, which have the standard commutativity/associativity/distributivity properties. The category $V e c t$ has as objects vector spaces (over the field $R$ ), and as morphisms linear maps. A linear map $f : U \to V$ between vector spaces U, V satisfies $f (u_{1} + u_{2}) = f (u_{1}) + f (u_{2})$ and $f (a u) = a f (u)$ . (Advanced readers may see nlab on Vect.)

Clearly, $R$ is a vector space, as is 0 (the vector space with only one element, which is zero). 0 is both an initial and a terminal object. Any linear map from 0 must always return the zero vector; and so must any linear map into 0. Therefore, by definition 0 is a category-theoretic zero object.

If U and V are vector spaces, then the direct sum $R$ , which has as elements pairs (u, v) with $u \in U, v \in V$ , and for which addition and scalar multiplication are element-wise, is also a vector space. The direct sum is both a product and a coproduct.

To show that the direct sum is a product, let U and V be vector spaces, and let $π_{1} : U \oplus V \to U$ and $π_{2} : U \oplus V \to V$ be the projections of the direct sum onto its elements. Let us suppose a third vector space T and linear maps $f : T \to U$ and $g : T \to V$ . Let $⟨ f, g ⟩ : T \to U \oplus V$ be defined as $⟨ f, g ⟩ (t) = (f (t), g (t))$ . Now $⟨ f, g ⟩$ uniquely commutes:

To show that the direct sum is a coproduct, let U and V be vector spaces, and let $i_{1} : U \to U \oplus V$ be defined as $i_{1} (u) = (u, 0)$ , and similarly let $i_{2} : V \to U \oplus V$ be defined as $i_{2} (v) = (0, v)$ . Let us suppose a third vector space W and linear maps $f : U \to W$ and $g : V \to W$ . Let $[f, g] : U \oplus V \to W$ be defined as $[f, g] (u, v) = f (u) + g (v)$ . Now $[f, g]$ uniquely commutes:

The upshot is that the direct sum is both a product and a coproduct; hence, by definition it is a biproduct. We can now abstract from the category $V e c t$ to semiadditive categories, which are by definition categories with a zero object and all pairwise biproducts. Let C stand for any semiadditive category, with biproduct $\oplus$ .

Biproducts enable powerful decomposition of morphisms (such as linear maps). Given $h : T \to U \oplus V$ (in C), we may uniquely decompose it as $h = ⟨ f, g ⟩$ for some $f : T \to U$ and $g : T \to V$ , specifically $f = π_{1} \circ h, g = π_{2} \circ h$ . And similarly, we may uniquely decompose $h : U \oplus V \to W$ as $h = [f, g]$ for some $f : U \to W$ and $g : V \to W$ , specifically $f = h \circ i_{1}, g = h \circ i_{2}$ .

Biproducts generalize from binary to n-ary. Suppose n is natural and $U_{i}$ is an object for natural $1 \leq i \leq n$ . Now the n-ary biproduct is $⨁_{i = 1}^{n} U_{i} = U_{1} \oplus \dots \oplus U_{n}$ . We take the empty biproduct to be 0. We can also generalize the projections $π_{i}$ , the injections $i_{i}$ , the "row-wise" combination $⟨ f, g ⟩$ , and the "column-wise" combination $[f, g]$ , from binary to n-ary.

This generalization to n-ary biproducts enables conceiving of matrices categorically. Let m, n be natural, and let $U_{i}$ and $V_{j}$ be objects in C, for natural $1 \leq i \leq m$ and $1 \leq j \leq n$ . Suppose $h : ⨁_{i = 1}^{m} U_{i} \to ⨁_{j = 1}^{n} V_{j}$ . We first decompose h "row-wise", as $h = ⟨ h_{1}, \dots, h_{n} ⟩$ where $h_{j} = π_{j} \circ h$ . Then we decompose each row "column-wise", as $h_{j} = [h_{j, 1}, \dots, h_{j, m}]$ where $h_{j, i} = π_{j} \circ h \circ i_{i}$ . We can now write h in matrix style, as $h = ⟨ [h_{1, 1}, \dots, h_{1, m}], \dots, [h_{n, 1}, \dots, h_{n, m}] ⟩$ ; the notation $⟨ \dots ⟩$ can be visualized as vertical matrix concatenation, and $[\dots]$ can be visualized as horizontal matrix concatenation.

This is the core abstract idea, but how to apply it more concretely? Back in $⟨ \dots ⟩$ , we can form the Euclidean space $R^{n} = ⨁_{i = 1}^{n} R$ . Now a map $h : R^{m} \to R^{n}$ decomposes as a $n \times m$ matrix of linear maps $h_{j, i} : R \to R$ . This is not quite a traditional matrix, but note that linear maps of type $R \to R$ are always multiplication by a constant real slope. Representing each $h_{j, i}$ by its slope yields a more traditional numeric matrix.

We can generalize matrix representation of linear maps to finite-dimensional vector spaces (which by definition have finite bases), by noting that each of these is isomorphic to $R^{n}$ for some natural n. Specifically, if a space U has a basis ${u_{1}, \dots, u_{n}}$ , then the linear map $f : R^{n} \to U$ defined as $f (x_{1}, \dots, x_{n}) = \sum_{i = 1}^{n} x_{i} u_{i}$ is an isomorphism. Hence, matrix representation extends to maps between finite-dimensional vector spaces.

So far, we have a treatment of matrix-vector multiplication, but not matrix-matrix multiplication. We would like to show that composition of linear maps leads to the matrix representations multiplying in the expected way. Let $m, n, p$ be natural, and let $U_{i}, V_{j}, W_{k}$ be objects in C (for naturals $1 \leq i \leq m, 1 \leq j \leq n, 1 \leq k \leq p$ ). Suppose we have maps $f : ⨁_{i = 1}^{m} U_{i} \to ⨁_{j = 1}^{n} V_{j}$ and $g : ⨁_{j = 1}^{n} V_{j} \to ⨁_{k = 1}^{p} W_{k}$ . We can write f in matrix form ( $f_{j, i} = π_{j} \circ f \circ i_{i}$ ), and similarly g ( $g_{k, j} = π_{k} \circ g \circ i_{j}$ ).

Now we wish to find the matrix form of the composition $h = g \circ f$ . We fix i, k and consider the entry $h_{k, i} = π_{k} \circ g \circ f \circ i_{i}$ . Now note $π_{k} \circ g = [g_{k, 1}, \dots, g_{k, n}]$ and $f \circ i_{i} = ⟨ f_{1, i}, \dots, f_{n, i} ⟩$ . Therefore

$h_{k, i} = [g_{k, 1}, \dots, g_{k, n}] \circ ⟨ f_{1, i}, \dots, f_{n, i} ⟩$

This expression is a row-column matrix multiplication, similar to a vector dot product. In the case of $V e c t$ , we can more explicitly write:

$h_{k, i} (u) = \sum_{j = 1}^{n} g_{k, j} (f_{j, i} (u))$

Since $H o m (U, V)$ in $V e c t$ , the set of linear maps from U to V, naturally forms a vector space, $h_{k, i}$ can also be written:

$h_{k, i} = \sum_{j = 1}^{n} (g_{k, j} \circ f_{j, i})$

In the case where each $U_{i}, V_{j}, W_{k}$ is $R$ , this aligns with traditional matrix multiplication; composing linear maps of type $R \to R$ multiplies their slopes.

There is a way to generalize the row-column matrix multiplication $[g_{k, 1}, \dots, g_{k, n}] \circ ⟨ f_{1, i}, \dots, f_{n, i} ⟩ = \sum_{j = 1}^{n} (g_{k, j} \circ f_{j, i})$ to semiadditive categories in general; for details, see Wikipedia on additive categories.

To summarize general lessons about semiadditive categories:

A map between biproducts $h : ⨁_{i = 1}^{m} U_{i} \to ⨁_{j = 1}^{n} V_{j}$ can be represented in matrix form as $⟨ [h_{1, 1}, \dots, h_{1, m}], \dots, [h_{n, 1}, \dots, h_{n, m}] ⟩$ with $h_{j, i} = π_{j} \circ h \circ i_{i}$ .
If we have maps $f : ⨁_{i = 1}^{m} U_{i} \to ⨁_{j = 1}^{n} V_{j}$ and $g : ⨁_{j = 1}^{n} V_{j} \to ⨁_{k = 1}^{p} W_{k}$ , the matrix entry $h_{k, i}$ of the composition $h = g \circ f$ is the row-column multiplication $[g_{k, 1}, \dots, g_{k, n}] \circ ⟨ f_{1, i}, \dots, f_{n, i} ⟩$ .

And in the case of $V e c t$ , these imply the standard results:

Linear maps between finite-dimensional vector spaces, with fixed bases, are uniquely represented as numeric matrices.
The matrix representation of a composition of linear maps equals the product of the matrices representing these maps.

This is a nice way of showing the standard results, and the abstract results generalize to other semiadditive categories, such as the category of Abelian groups. For more detailed category-theoretic study of linear algebra, see Filip Bár's thesis, "On the Foundations of Geometric Algebra". For an even more abstract treatment, see "Graphical Linear Algebra".