# Nontrivial lower bound on the sum of matrix norms

Let $X, V\in\mathbb{R}^{n\times r}$ such that $X^\top V$ is symmetric. The central quantity I care about is $$\|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2.$$ 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 $$\|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2\geq c\|X\|_{F}^2\|V\|_{F}^2.$$

• $\sigma_{r}(X)^2$ could be arbitrarily smaller than $\|X\|_{F}^2$. Commented Nov 18, 2017 at 22:46

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

• In the intervening years I learned a lot about this topic -- the potential for mismatch between $\| X V\|$ and $\| X \| \| V \|$ is a mechanism for cancellation in the estimation of Lyapunov exponents. See, e.g., the book of Duarte and Klein (Lyapunov Exponents of Linear Cocycles) and discussion therein on the "Avalanche principle". Commented Jul 7 at 18:03

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