Relations between the second norms of matrices Consider two arbitrary complex matrices $L$ and $M$. Let $\|L\|_2 \le \|M\|_2$. Prove that
$$
        \Bigg\|\begin{bmatrix}
        I & 0 \\
        L & I \\
        \end{bmatrix}\Bigg\|_2 \le
        \Bigg\|\begin{bmatrix}
        I & 0 \\
        M & I \\
        \end{bmatrix}\Bigg\|_2
$$
My attempt was to reduce the problem. Namely, let $L = U\Sigma V^*$ be the SVD for $L$. Then it is easy to see that
$$
\begin{bmatrix}
I & 0 \\
L & I \\
\end{bmatrix}
\begin{bmatrix}
I & L^* \\
0 & I \\
\end{bmatrix} = 
\begin{bmatrix}
V & 0 \\
0 & U \\
\end{bmatrix}
\begin{bmatrix}
I & \Sigma \\
\Sigma & \Sigma^2 + I \\
\end{bmatrix}
\begin{bmatrix}
V^* & 0 \\
0 & U^* \\
\end{bmatrix}
$$
It means that the eigenvalues of $ \begin{bmatrix}
I & 0 \\
L & I \\
\end{bmatrix}
\begin{bmatrix}
I & L^* \\
0 & I \\
\end{bmatrix} $ and $ \begin{bmatrix}
I & 0 \\
\Sigma & I \\
\end{bmatrix}
\begin{bmatrix}
I & \Sigma \\
0 & I \\
\end{bmatrix} $ are equal, so the singlular values for $ \begin{bmatrix}
I & 0 \\
L & I \\
\end{bmatrix} $ and $ \begin{bmatrix}
I & 0 \\
\Sigma & I \\
\end{bmatrix} $.
It follows that it is sufficient to prove the statement for diagonal matrices with nonnegative values on the diagonal.
But here I got stuck. Thanks for any help or ideas!
 A: It is easier to use the property that norm in question is induced by the Euclidean vector norm than to use SVD. By considering the squared norms of the inequality in question, it suffices to show that for any two vectors $\mathbf x$ and $\mathbf y$, there exist two unit vectors $\mathbf u$ and $\mathbf v$ such that
$$
\|\mathbf x\|^2 + \|L\mathbf x+\mathbf y\|^2
\le\|x\mathbf u\|^2 + \|M(x\mathbf u)+y\mathbf v\|^2\tag{1}
$$
where $x=\|\mathbf x\|$ and $y=\|\mathbf y\|$. Note that
\begin{align}
\|\mathbf x\|^2 + \|L\mathbf x+\mathbf y\|^2
&\le\|\mathbf x\|^2 + (\|L\|\|\mathbf x\|+\|\mathbf y\|)^2\\
&\le\|x\mathbf u\|^2 + (\|M\|\|x\mathbf u\|+\|y\mathbf v\|)^2.\tag{2}
\end{align}
So, if you can find two unit vectors $\mathbf u$ and $\mathbf v$ such that
$$
\|M\|\|x\mathbf u\|+\|y\mathbf v\|=\|M(x\mathbf u)+y\mathbf v\|,\tag{3}
$$
then you are done. But the choices of $\mathbf u$ and $\mathbf v$ should be obvious...
A: I will handle only the square matrix case here.  The other cases are similar, but require some care.
Let's reframe the question: if $L$ and $M$ are such that the largest singular values satisfy $\sigma_1(L) \geq \sigma_1(M)$, then (it suffices to show that) the diagonal matrices $\Sigma_M,\Sigma_N$ of singular values are such that the largest eigenvalue of 
$
\pmatrix{I & \Sigma_L \\
\Sigma_L & \Sigma_L^2 + I}
$
is greater than the largest eigenvalue of 
$
\pmatrix{I & \Sigma_M \\
\Sigma_M & \Sigma_M^2 + I}
$
To that end, suppose $\Sigma$ is a matrix with diagonal entries $\sigma_1 \geq \cdots \geq \sigma_n$.  Let 
$$
A = \pmatrix{I & \Sigma \\
\Sigma & \Sigma^2 + I} = I + 
\pmatrix{0 & \Sigma \\
\Sigma & \Sigma^2}
$$
Now, apply a permutation matrix similarity.  We reach the block-diagonal matrix given by
$$
PAP^* = I + 
\pmatrix{B_1 \\ & B_2 \\ && \ddots \\ &&& B_n}
$$
where $B_i =\left[\begin{smallmatrix}0&\sigma_i\\ \sigma_i & \sigma_i^2\end{smallmatrix}\right]$.
Each block of this has the characteristic equation $\lambda^2 - \sigma_i^2\lambda - \sigma_i^2$.  It follows that the eigenvalues of $B_i$ are 
$$
\lambda = \frac{\sigma_i^2 \pm \sqrt{\sigma_i^4 + 4\sigma_i^2}}{2} = 
\frac{\sigma_i^2 \pm \sigma_i\sqrt{\sigma_i^2 + 4}}{2}
$$
So, the largest eigenvalue of $A$ is $1 + \frac 12\left(\sigma_1^2 + \sigma_1\sqrt{\sigma_1^2 + 4}\right)$.  Now, it suffices to note that if $\sigma_1(L) \geq \sigma_1(M)$, then
$$
1 + \frac 12\left(\sigma_1^2(L) + \sigma_1(L)\sqrt{\sigma_1^2(L) + 4}\right) \geq
1 + \frac 12\left(\sigma_1^2(M) + \sigma_1(M)\sqrt{\sigma_1^2(M) + 4}\right)
$$
