Suppose $A$ is an $n \times n$ complex matrix with singular values $s_1 \ge s_2 \ge \cdots \ge s_n$ and eigenvalues $(\lambda_i)_{i=1}^{n}$ arranged so that $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$. Is it true that $s_1 \ge \lambda_1,\ s_1+s_2 \ge \lambda_1 + \lambda_2,$ and so on?

1For normal matrices, it seems clear that we have the even stronger statement $s_j \ge \lambda_j$ for each $j$. On the other hand, for nonnormal matrices this stronger statement fails. – David Ketcheson Oct 26 '14 at 11:05

2@David: How does this correlate with $\prod s_i=\prod \lambda_i=\det A$? – Ilya Bogdanov Oct 26 '14 at 16:14

1Am I missing something, or for normal matrices $s_i=\lambda_i$, since the eigendecomposition is an SVD up to phase factors? – Federico Poloni Oct 26 '14 at 18:00

@Federico: Surely;) – Ilya Bogdanov Oct 26 '14 at 19:18

2A relevant reference here is the classic paper of Horn, ams.org/mathscinetgetitem?mr=61573 , showing that the Weyl inequalities in Yanqi's answer in fact generate the complete set of relations between singular values and eigenvalues. Also, one can prove the inequalities by applying GramSchmidt to the eigenvectors to conjugate $A$ by a unitary matrices to uppertriangular form (so that the eigenvalues become diagonal entries), and then applying the SVD and orthogonality relations for the singular vectors. – Terry Tao Oct 26 '14 at 20:31
Let $\lambda(A)$ denote the vector of eigenvalues and $s(A)$ the vector of singular values (arranged in decreasing order). The claim of the question is whether $\lambda(A)^{\downarrow} \prec_w s(A)$. The answer to this question is yes (the proof follows using the tensor power trick Yanqi Qui mentioned above).
Theorem (Weyl's Majorant theorem). Let $f: (0,\infty)\to(0,\infty)$ be such that $f(e^t)$ is convex and monotone increasing in $t$. Then $$[f(\vert\lambda_1\vert),\ldots, f(\lambda_n)] \prec_w [f(s_1),\ldots,f(s_n)].$$
As a corollary, using the function $t \mapsto t^p$ for any $p \ge 0$, we obtain an affirmative answer to the OP's question (actually, by merely using the special case $p=1$). Actually, Weyl's Majorant theorem provides the following logmajorization (which implies the above result): \begin{equation*} \log \lambda(A) \prec \log s(A), \end{equation*} and this version also answers Ilya's comment, namely $\prod_i^n \lambda_i = \prod_i^n s_i$.
Another closely related result is that of absolute values of the Hermitian part of a complex matrix. Let $\Re(A) := (A+A^*)/2$. Then, we have
Theorem (FanHoffman). For every matrix $A$, we have \begin{eqnarray*} \lambda_j^{\downarrow}(\Re(A)) &\le& s_j(A),\qquad 1\le j \le n\\ \lambda(\Re(A)) &\prec_w& s(A). \end{eqnarray*}
Reference
R. Bhatia, Matrix Analysis (Springer GTM, 169).
The singular values of $A$ are the eigenvalues of $A$. Since $$ \lambda_1(A) \lambda_2(A) \cdots \lambda_k(A)$$ is an eigenvalue of $\underbrace{A\wedge A\wedge \dots \wedge A }_{\text{$k$ times}} $, we have \begin{align*} \lambda_1(A) \lambda_2(A) \cdots \lambda_k(A)  & \le \ A\wedge A\wedge \dots \wedge A \ \\ &= \Big\ \leftA\wedge A\wedge \dots \wedge A\right \Big\ \\ & = \Big\ A\wedge A\wedge \dots \wedge A \Big\ \\ & = \lambda_1(A) \lambda_2(A) \cdots \lambda_k(A) .\end{align*} It follows that $$\sum_{k = 1}^n \varphi(\lambda_k(A)) \le \sum_{k=1}^n\varphi(\lambda_k(A)) ,$$ for any $\varphi$ such that $t \rightarrow \varphi(e^t)$ is convex nondecreasing.


1Actually your answer does answer the original question, by creating weak majorization inequalities for the entire range, rather than just the $k=1,..,n$ case. – Suvrit Oct 26 '14 at 23:58