0
$\begingroup$

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 $$ ?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 19, 2021 at 19:14

1 Answer 1

2
$\begingroup$

@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)$.

$\endgroup$
10
  • $\begingroup$ 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)$$ ? $\endgroup$ Jul 20, 2021 at 9:16
  • $\begingroup$ @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. $\endgroup$ Jul 20, 2021 at 11:49
  • $\begingroup$ 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 ? $\endgroup$ Jul 20, 2021 at 13:09
  • $\begingroup$ Bit it fails no matter what $S_a$ is. $\endgroup$ Jul 20, 2021 at 13:46
  • 1
    $\begingroup$ If I understand you correctly now, you're basically asking if you can approximate a rank-3 matrix by a rank-1 matrix, and the answer is still no---a limit of rank 1 matrices is still rank 1. $\endgroup$ Jul 20, 2021 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.