# submultiplicity of matrix norm. Is $||AB||_F \leq ||A||_2||B||_F$?

Let $||\cdot||_F$ and $||\cdot||_2$ be the Frobenius norm and the spectral norm.

I'm reading Ji-Guang Sun's paper 'Perturbation Bounds for the Cholesky and QR Factorizations' from BIT 31 in 1991. While deriving the perturbation bound on Cholesky factorization $A=LL^T$ with $A\in\mathbb{R}^{n\times k}$ of rank $k$, he begins with the perturbed matrix $A+E$ and its Cholesky factorization.

$A+E=(L+G)(L+G)^T$

Expanding the RHS and subtracting $A$ from both sides, we have $E = GL^T + LG^T + GG^T$. Then he claimed in (2.12) of his paper that

$||E||_F\leq 2||L||_2||G||_F + ||G||_F^2$.

If I read $||L||_F$ instead of $||L||_2$, everything seems perfectly normal to me by the following three properties of any matrix norm.

• $||X^T||=||X||$ for any matrix norm
• subadditivity: $||X+Y||_p\leq||X||_p + ||Y||_p$
• submultiplicity: $||XY||_p\leq ||X||_p\cdot||Y||_p$ for $p=2$ or $F$

But I'm not sure why $||L||$ is a spectral norm in this equation even though every other norms are Frobenius norms. Does $||XY||_F\leq ||X||_2||Y||_F$ always hold?

-
I don't know. Have you tried it with, say, some $2\times2$ examples? –  Gerry Myerson Mar 29 '11 at 3:00

This inequality is true. But let me first make a comment. When you say that any matrix norm is submultiplicative ($\|XY\|\le\|X\|\cdot\|Y\|$), you understate that a matrix norm over $M_n(\mathbb C)$ is subordinated to a norm of $\mathbb C^n$: $$\|A\|:=\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}.$$ But the Frobenius norm is not subordinated, for instance because $\|I_n\|_F=\sqrt{n}$, whereas $\|I_n\|=1$ for any matrix norm. The reason for which the Frobenius norm is submultiplicative is therefore specific to it; it is more or less a consequence of Cauchy--Schwarz inequality.
Now, back to your question. Both norms are unitarily invariant, in the sense that $\|UAV\|=\|A\|$ whenever $U$ and $V$ are unitary matrices. Therefore we may assume that $A$ is diagonal, with diagonal entries $a_1,\ldots,a_n$. Now, we have $\|A\|_2=\max_i|a_i|$ and therefore $$\|AB\|_F^2 = \sum |a_i b_{ij}|^2\le \|A\|_2^2 \sum |b_{ij}|^2 =\|A\|_2^2\|B\|_F^2.$$
By singular value decomposition, $A=U\Sigma V^T$ and $B=Z\Lambda W^T$ where $U,V,Z,W$ are orthonormal and $\Sigma=diag(a_1,...,a_n),\Lambda=diag(b_1,...,b_n)$ are diagonal. Then $||A||=||\Sigma||$ and $||B||=||\Lambda||$ as you pointed out. Your argument is based on the claim that $||AB||=||\Sigma\Lambda||$, but $||AB||=|||U\Sigma VZ\Lambda W||=||\Sigma VZ\Lambda||$. I'm afraid we cannot guarantee that $\Sigma VZ\Lambda$ is unitarily similar to $\Sigma\Lambda=diag(a_1b_1, ...,a_n b_n)$. –  Federico Magallanez Mar 30 '11 at 6:11
@Federico. I only use $$\|AB\|_F=\|U\Sigma V^TB\|_F=\|\Sigma V^TB\|_F\le\|\Sigma\|_2\|V^TB\|_F=\|A\|_2\|B\|_F.$$ –  Denis Serre Mar 30 '11 at 7:56
The general result is equivalent to the result for diagonal matrices (with positive entries), since this is what maximizes the LHS, given specified singular values for $X, Y.$ I leave that case up to OP.