# Smallest singular value of $X\mapsto AX^{T}+XA^{T}$

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?

• What do you mean by $\parallel \;. \;\parallel_F$? – Ali Taghavi Aug 24 '17 at 19:16
• It would be strange if the rectangular case were easier than the square one... – Federico Poloni Aug 24 '17 at 19:32
• Is X the same size as A? – Min-Oo Aug 24 '17 at 19:42
• @AliTaghavi I mean the Frobenius norm. I've edited the question accordingly. – Richard Zhang Aug 24 '17 at 20:37
• @AliTaghavi, you're absolutely right. The square case is not interesting. Instead, consider the long-and-skinny case $n\ll m$. Where $n=1$, the minimum is certainly not zero. – Richard Zhang Aug 24 '17 at 20:48

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$.