Chapter 7 — Trace and Determinant

Solution — (1)

\( \tr(AB) = \sum_{i=1}^{n} (AB)_{ii} \), and \( (AB)_{ii} = \sum_{k=1}^{n} a_{ik} b_{ki} \) (the diagonal elements of \( AB \)). Hence \[\begin{aligned} \tr(AB) &= \sum_{i=1}^{n}\sum_{k=1}^{n} a_{ik} b_{ki} \\ &= \sum_{k=1}^{n}\sum_{i=1}^{n} b_{ki} a_{ik} = \sum_{k=1}^{n} (BA)_{kk} = \tr(BA). \end{aligned}\] \( \therefore\ \tr(AB) = \tr(BA) \quad \forall\, A, B \in \F^{n\times n}. \)

Solution — (2)

\( (A\herm)_{ij} = \overline{a_{ji}} = \overline{(A)_{ji}} \). With \( (AB)_{ij} = \sum_{k} a_{ik} b_{kj} \) (summing over the shared index), \[ (A\herm A)_{ij} = \sum_{k=1}^{m} \overline{a_{ki}}\, a_{kj}. \] So \[ \tr(A\herm A) = \sum_{i=1}^{n} (A\herm A)_{ii} = \sum_{i=1}^{n}\sum_{k=1}^{m} \overline{a_{ki}}\, a_{ki} = \sum_{i=1}^{n}\sum_{k=1}^{m} |a_{ki}|^2 \qquad \big( |z|^2 = \overline{z}\,z = z\,\overline{z} \big). \] Therefore \( \tr(A\herm A) = \|A\|_F^2 \). Since \( \tr(AB) = \tr(BA) \), we also have \( \tr(AA\herm) = \tr(A\herm A) \), and so \[ \|A\|_F^2 = \tr(A\herm A) = \tr(AA\herm). \]

Solution — (3)

For \( u \in \R^n \), \( \|u\|^2 = u \cdot u = u_1^2 + \dots + u_n^2 \). Now \[ uu\T = \begin{bmatrix} u_1 \\ \vdots \\ u_n \end{bmatrix}_{n\times 1} \begin{bmatrix} u_1 & \cdots & u_n \end{bmatrix}_{1\times n} = (\text{an } n\times n \text{ matrix}), \qquad (uu\T)_{ij} = u_i u_j. \] Hence \( \tr(uu\T) = \sum_{i=1}^{n} u_i \cdot u_i = \sum_{i=1}^{n} u_i^2 = \|u\|^2. \)

Solution — (4)

For \( u \in \C^n \), \( \|u\|^2 = |u_1|^2 + \dots + |u_n|^2 \) (for \( z \in \C \), \( |z|^2 = z\overline{z} = \overline{z}z \)). Since \( (uu\herm)_{ij} = u_i \overline{u_j} \), \[ \tr(uu\herm) = \sum_{i=1}^{n} u_i \overline{u_i} = \sum_{i=1}^{n} |u_i|^2 = \|u\|^2. \]

Solution — (5)

From Ch. 3, \( M \sim N \) iff there is an invertible matrix \( P \) such that \( M = PNP^{-1} \). So \( A \sim B \implies \exists\, P : A = PBP^{-1} \), and \[\begin{aligned} \tr(A) &= \tr(PBP^{-1}) = \tr\big((PB)P^{-1}\big) \\ &= \tr\big(P^{-1}(PB)\big) = \tr(IB) = \tr(B) \qquad (\text{as } \tr(AB) = \tr(BA)). \end{aligned}\] \( \therefore\ \tr(A) = \tr(B). \)

Solution

From Ch. 3 (Ex 37), if \( M \) and \( N \) are two matrix representations of a linear operator corresponding to two different bases, then \( M \sim N \).

Let \( T \in \Lin(V) \), and let \( \phi \) and \( \psi \) be the coordinate maps for the two bases of \( V \). Then \[ T = \phi^{-1} A\, \phi = \psi^{-1} B\, \psi \implies A = \phi\psi^{-1} B\, \psi\phi^{-1}. \] Put \( P = \phi\psi^{-1} \Rightarrow P^{-1} = \psi\phi^{-1} \). Then \( A = PBP^{-1} \implies A \sim B \). By Ex 73 (5), \( \tr A = \tr B \), so we are done.

Solution

\( [n] = \{1, 2, \dots, n\} \). Filling the \( n \) positions:

• 1st position: \( n \) choices
• 2nd position: \( n-1 \) choices
• \( \vdots \)
• \( (n-1) \)th position: \( 2 \) choices
• \( n \)th position: \( 1 \) choice

\[ n \times (n-1) \times (n-2) \times \dots \times 1 = n!. \qquad \therefore\ |\Pi_n| = n!. \]

Solution

For a transposition, choose any two positions to exchange. Choosing 2 out of \( n \): \( {}^{n}C_{2} = \dfrac{n(n-1)}{2} \). Hence \[ |T_n| = {}^{n}C_{2} = \frac{n(n-1)}{2}, \qquad \text{while}\quad |\Pi_n| = n! = n(n-1)(n-2)\cdots 2 \cdot 1. \]

Solution

Define a cycle \( (a_1\, a_2 \cdots a_k) \) by \[ \sigma(a_i) = \begin{cases} a_{i+1} & 1 \le i < k \\ a_1 & i = k \\ a_i & \text{for all other } i \end{cases} \]

For \( \sigma \in \Pi_n \), define a relation \( \sim\ \subseteq [n] \times [n] \) by \[ \forall\, a, b \in [n], \quad a \sim b \iff \exists\, n \in \Z : \sigma^{n}(a) = b. \] This is an equivalence relation:

• \( x \sim x \), as \( \sigma^{0} = x \quad \forall\, x \in [n] \).  (reflexive)
• \( x \sim y \implies \sigma^{n}(x) = y \) for some \( n \in \Z \implies x = \sigma^{-n}(y) \implies y \sim x \), \( \forall\, x, y \in [n] \).  (symmetric)
• \( x \sim y \) and \( y \sim z \implies \sigma^{n}(x) = y,\ \sigma^{m}(y) = z \implies \sigma^{n+m}(x) = z \implies x \sim z \), \( \forall\, x, y, z \in [n] \).  (transitive)

Thus \( \sim \) partitions \( [n] \) into orbits, and each orbit corresponds to a cycle (since \( \sigma \) is a bijection, \( \sigma^{k}(a) = a \) after some \( k \) steps). So any permutation \( \sigma \in \Pi_n \) decomposes into disjoint cycles.

Each cycle decomposes into transpositions: \[ (a_1\, a_2 \cdots a_k) = (a_1\, a_k)(a_1\, a_{k-1}) \cdots (a_1\, a_2) = \tau_1 \circ \dots \circ \tau_{k-1}. \] Doing this for each disjoint cycle, any permutation breaks down into a composition of transpositions.

Solution

First, the identity permutation \( \sigma_I(x) = x \) can be written as \( \sigma_I = (1\,2)(1\,2) \) — exchange the first two elements, then exchange again — so \( \sigma_I \) has even parity.

Now take \( \sigma = \tau_1 \circ \dots \circ \tau_k = s_1 \circ \dots \circ s_l \). Since a transposition exchanges just two elements, it is its own inverse: \( \tau_i^{-1} = \tau_i\ (1 \le i \le k) \), \( s_j^{-1} = s_j\ (1 \le j \le l) \). So \[ \sigma^{-1} = \tau_k \circ \dots \circ \tau_1 = s_l \circ \dots \circ s_1, \] and therefore \[ \sigma_I = \sigma\sigma^{-1} = \underbrace{\tau_1 \circ \dots \circ \tau_k \circ s_l \circ \dots \circ s_1}_{k + l \text{ transpositions}}. \] Since \( \sigma_I \) has even parity, \( k + l \) must be even \( \implies \) both \( k \) and \( l \) are odd, or both are even.

Solution — (1)

Let \( \sigma = \tau_1 \circ \dots \circ \tau_k \) and \( s = s_1 \circ \dots \circ s_l \) (compositions of transpositions). Then \( \sigma s = \tau_1 \circ \dots \circ \tau_k \circ s_1 \circ \dots \circ s_l \), so \[ \sign(\sigma s) = (-1)^{k+l} = (-1)^{k}(-1)^{l} = \sign(\sigma)\,\sign(s). \]

Solution — (2)

Take any \( w \in \Pi_n \). From \( \sigma s = w \) we get \( s = \sigma^{-1} w \); and from \( s\sigma = \theta \) (with \( \theta \in \Pi_n \)) we get \( s = \theta\sigma^{-1} \). Since \( \sigma \) is bijective, \( \sigma^{-1} \in \Pi_n \). Hence any \( s \in \Pi_n \) can be written as \( s = \sigma^{-1} w \) or \( s = \theta\sigma^{-1} \).

So for any \( \tau \in \Pi_n \), \[ \tau = \sigma s = \sigma(\sigma^{-1} w) = w, \qquad \text{or} \qquad \tau = s\sigma = (\theta\sigma^{-1})\sigma = \theta. \] Thus \( \Pi_n = \{ \sigma s : s \in \Pi_n \} = \{ s\sigma : s \in \Pi_n \}\ \forall\, \sigma \in \Pi_n. \)

Solution — (3)

\( \sigma \) is bijective, so \( \sigma^{-1} \) exists and \( \sigma^{-1} \in \Pi_n \); hence \( \{ \sigma^{-1} : \sigma \in \Pi_n \} \subseteq \Pi_n \). We can also write \( \sigma = (\sigma^{-1})^{-1} \) for any \( \sigma \in \Pi_n \) — every permutation is the inverse of some permutation. So \( \Pi_n = \{ \sigma^{-1} : \sigma \in \Pi_n \} \).