Linear Algebra/Determinants Exist/Solutions

Solutions

These summarize the notation used in this book for the $2$ - and $3$ - permutations.

$\begin{matrix} i & 1 & 2 \\ ϕ_{1} (i) & 1 & 2 \\ ϕ_{2} (i) & 2 & 1 \end{matrix} \begin{matrix} i & 1 & 2 & 3 \\ ϕ_{1} (i) & 1 & 2 & 3 \\ ϕ_{2} (i) & 1 & 3 & 2 \\ ϕ_{3} (i) & 2 & 1 & 3 \\ ϕ_{4} (i) & 2 & 3 & 1 \\ ϕ_{5} (i) & 3 & 1 & 2 \\ ϕ_{6} (i) & 3 & 2 & 1 \end{matrix}$

Problem 1

Give the permutation expansion of a general $2 \times 2$ matrix and its transpose.

Answer

This is the permutation expansion of the determinant of a $2 \times 2$ matrix

| \begin{matrix} a & b \\ c & d \end{matrix} | = a d \cdot | \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} | + b c \cdot | \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} |

and the permutation expansion of the determinant of its transpose.

| \begin{matrix} a & c \\ b & d \end{matrix} | = a d \cdot | \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} | + c b \cdot | \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} |

As with the $3 \times 3$ expansions described in the subsection, the permutation matrices from corresponding terms are transposes (although this is disguised by the fact that each is self-transpose).

This exercise is recommended for all readers.

Problem 2

This problem appears also in the prior subsection.

Find the inverse of each $2$ -permutation.
Find the inverse of each $3$ -permutation.

Answer

Each of these is easy to check.

permutation $ϕ_{1}$ $ϕ_{2}$
inverse $ϕ_{1}$ $ϕ_{2}$

permutation	$ϕ_{1}$	$ϕ_{2}$	$ϕ_{3}$	$ϕ_{4}$	$ϕ_{5}$	$ϕ_{6}$
inverse	$ϕ_{1}$	$ϕ_{2}$	$ϕ_{3}$	$ϕ_{5}$	$ϕ_{4}$	$ϕ_{6}$

This exercise is recommended for all readers.

Problem 3

Find the signum of each $2$ -permutation.
Find the signum of each $3$ -permutation.

Answer

$sgn (ϕ_{1}) = + 1$ , $sgn (ϕ_{2}) = - 1$
$sgn (ϕ_{1}) = + 1$ , $sgn (ϕ_{2}) = - 1$ , $sgn (ϕ_{3}) = - 1$ , $sgn (ϕ_{4}) = + 1$ , $sgn (ϕ_{5}) = + 1$ , $sgn (ϕ_{6}) = - 1$

Problem 4

What is the signum of the $n$ -permutation $ϕ = ⟨ n, n - 1, \dots, 2, 1 ⟩$ ? (Strang 1980)

Answer

The pattern is this.

$\begin{matrix} i & 1 & 2 & 3 & 4 & 5 & 6 & \dots \\ sgn (ϕ_{i}) & + 1 & - 1 & - 1 & + 1 & + 1 & - 1 & \dots \end{matrix}$

So to find the signum of $ϕ_{n!}$ , we subtract one $n! - 1$ and look at the remainder on division by four. If the remainder is $1$ or $2$ then the signum is $- 1$ , otherwise it is $+ 1$ . For $n > 4$ , the number $n!$ is divisible by four, so $n! - 1$ leaves a remainder of $- 1$ on division by four (more properly said, a remainder or $3$ ), and so the signum is $+ 1$ . The $n = 1$ case has a signum of $+ 1$ , the $n = 2$ case has a signum of $- 1$ and the $n = 3$ case has a signum of $- 1$ .

Problem 5

Prove these.

Every permutation has an inverse.
$sgn (ϕ^{- 1}) = sgn (ϕ)$
Every permutation is the inverse of another.

Answer

Permutations can be viewed as one-one and onto maps $ϕ : {1, \dots, n} \to {1, \dots, n}$ . Any one-one and onto map has an inverse.
If it always takes an odd number of swaps to get from $P_{ϕ}$ to the identity, then it always takes an odd number of swaps to get from the identity to $P_{ϕ}$ (any swap is reversible).
This is the first question again.

Problem 6

Prove that the matrix of the permutation inverse is the transpose of the matrix of the permutation $P_{ϕ^{- 1}} = {P_{ϕ}}^{t r a n s}$ , for any permutation $ϕ$ .

Answer

If $ϕ (i) = j$ then $ϕ^{- 1} (j) = i$ . The result now follows on the observation that $P_{ϕ}$ has a $1$ in entry $i, j$ if and only if $ϕ (i) = j$ , and $P_{ϕ^{- 1}}$ has a $1$ in entry $j, i$ if and only if $ϕ^{- 1} (j) = i$ ,

This exercise is recommended for all readers.

Problem 7

Show that a permutation matrix with $m$ inversions can be row swapped to the identity in $m$ steps. Contrast this with Corollary 4.6.

Answer

This does not say that $m$ is the least number of swaps to produce an identity, nor does it say that $m$ is the most. It instead says that there is a way to swap to the identity in exactly $m$ steps.

Let $ι_{j}$ be the first row that is inverted with respect to a prior row and let $ι_{k}$ be the first row giving that inversion. We have this interval of rows.

(\begin{matrix} ⋮ \\ ι_{k} \\ ι_{r_{1}} \\ ⋮ \\ ι_{r_{s}} \\ ι_{j} \\ ⋮ \end{matrix}) j < k < r_{1} < \dots < r_{s}

Swap.

(\begin{matrix} ⋮ \\ ι_{j} \\ ι_{r_{1}} \\ ⋮ \\ ι_{r_{s}} \\ ι_{k} \\ ⋮ \end{matrix})

The second matrix has one fewer inversion because there is one fewer inversion in the interval ( $s$ vs. $s + 1$ ) and inversions involving rows outside the interval are not affected.

Proceed in this way, at each step reducing the number of inversions by one with each row swap. When no inversions remain the result is the identity.

The contrast with Corollary 4.6 is that the statement of this exercise is a "there exists" statement: there exists a way to swap to the identity in exactly $m$ steps. But the corollary is a "for all" statement: for all ways to swap to the identity, the parity (evenness or oddness) is the same.

This exercise is recommended for all readers.

Problem 8

For any permutation $ϕ$ let $g (ϕ)$ be the integer defined in this way.

g (ϕ) = \prod_{i < j} [ϕ (j) - ϕ (i)]

(This is the product, over all indices $i$ and $j$ with $i < j$ , of terms of the given form.)

Compute the value of $g$ on all $2$ -permutations.
Compute the value of $g$ on all $3$ -permutations.
Prove this.
$sgn (ϕ) = \frac{g (ϕ)}{| g (ϕ) |}$

Many authors give this formula as the definition of the signum function.

Answer

First, $g (ϕ_{1})$ is the product of the single factor $2 - 1$ and so $g (ϕ_{1}) = 1$ . Second, $g (ϕ_{2})$ is the product of the single factor $1 - 2$ and so $g (ϕ_{2}) = - 1$ .
$\begin{matrix} permutation ϕ & ϕ_{1} & ϕ_{2} & ϕ_{3} & ϕ_{4} & ϕ_{5} & ϕ_{6} \\ g (ϕ) & 2 & - 2 & - 2 & 2 & 2 & - 2 \end{matrix}$
Note that $ϕ (j) - ϕ (i)$ is negative if and only if $ι_{ϕ (j)}$ and $ι_{ϕ (i)}$ are in an inversion of their usual order.

References

Strang, Gilbert (1980), Linear Algebra and its Applications (2nd ed.), Hartcourt Brace Javanovich