# Extend an inequality on matrix norms

Let $$A$$ denote an $$n \times n$$ matrix, and $$\sigma_i(\cdot)$$ denote $$i$$-th largest singular value. Can we extend the following result to general $$p \geq 1$$?

For all $$k = 1, \dots, n$$, $$\sum_{i = 1}^k \left[\sigma_i\left(M_1^\mathrm{T}AM_2\right)\right]^p \leq \sum_{i = 1}^k \left[\sigma_i(A)\right]^p$$ where $$M_1, M_2 \in \mathbb{R}^{n \times k}$$ satisfy $$M_1^\mathrm{T}M_1 = M_2^\mathrm{T}M_2 = I_k$$.

The special cases for $$p = 1$$ and $$p = 2$$ are known to be true and can be found in Theorem 7.4.1.1 and Corollary 4.3.39 of [1].

Remarks:

1. The results for $$k = 1$$ and $$k = n$$ are trivially true;
2. By considering the SVD of $$A$$, it is without loss of generality to assume that $$A$$ is a diagonal matrix: $$A = D = \mathrm{diag}(d_{1}, \dots, d_{n})$$ with $$d_{1} \geq \dots \geq d_{n} \geq 0$$.

[1] Horn, Roger A.; Johnson, Charles R., Matrix analysis, Cambridge etc.: Cambridge University Press. XIII, 561 p. (1985). ZBL0576.15001.

• @SamHopkins We can verify the case $k = 1$ for a quick sanity check. Jan 1 at 4:51

Update: the extension is correct since for $$j = 1, \dots, k$$ \begin{align}\sigma_j(M_1^\mathrm{T} A M_2) &= \sigma_j\left(\begin{bmatrix}M_1& O_{n, n-k}\end{bmatrix}^\mathrm{T} A \begin{bmatrix}M_2& O_{n, n-k}\end{bmatrix}\right)\\ & \leq \sigma_j(A) \cdot \left\|\begin{bmatrix}M_1& O_{n, n-k}\end{bmatrix}\right\| \cdot \left\|\begin{bmatrix}M_2& O_{n, n-k}\end{bmatrix}\right\| \\ &= \sigma_j(A). \end{align}

                  Below is an earlier proof.


By considering the SVD of $$A$$, it is w.l.o.g. to assume that $$A = D =\mathrm{diag}(d_1, \dots, \dots, d_n)$$ with $$d_1 \geq \dots \geq d_n \geq 0$$. Suppose we have the SVD $$M_1^\mathrm{T} D M_2 = U \hat{D} V^\mathrm{T}$$, where $$\hat{D} = \mathrm{diag}(\hat{d}_1, \dots, \hat{d}_k)$$, $$U$$ and $$V$$ are orthogonal matrices. Let us define $$n \times k$$ matrices $$Q = M_1 U, S = M_2V$$. Then we have $$Q^\mathrm{T}Q = S^\mathrm{T}S = I_k$$ and $$\hat{D} = Q^\mathrm{T} D S$$, which implies that $$\hat{d}_j = \sum_{i = 1}^n q_{ij} s_{i j} d_i, \quad j = 1, \dots, k,$$ where $$q_{ij}$$ and $$s_{i j}$$ are the $$(i, j)$$-th entries of $$Q$$ and $$S$$, respectively.

As a result, \begin{align} \sum_{j = 1}^k \left[\sigma_j\left(M_1^\mathrm{T}DM_2\right)\right]^p = \sum_{j = 1}^k (\hat{d}_j)^p &= \sum_{j = 1}^k \left(\sum_{i = 1}^n q_{ij} s_{i j} d_i\right)^p\\ &\leq \sum_{j = 1}^k \left(\sum_{i = 1}^n |q_{ij} s_{i j}| d_i\right)^p\\ &= \sum_{j = 1}^k \left(\sum_{i = 1}^n \frac{|q_{ij} s_{i j}|}{\sum_{i = 1}^n |q_{ij} s_{i j}|} d_i\right)^p \cdot \left(\sum_{i = 1}^n |q_{ij} s_{i j}|\right)^p\\ &\leq \sum_{j = 1}^k \sum_{i = 1}^n \frac{|q_{ij} s_{i j}|}{\sum_{i = 1}^n |q_{ij} s_{i j}|} d_i^p \cdot \left(\sum_{i = 1}^n |q_{ij} s_{i j}|\right)^p\\ &=\sum_{j = 1}^k \sum_{i = 1}^n |q_{ij} s_{i j}| d_i^p \cdot \left(\sum_{i = 1}^n |q_{ij} s_{i j}|\right)^{p-1}\\ &\leq \sum_{j = 1}^k \sum_{i = 1}^n \left(\frac{q_{ij}^2 + s_{ij}^2}{2}\cdot d_i^p \cdot \left(\sum_{i = 1}^n \frac{q^2_{ij}+ s^2_{i j}}{2}\right)^{p-1}\right)\\ &= \sum_{i = 1}^n c_i\cdot d_i^p, \end{align} where we have defined $$\displaystyle c_i = \sum_{j = 1}^k \frac{q_{ij}^2 + s_{ij}^2}{2}, i= 1, \dots, n$$. To obtain the second inequality, we have used the convexity of $$x \mapsto x^p$$. The last equality follows from the fact $$\sum_{i = 1}^n q_{ij}^2 = \sum_{i = 1}^n s_{ij}^2 = 1, \quad\text{for } j = 1, \dots, k.$$ Since $$0 \leq c_i \leq 1$$ for each $$i = 1, \dots, n$$, and $$\displaystyle \sum_{i = 1}^n c_i = \|Q\|_{\mathrm{F}}^2 + \|S\|_{\mathrm{F}}^2 = k$$, we have $$\sum_{i = 1}^n c_i\cdot d_i^p \leq \sum_{i = 1}^k d_i^p = \sum_{i = 1}^k \left[\sigma_i\left(D\right)\right]^p,$$ which completes the proof.

I post this instead of a comment, feel free to comment.

1. The inequality in the main question for $$p=1$$ (and $$p>1$$) can be found in chap. 3 Topics in matrix analysis by R. Horn and C. Johnson, (i don't see similar result in the references given, however the inequality follows by the folllowing argument 3).

2. Edit.

3. On the space of $$n\times n$$ complex matrices $$(\sum_{i=1}^k\sigma_i^p)^{\frac{1}{p}}$$ for $$k\le n$$, $$p\ge 1$$ where $$\sigma_i$$ are the singular values arranged in decreasing order, is a unitarily invariant norm: for $$k=n$$ it is $$p-$$ schatten norm. The proof is similar to the $$p-$$ schatten norm proof here [p-schatten][1]

4. The inequality is true for $$p=1$$ and any $$k\le n$$; by Ky-Fan dominance theorem it is true for any unitarily invariant norm which implies the result. [1]: https://math.stackexchange.com/q/4197721

• For the 2nd argument, if $n = k = 2$, $M_1, M_2$ are both unitary, so $\sigma_2(M_1^\mathrm{T} A M_2) = \sigma_2(A)$ for $j = 2$. Jan 4 at 12:59
• In your construction, both sides should be equal to $\sigma_2$, so the inequality holds. Also, you can find the reference for the submultiplicativity in the second exercise after Theorem 7.3.8, page 452 of matrix analysis by R. Horn and C. Johnson. Jan 4 at 16:03
• Your 4th and 3rd arguments essentially extend the result to any unitary invariant norm $|\!|\!| \cdot |\!|\!|$: $|\!|\!|M_1^\mathrm{T} A M_2|\!|\!| \leq |\!|\!| A|\!|\!|$. The norm in the 3rd argument was denoted as $\|\cdot\|_{(k)}^{(p)}$ in Bhatia's GTM 169. Exercise IV. 2.8. Jan 4 at 17:14
• Yes ok sorry i will edit, i didn't find the exact (submultiplicative) inequality though in Ch.7. M. Analysis. – This can be found in Fuzhen Zhang book Matrix theory Basic results and Techniques 2nd edition Section 8.4. Jan 4 at 18:35