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!

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

3 Answers 3

Reset to default
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.

Improve this answer
$\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$
    – Rodrigo de Azevedo
    Commented 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$
    – Federico Poloni
    Commented 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}$$

Improve this answer
$\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$
    – Federico Poloni
    Commented 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$
    – Federico Poloni
    Commented 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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .