Solvability of $A X B=C$ with $X=X^\mathrm{T}$

Question

I am studying symmetric solutions to the complex matrix equation \begin{equation} A X B=C, \end{equation} where $A$, $B$, and $C$ are $m\times n$, $n \times k$, and $m \times k$ complex matrices, respectively. We may further assume that these matrices are arbitrary random unstructured matrices (i.e., any submatrix of $A$, $B$, or $C$ is full-rank with probability 1). Furthermore, $X$ is the $n\times n$ matrix of unknowns, which is restricted to be symmetric (i.e., $X$=$X^\mathrm{T}$). I would like to find (and prove) a rule for obtaining the minimum $n$ that allows for a solution to this equation.

When trying to solve this problem by vectorizing, I reach a linear equation like \begin{equation} (B^\mathrm{T}\otimes A)\begin{bmatrix}Z_U+Z_D\end{bmatrix}v=\mathrm{vec}(C), \end{equation} where $Z_U$ and $Z_D$ are matrices selecting and permuting the elements of $(B^\mathrm{T}\otimes A)$ associated to the upper and lower triangular parts of $X$, respectively, and $v$ is the $n(n+1)/2$-sized vector of unique unknowns. We further know that $Z_D = K^{(n,n)}Z_U$, where $K^{(n,n)}$ is the respective conmutation matrix. What I have noticed is that the matrix $(B^\mathrm{T}\otimes A)\begin{bmatrix}Z_U+Z_D\end{bmatrix}$, and specifically $(B^\mathrm{T}\otimes A)(I+K^{(n,n)})$ where $I$ stands for identity matrix, may have rank lower than $mk$ even when $(B^\mathrm{T}\otimes A)$ has rank $mk$ (and $n(n+1)/2>mk$). I feel like there should be a way to predict how the rank of said product of matrices behaves, but I have failed to characterize it. We may also formulate this problem in terms of characterizing the right-invertibility of $(B^\mathrm{T}\otimes A)\begin{bmatrix}Z_U+Z_D\end{bmatrix}$.

Another empirical observation I noted is that, for the square case where $m=k$, the solvability of this equation is given by the simple rule $n=2m-1$, but I am not able to prove even this case.

Edit: When $\mathrm{rank}\left((B^\mathrm{T}\otimes A)\begin{bmatrix}Z_U+Z_D\end{bmatrix}\right)=mk$ the solution is trivially given by applying the pseudo-inverse $(.)^\dagger$ as $$v=\left((B^\mathrm{T}\otimes A)\begin{bmatrix}Z_U+Z_D\end{bmatrix}\right)^\dagger \mathrm{vec}(C),$$ and remapping $v$ to the symmetric matrix structure, but the question is about how to know if there is a solution or not. Specifically, about what values of $n$ assure solvability.

Edit 2: By empirical evaluation for the general case it seems that the solvability of this equation is given by the simple rule $n\geq m+k-1$. However, I would still like to find a formal proof to this rule, which I have failed to do so far.

Answer 1

Here $U^+$ denotes the Moore-Penrose inverse of $U$.

Assume that $A,B,C$ are generic; there exists a solution $U$ of $AU_{n,k}=C$ only if $AA^+C=C$.

This -generically- never happens unless $AA^+=I_m$, that is, when $n\geq m$. In the same way, there exists -generically- a solution $V$ of $V_{m,n}B=C$ only when $n\geq k$. In the sequel, we assume these 2 conditions are satisfied.

Consider the following example: $m=4,n=8,k=3$.

If we stack the matrices row by row, then $X\mapsto AXB$ is associated to the matrix $A\otimes B^T$. This last matrix has rank $mk=12$ and is surjective. The dimension of the affine space $R$ of all solutions of $AXB=C$ is $n^2-mk=8^2-12=52$. Now $S$ -the vector space of symmetric matrices- has dimension $n(n+1)/2=36$; -generically- the spaces $R,S$ (affine subspaces of $M_8$ of dimension $n^2=64$) are transverse. Finally, the space of symmetric solutions satisfies $dim(R\cap S)=dim(R)+dim(S)-dim(M_8)=n(n+1)/2-mk=24$.

Beware,if you want to be sure that there are symmetric solutions, then you have to assume $n(n+1)/2>mk$. For example, when $m=5,n=5,k=3$, generically there are no symmetric solutions.

$\textbf{EDIT 1}$ In fact, in addition to the conditions $n\geq m,n\geq k$,the condition $n(n+1)/2>mk$ is not sufficient. It seems that, as @Juan wrote above, that the good extra condition is $n\geq m+k-1$. For example:

$\bullet$ when $m=6,n=9,k=4$ ($n=m+k-1$), $dim(R\cap S)=n(n+1)/2-mk=21$.

$\bullet$ when $m=6,n=9,k=5$ ($n=m+k-2$), there are no symmetric solutions although $n(n+1)/2-mk=15$...

$\textbf{EDIT 2}$ $\textbf{Proposition.}$ Generically, there is a symmetric matrix solution if and only if $n\geq m,n\geq k,n\geq m+k-1$.

$\textbf{Proof.}$ $\bullet$ Assume that $m\leq k$.

Let $E_k=im(B)$ and $F_m$ be s.t. $\ker(A)_{n-m}\oplus F_m=\mathbb{C}^n$. $A$ is a bijection from $F_m$ to $im(C)$ and $X_{|E_k}$ is a fixed surjection onto $F_m$. Generically, $E_k$ anf $F_m$ are transverse.

If we want to extend $X_{|E_k}$ into a symmetric matrix $X$, then the submatrix associated with $X_{|E_k}$ must not cross (strictly) the diagonal of the large matrix reserved for $X$. Then $n\geq m+k-1$ and $dim(E_k\cap F_m)=1$ in the limit case (to see that, place the submatrix at the top right of the matrix reserved for $X$).

$\bullet$ If $k\leq m$, then note that $B^TXA^T=C^T$ admits a symmetric solution; the roles of $k,m$ are exchanged. Then we obtain again the condition $n\geq m+k-1$.

$\textbf{Conclusion.}$ If the above conditions are satisfied, then the set of symmetric solutions is an affine space of dimension $n(n+1)/2-mk$; otherwise, there are no symmetric solutions.

$\textbf{Answer to Juan's comment.}$ $\bullet$ If $n=m+k-1,m\leq k$ -for example $n=20,m=9,k=12$- then $dim(E_k\cap F_m)=1$ and that works.

Note that a symmetric matrix remains symmetric after a permutation of the elements of a basis. Thus we may assume that $e_1,\cdots,e_9$ is a basis of $F_m$ and $e_9,\cdots,e_{20}$ is a basis of $E_k$. The top right $9\times 12$ submatrix $S$ associated to $X_{|E_k}$ intersects the diagonal of $X$ only in $(9,9)$. Then we can complete the submatrix $S$ into a symmetric one.

$\bullet$ if $n=m+k-2,m\leq k$ -for example $n=20,m=10,k=12$- then $dim(E_k\cap F_m)=2$ and that doesn't work.

Here $e_1,\cdots,e_{10}$ is a basis of $F_m$. The top right $10\times 12$ submatrix $S$ intersects the diagonal in $(9,9)$ and $(10,10)$ and has an entry below the diagonal: $S_{10,9}$. Since, generically $S_{9,10}\not= S_{10,9}$, we cannot complete the submatrix into a symmetric one.