3
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Jan 4, 2023 at 12:59
  • $\begingroup$ 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. $\endgroup$ Jan 4, 2023 at 16:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 4, 2023 at 17:14
  • $\begingroup$ 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. $\endgroup$
    – Toni Mhax
    Jan 4, 2023 at 18:35

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.