# Prove that the Ky Fan norm satisfies the triangle inequality

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)

• Could you please define the Ky Fan $k$-norm and let us know what you already tried? Also, is this homework? – Glen Wheeler Mar 21 '11 at 19:17
• The Ky Fan $k$-norm of a matrix is the sum of the $k$ largest singular values of the matrix – user4727 Mar 21 '11 at 19:28
• @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"! :) – 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$.
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)$.
• 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$? – glS Jul 14 '20 at 16:58
• @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. – Ben Grossmann Jul 16 '20 at 9:26
• 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$. – David E Speyer Jul 16 '20 at 13:30
• 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$. – glS Jul 16 '20 at 15:48