Matrices that are > 1 in a sense - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T10:44:24Z http://mathoverflow.net/feeds/question/109612 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109612/matrices-that-are-1-in-a-sense Matrices that are > 1 in a sense YKY 2012-10-14T13:53:25Z 2012-12-06T22:02:38Z <p>How can I characterize the class of square matrices such that: $||MN||_F \ge ||M||_F$?</p> <p>In other words, when multiplied, they always give "bigger" products.</p> <p>The norm is the Frobenius norm, which is the same as the Euclidean norm of the vectorization of the matrices.</p> <p><strong>Note:</strong> 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: <br/> $U \otimes V = vec(mat(U) \cdot mat(V))$</p> <p><strong>Note:</strong> the Frobenius norm can be defined $||M|| = \sqrt{trace M^\ast M}$, so what we want is: <br/> $tr (MN)^\ast (MN) \ge tr M^\ast M$ <br/> $tr N^\ast M^\ast M N \ge tr M^\ast M$ <br/> $tr M^\ast M N N^\ast \ge tr M^\ast M$ <br/> $tr N N^\ast M^\ast M \ge tr M^\ast M$ <br/> using the cyclic property of trace.</p> <p><strong>Note:</strong> the Frobenius norm is also the $\sqrt{\mbox{sum of squares of entries}}$. So the requirement can also be spelled out as: <br/> $\sqrt{ \sum_{ij} (\sum_k m_{ik} n_{kj})^2 } \ge \sqrt{ \sum_{ij} m_{ij}^2 }$ <br/> $\sum_{ij} (\sum_k m_{ik} n_{kj})^2 \ge \sum_{ij} m_{ij}^2$</p> <p>But I don't know how to proceed further from this...</p> http://mathoverflow.net/questions/109612/matrices-that-are-1-in-a-sense/109861#109861 Answer by Niel de Beaudrap for Matrices that are > 1 in a sense Niel de Beaudrap 2012-10-16T23:27:24Z 2012-11-07T20:31:26Z <p>$\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).</p> <p>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 \;&amp;=\;\tr(MN N^\ast M^\ast) \;=\;\tr(N^\ast M^\ast MN) \\&amp;= \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) \\&amp;= \;\sum_j s_j^2 \tr\left( N^\ast \vec r_j^{\phantom \ast} \vec r_j^\ast N \right) \\&amp;= \;\sum_j s_j^2 \tr\left( \vec r_j^\ast N N^\ast \vec r_j^{\phantom \ast} \right) \\&amp;= \;\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).</p> <p>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 &mdash; 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 \| &lt; 1$.</p> <p>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</p> <p>$$\Bigl\| N^{-1} \Bigr\|_\infty \leqslant\; 1\;,$$ where $\| \ast \|_\infty$ is the <em>uniform norm</em> on operators: $$\| A \|_\infty = \sup\; \Bigl\{ \| A \vec v \| \;:\; \vec v \in \mathop{\mathrm{dom}}(A) \text{ and } \|\vec v\| = 1 \Bigr\}.$$</p> <p>(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$.</p>