This set of exercises is retrieved from the second chapter of Linear Algebra by Robert J. Valenza. Note that these solutions are not fully elaborated; You have to fill the descriptions by yourself.
Problem 1.1
Find the sets \(S,\) \(T\) and \(U\) and functions \(f: S \rightarrow T\) and \(g: T \rightarrow U\) such that \(g \circ f\) is injective, but \(g\) is not injective.
Solution. Take \(S = U = \left\{ 1 \right\} ,\,\, T = \left\{ 0,\,1 \right\},\) and \(f(s) = 1 ,\,\, g(t) = 1\) for all \(s\in S\) and \(t \in T.\)
Problem 1.2
Find sets \(S,\) \(T\) and \(U\) and functions \(f : S \rightarrow T\) and \(g: T \rightarrow U\) such that \(g \circ f\) is surjective, but \(f\) is not surjective.
Solution. Same as Problem 1.1.
Problem 1.3
Find a non-identity function \(\mathbb{R} \rightarrow \mathbb{R}\) which is its own inverse function. That is, \(f \circ f = 1_\mathbb{R}\) or, equivalently, \(f(f(x)) = x\) for all real \(x.\)
Solution. Take \(f(x) = -x.\)
Problem 1.4
Assess the injectivity and surjectivity of each of the following functions from \(\mathbb{R}\) to \(\mathbb{R}.\) Be sure to defend your responses rigorously. For example, to show that a function is bijective, you might exhibit the inverse function. You might also deduce valuable information by sketching the graph as you did in calculus.
- \(f(x) = 2x+1\)
- \(f(x)=x^3 - 3x\)
- \(f(x)=e^x\)
- \(f(x)=x^4 -2x^2\)
- \(f(x)=e^{-x^2}\)
Solution.(Defending is skipped.)
- Bijective.
- Surjective, but not injective.
- Injective, but not surjective.
- Not injective nor surjective.
- Not injective nor surjective.
Problem 1.5
Find the bijective map from the open interval \((-\pi /2 ,\, + \pi /2 )\) to the set \(\mathbb{R}\) of real numbers. This shows, by the way, that both sets have the same cardinality.
Solution. Take \(f(x) = \tan x .\)
Problem 1.6
Explicitly construct a bijective function from the set of integers \(\mathbb{Z}\) to the set of even integers \(2\mathbb{Z}.\) Despite your naive intuition to the contrary, this shows that \(\operatorname{Card}(\mathbb{Z}) = \operatorname{Card}(2\mathbb{Z}).\)
Solution. Take \(f(x) =2x.\)
Problem 1.7
Prove that if \(\operatorname{Card}(S) = \operatorname{Card}(T)\) and \(\operatorname{Card}(T) = \operatorname{Card}(U),\) then \(\operatorname{Card}(S) = \operatorname{Card}(U).\)
Solution. The composition of two bijective functions is a bijective function.
Problem 1.8
Let \(\mathbb{N} \times \mathbb{N}\) denote the set of all ordered pairs \((m,\,n)\) of natural numbers. Show that \(\operatorname{Card}(\mathbb{N} \times \mathbb{N}) = \operatorname{Card}(\mathbb{N})\) by explicitly constructing a bijection \(\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}.\)
Solution. Take the function \(f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) as \[f(m,\,n) = \frac{(m+n-2)(m+n-1)}{2} +n,\] provided that \(\mathbb{N} = \left\{ 1,\,2,\,3,\,\cdots \right\}.\)
Problem 1.9
Express the following composition of cycles in matrix notation.
\[\left( 1\quad 4\quad 7\quad 6 \right) \circ \left( 2 \quad 7 \quad 5 \right)\]
Be sure to work from right to left.
Solution. \[\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 6 & 3 & 7 & 2 & 1 & 5 \end{matrix} \right). \]
Problem 1.10
Decompose the following permutation into the product of disjoint cycles.
\[\pi = \left(
\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
6 & 5 & 9 & 1 & 4 & 3 & 8 & 7 & 2
\end{matrix}
\right)
\]
Solution. \[\pi = \left( 1 \quad 6 \quad 3 \quad 9 \quad 2 \quad 5 \quad 4 \right) \circ \left(7 \quad 8\right). \]
Problem 1.11
How many reversals does the permutation \(\pi\) in the previous problem manifest? What is its sign? Factor \(\pi\) into the product of transpositions.
Solution. The number of reversals is \[5+4+6+0+2+1+2+1=21.\] Its sign is \(-1,\) that is, the parity of \(\pi\) is odd. \(\pi\) is factorized as \[\pi = \left ( 4 \quad 5 \right) \circ \left ( 4 \quad 2 \right) \circ \left ( 4 \quad 9 \right) \circ \left ( 4 \quad 3 \right) \circ \left ( 4 \quad 6 \right) \circ \left ( 4 \quad 1 \right) \circ \left ( 7 \quad 8 \right) ,\] the composition of SEVEN transpositions.
Problem 1.12
Referring to the permutation,
\[\pi = \left(
\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
8 & 1 & 3 & 6 & 4 & 5 & 7 & 2
\end{matrix}
\right).
\]
- Express \(\pi\) as the product of disjoint cycles.
- Express \(\pi\) as the product of transpositions.
- Compute the sign of \(\pi.\)
Solution. \[\begin{align} \pi &= \left( 1 \quad 8 \quad 2 \right) \circ \left( 4 \quad 6 \quad 5 \right) \\[7pt] &= \left( 1 \quad 2 \right) \circ \left( 1 \quad 8 \right) \circ \left( 4 \quad 5 \right) \circ \left( 4 \quad 6 \right) . \end{align}\] The sign of \(\pi\) is \(1,\) that is, \(\pi\) is an even permutation.
Problem 1.13
Let \(\pi \in S_n\) be a \(k\)-cycle. For which positive integers \(m\) is \(\pi ^m\) equal to the identity map? Here \(\pi^m\) means \(\pi\) composed with itself \(m\) times.
Solution. \(m\) has to be a multiple of \(k.\)
Problem 1.14
Suppose that for permutations \(\pi\) and \(\tau\) in \(S_n ,\) \(\pi \circ \tau = \tau \circ \pi .\) (Recall that this is not in general true.) Show that for all positive integer \(n,\) \((\pi \circ \tau )^n = \pi^n \circ \tau^n .\)
Solution. Use mathematical induction for \(n.\)
Problem 1.15
Show that disjoint cycles commute; that is, if \(\pi\) and \(\tau\) are cycles with no elements in common, then \(\pi \circ \tau = \tau \circ \pi .\)
Solution. First prove commutativity for two disjoint transpositions. Next, express \(\pi\) and \(\tau\) as transpositions and prove commutativity. In the process, you can use mathematical induction.
Problem 1.16
Recall that every permutation may be written as the product of disjoint cycles. Using this fact and the previous three exercises, show that \(\pi ^{n!}\) is the identity map for any permutation \(\pi\) in \(S_n .\)
Solution. Let \(\pi\) be the product of disjoint \(m\) cycles \[\pi = \pi_1 \circ \pi_2 \circ \cdots \circ \pi_m ,\] where each \(\pi_i\) is a \(k_i\)-cycle. Because each \(k_i\) divides \(n! ,\) \({\pi_i}^{n!}\) is the identity map.
As a consequence, we have \[\pi ^{n!} = {\pi_1}^{n!} \circ {\pi_2}^{n!} \circ \cdots \circ {\pi_m}^{n!} ,\] that is, \(\pi^{n!}\) is a composition of the identity maps, thus it is the identity map.
Problem 1.17
We showed above that for transpositions \(\tau_1 ,\) \(\tau_2 ,\) \(\cdots ,\) \(\tau_m \)
\[\sigma \left( \tau_1 \circ \tau_2 \circ \cdots \circ \tau_m \right) = (-1)^m\]
and also that every permutation is the product of transpositions. Use this two facts to prove that for all permutations \(\pi_1\) and \(\pi_2 ,\)
\[\sigma \left( \pi_1 \circ \pi_2 \right) = \sigma \left( \pi_1 \right) \sigma \left( \pi_2 \right).\]
Solution. Express \(\pi_2\) as a product of transpositions \[\pi_2 = \tau_1 \circ \tau_2 \circ \cdots \circ \tau_m ,\] and use mathematical induction for \(m.\)
Problem 1.18
Show that if \(S\) and \(T\) are nonempty sets, then \(\operatorname{Card}(S \times T) = \operatorname{Card}(T \times S).\)
Solution. Define \(f : S \times T \rightarrow T \times S\) by \(f(s,\,t) = (t,\,s)\) then \(f\) is a bijective function.
Problem 1.19
Let \(S,\) \(S ' ,\) \(T ,\) \(T ' \) be sets such that \(S\) and \(T\) are disjoint, as are \(S ' \) and \(T ' .\) Assume further that
\[\operatorname{Card}(S) = \operatorname{Card}(S ' ) \quad\text{and}\quad\operatorname{Card}(T) = \operatorname{Card}(T ' ).\]
Show that \[\operatorname{Card}(S\cup T) = \operatorname{Card}(S ' \cup T ' ).\] Note that this result extends easily to arbitrary disjoint unions (possibly involving an infinite family of disjoint sets.)
Solution. By the definition, there are two bijective functions \(f : S \rightarrow S ' \) and \(g : T \rightarrow T ' .\)
Define \(\phi : S \cup T \rightarrow S ' \cup T ' \) by \[\phi(x) = \begin{cases} f(x) \quad &\text{if} \,\, x \in S \\[7pt] g(x) \quad &\text{if} \,\, x \in T. \end{cases}\]
Then \(\phi\) is a bijective function from \(S \cup T\) to \(S ' \cup T ' .\)Problem 1.20
Let \(S\) and \(T\) be nonempty sets. Show that there exist sets \(S ' \) and \(T ' \) such that
\[\operatorname{Card}(S) = \operatorname{Card}(S ' ) \quad\text{and}\quad \operatorname{Card}(T) = \operatorname{Card}(T ' )\]
with \(S ' \) and \(T ' \) disjoint.
Solution. Take \(S ' = S \times \left\{ 0 \right\}\) and \(T ' = T \times \left\{ 1 \right\}.\)
Problem 1.21
Prove Schröder–Bernstein theorem, that is, if \(X\) and \(Y\) are sets and both
\[\operatorname{Card}(X) \le \operatorname{Card}(Y) \quad\text{and}\quad \operatorname{Card}(X) \ge \operatorname{Card}(Y)\]
hold, then \(\operatorname{Card}(X) = \operatorname{Card}(Y).\)
Solution. See a kind and nice explanation: Click here.