# 2 Matrix category

## 2.1 Semiring, ring, and field

A semiring (rig) $$(R, +, \times, 0, 1)$$ is a set $$R$$ equipped with two binary operations, addition $$+$$ and multiplication $$\times$$, and two distinguished elements $$0$$ and $$1$$, such that

• addition $$(R, +, 0)$$ is a commutative monoid,
• multiplication $$(R, \times, 1)$$ is a monoid,
• multiplication $$\times$$ distributes over addition $$+$$, and
• the additive identity $$0$$ annihilates multiplication $$\times$$: $$0 \times a = 0 = a \times 0$$.

An additively idempotent semiring is a semiring $$(R, +, \times, 0, 1)$$ such that addition $$+$$ is idempotent: $$a + a = a$$.

$$1 + 1 = 1$$ implies $$a + a = a \times (1 + 1) = a \times 1 = a$$.

A multiplicatively idempotent semiring is a semiring $$(R, +, \times, 0, 1)$$ such that multiplication $$\times$$ is idempotent: $$a \times a = a$$.

• natural number semiring $$(\N, +, \times, 0, 1)$$
• Boolean semiring $$(\set{\lfal, \ltru}, \ldis, \lcon, \lfal, \ltru) \iso (\set{0, 1}, \max, \min, 0, 1) \incl ([0, 1], \max, \min, 0, 1)$$ max-min semiring
• min-plus semiring $$([0, \infty], \min, +, \infty, 0) \xtoot{\exp(-x)}{-\log(x)} ([0, 1], \max, \times, 0, 1)$$ Viterbi semiring
• min-plus semiring $$((-\infty, \infty], \min, +, \infty, 0) \xtoot{-}{-} ([-\infty, \infty), \max, +, -\infty, 0)$$ max-plus semiring
• probability semiring $$([0, \infty), +, \times, 0, 1) \xtoot{\log}{\exp} ([-\infty, \infty), \logsumexp, +, -\infty, 0)$$ log semiring
• $$\log(a + b) = \logsumexp(\log a, \log b)$$
• $$\log(a \times b) = \log a + \log b$$
• $$\log 0 = -\infty$$
• $$\log 1 = 0$$
• $$\exp(\logsumexp(a, b)) = \exp a + \exp b$$
• $$\exp(a + b) = \exp a \times \exp b$$
• $$\exp(-\infty) = 0$$
• $$\exp 0 = 1$$

A ring $$(R, +, \times, 0, 1)$$ is a set $$R$$ equipped with two binary operations, addition $$+$$ and multiplication $$\times$$, and two distinguished elements $$0$$ and $$1$$, such that

• addition $$(R, +, 0)$$ is an abelian group,
• multiplication $$(R, \times, 1)$$ is a monoid, and
• multiplication $$\times$$ distributes over addition $$+$$.

In a ring, the annihilation law follows from the distributivity law: $$0 \times a + 0 \times a = (0 + 0) \times a = 0 \times a$$, so $$0 \times a = 0$$.

A Boolean ring is a multiplicatively idempotent ring.

• integer ring $$(\Z, +, \times, 0, 1)$$
• Boolean ring $$(\set{\lfal, \ltru}, \lneqv, \ldis, \lfal, \ltru) \iso (\Z/2\Z, +, \times, 0, 1)$$

A field $$(R, +, \times, 0, 1)$$ is a set $$R$$ equipped with two binary operations, addition $$+$$ and multiplication $$\times$$, and two distinguished elements $$0$$ and $$1$$, such that

• addition $$(R, +, 0)$$ is an abelian group,
• multiplication $$(R, \times, 1)$$ is an abelian group, and
• multiplication $$\times$$ distributes over addition $$+$$.
• rational number field $$(\Q, +, \times, 0, 1)$$
• real number field $$(\R, +, \times, 0, 1)$$
• complex number field $$(\C, +, \times, 0, 1)$$

## 2.2 Matrix operations

For natural numbers $$a, b \in \N$$ and a set $$X$$, a $$X$$-valued matrix $$M_{a \times b}$$ of dimension $$a \times b$$ is a function $$M: [a] \times [b] \to X$$, where $$[a] := \set{i \in \N \mid 1 \leq i \leq a}$$. $$M(i, j)$$ is also denoted by $$M_{ij}$$.

The empty matrix $$\varnothing_{0 \times a}$$ or $$\varnothing_{a \times 0}$$ is the unique function from the empty set $$\varnothing$$ to $$X$$.

The semiring $$R$$-valued identity matrix $$I_a$$ is an $$a \times a$$ matrix such that $$I_a(i, j) = 1$$ if $$i = j$$ and $$I_a(i, j) = 0$$ if $$i \neq j$$.

The semiring $$R$$-valued zero matrix $$0_{a \times b}$$ is an $$a \times b$$ matrix such that $$0_{a \times b}(i, j) = 0$$.

The matrix product of two semiring $$R$$-valued matrices $$M_{a \times b}$$ and $$N_{b \times c}$$ is a $$R$$-valued matrix $$(MN)_{a \times c}$$ such that

$(MN)_{ik} := \sum_j M_{ij} \times N_{jk}.$

Specifically, $$\varnothing_{a \times 0} \varnothing_{0 \times c} = 0_{a \times c}$$.

The matrix addition of two semiring $$R$$-valued matrices $$M_{a \times b}$$ and $$N_{a \times b}$$ is a $$R$$-valued matrix $$(M + N)_{a \times b}$$ such that

$(M + N)_{ij} := M_{ij} + N_{ij}.$

The left scalar multiplication of a semiring $$R$$-valued matrix $$M_{a \times b}$$ and a scalar $$r \in R$$ is a $$R$$-valued matrix $$(rM)_{a \times b}$$ such that

$(rM)_{ij} := r \times M_{ij}.$

The Kronecker product of two semiring $$R$$-valued matrices $$M_{a \times b}$$ and $$N_{c \times d}$$ is a $$R$$-valued matrix $$(M \otimes N)_{(a \times c) \times (b \times d)}$$ such that

\begin{aligned} (M \otimes N) := \begin{bmatrix} M_{11} N & \cdots & M_{1b} N \\ \vdots & \ddots & \vdots \\ M_{a1} N & \cdots & M_{ab} N \end{bmatrix}_{(a \times c) \times (b \times d)}. \end{aligned}

## 2.3 Matrix category

The matrix category $$\cMat(R)$$ over a semiring $$R$$:

• objects: $$\N$$
• morphisms from $$a$$ to $$b$$: $$a \times b$$ $$R$$-valued matrices
• composition: matrix multiplication
• identity: identity matrix $$I_a$$

### 2.3.1 Zero object

• zero object: $$0$$
• terminal morphism: $$\varnothing_{a \times 0}$$
• initial morphism: $$\varnothing_{0 \times a}$$
• zero morphism: zero matrix $$0_{a \times b}: a \xto{\varnothing_{a \times 0}} 0 \xto{\varnothing_{0 \times b}} b$$

• $$a \oplus b := a + b$$
• $$\angles{M, N} := \begin{bmatrix} M & N\end{bmatrix}_{c \times (a + b)}$$
• $$\bracks{M, N} := \begin{bmatrix} M \\ N\end{bmatrix}_{(a + b) \times c}$$
• $$p_1 = \begin{bmatrix} I_a \\ 0_{b \times a} \end{bmatrix}_{(a + b) \times a}$$
• $$p_2 = \begin{bmatrix} 0_{a \times b} \\ I_b \end{bmatrix}_{(a + b) \times b}$$
• $$i_1 = \begin{bmatrix} I_a & 0_{a \times b} \end{bmatrix}_{a \times (a + b)}$$
• $$i_2 = \begin{bmatrix} 0_{b \times a} & I_b \end{bmatrix}_{b \times (a + b)}$$
• $$i_1 p_1 = I_a$$
• $$i_2 p_2 = I_b$$
• $$i_1 p_2 = 0_{a \times b}$$
• $$i_2 p_1 = 0_{b \times a}$$
• $$p_1 i_1 + p_2 i_2 = \begin{bmatrix} I_a & 0_{a \times b} \\ 0_{b \times a} & 0_{b \times b} \end{bmatrix}_{(a + b) \times (a + b)} + \begin{bmatrix} 0_{a \times a} & 0_{a \times b} \\ 0_{b \times a} & I_b \end{bmatrix}_{(a + b) \times (a + b)} = I_{a + b}$$

### 2.3.3 Biproduct morphism: block diagonal matrix

\begin{aligned} M_{a \times b} \oplus N_{c \times d} = \begin{bmatrix} M_{a \times b} & 0_{a \times d} \\ 0_{c \times b} & N_{c \times d} \end{bmatrix}_{(a + c) \times (b + d)} \end{aligned}

### 2.3.4 Diagonal & codiagonal: concatenation

• $$\Delta_a = \begin{bmatrix} I_a & I_a \end{bmatrix}_{a \times (a + a)}$$
• $$\nabla_a = \begin{bmatrix} I_a \\ I_a \end{bmatrix}_{(a + a) \times a}$$

For $$M_1, M_2 \in \Hom(a, b)$$, $$M_1 + M_2 = \Delta_a (M_1 \oplus M_2) \nabla_b$$.

• $$(A + B)C = AC + BC$$
• $$A(B + C) = AB + AC$$

### 2.3.6 Monoidal product: multiplication & Kronecker product

• multiplication $$a \otimes b := a \times b$$
• Kronecker product $$M \otimes N$$
• unit $$1$$
• composition: $$(MN) \otimes (M'N') = (M \otimes M')(N \otimes N')$$
• identity: $$I_a \otimes I_b = I_{a \times b}$$
• associativity: $$a \times (b \times c) = (a \times b) \times c$$, $$A \otimes (B \otimes C) = (A \otimes B) \otimes C$$
• unitality: $$1 \times a = a = a \times 1$$, $$I_1 \otimes A = A = A \otimes I_1$$
• left distributivity: $$a \times (b + c) = a \times b + a \times c$$, $$(A \oplus B) \otimes C = A \otimes C \oplus B \otimes C$$
• right distributivity: $$(a + b) \times c = a \times c + b \times c$$, $$A \otimes (B \oplus C) = A \otimes B \oplus A \otimes C$$