Nontrivial lower bound on the sum of matrix norms

Question

Let $X, V\in\mathbb{R}^{n\times r}$ such that $X^\top V$ is symmetric. The central quantity I care about is \begin{equation} \|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2. \end{equation} An easy lower bound for this quantity is given by $2\sigma_{r}(X)^2\|V\|_{F}^2$, where $\sigma_{r}(X)$ is the smallest singular value of $X$.

I'm wondering whether there exists some absolute constant $c>0$ such that the following holds \begin{equation} \|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2\geq c\|X\|_{F}^2\|V\|_{F}^2. \end{equation}

Answer 1

No. With $n = r = 2$, set $$X = \bigg(\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \bigg) \, , \quad V = \bigg( \begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \bigg) \, .$$ In particular, $X^T V = V^T X = 0$, the zero matrix.

If you restrict to invertible square matrices, the statement is still false. Set $$X = \bigg(\begin{array}{cc} 1 & 0 \\ 0 & \epsilon \end{array} \bigg) \, , \quad V = \bigg( \begin{array}{cc} \epsilon & 0 \\ 0 & 1 \end{array} \bigg) \, .$$ Then $X^T V = V^T X = \epsilon \operatorname{Id}$ and $\operatorname{Tr}(X^T V) = 2 \epsilon$. So, your LHS is $$ 2 \| \epsilon \operatorname{Id}\|_F^2 + (\operatorname{Tr}(\epsilon \operatorname{Id}))^2 = 8 \epsilon^2 \, , $$ which can be made arbitrarily small, while your RHS is $$ c \| X \|_F^2 \| V \|_F^2 = c (1 + \epsilon^2)^2 \geq c $$

The moral of the story is that the matrix norm is submultiplicative (not the Frobenius norm as above, but bear with me) in the sense that $\| X V \|$ can be arbitrarily smaller than $\| X \| \| V \|$. In the end, your constant $c$ depends either on how $X, V$ map each others singular value spaces to each other, or on some lower bound on the lowest singular value for either $X$ or $V$.

Answer 2

Let function $f : \mathbb R^{m \times n} \to \mathbb R_0^+$ be defined as follows

$$f (\mathrm X) := \| \,\mathrm X \mathrm A^\top \|_\text{F}^2 + \| \,\mathrm X^\top \mathrm A \,\|_\text{F}^2 + \left( \langle \mathrm A, \mathrm X \rangle \right)^2$$

where $\mathrm A \in \mathbb R^{m \times n}$ is given. Note that

$$\| \,\mathrm X \mathrm A^\top \|_\text{F}^2 = \| \,\mathrm A \mathrm X^\top \|_\text{F}^2 \geq \lambda_n ( \mathrm A^\top \mathrm A ) \, \| \mathrm X \|_\text{F}^2$$

$$\| \mathrm X^\top \mathrm A \|_\text{F}^2 = \| \mathrm A^\top \mathrm X \|_\text{F}^2 \geq \lambda_m ( \,\mathrm A \mathrm A^\top ) \, \| \mathrm X \|_\text{F}^2$$

and that $\left( \langle \mathrm A, \mathrm X \rangle \right)^2 \geq 0$. Hence,

$$f (\mathrm X) \geq \left( \lambda_n ( \mathrm A^\top \mathrm A ) + \lambda_m ( \,\mathrm A \mathrm A^\top ) \right) \| \mathrm X \|_\text{F}^2$$

Suppose that $\rm A$ is tall (i.e., $m > n$) and has full column rank (i.e., $\mbox{rank} (\mathrm A) = n$). In this case,

$$\lambda_n ( \mathrm A^\top \mathrm A ) = \sigma_n^2 (\mathrm A) = \left( \frac{\| \mathrm A \|_2}{\kappa (\mathrm A)} \right)^2$$

where $\kappa (\mathrm A)$ is the (finite) condition number of $\rm A$, and $\lambda_m ( \,\mathrm A \mathrm A^\top ) = 0$. Thus,

$$f (\mathrm X) \geq \left( \frac{1}{\kappa (\mathrm A)} \right)^2 \| \mathrm A \|_2^2 \, \| \mathrm X \|_\text{F}^2$$

Since

$$\| \mathrm A \|_\text{F} \leq \sqrt{\mbox{rank} (\mathrm A)} \, \| \mathrm A \|_2 = \sqrt{n} \, \| \mathrm A \|_2$$

we obtain

$$f (\mathrm X) \geq \underbrace{\frac 1n \left( \frac{1}{\kappa (\mathrm A)} \right)^2}_{=: c (\mathrm A)} \| \mathrm A \|_\text{F}^2 \, \| \mathrm X \|_\text{F}^2$$

where $c$ is a function of matrix $\rm A$.