I found a thread that solved the problem I need to turn in (or confirmed that I had done it correctly) but doesn't really resolve some confusion I have regarding norms and inner products.
I need to show that the Frobenius norm obeys the general definition of a matrix norm, and only the triangle inequality is giving me any trouble, but that's been worked to death : Frobenius Norm Triangle Inequality
But I went about it somewhat differently and it's highlighted a few concepts I'm shaky on. Here is my approach:
Starting from the defintion
$$
||A||_F = \left( \sum^m_{i=1} \sum^n_{j=1} |A_{ij}|^2 \right)^{1/2}.
$$
Now consider
$$
||A+B||_F = \left( \sum^m_{i=1} \sum^n_{j=1} |A_{ij}+B_{ij}|^2 \right)^{1/2}.
$$
Noting that each element $A_{ij}, B_{ij}$ can be thought of as vectors in $\Re^2$, I can apply the good old fashioned triangle inequality to the square root of each summand
such that $|A_{ij}+B_{ij}|\leq |A_{ij}|+|B_{ij}|$
Squaring both sides gives me
$|A_{ij}+B_{ij}|^2\leq |A_{ij}|^2+|B_{ij}|^2 +2|A_{ij}||B_{ij}|$
I see that I'm on the right track, but I'm afraid I'm a bit stuck here.
If I sum over all elements, I get back
$||A+B||_F^2 \leq ||A||_F^2 + ||B||_F^2 + 2\sum^m_{i=1} \sum^n_{j=1}|A_{ij}||B_{ij}|$
Is my approach hopelessly flawed, or is there some way I can salvage this?
Best Answer
The Frobenius norm of a matrix is identical to the standard Euclidean norm of the vectorized version of the matrix. So, the triangle inequality for vectors directly implies the triangle inequality for the Frobenius norm for matrices.
Let $\text{vec}(\cdot)$ be the vectorization operator that takes a $n$-by-$m$ matrix and unfolds it into a long length $n \cdot m$ vector, stacking each column below the previous one. For example,
$$\text{vec}\left(\begin{bmatrix}1 & 3 \\ 2 & 4\end{bmatrix}\right) = \begin{bmatrix}1 \\ 2 \\ 3 \\ 4\end{bmatrix}.$$
Incidentally, this is how the matrix is actually stored in a computer's memory in many programing languages.
Then from the definitions one can see that $$||M||_\text{Fro} = ||\text{vec}(M)||,$$ where the second norm is the standard euclidean on vectors. In each case we sum the squares of all the entries and take the square root. Additionally, one can notice that $$\text{vec}(A + B) = \text{vec}(A) + \text{vec}(B)$$ because in each case you just add each entry in one object to the corresponding entry in the other.
Hence, \begin{align} ||A + B||_\text{Fro} &= ||\text{vec}(A+B)||\\ &= ||\text{vec}(A) + \text{vec}(B)|| \\ & \le ||\text{vec}(A)|| + ||\text{vec}(B)|| \\ & = ||A||_\text{Fro} + ||B||_\text{Fro}. \end{align} Going from the second line to the third, we used the triangle inequality for vectors.
Edit:
As requested, you can finish your proof (not involving vectorization) as follows. You're really close. So far in the unvectorized proof from the original question question, the proof has progressed to the following statement: $$||A+B||_F^2 \leq ||A||_F^2 + ||B||_F^2 + 2\sum_{ij}|A_{ij}||B_{ij}|$$
Applying the Cauchy-Schwarz inequality to the last term yields: $$\sum_{ij}|A_{ij}||B_{ij}| \le \left(\sum_{ij}|A_{ij}|^2\right)^{1/2}\left(\sum_{ij}|B_{ij}|^2\right)^{1/2} = ||A||_F ||B||_F.$$
Hence, $$||A+B||_F^2 \leq ||A||_F^2 + ||B||_F^2 + 2||A||_F ||B||_F.$$
Using the fact that $a^2 + b^2 + 2ab = (a + b)^2$, we get: $$||A+B||_F^2 \leq (||A||_F + ||B||_F)^2$$ which yields the desired triangle inequality after taking the square root of each side.