# Can I rewrite this expression as a Kronecker product?

Let $$M$$ be a symmetric positive definite matrix, and let $$a > 0$$ be a given constant. Let $$\text{vec}(\cdot)$$ denote the operator that stacks vertically the columns of a $$d \times d$$ matrix into a $$d^2 \times 1$$ vector. Does there exists a matrix $$S$$ such that

$$\text{vec}(M) \text{vec}(M)^{\top} + a \, (M \otimes M) = S \otimes S$$ ?

• No such $S$ exists even if $d = 2$ and $M = I$ is the identity matrix. A necessary criterion for the existence of such an $S$ is that each block of the matrix you wrote on the left-hand-side is a multiple of each other, and that criterion fails in this case. Jul 19 '21 at 19:14

@Nathaniel Johnston already answered in comments. On a more general note, detecting whether a matrix is a sum of $$r$$ Kronecker products is essentially the same problem (up to a permutation of the entries) as determining whether a matrix has rank $$r$$.
Indeed, given a matrix $$M\in\mathbb{F}^{am \times bn}$$ (divided into blocks $$M_{ij}$$ each of size $$m\times n$$), rearrange its entries to form a matrix $$N\in\mathbb{F}^{mn \times ab}$$ such that each column of $$N$$ is the vectorization of a block $$M_{ij}$$; then a rank-$$r$$ decomposition of $$N = u_1 v_1^T + \dots + u_r v_r^T$$ corresponds to a decomposition of $$M$$ as sum of $$r$$ Kronecker products $$M = \operatorname{vec}^{-1}(v_1) \otimes \operatorname{vec}^{-1}(u_1) + \dots + M = \operatorname{vec}^{-1}(v_r) \otimes \operatorname{vec}^{-1}(u_r)$$.
• What if $a\to \infty$. Can we find a matrix $S_a$ such that $$\text{vec}(M) \text{vec}(M)^{\top} + a (M \otimes M) = a \, (S_a \otimes S_a)$$ ? Jul 20 '21 at 9:16
• @FrédéricOuimet - I'm not sure what would qualify as an answer as $a \rightarrow \infty$ really, but this fails for every single $a > 0$ for the exact same reason that has been given. The term on the right has "rank" (in a slightly unusual sense) 1, while the term on the left has "rank" at least 3. Jul 20 '21 at 11:49
• it means, does it hold asymptotically as $a \to \infty$. We could have $S_a = M + a^{-1/2} \text{*** something ***} + O(a^{-1})$. No ? Jul 20 '21 at 13:09
• Bit it fails no matter what $S_a$ is. Jul 20 '21 at 13:46