MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 4 Replaced all references with the 2-norm by Frobenius norm.

$\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 $M$ such that $\forall M: \| MN \|_2 |_F \geqslant \| M \|_2~$(where |_F~$(where $\|\ast\|_2$ \|\ast\|_F$ is the Frobenius norm, i.e. the 2-operator 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 \|_2^2 |_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 \|_2^2 |_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\|_2^2 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 \|_2^2$ |_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 \|_2 |_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 \|_2 |_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$.
show/hide this revision's text 3 Fixed typo

$\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 $M$ such that $\forall M: \| MN \|_2 \geqslant \| M \|_2~$(where $\|\ast\|_2$ is the Frobenius norm, i.e. the 2-operator 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 \|_2^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 \|_2^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\|_2^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 \|_2^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 \|_2 \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 \|_2 = 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 left-singular right-singular vectors of any matrix $M$.
show/hide this revision's text 2 Revised to answer the question for right-multiplication, and to work more directly with singular vectors

$\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 $M$ such that $\forall NM: \| MN \|_2 \geqslant \| N M \|_2~$(where $\|\ast\|_2$ is the Frobenius norm, i.e. the 2-operator norm).

I will generally consider the squares of the Frobenius norm, as the inequality is preserved under squaring. Consider an operator $N$ M$ with singular value decomposition $$ N M = \sum_j s_j \; \vec q_j \vec r_j^\ast \;,$$Then the Frobenius norm of $N$ M$ is just the Euclidean norm of the vector $\vec s$ of singular values, by$$ \| N M \|_2^2 \;=\;\tr(N N^\ast;=\;\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 \;.$$$$\begin{align*} \| MN \|_2^2 \;&=\;\tr(MN N^\ast M^\ast) \;=\;\tr(N^\ast M^\ast MN)\\&= \sum_j \sum_k s_j s_k \tr\left( M N^\ast \vec q_j^{\phantom r_j^{\phantom \ast} \vec r_j^\ast q_j^\ast \vec r_k^{\phantom q_k^{\phantom \ast} \vec q_k^\ast M^\ast r_k^\ast N \right)\\&= \;\sum_j s_j^2 \tr\left( M N^\ast \vec q_j^{\phantom r_j^{\phantom \ast} \vec q_j^\ast M^\ast r_j^\ast N \right) \\&= \;\sum_j s_j^2 \tr\left( \vec q_j^\ast M^\ast M r_j^\ast N N^\ast \vec q_j^{\phantom r_j^{\phantom \ast} \right)\\&= \;\sum_j s_j^2 \bigl\| M N^\ast \vec q_j^{\phantom r_j^{\phantom \ast} \bigr\|_2^2using the cyclic property of the trace on the second and second-to-last linelines, 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 $\| N M \|_2^2$ no matter what the left-singular right-singular vectors $\vec q_j$ 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 $N$ M$ is a rank one operator); so we may as well reduce to that special case — we require $\| M N^\ast \vec q r \|_2 \geqslant 1$ for all unit vectors $\vec q$r$. This 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 $\ker(M) = 0$; as c_n$ must be at least $M$ is square1$; otherwise, this implies that we would have $M$ is invertible\| N^\ast \vec b_n \|_2 = c_n \| \vec a_n \| < 1$.If

We have almost shown what was stated in the norms of every vector remain comments. Note that we can easily obtain the same or grow under action by singular value decomposition of $M$, 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 they the singular values of $N$ must shrink or remain also be at least $1$. Also, because all of the same with singular values of $M^{-1}$; that isN$ 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\| M^{-1N^{-1} \Bigr\|_\infty \leqslant\; 1\;, $$

(For operators on finite-dimensional vector spaces, the supremum can be replaced with a maximum.)

If we consider maximum; then the uniform norm is essentially the largest singular value decomposition of $M^{-1}$, it by definition.) This is easy just another way to show that this holds if formulate the criterion, and only if (because the largest singular value of $M^{-1}$ uniform norm is at a useful operator norm in its own right) possibly the most $1$. Then we can use this useful way to show present it succinctly. It is easy to see that the minimum singular value of $M$ must be at leastN$ being invertible and $1$. However\| N^{-1} \|_\infty \leqslant 1$ are both necessary and sufficient conditions: if $N^{-1}$ shrinks all vectors, I personally would be content with characterizing the suitable values of then $M$ by N$ stretches all vectors, and in particular the uniform norm on left-singular vectors of any matrix $M^{-1}$ as above.M$.
show/hide this revision's text 1