这道题绝大部分解法都是通过 ultra 一个奇怪的 $3\times 3\times 3$ 张量分解的 CP 分解数量来优化复杂度。在这个路线下，存在

• 梯度下降法做到 $r=4$，但是带有误差，见原始题解。
• 各种搞做到精确的 $r=4$。
  • https://www.luogu.com.cn/article/jdr1trgx （这里除了题解，还可以将 $\{0,1,-1\}$ 修改成 $\{2,1,0,-1,-2\}$ 可以解决掉除了 op(i,j)=(i+j)mod 3 以外的情况，可以见最后）
  • https://qoj.ac/submission/3187250
  • luogu 上还有一些 $r=5$ 的构造。总之各种各样。

并且 $r=4$ 已经是极限了，根据 知乎（其实还有其他回答也有相关的内容），我们知道，如果存在一个秩 $r=3$ 的张量 $T=(M_1,M_2,M_3)$（每个 $M_i$ 是 $3\times 3$ 的矩阵），且 $M_1$ 可逆，那么 $[M_1^{-1}M_2,M_1^{-1}M_3]=0$。下面内容借助了 AI 书写，因为作者不知道如何优雅的抄写zhihu内容。

$$T = M_0 \otimes e_0 + M_1 \otimes e_1 + M_2 \otimes e_2.$$ 这里 $M_k$ 是第 $k$ 个切片矩阵，$e_k$ 是标准基向量。根据 $r=3$：

$$T = \sum_{i=1}^3 u_i \otimes v_i \otimes w_i,$$ 其中 $u_i, v_i \in \mathbb{k}^3$，$w_i \in \mathbb{k}^3$。

按第三个指标切片，第 $k$ 个切片为： $$M_k = \sum_{i=1}^3 (w_i)_k\, u_i v_i^\top.$$ 这里 $(w_i)_k$ 是向量 $w_i$ 的第 $k$ 个分量。

特别地，假设 $A = M_0$ 可逆。由于 $$A = \sum_{i=1}^3 \alpha_i\, u_i v_i^\top,\quad \alpha_i = (w_i)_0,$$ 这是一个三个秩一矩阵之和。如果 $A$ 可逆（秩为3），那么： - 向量组 $\{u_1, u_2, u_3\}$ 必须线性无关，否则 $A$ 的秩小于3； - 向量组 $\{v_1, v_2, v_3\}$ 也必须线性无关，否则 $A$ 的秩小于3。

因此，$\{u_i\}$ 和 $\{v_i\}$ 各自构成 $\mathbb{k}^3$ 的一组基。可以把 $u_i$ 和 $v_i$ 变成标准基： $$u_i = e_i,\qquad v_i = e_i,\quad i=1,2,3.$$ （这里 $e_i$ 是 $\mathbb{k}^3$ 的标准基向量。）

于是切片 $A$ 变成： $$A = \sum_{i=1}^3 \alpha_i\, e_i e_i^\top = \operatorname{diag}(\alpha_1, \alpha_2, \alpha_3).$$ 因为 $A$ 可逆，所有 $\alpha_i \neq 0$。

其他两个切片 $B = M_1$ 和 $C = M_2$ 也相应变成： $$B = \sum_{i=1}^3 \beta_i\, e_i e_i^\top = \operatorname{diag}(\beta_1, \beta_2, \beta_3),$$ $$C = \sum_{i=1}^3 \gamma_i\, e_i e_i^\top = \operatorname{diag}(\gamma_1, \gamma_2, \gamma_3).$$ 也就是说，在可逆切片 $A$ 可逆的条件下，通过基变换，所有切片都可以同时对角化。

现在计算： $$A^{-1}B = \operatorname{diag}(\beta_1/\alpha_1,\ \beta_2/\alpha_2,\ \beta_3/\alpha_3),$$ $$A^{-1}C = \operatorname{diag}(\gamma_1/\alpha_1,\ \gamma_2/\alpha_2,\ \gamma_3/\alpha_3).$$ 两个对角矩阵必然交换，所以 $$[A^{-1}B, A^{-1}C] = 0.$$

推广到边界秩 $\le 3$ 是容易的，因为边界秩就是被一系列秩为3的张量逼近，取极限即可。

知乎回答中构造了一个运算表，拆分成 $A,B,C$： $$A = I,\qquad B ,\qquad C = J - I - B.$$ $J$ 是全1矩阵，$B$ 只有 $(0,1)$ 为1、其余为0。

$A = I$ 可逆，且 $A^{-1} = I$，所以 $$A^{-1}B = B ,\qquad A^{-1}C = C = J - I - B.$$ 显然可以忽略 $[B,I]$ 和 $[B,B]$ 项。然而 $$BJ - J B = \begin{pmatrix} 1 & 0 & 1 \\ 0 & -1 & 0 \\ 0 & -1 & 0 \end{pmatrix} \neq 0.$$ 这个矩阵非零，说明交换子不为零。所以 $r \ge 4.$

张量 $X\in\{0,1\}^{3\times3\times3}$，索引 $i,j,k\in\{0,1,2\}$：

$$X_{i,j,k}=[\;\mathrm{op}(i,j)=k\;],\qquad \mathrm{op}(i,j)=(i+j)\bmod 3,\ \text{但}\ \mathrm{op}(2,2)=0$$

三个切片：

$$X_0=\begin{pmatrix}1&0&0\\0&0&1\\0&1&1\end{pmatrix},\quad X_1=\begin{pmatrix}0&1&0\\1&0&0\\0&0&0\end{pmatrix},\quad X_2=\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix}$$

$$X=\sum_{t=1}^{4} a_t\otimes b_t\otimes c_t=\sum_{t=1}^4 a_t[i]\,b_t[j]\,c_t[k]$$