Monoidal width was recently introduced by the authors as a measure of the complexity of decomposing morphisms in monoidal categories. We have shown that in a monoidal category of cospans of graphs, monoidal width and its variants can be used to capture tree width, path width and branch width.
In this paper we study monoidal width in a category of matrices, and in an extension to a different monoidal category of open graphs, where the connectivity information is handled with matrix algebra and graphs are composed along edges instead of vertices. We show that here monoidal width captures rank width: a measure of graph complexity that has received much attention in recent years.

§ INTRODUCTION

Many applications of category theory rely on monoidal categories as algebras of processes <cit.>.

Morphisms are compound processes, defined as parallel and sequential compositions of simpler process components.
The compositional nature of this modelling allows a compositional computation of the underlying semantics.
But how efficient is this computation?
Given two processes \(f\) and \(g\), we can compute their semantics separately.
However, computing the semantics of their sequential composition \(f \dcomp g\) often requires an additional cost <cit.>. Indeed, the semantics of sequential composition often means resource sharing or synchronisation along the common boundary. This in turn carries a computational burden, dependent on the size of the boundary.
On the other hand, computing the semantics of a parallel composition \(f \tensor f'\) typically does not involve any resource sharing, as indicated by the wiring of the string diagrams, and thus typically does not require significant additional computational resources.
Taking this into account, the choice of the recipe for a morphism in terms of parallel and sequential compositions influences the cost of computing its semantics.
As shown in <Ref>, where vertical cuts represent sequential compositions and horizontal cuts represent parallel compositions, the same morphism can be defined in different ways with possibly different computational costs.

\[\interchangelawDecFig\]

Two monoidal decompositions of the same morphism, the right one being the cheapest.

Given a morphism, it is thefore desirable to find the least costly recipe of decomposing it in terms of more primitive components. We can rephrase the original question:
what is the most efficient way to decompose a morphism in a monoidal category?

The authors recently proposed monoidal width <cit.> as a way of assigning a natural number to a morphism of a monoidal category, representing – roughly speaking – the cost of its most efficient decomposition.

In turn, this is related to the cost of computing the semantics of this morphism.

Computing efficient decompositions is not a new problem.
The graph theory literature abounds <cit.> with notions of complexity of graphs that ultimately measure the difficulty of decomposing a graph into smaller components by cutting along the vertices or the edges of the graph.
Measures such as tree width <cit.>, path width <cit.>, branch width <cit.>, clique width <cit.> and rank width <cit.> are motivated by algorithmic considerations.
Probably the best known among several results that etablish links with algorithms <cit.>, the following shows the importance of tree width.
[Courcelle <cit.>]
Every property expressible in the monadic second order logic of graphs can be tested in linear time on graphs with bounded tree width.

The different notions of complexity for graphs vastly differ in low-level “implementation details” but they all share a similar underlying idea: that of defining decompositions and suitably measuring their efficiency.
One of our contributions is to exhibit monoidal width as a unifying framework for graph measures based on a notion of decomposition.
In fact, by choosing a suitable algebra of composition for graphs — i.e. choosing the right monoidal cateory — we recover some of these known measures as particular instances of monoidal width. We have previously captured <cit.> tree width, path width and branch width by instantiating monoidal width and two variants in a category of cospans of graphs.

In this paper we focus on rank width <cit.> – a relatively recent development that has attracted significant attention in the graph theory community. A rank decomposition is a recipe for decomposing a graph into its single-vertex subgraphs by cutting along its edges. The cost of a cut is the rank of the adjacency matrix that represents it, as shown in <Ref>. A useful intuition for rank width is that it is a kind of Kolmogorov complexity for graphs.
For example, although the family of cliques has unbounded tree width, the connectivity of cliques is quite simple to describe: and, in fact,  all cliques have rank width $1$.

\[\cutrankExFig{}\]

A cut and its matrix in a rank decomposition.

To capture rank width as an instance of monoidal width, rather than taking cospans, we work in a different monoidal category of graphs. First introduced in <cit.>, it was recently used <cit.> as a syntax for network games. This approach to computing with “open graphs” is more linear algebraic, building modularly on the theory of bialgebra, well known to be closely related to matrix algebra <cit.>. Indeed, the connectivity of graphs is handled with adjacency matrices, and boundary connections are matrices.

*Related work.
This manuscript, although self-contained, complements our previous work <cit.>, where we considered tree width, path width and branch width as instances of monoidal width.

Previous syntactical approaches to graph widths are the work of Pudlák, Rödl and Savickỳ <cit.> and the work of Bauderon and Courcelle <cit.>.
Their works consider different notions of graph decompositions, which lead to different notions of graph complexity.
In particular, in <cit.>, the cost of a decomposition is measured by counting shared names, which is clearly closely related to penalising sequential composition as in monoidal width.
Nevertheless, these approaches are specific to particular, concrete notions of graphs, whereas our work concerns the more general algebraic framework of monoidal categories.

Recent abstract approaches focus on other graph widths.
The work of Blume et. al. <cit.>, characterises tree and path decompositions in terms of colimits.
Abramsky et. al. <cit.> give a coalgebraic characterization of  tree width of relational structures (and graphs in particular).
Bumpus and Kocsis <cit.> also generalise tree width to the categorical setting, although their approach is far removed from ours.

Monoidal width is recalled in <Ref>.
In <Ref>, we study the monoidal width of matrices.
<Ref> recalls rank width and gives an equivalent recursive definition of it that will be useful as an intermediate step towards our main result, which is presented in <Ref>.

We use string diagrams <cit.>:
sequential and parallel compositions of \(f\) and \(g\) are drawn as in <Ref>, left and middle, respectively.
Much of the bureaucracy, e.g. the interchange law \((f \dcomp g) \tensor (f' \dcomp g') = (f \tensor f') \dcomp (g \tensor g')\), disappears (<Ref>, right).

String diagrammatic notation.

Props <cit.> are important examples of monoidal categories.
They are symmetric strict monoidal, with natural numbers as objects, and addition as monoidal product on objects. Roughly speaking, morphisms can be thought of as processes, and the objects (natural numbers) keep track of the number of inputs or outputs of a process.

§ MONOIDAL WIDTH

This section recalls the concept of monoidal width from <cit.>.

Monoidal width records the cost of the most efficient way one can decompose a morphism into its atomic components, thus capturing—roughly speaking—its intrinsic structural complexity.

A decomposition is a binary tree whose internal nodes are labelled with compositions or monoidal products, and whose leaves are labelled with atomic morphisms.

Let \(\cat{C}\) be a monoidal category and \(\decgenerators\) be a subset of its morphisms referred to as atomic.
The set $\decset{f}$ of monoidal decompositions of \(f \colon A \to B\) in $\cat{C}$ is defined:

\begin{align*}
\decset{f} \quad \Coloneqq \quad & \leafgenerator{f} &\text{if } f \in \decgenerators \\
\mid \quad & \nodegenerator{d_{1}}{\tensor}{d_{2}} &\text{if } d_1\in \decset{f_1},\,d_2\in \decset{f_2} \text{ and } f =_\cat{C} f_1\tensor f_2 \\
\mid \quad & \nodegenerator{d_{1}}{\dcomp_{X}}{d_{2}} &\text{if }d_1\in \decset{f_1 \colon A\to X},\,d_2\in \decset{f_2 \colon X\to B} \text{ and }f =_\cat{C} f_1\dcomp f_2
\end{align*}

The cost of a decomposition depends on the operations and atoms present:
each operation and each atomic morphism is associated with a cost, which we call weight.
Roughly speaking, sequential composition is priced according to the size of the object the composition occurs over, while monoidal products are free.
Finally, the weight of an atom is the application-specific cost of computing its semantics.

Let \(\cat{C}\) be a monoidal category and let \(\decgenerators\) be a set of atoms for \(\cat{C}\).
A weight function for \((\cat{C},\decgenerators)\) is a function \(\nodeweight \colon \decgenerators \union \monoidaloperations{\cat{C}} \to \naturals\) such that

* \(\nodeweight(X \tensor Y) = \nodeweight(X) + \nodeweight(Y)\),

* \(\nodeweight(\tensor) = 0\).

Let \(\cp_{1} \colon 1 \to 2\) and \(\cocp_{1} \colon 2 \to 1\) be the diagonal and codiagonal morphisms in a cartesian and cocartesian prop[In a cartesian prop the $\tensor$ satisfies the universal property of  products. Dually, in a cocartesian prop, the \(\tensor\) satisfies the universal property of the coproduct.] s.t. $\nodeweight(\cp_{1})=\nodeweight(\cocp_{1})=2$.
The following figure represents the monoidal decomposition of \(\cp \dcomp (\cp \tensor \id{}) \dcomp (\cocp \tensor \id{}) \dcomp \cocp\) given by
\( \nodegenerator{\cp}{\dcomp_{2}}{\nodegenerator{\nodegenerator{\nodegenerator{\cp}{\dcomp_{2}}{\cocp}}{\tensor}{\id{}}}{\dcomp_{2}}{\cocp}} \).

The width of a decomposition is the cost of the most expensive node in the decomposition tree.

Let \(\nodeweight\) be a weight function for \((\cat{C},\decgenerators)\).
Let $f$ be in $\cat{C}$ and $d\in \decset{f}$.
The width of $d$ is defined recursively as follows:

\begin{align*}\label{eq:def-width-mon-dec}
\decwidth(d) \defn\ &  \nodeweight(f) & \text{if }d=\leafgenerator{f} \\
&  \max \{\decwidth(d_1),\decwidth(d_2)\} & \text{if }d= \nodegenerator{d_{1}}{\tensor}{d_{2}}\\
&  \max \{\decwidth(d_1),\,\nodeweight(X),\,\decwidth(d_2)\} & \text{if } d= \nodegenerator{d_{1}}{\dcomp_{X}}{d_{2}}
\end{align*}

As sketched in <Ref>, decompositions can be seen as labelled trees $(S,\mu)$ where $S$ is a tree  and $\mu:\vertices(S)\to \decgenerators \union \monoidaloperations{\cat{C}}$ is a labelling function. With this we can restate the width as:

\[
\decwidth(d)=\decwidth(S,\mlabelling) \defn \max_{v \in \vertices(S)} \nodeweight(\mlabelling(v))
\]

which may be familiar to those aquainted with graph widths.

Monoidal width is simply the width of the cheapest decomposition.

Let \(\nodeweight\) be a weight function for \((\cat{C},\decgenerators)\)
and $f$ be in $\cat{C}$. Then the monoidal width of $f$ is
\( \mwd(f) \defn \min_{d\in \decset{f}} \decwidth(d)\).

With the data of <Ref>, define a family of morphisms \(n \colon 1 \to 1\) inductively:

* \(1 \defn \id{1}\);

* \(2 \defn \cp \dcomp_{2} \cocp\);

* \(n+1 \defn \cp \dcomp_{2} (n \tensor 1) \dcomp_{2} \cocp\) for \(n \geq 2\).

Each \(n\) has a monoidal decomposition of width \(n\): the root node is the composition along the \(n\) wires in the middle.
However,  \(\mwd(n)=2\) for any \(n\), with an optimal  decomposition shown above.

§.§ The width of copying

Before we begin with the original technical contributions of this paper in Section <ref>, we need to recall a technical result from <cit.> about decomposing copy morphisms.

We consider symmetric monoidal categories equipped with such morphisms and show that copying \(n\) wires costs at most \(n+1\).

Let \(\cat{X}\) be a symmetric monoidal category with symmetries given by \(\swap{X,Y}\).
We say that \(\cat{X}\) has coherent copying if there is a class of objects $\mathcal{C}_\cat{X}\subseteq \obj{\cat{X}}$,
satifying $X,Y\in \mathcal{C}_\cat{X}$ iff $X\tensor Y \in \mathcal{C}_{X}$, such that
every \(X\) in \(\mathcal{C}_\cat{X}\)
is endowed with a morphism \(\cp_{X} \colon X \to X \tensor X\).
Moreover, \(\cp_{X \tensor Y} = (\cp_X \tensor \cp_Y) \dcomp (\id{X} \tensor \swap{X,Y} \tensor \id{Y})\) for every \(X,Y \in \mathcal{C}_\cat{X}\).

An example is any cartesian prop with \(\cp_{n} \colon n \to n + n\) given by the cartesian structure.
We take \(\cp_{X}\), the symmetries \(\swap{X,Y}\) and the identities \(\id{X}\) as atomic for all objects \(X, Y\), i.e. the set of atomic morphisms is \(\decgenerators = \{\cp_{X},\, \swap{X,Y},\, \id{X} \ :\  X, Y \in \mathcal{C}_\cat{X}\}\).
The weight function is \(\nodeweight(\cp_{X}) \defn 2 \cdot \nodeweight(X)\), \(\nodeweight(\swap{X,Y}) \defn \nodeweight(X) + \nodeweight(Y)\) and \(\nodeweight(\id{X}) \defn \nodeweight(X)\).
In a prop, we take \(\nodeweight(n) \defn n\).
Note that $\nodeweight(\cp_{X\tensor Y}) = 2 \cdot \nodeweight(X\tensor Y) =
2\cdot (\nodeweight(X) + \nodeweight(Y))$, but utilising coherence we can do better, as illustrated below.

Let \(\cat{C}\) be a prop with coherent copying and consider \(\cp_{n} \colon n \to 2n\).
Let \(\gamma_{n,m} \defn (\cp_{n} \tensor \id{m}) \dcomp (\id{n} \tensor \swap{n,m}) \colon n + m \to n + m + n\).
We can decompose \(\gamma_{n,m}\) in terms of \(\gamma_{n-1,m+1}\) (in the dashed box), \(\cp_{1}\) and \(\swap{1,1}\) by cutting along at most \(n+1+m\) wires:

This allows us to decompose \(\cp_{n} = \gamma_{n,0}\) cutting along at most \(n+1\) wires. In particular, $\mwd(\cp_n) \leq n+1$.

The following result is a technical generalisation of the argument presented in <Ref>.

Let \(\cat{X}\) be a symmetric monoidal category with coherent copying.
Suppose that \(\decgenerators\) contains \(\cp_X\) for \(X \in \mathcal{C}_{\cat{X}}\), and \(\swap{X,Y}\) and \(\id{X}\) for \(X \in \obj{\cat{X}}\). Let $\overline{X}\defn X_1 \tensor \cdots \tensor X_n$,
\(f \colon Y \tensor \overline{X} \tensor Z \to W\) and let \(d \in \decset{f}\).
Let \(\gamma(f) \defn (\id{Y} \tensor \cp_{\overline{X}} \tensor \id{Z}) \dcomp (\id{Y \tensor \overline{X}} \tensor \swap{\overline{X}, Z}) \dcomp (f \tensor \id{\overline{X}})\).

\(\gamma(f) \,\defn\quad\)

There is a decomposition \(\copyMdec(d)\) of \(\gamma(f)\) s.t. \(\decwidth(\copyMdec(d)) \leq \max \{\decwidth(d), \nodeweight(Y) + \nodeweight(Z) + (n+1) \cdot \max_{i = 1,\ldots,n} \nodeweight(X_i)\}\).

§ MONOIDAL WIDTH IN MATRICES

Bialgebra axioms

Given the ubiquity of matrix algebra, matrices are an obvious case study.

<Ref> shows that the monoidal width of a matrix is, up to \(1\), the maximum of the ranks of its blocks.

Consider the monoidal category \(\Mat_{\naturals}\) of matrices with entries in the natural numbers.
The objects are natural numbers and morphisms from \(n\) to \(m\) are \(m\) by \(n\) matrices.
Composition is the usual product of matrices and the monoidal product is the biproduct: \(A \tensor B \defn \begin{psmallmatrix}A & \zeromat \\ \zeromat & B \end{psmallmatrix}\).
Let us examine matrix decompositions enabled by this algebra.
A matrix \(A\) can be written as a monoidal product \(A = A_{1} \tensor A_{2}\) iff the matrix has blocks \(A_{1}\) and \(A_{2}\), i.e. \(A = \begin{psmallmatrix} A_{1} & \zeromat \\ \zeromat & A_{2}\end{psmallmatrix}\).
On the other hand, a composition is related to the rank.

Let \(A \colon n \to m\) in $\Mat_{\naturals}$.
Then \(\min\{k \in \naturals : A = B \dcomp_k C\} = \rank(A)\).

We first introduce a convenient syntax for matrices.

The category \(\Mat_{\naturals}\) is isomorphic to the prop \(\Bialg\), generated by \(\cp \colon 1 \to 2\), \(\delete \colon 1 \to 0\), \(\add \colon 2 \to 1\) and \(\zero \colon 0 \to 1\) and quotiented by bialgebra axioms (<Ref>).

For the uninitiated reader, let us briefly explain this correspondence.
Every morphism \(f \colon n \to m\) in \(\Bialg\) corresponds to a matrix \(A = \BialgToMat(f) \in \Mat_{\naturals}(m,n)\): we can read the \((i,j)\)-entry of \(A\) off the diagram of \(f\) by counting the number of  paths from the \(j\)th input to the \(i\)th output.

The matrix \(\begin{psmallmatrix} 1 & 0 \\ 1 & 2 \\ 0 & 0 \end{psmallmatrix} \in \Mat_{\naturals}(3,2)\) corresponds to

The atomic morphisms $\decgenerators$ are the generators of \(\Bialg\), with the symmetry and identity on \(1\):  \(\decgenerators = \{\cp,\delete,\add,\zero,\swap{},\id{1}\}\).
The weight  \(\nodeweight \colon \decgenerators \union \monoidaloperations{\Bialg} \to \naturals\) has \(\nodeweight(\dcompnode{n}) \defn n\), for any \(n \in \naturals\), and \(\nodeweight(g) \defn \max\{m,n\}\), for \(g \colon n \to m \in \decgenerators\).

§.§ Monoidal width in \(\Bialg\)

The characterisation of the rank of a matrix in <Ref> hints at some relationship between the monoidal width of a matrix and its rank.
In fact, we have <Ref>, which bounds the monoidal width of a matrix with its rank.
In order to prove this result, we first need to bound the monoidal width of a matrix with its domain and codomain, which is done in <Ref>.

Let \(\cat{P}\) be a cartesian and cocartesian prop.
Suppose that \(\id{1}, \cp_1, \add_1, \delete_1, \zero_1 \in \decgenerators\)
and \(\nodeweight(\id{1}) \leq 1\), \(\nodeweight(\cp_1) \leq 2\), \(\nodeweight(\add_1) \leq 2\), \(\nodeweight(\delete_1) \leq 1\) and \(\nodeweight(\zero_1) \leq 1\).
Suppose that, for every \(g \colon 1 \to 1\), \(\mwd(g) \leq 2\).
Let \(f \colon n \to m\) be a morphism in \(\cat{P}\).
Then \(\mwd(f) \leq \min\{m,n\}+1\).

The proof proceeds by induction on \(\max\{m,n\}\).
The base cases are easily checked.
The inductive step relies on the fact that, applying <Ref>, if \(n < m\), we can decompose \(f\) as shown below by cutting at most \(n+1\) wires or, if \(m <n\), in the symmetric way by cutting at most \(m+1\) wires.

\[\mwdMatlessthanBoundariesOneShort{}\]

The details can be found in <Ref>.

We can apply the former result to \(\Bialg\) and obtain <Ref> because the width of \(1 \times 1\) matrices, which are numbers, is at most \(2\).
This follows from the reasoning in <Ref> as we can write every natural number \(k \colon 1 \to 1\) as the following composition:

Let \(k \colon 1 \to 1\) in \(\Bialg\).
Then, \(\mwd(k) \leq 2\).

Let \(f \colon n \to m\) in \(\Bialg\).
Then, \(\mwd f \leq \rank(\BialgToMat f) +1\).
Moreover, if \(f\) is not \(\tensor\)-decomposable, i.e. there are no \(f_1,f_2\) both distinct from \(f\) s.t. \(f = f_1 \tensor f_2\), then \(\rank(\BialgToMat f) \leq \mwd f\).

This result follows from <Ref> and <Ref>, which we can apply thanks to <Ref>.
The details are in <Ref>.

The bounds given by <Ref> can be improven when we have a \(\tensor\)-decomposition of a matrix, i.e. we can write \(f = f_{1} \tensor \dots \tensor f_{k}\), to obtain <Ref>.
The latter relies on <Ref>, which shows that discarding inputs or outputs cannot increase the monoidal width of a morphism in \(\Bialg\).

Let \(f \colon n \to m\) in \(\Bialg\) and \(d \in \decset{f}\).
Let \(f_{D} \defn f \dcomp (\id{m-k} \tensor \delete_k)\) and \(f_{Z} \defn (\id{n-k'} \tensor \zero_{k'}) \dcomp f\), where \(\delete_{k} \colon k \to 0\) is the discard morphism with \(k \leq m\) and \(\zero_{k'} \colon 0 \to k\) is the zero morphism with \(k' \leq n\).

\[\mwdafterdiscardStateFig{}\]

Then there are \(\deleteMdec(d) \in \decset{f_{D}}\) and \(\codeleteMdec(d) \in \decset{f_{Z}}\) such that \(\decwidth(\deleteMdec(d)) \leq \decwidth(d)\) and \(\decwidth(\codeleteMdec(d)) \leq \decwidth(d)\).

By induction.
The base cases are easy.
If \(f = f_1 \dcomp f_2\), use the inductive hypothesis on \(f_{2}\).

\[\mwdafterdiscardProofFigTwo{}\]

The \(f = f_{1} \tensor f_{2}\) case is similar.

The details are in <Ref>.

Let \(f \colon n \to m\) in \(\Bialg\) and \(d' = \nodegenerator{d'_1}{\dcomp_k}{d'_2} \in \decset{f}\).
Suppose there are \(f_1\) and \(f_2\) such that \(f = f_1 \tensor f_2\).
Then, there is \(d = \nodegenerator{d_1}{\tensor}{d_2} \in \decset{f}\) such that \(\decwidth(d) \leq \decwidth(d')\).

By <Ref>, \(\rank(\BialgToMat f_{1}) + \rank(\BialgToMat f_{2}) = \rank(\BialgToMat(f_{1} \tensor f_{2})) \leq k\) and, by <Ref>, there is a monoidal decomposition \(d_{i}\) of \(f_{i}\) such that \(\decwidth(d_{i}) \leq \rank(\BialgToMat f_{i}) + 1\).
Then, \(\decwidth(d) \defn \decwidth(\nodegenerator{d_{1}}{\tensor}{d_{2}}) \leq \max \{\rank(\BialgToMat f_{1}), \rank(\BialgToMat f_{2})\} + 1 \leq \rank(\BialgToMat f_{1}) + \rank(\BialgToMat f_{2})\) whenever \(\rank(\BialgToMat f_{1}), \rank(\BialgToMat f_{2}) > 0\).
We apply <Ref> to obtain the same result if \(\rank(\BialgToMat f_1) = 0\) or \(\rank(\BialgToMat f_2) = 0\).
The details are in <Ref>.

We summarise <Ref> and <Ref> in <Ref>.

Let \(f = f_{1} \tensor \dots \tensor f_{k}\) in \(\Bialg\).
Then, \(\mwd(f) \leq \max_{i = 1,\dots,k} \rank(\BialgToMat(f_{i})) + 1\).
Moreover, if \(f_i\) are not \(\tensor\)-decomposable, then \(\max_{i = 1,\dots,k} \rank(\BialgToMat(f_{i})) \leq \mwd f\).

By <Ref> there is a decomposition of \(f\) of the form \(d = \nodegenerator{d_1}{\tensor}{\cdots \nodegenerator{d_{k-1}}{\tensor}{d_k}}\), where we can choose \(d_i\) to be a minimal decomposition of \(f_i\).
Then, \(\mwd(f) \leq \decwidth(d) = \max_{i = 1,\ldots,k} \decwidth(d_i)\).
By <Ref>, \(\decwidth(d_i) \leq r_i +1\).
Then, \(\mwd(f) \leq \max\{r_1,\ldots,r_k\}+1\).
Moreover, if \(f_i\) are not \(\tensor\)-decomposable, <Ref> gives also a lower bound on their monoidal width: \(\rank(\BialgToMat(f_{i})) \leq \mwd f_i\); and we obtain that \(\max_{i = 1,\dots,k} \rank(\BialgToMat(f_{i})) \leq \mwd f\).

The results so far show a way to construct efficient decompositions given a \(\tensor\)-decomposition of the matrix.
However, we do not know whether \(\tensor\)-decompositions are unique.
<Ref> shows that every morphism in \(\Bialg\) has a unique \(\tensor\)-decomposition.

Let \(\cat{C}\) be a monoidal category whose monoidal unit \(0\) is both initial and terminal, and whose objects are a unique factorization monoid.
Let \(f\) be a morphism in \(\cat{C}\).
Then \(f\) has a unique \(\tensor\)-decomposition.

See <Ref> for a proof sketch and the proof.

Our main result in this section follows from <Ref> and <Ref>, which can be applied to \(\Bialg\) because \(0\) is both terminal and initial, and the objects, being a free monoid, are a unique factorization monoid.

Let \(f = f_1 \tensor \ldots \tensor f_k\) be a morphism in \(\Bialg\) and its unique \(\tensor\)-decomposition given by <Ref>, with \(r_i = \rank(\BialgToMat(f_i))\).

Then \(\max\{r_1,\ldots,r_k\} \leq \mwd(f) \leq \max\{r_1,\ldots,r_k\}+1\).

This result is obtained by applying <Ref> to the \(\tensor\)-decomposition given by <Ref>, which can be applied because, in \(\Bialg\), \(0\) is both terminal and initial, and the objects, being a free monoid, are a unique factorization monoid.

Note that the identity matrix
has monoidal width \(1\)
and twice the identity matrix
has monoidal width \(2\), attaining both the upper and lower bounds for the monoidal width of a matrix.

§ GRAPHS AND RANK WIDTH

Here we recall rank width <cit.> for undirected graphs.

An undirected graph \(G = \mathgraph[,\edgeendsfun]{E}{V}\) is given by a set of edges \(E\), a set of vertices \(V\) and a function \(\edgeendsfun \colon E \to \parti_{\leq 2}(V)\) that gives the endpoints of each edge.
We consider graphs up to isomorphism, or abstract graphs, thus the set of vertices can be fully characterised by its cardinality.
An abstract graph can be equivalently given by an adjacency matrix \(\adjeqclass{G}\), where \(G \in \MatN(n,n)\) and \(n\) is the number of vertices.
The equivalence class of adjacency matrices is defined by the equivalence relation

\[G \adjeqrel H \quad \text{ iff } \quad G + \transpose{G} = H + \transpose{H}.\]

We will refer to abstract undirected graphs as simply graphs.

A path in a graph \(G\) is a sequence of edges \((e_{1}, \dots, e_{k})\) together with a sequence of distinct vertices \((v_{1},\dots,v_{k+1})\) of \(G\) such that, for every \(i = 1,\dots,k\), \(\edgeends{e_{i}} = \{v_{i}, v_{i+1}\}\).
A tree is a graph such that there is a unique path between any two of its vertices.
Two vertices \(v\) and \(w\) in a graph \(G\) are neighbours if \(G\) has an edge between them.
The leaves of a tree are those vertices with at most one neighbour.
A subcubic tree is a tree where each vertex has between one and three neighbours.

A rank decomposition for a graph \(G\) is a tree whose leaves are labelled with the vertices of \(G\).

A rank decomposition \((Y,r)\) of a graph \(G\) is given by a subcubic tree \(Y\) together with a bijection \(r \colon \leaves(Y) \to \vertices(G)\).

Each edge \(b\) in the tree \(Y\) determines a splitting of the graph: it determines a two partition of the leaves of \(Y\), which, through \(r\), determines a two partition \(\{A_b,B_b\}\) of the vertices of \(G\).
This corresponds to a splitting of the graph \(G\) into two subgraphs \(G_{1}\) and \(G_{2}\).
Intuitively, the order of an edge \(b\) is the amount of information required to recover \(G\) by joining \(G_{1}\) and \(G_{2}\).
Given the partition \(\{A_b,B_b\}\) of the vertices of \(G\), we can record the edges in \(G\) beween \(A_{b}\) and \(B_{b}\) in a matrix \(X_{b}\).
This means that, if \(v_{i} \in A_{b}\) and \(v_{j} \in B_{b}\), the entry \((i,j)\) of the matrix \(X_{b}\) is the number of edges between \(v_{i}\) and \(v_{j}\).

Let \((Y,r)\) be a rank decomposition of a graph \(G\).
Let \(b\) be an edge of \(Y\).
The order of \(b\) is the rank of the matrix associated to it: \(\edgeorder(b) \defn \rank(X_{b})\).

Note that the order of the two sets in the partition does not matter as the rank is invariant to transposition.
The width of a rank decomposition is the maximum order of the edges of the tree and the rank width of a graph is the width of its cheapest decomposition.

Given a rank decomposition \((Y,r)\) of a graph \(G\), define its width as \(\decwidth(Y,r) \defn \max_{b \in \edges(Y)} \edgeorder(b)\).
The rank width of \(G\) is given by the min-max formula:

\[\rankwidth(G) \defn \min_{(Y,r)} \decwidth(Y,r).\]

§.§ Graphs with dangling edges

As intermediate step between rank decompositions and monoidal decompositions, we introduce recursive rank decompositions of graphs with dangling edges and we prove that they give a notion of width that is equivalent to rank width.
Similar recursive characterisations were done for tree decompositions in <cit.> and for path and branch decompositions in <cit.>.

We first need a notion of graph that is equipped with some open edges along which it can be glued with other graphs.

A graph with dangling edges \(\Gamma = \danglinggraph{G}{B}\) is given by an adjacency matrix \(G \in \MatN(k,k)\) that records the connectivity of the graph and a matrix \(B \in \MatN(k,n)\) that records the “dangling edges” connected to $n$ boundary ports.
We will sometimes write \(G \in \adjacency(\Gamma)\) and \(B = \boundary(\Gamma)\).

Two graphs with the same ports, as illustrated below, can be glued together:

glued with  gives

Decompositions are elements of a tree data type, with nodes carrying subgraphs \(\Gamma'\) of the ambient graph \(\Gamma\).
In the following \(\Gamma'\) ranges over the non-empty subgraphs of \(\Gamma\):
\(T_{\Gamma} \ \Coloneqq \ \leafgenerator{\Gamma'} \ \mid \ \nodegenerator{T_{\Gamma}}{\Gamma'}{T_{\Gamma}}\).
Given $T\in T_\Gamma$, the label function $\labelling$ takes a decomposition and returns the graph with dangling edges at the root: $\labelling\nodegenerator{T_1}{\Gamma}{T_2} \defn \Gamma$ and \(\labelling\leafgenerator{\Gamma} \defn \Gamma\).

Let \(\Gamma = \danglinggraph{G}{B}\) be a graph with dangling edges, where \(G \in  \MatN(k,k)\) and \(B \in \MatN(k,n)\).
A recursive rank decomposition of \(\Gamma\) is \(T \in T_{\Gamma}\) where either:
\(\Gamma\) has at most one vertex and \(T = \leafgenerator{\Gamma}\);
or \(T = \nodegenerator{T_1}{\Gamma}{T_2}\) and \(T_i \in T_{\Gamma_i}\) are recursive rank decompositions of subgraphs \(\Gamma_i = \danglinggraph{G_i}{B_i}\) of \(\Gamma\) such that:

* The vertices are partitioned in two, \(G = \begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}\);

* The dangling edges are those to the original boundary and to the other subgraph, \(B_1 = (A_1 \mid C)\) and \(B_2 = (A_2 \mid \transpose{C})\), where \(B = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix}\).

As with before, the recursive rank width of a graph is the width of its cheapest decomposition.

Let \(T\) be a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B}\).
Define the width of \(T\) recursively:
if \(T = \leafgenerator{\Gamma}\), \(\decwidth(T) \defn \rank(B)\),
and, if \(T = \nodegenerator{T_{1}}{\Gamma}{T_{2}}\), \(\decwidth(T) \defn \max\{\decwidth(T_1), \decwidth(T_2), \rank(B)\}\)
Expanding this expression, we obtain
\(\decwidth(T) = \max_{T' \text{ subtree of } T} \rank(\boundary(\labelling(T')))\).
The recursive rank width of \(\Gamma\) is defined by the min-max formula
\(\rrankwidth(\Gamma) \defn \min_{T} \decwidth(T)\).

We show that recursive rank width is the same as rank width, up to the rank of the boundary of the graph.

Let \(\Gamma = \danglinggraph{G}{B}\) be a graph with dangling edges and \((Y,r)\) be a rank decomposition of \(G\).
Then, there is a recursive rank decomposition \(\toRecursiveDec(Y,r)\) of \(\Gamma\) s.t. \(\decwidth(\toRecursiveDec(Y,r)) \leq \decwidth(Y,r) + \rank(B)\).

See <Ref>.

Before proving the lower bound for recursive rank width, we need a technical lemma that relates the width of a graph with that of its subgraphs.

Let \(T\) be a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B}\).
Let \(T'\) be a subtree of \(T\) and \(\Gamma' \defn \labelling(T')\) with \(\Gamma'= \danglinggraph{G'}{B'}\).
The adjacency matrix of \(\Gamma\) can be written as \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} G_L & C_L & C \\ \zeromat & G' & C_R \\ \zeromat & \zeromat & G_R \end{psmallmatrix}}\) and its boundary as \(B = \begin{psmallmatrix} A_L \\ A' \\ A_R \end{psmallmatrix}\).
Then, \(\rank(B') = \rank(A' \mid \transpose{C_L} \mid C_R)\).

See <Ref>.

Let \(T\) be a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B}\) with \(G \in \MatN(k,k)\) and \(B \in \MatN(k,n)\).
Then, there is a rank decomposition \(\fromRecursiveDec(T)\) of \(G\) such that \(\decwidth(\fromRecursiveDec(T)) \leq \decwidth(T)\).

See <Ref>.

From <Ref> and <Ref> we conclude the following result.

Let \(\Gamma = \danglinggraph{G}{B}\).
\(\rankwidth(G) \leq \rrankwidth(\Gamma) \leq \rankwidth(G) + \rank(B)\).

§ MONOIDAL WIDTH AND RANK WIDTH

This section contains our main results.
We prove that monoidal width in the prop of graphs \(\propGraph\) <cit.> corresponds to rank width, up to a constant multiplicative factor of \(2\).

We start by introducing the algebra of graphs with boundaries
and its diagrammatic syntax <cit.>.
A graph with boundaries is a graph together with two matrices \(L\) and \(R\) that record the connectivity of the vertices with the left and right boundary, a matrix \(P\) that records the passing wires from the left boundary to the right one and a matrix \(F\) that records the wires from the right boundary to itself.

A graph with boundaries \(g \colon n \to m\) is defined as \(g = \fullboundariesgraph{G}{L}{R}{P}{F}\), where \(\adjeqclass{G}\) is the adjacency matrix of a graph on \(k\) vertices, with \(G \in \MatN(k,k)\); \(L \in \MatN(k,n)\),  \(R \in \MatN(k,m)\), \(P \in \MatN(m,n)\) and \(F \in \MatN(m,m)\) recording connectivity information as explained above.
Graphs with boundaries are taken up to an equivalence making the order of the vertices immaterial.
Let \(g, g' \colon n \to m\) on \(k\) vertices, with \(g = \fullboundariesgraph{G}{L}{R}{P}{F}\) and \(g' = \fullboundariesgraph{G'}{L'}{R'}{P}{F}\).
The graphs \(g\) and \(g'\) are considered equal iff
there is a permutation matrix \(\sigma \in \MatN(k,k)\) such that
\(g' = \fullboundariesgraph{\sigma G \transpose{\sigma}}{\sigma L}{\sigma R}{P}{F}\).

Graphs with boundaries can be composed sequentially and in parallel <cit.>, forming a symmetric monoidal category \(\catGraph\).

The prop \(\propGraph\) provides a convenient syntax for graphs with boundaries.
It is obtained by adding a cup and a vertex generators to the prop of matrices \(\Bialg\) (<Ref>).

The prop of graphs \(\propGraph\) is obtained by adding to \(\Bialg\) the generators \(\cup \colon 0 \to 2\) and \(\vertex \colon 1 \to 0\) with the equations below.

\[\propGraphEqFig{}\]

These equations mean, in particular, that the cup transposes matrices
(<Ref>, left) and that we can express the equivalence relation of adjacency matrices: \(G \adjeqrel H\) iff \(G + \transpose{G} = H + \transpose{H}\) (<Ref>, right).

\(\cupTransposeFig{}\)             \(\adjeqrelFig{}\)
Adding the cup.

The prop of graphs \(\propGraph\) is isomorphic to the prop \(\catGraph\).

<Ref> means that the morphisms in \(\propGraph\) can be written in the following normal form

\[\morphismpropgraphExFig{}.\]

The prop \(\propGraph\) is more expressive than graphs with dangling edges (<Ref>): its morphisms can have edges between the boundaries as well.
In fact, graphs with dangling edges can be seen as morphisms \(n \to 0\) in \(\propGraph\).

A graph with dangling edges \(\Gamma = \danglinggraph{G}{B}\) can be represented as a morphism in \(\propGraph\)

\[g = \fullboundariesgraph{G}{B}{\initmap}{\finmap}{\emptymat} = \danglinggraphExFig{}\quad.\]

We can now formalise the intuition of glueing graphs with dangling edges as explained in <Ref>.
The two graphs there correspond to \(g_{1}\) and \(g_{2}\) below left and middle.
Their glueing is obtained by precomposing their monoidal product with a cup, i.e.  \(\cup_{2} \dcomp (g_{1} \tensor g_{2})\), as shown below right.

\[\danglinggraphGlueingExFig\]

§.§ Rank width in open graphs

The technical content of our main result (<Ref>) is split in two: an upper  and a lower bound.

As in the prop of matrices \(\Bialg\), the cost of composing along \(n\) wires is \(n\).
All morphisms in \(\propGraph\) are chosen as atomic.
One could restrict this to those with at most one vertex without affecting the results.

Let the set of atomic morphisms \(\decgenerators\) be the set of all the morphisms of \(\propGraph\).
The weight function \(\nodeweight \colon \decgenerators \union \monoidaloperations{\propGraph} \to \naturals\) is defined, on objects \(n\), as \(\nodeweight(\dcompnode{n}) \defn n\); and, on morphisms \(g \in \decgenerators\), as \(\nodeweight(g) \defn k\), where \(k\) is the number of vertices of \(g\).

Note that the monoidal width of \(g\) is bounded by the number of its vertices.

The upper bound (<Ref>) is established by associating to each recursive rank decomposition a suitable monoidal decomposition.
This mapping is defined inductively, given the inductive nature of both these structures.
Given a recursive rank decomposition of a graph \(\Gamma\), we can construct a decomposition of its corresponding morphism \(g\) as shown by the first equality in <Ref>.

\[\mwdrwdupperproofFigOneCuts{}\]

First step of a monoidal decomposition given by a recursive rank decomposition

However, this decomposition is not optimal as it cuts along the number of vertices \(k_{1} + k_{2}\).
But we can do better thanks to <Ref>, which shows that we can cut along the ranks, \(r_1 = \rank(A_1 \mid C)\) and \(r_2 = \rank(A_2 \mid \transpose{C})\), of the boundaries of the induced subgraphs to obtain the second equality in <Ref>.

\[\lemmacutalongranksIdeaFig{}\]

Let \(A_i \in \MatN(k_i,n)\), for \(i = 1,2\), and \(C \in \MatN(k_1,k_2)\).
Then, there are rank decompositions of \((A_1 \mid C)\) and \((A_2 \mid \transpose{C})\) of the form \((A_1 \mid C) = L_1 \cdot (N_1 \mid S \cdot \transpose{L_2})\), and \((A_2 \mid \transpose{C}) = L_2 \cdot (N_2 \mid \transpose{S} \cdot \transpose{L_1})\).

See <Ref>.

Once we have performed the cuts in <Ref> on the right, we have changed the boundaries of the induced subgraphs.
This means that we cannot apply the inductive hypothesis right away, but we need to transform first the recursive rank decompositions of the old subgraphs into decompositions of the new ones, as shown in <Ref>.
More explicitly, when \(M\) has full rank, if we have a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B' \cdot M}\), which corresponds to \(g\) below left, we can obtain one of \(\Gamma' = \danglinggraph{G}{B'}\), which corresponds to \(g'\) below right, of the same width.

\[\lemmarankonboundaryIdeaFig{}\]

Let \(T\) be a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B}\) and \(B = B' \cdot M\), with \(M\) that has full rank.
Then, there is a recursive rank decomposition \(T'\) of \(\Gamma' = \danglinggraph{G}{B'}\) such that \(\decwidth(T) = \decwidth(T')\) and such that \(T\) and \(T'\) have the same underlying tree structure.

See <Ref>.

With the above ingredients, we can show that rank width bounds monoidal width from above.

Let \(\Gamma = \danglinggraph{G}{B}\) be a graph with dangling edges and \(g \colon n \to 0\) be the morphism in \(\propGraph\) corresponding to \(\Gamma\).
Let \(T\) be a recursive rank decomposition of \(\Gamma\).
Then, there is a monoidal decomposition \(\rTomdec(T)\) of \(g\) such that \(\decwidth(\rTomdec(T)) \leq 2 \cdot \decwidth(T)\).

The proof proceeds by induction on \(T\).
The base cases are easily checked and the inductive step relies on the decomposition of \(g\) in <Ref>, which we can write thanks to <Ref>.
Applying the inductive hypothesis and <Ref>, the width of this decomposition can be bounded by \(\max \{r_1 + r_2, 2 \cdot \decwidth(T_1),  2 \cdot \decwidth(T_2)\} \leq 2 \cdot \decwidth(T)\), where \(T = \nodegenerator{T_1}{\Gamma}{T_2}\).
The details are in <Ref>.

Proving the lower bound is similarly involved and follows a similar proof structure.
From a monoidal decomposition we construct inductively a recursive rank decomposition of bounded width.
The inductive step relative to composition nodes is the most involved and needs two additional lemmas, which allow us to transform recursive rank decompositions of the induced subgraphs into ones of two subgraphs that satisfy the conditions of <Ref>.

Applying the inductive hypothesis gives us a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{(L \mid R)}\), which is associated to \(g\) below left, and we need to construct one of \(\Gamma' \defn \danglinggraph{G + L \cdot F \cdot \transpose{L}}{(L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P})}\), which is associated to \(f \dcomp g\) below right, of at most the same width.

\[\lemmawirestofutureIdeaFig{}\]

Let \(T\) be a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{(L \mid R)}\), with \(G \in \MatN(k,k)\), \(L \in \MatN(k,j)\) and \(R \in \MatN(k,m)\).
Let \(F \in \MatN(j,j)\), \(P \in \MatN(m,j)\) and define \(\Gamma' \defn \danglinggraph{G + L \cdot F \cdot \transpose{L}}{(L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P})}\).
Then, there is a recursive rank decomposition \(T'\) of \(\Gamma'\) such that \(\decwidth(T') \leq \decwidth(T)\).

See <Ref>.

In order to obtain the subgraphs of the desired shape we need to add some extra connections to the boundaries.
We have a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B}\), which corresponds to \(g\) below left, and we need one of \(\Gamma' = \danglinggraph{G}{B \cdot M}\), which corresponds to \(g'\) below right, of at most the same width.

\[\lemmaaddtoboundaryIdeaFig{}\]

The following result and its proof are very similar to <Ref>.

Let \(T\) be a recursive rank decomposition of \(\Gamma = \danglinggraph{G}{B}\) and let \(B' = B \cdot M\).
Then, there is a recursive rank decomposition \(T'\) of \(\Gamma' = \danglinggraph{G}{B'}\) such that \(\decwidth(T') \leq \decwidth(T)\) and such that \(T\) and \(T'\) have the same underlying tree structure.
Moreover, if \(M\) has full rank, then \(\decwidth(T') = \decwidth(T)\).

See <Ref>.

Let \(g = \fullboundariesgraph{G}{L}{R}{P}{F}\) in \(\propGraph\) and \(d \in \decset{g}\).
Let \(\Gamma = \danglinggraph{G}{(L \mid R)}\).
Then, there is a recursive rank decomposition \(\mTordec(d)\) of \(\Gamma\) s.t.
\(\decwidth(\mTordec(d)) \leq 2 \cdot \max \{\decwidth(d), \rank(L), \rank(R)\}\).

The proof proceeds by induction on \(d\).
The base case is easily checked, while the inductive steps are a bit more involved.
If \(d = \nodegenerator{d_1}{\dcomp_j}{d_2}\), then there are \(g_i = \fullboundariesgraph{G_i}{L_i}{R_i}{P_i}{F_i}\) such that \(g = g_1 \dcomp g_2\) and we can write \(g\) as follows.

\[\mwdrankwidthlowerproofFigFuture{}\]

In order to build a recursive rank decomposition of \(\Gamma\), we need recursive rank decompositions of \(\overline{\Gamma}_i = \danglinggraph{\overline{G}_i}{\overline{B}_i}\), but we can obtain recursive rank decompositions of \(\Gamma_i = \danglinggraph{G_i}{(L_i \mid R_i)}\) by applying only induction.
Thanks to <Ref>, we obtain a recursive rank decomposition of \(\Gamma'_2 = \danglinggraph{G_2 + L_2 \cdot F_1 \cdot \transpose{L_2}}{(L_2 \mid R_2 + L_2 \cdot (F_1 + \transpose{F_1}) \cdot \transpose{P_2})}\).
Lastly, we apply <Ref> to get recursive rank decompositions \(T_i\) of \(\overline{\Gamma}_i\).
Thanks to these, we can bound the width of \(T \defn \nodegenerator{T_1}{\Gamma}{T_2}\):

\[\decwidth(T) \leq 2 \cdot \max \{\decwidth(d_1), \decwidth(d_2), j, \rank(L), \rank(R)\} \codefn 2 \cdot \max \{\decwidth(d), \rank(L), \rank(R)\}.\]

If \(d = \nodegenerator{d_1}{\tensor}{d_2}\), we proceed similarly.
For the details, see <Ref>.

From <Ref>, <Ref> and <Ref>, we obtain our main result.

Let \(G\) be a graph and let \(g = \fullboundariesgraph{G}{\initmap}{\initmap}{\emptymat}{\emptymat}\) be the corresponding morphism of \(\propGraph\).
Then, \(\frac{1}{2} \cdot \rankwidth(G) \leq \mwd(g) \leq 2 \cdot \rankwidth(G)\).

§ CONCLUSIONS AND FUTURE WORK

We have shown that monoidal width, in a suitable category of graphs composable along open edges, yields rank width; a well-known measure from the graph theory literature.

Our goal with this line of research is to develop a generic, abstract “decomposition theory”.
We will study other graph widths like clique width and twin width, as well as go beyond graphs: e.g. by focussing on tree width for hypergraphs and relational structures, branch width for matroids and widths for directed graphs.
A part of decomposition theory means going beyond width as a mere number – in fact we believe that in each case the identification of a suitable monoidal category as an algebra of open graph structures is itself a worthwhile contribution. Indeed, having such an algebra means that a decomposition, rather than an ad hoc concept-specific construction, becomes more of a mathematical object in its own right.  Such compositional algebras will add to the quiver of compositional structures of applied category theory; for example serving as syntax for more sophisticated applications <cit.>.

Elena Di Lavore and Paweł Sobociński were supported by the European Union through the ESF funded Estonian IT Academy research measure (2014-2020.4.05.19-0001). This work was also supported by the Estonian Research Council grant PRG1210.

§ MATRICES

By induction on \(d\).

If the decomposition has only one node, \(d = \leafgenerator{f}\), then \(f\) is one of the six atoms in the first column of the table below.
The second and third columns show the decompositions of \(f_{D}\) for \(k = 1\) and \(k=2\).

If the decomposition starts with a composition node, \(d = \nodegenerator{d_{1}}{\dcomp}{d_{2}}\), then \(f = f_1 \dcomp f_2\), with \(d_{i}\) monoidal decomposition of \(f_i\).

By induction, there is a monoidal decomposition \(\deleteMdec(d_2)\) of \(f_2 \dcomp (\id{m-k} \tensor \delete_k)\) such that \(\decwidth(\deleteMdec(d_2)) \leq \decwidth(d_2)\).
Let \(\deleteMdec(d) \defn \nodegenerator{d_1}{\dcomp}{\deleteMdec(d_2)}\).
Then, \(\deleteMdec(d)\) is a monoidal decomposition of \(f \dcomp (\id{m-k} \tensor \delete_k)\) because \(f \dcomp (\id{m-k} \tensor \delete_k) = f_1 \dcomp (f_2 \dcomp \id{m-k} \tensor \delete_k)\).

If the decomposition starts with a tensor node, \(d = \nodegenerator{d_1}{\tensor}{d_2}\), then \(f = f_1 \tensor f_2\), with \(d_i\) monoidal decomposition of \(f_i \colon n_i \to m_i\).
There are two possibilities: either \(k \leq m_{2}\) or \(k > m_{2}\).
If \(k \leq m_2\), then \(f \dcomp (\id{m-k} \tensor \delete_k) = f_1 \tensor (f_2 \dcomp (\id{m_2-k} \tensor \delete_k))\).

By induction, there is a monoidal decomposition \(\deleteMdec(d_2)\) of \(f_2 \dcomp (\id{m-k} \tensor \delete_k)\) such that \(\decwidth(\deleteMdec(d_2)) \leq \decwidth(d_2)\).
Then, \(\deleteMdec(d) \defn \nodegenerator{d_1}{\tensor}{\deleteMdec(d_2)}\) is a monoidal decomposition of \(f \dcomp (\id{m-k} \tensor \delete_k)\).
If \(k > m_2\), then \(f \dcomp (\id{m-k} \tensor \delete_k) = (f_1 \dcomp (\id{m_1 - k + m_2} \tensor \delete_{k-m_2})) \tensor (f_2 \dcomp \delete_{m_2})\).

By induction, there are monoidal decompositions \(\deleteMdec(d_i)\) of \(f_1 \dcomp (\id{m_1-k+m_2} \tensor \delete_{k-m_2})\) and \(f_2 \dcomp \delete_{m_2}\) such that \(\decwidth(\deleteMdec(d_i)) \leq \decwidth(d_i)\).
Then, \(\deleteMdec(d) \defn \nodegenerator{\deleteMdec(d_1)}{\tensor}{\deleteMdec(d_2)}\) is a monoidal decomposition of \(f \dcomp (\id{m-k} \tensor \delete_k)\).

The second inequality is proven using the same inductive argument.

By hypothesis, \(d'\) is a monoidal decomposition of \(f\).
Then, there are \(g\) and \(h\) such that \(f_1 \tensor f_2 = f = g \dcomp h\).
By <Ref>, there are monoidal decompositions \(d_i\) of \(f_i\) with \(\decwidth(d_i) \leq r_i + 1\), where \(r_i \defn \rank(\BialgToMat f_i)\).
By properties of the rank, \(r_1 + r_2 = \rank(\BialgToMat f)\).
By <Ref>, \(\rank(\BialgToMat f) \leq k\).
There are two cases.

If \(r_i > 0\), then \(r_1 + r_2 \geq \max\{r_1,r_2\}+1\).

\begin{align*}
& \decwidth(d') \\
& = \max\{\decwidth(d'_1), k, \decwidth(d'_2)\} \\
& \geq k \\
& \geq \rank(\BialgToMat f) \\
& = r_1 + r_2 \\
& \geq \max\{r_1,r_2\}+1 \\
& \geq \max\{\decwidth(d_1), \decwidth(d_2)\} \\
& = \decwidth(d)
\end{align*}

If there is \(r_i = 0\), then \(f_i = \delete \dcomp_0 \zero\).
We may assume that \(f_1 = \delete \dcomp_0 \zero\).
Then, \(f_2 = (\id{} \tensor \zero) \dcomp g \dcomp_k h \dcomp (\id{} \tensor \delete)\).
By <Ref>, \(\mwd((\id{} \tensor \zero) \dcomp g) \leq \mwd(g)\) and \(\mwd(h \dcomp (\id{} \tensor \delete)) \leq \mwd(h)\).

\begin{align*}
& \decwidth(d') \\
& = \max\{\decwidth(d'_1), k, \decwidth(d'_2)\}\\
& \geq \max\{\mwd(g), k, \mwd(h)\} \\
& \geq \max\{\mwd((\id{} \tensor \zero) \dcomp g), k, \mwd(h \dcomp (\id{} \tensor \delete))\} \\
& \geq \mwd(f_2)\\
& = \decwidth(d_2)\\
& = \decwidth(d)
\end{align*}

Suppose \(f = f_1 \tensor \cdots \tensor f_m = g_1 \tensor \cdots \tensor g_n\) with \(f_i \colon X_i \to Y_i\) and \(g_j \colon Z_j \to W_j\) non \(\tensor\)-decomposables.
Suppose \(m \leq n\) and proceed by induction on \(m\).
By induction, \(\bar{f} \defn f_{1} \tensor \dots \tensor f_{m-1}\) has a unique \(\tensor\)-decomposition and we obtain

Then, \(k = m-1\), for every \(i < m-1\) \(f_{i} = g_{i}\) and \(f_{m-1} = (\id{} \tensor \zero) \dcomp g_{k} \dcomp (\id{} \tensor \delete)\).
With a similar argument, we obtain that \(n = m\), \(f_{m-1} = g_{m-1}\) and \(f_{m} = g_{m}\).

The details of this proof can be found below.

Suppose \(f = f_1 \tensor \cdots \tensor f_m = g_1 \tensor \cdots \tensor g_n\) with \(f_i \colon X_i \to Y_i\) and \(g_j \colon Z_j \to W_j\) non \(\tensor\)-decomposables.
Suppose \(m \leq n\) and proceed by induction on \(m\).

If \(m=0\), then \(f = \id{0}\) and \(g_{i} = \id{0}\) for every \(i = 1,\dots,n\) because \(0\) is initial and terminal.

Suppose that \(\bar{f} \defn f_{1} \tensor \dots \tensor f_{m-1}\) has a unique \(\tensor\)-decomposition.
Let \(A_{1} \tensor \dots \tensor A_{\alpha}\) and \(B_{1} \tensor \dots \tensor B_{\beta}\) be the unique \(\tensor\)-decompositions of \(X_{1} \tensor \dots \tensor X_{m} = Z_{1} \tensor \dots \tensor Z_{n}\) and \(Y_{1} \tensor \dots \tensor Y_{m} = W_{1} \tensor \dots \tensor W_{n}\), respectively.
Then, there are \(x \leq \alpha\) and \(y \leq \beta\) such that \(A_{1} \tensor \dots \tensor A_{x} = X_{1} \tensor \dots \tensor X_{m-1}\) and \(B_{1} \tensor \dots \tensor B_{y} = Y_{1} \tensor \dots \tensor Y_{m-1}\).

\begin{align*}
& \bar{f} \\
& = (\id{A_{1} \tensor \dots \tensor A_{x}} \tensor \zero_{A_{x+1} \tensor \dots \tensor A_{\alpha}}) \dcomp f \\
& \qquad \dcomp (\id{B_{1} \tensor \dots \tensor B_{y}} \tensor \delete_{B_{y+1} \tensor \dots \tensor B_{\beta}}) \\
& = (\id{A_{1} \tensor \dots \tensor A_{x}} \tensor \zero_{A_{x+1} \tensor \dots \tensor A_{\alpha}}) \dcomp (g_1 \tensor \cdots \tensor g_n) \\
& \qquad \dcomp (\id{B_{1} \tensor \dots \tensor B_{y}} \tensor \delete_{B_{y+1} \tensor \dots \tensor B_{\beta}}) \\
& = g_{1} \tensor \dots \tensor g_{k-2} \tensor ((\id{} \tensor \zero) \dcomp g_{k-1} \dcomp (\id{} \tensor \delete))
\end{align*}

By induction hypothesis, it must be that \(k = m-1\), for every \(i < m-1\) \(f_{i} = g_{i}\) and \(f_{m-1} = (\id{} \tensor \zero) \dcomp g_{k} \dcomp (\id{} \tensor \delete)\).

\begin{align*}
& = (\zero \tensor \id{X_{m}}) \dcomp f \dcomp (\delete \tensor \id{Y_{m}})\\
& = (\zero \tensor \id{X_{m}}) \dcomp (g_{1} \tensor \dots \tensor g_{n}) \dcomp (\delete \tensor \id{Y_{m}})\\
& = ((\zero \tensor \id{}) \dcomp g_{m-1} \dcomp (\delete \tensor \id{})) \tensor g_{m} \tensor \dots \tensor g_{n}
\end{align*}

By hypothesis, \(f_{m}\) is not \(\tensor\)-decomposable and \(m \leq n\).
Thus, \(n = m\), \(f_{m-1} = g_{m-1}\) and \(f_{m} = g_{m}\).

We proceed by induction on \(k = \max\{m,n\}\).

Base cases.

* If \(n = 0\), then \(f = \zero_m\) because \(0\) is initial by hypothesis.
Then, \(\mwd(f) = \mwd(\Tensor_m \zero_1) \leq \nodeweight(\zero_1) \leq 1 \leq 0 + 1 \).

* If \(m = 0\), then \(f = \delete_n\) because \(0\) is terminal by hypothesis.
Then, \(\mwd(f) = \mwd(\Tensor_m \delete_1) \leq \nodeweight(\delete_1) \leq 1 \leq 0 + 1 \).

* If \(m = n = 1\), then \(\mwd(f) \leq 2 \leq 1+1\) by hypothesis.

Induction steps.
Suppose that the statement is true for any \(f' \colon n' \to m'\) with \(\max\{m',n'\} < k = \max\{m,n\}\) and \(\min \{m',n'\} \geq 1\).
There are two possibilities.

* If \(0 < n < m = k\), then \(f\) can be decomposed as shown below because \(\cp_{n+1}\) is uniform by hypothesis and morphisms are copiable because \(\cat{P}\) is cartesian by hypothesis.

\[\mwdMatlessthanBoundariesOne{}\]

This corresponds to \(f = \cp_n \dcomp (\id{n} \tensor h_1) \dcomp_{n+1} (h_2 \tensor \id{1})\), where \(h_1 \defn f \dcomp (\delete_{m-1} \tensor \id{1}) \colon n \to 1\) and \(h_2 \defn f \dcomp (\id{m-1} \tensor \delete_1) \colon n \to m-1\).

Then, \(\mwd(f) \leq \max\{\mwd(\cp_n \dcomp (\id{n} \tensor h_1)),n+1,\mwd(h_2 \tensor \id{1})\}\).
So, we want to bound the monoidal width of the two morphisms appearing in the formula above.
For the first morphism,

\begin{align*}
& \mwd(\cp_n \dcomp (\id{n} \tensor h_1)) \\
\explain[\leq]{by~\Cref{lemma:mwd-copy}}\\
& \max\{\mwd(h_1),n+1\} \\
\explain[\leq]{by induction hypothesis}\\
& \max\{\min\{n,1\}+1,n+1\} \\
\explain{because \(0 < n\)}\\
& = n+1
\end{align*}

where we could apply the induction hypothesis because \(h_1 \colon n \to 1\) and \(1 , n < k\).

For the second morphism,

\begin{align*}
& \mwd(h_2 \tensor \id{1}) \\
\explain[\leq]{by definition}\\
& \mwd(h_2) \\
\explain[\leq]{by induction hypothesis}\\
& \min\{n,m-1\}+1\\
\explain{because \(n \leq m-1\)}\\
& n+1
\end{align*}

where we could apply the induction hypothesis because \(h_2 \colon n \to m-1\) and \(n, m-1 < k\).

Then, \(\mwd(f) \leq n+1 = \min\{m,n\}+1\) because \(n<m\).

* If \(0<m \leq n=k\), then \(f\) can be decomposed as shown below because \(\add_{n+1}\) is uniform by hypothesis and morphisms are cocopiable because \(\cat{P}\) is cocartesian by hypothesis.

\[\mwdMatlessthanBoundariesTwo{}\]

This corresponds to \(f = (h_1 \tensor \id{1}) \dcomp_{m+1} (\id{m} \tensor h_2) \dcomp \add_m\), where \(h_1 \defn (\id{n-1} \tensor \zero_1) \dcomp f \colon n-1 \to m\) and \(h_2 \defn (\zero_{n-1} \tensor \id{1}) \dcomp f \colon 1 \to m\).

Then, \(\mwd(f) \leq \max\{\mwd(h_1 \tensor \id{1}),m+1,\mwd((\id{m} \tensor h_2) \dcomp \add_m)\}\).
So, we want to bound the monoidal width of the two morphisms appearing in the formula above.
For the first morphism,

\begin{align*}
& \mwd(h_1 \tensor \id{1}) \\
\explain[\leq]{by definition}\\
& \mwd(h_1) \\
\explain[\leq]{by induction hypothesis or point 1}\\
& \min \{n-1,m\} +1 \\
\explain[\leq]{because \(m \leq n\)}\\
& m + 1
\end{align*}

where, if \(m < n\), we could apply the induction hypothesis because \(n-1,m < k\), or, if \(m = n\), we could apply point 1 because \(n-1 < m = k\).
For the second morphism,

\begin{align*}
& \mwd((\id{m} \tensor h_2) \dcomp \add_m)\\
\explain[\leq]{by~\Cref{lemma:mwd-copy}}\\
& \max\{\mwd(h_2),m+1\}\\
\explain[\leq]{by induction hypothesis of point 1}\\
& \max\{\min\{1,m\}+1,m+1\} \\
\explain{because \(m \geq 1\)}\\
& m+1
\end{align*}

where, if \(m < n\), we could apply the induction hypothesis because \(h_1 \colon n \to 1\) and \(1 , n < k\), and, if \(m = n\), we could apply point 1 because \(1 < m = k\).

Then, \(\mwd(f) \leq \max\{m+1,m+1,m+1\} = m+1 = \min\{m,n\}+1\) because \(m \leq n\).

We prove the second inequality.
Let \(d\) be a monoidal decomposition of \(f\).
By hypothesis, \(f\) is non \(\tensor\)-decomposable.
Then, there are two options.

If \(d = \leafgenerator{f}\), then either \(\nodeweight(\swap{}) = 2 \geq \rank(\BialgToMat (\swap{})) = 2\), \(\nodeweight(\cp_1) = \nodeweight(\add_1) = 2  \geq \rank(\BialgToMat (f)) = 1\) or \(\nodeweight(\delete_1) = \nodeweight(\zero_1) = 1 \geq \rank(\BialgToMat f) = 0\).
Then, \(\decwidth(d) = \nodeweight(f) \geq \rank(\BialgToMat (f))\).

If \(d = \nodegenerator{d_1}{\dcomp_k}{d_2}\), then there are \(g \colon n \to k\) and \(h \colon k \to m\) such that \(f = g \dcomp h\).
By <Ref>, \(k \geq \rank(\BialgToMat (f))\).
Then, \(\decwidth(d) \geq k \geq \rank(\BialgToMat (f))\).

We prove the first inequality.
By <Ref>, there are \(g \colon n \to r\) and \(h \colon r \to m\) such that \(f = g \dcomp h\) with \(r = \rank(\BialgToMat (f))\).
Then, \(r \leq m,n\) by definition of rank.
By <Ref>, we can apply <Ref> to obtan that \(\mwd(g) \leq \min\{n,r\}+1 = r+1\) and \(\mwd(h) \leq \min\{m,r\}+1 = r+1\).
Then, \(\mwd(f) \leq \max\{\mwd(g),r,\mwd(h)\} \leq r+1\).

§ RECURSIVE RANK WIDTH

Proceed by induction on \(\card{\edges(Y)}\).

If \(\card{\edges(Y)} = 0\), then either \(G = \emptyset\) or \(G\) has one vertex.
In either case, we define \(\toRecursiveDec(Y,r) \defn \leafgenerator{\Gamma}\) and obtain \(\decwidth(\toRecursiveDec(Y,r)) \defn \rank(B) \leq \decwidth(Y,r) + \rank(B)\).

If \(\card{\edges(Y)} > 0\), then \(Y = Y_1 \text{---} Y_2\) with \(Y_1\) and \(Y_2\) subcubic trees.
Let \(V_i \defn r(\leaves(Y_i))\) and \(G_i \defn \subgraphon{G}{V_i}\) be the subgraph of \(G\) on the vertices \(V_i\).
Since \(\{V_1, V_2\}\) is a partition of the vertices of \(G\) because \((Y,r)\) is a rank decomposition of \(G\), then we can write \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}}\), \(B = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix}\), \(B_1 = (A_1 \mid C)\) and \(B_2 = (A_2 \mid \transpose{C})\).
By induction hypothesis, there are recursive rank decompositions \(T_i\) of \(\Gamma_i = \danglinggraph{G_i}{B_i}\).
Then, \(T = \nodegenerator{T_1}{\Gamma}{T_2}\) is a recursive rank decomposition of \(\Gamma\) and, by applying <Ref>,

\begin{align*}
& \decwidth(T) \\
& \defn \max\{\decwidth(T_1), \decwidth(T_2), \rank(B)\}\\
& = \max_{T' \subtreeq T} \rank(\boundary(\labelling(T')))\\
& = \max_{T' \subtreeq T} \rank(A'\mid C')\\
& \leq \max_{T' \subtreeq T} \rank(C') + \rank(B)\\
& = \max_{b \in \edges(Y)} \edgeorder(b) + \rank(B)\\
& \codefn \decwidth(Y,r) + \rank(B)
\end{align*}

Proceed by induction on \(T\).

If \(T = \leafgenerator{\Gamma}\), then \(\Gamma' = \emptyset\) or \(\Gamma' = \Gamma\) and we are done.

If \(T = \nodegenerator{T_1}{\Gamma}{T_2}\), then \(\labelling(T_i) = \Gamma_i = \danglinggraph{G_i}{B_i}\) with \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}}\), \(B = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix}\), \(B_1 = (A_1 \mid C)\) and \(B_2 = (A_2 \mid \transpose{C})\).
Suppose that \(T' \subseteq T_1\).
Then, we can write \(\adjeqclass{G_1} = \adjeqclass{\begin{psmallmatrix} G_L & C_L & D' \\ \zeromat & G' & D_R \\ \zeromat & \zeromat & H_R \end{psmallmatrix}}\), \(A_1 = \begin{psmallmatrix}A_L \\ A' \\ F_R\end{psmallmatrix}\) and \(C = \begin{psmallmatrix}E_L \\ E' \\ E_R\end{psmallmatrix}\).
It follows that \(B_1 = \begin{psmallmatrix}A_L & E_L \\ A' & E' \\ F_R & E_R\end{psmallmatrix}\) and \(C_R = (D_R \mid E')\).
By induction hypothesis, \(\rank(B') = \rank(A' \mid E' \mid \transpose{C_L} \mid D_R)\).
The rank is invariant to permuting the order of columns, thus \(\rank(B') = \rank(A' \mid \transpose{C_L} \mid D_R \mid E') = \rank(A' \mid \transpose{C_L} \mid C_R)\).
We proceed analogously if \(T' \subseteq T_2\).

A binary tree is, in particular, a subcubic tree.
Then, we can define \(Y\) to be the unlabelled tree underlying \(T\).
The label of a leaf \(l\) of \(T\) is a subgraph of \(\Gamma\) with one vertex \(v_l\).
Then, there is a bijection \(r \colon \leaves(T) \to \vertices(G)\) such that \(r(l) \defn v_l\).
Then, \((Y,r)\) is a branch decomposition of \(G\) and we can define \(\fromRecursiveDec(T) \defn (Y,r)\).

By construction, \(b \in \edges(Y)\) if and only if \(b \in \edges(T)\).
Let \(\{v,v_b\} = \edgeends{b}\) with \(v\) parent of \(v_b\) in \(T\) and let \(T_b\) the subtree of \(T\) with root \(v_b\), with \(\labelling(T_b) = \Gamma_b = \danglinggraph{G_b}{B_b}\).
Then, we can write \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} G_L & C_L & C \\ \zeromat & G_b & C_R \\ \zeromat & \zeromat & G_R \end{psmallmatrix}}\) and \(B = \begin{psmallmatrix}A_L \\ A' \\ A_R\end{psmallmatrix}\).
By <Ref>, \(\rank(B_b) = \rank(A' \mid \transpose{C_L} \mid C_R)\).
By <Ref>, \(\edgeorder(b) \defn \rank(\transpose{C_L} \mid C_R)\).
Then, \(\rank(B_b) \geq \edgeorder(b)\) and

\begin{align*}
& \decwidth(Y,r) \\
& \defn \max_{b \in \edges(Y)} \edgeorder(b)\\
& \leq \max_{b \in \edges(Y)} \rank(B_b) \\
& \leq \max_{T' \subseteq T} \rank(\boundary(\labelling(T')))\\
& \codefn \decwidth(T)
\end{align*}

§ MONOIDAL WIDTH AND RANK WIDTH

Proceed by induction on \(T\).

If \(T = \leafgenerator{\Gamma}\), then we define \(T' \defn \leafgenerator{\Gamma'}\).
Clearly, \(T\) and \(T'\) have the same underlying tree structure.
Since \(M\) has full rank, we can compute \(\decwidth(T') \defn \rank(B') = \rank(B' \cdot M) \codefn \decwidth(T)\).

If \(T = \nodegenerator{T_1}{\Gamma}{T_2}\), then \(G = \begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}\), \(B_1 = (A_1 \mid C)\) and \(B_2 = (A_2 \mid \transpose{C})\), where \(B = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix}\) where \(\Gamma_i \defn \labelling_i(T_i)\), \(B_i \defn \boundary(\Gamma_i)\), \(G_i = \adjacency(\Gamma_i)\) and \(A_i \in \MatN(n,k_i)\).
Then, \(\begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix} = \begin{psmallmatrix} A'_1 \\ A'_2 \end{psmallmatrix} \cdot M = \begin{psmallmatrix} A'_1 \cdot M \\ A'_2 \cdot M \end{psmallmatrix}\) and \(B_i = (A_i \mid C_i) = (A'_i \mid C_i) \cdot \begin{psmallmatrix} M & \zeromat \\ \zeromat & \idmat{k_{-i}} \end{psmallmatrix}\).
Let \(B'_i \defn (A'_i \mid C_i)\).
The matrix \(\begin{psmallmatrix} M & \zeromat \\ \zeromat & \idmat{k_{-i}} \end{psmallmatrix}\) has full rank because both its blocks do.
By induction hypothesis, there are recursive rank decompositions \(T'_i\) of \(\Gamma_i = \danglinggraph{G_i}{B_i}\) with the same underlying tree structure as \(T_i\) and such that \(\decwidth(T'_i) = \decwidth(T_i)\).
Then, \(T' \defn \nodegenerator{T'_1}{\Gamma'}{T'_2}\) is a recursive rank decomposition of \(\Gamma'\) because \(G = \begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}\), \(B'_1 = (A'_1 \mid C)\) and \(B'_2 = (A'_2 \mid \transpose{C})\).
We can compute

\begin{align*}
& \decwidth(T')\\
& \defn \max \{\rank(B'), \decwidth(T'_1), \decwidth(T'_2)\}\\
& = \max \{\rank(B'\cdot M), \decwidth(T_1), \decwidth(T_2)\}\\
& \codefn \decwidth(T)
\end{align*}

Let us indicate with \(C_1 \defn C\) and \(C_2 \defn \transpose{C}\) and let \(L_i \cdot M_i\) be a rank decomposition of \((A_i \mid C_i)\), with \(L_i \in \MatN(k_i,r_i)\), \(M_1 \in \MatN(r_1,n+k_2)\) and \(M_2 \in \MatN(r_2, n+k_1)\).
By definition of rank decomposition, \(L_i\) and \(M_i\) have full rank \(r_i\).
We can write \(M_i = (N_i \mid K_i)\) with \(N_i \in \MatN(r_i,n)\), \(K_1 \in \MatN(r_1,k_2)\) and \(K_2 \in \MatN(r_2,k_1)\).
Then, \(C_i = L_i \cdot K_i\).
The rank of a composition is the minimum of the ranks and \(L_i\) has full rank, then

\begin{align*}
\rank(C) &= \rank(L_1 \cdot K_1) = \rank(K_1)\\
\rank(C) &= \rank(\transpose{C}) = \rank(L_2 \cdot K_2) = \rank(K_2)
\end{align*}

It follows that there are rank decompositions \(K_i = P_i \cdot Q_i\) with \(Q_i \in \MatN(s,r_i) \) and \(s = \rank(C)\).
Then, \(C = (L_1 \cdot P_1) \cdot Q_1 = \transpose{Q_2} \cdot (\transpose{P_2} \cdot \transpose{L_2})\) are rank factorizations of \(C\).
By <Ref>, there is an invertible matrix \(R \in \MatN(s,s)\) such that \(L_1 \cdot P_1 = \transpose{Q_2} \cdot R\) and \(Q_1 = \inv{R} \cdot (\transpose{P_2} \cdot \transpose{L_2})\).
Let \(S \defn P_1 \cdot \inv{R} \cdot \transpose{P_2}\) and we obtain \(C = L_1 \cdot S \cdot \transpose{L_2}\).
Then, \((A_1 \mid C) = L_1 \cdot (N_1 \mid S \cdot \transpose{L_2})\) and \((A_2 \mid \transpose{C}) = L_2 \cdot (N_2 \mid \transpose{S} \cdot \transpose{L_1})\).

Proceed by induction on \(T\).

If \(T = \emptydec\), then \(G\) must be empty, \(\rTomdec(T) = \emptydec\) and we are done.

If \(T = \leafgenerator{\Gamma}\), then \(\Gamma\) has one vertex, we define \(\rTomdec(T) \defn \leafgenerator{g}\) and \(\decwidth(T) \defn \rank(G) = \decwidth(\rTomdec(T))\).

If \(T = \nodegenerator{T_1}{\Gamma}{T_2}\), then \(\labelling(T_i) = \Gamma_i = \danglinggraph{G_i}{B_i}\), with \(G = \begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}\), \(B = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix}\), \(B_1 = (A_1 \mid C)\) and \(B_2 = (A_2 \mid \transpose{C})\).
By <Ref>, there are rank decompositions of \((A_1 \mid C)\) and \((A_2 \mid \transpose{C})\) of the form: \((A_1 \mid C) = L_1 \cdot (N_1 \mid S \cdot \transpose{L_2})\); and \((A_2 \mid \transpose{C}) = L_2 \cdot (N_2 \mid \transpose{S} \cdot \transpose{L_1})\).
This means that we can write \(g\) as

\[\mwdrwdupperproofFigOneCuts{},\]

with \(r_i = \rank(B_i)\).
Then, \(B_i = L_i \cdot M_i\) with \(M_i\) that has full rank \(r_i\).
By <Ref>, there is a recursive rank decomposition \(T'_i\) of \(\Gamma'_i = \danglinggraph{G_i}{L_i}\), with the same underlying binary tree as \(T_i\), such that \(\decwidth(T_i) = \decwidth(T'_i)\).
Let \(g_i \colon r_i \to 0\) be the morphisms in \(\propGraph\) corresponding to \(\Gamma'_i\) and let \(b \colon n \to r_1 + r_2\) be defined as

\[\mwdrwdupperproofFigTwo{}.\]

By induction hypothesis, there is a monoidal decomposition \(\rTomdec(T'_i)\) of \(g_i\) such that \(\decwidth(\rTomdec(T'_i)) \leq 2 \cdot \decwidth(T'_i) = 2 \cdot \decwidth(T_i)\).
Then, \(g = b \dcomp_{r_1 + r_2} (g_1 \tensor g_2)\) and \(\rTomdec(T) \defn \nodegenerator{b}{\dcomp_{r_1 + r_2}}{\nodegenerator{\rTomdec(T'_1)}{\tensor}{\rTomdec(T'_2)}}\) is a monoidal decomposition of \(g\).
Its width can be computed.

\begin{align*}
& \decwidth(\rTomdec(T))\\
& \defn \max \{\nodeweight(b), \nodeweight(\dcompnode{r_1 + r_2}), \decwidth(\rTomdec(T'_1)), \decwidth(\rTomdec(T'_2))\}\\
& \leq \max \{\nodeweight(b), \nodeweight(\dcompnode{r_1 + r_2}), 2 \cdot \decwidth(T'_1), 2 \cdot \decwidth(T'_2)\}\\
& = \max \{\nodeweight(b), r_1 + r_2, 2 \cdot \decwidth(T_1), 2 \cdot \decwidth(T_2)\}\\
& \leq 2 \cdot \max \{r_1, r_2, \decwidth(T_1), \decwidth(T_2)\}\\
& \codefn 2 \cdot \decwidth(T)
\end{align*}

Proceed by induction on \(T\).
If \(T = \leafgenerator{\Gamma}\), then we define \(T' \defn \leafgenerator{\Gamma'}\).
Clearly, \(T\) and \(T'\) have the same underlying tree structure.
We can compute \(\decwidth(T') \defn \rank(B') = \rank(B \cdot M) \leq \rank(B) \codefn \decwidth(T)\).
The inequality becomes an equality when \(M\) has full rank and we are done.

If \(T = \nodegenerator{T_1}{\Gamma}{T_2}\), then \(G = \begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}\), \(B_1 = (A_1 \mid C)\) and \(B_2 = (A_2 \mid \transpose{C})\), where \(B = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix}\) where \(\Gamma_i \defn \labelling_i(T_i)\), \(B_i \defn \boundary(\Gamma_i)\), \(G_i = \adjacency(\Gamma_i)\) and \(A_i \in \MatN(n,k_i)\).
Then, \(\begin{psmallmatrix} A'_1 \\ A'_2 \end{psmallmatrix} = \begin{psmallmatrix} A_1 \\ A_2 \end{psmallmatrix} \cdot M = \begin{psmallmatrix} A_1 \cdot M \\ A_2 \cdot M \end{psmallmatrix}\) and \(B'_i = (A'_i \mid C_i) = (A_i \mid C_i) \cdot \begin{psmallmatrix} M & \zeromat \\ \zeromat & \idmat{k_{-i}} \end{psmallmatrix}\).
By induction hypothesis, there are recursive rank decompositions \(T'_i\) of \(\Gamma'_i = \danglinggraph{G_i}{B'_i}\) with the same underlying tree structure as \(T_i\) and such that \(\decwidth(T'_i) \leq \decwidth(T_i)\).
If \(M\) has full rank, then \(\begin{psmallmatrix} M & \zeromat \\ \zeromat & \idmat{k_{-i}} \end{psmallmatrix}\) has full rank too because both its blocks do.
In this case, the induction hypothesis gives \(\decwidth(T'_i) = \decwidth(T_i)\).
Define \(T' \defn \nodegenerator{T'_1}{\Gamma'}{T'_2}\).
It is a recursive rank decomposition of \(\Gamma'\) because \(G = \begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}\), \(B'_1 = (A'_1 \mid C)\) and \(B'_2 = (A'_2 \mid \transpose{C})\).
We can compute

\begin{align*}
& \decwidth(T')\\
& \defn \max \{\rank(B'), \decwidth(T'_1), \decwidth(T'_2)\}\\
& = \max \{\rank(B \cdot M), \decwidth(T'_1), \decwidth(T'_2)\}\\
& \leq \max \{\rank(B), \decwidth(T_1), \decwidth(T_2)\}\\
& \codefn \decwidth(T)
\end{align*}

Again, the inequality is an equality when \(M\) has full rank.

Note that \((L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P}) = (L \mid R) \cdot \begin{psmallmatrix} \idmat{j} & (F + \transpose{F}) \cdot \transpose{P} \\ \zeromat & \idmat{m}\end{psmallmatrix}\).
Then, \(\rank(L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P}) \leq \rank (L \mid R)\).
Proceed by induction on \(T\).

If \(T = \leafgenerator{\Gamma}\), then \(\Gamma\) has one vertex and we can define \(T' \defn \leafgenerator{\Gamma'}\).
We can compute \(\decwidth(T') \defn \rank(L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P}) \leq \rank(L \mid R) \codefn \decwidth(T)\).

If \(T = \nodegenerator{T_1}{\Gamma}{T_2}\), then there are \(\Gamma_1 = \danglinggraph{G_1}{(L_1 \mid R_1 \mid C)}\) and \(\Gamma_2 = \danglinggraph{G_2}{(L_2 \mid R_2 \mid C)}\) such that \(T_i\) is a recursive rank decomposition of \(\Gamma_i\), and we can write \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} G_1 & C \\ \zeromat & G_2 \end{psmallmatrix}}\) and \((L \mid R) = \begin{psmallmatrix} L_1 & R_1 \\ L_2 & R_2 \end{psmallmatrix}\).
We can write \(\adjeqclass{G + L \cdot F \cdot \transpose{L}} = \adjeqclass{\begin{psmallmatrix} G_1 + L_1 \cdot F \cdot \transpose{L_1} & C + L_1 \cdot (F + \transpose{F}) \cdot \transpose{L_2} \\ \zeromat & G_2 + L_2 \cdot F \cdot \transpose{L_2}\end{psmallmatrix}}\) and \((L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P}) = \begin{psmallmatrix} L_1 & R_1 + L_1 \cdot (F + \transpose{F}) \cdot \transpose{P} \\ L_2 & R_2 + L_2 \cdot (F + \transpose{F}) \cdot \transpose{P} \end{psmallmatrix}\).

\begin{align*}
\Gamma'_1 \defn & \danglinggraph{G_1 + L_1 \cdot F \cdot \transpose{L_1}}{(L_1 \mid R_1 + L_1 \cdot (F + \transpose{F}) \cdot \transpose{P} \mid C + L_1 \cdot (F + \transpose{F}) \cdot \transpose{L_2})} \\
=& \danglinggraph{G_1 + L_1 \cdot F \cdot \transpose{L_1}}{(L_1 \mid (R_1 \mid C) + L_1 \cdot (F + \transpose{F}) \cdot (\transpose{P} \mid \transpose{L_2}))}\\
\text{ and }\\
\Gamma'_2 \defn & \danglinggraph{G_2 + L_2 \cdot F \cdot \transpose{L_2}}{(L_2 \mid R_2 + L_2 \cdot (F + \transpose{F}) \cdot \transpose{P} \mid \transpose{C} + L_2 \cdot (F + \transpose{F}) \cdot \transpose{L_1})} \\
=& \danglinggraph{G_2 + L_2 \cdot F \cdot \transpose{L_2}}{(L_2 \mid (R_2 \mid \transpose{C}) + L_2 \cdot (F + \transpose{F}) \cdot (\transpose{P} \mid \transpose{L_1}))}
\end{align*}

By induction, we have recursive rank decompositions \(T'_i\) of \(\Gamma'_i\) such that \(\decwidth(T'_i) \leq \decwidth(T_i)\).
Since \(\Gamma'_i\) satisfy the conditions for a recursive rank decomposition, we can define a recursive rank decomposition of \(\Gamma'\) as \(T' \defn \nodegenerator{T'_1}{\Gamma'}{T'_2}\), and compute its width.

\begin{align*}
& \decwidth(T')\\
& \defn \max \{\decwidth(T'_1), \decwidth(T'_2), \rank(L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P})\}\\
& \leq \max \{\decwidth(T_1), \decwidth(T_2), \rank(L \mid R + L \cdot (F + \transpose{F}) \cdot \transpose{P})\}\\
& \leq \max \{\decwidth(T_1), \decwidth(T_2), \rank(L \mid R)\}\\
& \codefn \decwidth(T)
\end{align*}

Proceed by induction on \(d\).

If \(d = \leafgenerator{g}\), then \(\decwidth(d) \defn k\), where \(k\) is the number of vertices of \(g\).
Pick any recursive rank decomposition of \(\Gamma\) and define \(\mTordec(d) \defn T\).
Surely, \(\decwidth(T) \leq k \codefn \decwidth(d)\)

If \(d = \nodegenerator{d_1}{\dcomp_j}{d_2}\), then there are \(g_i = \fullboundariesgraph{G_i}{L_i}{R_i}{P_i}{F_i}\) such that \(g = g_1 \dcomp g_2\).
Given the partition of the vertices determined by \(g_1\) and \(g_2\), we can decompose \(g\) in another way, by writing \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} \overline{G}_1 & C \\ \zeromat & \overline{G}_2\end{psmallmatrix}}\) and \(B = (L \mid R) = \begin{psmallmatrix} \overline{L}_1 & \overline{R}_1 \\ \overline{L}_2 & \overline{R}_2 \end{psmallmatrix}\).
Then, we have that \(\overline{G}_1 = G_1\), \(\overline{L}_1 = L_1\), \(P = P_2 \cdot P_1\), \(C = R_1 \cdot \transpose{L}_2\), \(\overline{R}_1 = R_1 \cdot \transpose{P}_2\), \(\overline{L}_2 = L_2 \cdot P_1\), \(\overline{R}_2 = R_2 + L_2 \cdot (F_1 + \transpose{F}_1) \cdot \transpose{P}_2\), \(\overline{G}_2 = G_2 + L_2 \cdot F_1 \cdot \transpose{L}_2\), and \(F = F_2 + P_2 \cdot F_1 \cdot \transpose{P}_2\).
Diagrammatically, this corresponds to the following equation.

\[\mwdrankwidthlowerproofFigFuture{}\]

We define \(\overline{B}_1 \defn (\overline{L}_1 \mid \overline{R}_1 \mid C)\) and \(\overline{B}_2 \defn (\overline{L}_2 \mid \overline{R}_2 \mid \transpose{C})\).
In order to build a recursive rank decomposition of \(\Gamma\), we need recursive rank decompositions of \(\overline{\Gamma}_i = \danglinggraph{\overline{G}_i}{\overline{B}_i}\).
We obtain these in three steps.
Firstly, we apply induction to obtain recursive rank decompositions \(\mTordec(d_i)\) of \(\Gamma_i = \danglinggraph{G_i}{(L_i \mid R_i)}\) such that \(\decwidth(\mTordec(d_i)) \leq 2 \cdot \max \{\decwidth(d_i), \rank(L_i), \rank(R_i)\}\).
Secondly, we apply <Ref> to obtain a recursive rank decomposition \(T'_2\) of \(\Gamma'_2 = \danglinggraph{G_2 + L_2 \cdot F_1 \cdot \transpose{L_2}}{(L_2 \mid R_2 + L_2 \cdot (F_1 + \transpose{F_1}) \cdot \transpose{P_2})}\) such that \(\decwidth(T'_2) \leq \decwidth(\mTordec(d_2))\).
Lastly, we observe that \((\overline{R}_1 \mid C) = R_1 \cdot (\transpose{P_2} \mid \transpose{L_2})\) and \((\overline{L}_2 \mid \transpose{C}) = L_2 \cdot (P_1 \mid \transpose{R_1})\).
Then we obtain that \(\overline{B}_1 = (L_1 \mid R_1) \cdot \begin{psmallmatrix} \idmat{n} & \zeromat & \zeromat\\ \zeromat &  \transpose{P_2} & \transpose{L_2} \end{psmallmatrix}\) and \(\overline{B}_2 = (L_2 \mid R_2 + L_2 \cdot (F_1 + \transpose{F_1}) \cdot \transpose{P_2}) \cdot \begin{psmallmatrix} P_1 & \zeromat & \transpose{R}_1 \\ \zeromat & \idmat{m} & \zeromat \end{psmallmatrix}\), and we can apply <Ref> to get recursive rank decompositions \(T_i\) of \(\overline{\Gamma}_i\) such that \(\decwidth(T_1) \leq \decwidth(\mTordec(d_1))\) and \(\decwidth(T_2) \leq \decwidth(T'_2) \leq \decwidth(\mTordec(d_2))\).
If \(k_1, k_2 > 0\), then we define \(\mTordec(d) \defn \nodegenerator{T_1}{\Gamma}{T_2}\), which is a recursive rank decomposition of \(\Gamma\) because \(\overline{\Gamma}_i\) satisfy the two conditions of a recursive rank decomposition from <Ref>.
If \(k_1 = 0\), then \(\Gamma = \overline{\Gamma}_2\) and we can define \(\mTordec(d) \defn T_2\).
Similarly, if \(k_2 = 0\), then \(\Gamma = \overline{\Gamma}_1\) and we can define \(\mTordec(d) \defn T_1\).
In any case, we can compute the width of \(\mTordec(d)\) (if \(k_i = 0\) then \(T_i = \emptydec\) and \(\decwidth(T_i) = 0\)) using the inductive hypothesis, <Ref>, <Ref>, the fact that \(\rank(L) \geq \rank(L_1)\), \(\rank(R) \geq \rank(R_2)\) and \(j \geq \rank(R_1), \rank(L_2)\) because \(R_1 \colon j \to k_1\) and \(L_2 \colon j \to k_2\).

\begin{align*}
& \decwidth(T) \\
& \defn \max \{\decwidth(T_1), \decwidth(T_2), \rank(L \mid R)\}\\
& \leq \max \{\decwidth(\mTordec(d_1)), \decwidth(T'_2), \rank(L \mid R)\}\\
& \leq \max \{\decwidth(\mTordec(d_1)), \decwidth(\mTordec(d_2)), \rank(L \mid R)\}\\
& \leq \max \{\decwidth(\mTordec(d_1)), \decwidth(\mTordec(d_2)), \rank(L) + \rank(R)\}\\
& \leq \max \{2 \cdot \decwidth(d_1), 2 \cdot \rank(L_1), 2 \cdot \rank(R_1), 2 \cdot \decwidth(d_2), 2 \cdot \rank(L_2), 2 \cdot \rank(R_2), \rank(L) + \rank(R)\}\\
& \leq 2 \cdot \max \{\decwidth(d_1), \rank(L_1), \rank(R_1), \decwidth(d_2), \rank(L_2), \rank(R_2), \rank(L), \rank(R)\}\\
& \leq 2 \cdot \max \{\decwidth(d_1), \decwidth(d_2), j, \rank(L), \rank(R)\}\\
& \codefn 2 \cdot \max \{\decwidth(d), \rank(L), \rank(R)\}
\end{align*}

If \(d = \nodegenerator{d_1}{\tensor}{d_2}\), then there are \(g_i = \fullboundariesgraph{G_i}{L_i}{R_i}{P_i}{F_i} \colon n_i \to m_i\) such that \(g = g_1 \tensor g_2\).
By exlicitly computing the monoidal product, we obtain that \(\adjeqclass{G} = \adjeqclass{\begin{psmallmatrix} G_1 & \zeromat \\ \zeromat & G_2 \end{psmallmatrix}}\), \(L = \begin{psmallmatrix} L_1 & \zeromat \\ \zeromat & L_2 \end{psmallmatrix}\), \(R = \begin{psmallmatrix} R_1 & \zeromat \\ \zeromat & R_2 \end{psmallmatrix}\), \(P = \begin{psmallmatrix} P_1 & \zeromat \\ \zeromat & P_2 \end{psmallmatrix}\) and \(F = \begin{psmallmatrix} F_1 & \zeromat \\ \zeromat & F_2 \end{psmallmatrix}\).
By induction, we have recursive rank decompositions \(\mTordec(d_i)\) of \(\Gamma_i \defn \danglinggraph{G_i}{B_i}\), where \(B_i = (L_i \mid R_i)\), such that \(\decwidth(\mTordec(d_i)) \leq 2 \cdot \max \{\decwidth(d_i), \rank(L_i), \rank(R_i)\}\).
Let \(\overline{B}_1 \defn (L_1 \mid \zeromat_{n_2} \mid R_1 \mid \zeromat_{m_2} \mid \zeromat_{k_2}) = B_1 \cdot \begin{psmallmatrix} \idmat{n_1} & \zeromat & \zeromat & \zeromat & \zeromat \\ \zeromat & \zeromat & \idmat{m_1} & \zeromat & \zeromat \end{psmallmatrix}\) and  \(\overline{B}_2 \defn (\zeromat_{n_1} \mid L_2 \mid \zeromat_{m_1} \mid R_2 \mid \zeromat_{k_1}) = B_2 \cdot \begin{psmallmatrix} \zeromat & \idmat{n_2} & \zeromat & \zeromat & \zeromat \\ \zeromat & \zeromat & \zeromat & \idmat{m_2} & \zeromat \end{psmallmatrix}\).
By <Ref>, we can obtain recursive rank decompositions \(T_i\) of \(\overline{\Gamma}_i \defn \danglinggraph{G_i}{\overline{B}_i}\) such that \(\decwidth(T_i) \leq \decwidth(\mTordec(d_i))\).
If \(k_1, k_2 > 0\), then we define \(\mTordec(d) \defn \nodegenerator{T_1}{\Gamma}{T_2}\), which is a recursive rank decomposition of \(\Gamma\) because \(\overline{\Gamma}_i\) satisfy the two conditions of a recursive rank decomposition in <Ref>.
If \(k_1 = 0\), then \(\Gamma = \overline{\Gamma}_2\) and we can define \(\mTordec(d) \defn T_2\).
Similarly, if \(k_2 = 0\), then \(\Gamma = \overline{\Gamma}_1\) and we can define \(\mTordec(d) \defn T_1\).
In any case, we can compute the width of \(\mTordec(d)\) (if \(k_i = 0\) then \(T_i = \emptydec\) and \(\decwidth(T_i) = 0\)) using the inductive hypothesis and <Ref>.

\begin{align*}
& \decwidth(T) \\
& \defn \max \{\decwidth(T_1), \decwidth(T_2), \rank(L \mid R)\}\\
& \leq \max \{\decwidth(\mTordec(d_1)), \decwidth(\mTordec(d_2)), \rank(L \mid R)\}\\
& \leq \max \{\decwidth(\mTordec(d_1)), \decwidth(\mTordec(d_2)), \rank(L) + \rank(R)\}\\
& \leq \max \{2 \cdot \decwidth(d_1), 2 \cdot \rank(L_1), 2 \cdot \rank(R_1), 2 \cdot \decwidth(d_2), 2 \cdot \rank(L_2), 2 \cdot \rank(R_2), \rank(L) + \rank(R)\}\\
& \leq 2 \cdot \max \{\decwidth(d_1), \rank(L_1), \rank(R_1), \decwidth(d_2), \rank(L_2), \rank(R_2), \rank(L), \rank(R)\}\\
& \leq 2 \cdot \max \{\decwidth(d_1), \decwidth(d_2), \rank(L), \rank(R)\}\\
& \codefn 2 \cdot \max \{\decwidth(d), \rank(L), \rank(R)\}
\end{align*}