Return to Question

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 (i.e. with $m=n$), 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?

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?

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 (i.e. with $m=n$), 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$.

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 (i.e. with $m=n$), 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?

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\}?$$

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 (i.e. with $m=n$), 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$.

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 (i.e. with $m=n$), 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$.