Prove $ \| {\bf A}^2\|_* \leq \operatorname{tr}({\bf A}^\dagger {\bf A})$

Question

I saw a lemma without any proof states that:

$$ \left\| {\bf A}^2 \right\|_* \leq \operatorname{tr} \left( {\bf A}^\dagger {\bf A} \right)$$

where $\bf A$ is an arbitrary square matrix and $\|\cdot\|_*$ denotes the nuclear norm (Schatten 1-norm).

I tried many inequalities related to the nuclear norm, but most of them only show what a nuclear norm is larger than.​ I can't prove it.​

Answer 1

We have $$ \| A^2\|_\ast = \sum_{i=1}^n \sigma_i(A^2) \leq \sum_{i=1}^n \sigma_i(A)^2 = \operatorname{Tr}(A^\dagger A) $$

where the inequality follows from the more general lemma (for $A=B$, $m=n=k=r$ and $p=1$):

Lemma. (Theorem 3.3.14 in [1]) Let $p>0$, and $A,B$ be two $n\times k$ and $k\times m$ matrices, respectively. Then, for any $r \leq \min(n,k,m)$, $$ \sum_{i=1}^{r} \sigma_i(AB)^p \leq \sum_{i=1}^{r} \sigma_i(A)^p\sigma_i(B)^p $$

[1] R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1991.

Answer 2

OK. After learning about Frobenius norm, I found a proof which is more simple than what has shown in the reference involved in the answer of @Clement C. This answer is from @user1551 and includes more detail.

Definition. For $A, B \in C^{m\times n}$, we can define Frobenius inner product (Hilbert-Schmidt inner product): $$\langle A, B\rangle_F=\sum_{i=1}^n\sum_{j=1}^m A_{ij}^*B_{ij}=tr(BA^\dagger)=tr(A^\dagger B)$$ It is easy to prove Frobenius inner product satisfy positivity, definiteness, conjugate symmetry, conjugate linearity in the first slot and linearity in the second slot, which is necessary for the definition of a inner product by applying the basic properties of trace.

Besides, we immediately find that Frobenius norm (Hilbert-Schmidt norm or Schatten 2-norm) has been derived: $$\langle A, A\rangle_F=tr(A^\dagger A)= \|A\|_F^2$$

Now we can take a look at Cauchy-Schwarz inequality under this condition.

Theorem. For any $A, B \in C^{m\times n}$, always holds Cauchy-Schwarz inequality: $$\|A\|_F \|B\|_F \geq |\langle A, B\rangle_F|$$ The inequality is saturated iff $A=cB$, where $c$ is an complex constant.

Proof.

Consider the Frobenius inner product $\langle A-\lambda I, A-\lambda I\rangle_F$. It's obviously that $\langle A-\lambda I, A-\lambda I\rangle_F \geq 0$. \begin{align} \text{i.e.}&&\langle A-\lambda I, A-\lambda I\rangle&=tr[(A-\lambda I)^\dagger(A-\lambda I)]\\ & & &=tr[A^\dagger A-\lambda A^\dagger B -\lambda^*B^\dagger A+|\lambda|^2 B^\dagger B]\\ & & &=\|A\|_F^2+|\lambda|^2\|B\|_F^2-\lambda \langle A, B\rangle_F-\lambda^* \langle B, A\rangle_F \geq 0 \end{align} Let $\lambda=\frac{\langle B, A\rangle_F }{\|B\|_F^2}$ \begin{align} |A\|_F^2+\frac{\langle B, A\rangle_F\langle B, A\rangle_F^*}{\|B\|_F^2}-\frac{\langle B, A\rangle_F\langle A, B\rangle_F}{\|B\|_F^2}-\frac{\langle B, A\rangle_F^*\langle B, A\rangle_F}{\|B\|_F^2} \geq 0 \end{align} Then we can get \begin{align} \hspace{12em}&&\|A\|_F \|B\|_F \geq |\langle A, B\rangle_F| &&\hspace{12em}\square \end{align}

Lemma. The nuclear norm of a matrix $T$ can be written as $\|T\|_*=\max\limits_{S^\dagger S=I} |tr(TS)|$.

Proof. For the sake of simplification, here we use Dirac (Bra-Ket) notation to prove this. (However, a proof by using matrix notation is equivalent.)

Suppose a matrix $T$ can be written as the form of SVD: $T=\sum\limits_j t_j |f_j\rangle\langle e_j|$ and a unitary matrix $S=\sum\limits_k |g_k\rangle\langle f_k|$, where $\{|e_j\rangle\}, \{|f_j\rangle\}, \{|g_j\rangle\}$ are orthonormal bases. $t_j\geq 0$ are singular values of $T$. So that $$ST=\sum\limits_j t_j |f_j\rangle\langle e_j|$$ $$|tr(ST)|=|\sum\limits_j t_j \langle f_j|g_j \rangle|\leq \sum\limits_j t_j |\langle f_j|g_j \rangle|\leq \sum\limits_j t_j =\|T\|_*$$ The inequality is saturated iff $S=\sum\limits_k |e_k\rangle\langle f_k|$ as $\{|e_j\rangle\}, \{|f_j\rangle\}, \{|g_j\rangle\}$ are orthonormal bases.

Now we can derive the lemma that \begin{align} \hspace{8em}&&\|T\|_*=\max\limits_{S^\dagger S=I} |tr(ST)|=\max\limits_{S^\dagger S=I} |tr(TS)| &&\hspace{9em}\square \end{align}

Theorem. Suppose A is a square matrix, then $$ \left\| {\bf A}^2 \right\|_* \leq \operatorname{tr} \left( {\bf A}^\dagger {\bf A} \right)$$ where $\|\cdot\|_*$ denotes the nuclear norm (Schatten 1-norm).

Proof. It follows directly from Cauchy-Schwarz inequality: \begin{align} \|A^2\|_\ast=\max\limits_{S^\dagger S=I}|\operatorname{tr}(A^2S)|=\max\limits_{S^\dagger S=I}|\langle A^\dagger,AQ\rangle_F|\le\max\limits_{S^\dagger S=I}\|A^\dagger\|_F\|AQ\|_F=\|A\|_F^2=\operatorname{tr}(A^\dagger A)\quad\square \end{align}

Besides, there is a corollary which can be derived by applying spectral theorem and the condition when Cauchy-Schwarz inequality is saturated.

Corollary. The inequality $\| {\bf A}^2 \|_* \leq \operatorname{tr} \left( {\bf A}^\dagger {\bf A} \right)$ is saturated iff $A$ is normal.