A matrix norm inequality Given a real $m\times n$ matrix $C$, a $m\times m$ diagonal matrix $p$ whose diagonal entries $p_{ii}$ are either 0 or 1, and a $n\times n$ diagonal matrix $q$ whose diagonal entries $q_{ii}$ are either 0 or 1.
Let $P(\alpha)=\frac{\exp(i\alpha)}{2}p + \frac{I-p}{2}$, a diagonal matrix whose diagonal elements are either $1/2$ or $\exp(i\alpha)/2$.
Let $Q(\alpha)=\frac{\exp(i\alpha)}{2}q + \frac{I-q}{2}$, a diagonal matrix whose diagonal elements are either $1/2$ or $\exp(i\alpha)/2$.
Then we can construct the function
$$n(\alpha)=\frac{\|P(\alpha) C + C Q(\alpha)\|}{\|C\|}$$
where the norm is the operator norm.
The figure below shows all possible $n(\alpha)$ curves for a $7\times 7$ matrix $C$.

We are interested in the behaviour of $n(\alpha)$ for $\alpha\in[0,\pi]$.
We can prove easily that $n(\alpha)\leq 1$:
$$\frac{\|P(\alpha) C + C Q(\alpha)\|}{\|C\|}\leq \frac{\|P(\alpha) C \|+\| C Q(\alpha)\|}{\|C\|}\leq \frac{\|P(\alpha)\|\| C \|+\| C \|\|Q(\alpha)\|}{\|C\|}\\
\leq \frac{\frac{1}{2}\| C \|+\| C \|\frac{1}{2}}{\|C\|} \leq 1$$
In the case where $P(\alpha)=I/2$, we can easily prove that $n(\alpha)$ is a nonincreasing function of $\alpha$:
$$n(\alpha+\delta_{\alpha})=\frac{\|C/2 + C Q(\alpha+\delta_{\alpha})\|}{\|C\|}=\frac{\|C (I/2+ Q(\alpha+\delta_{\alpha}))\|}{\|C\|}\\
=\frac{\|C (I/2+ Q(\alpha))(I/2+ Q(\alpha))^{-1}(I/2+ Q(\alpha+\delta_{\alpha}))\|}{\|C\|}\\
\leq n(\alpha)\|(I/2+ Q(\alpha))^{-1}(I/2+ Q(\alpha+\delta_{\alpha}))\|$$
$(I/2+ Q(\alpha))^{-1}(I/2+ Q(\alpha+\delta_{\alpha}))$ is a diagonal matrix with diagonal elements either 1 or $\frac{1+\exp(i(\alpha+\delta_{\alpha}))}{1+\exp(i\alpha)}$. Note $|\frac{1+\exp(i(\alpha+\delta_{\alpha}))}{1+\exp(i\alpha)}|\leq 1$ for relevant parameter values ($\alpha\in[0,\pi],\delta_{\alpha}>0,\alpha+\delta_{\alpha}\leq\pi$), so $\|(I/2+ Q(\alpha))^{-1}(I/2+ Q(\alpha+\delta_{\alpha}))\|\leq 1$ so $n(\alpha+\delta_{\alpha})\leq n(\alpha)$, so $n(\alpha)$ is indeed a non-increasing function of $\alpha$.
So, on to the actual question


*

*I suspect that $n(\alpha)$ is always a non-increasing function of $\alpha$, not just in the $P=I/2$ case as shown above, but the proof technique used above does not work in the general case. How could I prove this?

*It also seems like $n(\alpha)\geq \cos(\alpha/2)$. How could I prove this?

 A: I'm not sure about other induced norms, but your conjectures are true for the induced 2-norm (i.e. the largest singular value), the induced 1-norm (the maximum absolute column sum) and the induced $\infty$-norm (the maximum absolute row sum), owing to the following observation:

Proposition. Let $p=1,2$ or $\infty$ and $\|\cdot\|$ denotes the matrix norm induced by the vector $p$-norm. Let $A(t)=\pmatrix{X&tY\\ tZ&W}$ be a complex partitioned matrix where $t\ge0$ and $X,Y,Z,W$ are fixed (but not necessarily square). Then $\|A(t)\|$ is increasing in $t$.

Note that the above proposition is also true when $t$ is multiplied to the diagonal blocks rather than to the antidiagonal blocks, because the induced 1-, 2- or $\infty$-norms are permutation invariant. I shall defer the proof of this proposition to the end of the answer. Let's see why your conjectures are true first.


*

*Presumably $C$ is nonzero. So, we may assume that it has unit norm and we may ignore the denominator in the definition of $n(\alpha)$.

*Let $z=e^{i\alpha/2}$. Then both $P$ and $Q$, up to permutations of rows and columns, are of the form $(\frac{z^2}2I)\oplus(\frac12I)$ (but the sizes of the identity matrices may of course be different).

*Therefore, we may assume that $C=\pmatrix{X&Y\\ Z&W}$ and $CP+QC=\pmatrix{z^2X&\frac{z^2+1}2Y\\ \frac{z^2+1}2Z&W}$.

*Since $\|D_1A(t)D_2\|=\|A(t)\|$ for any diagonal unitary matrices $D_1$ and $D_2$, we have, in turn,
$$
n(\alpha)
=\left\|\pmatrix{X&\frac{z^2+1}{2z}Y\\ \frac{z^2+1}{2z}Z&W}\right\|
=\left\|\pmatrix{X&\cos(\frac\alpha2)Y\\ \cos(\frac\alpha2)Z&W}\right\|.
$$

*So, by the previous proposition, $n(\alpha)$ is decreasing in $\alpha$.

*Also, if we apply the above proposition to the diagonal blocks instead of the antidiagonal ones, we get
$$
\left\|\pmatrix{X&\cos(\frac\alpha2)Y\\ \cos(\frac\alpha2)Z&W}\right\|
\ge\left\|\pmatrix{\cos(\frac\alpha2)X&\cos(\frac\alpha2)Y\\ \cos(\frac\alpha2)Z&\cos(\frac\alpha2)W}\right\|
=\cos(\frac\alpha2).
$$


Remark.
The above shows that your two conjectures are true as long as the boxed proposition is true and the matrix norm in question is induced by some vector norms such that $\|Px\|=\|Dx\|=\|x\|$ for any permutation matrix $P$ and diagonal unitary matrix $D$. However, I'm not sure whether the boxed proposition is really true for every such matrix norm. It is true, however, for the induced 1-, 2- and $\infty$-norms, as shown below.

Proof of the proposition.
The proposition is trivial for $\|\cdot\|_1$ and $\|\cdot\|_\infty$. So, we will consider only the induced 2-norm.
Ignore the trivial case that $A(0)=0$. Let $F=\pmatrix{X&0\\ 0&W}$ and $G=\pmatrix{0&Y\\ Z&0}$, so that $A(t)=F+tG$. Now, choose a fixed $t>0$ and let $\sigma_t=\|A(t)\|_2$. Let $u$ and $v$ be respectively a left and a right unit singular vector of $A(t)$ corresponding to the singular value $\sigma_t$ (so that $Av=\sigma_t u$ and $u^\ast Av=\sigma_t$).
Note that the real part of $u^\ast Gv$ must be nonnegative. Suppose the contrary. Then $t(u^\ast Gv)=-p+bi$ for some $p>0$ and $b\in\mathbb R$. Therefore $u^\ast Fv=\sigma_t+p-bi$. Yet, by the variational characterisation of singular values, for any complex matrix $M$, we have
$$
\|M\|_2 = \max_{\|x\|_2=\|y\|_2=1} |x^\ast My|.
$$
Since $F+tG$ is unitarily equivalent to $F-tG$ (in fact, one can obtain the latter by left and right multiplying the former by matrices of the form $I\oplus-I$), the singular value of $F-tG$ must be equal to $\sigma_t$. Therefore, by the variational characterisation of singular values, we get $\sigma_t\ge|u^\ast(F-tG)v|=|(\sigma_t+2p)-2bi|$, which is impossible because $p>0$. Therefore the real part of $u^\ast Gv$ must be nonnegative.
So, $T>t$,
$$
|u^\ast A(T)v|
=|u^\ast A(t)v + (T-t)(u^\ast Gv)|
=|\sigma_t + (T-t)(u^\ast Gv)|
\ge\sigma_t
$$
and hence $\|A(T)\|_2\ge\|A(t)\|_2$ for any $T>t\ge0$. As $\|A(t)\|_2$ is continuous in $t$, we conclude that it is increasing at $t=0$ too. $\square$
