クロネッカー積のランク - 勾配降下党青年局

LyCORISのlokrで使われる、クロネッカー積とランクの関係が気になったので、検索してみたのですが、
日本語の記事は全く見つからずよく分からない英語の情報だけ見つかったので、その証明を確認してみます。
math.stackexchange.com

クロネッカー積とは行列 $A,B$ に対して、以下のような行列を返す演算です。
$A \otimes B = \begin{pmatrix} a_{11}B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B &\cdots & a_{mn}B \\ \end{pmatrix}$

$(m,n)$ 行列と $(p,q)$ 行列に対してクロネッカー積を適用すると、 $(mp,nq)$ 行列になります。

$\mathrm{rank}(A\otimes B) = \mathrm{rank}(A)\mathrm{rank}(B)$ になるらしく、その証明を目指します。

補題1.

行列 $A,B,C,D$ に対して、 $AC$ や $BD$ が定義できるサイズのとき、
$(A\otimes B)(C\otimes D) = AC\otimes BD$
証明.
$\begin{eqnarray} (A\otimes B)(C\otimes D) & =& \begin{pmatrix} a_{11}B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B &\cdots & a_{mn}B \\ \end{pmatrix} \begin{pmatrix} c_{11}D & \cdots & c_{1l}D \\ \vdots & \ddots & \vdots \\ c_{n1}D &\cdots & c_{nl}D \\ \end{pmatrix} \\ &=&\begin{pmatrix} {\displaystyle\sum_{k=1}^{n}} a_{1k}c_{k1}BD & \cdots & {\displaystyle\sum_{k=1}^{n}} a_{1k}c_{kl}BD \\ \vdots & \ddots & \vdots \\ {\displaystyle\sum_{k=1}^{n}} a_{mk}c_{k1}BD &\cdots & {\displaystyle\sum_{k=1}^{n}} a_{mk}c_{kl}BD \\ \end{pmatrix} \\ &=&\begin{pmatrix} {\displaystyle\sum_{k=1}^{n}} a_{1k}c_{k1} & \cdots & {\displaystyle\sum_{k=1}^{n}} a_{1k}c_{kl} \\ \vdots & \ddots & \vdots \\ {\displaystyle\sum_{k=1}^{n}} a_{mk}c_{k1} &\cdots & {\displaystyle\sum_{k=1}^{n}} a_{mk}c_{kl} \\ \end{pmatrix} \otimes BD \\ &=& AC\otimes BD \end{eqnarray}$

補題2.

$A,B$ が正則行列のとき、 $A\otimes B$ も正則行列。
逆行列は $(A\otimes B)^{-1}= A^{-1}\otimes B^{-1}$
証明.
$A$ を $(m,m)$ 行列、 $B$ を $(n,n)$ 行列とすると、補題1を使って、
$\begin{eqnarray} (A\otimes B)(A^{-1}\otimes B^{-1}) &=& AA^{-1} \otimes BB^{-1} \\ & =& I_m \otimes I_n \\ &=&\begin{pmatrix} I_n & & \huge{0} \\ & \ddots & \\ \huge{0} && I_n \\ \end{pmatrix} (m行) \\ &=& I_{mn} \end{eqnarray}$

補題3.

正則行列をかけてもrankは変わらない。つまり正則行列 $B,C$ と任意の行列 $A$ に対して、
$\mathrm{rank}(AB) = \mathrm{rank}(A)$
$\mathrm{rank}(CA) = \mathrm{rank}(A)$

証明.
以下のリンクに丸投げ。
行列のランクの定義・例・性質/公式 (証明付) - 理数アラカルト -

定理.

任意の行列 $A,B$ に対して、
$\mathrm{rank}(A\otimes B) = \mathrm{rank}(A)\mathrm{rank}(B)$
証明.
$\mathrm{rank}(A) = r, \mathrm{rank}(B) = s$ とする。
行列 $A,B$ を特異値分解すると、
$A = U_A\Sigma_A V_A, B=U_B\Sigma_B V_B$
ここで、 $\Sigma_A$ は下みたいな感じの行列です。
$\Sigma_A = \begin{pmatrix} \sigma_{1} & & & & & \\ & \ddots & & & \huge{0} & \\ & & \sigma_{r} & & & \\ & & & 0 & & \\ & \huge{0} & & & \ddots & \\ & & & & & 0 \end{pmatrix}$
なんかずれてる・・・？たすけて。 $\sigma_1 , \cdots, \sigma_r$ は0でない $A$ の特異値です。また $U_A,V_A,U_B,V_B$ は直交行列（つまり正則行列でもある）です。

補題2より、 $U_A^{-1}\otimes U_B^{-1},\ V_A^{-1}\otimes V_B^{-1}$ は正則行列であり、補題3より
$\mathrm{rank}(A\otimes B) = \mathrm{rank} ( (U_A^{-1}\otimes U_B^{-1})(A\otimes B)(V_A^{-1}\otimes V_B^{-1}) )$

ここで、補題1を使って、
$\begin{eqnarray} (U_A^{-1}\otimes U_B^{-1})(A\otimes B)(V_A^{-1}\otimes V_B^{-1}) &=& (U_A^{-1}A V_A^{-1}) \otimes (U_B^{-1} B V_B^{-1}) \\ &=& \Sigma_A \otimes \Sigma_B \\ &=& \begin{pmatrix} \sigma_{1}\Sigma_B & & & & & \\ & \ddots & & & \huge{0} & \\ & & \sigma_{r}\Sigma_B & & & \\ & & & 0 & & & \\ & \huge{0} & & & \ddots & \\ & & & & & 0 \end{pmatrix} \\ \end{eqnarray}$
この行列は、非零の対角成分が $rs$ 個でそれ以外の成分がすべて0の行列です。つまりランクは $rs$ です。
よって、
$\begin{eqnarray} \mathrm{rank}(A\otimes B) &=& \mathrm{rank} ( (U_A^{-1}\otimes U_B^{-1})(A\otimes B)(V_A^{-1}\otimes V_B^{-1}) ) \\ & = & rs \\ & = & \mathrm{rank}(A)\mathrm{rank}(B) \end{eqnarray}$