4
$\begingroup$

Let $A$ be a generic (or varying) square, real $ n \times n$ matrix. Let $G$ be a fixed $n \times k$ matrix, $k < n.$ Denote by $||.||_F$ the Frobenius norm.

Is it true that $||AG||_F \geq c(G) ||A||$, where $c(G)$ is a positive constant only depending on the matrix $G?$

P.S. I tend to think this is true when none of the elements of $G$ is zero, so that a minimum modulus of the elements of $G$ exists.

Thanks in advance!

$\endgroup$
3
  • 3
    $\begingroup$ Whst if $AG=0$? $\endgroup$ Nov 17, 2016 at 11:16
  • $\begingroup$ @FedorPetrov good point! May be the inequality is not correct, then. $\endgroup$ Nov 17, 2016 at 11:22
  • 1
    $\begingroup$ the Frobenius norm is submultiplicative, so the inequality is $\leq$ instead of $\geq$ $\endgroup$ Nov 17, 2016 at 11:22

3 Answers 3

7
$\begingroup$

For a short fat matrix $G$ (more columns than rows), $\|AG\|_F \geq \sigma_{\min}(G)\|A\|_F \geq n \sigma_{\min}(G) \|A\|$, where $\sigma_{\min}(G)$ is the least singular value of $G$. This follows from the fact that $\|G^*v\|\geq \sigma_{\min}(G^*)\|v\| = \sigma_{\min}(G)\|v\|$ for every vector $v$, applied to the rows of $A$.

However, if $G$ is tall thin (more rows than columns), then there is always a vector $w$ such that $w^*G=0$, because its rows are too many to be linearly independent. Hence $AG$ can be zero for a nonzero $A$, and there is no bound of the kind that you want.

$\endgroup$
2
  • $\begingroup$ Doesn't the inequality $$\|AG\|_F \geq \sigma_{\min}(G) \|A\|_F \geq n \, \sigma_{\min}(G) \|A\|$$ always hold? However, $\sigma_{\min}(G) > 0$ only if $G$ has full row rank. $G$ being fat does not imply it has full row rank. $\endgroup$ Nov 18, 2016 at 12:02
  • $\begingroup$ @RodrigodeAzevedo It might be the case that we have different definitions of singular values. With my definition, $\begin{bmatrix}1\\0\end{bmatrix}$ has one singular value $1$, and for $A=\begin{bmatrix}0&1\end{bmatrix}$ one has $0 = \|AG\|_F$ but $\sigma_{\min}(G)\|A\|_F=1.$ $\endgroup$ Nov 18, 2016 at 13:35
5
$\begingroup$

Given $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm B \in \mathbb R^{n \times p}$, let $\mathrm B \mathrm B^{\top} = \mathrm Q \Lambda \mathrm Q^{\top}$ be an eigendecomposition of $\mathrm B \mathrm B^{\top}$. Hence,

$$\begin{array}{rl} \| \mathrm A \mathrm B \|_{\text{F}}^2 &= \mbox{tr} (\mathrm A \mathrm B \mathrm B^{\top} \mathrm A^{\top})\\ &= \mbox{tr} (\mathrm A \mathrm Q \Lambda \mathrm Q^{\top} \mathrm A^{\top})\\ &= \mbox{tr} (\mathrm A \mathrm Q \Lambda (\mathrm A \mathrm Q)^{\top})\\ &\geq \lambda_{\min} (\mathrm B \mathrm B^{\top}) \, \mbox{tr} (\mathrm A \mathrm Q \mathrm Q^{\top} \mathrm A^{\top})\\ &= \lambda_{\min} (\mathrm B \mathrm B^{\top}) \, \mbox{tr} (\mathrm A \mathrm A^{\top})\\ &= \lambda_{\min} (\mathrm B \mathrm B^{\top}) \, \| \mathrm A \|_{\text{F}}^2\end{array}$$

Thus,

$$\| \mathrm A \mathrm B \|_{\text{F}} \geq \sqrt{\lambda_{\min} (\mathrm B \mathrm B^{\top})} \, \| \mathrm A \|_{\text{F}}$$

If $\mathrm B$ has full row rank, then $\sqrt{\lambda_{\min} (\mathrm B \mathrm B^{\top})} > 0$. Note that $\mathrm B$ can only have full row rank if it is square or fat. Thus, $p \geq n$ is necessary (though not sufficient).


Addendum

Given $\mathrm V \in \mathbb R^{m \times n}$ and $\Lambda := \mbox{diag} (\lambda_1, \dots, \lambda_n) \in \mathbb R^{n \times n}$, note that

$$\mbox{tr} (\mathrm V \Lambda \mathrm V^{\top}) = \mbox{tr} \left( \sum_{i=1}^n \lambda_i \mathrm v_i \mathrm v_i^{\top} \right) = \sum_{i=1}^n \lambda_i \| \mathrm v_i \|_2^2 \geq \min\{\lambda_1, \dots, \lambda_n\} \underbrace{\sum_{i=1}^n \| \mathrm v_i \|_2^2}_{= \| \mathrm V \|_{\text{F}}^2}$$

$\endgroup$
2
  • 2
    $\begingroup$ We are indeed saying the same thing. At least with my definition, $B$ has $\min(n,p)$ singular values, and the eigenvalues of $BB^T$ are the squares of the singular values of $B$, plus $n-p$ zeros if $n\geq p$. $\endgroup$ Nov 18, 2016 at 14:14
  • 2
    $\begingroup$ A short fat matrix $B$ has full row rank if and only if $\sigma_{\min}(B)>0$, so also from the criterion in my answer one can obtain that the positive constant $c(G)$ that OP asks about exists and is positive iff $B$ has full row rank. I agree with you that your answer makes the role of full row rank clearer, though. $\endgroup$ Nov 18, 2016 at 14:19
5
$\begingroup$

As stated$^*$ this problem has nothing to do with the Frobenius norm. The map $T: A \mapsto AG$ is a linear transformation from a finite-dimensional vector space, so for any norms we have a constant $c>0$ such that $\|AG\| \geq c \|A\|$ for all $A$, provided $T$ is injective (and if $T$ is not injective then of course any nonzero $A \in \ker T$ will give a counterexample). This is thanks to the standard compactness argument for equivalence of all norms on a finite-dimensional real or complex vector space.

(*) "As stated" $=$ if we care only about the existence of some positive $c$, not its size and its dependence on $G$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.