**Question:** Given the long and skinny matrix $A\in\mathbb{R}^{m\times n}$ with $m\ge n$, define the matrix valued operator


$$\mathcal{A}:X\mapsto AX^{T}+XA^{T}.$$


What is the tightest nontrivial lower-bound on the singular value


$$\sigma\_{\min}(\mathcal{A})\triangleq\min\_{X}\{\|\mathcal{A}(X)\|\_{F}:\|X\|\_{F}=1\},$$


where $\|X\|\_{F}^{2}=\mathrm{trace}(X^{T}X)$ is the usual matrix Euclidean norm (i.e. Frobenius norm)?


*Remark 1.* In the case that $A=a$ is a vector (i.e. with $n=1$), it is easy to show that $\sigma\_{\min}(\mathcal{A})=\sqrt{2}\|a\|$, since $\|ax^{T}+xa^{T}\|^{2}=2\|a\|^{2}\|x\|^{2}+2(a^{T}x)^{2}$, and the term $(a^{T}x)^{2}$ is obviously nonnegative. However in the general matrix case, we have $\|AX^{T}+XA^{T}\|^{2}=2\|AX^{T}\|\_{F}^{2}+2\mathrm{trace}[(A^{T}X)^{2}]$, and it appears possible for $\mathrm{trace}[(A^{T}X)^{2}]$ to be negative. 


*Remark 2.* In the case that $A$ is square and that $X$ is forced to be symmetric, this problem is closely related to the smallest singular value of the Lyapunov operator $A\otimes I+I\otimes A$, which is known to be related (in a fairly complicated way) to the singular values of $P$, where $P$ solves $AP+PA^{T}=I$.


**Edit 1.** Federico Poloni remarked that the rectangular case should not be easier than the square one. Agreed. In this case, consider where $n$ is very small, say 1 or 2, or at least $n\ll m/2,$ so that $\mathcal{A}(X)$ can be considered low-rank. As mentioned above, the $n=1$ case has an exact solution. Can tight bounds be derived for $n$ small? 



Smallest singular value of $X\mapsto AX^{T}+XA^{T}$
There is always a zero singular value as soon as $n \geq 2$.


Write $A = UD V$ with $D$ diagonal and $U, V$ orthogonal. Then we can write $X \mapsto AX^T + X A^T$ as $$X \mapsto UDV X^T + X V^T D^T U^T = U(D (U^T X V^T)^T + (U^T X V^T) D^T ) U^T$$ i.e. the composition of the operation $X \mapsto D X^T + X D^T$ with two orthogonal operatorions. So we may assume $A=D$ is diagonal 


By performing singular value decomposition on $A$, we may assume that $A$ is diagonal. Say the first two entries are $\lambda\_1,\lambda\_2$. Then $\begin{pmatrix} 0 & -\lambda\_1 \\ \lambda\_2 & 0 \end{pmatrix}$, padded with zero entries, is sent to zero. 


Of course if $\lambda\_1 = \lambda\_2=0$, then any $2 \times 2$ matrix is sent to $0$.


The remaining singular values are either $\sqrt{2}$ times a singular value of $A$, the square root of twice the sum of the squares of two different singular values of $X$, or twice a singular value of $A$.


