5
$\begingroup$

For any two matrices $\mathbf{A},\mathbf{B} \in \mathbb{C}^{n \times n}$, we know that the following majorization inequality holds

$$ \tag{1} \label{grz} \sigma^{\downarrow}(\mathbf{A}\mathbf{B}) \prec_w \sigma^{\downarrow}(\mathbf{A})\sigma^{\downarrow}(\mathbf{B}), $$ where $\sigma^{\downarrow}(\cdot)$ denotes the vector of singular values, ordered in the decreasing order. This is equivalent to the following system of inequalities $$ \tag{2} \label{sysineq} \sum_{i=1}^k\sigma_i^{\downarrow}(\mathbf{A}\mathbf{B}) \leq \sum_{i=1}^k \sigma_i^{\downarrow}(\mathbf{A})\sigma_i^{\downarrow}(\mathbf{B}), $$ for $k=1,\dots,n$.

Proof:

In all the textbooks or papers that I have seen, the proof of this majorization inequality is as follows. By the sub-multiplicativity of the spectral norm, one has $$ \sigma_1^{\downarrow}(\mathbf{A}\mathbf{B}) \leq \sigma_1^{\downarrow}(\mathbf{A})\sigma_1^{\downarrow}(\mathbf{B}). $$ By employing this inequality to the anti-symmetric tensor powers (i.e. the compound matrices) $\wedge^k(\mathbf{A})$ and $\wedge^k(\mathbf{B})$, we have $$ \sigma_1^{\downarrow}\big((\wedge^k \mathbf{A})(\wedge^k \mathbf{B})\big) \leq \sigma_1^{\downarrow}\big(\wedge^k \mathbf{A}\big)\sigma_1^{\downarrow}\big(\wedge^k \mathbf{B}\big), $$ for $k=1,\dots,n$. Then using the facts that $\wedge^k(\mathbf{A}\mathbf{B}) = (\wedge^k \mathbf{A})(\wedge^k \mathbf{B})$ and $\sigma_1^{\downarrow}\big(\wedge^k \mathbf{A}\big) = \prod_{i=1}^k \sigma_i^{\downarrow}(\mathbf{A})$, it follows that

$$ \tag{3} \label{lwm} \prod_{i=1}^k\sigma_i^{\downarrow}(\mathbf{A}\mathbf{B}) \leq \prod_{i=1}^k \sigma_i^{\downarrow}(\mathbf{A})\sigma_i^{\downarrow}(\mathbf{B}), $$ for $k=1,\dots,n$. Finally, inequality \eqref{grz} follows using the fact that log-weak majorization inequality \eqref{lwm} implies weak majorization inequality \eqref{grz} [Bhatia, Matrix analysis, Example II.3.5 (vi)].

Question:

Can we prove the majorization inequality \eqref{grz} without resorting to the tensor products and employing no facts about them?

Thanks in advance!

My attempt:

By the maximal characteristic of the singular values, we know that \begin{equation} \sigma_i(\mathbf{A}) = \max_{\substack{\|\bf{x}_i\|=\|\bf{y}_i\|=1 \\ \bf{x}_i \bot \text{span}\{\bf{x}_1,\dots, \bf{x}_{i-1}\} \\ \bf{y}_i \bot \text{span}\{\bf{y}_1,\dots, \bf{y}_{i-1}\}}}\big|\langle \mathbf{A}\bf{x}_i,\bf{y}_i \rangle\big|, \end{equation} for $i=1,\dots,n$. Using this formula, we can demonstrate that the inequalities \eqref{sysineq} are equivalent to the following system of inequalities: \begin{equation} \max_{\substack{\|\bf{x}_i\|=\|\bf{y}_i\|=1, \;i \in [k] \\ \bf{x}_1 \bot \dots \bot \bf{x}_k \\ \bf{y}_1 \bot \dots \bot \bf{y}_k}} \sum_{i=1}^k \big|\langle \mathbf{A}\mathbf{B} \bf{x}_i,\bf{y}_i \rangle\big| \leq \max_{\substack{\|\bf{x}_i\|=\|\hat{\bf{x}}_i\|=1, \;i \in [k] \\ \bf{x}_1 \bot \dots \bot \bf{x}_k \\ \hat{\bf{x}}_1 \bot \dots \bot \hat{\bf{x}}_k}} \max_{\substack{\|\bf{y}_i\|=\|\hat{\bf{y}}_i\|=1, \;i \in [k] \\ \bf{y}_1 \bot \dots \bot \bf{y}_k \\ \hat{\bf{y}}_1 \bot \dots \bot \hat{\bf{y}}_k}} \sum_{i=1}^k\big| \langle \mathbf{B}\bf{x}_i,\hat{\bf{x}}_i \rangle \langle \mathbf{A}\bf{y}_i,\hat{\bf{y}}_i \rangle\big|, \end{equation} for $k=1,\dots,n$. All I can show is that for each $i=1,\dots,k$, we have \begin{equation} \begin{split} \big|\langle \mathbf{A}\mathbf{B} \bf{x}_i,\bf{y}_i \rangle\big| &= \big|\langle \mathbf{B} \bf{x}_i, \mathbf{A}^\mathsf{H}\bf{y}_i \rangle\big| \\ & \leq \|\mathbf{B}\bf{x}_i\| \|\mathbf{A}^\mathsf{H}\bf{y}_i\| \\ & = \max_{\|\hat{\bf{x}}_i\|=1} \big|\langle \mathbf{B}\bf{x}_i,\hat{\bf{x}}_i \rangle\big| \max_{\|\hat{\bf{y}}_i\|=1} \big|\langle \mathbf{A}^\mathsf{H}\bf{y}_i,\hat{\bf{y}}_i \rangle\big|, \end{split} \end{equation} where $\mathbf{A}^\mathsf{H}$ is the conjugate transpose of $\mathbf{A}$. The inequality and the last equality follow by the Cauchy-Schwarz inequality. Therefore \begin{equation} \max_{\substack{\|\bf{x}_i\|=\|\bf{y}_i\|=1 \\ \bf{x}_1 \bot \dots \bot \bf{x}_k \\ \bf{y}_1 \bot \dots \bot \bf{y}_k}} \sum_{i=1}^k \big|\langle \mathbf{A}\mathbf{B} \bf{x}_i,\bf{y}_i \rangle\big| \leq \max_{\substack{\|\bf{x}_i\|=\|\hat{\bf{x}}_i\|=1 \\ \bf{x}_1 \bot \dots \bot \bf{x}_k}} \max_{\substack{\|\bf{y}_i\|=\|\hat{\mathbf{y}}_i\|=1 \\ \mathbf{y}_1 \bot \dots \bot \mathbf{y}_k}} \sum_{i=1}^k\big| \langle B\mathbf{x}_i,\hat{\mathbf{x}}_i \rangle \langle A\hat{\mathbf{y}}_i,\bf{y}_i \rangle\big|. \end{equation} However, these inequalities are weaker than what we want.

Bhatia, Rajendra, Matrix analysis, Graduate Texts in Mathematics. 169. New York, NY: Springer. xi, 347 p. (1996).

$\endgroup$
3
  • 1
    $\begingroup$ Taking the question literally, the answer is "Yes"; am feeling a bit lazy myself right now, but I hope to type up some of that answer in a few days if nobody else does it in the meanwhile. $\endgroup$
    – Suvrit
    Commented Jul 13, 2020 at 2:46
  • 1
    $\begingroup$ Since Suvrit seems busy, I'd say it follows from $$\sum_{i=1}^k \sigma^\downarrow_i(AB) = \sup_{U}|\mathop{\mathrm{Tr}}(UAB)| \le \sup_{U,V}|\mathop{\mathrm{Tr}}(UAVB)| =\sum_{i=1}^k \sigma^\downarrow_i(A)\sigma^\downarrow_i(B),$$ where $U$ and $V$ run over all partial isometries (contractions) of rank (at most) $k$. The only nontrivial is $\le$ part of the rightmost equality. $\endgroup$ Commented Jul 29, 2020 at 8:47
  • $\begingroup$ Thanks. It would be great if you could refer me to a proof of the last equality. To prove the inequality we can assume that $\hat{U}$ is the partial isometry that maximizes the LHS sup. Then, we need to show $$ |\mathrm{Tr}(B\hat{U}A)| \le \sup_{V}|\mathrm{Tr}(B\hat{U}AV)|. $$ Now, let $B\hat{U}A$ have the singular value decomposition $R\Sigma Q^*$, where $\Sigma$ has at most $k$ non-zero elements, then there exists a rank (at most) $k$ partial isometry $V=Q\Lambda Q^*$ s.t. $|\mathop{\mathrm{Tr}}(B\hat{U}A)|=|\mathop{\mathrm{Tr}}(B\hat{U}AV)|$. The inequality follows by taking the sup. $\endgroup$
    – LayZ
    Commented Jul 29, 2020 at 22:50

1 Answer 1

3
$\begingroup$

We prove that $$\sum_{i=1}^k \sigma^\downarrow_i(AB) = \sup_{U}|\mathrm{Tr}(UAB)| \le \sup_{U,V}|\mathrm{Tr}(UAV^*B)| =\sum_{i=1}^k \sigma^\downarrow_i(A)\sigma^\downarrow_i(B),$$ where $U$ and $V$ run over all partial isometries (or contractions) of rank (at most) $k$. The only nontrivial is $\le$ part of the rightmost equality. For the proof of this, we may assume that $A$ and $B$ are positive. Then by the Cauchy--Schwarz inequality, $|\mathrm{Tr}(UAV^*B)|$ attains the supremum $\mathrm{Tr}(UAU^*B)$ at some rank $k$ partial isometry $U$ (and $V=U$). Let's denote by $\tilde{A}$ (resp.\ $\tilde{B}$) the truncated operator $UAU^*$ (resp.\ $B$) on $\mathop{\mathrm{ran}} U$. Then $\tilde{A}$ and $\tilde{B}$ are positive operators of rank at most $k$ satisfying $\sigma^\downarrow(\tilde{A})\prec_w\sigma^\downarrow(A)$, $\sigma^\downarrow(\tilde{B})\prec_w\sigma^\downarrow(B)$, and $$\mathrm{Tr}(UAU^*B)=\mathrm{Tr}(\tilde{A}\tilde{B}).$$ For the computation of $\mathrm{Tr}(\tilde{A}\tilde{B})$, we may assume that $\mathop{\mathrm{ran}} U={\mathbb C}^k$ and $\tilde{A}$ is the diagonal matrix with entries $\sigma^\downarrow(\tilde{A})$. Let's denote by $\beta$ the diagonal entries of the positive matrix $\tilde{B}$. Then it satisfies $\beta^\downarrow\prec\sigma^\downarrow(\tilde{B})$. Hence in conclusion $$\sup_{U,V}|\mathrm{Tr}(UAV^*B)| = \mathrm{Tr}(\tilde{A}\tilde{B}) = \sum_{i=1}^k\sigma^\downarrow_i(\tilde{A})\beta_i \le \sum_{i=1}^k\sigma^\downarrow_i(A)\sigma^\downarrow_i(B).$$ Here, we have used (twice) the following fact. For any positive eventually-zero sequences $\alpha,\beta,\gamma$ with $\beta^\downarrow\prec_w\gamma^\downarrow$, one has $\sum_i\alpha^\downarrow_i\beta_i \le \sum_i\alpha^\downarrow_i\gamma^\downarrow_i$, because $$\sum_i\alpha^\downarrow_i\beta_i = \sum_i\bigl((\alpha^\downarrow_i-\alpha^\downarrow_{i+1})\sum_{j=1}^i\beta_j\bigr).$$

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. I have two questions. First, I understand that we are able to assume WLOG $A$ and $B$ are Hermitian, but why can we assume that they are positive at the same time. Second, could you elaborate more on how Cauchy-Schwarz inequality implies that $|\mathrm{Tr}(UAV^*B)|$ attains the supremum when $V$ and $U$ are equal? $\endgroup$
    – LayZ
    Commented Jul 30, 2020 at 1:45
  • 2
    $\begingroup$ @LayZ: (1) Consider the polar decomposition; (2) $(U,V)\mapsto\mathrm{Tr}(UAV^*B)$ is a semi-inner product. $\endgroup$ Commented Jul 30, 2020 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.