I stumbled upon a sequence of numbers $b_n$ such that for all $n\in \mathbb{N}$, $$b_n=\sum_{j=0}^M a_{n,j}$$ where $a_{n,j}$ are given by the recurrence,
$$a_{n,j}=\begin{cases} 1 & n=0 &\land &j=0\\ 0 & n=0 &\oplus &j=0\\ \sum_{i=0}^M \lambda_{i,j}\cdot a_{n-1,i} & 0<n\in\mathbb{N} & \land & 0<j\leq M \end{cases}$$
Is it possible to find a linear recurrence for $b_n$ based on that? Hopefully it can be done explicitly.
I don't see any immediate way for this to be rewritten into a linear recurrence. However, we can get a closed form. Let us rewrite
$$a_n=\begin{bmatrix}a_{n,0}\\a_{n,1}\\\vdots\\a_{n,M}\end{bmatrix}$$
$$\lambda=\begin{bmatrix}\lambda_{0,0}&\lambda_{1,0}&\cdots&\lambda_{M,0}\\\lambda_{0,1}&\lambda_{1,1}&\cdots&\lambda_{M,1}\\\vdots&\vdots&\ddots&\vdots\\\lambda_{0,M}&\lambda_{1,M}&\cdots&\lambda_{M,M}\end{bmatrix}$$
with $\lambda_{i,0}=0$.
We then have
$$a_n=\lambda^n\begin{bmatrix}1\\0\\\vdots\\0\end{bmatrix}$$
and finally,
\begin{align}b_n&=\begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix}^\intercal a_n\\&=\begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix}^\intercal\lambda^n\begin{bmatrix}1\\0\\\vdots\\0\end{bmatrix}\end{align}
which can be used to quickly compute $b_n$ for large $n$, among other things.