1
$\begingroup$

For two vectors $x$ and $y$ in $\mathbb{R}^n$, recall that $y$ weakly majorizes $x$, denoted by $x\prec_w y$, if the sum of the $k$ largest entries of $x$ is smaller than or equal to that of $y$ for each $k \in\{1, ..., n\}$.

For any matrix $A$, we use $\sigma(A)$ to denote the vector consisting of the singular values of $A$ in descending order.

Is the following "theorem" true if $A$ and $B$ are not square?

Theorem. For any matrices $A$ and $B$ of the same size, we have $|\sigma(A)-\sigma(B)| \prec_w \sigma(A-B)$, where the absolute value is taken entrywise.

This theorem is indeed true when $A$ and $B$ are both square matrices, and it is Theorem 2.3 of [A. S. Markus, The eigen- and singular values of the sum and product of linear operators, Uspekhi Mat. Nauk, 1964, Volume 19, Issue 4(118), 93–123]. [Markus 1964] attributes this result to [L. Mirsky, Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. II (1960), 50-59], which mentions it in the proof of Theorem 5. Theorem 5.4 of [Markus 1964] extends it to completely continuous operators on a separable Hilbert space. The inequality is also given in (2.9) of [T. Ando, Majorizations and inequalities in matrix theory. Linear algebra and its Applications, 1994, vol. 199, p. 17-67].

Question. Does the abovementioned theorem still hold when $A$ and $B$ are not square? It seems yes to me, and the proof in [Markus 1964] is still applicable. However, I have not found a reference stating this theorem in the non-square case and providing a proof. It would be great if anyone can direct me to such a reference. Thank you very much.

P.S.: A "simple" consequence of this "theorem" would be, for example, the Hoffman-Wielandt bound for singular values: $\|\sigma(A) - \sigma(B)\|_2 \le \|A-B\|_\text{F}$, which does hold in the rectangular case (e.g., [Corollary 7.3.5, R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, second edition, 2012]).

Update: Reference found. See Theorem 3.4.5 in [R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1994] and Theorem 10.24 in [Zhang, Matrix Theory: Basic Results and Techniques, Springer, New York, second edition, 2011]. Many thanks to @ToniMhax.

$\endgroup$
6
  • 1
    $\begingroup$ Why not just zero pad and then conclude? (and hence, no need of a separate reference?) $\endgroup$
    – Suvrit
    Jul 29, 2022 at 20:08
  • 1
    $\begingroup$ @Suvrit but the zeroes may appear in different places after rearrangement, is this ok? $\endgroup$ Jul 29, 2022 at 20:15
  • $\begingroup$ Thank you Suvrit and Fedor Petrov for the comments. I hope to have an exact reference with a proof, because first I do not want to prove an existing classical result in my paper, and second I detest citations that do not directly support the author's claim. Similar to the abuse of "obvious", such a citation gives readers an extra burden and it is not uncommon that the author's claim turns out problematic. Writing in that way often reflects the laziness and carelessness of the author. These are only personal opinions. Many thanks again. $\endgroup$
    – Nuno
    Jul 30, 2022 at 5:43
  • $\begingroup$ Anway, if such a seemingly "classical" result is true, it would be rather strange if no reference mentions it in an exact way. $\endgroup$
    – Nuno
    Jul 30, 2022 at 5:49
  • 1
    $\begingroup$ I don't see the issue, the square matrix $\begin{pmatrix}A&0\\0&0\end{pmatrix}$ has the same non zero singular values as $A$. So as suggested you add zeros to $A$ to $B$ and thus $A-B$. For rectangular $A$ and $B$ the vectors do not change except additional zeros. A reference with proof is Fuzhen Zhang : Matrix Theory Basic Results and Techniques 2011 Sec 10.4. $\endgroup$
    – Toni Mhax
    Jul 30, 2022 at 7:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.