# Kronecker-structured matrix kernel

Let $A,B\in\mathbb{C}^{n\times 3n}$ be two matrices, and denote the Kronecker matrix product by $\otimes$. The matrix $$M= \begin{bmatrix} A \otimes I_n \\\\ I_n \otimes B\end{bmatrix}$$ has size $2n^2 \times 3n^2$, therefore in the generic case its kernel has dimension $n^2$.

Is there a simple characterization of this kernel, or a way to compute it by exploiting this structure?

This problem comes from a numerical linear algebra problem (two-parameter eigenvalues problems). Do matrices with this structure appear in other fields, or do they ring a bell to you?

It looks appealing to look for vectors in this kernel in the form $v=a \otimes b \otimes c$, with $a,c\in\mathbb{C}^{n}$, $b\in\mathbb{C}^{3}$, since in this way they would be compatible with both Kronecker product structures. We normalize by restricting one entry of each of $a,b,c$ to be $1$, so we are left with $(n-1) + 2 + (n-1) = 2n$ unknowns. The condition $Mv=0$ is equivalent to $M(a\otimes b)=0$ and $N(b\otimes c)=0$, which are precisely $2n$ equations. So it looks like we should have several complex solutions in the generic case. Is there a viable way to compute them?

-
Isn't the relation $vec(ABC) = (C^T \otimes A) vec(B)$ helpful? –  Dirk Jan 24 '13 at 22:00
I tried playing with that relation, but I don't see how to put it to good use. Note that the block sizes in the two $\otimes$'s are different, so you can't use it to rewrite the two block rows as matrix products with the same format. –  Federico Poloni Jan 24 '13 at 22:18

Not an answer but too many equations for a comment: $\newcommand{\vec}{\mathrm{vec}}$ To compute an element $v\in\mathbb{R}^{3n^2}$ of the kernel of $$M = \begin{bmatrix} A\otimes I\\\\ I\otimes B\end{bmatrix}$$ we use the formula $\vec(ABC) = (C^T\otimes A)\vec(B)$ which holds whenever the products are defined.
Now we can write $v\in\mathbb{R}^{3n^2}$ as both $v=\vec(V)$ with $V\in\mathbb{R}^{n\times 3n}$ (stacking the $3n$ column vectors of length $n$ on top of each other) and $v= \vec(U)$ with $U\in\mathbb{R}^{3n\times n}$ (stacking the $n$ column vectors of length $3n$ on top of each other).
We write $$Mv = \begin{bmatrix} (A\otimes I)\vec(V)\\\\ (I\otimes B)\vec(U)\end{bmatrix} = \begin{bmatrix} \vec(VA^T)\\\\ \vec(BU)\end{bmatrix}.$$ Hence, the vectors $v=\vec(V)=\vec(U)$ in the kernel of $M$ are characterized by $$AV^T = 0,\qquad BU = 0.$$ Note that $V$ and $U$ are related by a reshape of their elements. Looks like this could be exloited algorithmically but I did not see yet how...