# Writing a sparse matrix as a Kronecker product

Let $$\mathbf{x}=[x_1, x_2, x_3, x_4]^{\top}$$. I was given the following matrix: $$A= \begin{bmatrix} \mathbf{x}^{\top} & \mathbf{0}^{\top} & \mathbf{0}^{\top}\\ \mathbf{0}^{\top} & \mathbf{x}^{\top} & \mathbf{0}^{\top}\\ \mathbf{0}^{\top} & \mathbf{0}^{\top} & \mathbf{x}^{\top} \end{bmatrix}.$$ I can write it as $$A=I\otimes\mathbf{x}^{\top}$$ where $$\otimes$$ is the Kronecker product.

Now suppose I have some of coordinates in each row as follows: $$A= \begin{bmatrix} x_1 & x_3 & 0 & 0 & 0\\ 0 & 0 & x_4 & 0 & 0\\ 0 & 0 & 0 & x_2 & x_4\\ \end{bmatrix}.$$ Is there any way I can write the above as a Kronecker product of some matrices? Possibly define some matrices with 0 and 1 elements that are used to pick the coordinates.

• I don't see a way because your matrix does not preserve a block-matrix structure. May 2, 2023 at 14:41

The matrix $$A$$ can be written as $$B_1\otimes B_2$$ in a non-trivial way if and only if $$x_4=0$$ and $${\bf x}$$ has at most one non-zero entry.
Proof. "$$\Rightarrow$$": Recall that given $$B_1\in\mathbb R^{m_1\times n_1}$$, $$B_2\in\mathbb R^{m_2\times n_2}$$ their Kronecker product is an element of $$\mathbb R^{m_1m_2\times n_1n_2}$$. Thus if there'd exist $$B_1,B_2$$ such that $$A=B_1\otimes B_2$$, then the dimensions of $$B_1,B_2$$ have to satisfy $$m_1m_2=3$$ and $$n_1n_2=5$$. This system of equations has four solutions in $$\mathbb N\times\mathbb N$$:
• The trivial solutions $$(m_1,n_1)=(3,5)$$ and $$(m_2,n_2)=(1,1)$$ (or vice versa). The reason this is trivial is that it is just a scaling: one of the $$B$$'s (say, $$B_1$$) is a complex number $$B_1=b_1\in\mathbb C$$ so $$A=B_1\otimes B_2=b_1B_2$$.
• $$(m_1,n_1)=(3,1)$$ and $$(m_2,n_2)=(1,5)$$, that is, $$B_1$$ is a column vector and $$B_2$$ is a row vector (or vice versa). Then there is another constraint we have to take into account: the rank of matrices is multiplicative under $$\otimes$$ which implies $${\rm rank}(A)={\rm rank}(B_1\otimes B_2)={\rm rank}(B_1)\cdot{\rm rank}(B_2)\leq 1\cdot1=1\,.$$ But if the rank of $$A$$ does not exceed $$1$$, then $$x_4$$ has to be zero, and at most one of the other entries of $${\bf x}$$ can be non-zero.
"$$\Leftarrow$$": We can write down these decompositions explicitly: \begin{align*} \begin{pmatrix}x_1&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{pmatrix}&=\begin{pmatrix}x_1&0&0&0&0\end{pmatrix}\otimes\begin{pmatrix}1\\0\\0\end{pmatrix}\\ \begin{pmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&x_2&0\end{pmatrix}&=\begin{pmatrix}0&0&0&x_2&0\end{pmatrix}\otimes\begin{pmatrix}0\\0\\1\end{pmatrix}\\ \begin{pmatrix}0&x_3&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{pmatrix}&=\begin{pmatrix}0&x_3&0&0&0\end{pmatrix}\otimes\begin{pmatrix}1\\0\\0\end{pmatrix}\tag*{\square} \end{align*}