For any two matrices $\mathbf{A},\mathbf{B} \in \mathbb{C}^{n \times n}$, we know that the following [majorization inequality](https://en.wikipedia.org/wiki/Majorization) 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](https://en.wikipedia.org/wiki/Compound_matrix)) $\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).



Proving a majorization inequality for the singular value of the product of two matrices without using tensor product
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).$$


