Writing a sparse matrix as a Kronecker product

Question

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.

Answer 1

The short answer is no, with the precise statement reading as follows:

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*}