Proving a majorization inequality for the singular value of the product of two matrices without using tensor product

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?

My attempt:

By the maximal characteristic of the singular values, we know that $$$$\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|,$$$$ for $$i=1,\dots,n$$. Using this formula, we can demonstrate that the inequalities \eqref{sysineq} are equivalent to the following system of inequalities: $$$$\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|,$$$$ for $$k=1,\dots,n$$. All I can show is that for each $$i=1,\dots,k$$, we have $$$$\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}$$$$ 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 $$$$\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|.$$$$ 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).

• 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. Commented Jul 13, 2020 at 2:46
• 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. Commented Jul 29, 2020 at 8:47
• 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.
– LayZ
Commented Jul 29, 2020 at 22:50

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).$$
• 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?
• @LayZ: (1) Consider the polar decomposition; (2) $(U,V)\mapsto\mathrm{Tr}(UAV^*B)$ is a semi-inner product. Commented Jul 30, 2020 at 1:49