Proof for associativity of semi-tensor product
January 29, 2023
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 ∈ ℳ m × n , B ∈ ℳ p × q A \in \mathcal{M}_{m \times n}, B \in \mathcal{M}_{p \times q} A ⊗ B ∈ ℳ p m × q n A \otimes B \in \mathcal{M}_{pm \times qn} A ⊗ B = [ a 11 B … a 1 n B ⋮ ⋱ ⋮ a m 1 B … a m n B ] . 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 ∈ ℳ m × n A \in \mathcal{M}_{m \times n} B ∈ ℳ p × q B \in \mathcal{M}_{p \times q} C ∈ ℳ n × r C
\in \mathcal{M}_{n \times r} D ∈ ℳ q × s D \in \mathcal{M}_{q \times s} ( A ⊗ B ) ( C ⊗ D ) = ( A C ⊗ B D ) . (A \otimes B) (C \otimes D) = (AC \otimes BD) .
Definition 2 (semi-tensor product). Let
A ∈ ℳ m × n , B ∈ ℳ p × q A \in \mathcal{M}_{m \times n}, B \in \mathcal{M}_{p \times q} l = lcm ( n , p ) l =
{\operatorname{lcm}} (n, p) n n p p ⋉ \ltimes A ⋉ B = ( A ⊗ I l / n ) ( B ⊗ I l / p ) . A \ltimes B = (A \otimes I_{l / n}) (B \otimes I_{l / p}) .
Theorem 1 (prime factorization theorem). every
integer
n n 1 1 n = ∏ i = 1 k p i n i , n = \prod_{i = 1}^k p_i^{n_i}, p 1 < p 2 < ⋯ < p k p_1 < p_2 < \cdots < p_k n i n_i
Corollary 1 .
a b = lcm ( a , b ) gcd ( a , b ) ab = {\operatorname{lcm}} (a, b) \gcd (a, b)
Associativity of the
semi-tensor product
Proposition 1 . Let
A ∈ ℳ p × q A \in \mathcal{M}_{p \times q} B ∈ ℳ r × s B \in \mathcal{M}_{r \times s} C ∈ ℳ t × u C \in \mathcal{M}_{t \times u} ( A ⋉ B ) ⋉ C = A ⋉ ( B ⋉ C ) . (A \ltimes B) \ltimes C = A \ltimes (B \ltimes C) .
Considering that the form of
( A ⋉ B ) ⋉ C (A \ltimes B) \ltimes C A ⋉ ( B ⋉ C ) A \ltimes (B
\ltimes C)
Proof. Define
⋉ 0 \ltimes_0 A ⋉ 0 B = ( A ⊗ I r ) ( B ⊗ I q ) A \ltimes_0 B = (A \otimes I_r) (B \otimes I_q)
{ I r = I lcm ( q , r ) / q ⊗ I gcd ( q , r ) , I q = I lcm ( q , r ) / r ⊗ I gcd ( q , r ) . \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
( A ⋉ 0 B ) = ( A ⊗ I lcm ( q , r ) / q ⊗ I gcd ( q , r ) ) ( B ⊗ I lcm ( q , r ) / r ⊗ I gcd ( q , r ) ) = ( A ⋉ B ) ⊗ I gcd ( q , r ) . \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 ⋉ 0 B ) ⋉ 0 C (A \ltimes_0 B) \ltimes_0 C
and
A ⋉ 0 ( B ⋉ 0 C ) A \ltimes_0 (B \ltimes_0 C) ,
( A ⋉ 0 B ) ⋉ 0 C = ( ( A ⋉ 0 B ) ⊗ I t ) ( C ⊗ I q s ) = ( ( A ⊗ I r ) ( B ⊗ I q ) ⊗ I t ) ( C ⊗ I q s ) = ( A ⊗ I r t ) ( B ⊗ I q t ) ( C ⊗ I q s ) = ( A ⊗ I r t ) ( ( B ⊗ I t ) ( C ⊗ I s ) ⊗ I q ) = ( A ⊗ I r t ) ( ( B ⋉ 0 C ) ⊗ I q ) = A ⋉ 0 ( B ⋉ 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
⋉ 0 \ltimes_0
is associative.
Then we consider the relation between
( A ⋉ 0 B ) ⋉ 0 C (A \ltimes_0 B) \ltimes_0 C ( A ⋉ B ) ⋉ C (A
\ltimes B) \ltimes C
( A ⋉ 0 B ) ⋉ 0 C = ( ( A ⋉ B ) ⊗ I gcd ( q , r ) ) ⋉ 0 C = ( ( ( A ⋉ B ) ⊗ I gcd ( q , r ) ) ⋉ C ) ⊗ I gcd ( q s , t ) = ( ( ( A ⋉ B ) ⊗ I gcd ( q , r ) ) ⊗ I lcm ( q s , t ) / ( q s ) ) ( C ⊗ I lcm ( q s , t ) ) ⊗ I gcd ( q s , t ) = ( ( ( A ⋉ B ) ⊗ I gcd ( q , r ) ) ⊗ I t ) ( C ⊗ I q s ) = ( ( A ⋉ B ) ⊗ I gcd ( q , r ) t ) ( C ⊗ I q s ) \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 I \{ n \} : = I_n ,
and then we get
( ( A ⋉ B ) ⊗ I gcd ( q , r ) t ) = ( A ⋉ B ) ⊗ I { r lcm ( s lcm ( q , r ) r , t ) s lcm ( q , r ) } ⊗ I { s t lcm ( q , r ) gcd ( q , r ) r lcm ( s lcm ( q , r ) r , t ) } = ( A ⋉ B ) ⊗ I { r lcm ( s lcm ( q , r ) r , t ) s lcm ( q , r ) } ⊗ I { s q t lcm ( s lcm ( q , r ) r , t ) } = ( A ⋉ B ) ⊗ I { r lcm ( s lcm ( q , r ) r , t ) s lcm ( q , r ) } ⊗ I { gcd ( q , r ) gcd ( s lcm ( q , r ) r , t ) } , \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 ⊗ I q s ) = C ⊗ I { lcm ( s lcm ( q , r ) r , t ) t } ⊗ I { t q s lcm ( s lcm ( q , r ) r , t ) } . (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 ( s lcm ( q , r ) r , t ) = t q s lcm ( s lcm ( q , r ) r , t ) \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)} ,
gcd ( q , r ) gcd ( s lcm ( q , r ) r , t ) = t q s lcm ( s lcm ( q , r ) r , t ) ⇔ t q s = gcd ( q , r ) s t lcm ( q , r ) r ⇔ t q s = s q r t r , \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 ⋉ 0 B ) ⋉ 0 C = ( ( A ⋉ B ) ⋉ C ) ⊗ I { gcd ( q , r ) gcd ( s lcm ( q , r ) r , t ) } (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 ⋉ 0 ( B ⋉ 0 C ) A \ltimes_0 (B \ltimes_0 C)
A ⋉ 0 ( B ⋉ 0 C ) = A ⋉ 0 ( ( B ⋉ C ) ⊗ I { gcd ( s , t ) } ) = ( A ⋉ ( ( B ⋉ C ) ⊗ I { gcd ( s , t ) } ) ) ⊗ I { gcd ( q , r t ) } = ( A ⊗ I { lcm ( q , r t ) q } ) ( ( B ⋉ C ) ⊗ I { gcd ( s , t ) lcm ( q , r t ) r t } ) ⊗ I { gcd ( q , r t ) } = ( A ⊗ I { r t } ) ( ( B ⋉ C ) ⊗ I { q gcd ( s , t ) } ) \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} ( A ⊗ I { r t } ) = A ⊗ I { lcm ( q , r lcm ( s , t ) s ) q } ⊗ I { r t q lcm ( q , r lcm ( s , t ) s ) } \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
( ( B ⋉ C ) ⊗ I { q gcd ( s , t ) } ) = ( B ⋉ C ) ⊗ I { s lcm ( r lcm ( s , t ) s , q ) r lcm ( s , t ) } ⊗ I { q r t lcm ( r lcm ( s , t ) s , q ) } \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 ⋉ 0 ( B ⋉ 0 C ) = ( A ⋉ ( B ⋉ C ) ) ⊗ I { q r t lcm ( q , r lcm ( s , t ) s ) } 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
q r t lcm ( q , r lcm ( s , t ) s ) = t q s lcm ( s lcm ( q , r ) r , t ) \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)}
q r t lcm ( q , r lcm ( s , t ) s ) = t q s lcm ( s lcm ( q , r ) r , t ) ⇔ r lcm ( q , r lcm ( s , t ) s ) = s lcm ( s lcm ( q , r ) r , t ) ⇔ r lcm ( s lcm ( q , r ) r , t ) = s lcm ( r lcm ( s , t ) s ) . \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 q, r, s, t
are coprime,
s lcm ( s lcm ( q , r ) r , t ) = s lcm ( s q , t ) = 1 q t = r p r s t / s = r lcm ( r lcm ( s , t ) s , q ) . \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 = ∏ i = 1 n p i a i q = \prod_{i = 1}^n p_i^{a_i} ,
r = ∏ i = 1 n p i b i r =
\prod_{i = 1}^n p_i^{b_i} ,
s = ∏ i = 1 n p i c i s = \prod_{i = 1}^n p_i^{c_i} ,
t = ∏ i = 1 n p i d i t = \prod_{i =
1}^n p_i^{d_i} , and then we get
r lcm ( s lcm ( q , r ) r , t ) = ∏ i = 1 n p i b i lcm ( ∏ i = 1 n p i min ( a i , b i ) + c i − d i , ∏ i = 1 n p i d i ) = ∏ i = 1 n p i b i + min ( min ( a i , b i ) + c i − b i , d i ) , s lcm ( r lcm ( s , t ) s ) = ∏ i = 1 n p i c i lcm ( ∏ i = 1 n p i min ( c i , d i ) + b i − c i , ∏ i = 1 n p i a i ) = ∏ i = 1 n p i c i + min ( min ( c i , d i ) + b i − c i , a i ) . \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
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 ) ⇔ 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 ) ⇔ min ( min ( a i , b i ) , d i + b i − c i ) = min ( min ( c i , d i ) + b i − c i , a i ) ⇔ min ( min ( a i , b i ) , d i + b i − c i ) = min ( min ( b i , d i + b i − c i ) , a i ) ⇔ min ( a i , b i , d i + b i − c i ) = min ( b i , d i + b i − c i , a i ) \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,
A ⋉ 0 ( B ⋉ 0 C ) = ( A ⋉ 0 B ) ⋉ 0 C ⇔ ( A ⋉ 0 ( B ⋉ 0 C ) ) Ψ = ( ( A ⋉ 0 B ) ⋉ 0 C ) Ψ ⇔ A ⋉ ( B ⋉ C ) = ( A ⋉ B ) ⋉ C , \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
Ψ = ( I { q s u − q r t lcm ( q , r lcm ( s , t ) s ) } ⊗ 𝟏 { q r t lcm ( q , r lcm ( s , t ) s ) } ) = ( I { q s u − t q s lcm ( s lcm ( q , r ) r , t ) } ⊗ 𝟏 { t q s lcm ( s lcm ( q , r ) r , t ) } ) \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} ◻