Regarding control approaches, it would be valuable to extend to SLDIs techniques already investigated in switching max-plus linear systems and max-plus automata: we mention model predictive control <cit.>, just-in-time control based on residuation theory <cit.>, geometric control <cit.>, and supervisory control <cit.>.

To conclude, we emphasize that interesting connections can be drawn between the concepts of stability in discrete-time switched linear systems[Recall that discrete-time switched linear systems follow $x(k+1) = A^1_{w_k} \cdot x(k)$, where $\cdot$ indicates the standard matrix-vector multiplication.] (see, e.g., <cit.>) and bounded consistency in SLDIs.
Considering the case of "unswitched" systems (i.e., discrete-time linear systems and LDIs), the two properties are both verifiable in strongly-polynomial time (using Jury's test for the former property <cit.>, using Theorem <ref> for the latter) and are related to the spectral radius in the respective algebras.
In their switching counterparts, stability and bounded consistency are – unsurprisingly – interconnected with the notion of joint spectral radius in the standard and max-plus algebras.
Further investigation of this link presents an exciting avenue for future research.

§ PROOF OF PROPOSITION <REF>

Let us consider SLDIs $\pazocal{S}$ under schedule $w = v^{+\infty}$, where $v = v_1v_2\ldots v_V$: for all $k\in\mathbb{N}$,

\[
\left\{
\begin{array}{rcccl}
A_{v_1}^0 \otimes x(V(k-1)+1) & \leq & x(V(k-1)+1) &\leq & B_{v_1}^0 \stimes x(V(k-1)+1),\\
A_{v_1}^1 \otimes x(V(k-1)+1) & \leq& x(V(k-1)+2) &\leq & B_{v_1}^1 \stimes x(V(k-1)+1),\\
A_{v_2}^0 \otimes x(V(k-1)+2) & \leq& x(V(k-1)+2) &\leq & B_{v_2}^0 \stimes x(V(k-1)+2),\\
A_{v_2}^1 \otimes x(V(k-1)+2) & \leq& x(V(k-1)+3) &\leq & B_{v_2}^1 \stimes x(V(k-1)+2),\\
& &\vdots& &\\
A_{v_V}^0 \otimes x(Vk) & \leq& x(Vk) &\leq & B_{v_V}^0 \stimes x(Vk),\\
A_{v_V}^1 \otimes x(Vk) & \leq& x(Vk+1) &\leq & B_{v_V}^1 \stimes x(Vk).
\end{array}
\right.
\]

By defining

\[
\tilde{x}(k) = \begin{bmatrix}
x(V(k-1)+1) \\ x(V(k-1)+2) \\ \vdots \\ x(Vk)
\end{bmatrix}
\]

and using Proposition <ref>, it is possible to rewrite the SLDIs above as the following LDIs: for all $k\in\mathbb{N}$,

\[
\begin{array}{rcl}
A_{v}^0 \otimes \tilde{x}(k) \leq & \tilde{x}(k) &\leq B_{v}^0 \stimes \tilde{x}(k),\\
A_{v}^1 \otimes \tilde{x}(k) \leq & \tilde{x}(k+1) &\leq B_{v}^1 \stimes \tilde{x}(k),
\end{array}
\]

\[
A_v^0 = \begin{bsmallmatrix}
A_{v_1}^0 & \pazocal{E} & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
A_{v_1}^1 & A_{v_2}^0 & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & A_{v_2}^1 & A_{v_3}^0 & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & A_{v_3}^1 & \cdots & \pazocal{E} & \pazocal{E}\\
\svdots & \svdots &\svdots &\sddots &\svdots &\svdots \\
\pazocal{E} & \pazocal{E} &\pazocal{E} &\cdots &A_{v_{V-1}}^1 & A_{v_V}^0
\end{bsmallmatrix},\quad
B_v^0 = \begin{bsmallmatrix}
B_{v_1}^0 & \pazocal{T} & \pazocal{T} & \cdots & \pazocal{T} & \pazocal{T}\\
B_{v_1}^1 & B_{v_2}^0 & \pazocal{T} & \cdots & \pazocal{T} & \pazocal{T}\\
\pazocal{T} & B_{v_2}^1 & B_{v_3}^0 & \cdots & \pazocal{T} & \pazocal{T}\\
\pazocal{T} & \pazocal{T} & B_{v_3}^1 & \cdots & \pazocal{T} & \pazocal{T}\\
\svdots & \svdots &\svdots &\sddots &\svdots &\svdots \\
\pazocal{T} & \pazocal{T} &\pazocal{T} &\cdots &B_{v_{V-1}}^1 & B_{v_V}^0
\end{bsmallmatrix},
\]

\[
A_v^1 = \begin{bsmallmatrix}
\pazocal{E} & \cdots & \pazocal{E} & A_{v_V}^1\\
\pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\svdots & & \svdots & \svdots\\
\pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}
\end{bsmallmatrix},\quad
B_v^1 = \begin{bsmallmatrix}
\pazocal{T} & \cdots & \pazocal{T} & B_{v_V}^1\\
\pazocal{T} & \cdots & \pazocal{T} & \pazocal{T}\\
\svdots & & \svdots & \svdots\\
\pazocal{T} & \cdots & \pazocal{T} & \pazocal{T}
\end{bsmallmatrix}.
\]

Hence, since SLDIs under periodic schedule $v^{+\infty}$ are equivalent to the above LDIs, according to Theorem <ref> they are boundedly consistent if and only if they admit, for some $\lambda\in\R$, a trajectory of the form

\[
\forall k\in\nat,\quad \tilde{x}(k) = \lambda^{k-1} \tilde{x}(1);
\]

observe that such a trajectory is $v$-periodic as, in terms of dater $x$, it satisfies the following property:

\[
\forall k\in\nat,\ \forall h\in\dint{1,V},\quad x(Vk+h) = \lambda x(V(k-1)+h).
\]

To find the set $\solSLDI$ of admissible periods for the SLDIs under schedule $v^{+\infty}$, we proceed as in Section <ref>, obtaining:

\[
\solSLDI = \solNCP{\lambda B_v^{1\sharp}\oplus \lambda^{-1} A_v^1 \oplus A_v^0\oplus B_v^{0\sharp}}.
\]

Therefore, the set $\solSLDI$ coincides with all the $\lambda$'s such that the precedence graph $\graph(\lambda P_v \oplus \lambda^{-1} I_v \oplus C_v )$ does not contain circuits with positive weight, where

\[
P_v = B_v^{1\sharp} =
\begin{bsmallmatrix}
\pazocal{E} & \pazocal{E} & \cdots & \pazocal{E}\\
\svdots & \svdots &  & \svdots\\
\pazocal{E} & \pazocal{E} & \cdots & \pazocal{E}\\
P_V & \pazocal{E} & \cdots & \pazocal{E}
\end{bsmallmatrix},\quad
I_v = A_v^1 =
\begin{bsmallmatrix}
\pazocal{E} & \cdots & \pazocal{E} & I_V\\
\pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\svdots & & \svdots & \svdots\\
\pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}
\end{bsmallmatrix},
\]

\[
C_v = A_v^0\oplus B_v^{0\sharp} =
\begin{bsmallmatrix}
C_1 & P_{1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
I_{1} & C_{2} & P_{2} & \pazocal{E} & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & I_{2} & C_{3} & P_{3} & \pazocal{E} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & I_{3} & C_{4} & P_{4} & \cdots & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & I_{4} & C_{5} & \cdots & \pazocal{E} & \pazocal{E}\\
\svdots & \svdots & \svdots & \svdots & \svdots & \sddots & \svdots & \svdots \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & C_{{V-1}} & P_{{V-1}}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & I_{{V-1}} & C_{V}
\end{bsmallmatrix},
\]

$P_h = B_{v_h}^{1\sharp}$, $I_h = A_{v_h}^1$, and $C_h = A_{v_h}^0\oplus B_{v_h}^{0\sharp}$ for all $h\in\dint{1,V}$.

§ PROOF OF THEOREM <REF>

In this section, we prove Theorem <ref>.
All symbols used in the following propositions are as in Proposition <ref> and Theorem <ref>.
To prove the theorem, we first need a number of technical propositions and lemmas, which provide closed formulas for the computation of elements of the Kleene star of particular sparse matrices.
We start from recalling some properties of the Kleene star operation in the max-plus algebra.

Given two matrices $a,b\in\Rmax^{n\times n}$, the following properties hold:

\begin{equation}\label{eq:aux1}
(a\oplus b)^* = a^* (b a^*)^*,
\end{equation}

\begin{equation}\label{eq:aux2}
a^*a^* = a^*,
\end{equation}

\begin{equation}\label{eq:aux3}
a(ba)^* = (ab)^*a.
\end{equation}

Some of the following intermediate results have already been concisely proven in <cit.>; here we provide a more detailed proof for the first of them.

Let $a\in\Rmax^{n_1\times n_1}$, $b\in\Rmax^{n_1\times n_2}$, $c\in\Rmax^{n_2\times n_1}$, and $d\in\Rmax^{n_2\times n_2}$.

\[
\begin{bmatrix}
a & b\\
c & d
\end{bmatrix}^* =
\begin{bmatrix}
a^*(a^*bd^*ca^*)^*a^* & (a^*bd^*ca^*)^*a^*bd^*\\
(d^*ca^*bd^*)^*d^*ca^* & d^*(d^*ca^*bd^*)^*d^*
\end{bmatrix}
\]

The lemma is proven by applying the formulas from the latter proposition to Algorithm 2 from <cit.>, which can be used for the computation of the Kleene star.

Let $M^* = \begin{bsmallmatrix}a & b\\c & d\end{bsmallmatrix}^* = \begin{bsmallmatrix}\pazocal{M}^{11} & \pazocal{M}^{12}\\\pazocal{M}^{21} & \pazocal{M}^{22}\end{bsmallmatrix}$, where each $\pazocal{M}^{ij}$ is a matrix partitioning $M^*$ such that $\pazocal{M}^{11}\in\Rmax^{n_1\times n_1}$; applying Algorithm 2 of <cit.>, we easily get

\[
\begin{array}{rcl}
\pazocal{M}^{11} & = & a^*b(d\oplus ca^*b)^*ca^*\oplus a^*\\
&\eqtop{\eqref{eq:aux1}}& a^*bd^*(ca^*bd^*)^*ca^* \oplus a^*\\
&\eqtop{\eqref{eq:aux2}}& a^*a^*bd^*d^*(ca^*a^*bd^*d^*)^*ca^*a^*\oplus a^*a^*\\
&\eqtop{\eqref{eq:aux3}}& a^*a^*bd^*(d^*ca^*a^*bd^*)^*d^*ca^*a^*\oplus a^*a^*\\
&\eqtop{\eqref{eq:aux3}}& a^*(a^*bd^*d^*ca^*)^*a^*bd^*d^*ca^*a^*\oplus a^*a^*\\
&=& a^*(a^*bd^*d^*ca^*)^+a^*\oplus a^*E_\otimes a^*\\
&=& a^*((a^*bd^*d^*ca^*)^+\oplus E_\otimes)a^*\\
&=& a^*(a^*bd^*d^*ca^*)^*a^*\\
&\eqtop{\eqref{eq:aux2}}& a^*(a^*bd^*ca^*)^*a^*,
\end{array}
\]

where $a^+ = a a^*$ and, consequently, $a^* = a^+ \oplus E_\otimes$.
The formula for matrix $\pazocal{M}^{12}$ can be obtained in a similar way starting from

\[
\pazocal{M}^{12} = a^*b(d\oplus ca^*b)^*,
\]

which comes from Algorithm 2 of <cit.>.
Formulas for $\pazocal{M}^{21}$ and $\pazocal{M}^{22}$ are directly derived from reasoning about the symmetry of the Kleene star operation.

Let us now divide matrix $\lambda P_v\oplus \lambda^{-1}I_v\oplus C_v$ into four blocks, such that the top-left block is $C_{1}\in\Rmax^{n\times n}$.
We will first focus on formulas to compute specific elements of the Kleene star of the bottom-right block of $\lambda P_v\oplus \lambda^{-1}I_v \oplus C_v$, which we will denote by $M$.
We use the following notation:

\[
M^* = \begin{bsmallmatrix}
C_{2} & P_{2} & \pazocal{E} & \cdots & \pazocal{E}\\
I_{2} & C_{3} & P_{3} &  \cdots & \pazocal{E}\\
\pazocal{E} & I_{3} & C_{4} &  \cdots & \pazocal{E}\\
\svdots & \svdots & \svdots & \sddots & \svdots\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \cdots & C_V
\end{bsmallmatrix}^*
\begin{bsmallmatrix}
\pazocal{M}^{22} & \pazocal{M}^{23} & \pazocal{M}^{24} & \cdots & \pazocal{M}^{2V}\\
\pazocal{M}^{32} & \pazocal{M}^{33} & \pazocal{M}^{34} & \cdots & \pazocal{M}^{3V}\\
\pazocal{M}^{42} & \pazocal{M}^{43} & \pazocal{M}^{44} & \cdots & \pazocal{M}^{4V}\\
\svdots & \svdots & \svdots & \sddots & \svdots\\
\pazocal{M}^{V2} & \pazocal{M}^{V3} & \pazocal{M}^{V4} & \cdots & \pazocal{M}^{VV}
\end{bsmallmatrix},
\]

where each $\pazocal{M}^{ij}$ is an $n\times n$ matrix.
Note that matrix $M$ is a block tridiagonal matrix, i.e., a matrix whose blocks are all $\pazocal{E}$ except for those in the main diagonal and in the first diagonals above and below the main diagonal.
We refer to <cit.> for some work related to tridiagonal matrices in the tropical (i.e., either max-plus or min-plus) algebra.

$\pazocal{M}^{22} = C_2^* (\mathbb{C}_2^{P})^* C_2^*$.

$\pazocal{M}^{VV} = C_{V}^* (\mathbb{C}_{V-1}^{I})^* C_{V}^*$.

The proof is done by induction on $V$.
For $V = 3$, the formula can be obtained directly from Lemma <ref>:

\[
\mathcal{M}^{33} = C_3^*(C_3^*I_2C_2^*P_2C_3^*)^*C_3^* = C_3^*(\mathbb{C}_2^I)^*C_3^*.
\]

Suppose now that the formula holds for $V-1$ with $V \geq 4$; we prove that it holds also for $V$.
By partitioning matrix $M$ in four blocks, such that the bottom-right block coincides with $C_V$, from Lemma <ref> we get

\[
\pazocal{M}^{VV} = C_V^*\left(C_V^*
\begin{bsmallmatrix} \mathcal{E} & \cdots & \mathcal{E} & I_{V-1} \end{bsmallmatrix}
\begin{bsmallmatrix}
C_2 & \cdots & \mathcal{E} & \mathcal{E}\\
\svdots & \sddots & \svdots & \svdots\\
\mathcal{E} & \cdots & C_{V-2} & P_{V-2}\\
\mathcal{E} & \cdots & I_{V-2} & C_{V-1}
\end{bsmallmatrix}^*
\begin{bsmallmatrix} \mathcal{E} \\ \svdots \\ \mathcal{E} \\ P_{V-1} \end{bsmallmatrix}
C_V^*\right)^* C_V^*;
\]

finally, we can use the induction hypothesis to simplify the latter expression into

\[
\mathcal{M}^{VV} = C_V^*(C_V^* I_{V-1} C_{V-1}^* (\mathbb{C}_{V-2}^I)^* C_{V-1}^* P_{V-1} C_V^*)^* C_V^* = C_V^*(\mathbb{C}_{V-1}^I)^* C_V^*.
\]

More in general, one can prove that, for all $i\in\dint{2,V}$,

\[
\pazocal{M}^{ii} = C_i^*(\mathbb{C}_{i}^P \oplus \mathbb{C}_{i-1}^I)^*C_i^*,
\]

considering $\mathbb{C}_V^P = \mathbb{C}_{1}^I = \pazocal{E}$.

$\pazocal{M}^{2V} = (\mathbb{C}^P_2)^* \mathbb{P}_2 (\mathbb{C}^P_3)^* \mathbb{P}_3 \cdots (\mathbb{C}^P_{V-1})^* \mathbb{P}_{V-1}$.

The proof is done by induction on $V$.
For $V = 3$, the formula can be obtained directly from Lemma <ref>:

\[
\mathcal{M}^{23} = (C_2^*P_2C_3^*I_2C_2^*)^*C_2^*P_2C_3^* = (\mathbb{C}_2^P)^* \mathbb{P}_2.
\]

Suppose now that the formula holds for $V-1$ with $V \geq 4$; we prove that it holds also for $V$.
By partitioning matrix $M$ in four blocks, such that the upper-left block coincides with $C_2$, from Lemma <ref> we get that $\pazocal{M}^{2V}$ is equal to the rightmost block of matrix

\begin{equation*}
\left(C_2^*
\begin{bsmallmatrix}
P_2 & \pazocal{E} & \cdots & \pazocal{E}
\end{bsmallmatrix}
\begin{bsmallmatrix}
C_3 & P_3 & \cdots & \pazocal{E}\\
I_3 & C_4 & \cdots & \pazocal{E}\\
\svdots & \svdots & \sddots & \svdots\\
\pazocal{E} & \pazocal{E} & \cdots & C_V
\end{bsmallmatrix}^*
\begin{bsmallmatrix}
I_2 \\ \pazocal{E} \\ \svdots \\ \pazocal{E}
\end{bsmallmatrix}
\right)^*
\begin{bsmallmatrix}
P_2 & \pazocal{E} & \cdots & \pazocal{E}
\end{bsmallmatrix}
\begin{bsmallmatrix}
C_3 & P_3 & \cdots & \pazocal{E}\\
I_3 & C_4 & \cdots & \pazocal{E}\\
\svdots & \svdots & \sddots & \svdots\\
\pazocal{E} & \pazocal{E} & \cdots & C_V
\end{bsmallmatrix}^*.
\end{equation*}

Expanding the expression using the induction hypothesis and Lemma <ref>, we get

\[
\begin{array}{rcl}
\pazocal{M}^{2V} &=& (\mathbb{C}_2^P)^* C_2^* P_2 (\mathbb{C}^P_3)^* \mathbb{P}_3 (\mathbb{C}^P_4)^* \mathbb{P}_4 \cdots (\mathbb{C}^P_{V-1})^* \mathbb{P}_{V-1} \\
&=& (\mathbb{C}_2^P)^* C_2^* P_2 (C_3^* P_3 \cdots I_3 C_3^*)^* C_3^*P_3 C_4^* (\mathbb{C}^P_4)^* \mathbb{P}_4 \mathbb \cdots (\mathbb{C}^P_{V-1})^* \mathbb{P}_{V-1} \\
&\eqtop{\eqref{eq:aux2}}& (\mathbb{C}_2^P)^* C_2^* P_2 (C_3^*C_3^* P_3 \cdots I_3 C_3^*)^* C_3^* C_3^*P_3 C_4^* (\mathbb{C}^P_4)^* \mathbb{P}_4 \mathbb \cdots (\mathbb{C}^P_{V-1})^* \mathbb{P}_{V-1} \\
&\eqtop{\eqref{eq:aux3}}& (\mathbb{C}_2^P)^* C_2^* P_2 C_3^*(C_3^* P_3 \cdots I_3 C_3^*C_3^*)^* C_3^*P_3 C_4^* (\mathbb{C}^P_4)^* \mathbb{P}_4 \mathbb \cdots (\mathbb{C}^P_{V-1})^* \mathbb{P}_{V-1} \\
&\eqtop{\eqref{eq:aux2}}& (\mathbb{C}_2^P)^* \mathbb{P}_2(\mathbb{C}_3^P)^* \mathbb{P}_3 (\mathbb{C}^P_4)^* \mathbb{P}_4 \mathbb \cdots (\mathbb{C}^P_{V-1})^* \mathbb{P}_{V-1},
\end{array}
\]

which is the desired formula.

With similar techniques, one can prove that, for all $V\geq 4$ and for all $i\in\dint{3,V-1}$,

\[
\pazocal{M}^{2i} = (\mathbb{C}^P_2)^* \mathbb{P}_2 (\mathbb{C}^P_3)^* \mathbb{P}_3 \cdots (\mathbb{C}^P_{i-1})^* \mathbb{P}_{i-1} (\mathbb{C}^P_{i})^*.
\]

$\pazocal{M}^{V2} = (\mathbb{C}_{V-1}^{I})^* \mathbb{I}_{V-1} (\mathbb{C}_{V-2}^{I})^* \mathbb{I}_{V-2} \cdots (\mathbb{C}_{2}^{I})^* \mathbb{I}_{2}$.

The proof is done by induction on $V$.
For $V = 3$, the formula can be obtained directly from Lemma <ref>:

\[
\mathcal{M}^{32} = (C_3^*I_2C_2^*P_2C_3^*)^*C_3^*I_2C_2^* = (\mathbb{C}_2^I)^* \mathbb{I}_2.
\]

Suppose now that the formula holds for $V-1$ with $V \geq 4$; we prove that it holds also for $V$.
By partitioning matrix $M$ in four blocks, such that the bottom-right block coincides with $C_{V}$, from Lemma <ref> we get that $\pazocal{M}^{V2}$ is equal to the leftmost block of matrix

\begin{equation*}
\left(C_V^*
\begin{bsmallmatrix}
\pazocal{E} & \cdots & \pazocal{E} & I_{V-1}
\end{bsmallmatrix}
\begin{bsmallmatrix}
C_2 & \cdots & \pazocal{E}\\
\svdots & \sddots & \svdots\\
\pazocal{E} & \cdots & C_{V-1}
\end{bsmallmatrix}^*
\begin{bsmallmatrix}
\pazocal{E} \\ \svdots \\ \pazocal{E} \\ P_{V-1}
\end{bsmallmatrix}
\right)^*
\begin{bsmallmatrix}
\pazocal{E} & \cdots & \pazocal{E} & I_{V-1}
\end{bsmallmatrix}
\begin{bsmallmatrix}
C_2 & \cdots & \pazocal{E}\\
\svdots & \sddots & \svdots\\
\pazocal{E} & \cdots & C_{V-1}
\end{bsmallmatrix}^*.
\end{equation*}

Expanding the expression using the induction hypothesis, Lemma <ref>, (<ref>), and (<ref>), we can get the desired formula with computations analogous to those in the proof of Lemma <ref>.

With similar techniques, one can prove that, for all $V\geq 4$ and for all $i\in\dint{3,V-1}$,

\[
\pazocal{M}^{i2} = (\mathbb{C}^P_i)^* \mathbb{I}_{i-1} (\mathbb{C}^P_{i-1})^* \mathbb{I}_{i-2} \cdots (\mathbb{C}^P_{3})^* \mathbb{I}_{2} (\mathbb{C}^P_{2})^*.
\]

In the next proposition, we focus on the top-left $n\times n$ block of matrix $(\lambda P_v \oplus \lambda^{-1} I_v \oplus C_v)^*$; we denote this block by $N\in\Rbar^{n\times n}$.

$N = C_1^*(\lambda \mathbb{M}^P \oplus \lambda^{-1} \mathbb{M}^I \oplus \mathbb{M}^C)^*C_1^*$.

Partitioning matrix $\lambda P_v\oplus \lambda^{-1} I_v \oplus C_v$ into four blocks, such that the top-left block is $C_1$, Lemma <ref> gives us

\[\def\arraystretch{1.5}
\begin{array}{rcl}
N &=& C_1^*\left(C_1^*
\begin{bsmallmatrix}
P_1 & \pazocal{E} & \cdots & \pazocal{E} & \lambda^{-1} I_V
\end{bsmallmatrix}
\begin{bsmallmatrix}
C_2 & P_2 & \cdots & \pazocal{E}& \pazocal{E}\\
I_2 & C_3 & \cdots & \pazocal{E}& \pazocal{E}\\
\svdots & \svdots & \sddots & \svdots & \svdots\\
\pazocal{E} & \pazocal{E} & \cdots & C_{V-1} & P_{V-1}\\
\pazocal{E} & \pazocal{E} & \cdots & I_{V-1} & C_V
\end{bsmallmatrix}^*
\begin{bsmallmatrix}
I_1 \\ \pazocal{E} \\ \svdots \\ \pazocal{E} \\ \lambda P_V
\end{bsmallmatrix}
C_1^*\right)^* C_1^*\\
(P_1 \pazocal{M}^{22} I_1 \oplus \lambda^{-1}I_V \pazocal{M}^{V2} I_1 \\
& \oplus & \lambda P_1 \pazocal{M}^{2V} P_V \oplus I_V \pazocal{M}^{VV} P_V)
C_1^*)^* C_1^*\\
&=& C_1^*(\mathbb{C}^P_1 \oplus \lambda^{-1}\mathbb{M}^I \oplus \lambda \mathbb{M}^P \oplus \mathbb{C}^I_V)^* C_1^*,
\end{array}
\]

where the latter step can be obtained from Lemmas <ref>-<ref>, (<ref>), and (<ref>).
Finally, the commutativity of $\oplus$ concludes the proof.

Lumped-node representation of $\graph(\lambda P_v \oplus \lambda^{-1} I_v \oplus C_v)$ when $V=5$.

After the technical propositions and lemmas above, we are finally ready to introduce the graphical part of the proof.
First of all, it is useful to visualize the structure of $\graph(\lambda P_v \oplus \lambda^{-1} I_v \oplus C_v)$; the lumped-node representation of Figure <ref> illustrates it in the case $V = 5$.
In this simplified representation, $\overline{k}$ indicates the set of nodes $\dint{(k-1)n+1,kn}$ for any $k\in\dint{1,5}$, and the matrix, say $Y$, associated to an arc from $\overline{k}_1$ to $\overline{k}_2$ indicates that an arc in $\graph(\lambda P_v \oplus \lambda^{-1} I_v \oplus C_v)$ from node $(k_1-1)n+j$ to node $(k_2-1)n+i$ exists iff $Y_{ij}\neq -\infty$, and that its weight is equal to $Y_{ij}$, for all $i,j\in\dint{1,n}$.

Recall that, for a square matrix $M$ such that $M^* = \begin{bsmallmatrix}\mathcal{M}^{11}& \mathcal{M}^{12}\\\mathcal{M}^{21} & \mathcal{M}^{22}\end{bsmallmatrix}$, where $\mathcal{M}^{ii}$ has dimension $n_i\times n_i$, $\graph(M)$ does not contain circuits with positive weight visiting any node $j\in\dint{1,n_1}$ (respectively, $j\in\dint{n_1+1,n_2}$) iff $\graph(\mathcal{M}^{11}) \in\nonegset$ (respectively, $\graph(\mathcal{M}^{22})\in\nonegset$).
We partition the set of circuits of $\graph(\lambda P_v \oplus \lambda^{-1} I_v \oplus C_v)$ in $V$ subsets as follows: (1) circuits visiting at least one node in $\overline{1}$, (2) circuits that do not visit any node in $\overline{1}$, but that visit at least one node in $\overline{2}$, (3) circuits that do not visit any node in $\overline{1}$ or $\overline{2}$, but that visit at least one node in $\overline{3}$, …, ($V$) circuits that do not visit any node in $\overline{1},\overline{2},\ldots,\overline{V-1}$, but that visit at least one node in $\overline{V}$.
From Proposition <ref>, the maximal weights of circuits in the first subset correspond to elements in the diagonal of $N = C_1^*(\lambda \mathbb{M}^P \oplus \lambda^{-1} \mathbb{M}^I \oplus \mathbb{M}^C)^*C_1^*$; thus these are non-positive iff $\graph(C_1)\in\nonegset$ and $\lambda\in\solNCP{\lambda \mathbb{M}^P\oplus\lambda^{-1}\mathbb{M}^I\oplus\mathbb{M}^C}$.
Let $k\in\dint{2,V-1}$.
From Lemma <ref>, the maximal weights of circuits in the $k$th subset correspond to elements in the diagonal of $C_k^*(\mathbb{C}^P_k)^* C_k^*$; thus, these are non-positive iff $\graph(C_k)\in\nonegset$ and $\graph(\mathbb{C}^P_k)\in\nonegset$.
As for circuits in the $V$th subset, their maximal weights come from the diagonal elements of $C_{V}^*$, which are finite iff $\graph(C_{V})\in\nonegset$.

§ PROOF OF PROPOSITION <REF>

Consider SLDIs (<ref>) under intermittently periodic schedule $w = u_0 v_1^{m_1} u_1 v_2^{m_2} u_2 \cdots v_q^{m_q} u_q$, where $U_q > 0$ (the case in which $U_q=0$ is analogous but must be considered separately): for all $k\in\dint{1,U_0}$,[In this section, $u_{hk}$ and $v_{hk}$ denote the $k$th mode in subschedules $u_h$ and $v_h$, respectively.]

\begin{equation}\label{eq:periodic_1}
\begin{array}{rcl}
A^0_{u_{0k}} \otimes x(k) \leq & x(k) & \leq B^0_{u_{0k}}\stimes x(k)\\
A^1_{u_{0k}} \otimes x(k) \leq & x(k+1) & \leq B^1_{u_{0k}}\stimes x(k),
\end{array}
\end{equation}

for all $h\in\dint{1,q}$, $j\in\dint{0,m_h-1}$, $k\in\dint{1,V_h}$,

\begin{equation}\label{eq:periodic}
\begin{array}{rl}
A^0_{v_{hk}} \otimes x(K_{h-1}+jV_h+k) &\leq  x(K_{h-1}+jV_h+k) \\ & \leq B^0_{v_{hk}}\stimes x(K_{h-1}+jV_h+k)\\
A^1_{v_{hk}} \otimes x(K_{h-1}+jV_h+k) &\leq x(K_{h-1}+jV_h+k+1)\\ & \leq B^1_{v_{hk}}\stimes x(K_{h-1}+jV_h+k),
\end{array}
\end{equation}

for all $h\in\dint{1,q}$, $k\in\dint{1,U_h}$,

\begin{equation}\label{eq:periodic_2}
\begin{array}{rl}
A^0_{u_{hk}} \otimes x(K_{h-1}+m_hV_h+k) & \leq x(K_{h-1}+m_hV_h+k)\\ & \leq B^0_{u_{hk}}\stimes x(K_{h-1}+m_hV_h+k),
\end{array}
\end{equation}

and for all $h\in\dint{1,q}$, $k\in\dint{1,U_h}$ with $(h,k)\neq(q,U_q)$,

\begin{equation}\label{eq:periodic_3}
\begin{array}{rl}
A^1_{u_{hk}} \otimes x(K_{h-1}+m_hV_h+k) & \leq x(K_{h-1}+m_hV_h+k+1) \\ & \leq B^1_{u_{hk}}\stimes x(K_{h-1}+m_hV_h+k).
\end{array}
\end{equation}

To search intermittently periodic trajectories, we substitute (<ref>) in (<ref>), obtaining:

for all $h\in\dint{1,q}$, $j\in\dint{0,m_h-1}$, $k\in\dint{1,V_h}$,

\begin{equation}\label{eq:intermittently_aux1}
\begin{array}{rcl}
A^0_{v_{hk}} \otimes \cancel{\lambda_h^{j}}x(K_{h-1}+k) \leq & \cancel{\lambda_h^{j}}x(K_{h-1}+k) & \leq B^0_{v_{hk}}\stimes \cancel{\lambda_h^{j}}x(K_{h-1}+k),
%A^1_{v_{hk}} \otimes \lambda_h^{j-1}x(K_{h-1}+k) &\leq \lambda_h^{j-1}x(K_{h-1}+k+1)\\ & \leq B^1_{v_{hk}}\stimes \lambda_h^{j-1}x(K_{h-1}+k),
\end{array}
\end{equation}

for all $h\in\dint{1,q}$, $j\in\dint{0,m_h-1}$, $k\in\dint{1,V_h-1}$,

\begin{equation}\label{eq:intermittently_aux2}
\begin{array}{rl}
A^1_{v_{hk}} \otimes \cancel{\lambda_h^{j}}x(K_{h-1}+k) &\leq \cancel{\lambda_h^{j}}x(K_{h-1}+k+1)\\ & \leq B^1_{v_{hk}}\stimes \cancel{\lambda_h^{j}}x(K_{h-1}+k),
\end{array}
\end{equation}

for all $h\in\dint{1,q}$, $j\in\dint{0,m_h-2}$ ($k = V_h$),

\begin{equation}\label{eq:intermittently_aux3}
\begin{array}{rcl}
A^1_{v_{hV_h}} \otimes \cancel{\lambda_h^{j}}x(K_{h-1}+V_h) \leq& \cancel{\lambda_h^{j}}\lambda_hx(K_{h-1}+1) & \leq B^1_{v_{hV_h}}\stimes \cancel{\lambda_h^{j}}x(K_{h-1}+V_h),
\end{array}
\end{equation}

and, for all $h\in\dint{1,q}$ ($j = m_h-1$, $k = V_h$),

\begin{equation}\label{eq:intermittently_aux4}
\begin{array}{rl}
A^1_{v_{hV_h}} \otimes \lambda_h^{m_h-1}x(K_{h-1}+V_h) &\leq x(K_{h-1}+m_h V_h +1)\\ & \leq B^1_{v_{hV_h}}\stimes \lambda_h^{m_h-1}x(K_{h-1}+V_h).
\end{array}
\end{equation}

To cancel out the $\lambda_h^{m_h-1}$'s from (<ref>), we perform a change of variables.
Let $\xi:\dint{1,U_0 + \left(\sum_{h=1}^{q}V_{h}+U_h\right)}\rightarrow \R^n$ be defined by:

for all $h\in\dint{0,q-1}$, $k\in\dint{\left(\sum_{j=1}^{h}U_{j-1}+V_j\right)+1,\sum_{j=1}^{h+1}U_{j-1}+V_j}$,

\[
\xi(k) = \left(\bigotimes_{j=1}^h \lambda_j^{-(m_j - 1)}\right) x\left(\left(\sum_{j=1}^h (m_j-1)V_j\right) + k\right),
\]

and for all $k\in\dint{\left(\sum_{j=1}^{q}U_{j-1}+V_j\right)+1,\left(\sum_{j=1}^{q}U_{j-1}+V_j\right) + U_q}$,

\[
\xi(k) = \left(\bigotimes_{j=1}^q \lambda_j^{-(m_j - 1)}\right) x\left(\left(\sum_{j=1}^q (m_j-1)V_j\right) + k\right).
\]

By substituting $\xi$ into inequalities (<ref>), (<ref>-<ref>) and simplifying whenever possible the terms in $\lambda_j$, we obtain that the above inequalities admit a solution in $x$ and $\lambda_1,\ldots,\lambda_q$ if and only if the following inequalities admit a solution in $\xi$ and $\lambda_1,\ldots,\lambda_q$: for all $h\in\dint{0,q}$, $k\in\dint{1,U_h}$,

\begin{equation}\label{eq:aux_init}
\begin{array}{rl}
A^0_{u_{hk}} \otimes \xi\left(\left(\sum_{j=1}^h U_{j-1}+V_j\right)+k\right) & \leq \xi\left(\left(\sum_{j=1}^h U_{j-1}+V_j\right)+k\right) \\
& \leq B^0_{u_{hk}} \stimes \xi\left(\left(\sum_{j=1}^h U_{j-1}+V_j\right)+k\right),
\end{array}
\end{equation}

for all $h\in\dint{0,q}$, $k\in\dint{1,U_h}$, $(h,k)\neq(q,U_q)$,

\begin{equation}
\begin{array}{rl}
A^1_{u_{hk}} \otimes \xi\left(\left(\sum_{j=1}^h U_{j-1}+V_j\right)+k\right) & \leq \xi\left(\left(\sum_{j=1}^h U_{j-1}+V_j\right)+k+1\right) \\
& \leq B^1_{u_{hk}} \stimes \xi\left(\left(\sum_{j=1}^h U_{j-1}+V_j\right)+k\right),
\end{array}
\end{equation}

for all $h\in\dint{1,q}$, $k\in\dint{1,V_h}$,

\begin{equation}
\begin{array}{r}
A^0_{v_{hk}} \otimes \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+k\right) \leq \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+k\right) \\
\leq B^0_{v_{hk}} \stimes \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+k\right),\\
A^1_{v_{hk}} \otimes \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+k\right) \leq \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+k+1\right) \\
\leq B^1_{v_{hk}} \stimes \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+k\right),\\
\end{array}
\end{equation}

and for all $h\in\dint{1,q}$ ($k=V_h$),

\begin{equation}\label{eq:aux_fina}
\begin{array}{r}
A^1_{v_{hV_h}} \otimes \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+V_h\right) \leq \lambda_h\xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+1\right) \\
\leq B^1_{v_{hV_h}} \stimes \xi\left(\left(U_0+\sum_{j=1}^{h-1} V_{j}+U_j\right)+V_h\right).
\end{array}
\end{equation}

The final step in the proof is to rewrite the inequalities (<ref>-<ref>) in terms of the extended vector

\[
\tilde{\xi} = \begin{bmatrix}
\xi(1)\\\svdots\\\xi\left(U_0 + \left(\sum_{h=1}^q V_{h}+U_h\right)\right)
\end{bmatrix}
\]

and use Proposition <ref> to get the max-plus-linear inequality

\begin{equation}\label{eq:final_aux}
A(\lambda_1,\ldots,\lambda_q) \otimes \tilde{\xi} \leq \tilde{\xi},
\end{equation}

where $A(\lambda_1,\ldots,\lambda_q)$ is a matrix with $(U_0 + \left(\sum_{h=1}^q V_{h}+U_h\right))n$ rows and columns.
Since only the first power of $\lambda_1,\ldots,\lambda_q$ shows up in (<ref>-<ref>), matrix $A(\lambda_1,\ldots,\lambda_q)$ has the desired form: $A(\lambda_1,\ldots,\lambda_q) = \bigoplus_{h=1}^q (\lambda_h P_h\oplus \lambda_h^{-1}I_h)\oplus C$.
Therefore, because of Proposition <ref>, (<ref>) translates into an MPIC-NCP.

§ PROOF OF THEOREM <REF>

Lumped-node representation of $\graph(A(\lambda_1,\lambda_2))$ from (<ref>).

For notational simplicity, we show how to prove the theorem for the matrix in (<ref>); the extension to the general case is simple but cumbersome.

First of all, it is useful to draw the parametric precedence graph $\graph(A(\lambda_1,\lambda_2))$ using the lumped-node representation (which was presented in Appendix <ref>); the graph is shown in Figure <ref>.
We recall that the objective is to describe in a more compact way the set $\solNCP{A(\lambda_1,\lambda_2)}$ of all parameters $(\lambda_1,\lambda_2)$ for which $\graph(A(\lambda_1,\lambda_2))$ does not contain circuits with positive weight.
Before illustrating the proof, it is convenient to relabel the nodes of $\graph(A(\lambda_1,\lambda_2))$ as in Figure <ref>; the graph in Figure <ref> therefore corresponds to the precedence graph $\graph(\overline{A}(\lambda_1,\lambda_2))$, where $\overline{A}$ is obtained permuting rows and columns of $A(\lambda_1,\lambda_2)$ as follows:

\begin{equation}\label{eq:intermittent_periodic_matrix_relabeled}
\scriptsize \overline{A}(\lambda_1,\lambda_2) =
\begin{bsmallmatrix}
C_{\wP_1} & \pazocal{E}  & \tikzmark{topleft} I_{\winit} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \lambda_1^{-1}I_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\tikzmark{toplefth} \pazocal{E} & C_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \lambda_2^{-1}I_{\wP_3} \tikzmark{toprighth} \\
P_{\winit} & \pazocal{E} & C_\winit & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
I_{\wP_1} & \pazocal{E} & \pazocal{E} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\lambda_1 P_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_2} & C_{\wP_4} & P_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & P_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_2} & C_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & I_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & C_{\wP_4} & P_{\wP_4} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \tikzmark{bottomleft} \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} \\
\pazocal{E} & \lambda_2 P_{\wP_3} & \tikzmark{bottomleft} \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_3}
\end{bsmallmatrix}.
\end{equation}

Clearly, $\graph(A(\lambda_1,\lambda_2))\in\nonegset$ if and only if $\graph(\overline{A}(\lambda_1,\lambda_2))\in\nonegset$.
We partition matrix $\overline{A}(\lambda_1,\lambda_2)$ in four blocks, as shown in (<ref>), and we use the notation

\[
\overline{A}(\lambda_1,\lambda_2)^* = \begin{bmatrix}
a & b \\ c & d
\end{bmatrix}^* = \begin{bmatrix}
\pazocal{M}^{11} & \pazocal{M}^{12}\\ \pazocal{M}^{21} & \pazocal{M}^{22}
\end{bmatrix},
\]

where $a$ and $\pazocal{M}^{11}$ are matrices of dimension $10\times 10$ (in general, $qn\times qn$).
Note that only blocks $b$ and $c$ depend on $\lambda_1$ and $\lambda_2$, whereas $a$ and $d$ are numerical matrices.

Then, we partition the set of circuits in $\graph(\overline{A}(\lambda_1,\lambda_2))$ in two subsets:

* the set of all circuits that do not pass through any node in $\overline{1}\cup\overline{2}$,

* the set containing all remaining circuits.

It is easy to see that there are no circuits with positive weight among those in the first subset if and only if $\graph(d)\in\nonegset$; due to the block tridiagonal structure of matrix $d$, verifying whether $\graph(d)$ contains circuits with positive weight can be done in linear time in the length of $u_0,\ldots,u_q$, $v_1,\ldots,v_q$ (i.e., the lengths of subschedules $\winit$, $\wP_1\wP_1\wP_3\wP_2\wP_4$, and $\wP_1\wP_3\wP_2\wP_4$) using the methods seen in Appendix <ref> (or, equivalently, in <cit.>).

As for the second subset of circuits, they all visit at least one node in $\overline{1}\cup\overline{2}$; therefore, their weight is non-positive if and only if $\graph(\pazocal{M}^{11})\in\nonegset$.
We can compute $\pazocal{M}^{11}$ using Lemma <ref>:

\[
\pazocal{M}^{11} = a^* (a^* bd^*ca^*)^*a^*.
\]

Therefore, $\graph(\pazocal{M}^{11})\in\nonegset$ if and only if

* $\graph(a)\in\nonegset$,

* $\graph(a^* bd^* ca^*)\in\nonegset$.

Since $a = \begin{bsmallmatrix}
C_{\wP_1} & \pazocal{E}\\
\pazocal{E} & C_{\wP_2}
\end{bsmallmatrix}$, the first condition is equivalent to having $\graph(C_{\wP_1})\in\nonegset$ and $\graph(C_{\wP_2})\in\nonegset$ (more generally, one has to check the non-positiveness of the circuits in $q$ precedence graphs, each of which contains $n$ nodes).

To check the second condition, we must compute $a^* bd^* ca^*$.
The main challenge here is to find a closed formula for

\[
bd^*c =
\begin{bsmallmatrix}
I_{\winit} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \lambda_1^{-1}I_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}\\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \lambda_2^{-1}I_{\wP_3}
\end{bsmallmatrix}\otimes
\]

\[
%	\begin{bsmallmatrix}
%		I_{\winit} & \pazocal{E} \\
%		P_{\wP_1} & \pazocal{E} \\
%		\pazocal{E} & \pazocal{E} \\
%		\pazocal{E} & \pazocal{E} \\
%		\lambda_1 I_{\wP_4} & \pazocal{E} \\
%		\pazocal{E} & \pazocal{E} \\
%		\pazocal{E} & \pazocal{E} \\
%		\pazocal{E} & \pazocal{E} \\
%		\pazocal{E} & I_{\wP_4} \\
%		\pazocal{E} & P_{\wP_1} \\
%		\pazocal{E} & \pazocal{E} \\
%		\pazocal{E} & \lambda_2^{-1} I_{\wP_4} \\
%	\end{bsmallmatrix}^\top
\otimes
\begin{bsmallmatrix}
C_\winit & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E}& \pazocal{E}  \\
\pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_2} & C_{\wP_4} & P_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3} & P_{\wP_3} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3} & C_{\wP_2} & P_{\wP_2} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_2} & C_{\wP_4} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & C_{\wP_4} & P_{\wP_4} & \pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_4} & C_{\wP_1} & P_{\wP_1} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_1} & C_{\wP_3}& P_{\wP_3} \\
\pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & \pazocal{E} & I_{\wP_3}& C_{\wP_3}
\end{bsmallmatrix}^*
\begin{bsmallmatrix}
P_{\winit} & \pazocal{E} \\
I_{\wP_1} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} \\
\lambda_1 P_{\wP_4} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} \\
\pazocal{E} & P_{\wP_4} \\
\pazocal{E} & I_{\wP_2} \\
\pazocal{E} & \pazocal{E} \\
\pazocal{E} & \pazocal{E} \\
\pazocal{E} & \lambda_2 P_{\wP_3}
\end{bsmallmatrix},
\]

which can be obtained by using Remarks <ref>, <ref>, and <ref>; the computation takes linear time complexity in the length of subschedules $u_0,\ldots,u_q$, $v_0,\ldots,v_q$.
The resulting matrix $a^* bd^* ca^*$, of the form $\lambda_1 P_1 \oplus \lambda_1^{-1} I_1 \oplus \lambda_2 P_2 \oplus \lambda_2^{-1} I_2 \oplus C$ (in general $\bigoplus_{i=1}^q \lambda_i P_i \oplus \lambda_i^{-1} I_i \oplus C$), has a number of rows and columns equal to $10$ (in general $qn$).
In conclusion, we reduced an MPIC-NCP on a graph with $75$ nodes (in general, $(U_0+\sum_{i=1}^q V_i + U_i)n$ nodes) to another MPIC-NCP on a graph with only $10$ nodes (in general, $pn$ nodes).

Lumped-node representation of $\graph(\overline{A}(\lambda_1,\lambda_2))$ from (<ref>).

§ ACKNOWLEDGMENT

We would like to thank Angelos Koumpis for implementing in C MEX a cache-aware max-plus matrix multiplication, which helped achieving the computational time shown in Figure <ref>.

This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), Projektnummer RA 516/14-1.
Partially supported by RVO 67985840, by the GACR grant 19-06175J, and by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy – EXC 2002/1 "Science of Intelligence" – project number 390523135.

§ CONFLICT OF INTEREST

The authors have no conflict of interest to declare that are relevant to this article.