3
$\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
    $\begingroup$ Whst if $AG=0$? $\endgroup$ – Fedor Petrov Nov 17 '16 at 11:16
  • $\begingroup$ @FedorPetrov good point! May be the inequality is not correct, then. $\endgroup$ – Let's talk math Nov 17 '16 at 11:22
  • 1
    $\begingroup$ the Frobenius norm is submultiplicative, so the inequality is $\leq$ instead of $\geq$ $\endgroup$ – Carlo Beenakker Nov 17 '16 at 11:22
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$
  • $\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$ – Rodrigo de Azevedo Nov 18 '16 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$ – Federico Poloni Nov 18 '16 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
    $\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$ – Federico Poloni Nov 18 '16 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$ – Federico Poloni Nov 18 '16 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, privacy policy and cookie policy

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