Proof for associativity of semi-tensor product

Preliminaries

In this section we’d like to introduce some definitions and properties involved in the proof for associativity of the semi-tensor product.

Definition 1 (kronecker product). Let A \in \mathcal{M}_{m \times n}, B \in \mathcal{M}_{p \times q}, then the kronecker product A \otimes B \in \mathcal{M}_{pm \times qn} is defined A \otimes B = \left[\begin{array}{ccc} a_{11} B & \ldots & a_{1 n} B\\ \vdots & \ddots & \vdots\\ a_{m 1} B & \ldots & a_{mn} B \end{array}\right] .

Lemma 1. Let A \in \mathcal{M}_{m \times n}, B \in \mathcal{M}_{p \times q}, C \in \mathcal{M}_{n \times r} and D \in \mathcal{M}_{q \times s}, then (A \otimes B) (C \otimes D) = (AC \otimes BD) .

Definition 2 (semi-tensor product). Let A \in \mathcal{M}_{m \times n}, B \in \mathcal{M}_{p \times q}, l = {\operatorname{lcm}} (n, p) being least common multiple of n and p. The semi-tensor product \ltimes is defined A \ltimes B = (A \otimes I_{l / n}) (B \otimes I_{l / p}) .

Theorem 1 (prime factorization theorem). every integer n greater than 1 can be represented uniquely as n = \prod_{i = 1}^k p_i^{n_i}, where p_1 < p_2 < \cdots < p_k are primes and the n_i are positive integers.

Corollary 1. ab = {\operatorname{lcm}} (a, b) \gcd (a, b).

Associativity of the semi-tensor product

Proposition 1. Let A \in \mathcal{M}_{p \times q}, B \in \mathcal{M}_{r \times s} and C \in \mathcal{M}_{t \times u}, then (A \ltimes B) \ltimes C = A \ltimes (B \ltimes C) .

Considering that the form of (A \ltimes B) \ltimes C and A \ltimes (B \ltimes C) are not that simple, it’s not a wise idea to prove the proposition by directly calculate the results of both sides and compare them. The procedure we would take is to find some equivalent but more simple forms to test the associativity, and then obtain the associativity of the semi-tensor product from the equivalent forms.

Proof. Define \ltimes_0: A \ltimes_0 B = (A \otimes I_r) (B \otimes I_q). Then we get \left\{\begin{array}{l} I_r = I_{{\operatorname{lcm}} (q, r) / q} \otimes I_{\gcd (q, r)},\\ I_q = I_{{\operatorname{lcm}} (q, r) / r} \otimes I_{\gcd (q, r) .} \end{array}\right. Thus \begin{aligned} (A \ltimes_0 B) & = (A \otimes I_{{\operatorname{lcm}} (q, r) / q} \otimes I_{\gcd (q, r)}) (B \otimes I_{{\operatorname{lcm}} (q, r) / r} \otimes I_{\gcd (q, r)})\\ & = (A \ltimes B) \otimes I_{\gcd (q, r)} . \end{aligned} Considering (A \ltimes_0 B) \ltimes_0 C and A \ltimes_0 (B \ltimes_0 C), \begin{aligned} (A \ltimes_0 B) \ltimes_0 C & = ((A \ltimes_0 B) \otimes I_t) (C \otimes I_{qs})\\ & = ((A \otimes I_r) (B \otimes I_q) \otimes I_t) (C \otimes I_{qs})\\ & = (A \otimes I_{rt}) (B \otimes I_{qt}) (C \otimes I_{qs})\\ & = (A \otimes I_{rt}) ((B \otimes I_t) (C \otimes I_s) \otimes I_q)\\ & = (A \otimes I_{rt}) ((B \ltimes_0 C) \otimes I_q)\\ & = A \ltimes_0 (B \ltimes_0 C), \end{aligned} thus the operator \ltimes_0 is associative.

Then we consider the relation between (A \ltimes_0 B) \ltimes_0 C and (A \ltimes B) \ltimes C. \begin{aligned} (A \ltimes_0 B) \ltimes_0 C & = ((A \ltimes B) \otimes I_{\gcd (q, r)}) \ltimes_0 C\\ & = (((A \ltimes B) \otimes I_{\gcd (q, r)}) \ltimes C) \otimes I_{\gcd (qs, t)}\\ & = (((A \ltimes B) \otimes I_{\gcd (q, r)}) \otimes I_{{\operatorname{lcm}} (qs, t) / (qs)}) (C \otimes I_{{\operatorname{lcm}} (qs, t)}) \otimes I_{\gcd (qs, t)}\\ & = (((A \ltimes B) \otimes I_{\gcd (q, r)}) \otimes I_t) (C \otimes I_{qs})\\ & = ((A \ltimes B) \otimes I_{\gcd (q, r) t}) (C \otimes I_{qs}) \end{aligned} For convenience, we denote I \{ n \} : = I_n, and then we get \begin{aligned} ((A \ltimes B) \otimes I_{\gcd (q, r) t}) & = (A \ltimes B) \otimes I \left\{ \frac{r {\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}{s {\operatorname{lcm}} (q, r)} \right\} \otimes I \left\{ \frac{st {\operatorname{lcm}} (q, r) \gcd (q, r)}{r {\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} \right\}\\ & = (A \ltimes B) \otimes I \left\{ \frac{r {\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}{s {\operatorname{lcm}} (q, r)} \right\} \otimes I \left\{ \frac{sqt}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} \right\}\\ & = (A \ltimes B) \otimes I \left\{ \frac{r {\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}{s {\operatorname{lcm}} (q, r)} \right\} \otimes I \left\{ \gcd (q, r) \gcd \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right) \right\}, \end{aligned} and (C \otimes I_{qs}) = C \otimes I \left\{ \frac{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}{t} \right\} \otimes I \left\{ \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} \right\} . it’s not hard to find that \gcd (q, r) \gcd \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right) = \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}, \begin{aligned} \gcd (q, r) \gcd \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right) = \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} & \Leftrightarrow tqs = \gcd (q, r) \frac{st {\operatorname{lcm}} (q, r)}{r}\\ & \Leftrightarrow tqs = \frac{sqrt}{r}, \end{aligned} and that’s trivial.

Thus we get (A \ltimes_0 B) \ltimes_0 C = ((A \ltimes B) \ltimes C) \otimes I \left\{ \gcd (q, r) \gcd \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right) \right\}.

By the same method, we consider A \ltimes_0 (B \ltimes_0 C). \begin{aligned} A \ltimes_0 (B \ltimes_0 C) & = A \ltimes_0 ((B \ltimes C) \otimes I \{ \gcd (s, t) \})\\ & = (A \ltimes ((B \ltimes C) \otimes I \{ \gcd (s, t) \})) \otimes I \{ \gcd (q, rt) \}\\ & = \begin{aligned} &\left( A \otimes I \left\{ \frac{{\operatorname{lcm}} (q, rt)}{q} \right\} \right) \left( (B \ltimes C) \otimes I \left\{ \frac{\gcd (s, t) {\operatorname{lcm}} (q, rt)}{rt} \right\} \right)\\ &\otimes I \{ \gcd (q, rt) \} \end{aligned}\\ & = (A \otimes I \{ rt \}) ((B \ltimes C) \otimes I \{ q \gcd (s, t) \}) \end{aligned} \begin{aligned} (A \otimes I \{ rt \}) & = A \otimes I \left\{ \frac{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)}{q} \right\} \otimes I \left\{ \frac{rtq}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} \right\} \end{aligned} and \begin{aligned} ((B \ltimes C) \otimes I \{ q \gcd (s, t) \}) & = (B \ltimes C) \otimes I \left\{ \frac{s {\operatorname{lcm}} \left( \frac{r {\operatorname{lcm}} (s, t)}{s}, q \right)}{r {\operatorname{lcm}} (s, t)} \right\} \otimes I \left\{ \frac{qrt}{{\operatorname{lcm}} \left( \frac{r {\operatorname{lcm}} (s, t)}{s}, q \right)} \right\} \end{aligned} so we get A \ltimes_0 (B \ltimes_0 C)= (A \ltimes (B \ltimes C)) \otimes I \left\{ \frac{qrt}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} \right\}.

And then we prove that \frac{qrt}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} = \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}. \begin{aligned} \frac{qrt}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} = \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} & \Leftrightarrow \frac{r}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} = \frac{s}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)}\\ & \Leftrightarrow r {\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right) = s {\operatorname{lcm}} \left( \frac{r {\operatorname{lcm}} (s, t)}{s} \right) . \end{aligned} When q, r, s, t are coprime, \begin{aligned} \frac{s}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} & = \frac{s}{{\operatorname{lcm}} (sq, t)}\\ & = \frac{1}{qt}\\ & = \frac{r}{prst / s}\\ & = \frac{r}{{\operatorname{lcm}} \left( \frac{r {\operatorname{lcm}} (s, t)}{s}, q \right)} . \end{aligned} And when they are not coprime, Let q = \prod_{i = 1}^n p_i^{a_i}, r = \prod_{i = 1}^n p_i^{b_i}, s = \prod_{i = 1}^n p_i^{c_i}, t = \prod_{i = 1}^n p_i^{d_i}, and then we get \begin{aligned} r {\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right) & = \prod_{i = 1}^n p_i^{b_i} {\operatorname{lcm}} \left( \prod_{i = 1}^n p_i^{\min (a_i, b_i) + c_i - d_i}, \prod_{i = 1}^n p_i^{d_i} \right)\\ & = \prod_{i = 1}^n p_i^{b_i + \min (\min (a_i, b_i) + c_i - b_i, d_i)},\\ s {\operatorname{lcm}} \left( \frac{r {\operatorname{lcm}} (s, t)}{s} \right) & = \prod_{i = 1}^n p_i^{c_i} {\operatorname{lcm}} \left( \prod_{i = 1}^n p_i^{\min (c_i, d_i) + b_i - c_i}, \prod_{i = 1}^n p_i^{a_i} \right)\\ & = \prod_{i = 1}^n p_i^{c_i + \min (\min (c_i, d_i) + b_i - c_i, a_i)} . \end{aligned} It remains to prove that \begin{aligned} & b_i + \min (\min (a_i, b_i) + c_i - b_i, d_i) = c_i + \min (\min (c_i, d_i) + b_i - c_i, a_i)\\ \Leftrightarrow &b_i - c_i + \min (\min (a_i, b_i) + c_i - b_i, d_i) = \min (\min (c_i, d_i) + b_i - c_i, a_i) \\ \Leftrightarrow & \min (\min (a_i, b_i), d_i + b_i - c_i) = \min (\min (c_i, d_i) + b_i - c_i, a_i) \\ \Leftrightarrow & \min (\min (a_i, b_i), d_i + b_i - c_i) = \min (\min (b_i, d_i + b_i - c_i) , a_i) \\ \Leftrightarrow &\min (a_i, b_i, d_i + b_i - c_i) = \min (b_i, d_i + b_i - c_i, a_i) \end{aligned} and that’s trivial.

Then by doing projection, \begin{aligned} A \ltimes_0 (B \ltimes_0 C) = (A \ltimes_0 B) \ltimes_0 C & \Leftrightarrow (A \ltimes_0 (B \ltimes_0 C)) \Psi = ((A \ltimes_0 B) \ltimes_0 C) \Psi\\ & \Leftrightarrow A \ltimes (B \ltimes C) = (A \ltimes B) \ltimes C, \end{aligned} where \begin{aligned} \Psi &= \left( I \left\{ qsu - \frac{qrt}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} \right\} \otimes {\boldsymbol{1}} \left\{ \frac{qrt}{{\operatorname{lcm}} \left( q, \frac{r {\operatorname{lcm}} (s, t)}{s} \right)} \right\} \right)\\ &= \left( I \left\{ qsu - \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} \right\} \otimes {\boldsymbol{1}} \left\{ \frac{tqs}{{\operatorname{lcm}} \left( \frac{s {\operatorname{lcm}} (q, r)}{r}, t \right)} \right\} \right) \end{aligned} ◻