Matrices that are > 1 in a sense

Question

How can I characterize the class of square matrices such that: $ ||MN||_F \ge ||M||_F $?

In other words, when multiplied, they always give "bigger" products.

The norm is the Frobenius norm, which is the same as the Euclidean norm of the vectorization of the matrices.

Note: if we recast this in vectors, we are asking for a class of vectors such that: $ || U \otimes V|| \ge ||V|| $ where $\otimes$ is the usual matrix product by turning the vectors into matrices and converting the result back to a vector. In other words, if vec means vectorization, and mat means matrixization, so $mat(X) = vec^{-1}(X)$, then:
$ U \otimes V = vec(mat(U) \cdot mat(V)) $

Note: the Frobenius norm can be defined $||M|| = \sqrt{trace M^\ast M}$, so what we want is:
$ tr (MN)^\ast (MN) \ge tr M^\ast M$
$ tr N^\ast M^\ast M N \ge tr M^\ast M$
$ tr M^\ast M N N^\ast \ge tr M^\ast M$
$ tr N N^\ast M^\ast M \ge tr M^\ast M$
using the cyclic property of trace.

Note: the Frobenius norm is also the $\sqrt{\mbox{sum of squares of entries}}$. So the requirement can also be spelled out as:
$ \sqrt{ \sum_{ij} (\sum_k m_{ik} n_{kj})^2 } \ge \sqrt{ \sum_{ij} m_{ij}^2 } $
$ \sum_{ij} (\sum_k m_{ik} n_{kj})^2 \ge \sum_{ij} m_{ij}^2 $

But I don't know how to proceed further from this...

Answer 1

$\def\vec#1{\mathbf{#1}}\def\tr{\mathop{\mathrm{tr}}}$ I'll develop the answer suggested in the comments for the sake of clarity. I'm assuming that you want conditions for $N$ such that $\forall M: \| MN \|_F \geqslant \| M \|_F~$(where $\|\ast\|_F$ is the Frobenius norm).

I will generally consider the squares of the Frobenius norm, as the inequality is preserved under squaring. Consider an operator $M$ with singular value decomposition $$ M = \sum_j s_j \; \vec q_j \vec r_j^\ast \;,$$ where $\vec q_j$ and $\vec r_j$ are the orthonormal sets of left- and right-singular vectors, and where the singular values are a decreasing sequence of non-negative reals, $s_1 \geqslant s_2 \geqslant \cdots \geqslant 0$. Then the Frobenius norm of $M$ is just the Euclidean norm of the vector $\vec s$ of singular values, by $$ \| M \|_F^2 \;=\;\tr(M M^\ast) = \tr\left( \sum_j \sum_k s_j s_k \; \vec q_j^{\phantom \ast} \vec r_j^\ast \vec r_k^{\phantom \ast} \vec q_k^\ast \right) = \;\sum_j s_j^2 \;.$$ Consider what happens when we multiply on the left by $M$: the square of the Frobenius norm is $$\begin{align*} \| MN \|_F^2 \;&=\;\tr(MN N^\ast M^\ast) \;=\;\tr(N^\ast M^\ast MN) \\\\&= \sum_j \sum_k s_j s_k \tr\left( N^\ast \vec r_j^{\phantom \ast} \vec q_j^\ast \vec q_k^{\phantom \ast} \vec r_k^\ast N \right) \\\\&= \;\sum_j s_j^2 \tr\left( N^\ast \vec r_j^{\phantom \ast} \vec r_j^\ast N \right) \\\\&= \;\sum_j s_j^2 \tr\left( \vec r_j^\ast N N^\ast \vec r_j^{\phantom \ast} \right) \\\\&= \;\sum_j s_j^2 \bigl\| N^\ast \vec r_j^{\phantom \ast} \bigr\|_F^2 \;,\end{align*}$$ using the cyclic property of the trace on the second and second-to-last lines, and the fact that the trace of a scalar is just the scalar itself (which happens in this case to be the inner product of a vector with itself, or the Euclidean-norm-square of that vector).

We want the value on the last line above to be larger than $\| M \|_F^2$ no matter what the right-singular vectors $\vec r_j$ happen to be, or what the singular values $s_j$ are. In particular, it must be larger even if $s_1$ is the only non-zero singular value (that is, even if $M$ is a rank one operator); so we may as well reduce to that special case — we require $\| N^\ast \vec r \|_F \geqslant 1$ for all unit vectors $\vec r$. If you consider the singular value decomposition of $N^\ast$, $$ N^\ast = \sum_k c_k \; \vec a_k \vec b_k^\ast \;,$$ this means in particular that the smallest singular value $c_n$ must be at least $1$; otherwise, we would have $\| N^\ast \vec b_n \|_F = c_n \| \vec a_n \| < 1$.

We have almost shown what was stated in the comments. Note that we can easily obtain the singular value decomposition of $N$ from that of $N^\ast$: $$ N = \left( \sum_k c_k\; \vec a_k \vec b_k^\ast \right)^\ast = \sum_k c_k\; \vec b_k \vec a_k^\ast \;;$$ then the singular values of $N$ must also be at least $1$. Also, because all of the singular values of $N$ are positive, it is invertible; and we can easily show $$ N^{-1} = \sum_k c_k^{-1} \;\vec a_k \vec b_k^\ast \;.$$ Then the maximum singular value of $N^{-1}$ is at most $1$, or equivalently

$$ \Bigl\| N^{-1} \Bigr\|_\infty \leqslant\; 1\;, $$ where $\| \ast \|_\infty$ is the uniform norm on operators: $$ \| A \|_\infty = \sup\; \Bigl\{ \| A \vec v \| \;:\; \vec v \in \mathop{\mathrm{dom}}(A) \text{ and } \|\vec v\| = 1 \Bigr\}. $$

(For operators on finite-dimensional vector spaces, the supremum can be replaced with a maximum; then the uniform norm is essentially the largest singular value by definition.) This is just another way to formulate the criterion, and (because the uniform norm is a useful operator norm in its own right) possibly the most useful way to present it succinctly. It is easy to see that $N$ being invertible and $\| N^{-1} \|_\infty \leqslant 1$ are both necessary and sufficient conditions: if $N^{-1}$ shrinks all vectors, then $N$ stretches all vectors, and in particular the right-singular vectors of any matrix $M$.