Matrices map between biproducts

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 $U \oplus V$ , 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. Let $0_{A, B} : A \to B$ be a zero function; since the direct sum also satisfies the identities $π_{1} \circ i_{1} = i d_{U}, π_{2} \circ i_{2} = i d_{V}, π_{1} \circ i_{2} = 0_{V, U}, π_{2} \circ i_{1} = 0_{U, V}$ , 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 $V e c t$ , 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".

[-]katherine2mo30

Cool stuff! I had previously seen that has a biproduct structure, but never even considered that matrices could be appropriately generalized using it.

One thought I had was about handling potentially infinite-dimensional vector spaces. In that case, if $V$ has a basis ${v_{i} : i \in I}$ , we still get a decomposition into a direct sum of copies of $R$ :

V ≅ ⨁ i \in I R,

However, when the indexing set $I$ is infinite, the coproducts and products in $V e c t$ differ, so the argument from the post doesn't go through verbatim. But it still feels like we have a (perhaps less useful) notion of matrix here: if $V$ has basis ${v_{i} : i \in I}$ and $U$ has basis ${u_{j} : j \in J}$ , then a linear map $T : V \to U$ is still fully determined by the collection ${a_{i, j} : (i, j) \in I \times J} \subseteq R$ , where $T (v_{i}) = \sum_{j \in J} a_{i, j} u_{j}$ and, for any fixed $i \in I$ , $a_{i, j}$ vanishes for all but finitely many $j \in J$ . Conversely, any collection ${a_{i, j} : (i, j) \in I \times J} \subseteq R$ with the aforementioned condition on the vanishing of the $a_{i, j}$ uniquely defines a linear map $T : V \to U$ . In the finite-dimensional case, when $V$ has dimension $m$ and $U$ has dimension $n$ , $I = {1, \dots, m}$ and $J = {1, \dots, n}$ .

This feels like it still captures the notion of "linear maps are in bijection with indexed collections of scalars" (now with an extra vanishing condition) that makes matrices useful for computing in the finite-dimensional case, although infinite collections are not as nice to work with (induction becomes an issue, for example). The category theory part of my brain wants to figure out the appropriate categorical structure that enables this, which would be something weaker than products and coproducts coinciding but instead maybe that they interact well. I might be asking for too much, though, since infinite-dimensional vector spaces are usually appearing in areas / approached using tools which, in my experience, aren't purely algebraic (e.g. functional analysis).

[-]jessicata1mo30

Here's a basic problem with infinite bases. Suppose duplicates its argument $ω$ times. And suppose $g : R^{ω} \to R$ sums all $ω$ entries. Now $g \circ f$ is not a sensible function.

So you really need to have some restriction. Like for example, maybe we interpret $R^{ω}$ as requiring all but a finite number of entries to be zero. That would at least rule out $f$ . Now $R^{ω}$ is not a "true infinite product" in the category-theory sense. But we would still have $R^{ω} ≅ R \oplus R^{ω}$ ("first" and "rest" of infinite list). Which might enable induction. I'm not sure.

Alternatively we could have $R^{ω}$ be unrestricted, but then $g$ can't be defined. Either way there's an issue with allowing functions to or from $R^{ω}$ to be represented by arbitrary infinite matrices.

EDIT: another framing of this is that "infinite product" ( $R^{ω}$ unrestricted) and "infinite coproduct" ( $R^{ω}$ restricted to all but finite being zero) come apart in $V e c t$ . So there isn't strictly an infinite biproduct.

[-]James Camacho2mo10

I believe

is the main idea. $[g_{i j} |$ (row/down vector) contracts many values down to one while $| f_{j i} ⟩$ (column/up vector) expands one value back up to many, linearly.

[-]jessicata1mo20

I don't understand the notation; it looks like bra/ket except not quite?

[-]James Camacho1mo10

Yeah, bra/ket but not quite. I was trying to match your notation where is the expander and $[\cdot, \cdot]$ is the contractor. I think I mixed up the bracket directions, and it makes more sense as

$h = ⟨ \begin{matrix} [h_{11} ⟩ & \dots & [h_{1 n} ⟩ ⋮ & ⋱ & ⋮ [h_{n 1} ⟩ & \dots & [h_{n n} ⟩ \end{matrix} ⎤ ⎥ ⎥ ⎦$

that way we can think of it as one big contraction

$[h_{11} ⟩, h_{12} ⟩, \dots, h_{n n} ⟩]$

or expansion

$⟨ [h_{11}, [h_{12}, \dots, [h_{n n} ⟩$

I believe bra/ket is for row and column vectors. I don't think it applies here, because in the general case (semiadditive categories), you have arbitrary linear maps as the entries. And in the $R^{m} \to R^{n}$ case, they're reals, not row or column vectors.

It is true that you can decompose as either $⟨ [\dots] \dots [\dots] ⟩$ or $[⟨ \dots ⟩ \dots ⟨ \dots ⟩]$ . To be clear I'm using $⟨ ⟩$ and [] from category theory product/coproduct notation, it's not meant to match linear algebra or bra/ket notation.

LESSWRONG
is fundraising!
LW

LESSWRONG
is fundraising!
LW

41

Matrices map between biproducts

41

41