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...



Matrices that are > 1 in a sense
$\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$.


