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

Question

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).

Answer 1

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).$$