Matrices that are > 1 in a sense

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

-
It looks like a semi-group, which contains the homotheties of ratio of absolute value at least one. – Julien Puydt Oct 14 '12 at 14:57
A normal matrix N is in this class iff all absolute values of its eigenvalues are at least 1. – jjcale Oct 14 '12 at 16:53
To complete jjcale's answer, for a matrix $N$, the condition $\forall M$, $\|MN\| \geq \|M\|$ is equivalent to "all singular values of $N$ are larger than or equal to $1$". – Mikael de la Salle Oct 14 '12 at 18:13
Someone noted that if M is a projection it may send N to 0, so MN = 0 with M,N non-zero, violating the inequality. Also, a projection is always positive definite. So we have a positive definite M that violates this. – YKY Oct 14 '12 at 18:50
There seems to be a quantifier missing from your question. Do you mean "the class of matrices $N$ such that for all $M$, we have $\Vert MN\Vert \geq \Vert M\Vert$?" If so, then I can't see what is wrong with Mikael's answer – Yemon Choi Oct 14 '12 at 22:15

$\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 \|_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$.

-
Just a nitpick: the Frobenius norm is not the operator 2-norm; the standard operator-2 norm is the largest singular value. – Suvrit Nov 6 '12 at 17:57
@Suvrit: good point. I'm used to dealing almost exclusively with normal operators, so the fact that they are not in fact equivalent in general had not occurred to me. I'll edit the answer. – Niel de Beaudrap Nov 7 '12 at 20:29
Even for normal operators the Frobenius norm and operator 2-norm are not the same. The operator 2-norm is (for normal or non-normal operators) the same as what you called the uniform norm. – Mark Meckes Nov 8 '12 at 14:13