Trace & Norms

Proof (sketch):

Properties 1, 2 follow immediately from the diagonal-sum definition and the linearity of summation. For Property 3, note that \((A^\top)_{ii} = a_{ii}\), so \(\operatorname{tr}(A^\top) = \sum_i (A^\top)_{ii} = \sum_i a_{ii} = \operatorname{tr}(A)\).

For Property 5, compute directly from the definitions of trace and matrix product: \[ \begin{align*} \operatorname{tr}(AB) &= \sum_{i=1}^n (AB)_{ii} \\\\ &= \sum_{i=1}^n \sum_{j=1}^n a_{ij} b_{ji} \\\\ &= \sum_{j=1}^n \sum_{i=1}^n b_{ji} a_{ij} \\\\ &= \sum_{j=1}^n (BA)_{jj} \\\\ &= \operatorname{tr}(BA), \end{align*} \] where the middle equality interchanges the order of a finite double sum.

Property 4 follows from the same kind of direct computation. It does not require Property 5. Expanding the product entrywise: \[ \begin{align*} \operatorname{tr}(A^\top B) &= \sum_{i=1}^n (A^\top B)_{ii} \\\\ &= \sum_{i=1}^n \sum_{j=1}^n (A^\top)_{ij} b_{ji} \\\\ &= \sum_{i=1}^n \sum_{j=1}^n a_{ji} b_{ji}. \end{align*} \] Renaming dummy indices (swap \(i \leftrightarrow j\)) gives \(\sum_{i=1}^n \sum_{j=1}^n a_{ij} b_{ij}\), matching the stated form.

Property 6 requires the characteristic polynomial. Write \(p_A(\lambda) = \det(\lambda I - A)\), which has the same roots as \(\det(A - \lambda I)\) because the two differ by the factor \((-1)^n\). We first show by induction on \(n\) that \(p_A\) is a monic polynomial of degree \(n\) whose coefficient of \(\lambda^{n-1}\) is \(-\operatorname{tr}(A)\). For \(n = 1\) it is \(\lambda - a_{11}\). For \(n \geq 2\), expand \(\det(\lambda I - A)\) along the first row as in the definition of the determinant. The term \(j = 1\) is \((\lambda - a_{11}) \det(\lambda I - A_{11})\), where \(A_{11}\) is \(A\) with its first row and column deleted, and by the induction hypothesis this equals \(\lambda^n - (a_{11} + \operatorname{tr}(A_{11}))\lambda^{n-1} + \cdots = \lambda^n - \operatorname{tr}(A)\lambda^{n-1} + \cdots\). For \(j \geq 2\) the term is \((-1)^{1+j}(-a_{1j})\) times the determinant of a minor in which only \(n - 2\) rows contain \(\lambda\). Since every product in the cofactor expansion uses exactly one entry from each row, that term has degree at most \(n - 2\). Over \(\mathbb{C}\), the fundamental theorem of algebra factors the monic polynomial \(p_A\) as \(\prod_{i=1}^n (\lambda - \lambda_i)\), where the \(\lambda_i\) are its roots counted with multiplicity, that is, the eigenvalues of \(A\) counted with algebraic multiplicity. Comparing the coefficient of \(\lambda^{n-1}\) gives \(\operatorname{tr}(A) = \sum_i \lambda_i\).

Proof:

Existence.
By the spectral theorem, \(S\) has a factorization \(S = Q \Lambda Q^\top\) with \(Q\) orthogonal and \(\Lambda = \operatorname{diag}(\lambda_1, \ldots, \lambda_n)\). Fix any such factorization and write \(\mathbf{q}_i = Q\mathbf{e}_i\) for the \(i\)-th column of \(Q\). Positive semidefiniteness gives \[ \lambda_i = \mathbf{e}_i^\top \Lambda \mathbf{e}_i = \mathbf{q}_i^\top S \mathbf{q}_i \geq 0. \] Set \(R = Q \Lambda_+ Q^\top\) with \(\Lambda_+ = \operatorname{diag}(\sqrt{\lambda_1}, \ldots, \sqrt{\lambda_n})\). Then \(R\) is symmetric, \[ \begin{align*} R^2 &= Q \Lambda_+ Q^\top Q \Lambda_+ Q^\top \\\\ &= Q \Lambda_+^2 Q^\top = S, \end{align*} \] and for every \(\mathbf{x} \in \mathbb{R}^n\), putting \(\mathbf{y} = Q^\top \mathbf{x}\), \[ \begin{align*} \mathbf{x}^\top R \mathbf{x} &= \mathbf{y}^\top \Lambda_+ \mathbf{y} \\\\ &= \sum_{i=1}^n \sqrt{\lambda_i}\, y_i^2 \geq 0. \end{align*} \] So \(R\) is a symmetric positive semidefinite square root of \(S\), and it satisfies \(R\mathbf{q}_i = Q \Lambda_+ \mathbf{e}_i = \sqrt{\lambda_i}\, \mathbf{q}_i\) for every \(i\).

Uniqueness.
Let \(R'\) be any symmetric positive semidefinite matrix with \(R'^2 = S\). Then \(R'S = R'^3 = SR'\). Fix an eigenvalue \(\mu\) of \(S\) and let \(E_\mu = \{\mathbf{v} \in \mathbb{R}^n : S\mathbf{v} = \mu\mathbf{v}\}\), of dimension \(k \geq 1\). For \(\mathbf{v} \in E_\mu\) we have \(S(R'\mathbf{v}) = R'S\mathbf{v} = \mu R'\mathbf{v}\), so \(R'\) maps \(E_\mu\) into itself. Let \(P \in \mathbb{R}^{n \times k}\) have as columns an orthonormal basis \(\mathbf{p}_1, \ldots, \mathbf{p}_k\) of \(E_\mu\) (the Gram-Schmidt process followed by normalization provides one). By the coordinate formula for an orthogonal basis, every \(\mathbf{v} \in E_\mu\) satisfies \(\mathbf{v} = \sum_{j=1}^k (\mathbf{p}_j^\top \mathbf{v})\, \mathbf{p}_j = PP^\top \mathbf{v}\). Every column of \(R'P\) lies in \(E_\mu\), so \(R'P = PC\) with \(C = P^\top R' P \in \mathbb{R}^{k \times k}\).

The matrix \(C\) is symmetric, so the spectral theorem gives \(C = Z \Gamma Z^\top\) with \(Z\) orthogonal and \(\Gamma = \operatorname{diag}(\gamma_1, \ldots, \gamma_k)\). The columns of \(PZ\) are orthonormal, since \((PZ)^\top PZ = Z^\top P^\top P Z = I_k\), and they lie in \(E_\mu\). Orthonormal vectors are linearly independent, and there are \(k = \dim E_\mu\) of them, so they form an orthonormal basis of \(E_\mu\). Moreover \(R'PZ = PCZ = PZ\Gamma\), so the \(j\)-th column \(\mathbf{u}\) of \(PZ\) satisfies \(R'\mathbf{u} = \gamma_j \mathbf{u}\). Then \(\gamma_j = \mathbf{u}^\top R' \mathbf{u} \geq 0\) and \[ \gamma_j^2 \mathbf{u} = R'^2 \mathbf{u} = S\mathbf{u} = \mu \mathbf{u}, \] so \(\gamma_j = \sqrt{\mu}\). Hence \(R'\) acts as \(\sqrt{\mu}\) on a basis of \(E_\mu\), that is, \(R'\mathbf{v} = \sqrt{\mu}\,\mathbf{v}\) for every \(\mathbf{v} \in E_\mu\).

Finally, each column \(\mathbf{q}_i\) of \(Q\) satisfies \(S\mathbf{q}_i = Q\Lambda\mathbf{e}_i = \lambda_i \mathbf{q}_i\), so \(\mathbf{q}_i \in E_{\lambda_i}\) and therefore \[ R'\mathbf{q}_i = \sqrt{\lambda_i}\,\mathbf{q}_i = R\mathbf{q}_i. \] The \(\mathbf{q}_i\) form a basis of \(\mathbb{R}^n\), so \(R' = R\). In particular \(R\) does not depend on the chosen factorization of \(S\), which justifies the formula in the theorem.

Proof:

Let \(A = U\Sigma V^\top\) be an SVD of \(A\), with \(U \in \mathbb{R}^{m \times m}\) and \(V \in \mathbb{R}^{n \times n}\) orthogonal and \(\Sigma \in \mathbb{R}^{m \times n}\) containing the singular values \(\sigma_1 \geq \cdots \geq \sigma_{\min(m,n)} \geq 0\) on its diagonal. Since \(U^\top U = I_m\), \[ A^\top A = V \Sigma^\top U^\top U \Sigma V^\top = V (\Sigma^\top \Sigma) V^\top, \] where \(\Sigma^\top \Sigma \in \mathbb{R}^{n \times n}\) is diagonal with entries \(\sigma_1^2, \ldots, \sigma_{\min(m,n)}^2\) (padded with zeros if \(n \gt m\)). The displayed identity is a factorization of the kind used in the square root theorem, with \(S = A^\top A\), \(Q = V\), and \(\Lambda = \Sigma^\top \Sigma\). That theorem therefore gives the square root by taking nonnegative square roots of the diagonal entries \(\sigma_i^2\) and of the padded zeros, namely \(\sqrt{\sigma_i^2} = \sigma_i\) (as \(\sigma_i \geq 0\)) and \(0\): \[ \begin{align*} \sqrt{A^\top A} &= V \, \Sigma_+ \, V^\top, \\\\ \Sigma_+ &= \operatorname{diag}(\sigma_1, \ldots, \sigma_{\min(m,n)}, 0, \ldots, 0). \end{align*} \]

Here \(\Sigma_+ \in \mathbb{R}^{n \times n}\), so \(\sqrt{A^\top A}\) is an \(n \times n\) matrix and its trace is well-defined. By the cyclic permutation property of trace (Property 5) together with \(V^\top V = I_n\), \[ \begin{align*} \operatorname{tr}\!\left(\sqrt{A^\top A}\right) &= \operatorname{tr}(V \Sigma_+ V^\top) \\\\ &= \operatorname{tr}(\Sigma_+ V^\top V) \\\\ &= \operatorname{tr}(\Sigma_+) \\\\ &= \sum_{i=1}^{\min(m,n)} \sigma_i \\\\ &= \|A\|_{\ast}. \end{align*} \]

Derivation:

Let \(A = U \Sigma V^\top\) be an SVD with \(U, V\) orthogonal and singular values ordered as \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{\min(m,n)} \geq 0\). The remaining singular values \(\sigma_i\), \(\min(m,n) \lt i \leq n\), vanish, since \(A^\top A\) has rank at most \(m\). For any \(\mathbf{x} \in \mathbb{R}^n\) with \(\|\mathbf{x}\|_2 = 1\), set \(\mathbf{y} = V^\top \mathbf{x}\). Since \(V\) is orthogonal, \(\|\mathbf{y}\|_2 = \|\mathbf{x}\|_2 = 1\) by the norm-preserving property. Similarly \(U\) preserves norms, so: \[ \begin{align*} \|A \mathbf{x}\|_2^2 &= \|U \Sigma V^\top \mathbf{x}\|_2^2 \\\\ &= \|\Sigma \mathbf{y}\|_2^2 \\\\ &= \sum_{i=1}^n \sigma_i^2 \, y_i^2. \end{align*} \] Bounding above by the largest singular value, \[ \begin{align*} \|A \mathbf{x}\|_2^2 &= \sum_{i=1}^n \sigma_i^2 y_i^2 \\\\ &\leq \sigma_1^2 \sum_{i=1}^n y_i^2 \\\\ &= \sigma_1^2. \end{align*} \] Equality is achieved by \(\mathbf{y} = \mathbf{e}_1\) (equivalently \(\mathbf{x} = V \mathbf{e}_1\), the first right singular vector), which gives \(\|A\mathbf{x}\|_2^2 = \sigma_1^2\). Thus \(\|A\|_2 = \sigma_1 = \sigma_{\max}\). The equality \(\sigma_{\max} = \sqrt{\lambda_{\max}(A^\top A)}\) follows directly from the definition of singular values as \(\sigma_i = \sqrt{\lambda_i(A^\top A)}\).

Proof:

Each \(d_i\) is an eigenvalue, since \(AQ\mathbf{e}_i = Q\Lambda Q^\top Q\mathbf{e}_i = Q\Lambda\mathbf{e}_i = d_i\, Q\mathbf{e}_i\) and \(Q\mathbf{e}_i \neq \mathbf{0}\). Conversely, if \(A\mathbf{v} = \lambda\mathbf{v}\) with \(\mathbf{v} \neq \mathbf{0}\), then \(\mathbf{y} = Q^\top\mathbf{v} \neq \mathbf{0}\) satisfies \(\Lambda\mathbf{y} = \lambda\mathbf{y}\), that is, \(d_i y_i = \lambda y_i\) for every \(i\). Choosing \(i\) with \(y_i \neq 0\) gives \(\lambda = d_i\).

Since \(A\) is symmetric, \(A^\top A = A^2 = Q\Lambda^2 Q^\top\), and \(\Lambda^2 = \operatorname{diag}(d_1^2, \ldots, d_n^2)\). The argument just given, applied to this factorization of the symmetric matrix \(A^\top A\), shows that the set of eigenvalues of \(A^\top A\) is \(\{d_1^2, \ldots, d_n^2\}\). By the spectral norm formula, \[ \begin{align*} \|A\|_2 &= \sqrt{\lambda_{\max}(A^\top A)} \\\\ &= \sqrt{\max_{i} d_i^2} \\\\ &= \max_{i} |d_i|. \end{align*} \]

Proof:

Upper bound.
Let \(A = U\Sigma V^\top\) be an SVD as in the proof of the nuclear norm via SVD, so that all off-diagonal entries of \(\Sigma\) vanish and \(\Sigma_{ii} = \sigma_i\) for \(1 \leq i \leq \min(m,n)\). Fix \(W \in \mathbb{R}^{m \times n}\) with \(\|W\|_2 \leq 1\) and put \(M = U^\top W V \in \mathbb{R}^{m \times n}\). The cyclic property of the trace (Property 5, applied to the \(n \times n\) product \((W^\top U \Sigma) V^\top\)) and \(V^\top W^\top U = M^\top\) give \[ \begin{align*} \operatorname{tr}(W^\top A) &= \operatorname{tr}(W^\top U \Sigma V^\top) \\\\ &= \operatorname{tr}(V^\top W^\top U \Sigma) \\\\ &= \operatorname{tr}(M^\top \Sigma) \\\\ &= \sum_{i=1}^{\min(m,n)} \sigma_i \, M_{ii}, \end{align*} \] where the last step is Property 4 for \(m \times n\) matrices, with only the diagonal entries of \(\Sigma\) contributing.

Next, \(\|M\|_2 = \|W\|_2\). Indeed, \(U^\top\) is orthogonal (since \(UU^\top = I_m\)), so \(U^\top\) preserves Euclidean length on \(\mathbb{R}^m\) and \(V\) preserves it on \(\mathbb{R}^n\), by the norm-preserving property. Hence, for \(\mathbf{x} \in \mathbb{R}^n\), \(\|M\mathbf{x}\|_2 = \|W(V\mathbf{x})\|_2\) and \(\|V\mathbf{x}\|_2 = \|\mathbf{x}\|_2\). As \(\mathbf{x}\) runs over the unit sphere of \(\mathbb{R}^n\), so does \(V\mathbf{x}\) (with inverse \(V^\top\)), and the two maxima in the induced norm coincide. Now \(M_{ii}\) is the \(i\)-th entry of \(M\mathbf{e}_i\), so \[ \begin{align*} |M_{ii}| &\leq \|M\mathbf{e}_i\|_2 \\\\ &\leq \|M\|_2 \, \|\mathbf{e}_i\|_2 \\\\ &= \|W\|_2 \leq 1. \end{align*} \] Since every \(\sigma_i \geq 0\), \[ \begin{align*} \operatorname{tr}(W^\top A) &\leq \sum_{i=1}^{\min(m,n)} \sigma_i \, |M_{ii}| \\\\ &\leq \sum_{i=1}^{\min(m,n)} \sigma_i \\\\ &= \|A\|_{\ast}. \end{align*} \]

The bound is attained.
Let \(J \in \mathbb{R}^{m \times n}\) have \(J_{ii} = 1\) for \(1 \leq i \leq \min(m,n)\) and all other entries \(0\), and put \(W_0 = UJV^\top\). The matrix \(M\) built from \(W_0\) is \(U^\top U J V^\top V = J\), so \(\|W_0\|_2 = \|J\|_2\) by the previous paragraph. For \(\mathbf{x} \in \mathbb{R}^n\), \(\|J\mathbf{x}\|_2^2 = \sum_{i=1}^{\min(m,n)} x_i^2 \leq \|\mathbf{x}\|_2^2\), with equality at \(\mathbf{x} = \mathbf{e}_1\), so \(\|W_0\|_2 = 1\). The computation above gives \(\operatorname{tr}(W_0^\top A) = \sum_i \sigma_i J_{ii} = \|A\|_{\ast}\). Hence the maximum exists and equals \(\|A\|_{\ast}\).

Norm properties.
If \(\|A\|_{\ast} = 0\), the nonnegative numbers \(\sigma_i\) sum to zero, so \(\Sigma = 0\) and \(A = U\Sigma V^\top = 0\). Conversely, every eigenvalue of \(0^\top 0 = 0\) is zero, so all singular values of the zero matrix vanish. For homogeneity, the linearity of the trace gives \(\operatorname{tr}(W^\top (cA)) = c\,\operatorname{tr}(W^\top A)\). If \(c \geq 0\), taking the maximum over \(W\) gives \(\|cA\|_{\ast} = c\|A\|_{\ast}\). If \(c \lt 0\), write \(c\,\operatorname{tr}(W^\top A) = |c|\operatorname{tr}((-W)^\top A)\) and note that \(W \mapsto -W\) maps the set \(\{\|W\|_2 \leq 1\}\) onto itself (since \(\|(-W)\mathbf{x}\|_2 = \|W\mathbf{x}\|_2\) for every \(\mathbf{x}\)), so again \(\|cA\|_{\ast} = |c|\,\|A\|_{\ast}\). For the triangle inequality, every \(W\) with \(\|W\|_2 \leq 1\) satisfies \[ \begin{align*} \operatorname{tr}(W^\top (A + B)) &= \operatorname{tr}(W^\top A) + \operatorname{tr}(W^\top B) \\\\ &\leq \|A\|_{\ast} + \|B\|_{\ast} \end{align*} \] by the upper bound, and taking the maximum over \(W\) gives \(\|A + B\|_{\ast} \leq \|A\|_{\ast} + \|B\|_{\ast}\).