Nearest Kronecker Product of a commutation matrix

Question

Given a commutation matrix $K$ of the size $n²$ by $n²$. How can I find matrix $A$ and $B$ both of the size $n$ by $n$ such that the equation below is (approximately) satisfied by finding its Nearest Kronecker Product.

$K = A ⊗ B$.

Answer 1

Write $A = \sum_{i,j} a_{ij}e_i e_j^T$, $B = \sum_{i,j} b_{ij}e_ie_j^T$.

First, we note that $$ K = A \otimes B \iff\\ K = \sum_{i,j,p,q} a_{ij}b_{pq} (e_ie_j^T) \otimes (e_pe_q^T) \iff\\ K = \sum_{i,j,p,q} a_{ij}b_{pq} (e_i \otimes e_p)(e_j \otimes e_q)^T \iff\\ \operatorname{vec}(K) = \sum_{i,j,p,q} a_{ij}b_{pq} (e_j \otimes e_q \otimes e_i \otimes e_p) \iff\\ P\operatorname{vec}(K) = \sum_{i,j,p,q} a_{ij}b_{pq} (e_j \otimes e_i \otimes e_q \otimes e_p) \iff\\ \operatorname{vec}^{-1}[P\operatorname{vec}(K)] = \sum_{i,j,p,q} a_{ij}b_{pq} (e_j \otimes e_i)(e_q \otimes e_p)^T \iff\\ \operatorname{vec}^{-1}[P\operatorname{vec}(K)] = \operatorname{vec}(A)\operatorname{vec}(B)^T $$ For the permutation matrix $P$ satisfying $$ P(u \otimes v \otimes x \otimes y) = u \otimes x \otimes v \otimes y. $$

The commutation matrix $K = K^{(n,n)}$ can be rewritten as $$ K = \sum_{i,j = 1}^n (e_i \otimes e_j)(e_j \otimes e_i)^T, $$ so that $$ \operatorname{vec}(K) = \sum_{i,j} e_j \otimes e_i \otimes e_i \otimes e_j \implies\\ P \operatorname{vec}(K) = \sum_{i,j} e_j \otimes e_i \otimes e_i \otimes e_j = \operatorname{vec}(K) \implies\\ \operatorname{vec}^{-1}(P\operatorname{vec}(K)) = K. $$ All together, we are looking for $A,B$ that give us the best (approximate) solution to $$ K = \operatorname{vec}(A) \operatorname{vec}(B)^T. $$ Because $K$ is an orthogonal matrix, the EYM theorem tells us that every rank-$1$ matrix with spectral norm $1$ is an equally good approximation for $K$. In other words, for every $A,B$ we have $$ \|K - A \otimes B\|_F^2 \geq n^2 - 1, $$ and $\geq$ can be replaced with $=$ if and only if $\sum_{i,j,p,q} a_{ij}^2 b_{pq}^2 = 1.$