Prove that $\text{tr}(((A+B)^T(A+B))^{1/2}) \leq \text{tr}((A^TA)^{1/2}) + \text{tr}((B^TB)^{1/2})$ I'm trying to show that the nuclear norm (sum of singular values of the matrix) is actually a valid matrix norm. I know that
$$\sum\limits_{i=1}^n \sigma_i(A) = \text{tr}((A^TA)^{1/2})$$
So now what is left to prove is triangle inequality
$$\text{tr}(((A+B)^T(A+B))^{1/2}) \leq \text{tr}((A^TA)^{1/2}) + \text{tr}((B^TB)^{1/2}) \quad \forall A,B\in M_{n\times n}(\mathbf{R})$$
Which is what I'm currently stuck at. Any help would be appreciated.
UPD. What vector norm the matrix norm $\text{tr}((A^TA)^{1/2})$ is associated to?
 A: The quantity $\|A\| = \sqrt{\langle A,A\rangle} = \operatorname{Tr}(A^TA)^{1/2}$ is a norm.
If you agree that $\langle A,B\rangle = \operatorname{Tr}(B^TA)$ is an inner product, then this inner product obeys the Cauchy-Schwarz inequality $|\langle A,B\rangle| \le \|A\|\|B\|$.
Therefore
\begin{align}
\|A+B\|^2 &= \langle A+B, A+B\rangle \\
&= \langle A,A\rangle + \langle A,B\rangle  + \langle B,A\rangle  + \langle B,B\rangle \\
&=\|A\|^2 + 2\langle A,B\rangle + \|B\|^2\\
&\le \|A\|^2 + 2|\langle A,B\rangle| + \|B\|^2\\
&\le \|A\|^2 + 2\|A\|\|B\| + \|B\|^2\\
&= (\|A\| + \|B\|)^2
\end{align}
so $\|A+B\| \le \|A\| + \|B\|$.
This matrix norm is not associated with any vector norm because for the identity matrix we have $\|I\| = \sqrt{n}$, and induced norms must satisfy $\|I\| = 1$.

The above discussion was for the norm $\|A\|_2 = [\operatorname{Tr}(A^TA)]^{1/2}$. This is about the norm $\|A\|_1 = \operatorname{Tr}[(A^TA)^{1/2}] =  \operatorname{Tr}|A|$ where $|A| = (A^TA)^{1/2}$.
Lemma $1$

For any matrix $A$ and two orthonormal bases $E = \{e_1, \ldots, e_n\}$ and $F = \{f_1, \ldots, f_n\}$ we have
  $$\sum_{i=1}^n \|Ae_i\|^2 = \sum_{i=1}^n \|Af_i\|^2$$
  In particular we have $\|A\|_2^2 = \sum_{i=1}^n \|Ae_i\|^2$.

Proof.
$$\sum_{i=1}^n \|Ae_i\|^2 = \sum_{i=1}^n \sum_{j=1}^n |\langle Ae_i, f_j\rangle|^2 =  \sum_{i=1}^n \sum_{j=1}^n |\langle e_i, A^Tf_j\rangle|^2 = \sum_{j=1}^n \|A^Tf_j\|^2$$
Applying this to $F$ and $F$ gives $\sum_{j=1}^n \|Af_j\|^2 = \sum_{j=1}^n \|A^Tf_j\|^2$ which completes the proof.
Let $G = \{g_1, \ldots, g_n\}$ be the orthonormal basis in which $A^TA$ diagonalizes with $A^TAg_i = \lambda g_i$. We have $$\|A\|_2^2 = \operatorname{Tr}(A^TA) = \sum_{i=1}^n \lambda_i = \sum_{i=1}^n \langle A^TAg_i, g_i\rangle = \sum_{i=1}^n \|Ag_i\|^2$$
Lemma $2$

For any positive matrix $A$ and two orthonormal bases $E = \{e_1, \ldots, e_n\}$ and $F = \{f_1, \ldots, f_n\}$ we have
  $$\sum_{i=1}^n \langle Ae_i, e_i\rangle = \sum_{i=1}^n \langle Af_i, f_i\rangle $$
  In particular, for any matrix $A$ we have $\|A\|_1 = \sum_{i=1}^n \langle |A|e_i, e_i\rangle = \||A|^{1/2}\|_2^2$.

Proof.
It follows from Lemma $1$:
$$\sum_{i=1}^n \langle Ae_i, e_i\rangle = \sum_{i=1}^n \|A^{1/2}e_i\|^2 = \sum_{i=1}^n \|A^{1/2}f_i\|^2 = \sum_{i=1}^n \langle Af_i, f_i\rangle$$
Let $G = \{g_1, \ldots, g_n\}$ be the orthonormal basis in which $|A|$ diagonalizes with $|A|g_i = \lambda_i g_i$. We have
$$\|A\|_1 = \operatorname{Tr}|A| = \sum_{i=1}^n \lambda_i = \sum_{i=1}^n \langle |A|g_i, g_i\rangle = \sum_{i=1}^n \||A|^{1/2}g_i\|^2 = \||A|^{1/2}\|_2^2$$
To prove the triangle inequality for $\|\cdot\|_1$ for the matrices $A$ and $B$, let $A = V|A|$, $B = W|B|$ and $A+B = U|A+B|$ be the respective polar decompositions, with $V,W,U$ unitary.
For any orthonormal basis $\{e_1,\ldots, e_n\}$ we have
\begin{align}
\|A+B\|_1 &= \sum_{i=1}^n \langle |A+B|e_i, e_i\rangle\\
&= \sum_{i=1}^n \langle U^*(A+B)e_i, e_i\rangle\\
&= \sum_{i=1}^n \langle (A+B)e_i, Ue_i\rangle\\
&= \sum_{i=1}^n \Big(\langle Ae_i, Ue_i\rangle + \langle Be_i, Ue_i\rangle\Big)\\
&= \sum_{i=1}^n \Big(\langle V|A|e_i, Ue_i\rangle + \langle W|B|e_i, Ue_i\rangle\Big)\\
&= \sum_{i=1}^n \Big(\langle |A|e_i, V^*Ue_i\rangle + \langle |B|e_i, W^*Ue_i\rangle\Big)\\
&= \sum_{i=1}^n \Big(\langle |A|^{1/2}e_i, |A|^{1/2}V^*Ue_i\rangle + \langle |B|^{1/2}e_i, |B|^{1/2}W^*Ue_i\rangle\Big)\\
&\le \left(\sum_{i=1}^n \||A|^{1/2}e_i\|^2\right)^{1/2}\left(\sum_{i=1}^n\||A|^{1/2}V^*Ue_i\|^2\right)^{1/2} + \left(\sum_{i=1}^n \||B|^{1/2}e_i\|^2\right)^{1/2}\left(\sum_{i=1}^n\||B|^{1/2}W^*Ue_i\|^2\right)^{1/2}\\
&= \||A|^{1/2}\|_2^2 + \||B|^{1/2}\|_2^2\\
&= \|A\|_1 + \|B\|_1
\end{align}
A: By padding the matrices with zeroes, we may assume that they are square. For any real square matrix $X$, let $X=USV^T$ be its singular value decomposition. Since $S$ is a nonnegative diagonal matrix and the diagonal entries of every real orthogonal matrix $W$ are bounded above by $1$, we have $\operatorname{tr}(S)=\max_{W^TW=I}\operatorname{tr}(SW)$. In turn, we have the following characterisation of the nuclear norm:
$$
\|X\|:=\operatorname{tr}\left((X^TX)^{1/2}\right)
=\operatorname{tr}(S)
=\max_{W^TW=I}\operatorname{tr}(SW)
=\max_{Q^TQ=I}\operatorname{tr}(XQ).
$$
Now the triangle inequality follows directly:
$$
\|A+B\|
=\max_{Q^TQ=I}\operatorname{tr}\left((A+B)Q\right)
\le\max_{Q^TQ=I}\operatorname{tr}\left(AQ\right)
+\max_{Q^TQ=I}\operatorname{tr}\left(BQ\right)
=\|A\|+\|B\|.
$$
