How can one simply see that Ky Fan $k$-norm satisfies the triangle inequality? (The Ky Fan $k$-norm of a matrix is the sum of the $k$ largest singular values of the matrix)

  • 2
    $\begingroup$ Could you please define the Ky Fan $k$-norm and let us know what you already tried? Also, is this homework? $\endgroup$ – Glen Wheeler Mar 21 '11 at 19:17
  • $\begingroup$ The Ky Fan $k$-norm of a matrix is the sum of the $k$ largest singular values of the matrix $\endgroup$ – user4727 Mar 21 '11 at 19:28
  • 3
    $\begingroup$ @user4727 Thanks for the edit. Are you aware of the original papers by Ky Fan (~1950)? The reason why it is called the "Ky Fan norm" is because he proved it is a norm first. This might be a good opportunity for some "research"! :) $\endgroup$ – Glen Wheeler Mar 21 '11 at 19:47

For any $k$-plane $U$ in $\mathbb{C}^n$, let $i_U$ be the inclusion of $U$ into $\mathbb{C}^n$ and let $p_U$ be the orthogonal projection of $\mathbb{C}^n$ onto $U$.

Lemma: Let the singular values of $A$ be $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n$. Then $\max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right)= \sigma_1+ \cdots +\sigma_k$, where the max is over all pairs of $k$-planes in $\mathbb{C}^n$.

Proof is left for the reader, using his or her favorite definition of singular values.

Then $\max_{U, V} \ \mathrm{Tr} \left(p_V \circ (A+B) \circ i_U\right) \leq \max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right) + \max_{U, V} \ \mathrm{Tr} \left( p_V \circ B \circ i_U \right)$.

  • $\begingroup$ isn't it the same to use $p_U$ rather than $i_U$ here? If by $i_U$ you mean the operator $i_U(x)=x$ for all $x\in U$, isn't this the same as the corresponding projector onto $U$? $\endgroup$ – glS Jul 14 '20 at 16:58
  • 2
    $\begingroup$ @glS The domain/codomain are essential here. Note that $i_U: U \to \Bbb C^n$ and $p_V : \Bbb C^n \to V$, so that $p_V \circ A \circ i_U$ is a map between $k$-dimensional vector spaces. $\endgroup$ – Ben Grossmann Jul 16 '20 at 9:26
  • 1
    $\begingroup$ Right. If you like matrices better than maps, then the lemma is that $\sigma_1 + \cdots + \sigma_k$ is $\max X^T A Y$, where $X$ and $Y$ run over $n \times k$ matrices with orthogonal columns. If $X$ is such a matrix, and $U$ is its column span, then $\iota_U$ is given by the matrix $X$ and $p_U$ by the matrix $X^T$. $\endgroup$ – David E Speyer Jul 16 '20 at 13:30
  • $\begingroup$ I see what you mean, thanks (assuming you just missed a trace in the comment). So in terms of matrices, you are essentially maximising $\operatorname{tr}(A U)$ over all matrices $U$ with rank $k$ which act as a unitary in a $k$-dimensional subspace. Which would make this sort of a generalisation of $\max\operatorname{tr}(AU)=\operatorname{tr}|A|$ where the maximisation is over all unitaries $U$. $\endgroup$ – glS Jul 16 '20 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.